<p dir="auto">Here is the sample illustrating the bug :</p>
<p dir="auto"><a href="http://jsfiddle.net/mzQnF/" rel="nofollow">http://jsfiddle.net/mzQnF/</a><br>
(just left-click to begin the camera animation)</p>
<p dir="auto">The scene is composed of an half sphere illuminated with two point lights, red and blue.<br>
A symmetry with the xy plane has been applied to the half sphere.</p>
<p dir="auto">The sphere's normals are not inverted as expected.</p>
<p dir="auto">Moreover, if doubleSided is activated, the illumination is not coherent, and the specular component is missing.</p>
<p dir="auto">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:</p>
<ul dir="auto">
<li>holes in polygons ( <a class="issue-link js-issue-link" data-error-text="Failed to load title" data-id="13703525" data-permission-text="Title is private" data-url="https://github.com/mrdoob/three.js/issues/3386" data-hovercard-type="issue" data-hovercard-url="/mrdoob/three.js/issues/3386/hovercard" href="https://github.com/mrdoob/three.js/issues/3386">#3386</a>: Holes in contours causes triangulation failure (partial solution: <a class="issue-link js-issue-link" data-error-text="Failed to load title" data-id="26317338" data-permission-text="Title is private" data-url="https://github.com/mrdoob/three.js/issues/4337" data-hovercard-type="pull_request" data-hovercard-url="/mrdoob/three.js/pull/4337/hovercard" href="https://github.com/mrdoob/three.js/pull/4337">#4337</a>); <a class="issue-link js-issue-link" data-error-text="Failed to load title" data-id="9924561" data-permission-text="Title is private" data-url="https://github.com/mrdoob/three.js/issues/2919" data-hovercard-type="issue" data-hovercard-url="/mrdoob/three.js/issues/2919/hovercard" href="https://github.com/mrdoob/three.js/issues/2919">#2919</a>: Triangulation fails for simple shape )</li>
<li>the sequence of contour and hole polygons ( <a class="issue-link js-issue-link" data-error-text="Failed to load title" data-id="26506499" data-permission-text="Title is private" data-url="https://github.com/mrdoob/three.js/issues/4357" data-hovercard-type="pull_request" data-hovercard-url="/mrdoob/three.js/pull/4357/hovercard" href="https://github.com/mrdoob/three.js/pull/4357">#4357</a>: toShapes: independence of shape and hole specification order, ref. <a class="issue-link js-issue-link" data-error-text="Failed to load title" data-id="13703525" data-permission-text="Title is private" data-url="https://github.com/mrdoob/three.js/issues/3386" data-hovercard-type="issue" data-hovercard-url="/mrdoob/three.js/issues/3386/hovercard" href="https://github.com/mrdoob/three.js/issues/3386">#3386</a> )</li>
<li>the winding order of contour and hole polygons ( <a class="issue-link js-issue-link" data-error-text="Failed to load title" data-id="30422128" data-permission-text="Title is private" data-url="https://github.com/mrdoob/three.js/issues/4626" data-hovercard-type="pull_request" data-hovercard-url="/mrdoob/three.js/pull/4626/hovercard" href="https://github.com/mrdoob/three.js/pull/4626">#4626</a>: toShapes: Bugfix; new optional parameter: noHoles; <a class="issue-link js-issue-link" data-error-text="Failed to load title" data-id="29706210" data-permission-text="Title is private" data-url="https://github.com/mrdoob/three.js/issues/4590" data-hovercard-type="issue" data-hovercard-url="/mrdoob/three.js/issues/4590/hovercard" href="https://github.com/mrdoob/three.js/issues/4590">#4590</a>: Text Triangulation Issues )</li>
<li>and finally performance issues: ( <a class="issue-link js-issue-link" data-error-text="Failed to load title" data-id="29788019" data-permission-text="Title is private" data-url="https://github.com/mrdoob/three.js/issues/4594" data-hovercard-type="issue" data-hovercard-url="/mrdoob/three.js/issues/4594/hovercard" href="https://github.com/mrdoob/three.js/issues/4594">#4594</a>, first solution step <a class="issue-link js-issue-link" data-error-text="Failed to load title" data-id="30403302" data-permission-text="Title is private" data-url="https://github.com/mrdoob/three.js/issues/4623" data-hovercard-type="pull_request" data-hovercard-url="/mrdoob/three.js/pull/4623/hovercard" href="https://github.com/mrdoob/three.js/pull/4623">#4623</a> )</li>
</ul>
<p dir="auto">It seems to work correctly by now but is quite slow if there are many vertices or holes.</p>
<p dir="auto">Instead of trying to improve the present code further, I created a new project <a href="https://github.com/jahting/pnltri.js">PnlTri.js</a>: <strong>Polygon Near-Linear Triangulation in JavaScript</strong></p>
<ul dir="auto">
<li>implementation of Raimund Seidel's randomised polygon trapezoidation and triangulation,</li>
<li>does not rely on polygon winding order and holes following on their contour,</li>
<li>reasonably <strong>fast</strong>: A square with 25000 square holes (~100k vertices -&gt; ~150k triangles) takes less than 3 seconds on my old Laptop (Core 2 Duo T7200, 2 GHz) with Firefox 30.0,</li>
<li>quite <strong>small</strong>: 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,</li>
<li>tested with all <em>difficult</em> data available to me in the Three.js examples and issues,</li>
<li>rather robust: in the presence of incompatible input it should produce "wrong" output but not crash.</li>
</ul>
<p dir="auto">I also created a branch for <a href="https://github.com/jahting/three.js/tree/withPnltri">Three.js with PnlTri</a>, replacing the present mechanism.<br>
So interested users of Three.js can test their data against it. More test data would be welcome.</p>
<p dir="auto">The main <strong>drawback</strong> 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.<br>
There is still some room to refactor PnlTri and reduce the code surrounding triangulation in Three.js.<br>
The next major step for PnlTri will be to allow polygons with intersections which would also increase robustness further.</p>
<p dir="auto"><a class="user-mention notranslate" data-hovercard-type="user" data-hovercard-url="/users/mrdoob/hovercard" data-octo-click="hovercard-link-click" data-octo-dimensions="link_type:self" href="https://github.com/mrdoob">@mrdoob</a>: Is it small enough for integration into Three.js, or should it be left for people to combine them on their own ?</p>