Delaunay Triangulation


I was trying to cap polygons with holes and all my gaps were coplanar. As opposed to my initial solution (finding edge rings and capping those, leaving me with no clue how to cut out holes) I decided to look up how to go about this. This was really a learning exercise and it proved more complex than I initially anticipated.

So the idea, and some illustrations displaying that I wasn’t the first to run into the problem of capping edge rings come from here:
Jose Esfer

But the most difficulty I had with finding a good reference for this. There’s a lot of scientific papers that go very, very far beyond my understanding of mathematical jargon and there’s a number of source code examples in various languages, but the few I opened were lengthy so I knew the only way to understand this was with a decent explanation, finally to be discovered here:
Computing constrained Delaunay triangulations

This explanation is pretty clear although it took me over a day to implement, further errors are yet to be discovered…

The only thing to watch for is the explanation of the actual triangulation algorithm where the first ‘New LR-edge’ is inserted and some edge gets deleted one image yet is not deleted in the next (and in my implementation hence never deleted). So following what the text actually says got me there.

UPDATE: Added debug output -> define UDT_Debug in the conditional compilation symbols of the project settings (also for the editor project) and get some control on where to stop triangulating. It displays potential new connection candidates as circles (green and blue) as well as the last edge (red) and the last deleted edge(s) (green).

Also randomization now generates input when you check it and then unchecks itself.

I’m not sure if it’s useful to post the source I ended up with, because it’ll be just another example out there, but since it’s for Unity it may be easier to get it running. Do select the GameObject you attach it to though because it relies on OnDrawSceneGUI which only gets called for selected objects.

It displays the current vertex numbers as well, which may give some confusion because the vertices get dynamically rearranged so this does not reflect your actual input.

Grab the package here!

Leave a Reply

Your email address will not be published. Required fields are marked *