• Advertisement
Sign in to follow this  

Removing holes in a triangulation (fonts)

This topic is 3918 days old which is more than the 365 day threshold we allow for new replies. Please post a new topic.

If you intended to correct an error in the post then please contact us.

Recommended Posts

Hey, I am trying to write a 3d font renderer class. Basically I am attempting to rewrite wglusefontoutlines(). I've extracted the font data and I've used delaunay triangulation to create triangles, but I'm now lost where to go from here. I need to remove the holes, and concave parts from the font outlines. Each glyph has multiple curve structures that represent either an outline, or a hole. http://i157.photobucket.com/albums/t77/gibber10/Untitled-1copy.jpg I could start by removing all the triangles that have any verticies in the supertriangle, but that wouldnt remove the inside of the glyph of a 'C' for example. I couldnt find a method on the web, but I am not sure what to look for as yet. I could do somthing with BSP trees i think, but that seems like overkill. It doesnt need to be a fast solution, since this is only pre-calc anyway. Once I've created the meshes they'll be static display lists/VBOs anyway. PS: The blue line that seems to be a bug, is actually the z axis :)

Share this post


Link to post
Share on other sites
Advertisement
Delaunay triangulation is not a good algorithm for this problem. You got lucky with your "C" character. Generally, the edges of the outline might not be edges in the triangulation, and the Delaunay triangulation always produces a set of triangles whose union is a convex region. You could try constrained Delaunay triangulation to force the edges to be in the triangulation.

Instead, just use a polygon triangulation algorithm, one that handles holes (for example, when you triangulat the "A" character).

I have ear-clipping code that might be useful. Go to my web site, Geometric Tools, and select the "Foundation" tab under "Browse Samples...". On the page that displays, select the "Triangulation" link.

Share this post


Link to post
Share on other sites
Thanks, that looks like just what I need.

I've implemented a simple triangulation by ear clipping, based on your pdf. Though I've skipped the complexity optimisation for now.

Share this post


Link to post
Share on other sites
Sign in to follow this  

  • Advertisement