|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:
- 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.
- 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.
- Remove the triangles so you have a void in the DT.
- Take all the points on the edges of that void and make triangles that include the new point as a vertex.
- Repeat this until you've added all the points from the original set.
- Now remove all triangles that have any "supervertices".
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!