Three.js polygon triangulation fails in pseudo duplicate points

Question

In three.js there is a function triangulateShape(). Now I encountered a failure to triangulate polygons that are simplified using Javascript Clipper. Simplifying in Clipper is done using Unioning. Wikipedia article determines unioning as finding the simple polygon or polygons containing the area inside either of two simple polygons. The same article says that in simple polygon "exactly two edges meet at each vertex" and also determines a weakly simple polygon, where edges can meet, but says nothing about the edge case where edges doesn't meet, but some or many vertices meet. So it's a bit unclear if this like case is simple polygon or weakly simple polygon.

Clipper has selected a permissive approach: simple polygon can have these like touching (or pseudo duplicate) vertices. This Clipper style permissive approach causes that the generated simple polygons are not simple in the meaning of what three.js:s triangulateShape() expects.

The following image shows two examples of this edge case. The left polygon is one "simple" polygon, the red dot is a "duplicate". The right one is as well one "simple" polygon, but the red dot is a "duplicate".

triangulateShape() fails in these cases, because it keeps track of points in array allPointsMap and checks from there if the point is duplicate. To remove these like duplicates I have two options:

---

OPTION 1.

Change Javascript Clipper internal code to handle these using extra parameter eg. breakPolygonByWeakDuplicates for SimplifyPolygon() and SimplifyPolygons(). As Angus Johnson described in his post, the change would be something like:

In the IntersectEdges() method, change the follow from ...

if ( e1Contributing && e2contributing )
{
  if ( e1stops || e2stops || 
    (e1Wc != 0 && e1Wc != 1) || (e2Wc != 0 && e2Wc != 1) ||
    (e1->polyType != e2->polyType && m_ClipType != ctXor) )
      AddLocalMaxPoly(e1, e2, pt); 
  else
      DoBothEdges( e1, e2, pt );
}

to ...

if ( e1Contributing && e2contributing )
{
    AddLocalMaxPoly(e1, e2, pt); 
    AddLocalMinPoly(e1, e2, pt);
}

The change is very easy, but then original Angus Johnson Clipper and Javascript Clipper would not be any more so compatible. Of course if original Clipper would make the change, the Javascript Clipper will follow it.

---

OPTION 2.

To change three.js triangulateShape() source code to accept also pseudo duplicates.

---

My question is: In which end this like extra simplification routine should be done? The first end is creation side (Clipper) and the other end is triangulation side (three.js).

I don't know polygon triangulation routines in various 3D libraries, so cannot imagine how permissive triangulation routines in general are. If someone knows this area, he/she could give more sophisticated answer.

Also I don't know how other boolean libraries handles unioning or simplifying this like pseudo duplicates. There surely is a reason why Clipper is permissive in the means of simple polygon (eg. compatibility with other boolean libraries), but definitely this makes problems in triangulating polygons in three.js.

For reference here is the triangulating code of three.js:

triangulateShape: function ( contour, holes ) {

    var shapeWithoutHoles = THREE.Shape.Utils.removeHoles( contour, holes );

    var shape = shapeWithoutHoles.shape,
        allpoints = shapeWithoutHoles.allpoints,
        isolatedPts = shapeWithoutHoles.isolatedPts;

    var triangles = THREE.FontUtils.Triangulate( shape, false ); // True returns indices for points of spooled shape

    // To maintain reference to old shape, one must match coordinates, or offset the indices from original arrays. It's probably easier to do the first.

    //console.log( "triangles",triangles, triangles.length );
    //console.log( "allpoints",allpoints, allpoints.length );

    var i, il, f, face,
        key, index,
        allPointsMap = {},
        isolatedPointsMap = {};

    // prepare all points map

    for ( i = 0, il = allpoints.length; i < il; i ++ ) {

        key = allpoints[ i ].x + ":" + allpoints[ i ].y;

        if ( allPointsMap[ key ] !== undefined ) {

            console.log( "Duplicate point", key );

        }

        allPointsMap[ key ] = i;

    }

    // check all face vertices against all points map

    for ( i = 0, il = triangles.length; i < il; i ++ ) {

        face = triangles[ i ];

        for ( f = 0; f < 3; f ++ ) {

            key = face[ f ].x + ":" + face[ f ].y;

            index = allPointsMap[ key ];

            if ( index !== undefined ) {

                face[ f ] = index;

            }

        }

    }

    // check isolated points vertices against all points map

    for ( i = 0, il = isolatedPts.length; i < il; i ++ ) {

        face = isolatedPts[ i ];

        for ( f = 0; f < 3; f ++ ) {

            key = face[ f ].x + ":" + face[ f ].y;

            index = allPointsMap[ key ];

            if ( index !== undefined ) {

                face[ f ] = index;

            }

        }

    }

    return triangles.concat( isolatedPts );

}, // end triangulate shapes

