Intersection of 3D objects
Author
First of all, my apologies if this question has been answered, been googling and also searched this site for something that could help me, but I couldn't find the right info.
Secondly, I am not actually programming a game, but similar principles are being used in my program.
Ok, over to the problem: I need to test the intersection between two 3-dimensional objects, initially two rectangular cubes, but if possible also with other shapes (only convex). My 3D rectangular cubes are defined by 8 (x,y,z) points.
At first I tried the algorithm Cygon posted here: http://www.gamedev.net/community/forums/topic.asp?topic_id=423383, but there appears to be a problem with this: the check creates it's "own" bounding box, ignoring rotation of my objects. This is perhaps better illustrated with some screen shots:
http://dl.getdropbox.com/u/386051/imghost/forums/project/Intersect_1.png
The first image is just used to illustrate my model, no collisions.
http://dl.getdropbox.com/u/386051/imghost/forums/project/Intersect_2.png
In this second image you will see a correct alert (shapes turn red), since two of my shapes are intersecting.
http://dl.getdropbox.com/u/386051/imghost/forums/project/Intersect_3.png
In this third case the problem becomes apparent when I get a false positive from both the links on the yellow finger alerting of a collision with the lower link on the blue finger.
This happens because the algorithm I used fetches the absolute max/min values along each global axis, and as such works as it's own non-rotated, bounding box.
Do you know of another algorithm I could use for this that would fix my problem?
Thank you for taking the time to read my post, and thank you in advance for your replies!
Hi,
Your post is fine. It is pretty much identical to an aspect of collision detection in games and doesn't appear to be blatantly academic, so I consider it on topic. (It appears you read the forum Forum FAQ or forum rules before posting, and I appreciate that!)
So, collision detection/intersection testing is typically done in at least two phases: broad phase and narrow phase. (Some implementations have a mid phase as well.) The broad phase is intended primarily to discard object pairs that cannot possibly intersect or collide. Broad phase tests are extremely cheap tests, which in many cases can be done in parallel on multiple cores or processors. These super cheap/fast tests can eliminate the need to do a more expensive test on all the possible pairs. They make collision detection fast. The narrow phase is intended to find out, from the remaining pairs that might collide or interest, which ones actually do. The axis-aligned bounding box test, which ignores object orientation, is primarily a broad phase test. All it has told you, really, in your third case, is that the objects might intersect.
So, you are in need of a narrow phase test. For rectangular cubes/rectanguloid specifically, a good and reasonable test would be to use oriented bounding boxes (OBB's). There is an article at Gamasutra, linked below, that has some code for this:
An Oriented Bounding Box (OBB) Intersection Test
Another page that lists other references for OBB vs. OBB intersection tests (and intersections between many other pairs of shape types) is:
Object/Object Intersection Page
You may note that the first link mentions a separating axis test (SAT). This test can be used for more complex shapes as well. There is a really good basic tutorial on the problems of game physics, including an overview of many of the challenges of collision detection (especially when objects are moving), at essentialmath.com. I've linked to that in the sticky thread at the top of this forum on physics engines and resources, and for convenience here:
List of physics engines and reference material
Your post is fine. It is pretty much identical to an aspect of collision detection in games and doesn't appear to be blatantly academic, so I consider it on topic. (It appears you read the forum Forum FAQ or forum rules before posting, and I appreciate that!)
So, collision detection/intersection testing is typically done in at least two phases: broad phase and narrow phase. (Some implementations have a mid phase as well.) The broad phase is intended primarily to discard object pairs that cannot possibly intersect or collide. Broad phase tests are extremely cheap tests, which in many cases can be done in parallel on multiple cores or processors. These super cheap/fast tests can eliminate the need to do a more expensive test on all the possible pairs. They make collision detection fast. The narrow phase is intended to find out, from the remaining pairs that might collide or interest, which ones actually do. The axis-aligned bounding box test, which ignores object orientation, is primarily a broad phase test. All it has told you, really, in your third case, is that the objects might intersect.
So, you are in need of a narrow phase test. For rectangular cubes/rectanguloid specifically, a good and reasonable test would be to use oriented bounding boxes (OBB's). There is an article at Gamasutra, linked below, that has some code for this:
An Oriented Bounding Box (OBB) Intersection Test
Another page that lists other references for OBB vs. OBB intersection tests (and intersections between many other pairs of shape types) is:
Object/Object Intersection Page
You may note that the first link mentions a separating axis test (SAT). This test can be used for more complex shapes as well. There is a really good basic tutorial on the problems of game physics, including an overview of many of the challenges of collision detection (especially when objects are moving), at essentialmath.com. I've linked to that in the sticky thread at the top of this forum on physics engines and resources, and for convenience here:
List of physics engines and reference material
Author
Thank you for a very helpful post!
The way I have solved this problem is using a similar approach to what you suggested; I first use the (cheap) axis-aligned bounding box test to see if there is potentially a collision.
Since not all my objects are boxes, but other shapes (triangular rectangles, for example), I found the oriented-bounding box test a little complicated. What I have done instead, is create a class I call Plane, which has 4 3D-points designating its corners. When a bounding box detects a potential collision, then all the planes (i.e. the surfaces) of the object are created, and a double for-loop testing all surfaces on object A for an intersection of all surfaces on object B. So for two box-shaped objects, this would mean 36 tests, which I still think is relatively cheap.
Such is my pseudo-code:
Again, thank you very much for your help!
The way I have solved this problem is using a similar approach to what you suggested; I first use the (cheap) axis-aligned bounding box test to see if there is potentially a collision.
Since not all my objects are boxes, but other shapes (triangular rectangles, for example), I found the oriented-bounding box test a little complicated. What I have done instead, is create a class I call Plane, which has 4 3D-points designating its corners. When a bounding box detects a potential collision, then all the planes (i.e. the surfaces) of the object are created, and a double for-loop testing all surfaces on object A for an intersection of all surfaces on object B. So for two box-shaped objects, this would mean 36 tests, which I still think is relatively cheap.
Such is my pseudo-code:
if(ob1.intersect(ob2)){ return ob1.planeIntersect(ob2);}//////////// in object class//////bool planeIntersect(Object3d ob2){ this.createPlanes(); ob2.createPlanes(); for(int i=0;i<this.planes.count();i++){ for(int j=0;j<ob2.planes.count();i++){ if(this.planes.intersects(ob2.planes[j])){ return true; } } } return false;}Again, thank you very much for your help!
I'd recommend taking another look at the SAT. I can almost assure you that for oriented boxes, the SAT will be much more efficient than the algorithm you're using currently. I would guess it would probably be more efficient for other simple convex shapes as well (by which I mean shapes with a relatively small number of faces).
How is your 'plane intersection' test implemented? One thing to keep in mind is that 'per-feature' tests like the one you appear to be using can miss cases where one object is fully contained within another. It can also be harder to extract meaningful contact information when using per-feature tests.
Finally, I probably would use a name other than 'plane' for your 'quad' class (in mathematics and geometry a plane has infinite extent, so calling the faces of your objects 'planes' is a bit inaccurate, I think).
How is your 'plane intersection' test implemented? One thing to keep in mind is that 'per-feature' tests like the one you appear to be using can miss cases where one object is fully contained within another. It can also be harder to extract meaningful contact information when using per-feature tests.
Finally, I probably would use a name other than 'plane' for your 'quad' class (in mathematics and geometry a plane has infinite extent, so calling the faces of your objects 'planes' is a bit inaccurate, I think).
This topic is closed to new replies.
Advertisement
Popular Topics
Advertisement
