Bezier Curves in Games (Part 3)

Bezier Curves in Games (Part 2)

In previous section, we talked about what is Bézier Curves, what are the various applications area, and how to write functions for generating control points for linear and bilinear curves. 

Lets now see how we can write code for Cubic Bézier Curves

                                             B(t) = (1−t)3 P0 + 3(1−t)2t P1 + 3(1−t)t2 P2 + t3 P3

Cubic Bézier Curves are 3rd degree curves to explain this type curve, you will need to specify four points.

• Two anchor points (say P1 and P2) these are the starting and ending points of the cubic curve.
• Two control points (say C1 and C2) these are control points which tells curve how fast or slow curve should leave these points.

Above image shows the basic Cubic Bézier Curve example. Artists who use Adobe Illustrator or Macromedia Freehand will recognise a cubic curve.

and who don't understand what I am talking about the will understand eventually as will will proceed forward.

So next thing is how can we find point on Cubic Bézier Curve. To achieve this we can use de Casteljau algorithm. Which is named after engineer Paul de Casteljau (born 1930 in Besancon, France) he developed this algorithm for evaluating calculations on certain family of curves, which later popularized by engineer Pierre Bézier.

This algorithm is widely used, with some modifications, as it is robust an numerically stable method for evaluating polynomials. So lets find the points.

Finding points on a Bézier curve using de Casteljau algorithm

Each point of a cubic Bezier point corresponds to a value between 0 and 1 for a parameter that will be noted with t in the followings. The de Casteljau algorithm consists of the following simple steps:

1. Consider a Bézier curve with control points . Connecting the consecutive points we create the control polygon of the curve.
2. Subdivide now each line segment of this polygon with the ratio  and connect the points you get. This way you arrive at the new polygon having one fewer segment.
3. Repeat the process until you arrive at the single point - this is the point of the curve corresponding to the parameter .

The following picture shows this process for a cubic Bézier curve:

Note that the intermediate points that were constructed are in fact the control points for two new Bézier curves, both exactly coincident with the old one. This algorithm not only evaluates the curve at , but splits the curve into two pieces at , and provides the equations of the two sub-curves in Bézier form.

The interpretation given above is valid for a non-rational Bézier curve. To evaluate a rational Bézier curve in , we may project the point into ; for example, a curve in three dimensions may have its control points  and weights  projected to the weighted control points . The algorithm then proceeds as usual, interpolating in . The resulting four-dimensional points may be projected back into three-space with a perspective divide.

In general, operations on a rational curve (or surface) are equivalent to operations on a non-rational curve in a projective space. This representation as the "weighted control points" and weights is often convenient when evaluating rational curves.

Here's the code to generate the points from the definition of the curve, we will use recursion for this, most of the code is self explanatory:

 // Calculate and Draw point from Casteljau Bezier algorithm   
  private void DrawCasteljau(List<point> points)   
  {   
  Point tempPoint;   
  for (double dt, dt <= 1; t += 0.001)   
  {   
    tempPoint = GetCasteljauPoint(points.Count-1, 0 , t);   
    image.SetPixel(tempPoint.X, tempPoint.Y, color);   
   }   
  }   
 // Calculate and Draw point from Casteljau Bezier algorithm  
 private void DrawCasteljau(List<point> points)  
 {  
  Point tempPoint;  
  for (double dt, dt <= 1; t += 0.001)  
  {  
     tempPoint = GetCasteljauPoint(points.Count-1, 0 , t);  
     image.SetPixel(tempPoint.X, tempPoint.Y, color);  
   }  
 }  

In if( r == 0) return points[i]; code line we are returning point value at index i. So, if r is 0 then it just return the point as is without calculation and if i == 5 then points[5] will return the point in the array that is at index.

Conclusion

Here we learned about Cubic Bézier Curves and how to find the points using  de Casteljau algorithm for such curves. In next blog will explore more and I will provide example unity project of  Bézier Curves written in C# language. I hope you got some more insight on Bézier Curves.

 References

1. http://en.wikipedia.org/wiki/B%C3%A9zier_curve
2. http://jeremykun.com/2013/05/11/bezier-curves-and-picasso/

Bezier Curves in Games (Part 1)

Bezier Curves are frequently used in computer graphics to produce curves which appear reasonably smooth at all scales as opposed to polygonal lines, which cannot scale as smoothly. Bezier curve have made programmers' lives easier because it is easy to use and above all they are pretty to look at.

They are the most fundamental curves for image processing and for generating computer graphics. They are used mainly to represent points, in approximations, curve fitting and for interpolation. Interpolation means Bezier curves are used to connect points together to form a smoother graphic. They are also used because they are easy to compute and they can be stitched together to form any shape that is wanted. 

