There is a triangulateShape() function in three.js . Now I am faced with the inability to triangulate polygons, which are simplified using the Javascript Clipper. Simplification in Clipper is done with Unioning. A Wikipedia article defines union as a search for simple polygons or polygons that contain a region inside any of two simple polygons. The same article says that in a simple polygon "exactly two edges meet at each vertex", it also defines a weakly simple polygon where edges can meet, but does not say anything about the edge case when edges do not meet, but some or many vertices intersect. Therefore, it is a little unclear whether this case is a simple polygon or a weakly simple polygon.
Clipper chose a permissive approach: a simple polygon can have vertices such as touching (or pseudo-doubles). This Clipper-style resolving approach leads to the fact that the generated simple polygons are not simple in the sense of what the three .js: s triangulateShape() expects.
The following figure shows two examples of this case. The left polygon is one “simple” polygon, the red dot is a “duplicate”. The correct one is also one “simple” polygon, but the red dot is the “duplicate”.
triangulateShape() not executed in these cases, since it tracks the points in the allPointsMap array and checks from there if the point is duplicated. To remove these duplicates, I have two options:
OPTION 1.
Modify the internal Javascript Clipper code to process them using an additional parameter, for example. breakPolygonByWeakDuplicates for SimplifyPolygon() and SimplifyPolygons() . As Angus Johnson described in his post , the change would be something like this:
In the IntersectEdges () method, change the value 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 simple, but then the original Angus Johnson Clipper and Javascript Clipper will not be more compatible. Of course, if the original Clipper makes a change, the Javascript Clipper will follow.
OPTION 2.
To modify the source code of three.js triangulateShape() to accept also pseudo duplicates.
My question is: In the end, should this be done as a simplification simplification procedure? The first end is the side of creation (Clipper), and the other end is the side of triangulation (three.js).
I do not know the multifaceted triangulation routines in various three-dimensional libraries, so I can not imagine how permissive triangulation procedures in general. If someone knows this area, he / she can give a more complex answer.
Also, I don't know how other logical libraries handle the union or simplification of this type of pseudo duplicate. Of course, the reason is that Clipper is solvable by means of a simple polygon (for example, compatibility with other Boolean libraries), but it definitely creates problems with triangulating polygons in three .js.
For reference, here is the triangulating code 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 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 , which shows an example of a polygon with a dot (150,150), which is a weak duplicate or pseudo-double. The different ways to represent this polygon are shown below:
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 managed to find a solution for triangulating also polygons that have this as weakly duplicating points, it would be very useful if you published your results.
UPDATE: Tested option 1, but failed: http://jsbin.com/owivew/1 . The polygon remains in one piece, although it must be divided into two parts. Perhaps Angus Johnson (creator of Clipper) has a better solution to provide.
UPDATE: here is a more complex “simple” polygon (after simplification in Clipper). All points that seem together are exactly identical. To divide this into truly simple polygons, it would require that it be divided into pieces. My eyes say that there are four lower polygons and one (larger) upper polygon with a hole, since a complete simplification of this will lead to 5 external polygons and 1 hole. Or, alternatively, one external polygon having 5 holes. Or maybe some other combination of outsiders and holes. It can be simplified in many ways.
The violin is at http://jsbin.com/ugimab/3 (also the JSON version of the polygon).
And here are the points numbered from 0 to 25:
In the image, the vertices 2,11,14,25 are the same coordinate, therefore it is a "pseudo-multiple vertex". Vertex3 is not a duplicate, but it touches the edge of 6-7.
UPDATE:
The proposed method based on moving duplicate points seems to work. If the duplicate point is replaced by two points located at a certain distance from the duplicated coordinate, creating the effect of a “broken pen", the triangulation works because the polygons obtained are true simple polygons, which is a requirement for the triangulator. Also, duplicates between the contour and the holes, as well as between the holes and holes are not allowed. The following figure shows the effect of this method. The distance here is 10px to show the effect, but actually, for example. 0.001 is enough to make polygons simple. Also, the default triangulator in Three.js r58 does not work as expected, but if it is changed to Poly2tri, then everything will be fine. The process is described in this rather long bug report: https://github.com/mrdoob/three.js/issues/3386 .