Triangulation Rhymes With Strangulation

There are many triangulation algorithms with run times ranging from O(n) to O(n³). From what I can tell, the O(n) method is very complicated and exists only in a paper. The two constantly cited algorithms are ear clipping and Seidel's.

I decided to implement ear clipping and holes using David Eberly's paper Triangulation By Ear Clipping. I recommend reading that paper to better understand what follows. Figures 2 through 9 in the paper present the simplicity of ear clipping. Our current code is a basic implementation of ear clipping. While Seidel is expected O(n log(n)) and basic ear clipping is O(n²), ear clipping is easier to implement and is near O(n log(n)) in practice. Actually, easier was the sole reason; the near O(n log(n)) was a surprise.

In a short time, I successfully implemented ear clipping. The next thing to work on was the speed as the O(n²) run time does not scale well.

The algorithm clips one ear at a time from the polygon. An ear is a triangle that contains no reflex vertices. Eberly defines a reflex vertex as "one for which the interior angle formed by the two edges sharing it is larger than 180 degrees."

Much of the processing time is spent determining if a possible ear contains a reflex vertex. A basic implementation will check against every reflex vertex, a linear search. This is how this method becomes O(n²). To limit the number of checks, I place reflex vertices into leaves of a binary tree. When determining if a triangle is an ear, I only compare the vertices of the leaves that overlap the axis aligned bounding box (AABB) of the ear.

To construct the tree, I create two lists: one contains the reflex vertices sorted along the x axis, one contains them sorted along the y axis. Next, I determine the AABB of the root reflex vertices and split the root along the longest side. I do not halve the AABB; I halve the vertices. For example, if the AABB is longest along the x-axis and there are 256 vertices in the sorted x-axis list, I take the first 128 and assign them to one child and assign the remaining to the other child. I continue processing each child in a similar way. I stop splitting a child when the number of vertices in a child is equal to or less than a threshold, 16; this child is a leaf. In this way, each leaf contains approximately the same number of vertices.

Below is an example showing the different levels of the tree for Australia, starting with the root, and ending with the leaves. The border is in blue, the yellow lines define the final triangulation, and the tree nodes are in transparent gray.

The children are of varying size because they have different AABBs. In general, larger leaves overlap larger triangles.

I compared the speed of triangulating a polygon using the original linear reflex vertex test versus using the tree. The tests were done on a 3.06 GHz Xeon processor. The test data included the polygons for zip codes, states, and countries. The number of reflex vertices in a polygon was typically 40-50% of the total number of vertices.

As expected, the tree search improved the speed more and more as the number of vertices increased. Although I did not do timing tests, the time required to create the tree seemed insignificant compared to the time required to determine the ears.

Here are some timing tests I did comparing our baseline code to the new code for a few polygons:

Once again, the speed up was significant. Customers that load and fill large STK area targets should see a noticeable decrease in scenario load time. Note that times in this table are slightly better than times in the previous table for the same number of vertices; I made other slight improvements to the code between the two tests.

The following chart graphs the creation times for 2086 polygons that I tested.

The creation times for this test set nearly track the n log(n) line, which is also graphed. So in practice, the algorithm is running near O(n log(n)) and far from O(n²). Excellent. I do not have time for a more rigorous examination of the run times.

I decided against halving along a child's AABB because the tree would become unbalanced towards areas of higher reflex vertex density. It did not make sense that checking triangles in higher density areas would take longer than those in lower areas. But, I could be wrong. I will not know unless I test such a tree.

Another way that I tried to reduce the number of reflex vertex checks was to calculate the oriented bounding box (OBB) of the possible ear and compare that against the tree. In Australia above, there are a number of long thin triangles with AABBs that cover much more area than the ears themselves. I surmised that an OBB would fit the ear better and lower the number of leaves that the ear overlaps. Overall, this negatively impacted performance. Calculating the box and executing the OBB vs AABB overlap test was more expensive than the reduction in the number of checks, if any.

I use 16 as the maximum number of vertices per leaf which may not be the best value. I tested 8 and 32. Those value degraded performance. There could be a sweet spot, but I'll leave that for future work.

At AGI, we've been talking about adding holes for years. Using Eberly as a guide, holes were painless to add. The first image at the top is a snapshot from STK's 3D window of a polygon with four holes, a tribute to Patrick Swayze. I've forwarded the screen shot to Christo and hope to begin wrapping the western U.S. soon.

While writing this blog, I came upon this very recent Martin Held presentation noting that ear clipping with geometric hashing is near O(n). I believe that geometric hashing is a fancy way of saying that a grid or tree is being used much in the same way that I did.

I also just read some of Held's FIST paper. I would have benefited greatly if I had read the paper from the start. I only did after building up enough steam to locate a postscript reader. Rather than using a tree, he uses a grid. The size of the grid is based on the number of vertices, the aspect ratio of the AABB, and an experimentally determined constant. I had considered a grid as I had recalled that a grid is used to accelerate the point in polygon test described by Eric Haines in Graphics Gems IV. We implemented Haines' test for STK/Coverage with great effect. However, there were issues with precision, memory usage, and determining the grid's optimal size that made me shy away from this approach. Given Held's paper though, I would like to try the grid in the future.

I've completed the first phase of reworking our triangulation code. Our new triangulation code executes faster, scales better, and can handle holes. That's pretty good for nearly a month's work. There is still much to be done, however. The code does not handle a polygon that overlaps itself. Triangulating polygons on the earth that span more than 180 degrees in longitude do not work. The code can produce long thin triangles that are bad for lighting. We will get to all that, but for now there are more pressing issues to resolve for the most frabjous Point Break alpha.