On-Line Geometric Modeling Notes

A Divide and Conquer Method for Curve Drawing

Overview

In the late 1960s, two European engineers independently developed a mathematical curve formulation which was extremely useful for modeling and design and also easily adaptable to use on a computer system. The primary feature of this method was that the controlling parameters of the curve were simply points in three-dimensional space, and each of these points had an influence on the curve. This curve, commonly called the Bézier curve, is the representation that is most frequently used in computer graphics and geometric modeling.

We present in these notes a form of the Bézier curve which can be developed through a simple divide-and-conquer, or subdivision method. This will not give us a rigorous definition of the Bézier curve, but will serve as motivation as it follows the general construction procedure for the curve.

To get a postscript version of these notes look here.

The Subdivision Procedure

This curve is defined by using three control points , , and . Whereas these points can be arbitrarily placed in three-dimensional space, we will illustrate the algorithm with the points below:

We will develop a method that uses these points to construct a curve. The curve will pass through the points and and will lie within the triangle . will be a control point that serves as a ``handle'' or a ``influence'' on the curve. Our general procedure will split the curve into two segments, each of which is again specified by three control points. With this procedure, we can recursively generate many small segments of the curve, which can be eventually approximated by straight lines when the curve is to be drawn. The procedure is quite simple, the most complicated mathematics being the calculation of midpoints of the lines connecting control points.

The Basic Subdivision Procedure

The procedure to subdivide the curve into two segments can be described as follows:

• First, let be the midpoint of the segment ,
  
  
• then, let be the midpoint of segment ,
  
  
• and finally let be the midpoint of the segment .
  
  

We define to be a point on the curve. Note that we have created two new sets control points ( and ) which can be use to define the first and second portions of the subdivided curve, respectively. We now have define an additional point on the curve and two new sets of three control points that can be used to continue subdividing the curve.

Continuing the Subdivision

Performing the procedure again, we use the control points , relabeling them for convenience as , , and respectively, and apply our procedure

• First let be the midpoint of the segment .
  
  
• then let be the midpoint of segment .
  
  
• and finally let as the midpoint of the segment .
  
  

We now define to be a point on the curve. This process produces another point on the curve, and creates two new sets of control points as was the case before.

If we consider the control points , , and , generated in the first subdivision, and relabel them as , , and respectively, we can again apply the subdivision procedure

• as the midpoint of the segment .
  
  
• as the midpoint of segment .
  
  
• as the midpoint of the segment .
  
  

We now have on the curve.

The Subdivision Algorithm

Three points have now been generated on the curve and four subcurves have been generated. The final curve, together with the points generated, is shown as follows:

You should now see how to proceed. At each step the process creates both a point on the curve and two new sets of control points. This effectively subdivides the curve into two new curve segments, each of which can be handled separately.

Summary

This is a somewhat unique method to define a curve, and probably not previously seen by many students. It is a geometric method, as it uses only the midpoint formula as it's fundamental tool. It uses the basic computer science paradigm of (sub)divide and conquer to calculate points on the curve. The curve can be ``drawn'' using computer graphics by calculating a somewhat-dense set of points, and connecting them with straight lines.

The curve drawn by this method is a quadratic Bézier curve.

This document maintained by Ken Joy Comments to the Author All contents copyright (c) 1996, 1997 Computer Science Department, University of California, Davis All rights reserved.