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

Question

在three.js中有一个功能triangulateShape().现在我遇到了使用Javascript Clipper简化三角形多边形的失败.Clipper中的简化是使用Unioning完成的.维基百科文章将联合确定为找到包含两个简单多边形中任一区域内的区域的简单多边形或多边形.同一篇文章说,在简单的多边形"恰好两个边缘在每个顶点相遇"并且还确定了一个弱简单的多边形,边缘可以在这里面相遇,但是没有说明边缘不满足的边缘情况,但有些或许多顶点相遇.所以有点不清楚这种情况是简单的多边形还是弱简单的多边形.

Clipper选择了一种允许的方法:简单的多边形可以使这些像触摸(或伪复制)顶点.这种Clipper风格的许可方法导致生成的简单多边形在three.js:s triangulateShape()期望的含义中并不简单.

下图显示了此边缘情况的两个示例.左边的多边形是一个"简单"多边形,红点是"重复".右边的也是一个"简单"的多边形,但红点是"重复".

triangulateShape()在这些情况下失败,因为它跟踪数组中的点,allPointsMap并从那里检查点是否重复.要删除这些重复项,我有两个选择:

---

OPTION 1.

更改Javascript Clipper内部代码以使用额外参数来处理这些内容,例如.breakPolygonByWeakDuplicates为SimplifyPolygon()和SimplifyPolygons().正如安格斯约翰逊在其帖子中所描述的那样,改变将是这样的:

在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 );
}

至 ...

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

这种变化非常简单,但原来的Angus Johnson Clipper和Javascript Clipper将不再那么兼容.当然,如果原始Clipper会进行更改,Javascript Clipper将遵循它.

---

OPTION 2.

更改three.js triangulateShape()源代码以接受伪重复项.

---

我的问题是:在哪一端,这应该像额外的简化程序一样？第一端是创建侧(Clipper),另一端是三角测量侧(three.js).

我不知道各种3D库中的多边形三角测量例程,因此无法想象一般的广泛的三角测量例程.如果有人知道这个领域,他/她可以提供更复杂的答案.

另外我不知道其他布尔库如何处理联合或简化伪复制.肯定有一个理由是为什么Clipper在简单多边形方面是允许的(例如与其他布尔库的兼容性),但是这肯定会在three.js中对三角形中的多边形进行三角测量.

这里参考的是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 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";

---

更新:如果有人设法找到一个解决方案来对多边形进行三角测量,这些多边形具有弱复制点,那么如果您要发布您的发现,将会非常有用.

---

更新:测试选项1,但没有成功:http://jsbin.com/owivew/1.多边形保持为一体,尽管它应该分成两部分.也许安格斯约翰逊(Clipper的创造者)有更好的解决方案.

---

更新:这是一个更复杂的"简单"多边形(在Clipper中简化后).所有似乎在一起的点完全相同.要将其划分为真正简单的多边形,需要将其分成几部分.我的眼睛说这里有4个底部多边形和一个(更大)的上部多边形,它有一个洞,因此总体上简化了这将产生5个外部多边形和1个洞.或者可选地,一个外部多边形具有5个孔.或者可能是其他一些outers和hole的组合.它可以通过许多不同的方式简化.

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

以下是0到25之间的点数:

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

---

更新:

基于移动重复点的建议方法似乎有效.如果复制点被重复坐标的特定距离上的两个点替换,产生"破碎的笔尖"效果,则三角测量工作,因为生成的多边形是真正的简单多边形,这是三角形的要求.此外,不允许在轮廓和孔之间以及孔和孔之间重复.下图显示了此方法的效果.这里的距离为10px以显示效果,但实际上例如.0.001足以使多边形变得简单.此外,Three.js r58中的默认三角函数不能按预期工作,但如果将其更改为Poly2tri,那么一切都很好.这个过程在这个相当长的错误报告中描述:https://github.com/mrdoob/three.js/issues/3386.

Answer 1

您可以编写一个函数来检测重复的顶点并将它们向后移动 1px 以使它们离散（它们不再共享公共边）。这样就不会再出现共同的边缘，也不会产生错误，但视觉结果看起来仍然相同。

一种粗略的解决方案，但它可能有效。