Earcut: Interesting new polygon triangulator

[mrdoob]

https://github.com/mapbox/earcut

@jahting did you had a look at it?

[zz85]

interesting!

[mrdoob]

If someone has some spare time would be nice to test it out and see how it compares.

[mourner]

Hey guys, I wrote this thing. Let me know if you need any help with it. :) A big fan of your work!

[tonnot]

@mourner .
I have some doubts:
1.- Does earcut create a right delaunay network?
2.- Is (or would it be ) it possible to add fill points ?
3.- Is (or would it be) it possible to add hard / break lines to create constrained D. ?
(as in http://www.iue.tuwien.ac.at/phd/fleischmann/node51.html)

[mourner]

@tonnot
To answer 1 and 3 — no, it does not align with goals of the library. Here's a quote from the readme:

The aim of this project is to create a JS triangulation library that is fast enough for real-time triangulation in the browser, sacrificing triangulation quality for raw speed and simplicity, while being robust enough to handle most practical datasets without crashing or producing garbage.

While Constrained Delaunay triangulation produces optimal quality triangulation without sliver triangles, it is pretty expensive to do. Look at the benchmarks — poly2tri.js which implements CDT is 6-20x slower, considering that it's also not robust — it'll fail completely on lots of conditions like duplicate vertices, vertices touching edges, any kinds of self-intersections etc. Combining it with something like Clipper.js for cleaning up complex polygons dramatically slows it down even further while adding complexity. For the use cases Earcut was created, this wasn't acceptable.

2 — Yes, it'll be very easy to add fill points support. They'll be handled pretty much the same way as holes.

[tonnot]

OK, Thank you.

[mourner]

FYI just released 2.0.0 which is even faster, more robust and takes less memory than last time you've checked. :) PIXI.js is going to switch in a few days. You should too. :)

[mourner]

@mrdoob any comments? What did you decide?

[mrdoob]

I think it's great! But seems like no one is stepping in to give it a go 😕

[felixpalmer]

For reference, here is how earcut can be integrated with THREE.js (following the patching approach taken with pnltri.js):

var toList = function ( contour, holes ) {
  var list = [];
  contour.forEach( function ( v ) { list.push( v.x, v.y ); } );
  holes.forEach( function ( hole ) {
    hole.forEach( function ( v ) { list.push( v.x, v.y ); } );
  } );
  return list;
};
var flattenShape = function ( contour, holes ) {
    var result = { vertices: toList( contour, holes ), holes: [], dimensions: 2 };
    var holeIndex = contour.length;
    holes.forEach( function ( hole ) {
      result.holes.push( holeIndex );
      holeIndex += hole.length;
    } );
    return result;
};
THREE.Shape.Utils.triangulateShape = ( function () {
  return function triangulateShape( contour, holes ) {
    var data = flattenShape( contour, holes );
    var result = earcut( data.vertices, data.holes, data.dimensions );
    var grouped = [];
    for ( var i = 0, il = result.length; i < il; i += 3 ) {
      grouped.push( [result[i], result[i+1], result[i+2]] );
    }
    return grouped;
  };
} )();

Generally I've found the performance and results to be great, in line with what is claimed on earcut's GH page. I've been testing on fairly difficult OSM forest outlines (which was crashing the built-in triangulation because it couldn't cut paths to the holes).

[mourner]

@felixpalmer great to hear that, thanks for looking into this! Would you be up to making a PR to THREE.js for Earcut integration?

I rewrote your code slightly to make it a bit faster and simpler (avoiding forEach in hot code):

function addContour( vertices, contour ) {
    for ( var i = 0; i < contour.length; i++ ) {
        vertices.push( contour[i].x );
        vertices.push( contour[i].y );
    }
}

THREE.Shape.Utils.triangulateShape = function ( contour, holes ) {
    var vertices = [];

    addContour( vertices, contour );

    var holeIndices = [];
    var holeIndex = contour.length;

    for ( i = 0; i < holes.length; i++ ) {
        holeIndices.push( holeIndex );
        holeIndex += holes[i].length;
        addContour( vertices, holes[i] );
    }

    var result = earcut( vertices, holeIndices, 2 );

    var grouped = [];
    for ( var i = 0; i < result.length; i += 3 ) {
        grouped.push( result.slice( i, i + 3 ) );
    }
    return grouped;
};

