reflect polygon winding order in triangle winding order

[andreasplesch]

Currently, earcut will always produce triangles in a clockwise winding order, regardless of the sense of the winding order of the original polygon. In 3d, this can reverse the direction of the normal vector which is used for example for lighting calculations of the generated triangles with respect to the original polygon. So for 3d applications it is often required to reflect the winding order of the original polygon in the winding order of the triangles. I created a branch with a few, simple modifications to this effect here: https://github.com/andreasplesch/earcut/tree/ccw-winding I would gladly submit a pull request if there is a desire to accommodate such a feature. There is a performance cost for ccw polygons since the array of indices needs to be reversed. array.reverse(), however, is a native array function, and hopefully optimized. To avoid this cost, it would be necessary to take into account winding order during construction of the triangle list which is also possible.

[andreasplesch]

Alternatively, to avoid the .reverse if not desired, it would be an option to just return the computed winding order of the polygon, in addition to the triangles, and then leave reversing to the consumer, or a wrapper function. However, this requires returning an array or object and would not be compatible.

[mourner]

That's a valid feature request, thanks! My hunch is that reverse is not an efficient way to do this — we need to construct triangles in the right order in place, but I need to confirm that by running benchmarks.

[andreasplesch]

Ok. Another option would be to have a (not required) "keep_sense" parameter for the earcut function. By default, it would be false and there would be no reversing. Only if requested (true) ccw polygon triangles would be reversed. This way, there is backward compatibility and transparency.

[andreasplesch]

x3dom maintainers absorbed earcut with the ccw-winding order patch in place but otherwise unchanged here:

https://github.com/x3dom/x3dom/issues/581

The patch will be available in the developer version of x3dom by tomorrow, and likely in the next stable version. Feel free to look the PR above over and voice concerns if there are any.

Using array.reverse() on polygons with 50k points did not have a noticeable effect on performance in use cases although I am sure there is some cost.

[mourner]

@andreasplesch awesome, thanks for letting me know!

[JamesJungmoonLim]

@andreasplesch there needs to be 'var' in line47.(because it wasn't declared)

[andreasplesch]

@JamesJungmoonLim Thanks !

https://github.com/andreasplesch/earcut/commit/b41cd71ebbf85dc40e9d93b3f85f48c45b1928e1