Triangulation Rhymes With Strangulation

Triangulation is the process of decomposing a simple polygon into a set of triangles.  Recently, a customer uncovered a bug with our triangulation algorithm.  The customer defined the boundary of a polygon that would be rendered on the earth.  Our code failed to triangulate the polygon due to a precision issue.  Additionally, the customer was creating multiple polygons to work around the fact that our code does not allow for holes inside a polygon.

We knew that we were going to rework our triangulation code for Point Break and a customer had an immediate need, so we bumped up the work's priority.  While our current code generally works, it has significant speed and precision issues.  So, we decided to start anew.


"Nothing can happen till you swing the bat."

There are many triangulation algorithms with run times ranging from O(n) to O(n3).  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(n2), 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 lon(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(n2) run time does not scale well.

"Hurry up and sit down."

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(n2).  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.

"It takes an idiot to do cool things.  That's why it's cool."

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.

Number of Vertices Linear Search (secs) Tree Search (secs) x Faster
126 0.000128 0.000177 1.38
1,301 0.007372 0.002058 3.58
14,488 1.124980 0.033220 33.86
16,107 1.742927 0.038522 45.25
20,927 4.648779 0.053389 87.01

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:

Number of Vertices Current Code (secs) New Code (secs) x Faster
1,021 0.016 0.0017 9.4
4,992 0.35 0.0078 44.9
6,494 0.61 0.012 50.8
14,488 3.97 0.031 128.1
20,927 9.28 0.052 178.5

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(n2).  Excellent.  I do not have time for a more rigorous examination of the run times.

"What are you talking about?"

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.

"Where are my eyebrows?"

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.

"How should I know? I'm still in grade school."

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.

2 Responses to “Triangulation Rhymes With Strangulation”

  1. 1 qz0rz

    “Our current code is a basic implementation of ear clipping. While Seidel is expected O(n log(n)) and basic ear clipping is O(n2), 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 lon(n)) was a surprise.”

    lol, that’s awesome… pretty impressive triangulating 20k vertex polygon in 0.05 secs (even on a badass machine)! I dunno what your typical use case is, but this sounds fast enough that you might not have to worry about optimizing it for a while…

  2. 2 deron

    Yeah, I was happy that we did get such good performance. I was also happy to learn that Held is using a form of ear clipping, rather than Seidel, to get near O(n). If I had more time, I’d like to investigate that, but the performance is good enough to move on to more important issues.

    Hopefully, these area targets are the worse case. Another application would be to triangulate a sensor intersection with a central body (earth, moon, Mars, etc.) The number of reflex vertices is the performance limiting factor. If a polygon has no reflex vertices, ear clipping is O(n). A sensor intersection has far fewer reflex vertices than area targets, so I would expect an intersection to also compute quickly.

Comments are currently closed.