4 ms·

Flattening Quadratic Béziers

100 points by jwmerrill 7y ago

taeric 7y ago
I'm curious how this compares to the techniques that METAFONT uses. I'll try and make it a point to dig up that book this holiday.
- raphlinus 7y ago
  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.
  - taeric 7y ago
    Any chance you can expand on what you mean regarding bilevel? Is it covered in 304? This reminded me I want to pick up MetaPost, and the graphics it generates seem quite nice. Just not good for a graphics pipeline?
    - dhfhjjfdcbbvfg 7y ago
      Bilevel just means black and white, i.e. the output is a bitmap with just one bit per pixel.
      - taeric 7y ago
        Ah, thanks! That is not the case for MetaPost though, right?
romwell 7y ago
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.

100 points by jwmerrill 7y ago

I'm curious how this compares to the techniques that METAFONT uses. I'll try and make it a point to dig up that book this holiday.

raphlinus 7y ago
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.
- taeric 7y ago
  Any chance you can expand on what you mean regarding bilevel? Is it covered in 304? This reminded me I want to pick up MetaPost, and the graphics it generates seem quite nice. Just not good for a graphics pipeline?
  - dhfhjjfdcbbvfg 7y ago
    Bilevel just means black and white, i.e. the output is a bitmap with just one bit per pixel.
    - taeric 7y ago
      Ah, thanks! That is not the case for MetaPost though, right?

romwell 7y ago

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.