Jump to content
  • Advertisement
Sign in to follow this  
krypto

Check *IF* two faces intersect

This topic is 3987 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
Advertisement
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 * 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 - 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 - 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 - 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
Quote:
Original post by oliii
Triangles are convex polygons :)


Ah, well, see! You learn something new every day. Thanks again.

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
Sign in to follow this  

  • Advertisement
×

Important Information

By using GameDev.net, you agree to our community Guidelines, Terms of Use, and Privacy Policy.

We are the game development community.

Whether you are an indie, hobbyist, AAA developer, or just trying to learn, GameDev.net is the place for you to learn, share, and connect with the games industry. Learn more About Us or sign up!

Sign me up!