Public Group

# 3D collision detection

This topic is 4760 days old which is more than the 365 day threshold we allow for new replies. Please post a new topic.

## 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 on other sites
Wouldn't a better approach be to use your spatial datastructure (Octree/BSP) to quickly discard entities then do your collision detection algorithm.

##### Share on other sites
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.

##### 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 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 on other sites
Hmm sounds like extra work. Ah not much of a deal for somewhat of a small project [wink].

Great to know though. Thanks!!!

##### 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.

1. 1
Rutin
33
2. 2
3. 3
4. 4
5. 5

• 11
• 10
• 13
• 96
• 11
• ### Forum Statistics

• Total Topics
632974
• Total Posts
3009641
• ### Who's Online (See full list)

There are no registered users currently online

×