Jump to content
  • Advertisement
Sign in to follow this  
RealMarkP

Collision detection with complex objects

This topic is 3656 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

I'm trying to wrap my head around how a person could walk/run around the inside of a house where walls and objects are in the way. I was told that if you make a very simplified version of the interior of the house, using nothing but simple quads, you can just do intersections with triangles. For example, our character has a bounding box around him, and when walking around the house, we would do collision checks between that box and each triangle that is touched. Is this it? Seems like I'm missing something. Does anyone know any further reading I can do about this subject? EDIT: I was also thinking of using a physics engine to detect this OBB - Convex Hull collision.

Share this post


Link to post
Share on other sites
Advertisement
the environment is generally triangles, and the character has a collision proxy (bounding box, spheres, ellipse, cylinder) that roughly contains him. The triangles are generally part of a BVH (bounding volume hierarchy) as you do not want to test against thousands of triangles every frame.

Do use a physics engine if you can, as this stuff is hard to deal with.

Share this post


Link to post
Share on other sites
Am I correct ot assume that I would have to use an Octree (Which is a BVH in its nature, I believe) to cut up the scene into its constituents? Since these are static scenes that we are cutting up, there would be no need to update them, other then traversal with a dynamic bounding volume.

EDIT: Would KD Trees be better for this job?

[Edited by - RealMarkP on June 19, 2008 9:58:18 AM]

Share this post


Link to post
Share on other sites
imo, octrees are best used for point clouds, where the particle has no dimension. Else, you will end up with triangles referenced in multiple leaves, and that's generally bad.

A (loose) kd-tree is much better. The other advantage is that you can easily predict the memory consuption, and fine-tune it.

I've used a binary, compressed axis aligned tree, as described in the Game Programming Gems 2 (or book 3?, very similar to a kd tree). It does the job very nicely.

Share this post


Link to post
Share on other sites
I head KD-Trees were a bit slow when it came to geometry that spanned large distances, such as terrains. Is that true?

I'll definitely start looking at KD-Trees.

Share this post


Link to post
Share on other sites
yes, having large triangles is bad. But it's also true for rendering and the actual collision detection (you then get potential floating point drift and innacuracies).

In short, if you have very large triangles, split them up (that should be straight forward). Also, small triangles can be annoying in CD. Usually, the collision mesh is only an approximation of the graphical mesh. A sort of cleaned up, lower level of detail.

Also, you do not need one giant tree for the whole world. If your world is already segmented (portals, buildings on terrain, ...), then you would have a collection of small trees, one for each area. Terrains can also be a special case. If they are typical heightmaps, then they are already partitioned by their very nature, and you dont need a BVH for them.

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.

Participate in the game development conversation and more when you create an account on GameDev.net!

Sign me up!