Binding for the clip2tri (poly2tri and clipper) library

[httpdigest]

This is probably too specific, but having a binding for the clip2tri library https://github.com/raptor/clip2tri (MIT license) featuring a very simplistic C interface would be great to have in LWJGL 3, in case people want to triangulate arbitrary 2D polygons with holes, such as when rendering OpenStreetMap data (buildings, greens,...).

[kappaOne]

in case it helps, was looking into this problem a while back too, found that both LibGDX and Slick2D have a nice collection of 2d triangulators written in Java which seem to work well.

[httpdigest]

Thanks, kappa, for mentioning Slick2D. I had a look at LibGDX but their triangulations (ear and delaunay) all cannot handle holes. I would definitely favor a Java solution before going native :) so I'll take a look at Slick2D. Can you say something about the quality of the triangulators there, because sadly neither of the Slick2D triangulators reference any paper of the algorithms they implement, so it is unclear what is implemented there to read about the properties of the algorithm. Also, only the "Mann" triangulator supports holes.

[kappaOne]

From my tests so far LibGDX's EarClippingTriangulator seems the most robust triangulator. The MannTriangulator is also good and even faster in a few cases than the EarClippingTriangulator, however found it glitched on a few use cases (maybe I was using an unsupported draw order or something).

As for holes, I've found that adding a double edge slice and the hole in reverse to the original points/shape allows you to then pretty much use any triangulator (even those that don't support holes), the full technique can be read about at section 3 of this link http://www.geometrictools.com/Documentation/TriangulationByEarClipping.pdf

I've also written a triangulator based on the technique found here http://www.emanueleferonato.com/2011/09/12/create-non-convex-complex-shapes-with-box2d/ which basically splits any concave shape into convex. Then just brute forces the convex shape into triangles (picks a point in the shape and draw lines to all other points in the shape) which works fast. However at the moment it has a few kinks that I'm trying to iron out before it's usable.

Depending on your usecase GPU triangulation seems to be pretty popular (implemented by browser vendors) using the stencil buffer technique (probably could also implement it using a FBO and shaders these days). Some details of the implementation can be found here and here. If usable for your usecase its pretty fast (and supports holes) however has the disadvantage in that it doesn't provide you with the actual points for the new triangles.

[kappaOne]

Also I came across this library which looks pretty nice feature wise, though haven't got round to trying it yet. It has a slightly out of date java port here. It's not much code (single class) so porting the latest javascript version to java doesn't look like a huge task.

[httpdigest]

Thanks, @kappaOne, for all the information; appreciate it! I finally got to trying the JavaScript earcut library. This one works really great on the browser. I had no issues so far triangulating three million OSM buildings in no time. The resulting triangles are as good as can be with such a triangulation algorithm that only works on existing nodes and does not introduce intermediate vertices to produce less degenerate triangles. I begun porting it to Java, because I also need to triangulate on the server.

[httpdigest]

I think this issue can be closed now, since I have no further need for clip2tri.