3D rectangle, as a polygon? or a 3D box? How is your triangle and rectangle defined? 3 and 4 points? Do they have a normal vector supplied?

In any case, The SAT should sort it out simply and efficiently.

As long as the 4 points of the box lie in the same plane (if not you'll have to treat it as 2x triangles and decide on which diagonal to split)

Treat your triangle as 3 rays, if 2 rays intersect the plane the quad lies in form a line between these 2 intersections. Now you've got a line in quad test, you can do this in 2D (which is much more robust) by projecting onto the best fitting 2D plane. (so that the projection has the largest area) For example if your plane has a y normal component of 0.9 you project onto the XZ plane. If you plane has a x normal component of -0.9 you project YZ plane.

Hope that helps :)

Quote:Original post by captainfreedom
Thanks for your answer, Martin.
What is the "line in quad" test?

Ok, consider each point on your line, do point in polygon, if either point is in the quad you can say yes, intersection occured.

Now you only have to handle the corner case both points are outside of the quad but the line crosses the quad boundaries. You simply have to check if your line intersects any of the 4 lines comprising the quads. Google 2D line intersection should give you the answer. You can early out the moment your line crosses any one of the quads boundary lines.

the SAT is the separation axis theorem.

What the sat tells you is that if there is a plane separating two convex objects (here, triangle and rectangle), where both objects do not intersect that plane, then the objects cannot intersect.

objects not intersecting...




objects intersecting



In theory, where you have two objects that do not intersect, there is an infinite number of planes separating them. However, given the topology of the two objects, you can reduce your to to only a handful of objects.

The SAT works by 'squishing' objects from 3 dimensions, into several test in one dimension.

If you imagine a plane in 3D (any plane), and project the objects onto that plane, then this reduces the dimensions to 2D. For example, what you do to render 3D graphics onto a 2D screen, is project each objects onto a 2D plane (that simulates the display of an imaginary camera in 3D).

The SAT goes further and projects the objects onto a single line, thus reducing them to 1D. Using a simple interval test, and a handful of lines on which you project the objects, you can detect if two objects intersect in 3D.


this is the process for a 2D SAT test (using 2D polygons).

to solve the SAT, you need two things.
1) a 'project' function that projects an object onto an axis, thus reducing the object to 1D.
2) a list of axis to test against.

the projection function is simple, without considering any kind of optimisation. You just take the min and max of the dot products of every vertices making up that object along an axis (which is just a vector).

void calculateMinMax(Vector axis, Vector* vertices, int verticesCount, float& min, float& max){    min = max = vertices[0].dotProduct(axis);    for(int i = 1; i < verticesCount; i ++)    {        float d = vertices.dotProduct(axis);        if(d < min) min = d;        else if (d > max) max = d;    }}

now, to work out which axes to test, the process is quite simple for two convex polygons (i.e. a triangle and a rectangle). you test against :

1) the normals of each polygons.
2) the cross product of every edge of each polygons against the edges on the other polygon.

To determine if the objects intersect,
1) for each axis to test against.
- compute interval [mina, maxa] of polygon A along that axis.
- compute interval [minb, maxb] of polygon B along that axis.
- if the intervals [mina, maxa] and [minb, maxb] do not overlap, then the objects are separated by the axis, and cannot intersect.
2) if no separation axis is found, then the objects intersect.

