Surface triangulation - Redemption

28 Sep 2014

I’m not dead yet, and I’m still working on the game, hopefully a lot more after this post, now that I’ve finally fixed the dreaded polygon triangulation algorithm I talked about in previous posts.

As a quick refresher, the problem I got stuck at was that polygon triangulation failed for polygons with vertical edges, and none of authors of the many different papers and slide decks on the algorithm was kind enough to mention how to deal with them. After a few failed attempts and a lot of reading, I got a little fed up with the thing, so I posted a question on Stack Overflow, and temporarily suspended work on the game. Sadly, my Stack Overflow question did not result in any useful solutions, so I decided to copy a few open-source libraries that implement polygon triangulation to my laptop before a long flight back after a business trip. The piece of code that finally revealed the solution was poly2tri by Wu Liang. This small C program has a debug mode that writes a log of the various steps performed by the algorithm, and upon feeding it my problematic test polygon (a left-pointing arrow) it was immediately clear that my own implementation was incorrectly classifying vertices with incident vertical edges.

Instead of going into a lot of detail about the actual problem and its solution here, I’ll refer to my Stack Overflow question, which I answered myself with a description of the solution. In its current state the triangulation algorithm works for all my test cases, which are quite a few now, covering every corner case I could come up with.

Next steps

With the triangulation problem out of the way – it only took me 2 months :-/ – I can finally move on to rendering the planet surface (which is, of course, a large polygon that needs to be triangulated). Hopefully the next update will take a little less than 2 months, and will again have some images or video for a change ;-)

Development scoreboard

I kind of lost track of the time spent trying to get the triangulation algorithm working, but I estimate another 15 hours on top of the 20 I already spent on it is not too far off the mark. This means total development time is now at about 86 hours. SLOC count is still 1249, just like it was at the time of my previous post. Can you imagine it, 15 hours of dicking around, and not a single line of code was added to fix the algorithm… Fun fact: the unit tests are now 781 SLOC, which is more than double compared to before I started working on the triangulation algorithm.