Path: utzoo!utgpu!news-server.csri.toronto.edu!rpi!think.com!sdd.hp.com!elroy.jpl.nasa.gov!ncar!csn!hellgate.utah.edu!gr.utah.edu!gershon From: gershon%gr.utah.edu@cs.utah.edu (Elber Gershon) Newsgroups: comp.lang.postscript Subject: Re: Bezier math help Message-ID: <1991May22.131814.12328@hellgate.utah.edu> Date: 22 May 91 19:18:14 GMT References: Organization: University of Utah CS Dept Lines: 44 In article petrus@alex.stacken.kth.se (Lars Petrus) writes: > > Hello world! > > I'm doing some PostScript processing in C, and I could use your help! > >1) What is the correct mathematical way to split a curve into two curves >at a specified value of t? This is easy. Evaluate the curve at t. The left side of the evaluation is the left polygon and the right side is the right polygon. >2) What is the best way to find all intersections of two curves? This is hard. Two curves of degrees d1 and d2 intersect at most d1 * d2 times. For two cubics, which PS uses, it means they can intersects 9 times! Common methods for solving the problem uses some kind of divide and concour techniques - put a bounding box on the control polygon. if bounding boxes intersect, subdivide the two curves and recurse with the 4 sub curves, until bounding boxes are small enough. Numeric improvements (Newton Raphson!?) may be of help here. Tom Sederberg (BYU) has some papers describing new ideas in this area: 1. "Comparison of three curve intersection algorithms", Thomas W Sederberg and Scott R Parry, Computer Aided design, volume 18, number 1, jan/feb 1986. 2. "Curve intersection using Bezier clipping", T W Sederberg and T Nishita, Computer Aided Design, volume 22, number 9, nov 1990. 3. "Analytic approach to intersection of all piecewise parametric rational cubic curves", R N Goldman and T W Sederberg, Computer Aided Design, volume 19, number 6, july/aug 1987. Hope this helps. Gershon Elber Gershon gershon@cs.utah.edu 918 University village Tel: (801) 582-1807 (Home) Salt Lake City, Utah 84108-1180 Tel: (801) 581-7888 (Work)