Имея загруженную сетку с двумя или более пересекающимися гранями, я хотел бы отобразить эти грани другим цветом.Мне не нужны точки пересечения или сегменты, я просто ищу самый быстрый способ узнать, пересекаются ли две грани / треугольника.В этом примере есть три пересекающиеся грани, которые должны отображаться красным цветом (materialIndex = 1).
Сначала я попробовал несколько тестов, основанных на использованииRaycaster три раза (по одному на каждый край лица A, ограничивая Raycaster расстоянием между обеими точками) против лица B. Но я не смог заставить его работать (было обнаружено огромное количество ложных пересечений, и вдальние / неправильные места.
Кажется, что метод Томаса Мёллера - один из самых быстрых способов обнаружения этих пересечений. Я попытался перенести соответствующие вычисления в 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)");
}