davis@pacific.mps.ohio-state.edu ("John E. Davis") (12/10/90)
Hi, What is the most efficient algorithm to draw a cubic polynomial on a 2-d grid? I can always calculate the xy values and draw a line from one to the next but there must be a better way. For example, I am sure that one does not draw a circle from its equation (x = r cos q, y = r sin q). I looked in the fac sheet but the closest I found was drawing circles via splines. Well, how do I draw a cubic spline? Ultimately, drawing curves amounts to turning on pixels. How do I choose which pixels to turn on? -- John bitnet: davis@ohstpy internet: davis@pacific.mps.ohio-state.edu
jroth@allvax.enet.dec.com (Jim Roth) (12/10/90)
In article <DAVIS.90Dec9164433@pacific.mps.ohio-state.edu>, davis@pacific.mps.ohio-state.edu ("John E. Davis") writes... >Hi, > > What is the most efficient algorithm to draw a cubic polynomial on a 2-d >grid? I can always calculate the xy values and draw a line from one to the >next but there must be a better way. For example, I am sure that one does not >draw a circle from its equation (x = r cos q, y = r sin q). I looked in the >fac sheet but the closest I found was drawing circles via splines. Well, how >do I draw a cubic spline? Ultimately, drawing curves amounts to turning on >pixels. How do I choose which pixels to turn on? In principle an implicit (singular) cubic polynomial in x and y can be created from the parametric form, and an incremental stepping algorithm in terms of kings moves among the pixel grid can be written in a manner similar to the more well known Bresenham circle or Pittway conic section algorithms. The problems with this are that one has to subdivide the spline into sections depending on which quadrant the tangents lie in (to simplify the inner loops of the stepping algorithm), and one has to identify the singular point (self intersecting point which always exists in a parametric spline), etc. This turns out to be a fair amount of work, but may in fact be more efficient than evaluating the spine with a polyline approximation. I don't know of a public domain piece of code to do this, but do seem to recall a paper in CAD magazine on the subject; perhaps there was a recent TOG paper as well. This has been on my list of things to investigate as well, but I have not yet had time to work on it. If you wish to draw a polyline approximation, it would be desirable for the line drawing algorithm to be able to initialize on non-pixel boundaries - this will give higher quality curves than if you segment the spline and snap the polyline endpoints to pixel grid points. There are really a number of tradeoffs here in terms of curve rendering quality versus efficiency. - Jim