Three.js多边形三角剖分在伪重复点中失败 [英] Three.js polygon triangulation fails in pseudo duplicate points
问题描述
在 three.js 中，有一个功能triangulateShape().现在，我无法对使用JavaScript Clipper简化的多边形进行三角剖分. Clipper中的简化是使用Unioning完成的. Wikipedia文章确定联合是在查找两个或两个简单多边形中包含该区域的简单多边形或包含多个多边形的多边形.同一篇文章说，在简单多边形中，每个顶点恰好有两个边相交"，并且还确定了边可以相遇的弱简单多边形，但是对于边不相交但有一些或多个顶点相交的边情况，则没有任何说明. .因此，尚不清楚这种情况是简单多边形还是弱简单多边形.
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选择了一种允许的方法:简单的多边形可以具有这些点，例如接触(或伪重复)顶点. 此Clipper样式的允许方法导致生成的简单多边形不是简单，其含义为three.js:s triangulateShape()期望.
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()会失败，因为它会跟踪数组allPointsMap中的点，并从那里检查该点是否重复.要删除这些类似的重复项，我有两种选择:
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.
更改Javascript Clipper内部代码以使用额外的参数(例如)来处理这些代码. breakPolygonByWeakDuplicates用于SimplifyPolygon()和SimplifyPolygons().正如安格斯·约翰逊(Angus Johnson)在其帖子中所述> 像:
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:
在IntersectEdges()方法中，将跟随项从...更改为
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 );
}
到...
if ( e1Contributing && e2contributing )
{
AddLocalMaxPoly(e1, e2, pt);
AddLocalMinPoly(e1, e2, pt);
}
更改非常容易，但是原始的Angus Johnson Clipper和Javascript Clipper不再兼容.当然，如果原始Clipper可以进行更改，则Javascript Clipper会紧随其后.
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.
要更改three.js triangulateShape()源代码，使其也接受伪重复.
To change three.js triangulateShape() source code to accept also pseudo duplicates.
我的问题是:应该在哪一端进行类似简化的例行程序?一端是创建端(Clipper)，另一端是三角端(three.js).
我不知道各种3D库中的多边形三角剖分例程，因此无法想象总体上三角剖分例程的宽松程度.如果有人知道这方面，他/她可以给出更复杂的答案.
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.
我也不知道其他布尔库如何像伪重复一样处理联合或简化它.肯定Clipper允许使用简单的多边形(例如，与其他布尔库的兼容性)是有原因的，但是，这肯定会导致在three.js中对多边形进行三角剖分的问题.
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.
作为参考，这里是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)为弱副本或伪副本的多边形的示例.下面显示了表示此多边形的各种方法:
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.
更新:已测试选项1，但未成功: http://jsbin.com/owivew/1 .尽管应将其分割为两部分，但该多边形仍保留为一个整体.也许，Clipper的创作者安格斯·约翰逊(Angus Johnson)有更好的解决方案.
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.
更新:这是一个更复杂的简单"多边形(在Clipper中简化后).似乎在一起的所有观点都是完全相同的.要将其划分为真正简单的多边形，需要将其划分为多个部分.我的眼睛说这是4个底部多边形和一个(较大)上部多边形，其中有一个孔，因此总体上进行简化将产生5个外部多边形和1个孔.或者，一个外部多边形具有5个孔.或者可能是外部和孔的其他组合.可以通过许多不同的方式对其进行简化.
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.
小提琴位于 http://jsbin.com/ugimab/3 (也包括JSON-多边形的版本).
The fiddle is in http://jsbin.com/ugimab/3 (also JSON-version of the polygon).
这是从0到25的点:
在图像顶点2,11,14,25是相同的坐标，因此它是伪多重顶点". Vertex3不是重复的，但它触及6-7的边缘.
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.
更新:
建议的方法基于移动重复点似乎有效.如果将重复点替换为在重复坐标一定距离上的两个点，从而产生折断的笔尖"效果，则三角剖分将起作用，因为生成的多边形然后才是真正的简单多边形，这是三角剖分器的要求.同样，轮廓与孔之间以及孔与孔之间也不允许重复.下图显示了此方法的效果.这里的距离为10px，以显示效果，但实际上例如. 0.001足以使多边形简单.同样，Three.js r58中的默认三角剖分器无法按预期工作，但是如果将其更改为Poly2tri，则一切正常.此过程在较长的错误报告中进行了描述: https://github.com/mrdoob /three.js/issues/3386 .
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.
推荐答案
您可以编写一个函数，检测重复的顶点并将它们向后移动1px，以使它们离散(它们不再共享公共边).这样，将不再有常见的边缘并且不会产生任何错误，但是视觉结果仍然看起来相同.
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.
这篇关于Three.js多边形三角剖分在伪重复点中失败的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！
