RE: [Algorithms] fast triangle-segment test *with precomputation*

[Norman V. <nh...@ca...>]

Charles Bloom writes:
>
>Ok, so the Moller+Haines triangle-segment test is about
>as good as it gets without any precomputation.  The
>question is, how fast can you get with arbitrary
>precomputation?  For example, I can precompute the
>plane of the triangle, and the three perpendicular
>planes which go through the edges.  Then the intersections
>are all rays that hit the plane of the triangle and
>whose intersection point is inside the three planes.
>(BTW I don't care about computing the barycentric
>coordinates).

Hey I want to know the same thing !

Here is a naive beginning :-)

Norman


// check to see if the intersection point is  actually inside this face
static bool PointInTriangle( Vec3 point, Vec3 tri[3] )
{
    REAL xmin, xmax, ymin, ymax, zmin, zmax;

    // punt if outside bouding cube
    if ( point[0] < (xmin = MIN3 (tri[0][0], tri[1][0], tri[2][0])) ) {
        return false;
    } else if ( point[0] > (xmax = MAX3 (tri[0][0], tri[1][0], tri[2][0])) )
{
        return false;
    } else if ( point[1] < (ymin = MIN3 (tri[0][1], tri[1][1], tri[2][1])) )
{
        return false;
    } else if ( point[1] > (ymax = MAX3 (tri[0][1], tri[1][1], tri[2][1])) )
{
        return false;
    } else if ( point[2] < (zmin = MIN3 (tri[0][2], tri[1][2], tri[2][2])) )
{
        return false;
    } else if ( point[2] > (zmax = MAX3 (tri[0][2], tri[1][2], tri[2][2])) )
{
        return false;
    }

    // drop the smallest dimension so we only have to work in 2d.

    REAL dx = xmax - xmin;
    REAL dy = ymax - ymin;
    REAL dz = zmax - zmin;
    REAL min_dim = MIN3 (dx, dy, dz);

    REAL x1, y1, x2, y2, x3, y3, rx, ry;

    if ( fabs(min_dim-dx) <= MY_EPSILON ) {
        // x is the smallest dimension
        x1 = point[1];
        y1 = point[2];
        x2 = tri[0][1];
        y2 = tri[0][2];
        x3 = tri[1][1];
        y3 = tri[1][2];
        rx = tri[2][1];
        ry = tri[2][2];
    } else if ( fabs(min_dim-dy) <= MY_EPSILON ) {
        // y is the smallest dimension
        x1 = point[0];
        y1 = point[2];
        x2 = tri[0][0];
        y2 = tri[0][2];
        x3 = tri[1][0];
        y3 = tri[1][2];
        rx = tri[2][0];
        ry = tri[2][2];
    } else if ( fabs(min_dim-dz) <= MY_EPSILON ) {
        // z is the smallest dimension
        x1 = point[0];
        y1 = point[1];
        x2 = tri[0][0];
        y2 = tri[0][1];
        x3 = tri[1][0];
        y3 = tri[1][1];
        rx = tri[2][0];
        ry = tri[2][1];
    } else {
        // all dimensions are really small so lets call it close
        // enough and return a successful match
        return true;
    }

    // check if intersection point is on the same side of p1 <-> p2 as p3
    REAL tmp = (y2 - y3) / (x2 - x3);
    int side1 = SIGN (tmp * (rx - x3) + y3 - ry);
    int side2 = SIGN (tmp * (x1 - x3) + y3 - y1);
    if ( side1 != side2 ) {
        // printf("failed side 1 check\n");
        return false;
    }

    // check if intersection point is on correct side of p2 <-> p3 as p1
    tmp = (y3 - ry) / (x3 - rx);
    side1 = SIGN (tmp * (x2 - rx) + ry - y2);
    side2 = SIGN (tmp * (x1 - rx) + ry - y1);
    if ( side1 != side2 ) {
        // printf("failed side 2 check\n");
        return false;
    }

    // check if intersection point is on correct side of p1 <-> p3 as p2
    tmp = (y2 - ry) / (x2 - rx);
    side1 = SIGN (tmp * (x3 - rx) + ry - y3);
    side2 = SIGN (tmp * (x1 - rx) + ry - y1);
    if ( side1 != side2 ) {
        // printf("failed side 3  check\n");
        return false;
    }

    return true;
}