Transform shape built of contour splines to simple polygons

I've dumped glyphs from truetype file so I can play with them. They have shape contours that consist from quadratic bezier curves and lines. I want to output triangles for such shapes so I can visualize them for the user.

Traditionally I might use libfreetype or scan-rasterise this kind of contours. But I want to produce extruded 3D meshes from the fonts and make other distortions with them.

So, how to polygonise shapes consisting from quadratic bezier curves and lines? There's many contours that form the shape together. Some contours are additive and others are subtractive. The contours are never open. T开发者_StackOverflowhey form a loop.

(Actually, I get only contour vertices from ttf glyphs, those vertices define whether they are part of the curve or not. Even though it is easy to decompose these into bezier curves and lines, knowing the data is represented this way may be helpful for polygonizing the contours to triangles)

This is simple. You need to implement boolean operations on your curves, then proceed by joining pairs of curves untily you are left with a single curve.

First, you need to evaluate the curves and convert them to polylines.

Then you need to make sure that there is a vertex at every place where two contours intersect (this part can actually be trying, due to the numeric errors; you can use the Bentley-Ottmann algorithm).

Finally, all you need to do is to traverse the curves and connect them in the correct order to perform the boolean operation, producing weakly simple polygons.

Such polygons can be triangulated using e.g. ear clipping algorithm (which is slow, but rather simple to implement).

Hope this helps ...