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!)
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]
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.
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.
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,
[x2, y2], and
[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]
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
Every 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.