Jump to content
  • Advertisement

Archived

This topic is now archived and is closed to further replies.

Quadtrees and Octrees for Collisions

This topic is 5185 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 have a basic understanding of these two trees. Basically, you cut your level up into smaller and smaller pieces. How would you use it for collision though? Do you have to update all of your entities everytime they move and tell the engine what ''branch'' in the tree they''re now in? Or do you calculate it as you need it? Anyone have some good papers on this kinda stuff?

Share this post


Link to post
Share on other sites
Advertisement
I''ve been trying to find infromation on this subject my self and was unable to find much on Octrees in the way of collision detection. However Ogre (http://www.ogre3d.org/) demonstartes a good implementation of octrees (and other spatial partitioning methods) and shows a method of using them for collision.

Share this post


Link to post
Share on other sites
you can always cache the branch that contains the entity, but it''s unnecessary most of the time. just query the tree with the entity bounding volume as you need it. the query overhead should be tiny.

if you find that the bottleneck in your game is the tree query, you can look into optimising that, using caching. however, you have to keep in mind that you should have to be abe to walk up the tree when the entity leaves it''s branch.

Share this post


Link to post
Share on other sites
Anyone have some good information on bounding boxes with these trees either?

I mean, if you have an object thats too big for a single branch of the tree, what are you left to do? Are you stuck checking the colissions in every branch the entity is in? I guess, no matter what size the entity is, they''d be pretty likely to be in two branches at once. How would you determine this? It couldn''t just be from the point in space where they''re at, it''d have to be done with a bounding volume of some sort right?

Sorry, I just haven''t found much information on the subject and its the next part of the game I''m working on. Hard to make a fun game without collision =)

Share this post


Link to post
Share on other sites
Guest Anonymous Poster
One of the GPG books as an article on direct access quadtrees which allows you to rapidly insert dynamic objects in constant time. Check that out, it''s easily extensible to octrees.

If a bounding volume is too large, store it in the parent.

Share this post


Link to post
Share on other sites
Guest Anonymous Poster
For collsions between objects you can use the method described in the paper "A simple and efficent method for accurate colision detection among deformable polyhedral objects in arbitrary motion" by ATR.

/__fold

Share this post


Link to post
Share on other sites

  • 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!