It's at heart a recursive bisection approach. See section 304 of "Metafont: the Program" in particular. But also keep in mind they're generating bilevel output (in which variants of Bresenham are effective), and today we're much more concerned with antialiased rendering.
Funny that: just yesterday I was trying to 3D print a stamp whose design I made in Inkscape, and ran into the problem of OpenSCAD only understanding polylines and not Bezier curves in the DXF export.
So, the problem was to flatten the Beziers. I thought this would be a trivial thing. After all, just sampling the t parameter densely gets you somewhere, and with numerical integration, you can sample at uniform arc length intervals, which is just about what I needed anyway.
Thankfully, Inkscape has this feature as a plug-in: Extensions -> Modify Path -> Add Nodes.. -> By Max Seg. Length (1.0), if anyone is looking (after which you can apply "Straighten Segments" and live happily ever after).
But then I realized that flattening a Bezier by specifying the bound on how much the flattened polyline can deviate from the curve is nontrivial, as is doing the subdivision in an efficient manner. I didn't need this, but wondered about it. And now this article pops up as a manifestation of the Baader-Meinhof effect.
That aside, writing your own Bezier editor is a fun little project that I can highly recommend. If you don't care about it being perfect, rendering a Bezier is as simple as taking weighted averages, repeatedly. And if your curvature doesn't get crazy, it will look as good as anything else.
6 comments
[ 2.6 ms ] story [ 25.4 ms ] threadThis reminded me I want to pick up MetaPost, and the graphics it generates seem quite nice. Just not good for a graphics pipeline?
So, the problem was to flatten the Beziers. I thought this would be a trivial thing. After all, just sampling the t parameter densely gets you somewhere, and with numerical integration, you can sample at uniform arc length intervals, which is just about what I needed anyway.
Thankfully, Inkscape has this feature as a plug-in: Extensions -> Modify Path -> Add Nodes.. -> By Max Seg. Length (1.0), if anyone is looking (after which you can apply "Straighten Segments" and live happily ever after).
But then I realized that flattening a Bezier by specifying the bound on how much the flattened polyline can deviate from the curve is nontrivial, as is doing the subdivision in an efficient manner. I didn't need this, but wondered about it. And now this article pops up as a manifestation of the Baader-Meinhof effect.
That aside, writing your own Bezier editor is a fun little project that I can highly recommend. If you don't care about it being perfect, rendering a Bezier is as simple as taking weighted averages, repeatedly. And if your curvature doesn't get crazy, it will look as good as anything else.