3D collision detection
Author
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!
Wouldn't a better approach be to use your spatial datastructure (Octree/BSP) to quickly discard entities then do your collision detection algorithm.
Author
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.
So far I can handle about 20 entities with 2000 quads.
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.
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.
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.
Author
Hmm sounds like extra work. Ah not much of a deal for somewhat of a small project [wink].
Great to know though. Thanks!!!
Great to know though. Thanks!!!
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.
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.
This topic is closed to new replies.
Advertisement
Popular Topics
Advertisement