bool polygonsIntersect(Vector* a, int anum, Vector* b, int bnum){    // the normals of the polygons    Vector na = (a[1] - a[0]).crossProduct(a[2] - a[1]);    Vector nb = (b[1] - b[0]).crossProduct(b[2] - b[1]);    // test against normal of polygon a    if(!polygonsIntersectAlongAxis(na, a, anum, b, bnum))        return false;    // test against normal of polygon b    if(!polygonsIntersectAlongAxis(nb, a, anum, b, bnum))        return false;    // test against edge cross products    // a edges    for(int ia = 0, ja = anum-1; ia < anum; ja = ia, ia++)    {        // edge on polygon a        Vector ea = a[ia] - a[ja];        // b edges        for(int ib = 0, jb = bnum-1; ib < bnum; jb = ib, ib++)        {            // edge on polygon b            Vector eb = b[ib] - b[jb];            // axis, cross product of the edges            Vector c = ea.crossProduct(eb);            // edges are parallel, not a valid axis, ignore test.            if(c.dotProduct(c) < 1.0E-8f)                 continue;            // test against axis c           if(!polygonsIntersectAlongAxis(c, a, anum, b, bnum))                return false;        }    }    // no separation axis found, they intersect    return true;}

bool polygonsIntersectAlongAxis(vector n, Vector* a, int anum, Vector* b, int bnum){    float amin, amax; // interval of polygon 'a'.    float bmin, bmax; // interval of polygon 'b'.    calculateMinMax(n, a, anum, amin, amax); // calculate projection interval of 'a' on axis 'n'.    calculateMinMax(n, b, bnum, bmin, bmax); // calculate projection interval of 'b' on axis 'n'.         // check if intervals do not overlap    bool disjoint = (amin > bmax || amax < bmin);    // if the intervals overlap (NOT disjoint), then the polygon projections intersect along axis 'n'.    return (!disjoint);}

however, with polygons, since they have no 'depth' there is a catch. If the polygons are co-planar, then the test needs to be different. You need to test along the vector cross product of each edge of each polygons, and the shared plane normal (basically, very very similar to a 2D test).

This step is unnecessary, if you consider 3 dimesional polytopes (example, boxes, pyramids, convex hulls, ...).

bool polygonsIntersectCoplanar(Vector n, Vector* a, int anum, Vector* b, int bnum){    // test against plane normal    if(!polygonsIntersectAlongAxis(n, a, anum, b, bnum))        return false;    // test against 'a' edges cross products with 'n'    for(int i = 0, j = anum-1; i < anum; j = i, i ++)    {        // edge on polygon a        Vector e = a - a[j];        Vector en = e.crossProduct(n);        // test against axis c        if(!polygonsIntersectAlongAxis(en, a, anum, b, bnum))            return false;        }    }    // test against 'b' edges cross products with 'n'    for(int i = 0, j = bnum-1; i < bnum; j = i, i ++)    {        // edge on polygon b        Vector e = b - b[j];        Vector en = e.crossProduct(n);        // test against axis c        if(!polygonsIntersectAlongAxis(en, a, anum, b, bnum))            return false;        }    }    // no separation axis found, they intersect    return true;}bool polygonsIntersect(Vector* a, int anum, Vector* b, int bnum){    // the normals of the polygons    Vector na = (a[1] - a[0]).crossProduct(a[2] - a[1]);    Vector nb = (b[1] - b[0]).crossProduct(b[2] - b[1]);    // normalise vectors to check if they are coplanar    na.normalise();     nb.normalise();       // check if coplanar. Then run co-planar test instead    if(fabs(na.dotProduct(nb)) > 0.99999f)        return polygonsIntersectCoplanar(na, a, anum, b, bnum);    // else use standard test    // test against normal of polygon a    if(!polygonsIntersectAlongAxis(na, a, anum, b, bnum))        return false;    // test against normal of polygon b    if(!polygonsIntersectAlongAxis(nb, a, anum, b, bnum))        return false;    // test against edge cross products    // a edges    for(int ia = 0, ja = anum-1; ia < anum; ja = ia, ia++)    {        // edge on polygon a        Vector ea = a[ia] - a[ja];        // b edges        for(int ib = 0, jb = bnum-1; ib < bnum; jb = ib, ib++)        {            // edge on polygon b            Vector eb = b[ib] - b[jb];            // axis, cross product of the edges            Vector c = ea.crossProduct(eb);            // edges are parallel, not a valid axis, ignore test.            if(c.dotProduct(c) < 1.0E-8f)                 continue;            // test against axis c           if(!polygonsIntersectAlongAxis(c, a, anum, b, bnum))                return false;        }    }    // no separation axis found, they intersect    return true;}

[Edited by - oliii on December 19, 2008 10:19:57 AM]

the SAT is great for that sort of stuff. You can derive contact informations from it, it's simple vector maths (dot products, cross products, that's it), it's fast (no complex algorithms, can be optimised a lot for standard shapes), it's got no divisions (so pretty solid), no special case and complex branching (except in the case I highlighted), can be extended for swept tests (linear translations, finding teh time of collision) easily, and transposes from 2D to 3D.

It's what is used by physics engines, extended for arbitrary convex shapes in the form of the GJK algorithm. But for polygons and simple polytopes, it's good enough as it is.

Hope the code I provided works, it's untested.