Three.JS 中的三角形-三角形交叉点
Triangle-triangle intersections in Three.JS
加载的网格有两个或多个相交的面，我想用不同的颜色显示这些面。我真的不需要交点或线段，我只是在寻找最快的方法来了解两个 faces/triangles 是否相交。在此示例中，应以红色显示三个相交面 (materialIndex=1)。
最初我尝试了几次基于对面 B 使用 raycaster 三次（A 面的每个边缘一次，将 raycaster 限制在两点之间的距离）的测试。但我无法使其工作（在 far/wrong 处检测到大量错误交叉点。
似乎 Tomas Möller 的方法是检测这些交叉点的更快方法之一。我尝试将涉及的计算迁移到Three.JS，我认为一切都在正确的地方，但结果不是预期的结果。
/**
* -----------------------------------------------------------------------
* "A Fast Triangle-Triangle Intersection Test" (by TOMAS MOLLER)
* http://web.stanford.edu/class/cs277/resources/papers/Moller1997b.pdf
* -----------------------------------------------------------------------
*
* Let us denote the two triangles T1 and T2; the vertices of T1 and T2
* by V10,V11,V12, and V20,V21,V22 respectively; and the planes in which the
* triangles lie #1 and #2. First, the plane equation #2: N2 · X + d2 = 0
* (where X is any point on the plane) is computed: (1)
*
* N2 = (V2.1 - V2.0) * (V2.2 - V2.0)
* d2 = -N2 · V2.0
*
* Then the signed distances from the vertices of T1 to #2 (multiplied by
* a constant N2 · N2) are computed by simply inserting the vertices
* into the plane equation: (2)
*
* dV1.i = N2 · V1.i + d2 (i=0,1,2)
*
* Now, if all dV1.i != 0 (i=0,1,2) (that is, no point is on the plane)
* and all have the same sign, then T1 lies on one side of #2 and the overlap
* is rejected. The same is done for T2 and #1. These two early rejection tests
* avoid a lot of computations for some triangle pairs. Indeed, for a pair to
* pass this test there must be some line of direction N1 * N2 that meets both.
*
* If all dV1.i = 0 (i=0,1,2) then the triangles are co-planar, and this case
* is handled separately. If not, the intersection of #1 and #2 is aline,
* L = O + tD, where D = N1 * N2 is the direction of the line and O is some point
* on it. Note that due to our previous calculations and rejections, both triangles
* are guaranteed to intersect L. These intersections form intervals on L, and
* if these intervals overlap, the triangles overlap as well.
**/
此 JSFiddle 包含我正在使用的迁移代码。我使用的是归一化向量，但我想我遗漏了这些值的一些最终计算。
function checkIntersectedFaces(){
var face, vA, vB, vC, vAnorm, vBnorm, vCnorm;
var face2, vA2, vB2, vC2, vA2norm, vB2norm, vC2norm;
// We only focus on the small stand-alone triangle
console.group("CHECKING MAIN FACE (#4)");
face = faces[4];
vA = vertices[face.a].clone();
vB = vertices[face.b].clone();
vC = vertices[face.c].clone();
console.groupCollapsed("face vertices");
console.log("vA, vB, vC");
console.log([vA, vB, vC]);
console.groupEnd("face vertices");
vAnorm = vA.clone().normalize();
vBnorm = vB.clone().normalize();
vCnorm = vC.clone().normalize();
console.groupCollapsed("face vertices (normalized)");
console.log("vAnorm, vBnorm, vCnorm");
console.log([vAnorm, vBnorm, vCnorm]);
console.groupEnd("face vertices (normalized)");
// Compare main face (stand-alone triangle) against all other faces
for(var faceIndex=0; faceIndex< faces.length; faceIndex++){
if(faceIndex == 4) continue; // avoid self-comparison
console.group("VS FACE #" + faceIndex);
face2 = faces[faceIndex];
if(faceIndex == 1 || faceIndex == 3)
console.warn("This face should be detected as INTERSECTED");
vA2 = vertices[face2.a].clone();
vB2 = vertices[face2.b].clone();
vC2 = vertices[face2.c].clone();
console.groupCollapsed("face vertices");
console.log("vA2, vB2, vC2");
console.log([vA2, vB2, vC2]);
console.groupEnd("face vertices");
vA2norm = vA2.clone().normalize();
vB2norm = vB2.clone().normalize();
vC2norm = vC2.clone().normalize();
console.groupCollapsed("face vertices (normalized)");
console.log("vA2norm, vB2norm, vC2norm");
console.log([vA2norm, vB2norm, vC2norm]);
console.groupEnd("face vertices (normalized)");
/////////////////////////////////////////////////////////////
// MOLLER calculations
/////////////////////////////////////////////////////////////
var n2 = vB2.sub(vA2) .multiply( vC2.sub(vA2) );
var d2 = -n2.dot( vA2 );
var dA = n2.dot( vA ) + d2;
var dB = n2.dot( vB ) + d2;
var dC = n2.dot( vC ) + d2;
console.groupCollapsed("n2");
console.log(n2);
console.log("d2", d2);
console.log("dA", dA);
console.log("dB", dB);
console.log("dC", dC);
console.groupEnd("n2");
/////////////////////////////////////////////////////////////
var n2norm = vB2norm.sub(vA2norm) .multiply( vC2norm.sub(vA2norm) );
var d2norm = -n2norm.dot( vA2norm );
var dAnorm = n2norm.dot( vAnorm ) + d2norm;
var dBnorm = n2norm.dot( vBnorm ) + d2norm;
var dCnorm = n2norm.dot( vCnorm ) + d2norm;
console.groupCollapsed("n2 (normalized)");
console.log(n2norm);
console.log("d2", d2norm);
console.log("dA", dAnorm);
console.log("dB", dBnorm);
console.log("dC", dCnorm);
console.groupEnd("n2 (normalized)");
/////////////////////////////////////////////////////////////
// CHECK INTERSECTIONS
/////////////////////////////////////////////////////////////
if(dAnorm!=0 && dBnorm!=0 && dCnorm!=0){
console.warn("NO INTERSECTION");
}
else if(dAnorm==0 && dBnorm==0 && dCnorm==0){
console.warn("CO-PLANAR FACES");
}
else{
console.warn("INTERSECTION FOUND!");
face.materialIndex = 1;
face2.materialIndex = 1;
}
/////////////////////////////////////////////////////////////
/////////////////////////////////////////////////////////////
console.groupEnd("VS FACE #" + faceIndex);
}
console.groupEnd("CHECKING MAIN FACE (#4)");
}
我在 中找到了一个可行的解决方案，它建议使用 Ray.js 及其方法 intersectTriangle()（而不是 Raycaster）。如果你有每个面的三个顶点来比较，它会更快，也更容易使用。然后，您可以将主面的 3 个边缘中的每一个边缘投射到其他每个面上。它 returns 一个向量，边与面的交点。
但似乎您必须遵循某些步骤才能避免在发射射线时出错。首先，将输出变量定义为 Vector3。然后，将 intersectTriangle() 调用的结果分配给该变量，并且还将此输出变量用作调用中的目标。像这样的东西，它看起来多余，但它不能以任何其他方式工作：
var ray = new THREE.Ray();
ray.set(sourceVector, directionVector);
var intersect = new THREE.Vector3();
intersect = ray.intersectTriangle(triangle[0], triangle[1], triangle[2], false, intersect);
（"triangle" 一个简单的数组，其中包含构成要比较的面的 3 个向量）
加载的网格有两个或多个相交的面，我想用不同的颜色显示这些面。我真的不需要交点或线段，我只是在寻找最快的方法来了解两个 faces/triangles 是否相交。在此示例中，应以红色显示三个相交面 (materialIndex=1)。
最初我尝试了几次基于对面 B 使用 raycaster 三次（A 面的每个边缘一次，将 raycaster 限制在两点之间的距离）的测试。但我无法使其工作（在 far/wrong 处检测到大量错误交叉点。
似乎 Tomas Möller 的方法是检测这些交叉点的更快方法之一。我尝试将涉及的计算迁移到Three.JS，我认为一切都在正确的地方，但结果不是预期的结果。
/**
* -----------------------------------------------------------------------
* "A Fast Triangle-Triangle Intersection Test" (by TOMAS MOLLER)
* http://web.stanford.edu/class/cs277/resources/papers/Moller1997b.pdf
* -----------------------------------------------------------------------
*
* Let us denote the two triangles T1 and T2; the vertices of T1 and T2
* by V10,V11,V12, and V20,V21,V22 respectively; and the planes in which the
* triangles lie #1 and #2. First, the plane equation #2: N2 · X + d2 = 0
* (where X is any point on the plane) is computed: (1)
*
* N2 = (V2.1 - V2.0) * (V2.2 - V2.0)
* d2 = -N2 · V2.0
*
* Then the signed distances from the vertices of T1 to #2 (multiplied by
* a constant N2 · N2) are computed by simply inserting the vertices
* into the plane equation: (2)
*
* dV1.i = N2 · V1.i + d2 (i=0,1,2)
*
* Now, if all dV1.i != 0 (i=0,1,2) (that is, no point is on the plane)
* and all have the same sign, then T1 lies on one side of #2 and the overlap
* is rejected. The same is done for T2 and #1. These two early rejection tests
* avoid a lot of computations for some triangle pairs. Indeed, for a pair to
* pass this test there must be some line of direction N1 * N2 that meets both.
*
* If all dV1.i = 0 (i=0,1,2) then the triangles are co-planar, and this case
* is handled separately. If not, the intersection of #1 and #2 is aline,
* L = O + tD, where D = N1 * N2 is the direction of the line and O is some point
* on it. Note that due to our previous calculations and rejections, both triangles
* are guaranteed to intersect L. These intersections form intervals on L, and
* if these intervals overlap, the triangles overlap as well.
**/
此 JSFiddle 包含我正在使用的迁移代码。我使用的是归一化向量，但我想我遗漏了这些值的一些最终计算。
function checkIntersectedFaces(){
var face, vA, vB, vC, vAnorm, vBnorm, vCnorm;
var face2, vA2, vB2, vC2, vA2norm, vB2norm, vC2norm;
// We only focus on the small stand-alone triangle
console.group("CHECKING MAIN FACE (#4)");
face = faces[4];
vA = vertices[face.a].clone();
vB = vertices[face.b].clone();
vC = vertices[face.c].clone();
console.groupCollapsed("face vertices");
console.log("vA, vB, vC");
console.log([vA, vB, vC]);
console.groupEnd("face vertices");
vAnorm = vA.clone().normalize();
vBnorm = vB.clone().normalize();
vCnorm = vC.clone().normalize();
console.groupCollapsed("face vertices (normalized)");
console.log("vAnorm, vBnorm, vCnorm");
console.log([vAnorm, vBnorm, vCnorm]);
console.groupEnd("face vertices (normalized)");
// Compare main face (stand-alone triangle) against all other faces
for(var faceIndex=0; faceIndex< faces.length; faceIndex++){
if(faceIndex == 4) continue; // avoid self-comparison
console.group("VS FACE #" + faceIndex);
face2 = faces[faceIndex];
if(faceIndex == 1 || faceIndex == 3)
console.warn("This face should be detected as INTERSECTED");
vA2 = vertices[face2.a].clone();
vB2 = vertices[face2.b].clone();
vC2 = vertices[face2.c].clone();
console.groupCollapsed("face vertices");
console.log("vA2, vB2, vC2");
console.log([vA2, vB2, vC2]);
console.groupEnd("face vertices");
vA2norm = vA2.clone().normalize();
vB2norm = vB2.clone().normalize();
vC2norm = vC2.clone().normalize();
console.groupCollapsed("face vertices (normalized)");
console.log("vA2norm, vB2norm, vC2norm");
console.log([vA2norm, vB2norm, vC2norm]);
console.groupEnd("face vertices (normalized)");
/////////////////////////////////////////////////////////////
// MOLLER calculations
/////////////////////////////////////////////////////////////
var n2 = vB2.sub(vA2) .multiply( vC2.sub(vA2) );
var d2 = -n2.dot( vA2 );
var dA = n2.dot( vA ) + d2;
var dB = n2.dot( vB ) + d2;
var dC = n2.dot( vC ) + d2;
console.groupCollapsed("n2");
console.log(n2);
console.log("d2", d2);
console.log("dA", dA);
console.log("dB", dB);
console.log("dC", dC);
console.groupEnd("n2");
/////////////////////////////////////////////////////////////
var n2norm = vB2norm.sub(vA2norm) .multiply( vC2norm.sub(vA2norm) );
var d2norm = -n2norm.dot( vA2norm );
var dAnorm = n2norm.dot( vAnorm ) + d2norm;
var dBnorm = n2norm.dot( vBnorm ) + d2norm;
var dCnorm = n2norm.dot( vCnorm ) + d2norm;
console.groupCollapsed("n2 (normalized)");
console.log(n2norm);
console.log("d2", d2norm);
console.log("dA", dAnorm);
console.log("dB", dBnorm);
console.log("dC", dCnorm);
console.groupEnd("n2 (normalized)");
/////////////////////////////////////////////////////////////
// CHECK INTERSECTIONS
/////////////////////////////////////////////////////////////
if(dAnorm!=0 && dBnorm!=0 && dCnorm!=0){
console.warn("NO INTERSECTION");
}
else if(dAnorm==0 && dBnorm==0 && dCnorm==0){
console.warn("CO-PLANAR FACES");
}
else{
console.warn("INTERSECTION FOUND!");
face.materialIndex = 1;
face2.materialIndex = 1;
}
/////////////////////////////////////////////////////////////
/////////////////////////////////////////////////////////////
console.groupEnd("VS FACE #" + faceIndex);
}
console.groupEnd("CHECKING MAIN FACE (#4)");
}
我在
但似乎您必须遵循某些步骤才能避免在发射射线时出错。首先，将输出变量定义为 Vector3。然后，将 intersectTriangle() 调用的结果分配给该变量，并且还将此输出变量用作调用中的目标。像这样的东西，它看起来多余，但它不能以任何其他方式工作：
var ray = new THREE.Ray();
ray.set(sourceVector, directionVector);
var intersect = new THREE.Vector3();
intersect = ray.intersectTriangle(triangle[0], triangle[1], triangle[2], false, intersect);
（"triangle" 一个简单的数组，其中包含构成要比较的面的 3 个向量）