<p>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 <em>Uniform</em> B-Splines to Beziers, those too.</p>

<p>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.</p>

<p>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.</p>

<p>Finally, if you need info on derivatives of Beziers (or almost everything else related to them), <a href="https://pomax.github.io/bezierinfo/">this astounding web-page appeared</a> in my twitter feed recently.</p>

CC BY-SA 3.0
2015-09-14T13:10:41.883Z
2015-09-14T13:18:08.537Z
2015-09-14T13:18:08.537Z
Simon F
<p>In all computer graphics books there are algorithms for scan converting simple primitives like lines, circles, ellipse,...</p>

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

<p>Where can I find the references ?</p>

<p>I have also another doubt: are scan converting and rastering the same thing ?</p>

CC BY-SA 3.0
2015-09-14T08:00:20.543Z
_"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.
Simon F
CC BY-SA 3.0
2015-09-14T11:03:25.847Z
See https://en.wikipedia.org/wiki/Bézier_curve#Computer_graphics.
lhf
<curve>
Algorithms for scan converting b-spline and nurbs
Valerio
# Algorithms for scan converting b-spline and nurbs

(Asked by: username_0 on 2015-09-14)

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 ?

**Tags:** curve

> **Comments:**
> **username_1**: _"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.  
> **username_2**: See https://en.wikipedia.org/wiki/Bézier_curve#Computer_graphics.  

---

## 1 answers

### Answer by username_1 on 2015-09-14. Score: 5

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](https://pomax.github.io/bezierinfo/) in my twitter feed recently.


---

