7
$\begingroup$

In all computer graphics books there are algorithms for scan converting simple primitives like lines, circles, ellipse,...

I can't find algorithms for more advanced curves like bezier curves, b-spline, nurbs.

Where can I find the references ?

I have also another doubt: are scan converting and rastering the same thing ?

Improve this question
$\endgroup$
2
  • $\begingroup$ "I have also another doubt: are scan converting and rastering the same thing ?" <sarcasm>That might depend on who's paying the patent lawyer you meet </sarcasm>. I, however, would tend to say that scan converting is probably a subset of the rasterisation process, i.e. Scan conversion being the process that determines which pixels are inside a (or all) each primitive(s). Whether you should also include the shading/texturing in the "scan conversion" is a bit uncertain. I tend to think of those as a 'separate' step. $\endgroup$
    – Simon F
    Commented Sep 14, 2015 at 8:00
  • $\begingroup$ See en.wikipedia.org/wiki/Bézier_curve#Computer_graphics. $\endgroup$
    – lhf
    Commented Sep 14, 2015 at 11:03

1 Answer 1

Reset to default
5
$\begingroup$

Ignoring Non-uniform B-splines (rational or not), I have had some experience with rasterisation of Beziers and, since there is a trivial mapping from Uniform B-Splines to Beziers, those too.

I have used two different techniques: The first was a scan-line renderer that used Newton-Rhapson to compute the intersection of the current scanline with the curve. This requires the first derivative but, as that can be trivially derived, again as a Bezier representation, from the control points of the parent curve, it's easy to obtain. Further, the bounding box of the control points of the 1st derivative can be useful to detect if the region might have more than 1 intersection with the scan line. The current scanline can use the previous scanline's solution as a starting point - usually that gives a highly accurate solution with one iteration.

Alternatively, a second approach is to simply apply binary subdivision of the curve and render it as series of straight line segments with your favourite polygonal renderer. If I recall correctly, at least with cubic Beziers, with each subdivision the error between the line segment joining the end points of the (sub)Bezier and the true curve decreases by a factor of 4. In most cases it therefore doesn't take many subdivisions before the difference between the polygonal approximation and the true curve is insignificant.

Finally, if you need info on derivatives of Beziers (or almost everything else related to them), this astounding web-page appeared in my twitter feed recently.

Improve this answer
$\endgroup$
1
  • $\begingroup$ For cubic curves, the scanline approach can also be looked at as a 1D problem, only involving the Y equation, which is a cubic. You can find the two extrema analytically (it's a quadratic equation) to achieve reliable separation of the roots. Full analytical computation of the roots is also possible, but incremental resolution (Newton or other) is less expensive. $\endgroup$
    – user1703
    Commented Sep 23, 2015 at 6:33

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Not the answer you're looking for? Browse other questions tagged or ask your own question.