Most of the time, using conventional/procedural graphic techniques are the best way to make  game features that give more control and make it outstanding. Here is a simple example of an animated river using Bezier curve in Unity3D, to give an idea about what type of graphical implementations we can produce using Bezier curves.

Animated River using Bezier curve (Unity Web Player Link) :-

Applications

Bezier curves are used in Games, Computer Graphics, Animations and Fonts. Here are some more details:-

• Games and Computer Graphics

• The Bezier curve is essential in allowing engineers, graphic designers, and architects to create images to represent the items they are making. Without the Bezier curve, it would be more difficult to draw or generate images with a computer.

• In all the games, we are using bezier curves directly or indirectly for many different things. It can describe paths and different shapes. For example fonts, vehicle design, drawing paths for various AI in games, dynamic rivers, roads etc.

• Vector graphics programs like Adobe Illustrator, Corel and Inskcape.

• Graphics Editing Softwares like Adobe Photoshop, GIMP, Pizap, Microsoft Publisher, Picasa

• 3D Modelling tools like Blender, Maya, 3DSMax many more

• Animation 

• In Animation applications like Adobe Flash and Synfig

• In 3D tools like Blender, Maya, 3DSMax,Unity3D to define 3D paths as well as 2D curves for keyframe interpolation.

• Fonts 

• Creating fonts or images is fairly simple with the aid of Bezier curves.

• Font engines like FreeType, draw the font's curves on pixelated surface in a process of font rasterization.

• Modern imaging systems like PostScript, Asymptote, Metafont aand SVG

• TrueType and OpenType fonts use these for different kinds of the fonts and flavours.

Understanding Bezier curves better

We all know what a curve is. Below are some examples of the curves in the diagram. Generally speaking, they are objects similar to a line but not necessarily straight.

Bezier Curve Definition

Bezier curve is a type of curve that is easy to use, and can form many shapes. 

Mathematically, Bezier curve can be defined by set of control points P0, P1, P2 through Pn, where n is called its order.
n = 1 for linear
n = 2 for quadratic
and so on.
In Bezier curves start point and end point are the main points.
The intermediate points generally do not lie on the curve, and the first and the last control points are always a part of the Bezier curve.

Here are some examples of valid Bezier curves:-

1. Curve without inflection and loop
2. Curve with inflection and without loop
3. Curve with loop
4. Curve with cusp
5. Curve with straight lines
6. Curve with parallel control points

So Bezier curve can be defined for any degree of n. So you can write a function to draw curve from 1 to infinity. Based on the order of curve or number of anchor points we can term curves by names like:-

Linear Bezier:
                                                                                         


Quadratic Bezier:
                                                                                              

Cubic Bezier:
                                                                                                    


5th Order Bezier
and so on...

When we're talking about Bezier curves, we're talking about the things that you can see in the following graphics. They run from some start point to some end point, with their curvature being influenced by one or more "intermediate" control points. 

The P0 and P2 are the startpoint and endpoint of the curve, and P1 is the control point of the Bezier curve. This curve does not pass through the control points. Here is a function that can be used to find the intermediate control point.

 

1 2 3 4 5

// Calculate the control point from two points private Vector3 FindControlPoint(Vector3 P0, Vector3 P1) { return new Vector3((p1.x + p2.x)/2,(p1.y + p2.y)/2); }

This function above is the basic building block of Bezier curves.

Here's the code to generate the points from the definition of the curve:

1 2 3 4 5 6 7

// Calculate point from quadratic Bezier expression private Vector3 QuadraticBezier(Vector3 P0, Vector3 P1, Vector3 C, float t) { float x = (1 - t) * (1 - t) * P0.x + (2 - 2 * t) * t * C.x + t * t * P1.x; float y = (1 - t) * (1 - t) * P0.y + (2 - 2 * t) * t * C.y + t * t * P1.y; return new Vector3(x, y); }

While implementing Bezier paths or creating Bezier curves you can speed up the development process by understanding the mathematical equations and then you can create your algorithm based on that. It is always suggested to draw the points, tangents or curves to debug the implementation.

Conclusion

These were the basics for the Bezier curve, In next blog we will dive into the code and implementation part, I will present Unity3D tutorial for using Bezier curve for 2D games like flight control and later on, we will proceed create a 3D example. I hope you got some ideas about Bezier applications area and implementation. 

References

1. http://en.wikipedia.org/wiki/B%C3%A9zier_curve
2. http://pomax.github.io/bezierinfo/