Calculating pairs in an octree

Performance Tuning
#1

I’m extending the code in an octree I wrote for my graphics engine to have the ability to return all pairs of intersecting objects (by axis-aligned box) for use in a physics engine I’m working on. The octree can contain data elements at non-leaf nodes (i.e. so that data overlapping two leaves is stored in those leaves parent, etc.). This means that only one node ever contains a data element at a time.

The obvious way of figuring out all of the pairs seemed to be:


1. Start at the root node
2. Go through every element in the node and intersect with elements in node (doing smart so we don't duplicate intersection tests).
3. Test every element in the node with all of the elements in the node chain back up to the root
4. Go to #2 with every child node of the current node

Hopefully I explained it well enough. The algorithm as described works, and is faster than brute force, and faster than doing an octree query for each object in the scene to see which things it intersects with.

My question is whether or not there better approaches to this when using an octree? (I’m not interesting any of the sweep and prune strategies that exist for collision detection).

#2

Hello, this is great article. I have blog and I thanks to say you thanks. Regards!

#3

a) Nate’s been hacked?

b) For the oct-tree, there are obviously some unnecessary comparisons that are going to be made against elements in the ancestor nodes:

http://img827.imageshack.us/img827/2812/octy.png

Where the left shows elements in a leaf node, the middle shows elements of its parent, and on the right its grandparent. The nodes in red will be compared against, but don’t need to be.

Perhaps you could have each non-leaf node know its height, and to separate its elements up (so into 4 buckets for the height 1 parent, 8 buckets for the height 2 grandparent). There would have to be more house keeping to associate child nodes with their relevant buckets, but it might be worth it.

#4

_BANHAMMER DEPLOYMENT ACTIVATED
_CHARGING…
_!!!EMERGENCY ABORT!!!

As to the octree: I can’t see any better way of getting all intersection pairs in general.

I can see one optimisation, but I’m not convinced it’ll be terribly useful in the context of a physics engine. At any rate: At each node, check for collisions in descending order of object volume. If you find that an object A lies entirely within another object B, then from that point on you can restrict the search for objects that intersect with A to those that have already been found to intersect B, rather than every other object in that node and above.
However, in a physics engine I imagine that one object lying entirely within another is something that you’re trying very hard to avoid. :stuck_out_tongue:

#5

This is more a “food for thought” post. I’ve always used data only in leaf strategy, where leafs contain edge data. Nodes that share an edge are maintained to be within one depth level of one another. So when you are doing neighborhood queries you only walk edges that your bounding volume crosses and each edge will “lead” to either one or two neighbor nodes. One trick here is the question of scale and dealing with objects which exists in multiple nodes. BUT: I’ve only done this in native where a primary goal is memory reduction and I haven’t thought about it in a java context.

#6

lhkbob: your approach will lead to a lot of items in the root node (or in any parent-node)

Imagine a forest: lots of trees uniformly spread in a huge world (say 100*100km). All trees overlapping the center axes of the root node OR the world-edge, will be stored in the root:


___________________
|        |        |
|        |        |
|________|________|
|        |        |
|        |        |
|________|________|

Let’s do some simple math: let’s say the world is filled with (about) 1 tree per 33m. As you walk in a straight line through the forest, you’ll encounter a tree every 3m. There are 6 lines through your world that would resemble the intersection-lines of the root-node, that - if intersected - would cause the item to be put in the root node: 6 100km long lines. A tree every 3m: 6(100.000/3) = 200.000 trees in your root node.

Ofcourse the same applies for any parent node: it will hold a LOT of items that intersect the child-node edges.

Keep in mind that the above example is more like what happens in a quadtree. In an octtree the problem is (obviously) worse, as you have not 6 but 24 intersection-lines that will cause any object to be stores in the parent (of the parent (of the parent (of the …))).

#7

If I store all of my data at the leaves, I’d have to have elements present in multiple leaves at the same time. This makes it a lot harder to keep out duplicates when searching through the tree. Does it turn out that the better distributed tree is worth the extra bookkeeping?

#8

In my (ancient) forest-render, I simply used a HashSet while collecting items from the tree.

Another approach I used, allowing some margin of error, but was blazingly fast, was to only store items in the leafs, solely based on position (ignoring bounding boxes), and make the frustum volume slightly larger to account for the ‘general volume of an item’. Ofcourse you’d have to limit the bounding volume of items, but in my code everything was smaller than 10m, and if larger, I cut it in pieces. Advantage of that is that you can render only parts of big items.

#9

Another issue with everything in the leaf nodes is that updating moving elements, or removing them can be expensive because you don’t know all of the nodes they’re part of without doing a query.

I’m thinking I can use my current octree for dynamic objects and do a leaf-only octree for static shapes. It’s likely that a single moving object will not stay across any axis for that long so the drawback to my structure isn’t too bad (and has fast updates). I could even do something to detect how much something seems to move and automatically choose which tree to place it in.

#10

As said, if you use the second approach, you only have to find 1 leaf. Princec used the slightly ‘bad’ but super-fast way to store the current-leaf in every unit. That way you can instantly find it, which is always faster than whatever clever algorithm you come up with.

#11

Yep, that way works a treat, means the fastest possible removal. I still have the problem of when things fall across quadtree boundaries pushing some objects way way up into a much larger quadrant than they need to be in but I also reasoned that the number of such objects is also very small in reality so it was a tradeoff that I could live with.

I could instead make objects part of each quadtree node that any of their corners live in and maintain 4 pointers to these nodes, which would still allow for extremly fast removal and then I think I could get rid of the need to push entities up into bigger nodes than they needed to be in. But then when doing a query on the tree I’d have to cull the duplicates.

Cas :slight_smile:

#12

Culling duplicates might be the way to go. With a scene of 10000 randomly placed same-size cubes, I get about 8500 in non-leaf nodes and only 1500 in the leaf nodes. Of course that’s not 8500 at the root node, but it seems pretty bad.

#13

“Told you so” :stuck_out_tongue:

As you keep subdividing the tree, the chance that an item intersects an edge, eventually converges to 1.

#14

an edge is fine… it’s just certain edges which are the problem.

Cas :slight_smile:

#15

No, every edge causes the item to be moved to the parent node. if the parent node shared that edge (50% chance) it will be moved to the parent-of-the-parent, if that parent shares that edge (50% of 50% chance) the item will be… etc etc.

This happens in all nodes, and as lhkbob discovered, 85% of all items ended up in non-leafs. As you fill your world uniformly with items, you’ll reach 99% pretty quickly.

#16

This is one of the reasons I like an edge based representation. You almost never need to walk the tree.

If the majority of the dynamic objects are bound within a given bounding size, the you can store these objects in a single leaf. You have the added constraint that the lowest level of the region kd-tree is the bounding volume just large enough to enclose this maximum size. For the purpose of determine the set of nodes to visit you simple add half this bounding dimension. Larger objects can be handled either in an aux data structure or by proxy objects which are stored in multiple leaves.