Delaunay Triangulations

Apparently, Delaunay triangulation is harder than I thought. It seems like such a simple idea: draw triangles between points in a set so that the circle that runs through the triangle's points doesn't have any other points in it. Although there are apparently lots of solutions, but the simpler ones that tutorials exist for aren't very efficient and no one's talking about the efficient ones.

A 2D Delaunay Triangulation in MATLAB

Why Delaunay? Why can't I just be happy with drawing regular triangles? It's because the DT focuses on maximizing the internal angles. In layman's terms, it avoids long, skinny triangles which turns out to be bad for both rendering and finite element analysis. This will help when I eventually have to split surfaces up into triangles for OpenGL rendering. Of course, there might be a quick easy way to tessellate a Bezier surface without resorting to triangulation methods. If there are, please let me know ASAP!

Anyway, I'm trying to first start out with a 2D triangulation. It seemed like the simplest way to go. I implemented a Bowyer-Watson algorithm because it was easily explained and it was incremental. It is also supposedly one of the fastest DT algorithms out there. Here's the basic gist of how it works:

1. If you have a set of points, start out by drawing a "supertriangle" around all the points. The DT should just consist of the "supervertices" right now, which don't really belong there but we'll remove them later. Since the triangulation consists of only 3 points right now, you can say it's Delaunay.
2. Include each point from the point set into the DT. Check to see which triangles (by checking their circumcircles) are made non-Delaunay by the point.
3. Remove the triangles so you have a void in the DT.
4. Take all the points on the edges of that void and make triangles that include the new point as a vertex.
5. Repeat this until you've added all the points from the original set.
6. Now remove all triangles that have any "supervertices".

If you've followed this algorithm, then supposedly you should have a Delaunay triangulation of the point set. I made code that did this, but it wasn't very efficient. After hours of trial and error, it finally produced what it was supposed to! Well, kinda. I did get a Delaunay triangulation, but removing the "supervertices" from the set caused the DT to not represent the true convex hull of the points. It removes the triangles that contain points that, if connected, would build a convex hull. I guess the question is, "If you know what the problem is, why not fix it?" Good question. First of all, I don't know how to just limit my searches to triangles around the outer edge. I read about a quad-edge data structure that Guibas and Stolfi came up with to map the DT topologically (meaning each triangle would know who its neighbors, either triangles or points, were) and I could use that, but I didn't quite understand how to pinpoint only the DT edges and how to connect them or check to see if they were already connected. Second, I read that the "supertriangle" method doesn't always produce correct results, which worries me because I don't know any other method for producing a starting DT. This algorithm would be great if I already had a rough DT, but I haven't seen a good method for doing that either.

I'm sort of stuck on Delaunay triangulations, but I read about a technique that talked about a 2D DT being a projection of a 3D convex hull of a paraboloid onto a plane. I know I used some big words, but let me explain. A paraboloid is a 3D representation of a parabola. Imagine taking a normal parabola (like y= x^2) and revolving it about the axis that passes through the saddle and the focus (like x=0) and you get a paraboloid. For a set of 2D points in (x,y) format, we can find the "middle" of the point set (center of mass) and set that as (xm, ym). We then set the Z value of the 2D points equal to sqrt((x-xm)^2+(y-ym)^2) and that way we get the paraboloid. Then, we just compute the lower convex hull of the paraboloid and then we can project it onto a 2D plane. This will create a DT of the 2D point set.

I guess my next task is to learn how to get a convex hull in 3D. However, I think I'll start slow and learn how to do it in 2D. It seems there are a lot of techniques and I'll cover some of them in my next post. Happy sciencing!