Jump to content
  • Advertisement

Archived

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

Polygon-cube (AABB) intersection

This topic is 5126 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 am wondering if anyone can explain (or provide a tutorial) about polygon-cube (axis oriented) intersection. I have found no resources on google, it all seems to refer to books I don''t have. I have figured at first that you could test if any of the vertices of the cube is inside the AABB, however, it quickly becomes apparent that this is not accurate at all, as the middle of the cube can intersect the corner of an AABB, for example, without having any vertices inside.

Looking for a serious game project?
www.xgameproject.com

Share this post


Link to post
Share on other sites
Advertisement
II think what you''re dealing with essentially is a problem of collision detection between two convex polyhedra, somewhat simplified due to the axis-alignment.

This can be handled by brute force by testing each vertex (as you said), and also testing each edge of each object against each face of the other. But this isn''t very efficient.

The way this is usually handled is through a separating plane or separating axis test. Google or find a reference on
"collision detection convex polyhedra separating plane (or axis)". I think it''s discussed in the first volume of the ''Fly3D'' book, among other places.

The actual algorithm is probably too complicated to explain here. Maybe someone else will have an easier answer, but this is the best solution I can think of...

Share this post


Link to post
Share on other sites
Well first, this isn''t collision detection, as velocity is in no way implied... Its intersection testing.

It would be good with a separating plane, because the polygons already have their own bounding planes and surface plane.



Looking for a serious game project?
www.xgameproject.com

Share this post


Link to post
Share on other sites
"Well first, this isn''t collision detection, as velocity is in no way implied... Its intersection testing."

Well, I''m looking at Dave Eberly''s Game Engine Design book, and intersection testing is discussed in the chapter ''Collision Detection.'' So I think I can safely call it a collision detection problem. But yes, to be more specific, it is a static intersection test that you''re talking about

Share this post


Link to post
Share on other sites
This is just my suggestion and the solution depends on how many vertices your polygons contain but.

I would modify the Möller triangle-cube instersection algoritm. I think the first two early-exit ways would be same for a polygon as for a triangle. Maybe it's better to first check the plane that polygon resides in against the cube. Then split the polygon into faces and use the simplified separating axis theorem to check each triangle against the cube. Some of the edges will be the same for two triangles so this can also be simplified.

I think Gems IV or V has a (better?) solution for this...

Möller tri-box



[edited by - __fold on May 9, 2004 5:29:48 AM]

Share this post


Link to post
Share on other sites
i have written a function to check for intersection against a triangle and an axis aligned bounding box , this coul dbe easily extended to a polygon , here is what i did
there are different stages

1 ) check if all of 3 points of the triangle are included
inside the bounding box , if so return 1 ( fully included )

2) if not : check every side connecting the vertices
( spelling ?? )creating a vector starting from
p1, to p2 , check the intersection against a ray
and each plane of the bounding box , note that this
function is optimized to do an early exits
if one side of the triangle intersect one side
of the bounding box, return 2 ( intersection )

3) if all of these test have failed the triangle is surely out of
the bounding box

This function is pretty fast , becaue of the optimizations
for the ray / aligned plane intersection test and early
rejections.

I hope it helped.



Share this post


Link to post
Share on other sites
"1 ) check if all of 3 points of the triangle are included
inside the bounding box , if so return 1 ( fully included )

2) if not : check every side connecting the vertices
( spelling ?? )creating a vector starting from
p1, to p2 , check the intersection against a ray
and each plane of the bounding box , note that this
function is optimized to do an early exits
if one side of the triangle intersect one side
of the bounding box, return 2 ( intersection )"

I''m not sure, but I think you could have a case where neither of these conditions were met, but the triangle did intersect the box. Imagine a very large triangle and a relatively small box, with the box resting in the middle of the triangle. In this case no triangle vertices would be in the box, and no triangle edges would intersect the box faces, but the triangle would intersect the box.

Share this post


Link to post
Share on other sites
jyk you are right , in fact , there is a further step in my function i''ve completely forgot to mention, is is a ray intersection check, using the corner of the box and looking for the intersected point inclusion in the triangle

Share this post


Link to post
Share on other sites
Well I already fixed the problem... And I implemented something similar but a bit modified:

1 ) check if *any* of 3 points of the *polygon* are included
inside the *cube*, if so return true (intersection).

2) if not : test every edge of the polygon against the 6 faces of the cube. If there is an intersection, return true.

3) if not : test every edge of the cube against the polygon, if there is an intersection, return true.

4) If all previous tests failed, there is no intersection, return false.

Its not fast, but its accurate, and its used only when building the octree, so I guess thats allright.



Looking for a serious game project?
www.xgameproject.com

[edited by - Max_Payne on May 9, 2004 6:42:46 PM]

Share this post


Link to post
Share on other sites
"1 ) check if *any* of 3 points of the *polygon* are included
inside the *cube*, if so return true (intersection).

2) if not : test every edge of the polygon against the 6 faces of the cube. If there is an intersection, return true.

3) if not : test every edge of the cube against the polygon, if there is an intersection, return true.

4) If all previous tests failed, there is no intersection, return false."

That should do it. And if this is just for building an octree, you probably don''t need a fancy separating plane algorithm - the brute-force method should work just fine.

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!