Fast and robust polygon triangulation was the hardest challenge in the period when we developed the OpenGL version of our 2D vector graphics engine (www.amanith

Fast and robust polygon triangulation was the hardest challenge in the period when we developed the OpenGL version of our 2D vector graphics engine (www.amanithvg.com), it was in the early 2000. I clearly remember all such research papers. After studying all of them and after three complete rewrite of the engine, we finally implemented a classic 2 step algo: sweepline polygon decomposition to monotone polygons, and then monotone polygons to triangles. We had really heavy headaches dealing with intersections, autointersections, splitting edges, comparing and merging original vertexes with vertexes created by splitting edges, managing edges connectivity and topology. After some try, we totally discarded the idea to write it in floating point arithmetic, preferring fixed point integers instead (and this was a real turning point for the robustness!). Anyway, good times to remember!