Three.js多边形三角剖分在伪重复点中失败

Question

在three.js中，有一个函数triangulateShape()。现在，我无法对使用JavaScript Clipper简化的多边形进行三角剖分。 Clipper中的简化是使用Unioning完成的。 Wikipedia article将联合确定为查找简单多边形或包含两个简单多边形中的一个内部区域的多边形。同一篇文章说，在简单多边形中，“每个顶点恰好有两个边相交”，并且还确定了边可以相遇的弱简单多边形，但是对于边不相交但有一些或多个顶点相交的边情况，则没有任何说明。 。因此，尚不清楚这种情况是简单多边形还是弱简单多边形。

Clipper选择了一种允许的方法:简单的多边形可以具有这些点，例如接触(或伪重复)顶点。 This Clipper style permissive approach导致生成的简单多边形在Three.js:s triangulateShape()所期望的意义上并不简单。

下图显示了这种边缘情况的两个示例。左边的多边形是一个“简单”多边形，红点是一个“重复”多边形。右边的也是一个“简单”的多边形，但是红点是“重复的”。

在这种情况下，triangulateShape()会失败，因为它会跟踪allPointsMap数组中的点，并从那里检查该点是否重复。要删除这些类似的重复项，我有两种选择:
OPTION 1.
更改Javascript Clipper内部代码以使用额外的参数(例如)来处理这些代码。 breakPolygonByWeakDuplicates和SimplifyPolygon()的SimplifyPolygons()。正如安格斯·约翰逊(Angus Johnson)描述in his post一样，更改将类似于:

在IntersectEdges()方法中，将跟随项从...更改为...

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

更新:我做了一个SVG http://jsbin.com/ugimab/1，其中有一个点为(150,150)的多边形的示例，该点是弱重复项或伪重复项。下面显示了表示此多边形的各种方法:

var strongDuplicate1 = [{“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”；



更新:如果有人设法找到一种解决方案，也可以对具有类似弱重复点之类的多边形进行三角测量，则如果发布结果，将非常有帮助。

更新:测试了选项1，但未成功: http://jsbin.com/owivew/1。尽管应将其分割为两部分，但该多边形仍保留为一个整体。也许Angus Johnson(Clipper的创造者)有更好的解决方案可以提供。

更新:这是一个更复杂的“简单”多边形(在Clipper中简化后)。似乎在一起的所有观点都是完全相同的。要将其划分为真正简单的多边形，需要将其划分为多个部分。我的眼睛说这是4个底部多边形和一个(较大)上部多边形，其中有一个孔，因此总体上进行简化将产生5个外部多边形和1个孔。或者，一个外部多边形具有5个孔。或者可能是外部和孔的其他组合。可以通过许多不同的方式进行简化。

fiddle 在 http://jsbin.com/ugimab/3(也是多边形的JSON版本)中。

以下是点从0到25的编号:

在图像顶点2,11,14,25是相同的坐标，因此它是“伪多个顶点”。 Vertex3不是重复的，但它触及6-7的边缘。

更新:

基于移动重复点的 The suggested method似乎有效。如果将重复点替换为在重复坐标一定距离上的两个点，从而产生“折断的 Nib ”效果，则三角剖分将起作用，因为生成的多边形然后才是真正的简单多边形，这是三角剖分器的要求。此外，轮廓和孔之间以及孔与孔之间也不允许重复。下图显示了此方法的效果。这里的距离为10px，以显示效果，但实际上例如。 0.001足以使多边形简单。同样，Three.js r58中的默认三角剖分器无法按预期工作，但是如果将其更改为Poly2tri，则一切正常。这个过程在相当长的bug报告中进行了描述: https://github.com/mrdoob/three.js/issues/3386。

Answer 1

您可以编写一个函数来检测重复的顶点并将其向后移动1px，以使其离散(不再共享公共(public)边)。这样，将不再有常见的边缘，并且不会产生任何错误，但是视觉结果仍然相同。

有点粗略的解决方案，但它可能会起作用。