Drawing a Continuous Bezier Curve
Articles —> Drawing a Continuous Bezier Curve
A Bezier Curve is a parametric smooth curve generated from two end points and one or more control points, points which may not necessarily fall on the curve but whose position is used to calculate the path of the curve. There are different types of Bezier curves, in particular the quadratic and cubic Bezier curves, each of which uses a different number of control points. Shown below is an example of a cubic Bezier Curve with it's two end points (P0 and P3) and control points P1 and P2:
The cubic Bezier Curve is given by the following equation...
B(t) = (1 - t)3P0 + 3(1-t)2tP1 + 3(1-t)t2P2 + t3P3
...where t is a fractional value along the length of the line (0 <= t <= 1). To draw a line using this equation, one can divide the curve into smaller segments, calculate the end points of each segment using the Bezier cubic equation and draw the line for the segment. For instance, one can draw a line between the points defined by t = 0 and t = 0.01, then t = 0.01 and t = 0.02, and so on.
The Bezier equations are useful for a small set of points, however one may often be required to draw a smooth curve between a larger, unknown number of points. Given the Bezier equations constrain the math to a small set (1 or 2) of control points, we are forced to adapt an algorithm from these equations useful for a larger and potentially variable set of points. For example, we can break up our set of points into smaller, more manageable bezier curves, all of which share an endpoint with its immediate neighbor. However, if we simply connect each curve in this manner we end up with two curves that may often have a jagged transition. Consider two sets of four points A0 - A3 and B0 - B3, each defining its own cubic Bezier curve (A3 = B0):
Two consecutive cubic Bezier curves. Note the non-continuous behavior of the end point of curve one (green) and start point of curve 2 (blue).
What is going on here? If we think about this mathematically, the slope at the end of curve one (A) is different than that of curve two (B). In other words, the gradients of the curves where they meet differ (in this case, drastically), resulting in a seemingly jagged intersection at B0A3.
There is a way to rectify this behavior - enforce the rule that the gradients at the start and end of each consecutive curves are the same. Recall from calculus that, to determine the gradient of a curve, we can take the first derivative:
B'(t) = 3(1 - t)2(P1 - P0) + 6(1-t)t(P2 - P1) + 3t2(P3 - P2)
Given we are thinking about the gradients being equal at the end of curve one and beginning of curve 2, we can use the above equations where t = 0 (beginning) and t = 1 (end). Consider two curves with points A0-A3 and B0-B3
B'B(0) = 3(1 - 0)2(B1 - B0) + 6(1-0)0(B2 - B1) + 302(B3 - B2)
= 3(B1 - B0)
B'A(1) = 3(1 - 1)2(A1 - A0) + 6(1-1)1(A2 - A1) + 3(1)2(A3 - A2)
= 3(A3 - A2)
How can we enforce these to be equal as we construct our curves? Conceptually, we can think of the end/start points between curves as a new control point rather than an end point. But if these are control points, we need new start/end points. Mathematically, if we want the gradients to be equal we equate the two gradient equations above:
3(B1 - B0) = 3(A3 - A2)
B1 - B0 = A3 - A2
Solving for B0:
B0 = B1 - A3 + A2
But wait, B0 and A3 are the end point, which are equal, thus
B0 + A3 = B1 + A2
2(B0) = B1 + A2
B0 = (B1 + A2)/2
This is just the midpoint between B1 + A2. Thus, we can use the midpoints between the true values as start/end-points for our continuous Bezier curve. Using the above example of A and B points, along with the calculated midpoints, we end up with three Bezier curves:
Continuous Bezier Curve using Midpoints.
Thus, the algorithm to draw a continuous curve based upon a set S of n points would be to calculate the midpoint for every pair of points in S, inserting the midpoint between the parent points (one can exclude the first and last set of points, but for simplicity we will do so for all pairs). The resulting set can then be used to draw several consecutive Bezier curves, resulting in a seemingly continuous curve. Below is an implementation of this algorithm in Java - generating both the midpoints as well as the segment points along the curve, dependent upon both a given increment of t and an array of Points which constitute the end and control points of the curve.
/** * Generates several 3D points in a continuous Bezier curve based upon * the parameter list of points. * @param controls * @param detail * @return */ public static Tuple3d[] getCurvePoints(Tuple3d[] controls, double detail){ if ( detail > 1 || detail < 0 ){ throw new IllegalStateException(""); } List<Tuple3d> renderingPoints = new ArrayList<Tuple3d>(); List<Tuple3d> controlPoints = new ArrayList<Tuple3d>(); //generate the end and control points for ( int i = 1; i < controls.length - 1; i+=2 ){ controlPoints.add(center(controls[i-1], controls[i])); controlPoints.add(controls[i]); controlPoints.add(controls[i+1]); if ( i+2 < controls.length - 1 ){ controlPoints.add(center(controls[i+1], controls[i+2])); } } //Generate the detailed points. Tuple3d a0, a1, a2, a3; for ( int i = 0; i < controlPoints.size() - 2; i+=4 ){ a0 = controlPoints.get(i); a1 = controlPoints.get(i+1); a2 = controlPoints.get(i+2); if ( i + 3 > controlPoints.size() - 1 ){ //quad for ( double j = 0; j < 1; j += detail){ renderingPoints.add(quadBezier(a0,a1,a2,j)); } }else{ //cubic a3 = controlPoints.get(i+3); for ( double j = 0; j < 1; j += detail){ renderingPoints.add(cubicBezier(a0,a1,a2,a3,j)); } } } Tuple3d[] points = new Tuple3d[renderingPoints.size()]; renderingPoints.toArray(points); return points; } /** * A cubic bezier method to calculate the point at t along the Bezier Curve give * the parameter points. * @param p1 * @param p2 * @param p3 * @param p4 * @param t A value between 0 and 1, inclusive. * @return */ public static Tuple3d cubicBezier(Tuple3d p1, Tuple3d p2, Tuple3d p3, Tuple3d p4, double t){ return new Tuple3d( cubicBezierPoint(p1.x, p2.x, p3.x, p4.x, t), cubicBezierPoint(p1.y, p2.y, p3.y, p4.y, t), cubicBezierPoint(p1.z, p2.z, p3.z, p4.z, t)); } /** * A quadratic Bezier method to calculate the point at t along the Bezier Curve give * the parameter points. * @param p1 * @param p2 * @param p3 * @param t A value between 0 and 1, inclusive. * @return */ public static Tuple3d quadBezier(Tuple3d p1, Tuple3d p2, Tuple3d p3, double t){ return new Tuple3d( quadBezierPoint(p1.x, p2.x, p3.x, t), quadBezierPoint(p1.y, p2.y, p3.y, t), quadBezierPoint(p1.z, p2.z, p3.z, t)); } /** * The cubic Bezier equation. * @param a0 * @param a1 * @param a2 * @param a3 * @param t * @return */ private static double cubicBezierPoint(double a0, double a1, double a2, double a3, double t){ return Math.pow(1-t, 3) * a0 + 3* Math.pow(1-t, 2) * t * a1 + 3*(1-t) * Math.pow(t, 2) * a2 + Math.pow(t, 3) * a3; } /** * The quadratic Bezier equation, * @param a0 * @param a1 * @param a2 * @param t * @return */ private static double quadBezierPoint(double a0, double a1, double a2, double t){ return Math.pow(1-t, 2) * a0 + 2* (1-t) * t * a1 + Math.pow(t, 2) * a2; } /** * Calculates the center point between the two parameter points. * @param p1 * @param p2 * @return */ public static Tuple3d center(Tuple3d p1, Tuple3d p2){ return new Tuple3d( (p1.x + p2.x) / 2, (p1.y + p2.y) / 2, (p1.z + p2.z) / 2 ); }
In the above code, there are five accessory methods which implement the cubic and quadratic Bezier equations as well as a method to locate the center point. Also note the accessory Tuple3d class, a class described in my Rubiks Cube article.
As a demonstration of this technique, the image below is the visualization of the Lorenz Attractor. The Lorenz Attractor generates a series of points, which were plotted as a continuous curve based upon the midpoint continuous Bezier curve.
Comments
- Para Parasolian - October, 3, 2016
Hi
Thanks for your article. Could you pl. clarify the use of 3D points in the code whereas you use only 2D points in the article.
Thanks.
- Prabakaran d - September, 17, 2017
What is the reason for its smoothness compared to cubic spline curves?
1. higher order derivatives
2. control points
3.curve passes through all the data points
4. All the above