Jump to content
  • Advertisement

Archived

This topic is now archived and is closed to further replies.

NetArc

OBB Collision Detection

This topic is 5865 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

I need some help on OBB(oriented bounding box) collision detection... I know how to see if a point enters the box, but im very stumped on how to see if another box collides with another one. Each box contains 6 planes and It contains all the wall information in quads. Can Anyone Help me with this subject? -NetArc

Share this post


Link to post
Share on other sites
Advertisement
ummm, i just bought a book, "3D Game Engine Design", by Dr. David H. Eberly, and it''s got a whole chapter devoted to collision detection (and it''s a really big chapter), but i haven''t digested it yet.

i present 2 ways that i can help you:
1) wait for me to need to code collision detection (couple of months) thus giving me reason to read that section, or
2) run, don''t walk, and go buy the book (it''s worth the 60 big ones you gotta drop on it, even if you don''t eat for 2 days at the end of that pay period )

just kidding, but seriously, this book has it all.

have you checked w/ the GD reference?

i''m sure there''s something in there ''bout oriented bounding boxes, and lots more geometry, too




~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~
I have no name that you may call me. I am merely Succinct.
~Succinct Demos Online~

"Hey, where''d that display list rotate off to now?"
-(Drop me a line here)-

Share this post


Link to post
Share on other sites
I''ve had Eberly''s book for a few weeks now, but I''ll try not to spoil the plot for Succinct

It''s better not to represent the box as quads. Instead, represent it using a) its three local coordinate axes and b) its size along each of these axes.

To determine if there is an intersection, you can try to find a line that separates box A from box B. If you can find such a line, they don''t intersect. Otherwise, they do. There are an infinite amount of lines to try this with, but you can get away with only checking the local axes of each box plus the cross products of the axes of box A and box B. All together, that makes 15 axes. To find out if a line separates the boxes, you need to project the boxes on the line.

This is called the ''separating axis'' technique. For more details, there''s a collision detection article on Gamasutra, or you can try www.realtimerendering.com/int.

Good luck!

Share this post


Link to post
Share on other sites
Thx for those links and the other help. A lot of those examples are very complex expecially the .pdf ones. Ive heard of a lot of techniques but the one I see that sticks out mostly for speed and accuracy is the 'seperating axis' one. I pretty much understand the theory of the 'seperating axis' technique, but im lost on how to actually implement it.
Any Help Here?


Also, ive come up with another problem. When I raytrace from a point to another point i sometimes come up with the wrong plane intersection... like the following

$
-------- a
O
-------- b

if i were to trace from O to $, I would sometimes come up with a collision on the plane b instead of plane a. Here is how i do its collision checking... the routine i use:

for (int i=0; i<2; i++)
{
// quad.p is an array of 4 vectors
Vf = RayCollisionPlane(cam.c, Vf, planes.quad.p);
if (IntersectOnPolygon(Vf, planes[i].quad.p))
break;
Vf = Vector(0,0,0); // Reset Our Vector
}

and the functions it calls:

// Find Our Intersection Between Our Ray and the specified Plane.
// doesnt mean our intersection is really on it!!
inline Vector RayCollisionPlane( Vector line_start, Vector line_end, Vector TriVertices[4])
{
// Our Three Points
Vector Vec1=TriVertices[0]; //Vector( 0.0, 1.0, -1.0);
Vector Vec2=TriVertices[1]; //Vector( 1.0,-1.0, -1.0);
Vector Vec3=TriVertices[2]; //Vector(-1.0,-1.0, -1.0);
// Vector Normal On Our Three Points
Vector V1=Vec2-Vec1;
Vector V2=Vec3-Vec1;
Vector VecNorm=CrossProduct(V1, V2);

// Calculate Distance From A Point To a Plane
Vector l1 = line_start - Vec1;
float Distance_to_plane=DotProduct(l1, VecNorm);
// Calculate The Length of Our Line from point1 to point2
Vector l_dir= (line_end - line_start);
float line_length=DotProduct(l_dir, VecNorm);

// what is our line projections percentage of length correctness
float percentage=-Distance_to_plane/line_length;

// Create Our Intersect point
Vector intersect;
intersect.x=line_start.x+l_dir.x*percentage;
intersect.y=line_start.y+l_dir.y*percentage;
intersect.z=line_start.z+l_dir.z*percentage;
// return our intersect point
return intersect;
}

// This takes a intersect result and a polygon and sees if it actually hit the polygon
inline bool IntersectOnPolygon( Vector intersect, Vector TriVertices[4] )
{
// Create our Vector Normal
Vector Vec1 = TriVertices[1] - TriVertices[0];
Vector Vec2 = TriVertices[2] - TriVertices[0];
Vector vecNormal = CrossProduct(Vec1,Vec2);

Vector V1= intersect - TriVertices[0];
float result=DotProduct(V1,vecNormal);
if (result > 0.0)
return false;

// Now see if we hit the triangle and not the plane
Vector Lines[3];
float total_angles = 0.0;
for (int i=0; i<3; i++)
{
Lines[i]=intersect-TriVertices[i];
Lines[i]=Normalize(Lines[i]);
}
for ( i=0; i<2; i++)
{
total_angles+= (float)acos(DotProduct(Lines[i],Lines[i+1]));
}
total_angles+= (float)acos(DotProduct(Lines[2],Lines[0]));

if ( fabsf( float(total_angles-6.28) ) < 0.01 )
return true;
else
return false;
}


Any help on this too would be greatly appreciated

-NetArc

Edited by - NetArc on December 1, 2000 1:51:54 AM

Share this post


Link to post
Share on other sites
I spent hours trying to get OBB to do coll det for a game I am doing, but found that although i got the algorithm working, IT DOSENT ALWAYS WORk. it depends on the exact sizes of your boxes and the angle they are at, or at least it seemed to for me.
I swapped to use a test where i check all 4 corners of my box for being inside the other box, and then do the reverse, and this seems to work much much better ( and is several hundred times less code and quicker too.)
Hope this helps

http://www.positech.co.uk

Share this post


Link to post
Share on other sites
I've trying to figure out if testing all the points on 3D rectangular prisms in question is a good idea or not. I'm having trouble visualizing how the algorithm for checking the points would work, since the points would be rotated...i.e. how do you know which points the check point should be greater than and which ones it should be less than. Is this a workable option for OBB implementation?

[edited by - SpaceThief on May 29, 2002 1:53:39 PM]

Share this post


Link to post
Share on other sites

  • Advertisement

Important Information

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

Participate in the game development conversation and more when you create an account on GameDev.net!

Sign me up!