Home :: Tutorials :: Geometry

1. Convex Hulls and Mid-Points
2. Plotting the Rest of the Curve
3. Example of Potential Use

## Introduction

Bezier curves are an invaluable tool for anyone working in computer graphics. My first introduction to these curves was in Adobe® Illustrator® and in PostScript. To my surprise, these complex curves can be plotted using a simple geometric approach. This tutorial describes this approach for rendering 3'rd order Bezier curves.

At the end of this discussion, an example shows how the control points of a <path> element can be animated along another path.

## Convex Hulls and Mid-Points

To describe the curve, the user places four points called control points. The curve passes through the first and fourth control points. The second and third control points act as magnets for the curve. The curve never actually passes through these points.

Now we find a single point on the curve using these four control points. First, we draw the convex hull of the curve by connecting the control points in the order they were drawn.

Find the midpoint of each line segment that we drew.

Connect these points to form a new hull.

Find the midpoint of each of these new line segments.

Connect these two points.

Finally, find the midpoint. This is the point found at the middle of the curve.

The last line used here is a tangent to the point found on the Bezier curve. This tangent can be used to calculate a stroke for the final curve.

As seen in the examples below, I've added perpendicular lines to each point found in the curve. If you imagine connecting all of the line endpoints by traversing them in a clockwise or counter-clockwise order, you can see that a thicker (or stroked) version of the skeleton Bezier will result.

## Plotting the Rest of the Curve

#### Points Other Than the Mid-Point

In the previous section, we found the midpoint of the approximated Bezier curve. It is also possible to find other points along the curve. For example, If you found the point 25% along each line, then you will end up with a point 25% into the Bezier curve. Note that this is not exactly true, but this will work for our needs. You can use a loop to find various points along the curve and then connect these points to approximate the original Bezier curve.

The image to the right connects 14 points on two different curves using this method.

#### Recursion with Depth

Another approach involves defining the point-finding function recursively. If you look at the final image from the first section, you can see that seven internal red boxes can be made into two hulls similar to the initial hull. One appears to the left of the final point and one appears to the right. Each of these hulls can be used just like the first to find new mid-points. This process continues to a programmer defined depth.

The image to the right draws two curves using 3 levels of recursion. This results in curves with 16 segments.

#### Recursion with Flatness

A variation of the recursive method determines if a segment can be approximated with a straight line given a certain tolerance (need diagram here). Imagine drawing a line between the first and the last control point. If the distance from the second control point to this line and the distance of the third control point to this line are below the flatness level, then that curve can be approximated with a straight line.

This method is perhaps one of the best approaches for drawing a Bezier curve since the algorithm adjusts the number of segments needed to best represent the curve within the given tolerance.

The image to the right uses a flatness of 4. Notice that more segments are used in the first curve where the curve turns sharply. Also notice how the second curve has fewer segments than the other two methods. This differs from the first two methods which will always use the same number of segments regardless of a curve's complexity.

## Example of Potential Use

SVG includes a very powerful and flexible ability to create animations. However, at times it is necessary to animate various points of a shape along their own paths. Morphing between two shapes is an example. Short of defining a large series of intermediate shapes to cycle through in your animation, SVG does not directly support this functionality.

The following example uses the Node_Builder, Scheduler, and Bezier JavaScript objects to animate the second and third control points of a path along separate Bezier paths. In a familiar format, I have drawn handles (grey lines with a red circle) from the first control point to the second control point and from the fourth control point to the third control point. The grey curves show the Bezier paths that the second and third control points will follow. In order to move these control points along those paths, we must travel along the curves in a step-wise fashion. This is where we can apply our drawing methods to calculate points along the Bezier curves. The first drawing method allows us to calculate any point on the curve based on a percentage. This is exactly what we need for this animation. We simply move from 0% to 100% along the Bezier curve and back. These calculated values are then fed back into the second and third control points of the original curve (green curve on top) to create the animation.

Right-click or control-click the image and View Source to see the complete details of how this SVG has implemented the functionality. Please have a look at Morphius for an encapsulated version of this code.