Jump to content
  • Advertisement
Sign in to follow this  
tomba

collsion detection optimzation?

This topic is 3966 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, 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.

Share this post


Link to post
Share on other sites
Advertisement
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.

Share this post


Link to post
Share on other sites
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.

Share this post


Link to post
Share on other sites
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

Share this post


Link to post
Share on other sites
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.

Share this post


Link to post
Share on other sites
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?

Share this post


Link to post
Share on other sites
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.

Share this post


Link to post
Share on other sites
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)

Share this post


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

  • Advertisement
×

Important Information

By using GameDev.net, you agree to our community Guidelines, Terms of Use, and Privacy Policy.

We are the game development community.

Whether you are an indie, hobbyist, AAA developer, or just trying to learn, GameDev.net is the place for you to learn, share, and connect with the games industry. Learn more About Us or sign up!

Sign me up!