Fastest way to do bounds search in an octree

[TimeVector]

I’m currently optimizing my loose octree, and I’m trying to optimize it for the worst case scenario, around 2000 objects stepped at 60hz.

Some important info about the octree:

• Currently I have a dimension of (128, 128, 128) and a depth of 7, though I don’t think I really have enough objects to max out the nodes - playing with depth I only notice a sharp increase in OBB-OBB comparisons around depth 1 or 2.

• Objects are randomly generated around the octree bounds with a min size of 1 and a max size of 5

• Nodes are dynamically allocated whenever a partition occurs. I store nodes in a 1D array, which is compressed from a 3D array.

• The octree has a looseness of 2 baked in.

Updating objects (removal and insertion) takes only ~6ms, so it’s not the issue here. Querying is - with 2000 objects each calling a OBB (Oriented Bounding Box) collision query once per frame, I get around ~400ms frame time.

Doing some stat tracking, per 2000 queries there are:

• ~160k cheap, ~80k expensive OBB-Node comparisons

• ~60k cheap, 154 expensive OBB-OBB comparisons

A cheap comparison is a simple bounding radius check, while an expensive check is a SAT (Separating Axis Theorem) test in 3D.

Clearly, I think the largest performance hit while querying is the 80k expensive OBB-node comparisons. My nodes are AABBs (axis aligned bounding box), so perhaps there’s a cheaper way of figuring out if there is an intersection?

Any help would appreciated, I’ve been searching stack overflow/gamedev forums to no avail for a couple hours now.

[TimeVector]

Ended up switching to a quadtree since height isn’t nearly as important for my game, and also did sloppy intersection checks with nodes by generating an AABB for each OBB.

Got insertion down to 3ms and query to 4ms for 2000 objects.

I think the halving of checks and sloppier/cheaper node checks were the main performance boost. While that meant more nodes were potentially being checked against (and thus more objects), the cheaper overall check and culling options meant that the negatives were minimized. Besides, the main bottleneck were the node checks anyway.