collsion detection optimzation?
Author
Hi, say u have a complex environment(hill and holes) with like 230,000 faces and a sphere. If u are trying to find the collision detection between the environment and sphere , is there a fast way to find which face it will intersect with rather than going through all 230,000 faces to find which one it will intersect with?
I know you can use "boundary boxes" but that decreases accuracy with non-linear shapes. How do professional games do collision with their environment? do they do a huge loop and check or is there a better way? Thanks for your time.
Look into spatial partitioning. For instance, Octrees in your particular case are a good choice. If your area for the 230,000 faces is small then you can use a 3 dimensional grid and take advantage of 3DDDA for ray casting and such. Depends on the purpose, but normally an octree is enough. Is the area static? Also a per face collision system might be inefficient. Maybe create convex boundary boxes over the models and such to make things less intensive.
most developer use an optimized structure to hold their world data. The Structure makes it easy to figure out collision. which only test the models in the area or line of fire
Quake used BSP.
Quake used BSP.
Quote:Original post by tomba
what do u mean by "create convex boundary boxes"?
use a very low poly model to represent collison model this is seen in half life 2 and other next gen games
How do you initially represent your landscape? Is it a height map or are the faces uniformly placed (say as a grid)? One of the best ways to optomize these situations is to set the data up to be easy to work with.
If you do/did have a heightmap or uniformly spaced grid, then your first step would be to calculate the region the sphere could possibly intersect with. This is basically a 2D problem, finding where on the 2D grid the circular cross section occupies. As long as the grid is not too dense, this could be good enough.
If you do/did have a heightmap or uniformly spaced grid, then your first step would be to calculate the region the sphere could possibly intersect with. This is basically a 2D problem, finding where on the 2D grid the circular cross section occupies. As long as the grid is not too dense, this could be good enough.
Author
well i dont; really have a enviroment with 230,000 faces , i just want to how would u load or work with enviroments so they can be used to collsion detection easily. How would i do grid on enviroments (is it like tiling system in 2D?)?
From what i read these are possible ways:
BSP
Octree
3DDDA
Grid Method
Is that right or are they all pointing to the same thing?
From what i read these are possible ways:
BSP
Octree
3DDDA
Grid Method
Is that right or are they all pointing to the same thing?
If you would like to change to a more grid like system, a heightmap could be a good choice. As long as your terrain has no overhangs or tunnels, it should work well. They are also a very common reprentation of terrain, so googling for it should provide some good resources. Using a heightmap has the benifit of simplifying your sphere/terrain tests to figuring out where on the grid the circle is and then testing against only those faces. Your terrain can then become very large, and not take longer to test with.
Author
well assuimg the enviroment is something like say half life 2 world maps, how would u partion it? like how do i start from reading the world from obj file?
i don't know how to start. i have ideas but they are hard to implement.
do i do this when reading the world from a file:
create a grid by 8x8
for each faces in file
if each vertex in face(j) is in grid[k]
grid[k] points to face(j)
i don't know how to start. i have ideas but they are hard to implement.
do i do this when reading the world from a file:
create a grid by 8x8
for each faces in file
if each vertex in face(j) is in grid[k]
grid[k] points to face(j)
Here are a couple of useful articles, a google search can turn up many others.
Practical Collision Detection (.pdf file)
AABB Trees
Practical Collision Detection (.pdf file)
AABB Trees
This topic is closed to new replies.
Advertisement
Popular Topics
Advertisement