---

UPDATE: I made one SVG http://jsbin.com/ugimab/1 where is an example of a polygon that has point (150,150) which is a weak duplicate or pseudo duplicate. The following show various ways to represent this polygon:

var weakDuplicate1 = [{"X":100,"Y":200},{"X":150,"Y":150},{"X":100,"Y":100},{"X":200,"Y":100},{"X":150,"Y":150},{"X":200,"Y":200}];

var weakDuplicate2 = [100,200, 150,150, 100,100, 200,100, 150,150, 200,200];

var weakDuplicate3 = "M100,200 L150,150 L100,100 L200,100 L150,150 L200,200Z";

---

UPDATE: If someone has managed to find a solution for triangulating also polygons which have this like weakly duplicate points, it would be very helpful if you would publish your findings.

---

UPDATE: Tested Option 1, but it was not successful: http://jsbin.com/owivew/1. The polygon remains as one piece, although it should be spitted into two parts. Maybe Angus Johnson (Clipper' creator) has better solution to provide.

---

UPDATE: Here is a more complex "simple" polygon (after simplifying in Clipper). All the points that seems to be together are exactly identical. To divide this to truly simple polygons, would require it to be divided into pieces. My eyes say that here is 4 bottom polygons and one (bigger) upper polygon that has a hole, so as a total simplifying this would produce 5 outer polygons and 1 hole. Or alternatively one outer polygon that have 5 holes. Or possibly some other combination of outers and holes. It can be simplified in many different ways.

The fiddle is in http://jsbin.com/ugimab/3 (also JSON-version of the polygon).

And here are the points numbered from 0 to 25:

In the image vertices 2,11,14,25 are the same coordinate, so it is a "pseudo-multiple-vertice". Vertex3 is not a duplicate, but it touches the edge 6-7.

---

UPDATE:

The suggested method that is based on moving duplicate points seems to work. If the duplicate point is replaced by two points that are on certain distance of the duplicate coordinate, producing "broken pen nib" effect, the triangulation works, because the produced polygons are then true simple polygons, which is the requirement for triangulator. Also there are not allowed to be duplicates between contour and holes nor between holes and holes. The following image shows the effect of this method. The distance is here 10px to show the effect, but in reality eg. 0.001 is enough to make polygons simple. Also default triangulator in Three.js r58 is not working as expected, but if it is changed to Poly2tri, then all is well. The process is described in this rather long bug report: https://github.com/mrdoob/three.js/issues/3386.

Answer 1

You could write a function that detects the duplicate vertices and moves them backward 1px to make them discrete(they no more share a common edge). This way there will be no more common edges and no errors are produced but the visual result still looks the same.

Kind of crude solution but it might work.

Answer 2

There are several issues with the triangulation solution used in three.js. There are several other javascript triangulation libraries available and it might very well be that in the future the current library will be exchanged for something else like for example earcut.js. There is a discussion about this here in this issue on GitHub.

Your issue of self intersecting edges is not a problem for earcut as is demonstrated in this multi viewer here.

---

If you already want to use a different triangulation solution in your project I would like to refer to a three.js triangulation library (an adapter) I made. The adapter allows connecting three other triangulation libraries seamlessly to your three.js project:

• earcut - earcut triangulation library
• poly2tri - poly2tri triangulation library
• libtess - libtess tessellation library

All you need to do is include the triangulation.js file:

<script src="triangulation.js"></script>

And set the library of your choosing using the setLibrary method:

THREE.Triangulation.setLibrary('earcut');

Depending on the library you choose you will obviously need to embed of the files for the library itself. Currently for libtess the additional tessy.js is needed which can be found in the repository.

Read more about the project here on GitHub.