• Advertisement
Sign in to follow this  

3D collision detection

This topic is 4581 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 was wondering. For 3d collision detection do you check for collision with every primative in the level for each entity? It seems kinda inefficient. Is there I way I don't know about? It's not that it's a big problem, I was just wondering. Thanks!

Share this post


Link to post
Share on other sites
Advertisement
I have no idea what any of those things are [smile]. Basically I'm checking the gravity of the entity, then if it's hitting any of the walls or floors within the stage. Then I move to the next entity.

So far I can handle about 20 entities with 2000 quads.

Share this post


Link to post
Share on other sites
Essentially, it's partitioning [or in english, the different 'stuff' is collected into groups, which are collected into larger groups, which are collected into...] so that you don't have to check everything. The partitioning allows you to only check things in the same [and sometimes bordering] group since the grouping allows you to automatically know that only those things could possibly collide with the object in question.

Share this post


Link to post
Share on other sites
What you're looking for is called broad-phase collision culling - that'll give you a phrase to google for.

The general idea is to divide space up into smaller subspaces, and somehow keep track of which subspace each object is in. It should be clear that an object can only possibly intersect with other objects in its subspace. So lets say you have 100 objects - that's 10,000 tests, brute-force. Now, let's say that your world is divided into 10 subspaces, each of which happens to contain 10 of your objects at the moment. You only need to test objects against other objects in the same subspace, so you now have 10*(10*10) = 1000 tests, a reduction of an order of magnitude. (The actual numbers are a bit different 'cause you only need to test each pair once.)

There are countless ways to implement broad-phase methods (armitage mentioned a couple). Often for small environments it's not necessary; for larger or more complicated environments, which method to employ will depend on the nature of the environment.

Share this post


Link to post
Share on other sites
If you want to cut the number of tests drastically without too much work, here's a simple approach.

Assuming an array of n objects, iterate trough the array testing each object for collision with only the objects located after it in the array. This way you'll reduce the number of tests from n^n to n by avoiding redundant testing. (if object1 doesn't collide with object2, object2 doesn't collide with object1)

Edit: It's (n-1)^(n-1) tests versus (n-1)! tests. I'm tired.

Share this post


Link to post
Share on other sites
Sign in to follow this  

  • Advertisement