Number of Quadratic Bezier Segments used to Approximate a Cubic

Number of Quadratic Bezier Segments used to Approximate a Cubic

Post by Scott Thompso » Sat, 30 Jun 2001 23:57:25



I'm searching for the mathematical justification, preferably in the form
of a journal article or white paper, for a routine I found as part of
Apple's QuickDraw GX cubic library.  A version of the same routine can
also be found in the Balloon graphics system of Squeak <www.squeak.org>.

The problem at hand is approximating a cubic bezier segment with a
compound curve composed of quadratic bezier segments.  According to the
comments on the routine,it calculates an upper bound for the number of
quadratic bezier segments needed to approximate the cubic within a
certain error.

Given the points of the cubic as a, b, c, and d (with a and d as the
endpoints of the curve, b and c as the intermediate control points, the
routine makes the following calculation (in pseudocode):

somevector = (3*b - a) - (3*c - d)
veclen = sqrt(someVector.x ^ 2 + someVector.y ^ 2)
numQuads = (veclen / 20.0) ^ (1.0/3.0)    // or cube root of veclen / 20
numQuads = ceil(numquads)

if(numQuads <= 0) numQuads += 1;  

return numQuads

After this, the code simply uses forward differencing to generate
quadratic segments at an interval of 1.0 / numquads.  

The first mysterious quantity is the vector calculated in the first
line.  I don't understand what value is being calculated (why are the
control vector's components multiplied by 3 before the vector back to
the endpoints is determined?)

Also according to the comments, the accuracy of the generated curves can
be increased by changing the mysterious 20 in the afformentioned
equation with a different value. (10 for half pixel accuracy, 5 for
quarter pixel accuracy etc...)

My question is does anyone know where this routine came from?  It looks
to be doing some calculations based on a least-squares fit of the
original cubic, but on the whole I find the routine very mysterious and
black-magic like.  Can you suggest where I might find a paper describing
the mathematics behind the technique used?

Scott Thompson

 
 
 

Number of Quadratic Bezier Segments used to Approximate a Cubic

Post by Scott Thompso » Sun, 01 Jul 2001 07:07:12


Quote:> After this, the code simply uses forward differencing to generate
> quadratic segments at an interval of 1.0 / numquads.  

Actually, I was wrong, the code is not using forward differencing, it is
directly evealuating the curve from the cubic definition at each step.

The error on my part makes the code even more mysterious and bizzarre.

Scott

 
 
 

Number of Quadratic Bezier Segments used to Approximate a Cubic

Post by Richard J Kin » Mon, 16 Jul 2001 08:02:34


Quote:Scott Thompson writes:
>The first mysterious quantity is the vector calculated in the first
>line.  

Offhand, I'd say this looks like a crude flatness test.  The mysterious 20
is a value which is tweaked empirically to select a threshold of flatness
to split into more curves or not, or so I would guess.

The number 3 does naturally show up in cubic Bezier computations, seeing as
how 3 is the cubic exponent and thus ends up in coefficients during
differentiation.  But I haven't analyzed the equations you cite to induce
where they come from.

For example, a straight line as a Bezier curve is "most naturally" given
with its control points 1/3 the way from one endpoint to the other, and
vice versa, even though the control points could be anywhere in between.

Richard Kinch
More Bezier expertise at http://www.truetex.com/bezexp.htm