Beziers

Beziers are easy-to-define curves. Since one of their applications is in computer graphics, they were covered at GDC 09 by Squirrel Eiserloh. Squirrel, by the way, gives a great presentation, and I’m cribbing a lot from the approach his presentation used. (Here‘s a presentation on interpolating position, but it’s not the one Squirrel used at GDC).

This article covers the just the beginning of Squirrel’s talk. I will probably cover more of it later. (In this article, I don’t even tell you what a Spline is!)

Linear Beziers

All Bezier curves can be thought of as ways of describing the motion of a virtual pen as it travels from one point to another. In its simplest form, the path from the start point to the endpoint is a straight line. To describe a point moving along a line, you take a weighted average of the two endpoints.

In the beginning, time 0, the pen is at the start point, [x1, y1]. At time 1, it’s at the end, or [x2, y2]. At time 0.5, at the midpoint: [(0.5)x1 + (0.5)x2, (0.5)y1 + (0.5)y2]. To find where you are at any other time t between 0 and 1:

[(1-t)x1 + (t)x2, (1-t)y1 + (t)y2]

linear-spline1

As t moves from 0 to 1, the pen’s position moves from the starting point to the endpoint. This sliding weighted averaging is yet another example of linear interpolation, which was almost the title of this article.

Quadratic Beziers

This step contains the critical idea, which lets you build higher-order Beziers out of smaller ones. The technique for drawing quadratic Beziers is to is linearly interpolate between a starting point and an endpoint, just as above, except that this time the start point and the endpoint are moving. They have their own start points and endpoints, and use linear interpolation as above.

quadratic-spline-1

As you can see here, the start point ends at the same place the end point begins.

Let’s call the start point [xa, ya] and the end point [xb, yb]. Then the path the pen follows is this:

[(1-t)xa + (t)xb, (1-t)ya + (t)yb]

Since the start point and the end point are moving themselves, xa (and the rest of those) are variable, not constant. Their movement is described in terms of their start points and endpoints, [x1, y1], [x2, y2], and [x3, y3].
quadratic-spline-2

[xa, ya] = [(1-t)x1 + (t)x2, (1-t)y1 + (t)y2]
[xb, yb] = [(1-t)x2 + (t)x3, (1-t)y2 + (t)y3]

The the position of the pen at time t comes from substituting these:
[(1-t)((1-t)x1 + (t)x2) + (t)((1-t)x2 + (t)x3),

(1-t)((1-t)y1 + (t)y2) + (t)((1-t)y2 + (t)y3)]

=[(1-t)2x1 + 2(t)(1-t)x2 + t2x3,

(1-t)2y1 + 2(t)(1-t)y2 + t2y3]

bezier_2_big
quadratic-spline-3

Cubic Beziers and beyond

The key idea was taking two Beziers, in this case linear, and interpolating between them to create a meta-Bezier, in this case a quadratic Bezier. You can use this idea to make a Bezier out of four points instead of three, by making a quadratic Bezier out of the first three points, then another quadratic out of the last three, and interpolating between those two to get a cubic Bezier. This is the most common kind of Bezier in computer graphics. Here’s the math, sans motivation:

[(1-t)3x1 + 3(t)(1-t)2x2 + 3(t)2(1-t)x3 + t3x4,

(1-t)3y1 + 3(t)(1-t)2y2 + 3(t)2(1-t)y3 + t3y4]

This image stolen from wikipedia

This image stolen from wikipedia

 


fuzzyEvery GDC article I write has the goal of helping us do a better job at IMVU. Since I want my articles to be relevant to a wider audience, I’m separating out the IMVU tie-ins. What follows is the IMVU-centric section of this post, which won’t be relevant to everyone. For the rest of you, please enjoy the fuzzy kitten.

 

How can we use this at IMVU? Since most of our art is user-generated, it’s the content creators, not us, who would want to learn about splines if they wanted to incorporate moving parts. I expect that they already have tools that handle this kind of math for them. But there’s another use – the particle system. Beziers – and later, splines – provide a simple, intuitive way to let users define curves. Just place and drag around the control points, and the particles know how to curve from the beginning to the end. There might be a good way to expose Bezier controls to content creators to help them define particles in their furniture or clothes.

About these ads

7 Responses to Beziers

  1. Ben says:

    This one is one of my favorites since it’s both relatively simple, and in a sense is a recursive solution in that to get an nth-Bezier you build it out of (n-1)-Beziers.

    So many cool mathematically-sound shortcuts abound in computer graphics! This field is by far one of my favorite subjects in computer science since I’m both a visual learner and math-y. I’d be working in the field if success in it wasn’t as depending on the knowledge of low-level hardware optimizations. I suck at those.

    Incidentally, those of you who build splines with Photoshop or Gimp should now have a much better grasp on what those bells and whistles on your line anchors are doing! (you’re changing the start/end points of “sub-beziers”)

  2. Chad says:

    Why are cubic more common than quadratic?

    • joblivious says:

      Because of how they behave when you string a lot of them together end-to-end. If you know the tricks, you can shift a couple control points around without breaking the slope continuity from one Bezier to the next and without changing any but two neighboring Beziers. (I think)

      Also, the first graphic is wrong. It says (t-1) where it should say (1-t). I’ll fix it tomorrow.

  3. Salman says:

    wow,,, I couldn’t understand a word :-D but it’s nice to see these kind of blogs also exist ;-)

  4. […] Beziers Beziers are easy-to-define curves. Since one of their applications is in computer graphics, they were covered at GDC 09 […] […]

  5. […] Beziers « Integrable Is A Word (tags: math) […]

Leave a Reply

Fill in your details below or click an icon to log in:

WordPress.com Logo

You are commenting using your WordPress.com account. Log Out / Change )

Twitter picture

You are commenting using your Twitter account. Log Out / Change )

Facebook photo

You are commenting using your Facebook account. Log Out / Change )

Google+ photo

You are commenting using your Google+ account. Log Out / Change )

Connecting to %s

Follow

Get every new post delivered to your Inbox.

%d bloggers like this: