Re: [Devel] Problems with bbox code and cubic bezier curves

[Tom Kacvinsky]

Hmmm... I guess I should have been more precise.  If the control points
for a cubic Bezier curve are (x1,y1) -- (x4,y4) and t in [0,1], then the
parametric equations are:

  x(t) = (substitute x_i for P_i in the equations below)

  y(t) = (substitute y_i for P_i in the equations below)

Correct?

Yes, Bezier curves have *tons* of useful properties.  Always contained in their
convex hulls, nice recursive algorithms for getting points on the curve by using
midpoint rules, etc...  Good stuff!

I had been working through the math before receiving this, and it makes sense.

The only question I have is about normalising the 16.16 fixed floats to 8.16
fixed floats.  That only allows for integer parts between -128 and +127!

Tom

On Wed, 25 Apr 2001, David Turner wrote:

> Hi Tom,
>
> >
> > Hey, you aren't the only one who has been flexing (or trying to flex) those 
> > old
> > rusty mathematical muscles!  Anyway, I must admit despite a degree in math, 
> > I do
> > not understand the new code, other than the general gist of things (solve 
> > for
> > extrema, and test the bbox at the endpoints and the extrema). Can you tell 
> > me
> > what reference you used for the code?  I had asked about the particular
> > parametric equations used to describe the bezier arcs, but no one took the 
> > bait
> > and answered.
> >
> > If I had that (the pararmetric equations), I could follow the code a lot 
> > easier.
> >
>
> OK, no problem:
>
>   for quadratic (conic) beziers, were P1, P2 and P3 are the control points:
>
>     P(t) = P1 + 2t.(P2-P1) + t^2.(P3-2P2+P1)
>
>   for cubics:
>
>     P(t) = P1 + 3t.(P2-P1) + 3t^2.(P3-2P2+1) + t^3.(P4-3P3+3P2-P1)
>
> A quick rule of thumb to reconstruct the polygon, or even to
> easily draw an arbitrary point of a conic or cubic by hand:
>
>   for t in (0..1)
>
>   for conics:
>
>      let P1, P2, P3 be the control points,
>
>      define  Q1(t) = P1 + t.(P2-P1)
>              Q2(t) = P2 + t.(P3-P2)
>
>      then   P(t) = Q1 + t.(Q2-Q1)
>
>   for cubics:
>
>      let P1, P2, P3 and P4 be the control points,
>
>      define  Q1(t) = P1 + t.(P2-P1)
>              Q2(t) = P2 + t.(P3-P2)
>              Q3(t) = P3 + t.(P4-P3)
>
>      define  R1(t) = Q1 + t.(Q2-Q1)
>              R2(t) = Q2 + t.(Q3-Q2)
>
>      then    P(t) = R1 + t.(R2-R1)
>
>   you can apply this "rule" recursively to build
>   higher-order beziers too :-)
>
>   Also note that all Q1, Q2, Q3, R1, R2 are control points
>   for the sub-arcs P1..P(t) and P(t)..P3 (or P(t)..P4) !!
>
>   Beziers have _tons_ of weird and useful properties,
>   I love them :-)
>
> Regards,
>
> - David
>