Three.js 多边形三角剖分在伪重复点中失败 [英] Three.js polygon triangulation fails in pseudo duplicate points
问题描述
在 所描述的那样，变化将是喜欢:
在 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);别的DoBothEdges( e1, e2, pt );}到...
<前>if ( e1Contributing && e2contributing ){AddLocalMaxPoly(e1, e2, pt);AddLocalMinPoly(e1, e2, pt);}更改非常容易，但是原来的 Angus Johnson Clipper 和 Javascript Clipper 将不再那么兼容.当然，如果原来的 Clipper 会做出改变，Javascript Clipper 也会跟着做.
<小时>选项 2.
更改three.js triangulateShape() 源代码以接受伪重复项.
我的问题是:这种额外的简化程序应该在哪一端完成?第一端是创建端(Clipper)，另一端是三角剖分端(three.js).
我不知道各种 3D 库中的多边形三角剖分例程，因此无法想象一般的三角剖分例程有多么宽松.如果有人知道这个领域，他/她可以给出更复杂的答案.
此外，我不知道其他布尔库如何处理联合或简化，如伪重复.Clipper 允许简单多边形的方式肯定是有原因的(例如，与其他布尔库的兼容性)，但这肯定会导致在 Three.js 中对多边形进行三角剖分.
参考这里是three.js的三角代码:
triangulateShape:函数(轮廓，孔){var shapeWithoutHoles = THREE.Shape.Utils.removeHoles(轮廓，孔)；var shape = shapeWithoutHoles.shape,allpoints = shapeWithoutHoles.allpoints,isolatedPts = shapeWithoutHoles.isolatedPts;var 三角形 = THREE.FontUtils.Triangulate( shape, false );//True 返回线轴形状点的索引//要保持对旧形状的引用，必须匹配坐标，或从原始数组偏移索引.做第一个可能更容易.//console.log( "triangles",triangles,triangles.length);//console.log("allpoints",allpoints, allpoints.length);var i, il, f, 脸,键、索引、allPointsMap = {},孤立点地图 = {};//准备所有点映射for ( i = 0, il = allpoints.length; i <小时>
更新:我制作了一个 SVG 似乎有效.如果将复制点替换为复制坐标一定距离上的两个点，产生断笔尖"效果，则三角剖分起作用，因为生成的多边形是真正的简单多边形，这是三角剖分器的要求.轮廓与孔之间、孔与孔之间也不允许重复.下图展示了这种方法的效果.此处的距离为 10px 以显示效果，但实际上例如.0.001 足以使多边形变得简单.Three.js r58 中的默认三角测量器也没有按预期工作，但如果将其更改为 Poly2tri，则一切正常.这个相当长的错误报告描述了这个过程:https://github.com/mrdoob/three.js/issues/3386.
您可以编写一个函数来检测重复的顶点并将它们向后移动 1px 以使它们离散(它们不再共享公共边).这样就不会再有共同的边缘，也不会产生错误，但视觉效果看起来还是一样的.
粗略的解决方案，但它可能会奏效.
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.
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屋！
