Curves in all the right places

on
Curves are now my latest favourite thing

For my latest game I need to implement smooth curves that pass through points in the screen.
With my basic knowledge of curves I know there are definitely many functions to choose from but for the purposes of this article I'm going to stick to 2
  • Catmull Rom Spline curves
  • Bezier Curves

There are 2 distinct differences between the 2. Catmull Rom Spline curves (or CRS curves from now in) pass through each point. To control the curve you move the points.
Bezier on the other hand, while connecting 2 points the steepness and curve are generated by 2 other control points. So essentially, Bezier doesnt pass through all the points.

Each one has its advantages and disadvantages, but both are perfect for gamedev.

Building the class

Let's start by building a point class..

Class Point
  Field x:Float
  Field y:Float
end

Catmull Rom Spline

WIKI

Here it is in equation form:
q(t) = 0.5 * (1.0f,t,t*t,t*t*t) * [ 0, 2, 0, 0] [P0]
                                  [-1, 0, 1, 0]*[P1]
                                  [ 2,-5, 4,-1] [P2]
                                  [-1, 3,-3, 1] [P3]

Where (t) is any point on the line  0.0 < t < 1.0

Sticking this into the point class gives us this:
Class Point
  Field x:Float
  Field y:Float

   Method CatmullRomSplinePoint:Void(t:Float,p0:Point,p1:Point,p2:Point,p3:Point)
    x = 0.5 *( (2 * p1.x) + (-p0.x + p2.x) * t + (2*p0.x - 5*p1.x + 4*p2.x - p3.x) * Pow(t,2) + (-p0.x + 3*p1.x- 3*p2.x + p3.x) * Pow(t,3) )
    y = 0.5 *( (2 * p1.y) + (-p0.y + p2.y) * t + (2*p0.y - 5*p1.y + 4*p2.y - p3.y) * Pow(t,2) + (-p0.y + 3*p1.y- 3*p2.y + p3.y) * Pow(t,3) )
  End
End

Lets use this class to draw a point from point B to C (CRS uses points A and D to created a seamless line between segments)

Now let's cycle through all the points to draw a continuous line.

Now lets add some randomness

Nice!

Bezier Curves

WIKI. Bezier curves uses 2 extra points to control the curve.

The equation for Bezier is as follows..
P = (1−t)3P1 + 3(1−t)2tP2 +3(1−t)t2P3 + t3P4

And here it is in our class
Method BezierPoint:void(t:Float,p0:Point,p1:Point,p2:Point,p3:Point)
  Local u:Float = 1-t;
  Local t2:Float = t*t;
  Local u2:Float = u*u;
  Local u3:Float = u2 * u;
  Local t3:Float = t3 * t;


   x = u3 * p0.x + 3 * u2 * t * p1.x + 3 * u * t2 * p2.x + t3 * p3.x
  y = u3 * p0.y + 3 * u2 * t * p1.y + 3 * u * t2 * p2.y + t3 * p3.y
End

Now when we draw from point A to B and use control points Ab and Bb we get the following.

If we continue and draw from A to D using control points Ab, Bb, Cb and Db we get more curves

Note that sharp change in direction. That is because the control point for A is always Ab, Bb is for point B etc. That means the curve is always influenced by that one control point in one direction. 

For the curve to pass smoothly through B it would need to influenced by Bb from one side and then influenced by Bb+180° on the other

We can quickly add 180° to the control point by inverting the difference between control point and point
New control point = p - ( cp -p)
Let's create a new method for BezierSmooth using the same points.
Method BezierPointSmooth:Void(t:Float,p0:Point,p1:Point,p2:Point,p3:Point)

  Local p:Point = New Point()
  p.x = p3.x - (p2.x - p3.x)
  p.y = p3.y - (p2.y - p3.y)

   Local u:Float = 1-t;
  Local t2:Float = t*t;
  Local u2:Float = u*u;
  Local u3:Float = u2 * u;
  Local t3:Float = t3 * t;


   x = u3 * p0.x + 3 * u2 * t * p1.x + 3 * u * t2 * p.x + t3 * p3.x
  y = u3 * p0.y + 3 * u2 * t * p1.y + 3 * u * t2 * p.y + t3 * p3.y
end

In that method we 'invert' the 2nd control point and use it in the equation.
Now we get this using the same data:
Nice!

Let's add some movement in the control points.

What's the cost?

In my tests of my implementation, Bezier curves are 30% faster to implement. Obviously it doesn't mean they are better. While Bezier are faster and more fun, Catmull Rom Spline can give you more predictable results as each point is passed with no extra control points.

Comments

Post a Comment