orpheus@reed.UUCP (P. Hawthorne) (01/30/91)
Newsgroups: comp.graphics
Subject: Clipping Bezier Curves
Expires:
References:
Sender:
Reply-To: orpheus@reed.UUCP (P. Hawthorne)
Followup-To:
Distribution: world
Organization: Reed College, Portland OR
Keywords:
Is there an algorithm to clip Bezier curves?
One possible method I had imagined was recursive subdivision of the curve
with the test for recursion based on whether the segment was entirely inside
the boundaries. I hesitate to use this method if there is a cheaper, and
perhaps easier, method.
orpheus@reedgershon%gr.utah.edu@cs.utah.edu (Elber Gershon) (03/09/91)
In article <15975@reed.UUCP> orpheus@reed.UUCP (P. Hawthorne) writes: > > Is there an algorithm to clip Bezier curves? > > One possible method I had imagined was recursive subdivision of the curve >with the test for recursion based on whether the segment was entirely inside >the boundaries. I hesitate to use this method if there is a cheaper, and >perhaps easier, method. > > > orpheus@reed I guess the main problem is to find the intersection of a straight line and a Bezier curve. One can easily reduce the dimensionality of this problem by substituting the Bezier curve parametric components into the line equation and solve for t using a scalar problem of the form: -- \ Bi(t)Pi = X0 / -- Closed form solutions for the zero set of polynomials are known, I think, up to order 5 (degree 4), so one can transform the Bezier basis functions above using monomial basis functions and get the solution analytically. Alternative more robust way will be to attempt and symbolically solve the above equation. I used the reduce program and unfortunatelly it successfully solved for the linear and quadratic case only. The cubic case was 64kbytes long... Anyone has reasonable such cubic solution? The reduce linear (obvious) and quadratic (verified by expanding the above equation) solutions follow. Beware of the degenerate case of P0 - 2P1 + P2 = 0 in the quadratic eqn. which converges to the linear case. Gershon REDUCE 3.3, 15-Jan-88 ... ***** Solve for 2th order bezier ***** 12: 12: 12: 12: 12: 12: 12: 12: P0 - X0 {T=---------} P0 - P1 13: 13: ***** Solve for 3th order bezier ***** 14: 14: 14: 14: 14: 14: 14: 14: 2 {T= - (SQRT( - P0*P2 + P0*X0 + P1 - 2*P1*X0 + P2*X0) - P0 + P1)/(P0 - 2*P1 + P2), 2 T=(SQRT( - P0*P2 + P0*X0 + P1 - 2*P1*X0 + P2*X0) + P0 - P1)/(P0 - 2 *P1 + P2)}