Jump to content
  • Advertisement
Sign in to follow this  
godmodder

Mom, I'm stuck in the tree ! - Octree for Collision Detection

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

Hello, guys, I'm trying to use my octree structure for collision detection. I couldn't find any useful tutorials/docs on the net, so I figured out some way to do it myself. My camera has a radius (2.0f) and I used to have bruteforce sphere-polygon collision detection. What I did with the octree was the following: - Find the node that the camera is in - Always check that node for collisions - Check if the camera's sphere collides with a bounding box of a node - If it collides with a node, that node is also checked for collision (BTW: I only store geometry in the leaf nodes) I've got this algorithm up and running and it works for most of the time. But sometimes (well, quite frequently), the camera bounces back and forth where it's supposed to just slide and on some occasions you can just fly into walls etc... (although this is a rare case, mostly it does the bounce thing) Do you guys know what the problem could be? Or even better, do you know of any useful docs/tutorials about this matter? Thanx in advance for any help, Jeroen

Share this post


Link to post
Share on other sites
Advertisement
There could be many reasons for your bouncing and inter-pentration.

One thing that comes to mind from your description of the process you use is whether at each iteration of the collision/responce (for sliding/bouncing) you re-calculate the current node/s the camera sphere is now colliding with. If you don't do this, then collsiions can obviously be missed, only to be detected next frame.

Other reasons could be floating point errors or bugs in your collision routines.
You might also want to have a cut off point where if the velocity of the entity drops to some small value during the iteration of collision and responce you stop. You might also want to check if enter a ping-ponmg situation, between iterations, and possibly between preivous movement and the current.

As to your method, i'd recommend the following

Calculate a axis aligned bounding box representing the 'extremes' that the entity can move in this frame. Specifically then you get the 'intended' distance the entity wishes to travel for this frame, add on the radius of the entity, then use this as a raidus to build a AABB centered on the entities position.

You then push this AABB down the tree to collect all the nodes that are intersected. You can either store these nodes, or the polygon indices within them into a 'Potential Collision Set'. This will ensure regardless of your collision responce method that you'll always consider all polygons that could be collided with, by iterating through the PCS

You could refine this somewhat, such as removing any polygons that are within a node, but not within the AABB of the entity. You could also reduce the AABB radius in the 'backwards' direction of the entity if you assume that after a collision they lose speed (travel less distance), but in practice i've found (or rather suspect) that doing so makes it less robust.

The would be a cravet to this, if you have a very fast (travel long distances) entity, where it might be more benifical to take a different apporach such as you outlined, starting at the current node and traversing nodes along the direction of the enitiy is moving.

As to fixing your issues, i'd suggest first returning to a pure brute force method (with a smaller (less surfaces to collide with ) test level. You can then ensure that the collision detection and response is working perfectly before adding the spatial partitioning aspect.

Share this post


Link to post
Share on other sites
I think without seeing how you coded the behaviour of the camera it is quite hard to tell what is going wrong. For example, I don't really know what you mean by 'slide'. If a camera hits a solid object, should it just go as close as it can? What does that mean? However, here are a couple guesses:

First: You didn't code your octree algorithm right :) That might produce the bad behaviour. As a debugging technique, why don't you set the colour you are rendering the objects with as something like red so you can tell what nodes are being triggered. (This is of course if that is a somewhat trival piece of code to add)

Second: Your camera may not bounce off walls because it is possibly moving so fast it goes right through the wall. Try adding a check that in the camera's NEXT step it will not move through an object. That way you won't fly through and miss the collision.

Three: Perhaps your not transition through nodes correctly. Maybe your camera is slipping off one node onto another (because it is moving fast) but the check is being performed on the old node.

Hope this gives some food for thought. I don't mean to insult, just give some ideas as to what's wrong.

J

Share this post


Link to post
Share on other sites
Hello,

I solved the problem: I doubled the radius of my camera for node detection (not for collision with the geometry) and now everything is just like with the bruteforce approach, except for the performance ofcourse: FPS went up from 170 to 400+
I turned out my algorithm was fine, but since the radius first was the same as the radius for the actual collision, things were a bit unstable.

Thanx,
Jeroen

Share this post


Link to post
Share on other sites
I'm about to implement what you've just done, and have a question for you:

When you get which box you're collision-testing, do you gather ALL octree-boxes that are within the camera-radius? Or do you still test only the box that camera is in?

EDIT:

I just realized you answered my question before I posted it. ;)
Thank you!

Share this post


Link to post
Share on other sites
It just so happens I wrote an article on this a few years ago (well, quite a few years ago). I reformatted it and put it on my site here . Check the article downloads section for the code.

Let me know if it's helpful at all (but don't bother asking questions, I don't remember a damn thing about it :-).

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!