Postscript is not just for printing!
This page is a brief snippet about using PostScript to draw Bezier curves. Please direct questions, comments, or requests to, Charles Shiflett ( yikes.com/~bear ).

The Algorithm

The first known use of an analytical method to solve bezier curves was by Paul De Casteljau who in the 50's, while working at Citroen, developed the following method to solve spline curves. Prior methods involved a flexible metal strip (a spline), combined with large metal weights (ducks) to set the control points of the spline. From a mathematical standpoint, a spline originated from the idea of a conic section of a parabola, and, a Bezier Curve is really just a function of the form ... . This algorithm generates C2 curves, which is a continuous, twice differntiable, curve. Geometrically, his algorithm was as follows:
  1. Find the midpoints between control, start, and end points
  2. Draw a line between adjacent midpoints
  3. Find the midpoint of the lines drawn in step 2.
  4. Draw a line between midpoints found in step 3.
  5. Find the midpoint of the line drawn in step 4.
  6. The points are then renumbered starting from the start point, numbered at each vertex, and ending at the midpoint in step 5. This constitutes the left half. The right half starts from the midpoint at step 5, and is numbered at each vertex, and ends at the endpoint.
  7. The algorithm continues to step 1, using the numbering scheme from step 6.
This results of the algorithm (for three iterations) are shown in Image 1, where the black A represents the start of a spline curve, the black D represent the end, and the black B, & C represent the control points. The Sky blue lines are the result of the 1st iteration of this algorithm (along with renumbering), yellow the second, and red is the third.

Image 1: Results of De Casteljau algorithm, with "work" shown.

Example Code


	% Shows work to compute Bezier
	% 
	% P1x P1y moveto
	% P2x P2y lineto
	% P3x P3y lineto
	% P4x P4y lineto
	% R3x R3y moveto
	% Hx Hy   lineto
	% L2x L2y lineto
	% L3x L3y moveto
	% R2x R2y lineto

	recursionCount 0 eq {
		Cx Cy lineto
		P4x P4y lineto
        } if

	recursionCount 0 ne {

		recursionCount 
		Cx Cy
		R2x R2y
		R3x R3y
		P4x P4y 

		recursionCount 
		P1x P1y
		L2x L2y
		L3x L3y
		Cx Cy

		ComputeBezier 
		ComputeBezier 
	} if
} def

1 1 moveto
10 1 1 100 700  600 750 500 1 ComputeBezier
stroke

% Compare to postscript curveto operator

%1 setlinewidth
%1 1 moveto
%100 700 600 750 500 1 curveto
%1 1 1 setrgbcolor
%stroke 
  
%Bezier.ps: Creates a Bezier Curve 
%  By Charles Shiflett

/midpoint {
	%args:  x1 x2 y1 y2 
	%returns: midpoint (x, y)
	add 
	2 div
	3 1 roll
	add
	2 div
	exch
} def

/ComputeBezier {
	%Syntax almost like curveto
	/P4y exch def /P4x exch def
	/P3y exch def /P3x exch def
	/P2y exch def /P2x exch def
	/P1y exch def /P1x exch def
	
	1 sub
	/recursionCount exch def


	%Compute Left Side
	P1x P2x P1y P2y midpoint
	/L2y exch def /L2x exch def
	P2x P3x P2y P3y midpoint
	/Hy exch def /Hx exch def
	L2x Hx L2y Hy midpoint
	/L3y exch def /L3x exch def

	%Compute Right Side
	P3x P4x P3y P4y midpoint
	/R3y exch def /R3x exch def
	Hx R3x Hy R3y midpoint
	/R2y exch def /R2x exch def

	%Compute Center
	L3x R2x L3y R2y midpoint
	/Cy exch def /Cx exch def


Multiple Control Points?

Same idea as above, but different implementation. Probably a pain to implement in postscript. For an example in C, take a look at yikes.com/~bear/bim.