Investigate new triangulation library

[pjcozzi]

https://github.com/mapbox/seidel

Investigate for speed and robustness.

In addition to the runtime for the algorithm itself, we also care about the shape of the triangles that it produces since this will impact the speed of the Cesium subdivision step and the number of triangles it produces.

@DavidHudlow this may be of interest to you.

[pjcozzi]

We may also be interested in constrained Delaunay triangulation to produce better triangles for subdivision. @mourner mentioned a library at FOSS4G.

[mourner]

https://github.com/r3mi/poly2tri.js. It's pretty sensitive to polygon quality though.

I'm currently investigating a new triangulation algorithm here, could replace my Seidel's implementation because it claims to be a constant factor of 40 faster: http://www.cis.usouthal.edu/~hain/general/Publications/CISST'05_Trapezoidation.pdf
http://www.cis.usouthal.edu/~hain/general/Theses/Gulve_thesis.pdf

[pjcozzi]

Cool, looking forward to your results.

You are also welcome to take a look at the randomized algorithm (expected n log n) we currently use by @DavidHudlow (in #947):

https://github.com/AnalyticalGraphicsInc/cesium/blob/master/Source/Core/PolygonPipeline.js#L705

[mourner]

OK, found a public implementation listing in the perf comparison thesis (my second link above), so should be pretty straightforward. The only problem is to convert resulting trapezoid sequences into triangles efficiently.

[pjcozzi]

Nice. If it is useful, the triangulation of any simple polygon of n vertices is always n - 2 triangles so it is easy to allocate the index buffer in advance. I image trapezoids could just be bisected using the shorter of the two possible edges to produce reasonable-ish triangles. What issues do you see?

[mourner]

@pjcozzi that would produce many more triangles than needed (trapezoids have a lot of "additional" nodes) — I'll probably use something similar to what I have in seidel – convert trapezoid sequences into multiple monotone mountains by connecting nodes at the right time, and then triangulate each mountain. Just needs porting implementation properly and adjusting triangulation for the new algorithm's output.

[pjcozzi]

ah, right. I see. Sorry, I have not actually implemented trapezoidal decomposition.

[mourner]

@pjcozzi FYI I wrote a new JS library for triangulation, this time much more robust while being many times faster. It's pretty awesome. Check it out: https://github.com/mapbox/earcut

[mourner]

It focuses on triangulation speed over quality though — producing less sliver triangles is something I might look into in future.

[pjcozzi]

Thanks for the note @mourner. We'll have a look when we revisit this again.