Hi,

I'm implementing a collision-detection system on my 3D game. The idea is to use an octree to partition space so I can save up CPU by not needlessly testing for object collisions. I'm sure those of you who can help me will know all this by now but I'll link some relevant things nonetheless:

Introduction to Octrees (this is the basis tutorial I'm learning from)

Loose Octrees

My problem is this:

I will have a great disparity in size on the objects that I want to test collisions against. It would be something like 100 to 1 or more, meaning that there are objects that are more than 100 times the size of the others. Think of it as having big planets and small asteroids, though their meshes will not be necessarily spherical.

My problem is that when partitioning the space in cubes for the octree, the "planets" will leave considerable space empty in their bounding-box, considering their relative scale to the asteroids'. This means that I could reasonably have dozens of asteroids in the planet's "super-node", in each planet. This is still better than brute-forcing, of course, but I don't reckon I will be able to get a decent enough performance to have several planets being tested with dozens of asteroids each frame.

Am I thinking about this wrong? Should I consider testing whether the asteroids' enclosing node is able to collide with the planet's sphere rather than using the bounding-box? Is using an octree in this sort of situation just a bad idea? Kind of lost as to how to think this, any help would be appreciated.

TL;DR:

Using an octree to collision test objects. Have objects that are very large relative to others, and its nodes will reasonably contain dozens of small objects.

It depends on your octree implementation. If you only allow for leaves to contain objects, your "planets" might cause many "asteroids" being contained in a single leaf. In this case you could create two octrees, one for very large objects and one for smaller objects.

If you allow for all your nodes to contain objects, you can place a large object into the biggest encompassing node and your smaller objects into sub-nodes of that node. This will increase the size of your octree data structure though.

It depends on your octree implementation. If you only allow for leaves to contain objects, your "planets" might cause many "asteroids" being contained in a single leaf. In this case you could create two octrees, one for very large objects and one for smaller objects.

If you allow for all your nodes to contain objects, you can place a large object into the biggest encompassing node and your smaller objects into sub-nodes of that node. This will increase the size of your octree data structure though.

Regarding the second option, it's the one I've considered. But the fact is that the biggest encompassing node for a planet will have a ton of sub-nodes where asteroids could possibly be, and I'd just have to brute-force them all. This doesn't seem like a very good option.

Regarding the first one of having two octrees, I had though about it but can't really grasp how I would cross-reference asteroid-tree with planet-tree so I could detect collisions between them, or how I could cut back on the planets' sub-nodes.

I've made an illustration of my problem below, in 2D for simplicity's sake. The planet's encompassing node leaves too many sub-nodes for small objects to occupy. While the octree helps by not having to test every asteroid against each other, I'll have to test all of them against the planet. Is this ok? Is there a better solution I'm not thinking of? It's quite probable I'll have a lot of objects in that space, near the planet

Green - planet

Blue - asteroids

Red - Bounding Boxes

Grid - Minimum node size

I've made an illustration of my problem below, in 2D for simplicity's sake. The planet's encompassing node leaves too many sub-nodes for small objects to occupy. While the octree helps by not having to test every asteroid against each other, I'll have to test all of them against the planet. Is this ok? Is there a better solution I'm not thinking of? It's quite probable I'll have a lot of objects in that space, near the planet

Assuming all of your asteroids or your planet move then yes, you'll have to check all of the asteroids against the planet, but that's not bad complexity wise since there is only a single planet.

Regarding the first one of having two octrees, I had though about it but can't really grasp how I would cross-reference asteroid-tree with planet-tree so I could detect collisions between them, or how I could cut back on the planets' sub-nodes.

Well once you start your collision detection, you get a list of objects you might collide with from both trees, combine both lists and perform your collision detection on the list of objects. What do you mean with cutting back on the planets' sub-nodes? Your planet wouldn't have any(or barely any) sub-nodes if your planets and asteroids are in different octrees.

When descending down the octree, you can keep a list of all planets in the already visited high level nodes, and when recursing deeper you can discard all planets from this list that do not intersect the octree node your descending into.

I'm not sure what you mean. Do you mean as in testing the planet itself (spherical) against intersection of its subnodes? So instead of detecting for collisions in all the subnodes vs. parentnode, I'd have a preliminary step that crosses the sphere's radius with the distance of the subnode to the parentnode center?

I like this idea, it should help quite I bit I think. The only problem is that I don't know whether all the massive meshes will be spherical. I imagine this procedure gets real tricky with concave shapes. I'll run with it for now though.

Assuming all of your asteroids or your planet move then yes, you'll have to check all of the asteroids against the planet, but that's not bad complexity wise since there is only a single planet.

Well once you start your collision detection, you get a list of objects you might collide with from both trees, combine both lists and perform your collision detection on the list of objects. What do you mean with cutting back on the planets' sub-nodes? Your planet wouldn't have any(or barely any) sub-nodes if your planets and asteroids are in different octrees.

The trouble is that there are several planets, hopefully... That was only an illustration of the problem using just one.

About the dual-tree, I meant that even if I break it up into two octrees, how will it help me not have to run detection on some of the asteroids' nodes that are (albeit in a different tree), in the planet's node space? my problem is exactly in the crossing, not in the asteroid-to-asteroid or planet-to-planet

By the way, thanks very much for the answers guys, just being able to talk about this is helping a lot

The trouble is that there are several planets, hopefully... That was only an illustration of the problem using just one.

Yeah, but I'm assuming you're not going to have a lot of planets crammed up in a single node.

About the dual-tree, I meant that even if I break it up into two octrees, how will it help me not have to run detection on some of the asteroids' nodes that are (albeit in a different tree), in the planet's node space? my problem is exactly in the crossing, not in the asteroid-to-asteroid or planet-to-planet

Having two trees allows for a different data structure, you'll still have to check all your asteroids against the planet. The thing is, that shouldn't be much of a problem. If that is somehow very expensive you could do a simpler check like bounding sphere vs bounding sphere, before you do your full blown collision detection.

By the way, thanks very much for the answers guys, just being able to talk about this is helping a lot

You're welcome :)

My problem is that when partitioning the space in cubes for the octree, the "planets" will leave considerable space empty in their bounding-box, considering their relative scale to the asteroids'. This means that I could reasonably have dozens of asteroids in the planet's "super-node", in each planet. This is still better than brute-forcing, of course, but I don't reckon I will be able to get a decent enough performance to have several planets being tested with dozens of asteroids each frame.

If the octree looks like as shown in your picture, don't worry, I guarantee you will have decent performance. You will at most test each other object in the node of the planet against that planet. Since the planet is huge, there won't fit many other planets inside the same node, and the number of tests in that node in general remains linear. Since the planet is a sphere, testing collision for that against other objects is dead simple, and you should be able to do in the order of 100k such tests per frame on current desktop PCs without seeing a blip anywhere.

If you have lots of planets, then you might end up in a scenario where things don't look at all like shown in your picture. Your picture is an ideal depiction of the scenario where the octree split planes fit the planet bounds perfectly. If you are doing uniform halving splits, that will most likely never be the case, and you can end up having a very tiny part of a sphere straddling over to a neighboring cell that is almost empty from that planet. If this happens for a lot of planets, there might be a way to do better by considering doing a object partition instead of a space partition, but I would not worry about that until you test your performance in practice and prove it to be a problem.

When measuring your octree performance, it is useful to compute the number of objects in it, the number of traversed nodes it has (empty or not) when doing checks, and the number of pairwise object tests you make. As long as you are seeing linear'ish performance as opposed to quadratic, there's not much chance of getting poor performance, unless your code is very inefficient otherwise (or if this is for a triple-A game with object counts nearing multiple millions).

I don't think you'd have a problem if the planet is just approximated as a sphere. If for some reason the planets can be more complex shapes (and you notice a performance problem) then you might need to subdivide the planet a bit further to make some more octree nodes.

Another thing to think about is can your planets move relative to one another? If your space game has all of these objects constantly moving around it may be best to forget the octree and use an insertion based AABB tree. These kinds of topics on gamedev.net are common, and someone always comes along and recommends insertion AABB trees. They aren't complex, very performant, and are designed to work with many moving objects, unlike octrees (which are best for static environments). At least read a couple articles about Dynamic AABB trees, and see if you like the idea.

The only time you'll run into problems with this model is when you need to move the planet. Moving a small object means only testing a small number of objects; moving the very large object means you need to test against all the smaller objects, which based on your description could potentially be a problem. If your planet moves you've got to check everything nearby, and at planet scale that could in theory be an enormous number of objects.

Asteroid moving = few checks.

Planet moving = lots of checks.