Fast polygon triangulation (Seidel's Trapezoidation) - reasonably small

[jahting]

Three.js at present includes a Shape/Text triangulation which was easy to implement but also needed several add-ons, eg. to decide between contours and holes and to remove those holes, and it had quite some issues concerning:

• holes in polygons ( #3386: Holes in contours causes triangulation failure (partial solution: #4337); #2919: Triangulation fails for simple shape )
• the sequence of contour and hole polygons ( #4357: toShapes: independence of shape and hole specification order, ref. #3386 )
• the winding order of contour and hole polygons ( #4626: toShapes: Bugfix; new optional parameter: noHoles; #4590: Text Triangulation Issues )
• and finally performance issues: ( #4594, first solution step #4623 )

It seems to work correctly by now but is quite slow if there are many vertices or holes.

Instead of trying to improve the present code further, I created a new project PnlTri.js: Polygon Near-Linear Triangulation in JavaScript

• implementation of Raimund Seidel's randomised polygon trapezoidation and triangulation,
• does not rely on polygon winding order and holes following on their contour,
• reasonably fast: A square with 25000 square holes (~100k vertices -> ~150k triangles) takes less than 3 seconds on my old Laptop (Core 2 Duo T7200, 2 GHz) with Firefox 30.0,
• quite small: adds about 10k to three.min.js or about 2k to the gziped file, and it should be possible to further simplify some functions surrounding triangulation in Three.js,
• tested with all difficult data available to me in the Three.js examples and issues,
• rather robust: in the presence of incompatible input it should produce "wrong" output but not crash.

I also created a branch for Three.js with PnlTri, replacing the present mechanism. So interested users of Three.js can test their data against it. More test data would be welcome.

The main drawback might be that this algorithm often produces rather long, slim triangles. I'm thinking about a post-processing step to improve on this in the future. There is still some room to refactor PnlTri and reduce the code surrounding triangulation in Three.js. The next major step for PnlTri will be to allow polygons with intersections which would also increase robustness further.

@mrdoob: Is it small enough for integration into Three.js, or should it be left for people to combine them on their own ?

[mrdoob]

Hmm, how's it performance wise compared to the current code? If this is a full replacement, I'm tempted to have it as a library outside the lib (used in examples folder) and reduce the code in core even more...

[jahting]

From the past issues you can see that the problems with current implementation start with holes, which are needed for fonts also (e.g. "$", "%", "&").

For polygons without holes the current implementation is quite fast. While it has a worse worst case running time, for all practical cases (fonts or polygons up to at least 500 vertices) it seems to be faster than PnlTri.js . So I guess I should integrate the old core triangulation (which is quite small) for polygons without holes into PnlTri.js too.

For polygons with holes a big advantage of PnlTri.js is that it makes no assumption on winding order, a big problem with the current implementation. Even with using PnlTri.js the extrusion algorithm still relies on winding order (ref. "opQR" in: http://jsfiddle.net/MnV2R/2/) but that might be resolved.

Using my old Laptop (Core 2 Duo T7200, 2 GHz) with Firefox 30.0:

• the tree example from issue #3386 (138 vertices + 44 holes (176 additional vertices) -> 400 triangles) takes with:
  • Three.js: 150 milliseconds
  • PnlTri.js: ~15 milliseconds
• A square with 1600 square holes ( ~6400 vertices -> ~10k triangles) takes with:
  • Three.js: 5.5 seconds - 6 minutes (depending on order of vertices)
  • PnlTri.js: ~240 milliseconds

[mrdoob]

I like the numbers! :)

Do you mind doing a PR with the pnltri.min.js in examples/js and with the relevant examples updated?

[zz85]

:+1:

[jahting]

Triangulation is only used internally by ExtrudeGeometry, ShapeGeometry and TextGeometry and not called explicitly in any example. So changing any example would just require the following glue code:

THREE.Shape.Utils.triangulateShape = function ( contour, holes ) {
    var pnlTriangulator = new PNLTRI.Triangulator();
    return  pnlTriangulator.triangulate_polygon( [ contour ].concat(holes) );
}

... a rather nasty method :-( .

So instead of changing any existing example I would suggest, that I make a copy of webgl_geometry_text.html -> webgl_geometry_text2.html and add this glue code as an additional example.

[mrdoob]

Well, that seems like a good first step. Does the triangulator needs to be instanced all the time, or could it be like this?

THREE.Shape.Utils.triangulateShape = ( function () {
    var pnlTriangulator = new PNLTRI.Triangulator();
    return function ( contour, holes ) {
        return pnlTriangulator.triangulate_polygon( [ contour ].concat(holes) );
    };
} )();

[zz85]

@jahting do you think changing the way we do triangulation as suggested in this issue https://github.com/mrdoob/three.js/issues/4745 would be more better since you're working in this area too?

[jahting]

@zz85 yes I agree with your idea in #4745. As you can see from my example #4950 the API of the present triangulation and my new one is quite small - just an Array of vertex lists (polygons and holes), which are just Arrays of objects with at least the attributes x and y. The resulting triangles are presented as Array of triangles, which are triples of indexes into the original vertex list (faces). This API is not sufficient for triangulations which allow the creation of additional Steiner points, which at present seems not necessary. So it is easy to separate the triangulation and write adapters for other libraries.

[arodic]

Are there any intentions to replace THREE.triangulateShape with pnltri in the future?

[mrdoob]

I think it'll happen eventually. It's a matter of being able to fit it in the ~100kb gzip budget :)

[jahting]

I'm still working on improving performance and functionality and reducing size. It would help if someone knows how to change the output of the closure compiler so it can be used as input to the closure compiler again (for including the compiled version of pnltri in three.js).

[tonnot]

@jahting
Sorry if I ask something already answered...

• does plntri support 'fill' points ( points inside polygons) . For example: I have a square and a point inside it (a symple pyramid) ....
• does plntri support hard lines? ( lines -not polygons- that define alignments that cant be crossed by triangulation). This is the case when you have a quarry or a open pit mine data.
• does plntri support any 'pre-duplicate-analysis' ? (to avoid duplicate points).
• does plntri support any triangle order ? Imagine you have to make some surface cuts to view the relief...

Anyway, thanks for this superb job

[jahting]

@tonnot

• as long as you have polygons without holes pnltri.js behaves exactly like three.js, thus e.g. you could include a 'fill' point by cutting a path to it from a contour point and back. This mechanism allows for duplicate points.
• for polygons with holes I try to answer your questions:
  • no support for 'fill' points at present, but you could replace them with a very small triangular hole
  • I'm not sure I understand your "hard line" question, but I intend to extend pnltri.js to handle line intersections which would also allow to include lines instead of polygons
  • neighboring duplicate points (aka zero length edges) are removed from input, but handling all cases of non-adjacent duplicate points is my next planned extension step
  • I'm not sure I understand your "triangle order" question, but pnltri.js does not order the resulting triangles since running time for sorting is worse than that for triangulation, so I leave it to those users who need it.

I hope I could answer your questions and that pnltri.js is still useful for you.

[mourner]

@mrdoob FYI in case you're still considering a better triangulation algorithm. I wrote https://github.com/mapbox/earcut, ultimately the fastest and smallest (2.3k gzipped) JS triangulation library. It's very robust and scales well with shape complexity. Check it out!

[WestLangley]

@mourner #5959 : - )