@mrdoob would you only consider a THREE.js PR with the patched Earcut integration, or be up to a PR that fully replaces triangulation code with Earcut?

[mrdoob]

Lets start by doing a webgl_geometry_text3.html (based on webgl_geometry_text2.html) that uses Earcut 😊

[felixpalmer]

@mrdoob @mourner done.

Also see http://www.piste.io/ for a larger integration, I use it to triangulate the forests

[MasterJames]

I get missing the following required extensions: OES_texture_float_linear
But on a Samsung Galaxy Note 3
With Chrome 46.0.2490.76
It should not be not working I figured?

[Wilt]

If I am not mistaken earcut allows also for triangulation in 3rd dimension. This makes it possible to define something like a THREE.Path3 and THREE.Shape3 where points are all in the same 3D plane.

I could use something like that. I mentioned that earlier in this issue.

Right now I solve this by defining a transformation matrix using the plane normal and position and then I transform all vectors using this matrix. Then I do the triangulation and then I transform the result back with the inverse matrix.

[mourner]

@Wilt note that Earcut triangulates 3D in the sense that z coordinate is disregarded (as if you triangulated a projection on a XY plane), but z coordinate is retained in the result. 3D triangulation is hard to define, but triangulation of a projection is one of the common approaches.

[Wilt]

So it is not calculating the z values for new vectors at all?

[Wilt]

I made a fork from earcut and did some testing to see how it works. It can be found here if someone is interested.

Here a running html test page. I will try to add more tests and maybe an interface to add your own test soon.

If there is interest I can also make a repository where several clipping libraries are merged and we can compare results.

I am also working on updating ThreeCSS/ThreeBSP from Chander Prall to work with the THREE.BufferGeometry class directly. I already have a toBufferGeometry method implemented. You can see that here in an example. where I show result from my ThreeBSP.toBufferGeometry method.

I would in the and like to work on a boolean library that uses a faster clipping algorithm like earcut or poly2tri. The thing with boolean operations is that it is much more complicated. So some help would be nice :P

For me it is not only about speed, but I want to prevent that I get artifacts in my result like T crossings (or however I should name those; I mean additional (unneeded points on the edges)).

[WestLangley]

@Wilt + 1

[Wilt]

I made an update for ThreeBSP here in my develop branch and here you can see that it is working for both indexed and non indexed buffer geometries.

[Wilt]

Here a first attempt to make some comparison of polygon tiangulation with the different libraries. For now I simply exchange the Shape.Utils.triangulate and Shape.Utils.triangulateShape methods with other ones depending on the chosen algorithm/library on runtime.
The multiple viewer is kind of nice because you can see the triangulation result of the 4 different algorithms in one overview...

When implementing this for real the code can of course be written much more efficient since now each method is adapted to the existing three.js code.

It could also be a nice idea to allow the user to choose a triangulation library themselves. Why restrict it if it can work with several ones. Some will like the speed of earcut, others like maybe the results of poly2tri. We could just provide triangulation adapters. The different algorithm adapters can go in a three.js/extras/triangulation folder.

If we make more neutral code people can write even their own adapter to another triangulation algorithm/library and offer it in a pull request.

[WestLangley]

@Wilt Sweet! I like the multi-viewer.

[Wilt]

@WestLangley Happy you like it :D
Maybe not the right place to ask it, but was that the most efficient way to get those cameras in sync?

[mrdoob]

Yeah, I like the multi-viewer too!

I think showing the shape that is being triangulated, the number of resulting triangles and the milliseconds that each library took would be great additions.

[Wilt]

@mrdoob I will work on this as soon as I have some time. It might not be too soon, since I am also very busy with the project where I am using your awesome framework.

[WestLangley]

was that the most efficient way to get those cameras in sync?

@Wilt Probably. But I'd remove the animation loop. You don't need it. Use a modification of this pattern:

controls.addEventListener( 'change', render );