cn@allgfx.agi.oz (Con Neri) (02/08/90)
About two months ago I asked the readers of the groups comp.graphics and sci.math for information regarding an algorithm to produce a bezier curve for a set of points without knowing the control points. Well after a great deal of study and research and help from the net I have done it. Before I state the results, I would like to thank the following people who supplied me with advice, it was much appreciated. "Prof. David F. Rogers" <dfr%cad.usna.mil@murtoa.cs.mu> cchen%enuxha.eas.asu.edu@murtoa.cs.mu (Chao-Chi Chen) tim%nwnexus.WA.COM@murtoa.cs.mu (Tim Anderson) Doug Heins <dheins%hpbsl88.boi.hp.com@murtoa.cs.mu> MORRISON%FORDMURH.bitnet@murtoa.cs.mu Philip J. Schneider <pjs%decwrl.dec.com@murtoa.cs.mu> kevinwu%Sun.COM@murtoa.cs.mu Munish Mehra <munish%ms.uky.edu@murtoa.cs.mu> cat!joerg%relay.EU.net@munnari (Markus Schichtel) abdul shammaa <uunet!sdrc!spabdul@murtoa.cs.mu> I am especially grateful to Philip Schneider, whose help has proven to be invaluable. And whose thesis is a must for anyone wishing to work in this area. His thesis is Phoenix: An interactive Curve design System Based on the Automatic Fitting of Hand Sketched Curves. Masters Thesis University of Washington 1988. Philip's algorithm will also be incorporated in an book to be released later on in the year (About August). The book is "Graphics Gems", edited by Andrew Glassner of Xerox Palo Alto Research Center, published by Academic Press. The book is a diverse collection of tutorials, algorithms, etc., contributed by a lot of folks in the computer graphics industry. For those of you who do not remember the original question, it was as follows: >We have been trying for some time now to come up with an algorithm to outline >an image using a series of bezier curves (ie to use with postscript). The >problem we are facing is that we have a series of points that describe the >outline but cannot find an algorithm to produce the beziers from these points. >The algorithms i have seen all assume that the control points are known for the >bezier curve to be fitted. > >Does anybody know of an algorithm to evaluate the control points for a bezier >curve that best fits a set of points? If anyone has seen a documented >description of an algorithm i would dearly love to hear about it. > The replies I received were: From: "Prof. David F. Rogers" <dfr%cad.usna.mil@murtoa.cs.mu> Look in Mathematical Elements for Computer Graphics 2nd ed by Rogers and Adams, McGraw-Hill 1990 under B-spline fitting. From: cchen%enuxha.eas.asu.edu@murtoa.cs.mu (Chao-Chi Chen) As far as I know, if you want to use the Bezier curve (curveto) in Postscript, you can only use Cubic Bezier curve, i.e. use 4 control points to define the Bezier curve you want. If you want to find *A* Bezier curve passes through the points and use Postscript, you must find the piece-wise Bezier curves to interpolate those points if the curve is pretty complicate. One solution is that you digitize the curve and pick certain number of points on the curve and find a Cubic B-Spline curve interpolates those points. Once you find the B-Spline curve, then, you can convert the B-spline curve into piece-wise cubic Bezier curve and use Postscript's curveto commands to plot the curve. You may find the algorithm how to find the B-Spline curve to interpolate data points and convert B-Spline into Bezier curve from most of the Computer Aided Geometric Design books. I am using "Curves and Surfaces for Computer Aided Geometric Design - A Practical Guide" by Gerald Farin from Academic press, ISBN 0-12-249050-9 From: tim%nwnexus.WA.COM@murtoa.cs.mu (Tim Anderson) noticed your note in sci.math regarding fitting bezier's to a set of data points. This is a VERY big can of worms... I have a monsterous pile of papers about curves and surfaces in general, and some deal exclusively with the interpolation question. Couple pointers: get Micheal Mortenson's book 'Geometric Modeling'. It is the 'bible' of CAGD. Though a bit general in alot of things, and some of his approaches are downright silly, a more definitive reference does not exist. Plus he has a great bibliography. Since I am currently working on approximating NRBS with cubic bezier segments, I will point you also at a paper in 'Computer Aided Geometric Design', 4, 1987 pgs 59-66. This is 'approximate conversion of spline curves' by Josef Hoschek. Though it deals with translating curves from one form to the other, the development of bezier curves in that paper can be applied to the problems of data fitting. You would use this paper more in terms of how to go about building bezier curves from data sets... This is by no means the only way to do this problem. I urge you to go dig through 'CAD' magazine, and 'CAGD' magazine, plus 'Computer Graphics (aka SIGGRAPH proceedings)' for articles and pointers to whatever problem you may be having in curve construction... Then again, you could always farm the work out to me! (I had to throw that in there...) Good luck! Received: from FORDMURH.BITNET by CUNYVM.CUNY.EDU (IBM VM SMTP R1.2.2MX) with BSMTP id 0770; Mon, 18 Dec 89 13:10:04 EDT X-Original-To: @allgraphic.dis, MORRISON Dear Mr. Neri, Ken Ribet at Berkeley forwarded the email message you sent requesting help with the problem of producing Bezier outlines from points without any tangent (i.e. control point) data. The good news is that Projective Solutions, a mathematical consulting compnay of which I am President, has done considerable work on the soert of problems you mention. In particular, we have Pascal and C programs running mainly on Mac's but which have also been ported to Unix systems like the Sun/3 to do exactly what you want. The bad news is that our business is licensing these algorithms and our implementations of them. If you are interested in discussing such a license with us, please give our office a call (212) 678-6595 and ask for Henry Pinkham or myself (Ian Morrison). We will be in and out of the office over the Christmas season so if no one is in, please leave a message and we will get back to you. We would be interested in hearing what your applications are and in exploring how Projective Solutions might be able to help you with them. If you have no budget for such software and want to try to derive your own algorithms, I suggest looking at Knuth's book "MetaFont: the program" where he discusses his approach to this problem inside MetaFont. We think our algorithms are substantially superior to the ones MetaFont uses in most circumstances but many of the basic ideas can be found in the book. I hope to hear from you in the near future. Good luck with the Beziers. From: pjs%decwrl.dec.com@murtoa.cs.mu (Philip Schneider) Well, I think you're in luck here. I did my thesis on this very subject -- I came up with an algorithm for fitting piecewise Bezier curves to digitized line/outline data. I'll send you off a copy of it by normal mail (much too large to e-mail, I think), so let me know if you don't get it (don't know how long it takes, but I can send one off in the next couple of days). The algorithm is recursive -- you attempt to fit the entire curve with one segment. Measure the distance between the curve and the original points. If it doesn't fit to the desired tolerance, subdivide the data into two halves at the point of poorest fit. Apply algorithm recursively until the entire curve has been fitted (with some number of cubic Bezier segments). The sub-algorithm that performs the fit works as follows : 1. Place the first and fourth control points at the endpoints of the data (line) to be fitted. 2. Estimate the unit tangent to the data points, at the first and last data points. (Look at vectors defined by each end data-point and one or more of its neighbors, use linear regression, etc.) 3. These tangents define lines along which you will place the two interior control points (control points 2 and 3). This will maintain geometric continuity across the joints in the final, piecewise Bezier curves. 4. The interior control points are placed along the tangent lines using a form of least-squares curve fitting. I know this sounds expensive -- one of the points of the thesis was to find out if this very simple and elegant technique would be sufficiently fast and robust. I think that I can claim success in this matter -- I use the algorithm in an interactive curve-drawing program, and find it more than fast enough. From: kevinwu%Sun.COM@murtoa.cs.mu What do you mean by best? I assume that you want a curve that interpolates the points (i.e. passes through the points) and that you want a curve that looks smooth. Since PostScript only supports cubic Bezier curves, and since I don't care to go into a lengthy explanation, the following description will be just enough to get you a working solution. Assume you have the points {p(0), p(1), p(2), ..., p(n-1)}. Let C(l) be a "vector of points" of the form | p(l-1) | | p(l) | | p(l+1) | | p(l+2) | Let B(l) be the vector of Bezier control points. One way to convert C(l) to B(l) is with the following matrix: M = | 0 1 0 0 | | -1/6 1 1/6 0 | | 0 1/6 1 -1/6 | | 0 0 1 0 | so B(l) = M C(l). This gives you interpolation with Cardinal splines. The curve segments are C1-continuous, meaning that curve segments join end-to-end and the tangent vectors are continuous at segment end points. You will have n-3 curve segments as "l" takes on the values 1, 2, ..., n-3. When l=1, you use the points p(0), p(1), p(2), p(3) to generate the control points for a Bezier curve that starts at p(1) and terminates at p(2). The tangent vector at p(1) is parallel to p(2)-p(0); similarly, the tangent vector at p(2) is parallel to p(3)-p(1). The composite curve does not extend to p(0) and p(n-1) so you will need to decide how to treat the ends. However, if your curves are closed, just wrap the points around. If you want to know why this works, read pages 18-38 of my thesis. You can get a copy by writing to: Debra S. McKenzie-Lee Dept. Aero/Astro Durand Bulding, Room 370 Stanford University Stanford, California 94305-4035 From: Munish Mehra <munish%ms.uky.edu@murtoa.cs.mu> It is fairly trivial to compute a set of Control points for a given set of fitting points. (I just figured this out a few days ago) It is basically solving a set of mn equation, where the grid is of size m X n. Several programs exist to fit a Beizer or B-spline to a surface. I'm in the process of writing one. (If you have one already - send it by - If not I can try and find some (by ftp'ing)) My advisor here has a neat parallel algorithm to fit a Beizer to a set of fitting points.- If you'd like it - send mail to cheng@ms.uky.edu. From: cat!joerg%relay.EU.net@munnari (Markus Schichtel) HI there in Down Under! I think I have something for you guys.I am a math student at Darmstadt West Germany and familiar with that stuff because we have a prof who is big into that. Ok The point is if you use rational BEZIER curves then you dont have to know the BEZIER points since you have introduced some weights to the points Hence the interpolation problem is finding those weights. However you have to take care of two things: First the shape of your control polygon and second how to parametrize the points to be interpolated. 1) Shape of control polygon it must have the same shape like the polyline through all the points to be interpolated.i.e the # of inflections must be the same By the variation diminishing property of the BERNSTEIN POLYNOMIALS you are guranteed that the curve won't have more inflections than the control polygon. 2) Parametrization One should use at least chordal parametrization for good results or even better centipedal. Last but not least you may think about a B-Spline technique to solve your problem. I hope I could help you a little. Remember it is not necessary to know the control points you can choose 'em From: abdul shammaa <uunet!sdrc!spabdul@murtoa.cs.mu> problem: Given n+1 points, {Qi}, interpolate the {Qi} by fitting a Bezier curve. Solution: You have to set up (nxn) linear simultaneous equations and fit a Bezier curve of the n(th) degree. Example: Fit a Bezier curve through the points Q0, Q1, Q2, and Q3. x Q0 x Q2 x Q3 x Q1 1. Select parameter values (ui) to correspond to the above four points. You should choose u0 = 0.0 at Q0 ui = ui-1 + 1/(n+1)*sum of (distances Qi-Qi-1) then, normalize the parameter values so that u3 = 1.0. 2. Set up the equations as follows: P0 = Q0 (1) B0(u1)*P0 + B1(u1)*P1 + B2(u1)*P2 + B3(u1)*P3 = Q1 (2) B0(u2)*P0 + B1(u2)*P1 + B2(u2)*P2 + B3(u2)*P3 = Q2 (3) P4 = Q3 (4) where, Pi's are the control points (unknowns) Bi's are Bezier basis functions 3. Solve for the unknowns Pi's. The disadvantage of using Bezier curves for fitting though points is that as the number of points increases, the curve degree also increases. So, if you have (n+1) points, you have to use n degree curve, i.e.; you must solve (n+1) equations. The problem of having to use higher order curve as the number of points increase can be eliminated if you could use B-splines instead. If anybody has anything further to add to this topic, please feel free to send me some e-mail to discuss it. Thanks again to everyone who helped. Con Neri. All Graphic R+D e-mail: cn@allgfx.agi.oz.au 73 Whiteman ST tele: +61-3-6966401 South Melbourne tele: +61-3-6464333 Vic 3205 tele: +61-3-6906788 AUSTRALIA