Sign in to follow this  
gibber10

Removing holes in a triangulation (fonts)

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
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

Create an account or sign in to comment

You need to be a member in order to leave a comment

Create an account

Sign up for a new account in our community. It's easy!

Register a new account

Sign in

Already have an account? Sign in here.

Sign In Now

Sign in to follow this