Sign in to follow this  

Check *IF* two faces intersect

This topic is 3736 days old which is more than the 365 day threshold we allow for new replies. Please post a new topic.

If you intended to correct an error in the post then please contact us.

Recommended Posts

First, let me apologize if this topic has been covered. Search after search yielded various discussions of how to find WHERE two faces (or ray/face, frustrums, boxes, etc) intersect. I just need to know how to check *IF* two faces intersect. I tried applying some of the info from these other posts to simply return a boolean value, but so far I haven't found any method that seems to work. For responders, can you please tone down the technical speak a bit? I'm a veteran application programmer, but I'm still fresh with 3D programming. My background is mainly in XML/DOM and cracking file formats. I dabble a bit into cryptography, so Math isn't 100% alien to me, but a lot of the 3D terminology still throws me for a loop. TIA- Krypto

Share this post


Link to post
Share on other sites
A face is simply a collection of edges. Two faces intersect if an edge from one face passes through the other face.

This boils down to two types of tests. First you test each edge of one face against the plane on which the other face lies. If an edge intersects this plane, you need to check if the intersection point is within the other face (since the plane is infinite yet the face is finite). If so, you have a collision. Otherwise, you keep checking edges. If none intersect, you do the whole process again, this time switching the two faces so that you're checking the edges of the second face against the plane of the first face. If nothing intersects this time around, then there is no collision.

So what you need to lookup is the edge-plane test (variations are also known as vector-plane, or ray-plane) and the point-in-polygon test (there are variations for both convex and concave polygons). As you can see, determining the intersection point(s) is just a byproduct of the test, and you can ignore it if you want.

Share this post


Link to post
Share on other sites
If it's convex faces (Quads, tris, convex polygons), you can use the SAT as well. Faster than the edge-triangle intersect test, simpler and more robust.


void calculateInterval(const Vector& axis, const Vector* V, const int numV, double& min, double& max)
{
min = max = axis * V[0]; // dot product
for(int i = 1; i < numV; i ++)
{
double d = V[i] * axis;
if (d < min) min = d;
else if (d > max) max = d;
}

}

bool intervalsIntersect(double& mina, double& maxa, double& minb, double& maxb)
{
return (mina <= maxb && minb <= maxa);
}

bool polygonIntervalsIntersect(const Vector& axis, const Vector* A, const int numA, const Vector* B, const int numB)
{
double mina, maxa;
double minb, maxb;
calculateInterval(axis, A, numA, mina, maxa);
calculateInterval(axis, B, numB, minb, maxb);
return intervalsIntersect(mina, maxa, minb, maxb);

}

bool polygonsIntersect2D(const Vector* A, const int numA, const Vector* B, const int numB)
{
for(int j = numA-1, i = 0; i < numA; j = i, i ++)
{
Vector edge = A[i] - A[j];
Vector axis(-edge.y, edge.x);
if (!polygonIntervalsIntersect(axis, A, numA, B, numB)) return false;
}


for(int j = numB-1, i = 0; i < numB; j = i, i ++)
{
Vector edge = B[i] - B[j];
Vector axis(-edge.y, edge.x);
if (!polygonIntervalsIntersect(axis, A, numA, B, numB)) return false;
}
return true;
}

bool polygonsIntersect3D(const Vector* A, const int numA, const Vector* B, const int numB)
{
Vector E = A[1] - A[0];
Vector F = A[2] - A[1];
Vector N = E ^ F; // cross product (normal of A)

if (!polygonIntervalsIntersect(N, A, numA, B, numB)) return false;


Vector G = B[1] - B[0];
Vector H = B[2] - B[1];
Vector M = G ^ H; // cross product (normal of B)

if (!polygonIntervalsIntersect(M, A, numA, B, numB)) return false;


for(int j = numA-1, i = 0; i < numA; j = i, i ++)
{
Vector a = A[i] - A[j]; // edge of A

for(int k = numB-1, l = 0; l < numB; k = l, l ++)
{
Vector b = B[l] - B[k]; // edge of B

Vector axis = a ^ b; // cross product (of the two edges)

const float tolerance = 1.0E-8;

if (axis * axis < tolerance) continue; // degenerate axis

if (!polygonIntervalsIntersect(axis, A, numA, B, numB)) return false;
}
}
return true;
}

Share this post


Link to post
Share on other sites
Thank you both for answering my question. The faces aren't convex, simply triangles. Zipster gave me the info I'll need to find precisely what I'm looking for, but oliii gave me what I'll likely need later.

I'm working at learning 3D programming by writing code. The project I'm working on right now is a simple set of geometry classes with common functions (collision detection, matrix math, etc). Eventually, I'd like to pick up support for faces with more than 3 vertices and spline objects (assuming I'm right in thinking spline geometry and nurbs objects are related?).

Again, thank you both.

Krypto

Share this post


Link to post
Share on other sites
One more quick question...

I'm using OpenGL for my API because I would like to keep my cross-platform options open. As a result, my Vector objects are simply float[3] variables. When you gave the code to check collisions above, you used a double to track the dot product. Would it be better - in terms of memory or speed - to use a double over a float? The scale of my world space isn't fine enough to need the additional precision, but if there's an efficiency boost somewhere I might reconsider my data structures.

TIA (again)

Krypto

Share this post


Link to post
Share on other sites
Quote:
I'm using OpenGL for my API because I would like to keep my cross-platform options open. As a result, my Vector objects are simply float[3] variables.
Just FYI, the fact that you're using OpenGL as your graphics API in no way means that you have to represent vectors and matrices using arrays of floats. Using a proper math library instead will make your life much easier.

Anyway, the use of doubles in the posted example is probably just incidental. If you're using floats for your vectors and matrices, you can just use a float to accumulate the dot product as well.

Share this post


Link to post
Share on other sites

This topic is 3736 days old which is more than the 365 day threshold we allow for new replies. Please post a new topic.

If you intended to correct an error in the post then please contact us.

Create an account or sign in to comment

You need to be a member in order to leave a comment

Create an account

Sign up for a new account in our community. It's easy!

Register a new account

Sign in

Already have an account? Sign in here.

Sign In Now

Sign in to follow this