Sign in to follow this  

collsion detection optimzation?

This topic is 3626 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
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
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[i][k]
grid[i][k] points to face(j)

Share this post


Link to post
Share on other sites
The core idea to all these optimizations is that, instead of performing collision checks against every other object, you add some cheap intermediate checks that tell you if you even need to check against a certain number of objects.

If you have 10.000 objects, equally divided over a single room, you could do a simple check: is my object in the left half, or in the right half of the room? If it's in the right half, you don't need to check it against the objects in the left half, do you? That's a single check that reduced the number of actual collision checks by roughly 5.000.

Boundary boxes serve a similar purpose: they're less precise, but that's fine. If the boundary box of your object didn't collide with another object, then you know your object doesn't collide with that object as well, but this check is much cheaper than a per-poly check. If the bounding boxes do collide, then you can always check if your object itself collides with that other object.


However, it also depends on how accurate you need your detection to be. For most AAA games, a few bounding boxes per character are sufficient. And a simplified version of the visual hull is fine, because you don't want to collide with every shrub and pebble.

Share this post


Link to post
Share on other sites
Nice post.

Id like to ask what about rendering. Do people iterate through all world objects etc. or only what will actualy be drawn on screen.

Ive read a article about how they used a graph data structure in Doom I/II to hold the map. It didnt go into that much detail so not to sure. But its a waste of time to render stuff if its not going to be drawn on screen so i guess a simple list is extremly ineffecient.

But how do you know what to draw in for example a FPS. I cant imagin having to figure out what is actualy on screen or off screen, I see what could be done in a very flat 3D world like that of Doom. But what about a mordern FPS. But then again, maybe this simply isnt a issue compared to such things as collision detection speed wise.

Share this post


Link to post
Share on other sites
Similar tricks can be used to determine what needs to be rendered. You can check if visual objects collide with the view cone, for example, and you can disregard anything that's behind the camera (which may actually be above the camera if the camera is looking down, but oh well, you get the idea).

And, similar to collision detection, dividing your world into smaller regions and checking against the bounding box of a region before checking against its content can prevent a lot of unnecessary checks. If a region is behind the camera, it's content is, too, and can safely be disregarded.


For certain environment types, other methods are possible, too. If a level consists of multiple connected area's, you can create a data structure that stores which area is visible from which other areas. This information can then be used to determine which areas need to be rendered, based on the area that the camera is in.

Half-Life levels, for example, use binary space partitioning (bsp) to generate a tree structure that contains all convex areas. A compile tool is used to generate this structure, and another tool is used to determine which area is visible from which other area. This data is then stored inside the map file, so there's no run-time cost. In the mapping communities, compile times of hours, sometimes even days, weren't uncommon though... but I digress. :)

Share this post


Link to post
Share on other sites

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

Create an account or sign in to comment

You need to be a member in order to leave a comment

Create an account

Sign up for a new account in our community. It's easy!

Register a new account

Sign in

Already have an account? Sign in here.

Sign In Now

Sign in to follow this