Xref: utzoo comp.sources.wanted:6129 comp.lang.postscript:1471
Path: utzoo!attcan!cmtl01!matrox!uvm-gen!uunet!lll-winken!ames!ncar!ico!rcd
From: rcd@ico.ISC.COM (Dick Dunn)
Newsgroups: comp.sources.wanted,comp.lang.postscript
Subject: Re: Bezier Curve source required
Summary: simple bisection algorithm
Message-ID: <13960@ico.ISC.COM>
Date: 26 Jan 89 05:17:38 GMT
References: <30936@vax1.tcd.ie> <879@ssp15.idca.tds.philips.nl>
Organization: Interactive Systems Corp, Boulder, CO
Lines: 48

> >	Has anyone got pascal source code, for Bezier curves? I recently
> >recieved the database for a goblet, but the writing of a program to plot the
> >points is beyond me.

I don't have the code written out and tested (well, I do, but it's in C and
assembly language for some obscure hardware:-), but it turns out to be
quite simple.  Call the four control points of the curve A, B, C, and D in
order (i.e., A and D are the endpoints).  The algorithm requires bisecting
segments--if we denote coordinates of points as A=(Ax,Ay), B=(Bx,By) then
define		Bisect(A,B) = ((Ax+Bx)/2, (Ay+By)/2)
To get the points you need to plot, use a recursive algorithm which splits
the curve until the segments are small enough or the angle between them is
small enough.  One step goes like this:
	First bisect each of the three segments from taking control points
	in order:
		P1 = Bisect(A,B)
		P2 = Bisect(B,C)
		P3 = Bisect(C,D)
	Now bisect each of the new segments formed by these:
		Q1 = Bisect(P1,P2)
		Q2 = Bisect(P2,P3)
	Finally, bisect that segment:
		R = Bisect(Q1,Q2)
You now have two Bezier curves, each of which is shorter and flatter than
the original.  The control points for these curves are A-P1-Q1-R and
R-Q2-P3-D.  R lies on the curve.  You can repeat the algorithm with each of
the subcurves, or if you've gotten things down far enough, just draw
segments AR and RD.

> A related question (I think it's just the inverted algorithm...):
> 
> I'm looking for a program that calculates the so called
> Bezier cubic control points when giving a number of points 
> that should be placed in the resulting Bezier cubic section.

This is a rather harder problem.  Now, at first blush you might think that
if you had the endpoints plus two points on the curve, you should be able
to define the curve uniquely--after all, there are four control points, so
it seems like the same number of degrees of freedom, but not so.  Anyway,
if you have a bunch of points, you're probably going to need to do a fit of
the curve which minimizes some error criterion.  I fiddled around with this
for a little while, stumbling over the problem of trying to get a useful
error criterion given the parametric representation...and eventually
decided that I was too lazy to work it through, but I *would* like to see
how it is done.
-- 
Dick Dunn      UUCP: {ncar,nbires}!ico!rcd           (303)449-2870
   ...A friend of the devil is a friend of mine.