three.jsintersectionface

Triangle-triangle intersections in Three.JS

Having a loaded mesh with two or more intersected faces, I would like to display those faces with a different color. I don´t really need the intersection points or segments, I´m just looking for the fastest way to know if two faces/triangles intersect. In this example, there are three intersected faces that should be displayed in red (materialIndex=1).

enter image description here

Initially I tried several tests based on using a raycaster three times (one for each edge of face A, limiting the raycaster to the distance between both points) against face B. But I wasn´t able to make it work (there was a huge number of false intersections detected, and in far/wrong places.

It seems that the method by Tomas Möller is one of the faster ways to detect these intersections. I tried to migrate the involved calculations to Three.JS, and I think everything is on the right place, but the results are not the ones expected.

/**
 * -----------------------------------------------------------------------
 * "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.
 **/

This JSFiddle contains the migrated code I´m working with. I´m using normalized vectors, but I think I´m missing some final calculation with these values.

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)");
}
Solution

  • I found a working solution in this thread, which suggests using Ray.js and its method intersectTriangle() (instead of Raycaster). It´s faster, and easy to use if you have the three vertices of each face to compare. Then, you can raycast each of the 3 edges of the main face against every other face. It returns a vector with the intersection point of the edge vs face.

    But it seems you must follow certain steps to avoid errors when firing the ray. First, define the output variable as a Vector3. Then, assign the result of the intersectTriangle() call to that variable, AND ALSO use this output variable as the target in the call. Something like this, it looks redundant but it doesn´t work any other way:

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

    (being "triangle" a simple array with the 3 vectors that form the face to compare with)