Jump to content
  • Advertisement

Archived

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

tolwak

how do u start ur initial OBB collision test between all world objects?

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

hi all... i want to know how do u game developers start ur OBB tests between all world objects before starting more accurate tests incase two objects OBB are collided?... there is one way i know where u use two counter loops (a loop and another inner loop) to check for collision between object ''a'' specified by the outer loop and object ''b'' which is specified in the inner loop, if two OBB are collided then start another accurate collision test in a new thread to let the loop continue. this looks too expensive to me coz there could be more than 5000 objects in the world (5000*5000=number of tests). can u give me a link for an article about this or tell me another better way to do this?. thanx in advance

Share this post


Link to post
Share on other sites
Advertisement
One way I thought of (and I''m no expert) but would be to check all the collisions on a certain axis. If the coordinates on that axis match, you do further checks to see if the other dimensions mark a collision as well.

Share this post


Link to post
Share on other sites
Peon has described the beginnings of a very cool algorithm called Recursive Dimensional Clustering. It was first published in games programming gems 2, but should hopefully be more more publicly available now (written by Steve Rabin i think). It runs in O(nlogn)[base2], which is pretty darn nice, and "clusters" all the objects. Basically this means that if A is colliding with B and C is colliding with B, then it will put those 3 into a cluster group. Now obviously this isn''t perfect, since in actuality C isn''t colliding with A, so this is where your more specific collision tests come into play (ray plane intersection and all that). You can basically treat it to mean that each object in a cluster "might" be in collision with each other object in that cluster group. It''s a really sweet algorithm, and very easy to implement.

Share this post


Link to post
Share on other sites
I'd like to note that you don't have to do 25,000,000 tests for 5,000 objects. You would do:

for(int i=0; i<NumObjects; i++)
{
for(int b=i+1; b<NumObjects; b++)
{
ObjectArray[i]->CheckCollision(ObjectArray[b]);
}
}


Unless you've badly designed your collision detection such that it does movement as well, or doesn't check to see if the specified object is colliding with it rather than just it colliding with specified object, you don't need to check the same pairs. Object 1 checks itself against all other objects, so why should all other objects check against object 1 again?
Also objects don't need to check against themselves, because their collision box always would show a collision. Therefore, b is current object + 1, going to the next object. I don't know what the number of calculations run is, but it's not 25 million.

Edit: 12,497,500 with the given method. Basically cut the number of calculations in half. Just wanted to point this out, but you'll probably want to find a better method.

[edited by - Erzengeldeslichtes on September 23, 2003 1:31:40 PM]

Share this post


Link to post
Share on other sites
Use a quad/octtree to manage the geometry in the scene. Then identify in which node is the object you want to check and test collision with all the objects in that node.
-First do a preliminar and cheap sphere-sphere test.
-If there is intersection then you can do sphere-AABB, sphere-OBB, AABB-AABB or whatever more accurate test that you want

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.

GameDev.net is your game development community. Create an account for your GameDev Portfolio and participate in the largest developer community in the games industry.

Sign me up!