# Linear search vs Octree (Frustum cull)

I am wondering whether I should look into implementing an octree of some kind.

I have a very simple game which consists of a 3d plane for the floor. There are multiple objects scattered around on the ground, each one has an aabb in world space.

Currently I just do a loop through the list of all these objects and check if its bounding box intersects with the frustum, it works great but I am wondering if if it would be a good investment in an octree. I only have max 512 of these objects on the map and they all contain bounding boxes. I am not sure if an octree would make it faster since I have so little objects in the scene.

http://publications.dice.se/attachments/CullingTheBattlefield.pdf

Linear brute force frustum culling is...

Simpler:

• Easier to code
• Easier to debug
• Easier to maintain
• Easier to optimize

/**
* Returns wheter the given sphere is in the frustum
* @param center The center of the sphere
* @return Wheter the sphere is in the frustum
*/

public boolean sphereInFrustum(Vector3 center, float radius) {
for (int i = 0; i < 6; i++)
if ((planes[i].normal.x * center.x + planes[i].normal.y * center.y + planes[i].normal.z * center.z) < (radius + planes[i].d))
return false;
return true;
}


Faster:

• Memory is bottleneck

512 is so little amount of objects that you are just wasting your time to even thinking this problem. My java implementation use about 2ms for 1000 objects on cheap android phone. Just testing against bounding sphere is good enough and lot simpler.

• Depends on the objects. If the vert count on the 512 objects puts the GPU right near the limit of what it can handle without dropping below 30-60hz, then some decent culling algorithm might be needed. For example I've got a 4096x4096 terrain divided into 256 objects/chunks (smallest size to fit in a 16-bit index buffer). With simple frustum culling (and no spatial partitioning), the checks against those objects can be more expensive than the 10-15 checks needed when using a quad-tree. But yes, if the objects are fairly cheap to render, advanced culling might not be worth the effort. – Nic Foster Jun 11 '12 at 16:00
• Also, that was a nice link you posted, it's very interesting reading about the low-level optimization companies have had to go through because of the asinine PS3 architecture. Luckily those kinds of hoops probably will not be required on the next-gen consoles. – Nic Foster Jun 11 '12 at 16:13
• I didn't say culling is not needed but that nothing special way to cull is not needed. Just linear bruteforce frustum culling and call it a day. Also memory will be the bottleneck in next generation consoles also so these kind of techniques will be relevant there too. – kalle_h Jun 12 '12 at 14:57
• Interesting comment about the memory bottleneck. It's certainly the largest bottleneck with the current generation, but I'd estimate that the next-gen consoles with have at least 3GB or memory, maybe 4GB, that should be plenty for any console game for awhile I would imagine. But anyhow, back on topic, yea brute force culling might be fine for a small amount of objects. – Nic Foster Jun 12 '12 at 16:08
• It's not the amount of memory but bandwith and latency. Random memory access is slow. This processing vs memory speed gap is only growing. – kalle_h Jun 13 '12 at 11:40

If your game is going to remain a game with just a 3D plane, you could simplify by using a quad-tree instead of an octree. However, an octree will cover all the bases, in case you decide to have things that fly, or decide not to have only a 3D plane for the ground.

An octree will almost certainly make things faster if you have 512 of those objects in existence all at one time (unless they're all very close to each other), especially if you're not batching your drawing of those objects, 512 draw calls is quite a bit for most devices. Since you've not asked, I'll assume you understand how an octree works and won't explain the details. Long story short, you should be able to check the camera frustum against the root of the octree, and then against that node's child nodes, and through recursion keep going until you reach the leaf nodes (nodes with no children of their own).

One thing to keep in mind is the size you want the smallest nodes to be. Too many subdivisions will use more memory and will result in too many frustum<->AABB checks which will end up being slower than the 512 draw calls would. For example I use a quad-tree in my engine, and in a 4096x4096 map I found that 512x512 was the optimal smallest size. This resulted, in my case, in a tree that had a depth of 4. I would recommend tweaking the minimum size until you find the sweet spot for performance.

Octrees aren't the only way of handling spatial partitioning. If your objects are static - which it sounds like they might be - then you may be better off not using an octree but instead using a hierarchy of bounding volumes. And even if they're dynamic, you don't necessarily need a full octree; you can go down to a quadtree, the two-dimensional version, and treat all boxes (for purposes of the spatial partitioning) as having the same height.

As for whether it's worth it, a lot of that depends on just what you're intending to do; 512 objects is few enough that individual frustum culling is probably fine, but you may find yourself wanting the spatial partition for other reasons (for instance, for object interaction).

I would like to emphasize that you should only optimize when you need to. If your game is simple enough perhaps you don't need to cull anything. If the game is small enough having an octree could actually make your game slower. Is speed really an issue for you? Then why? Try running a profiler and see where all the time spent is and really analyze why that might be the case. If culling is than an issue try the simple solution (linear search), then do the octree after that. This should help you get your game out faster as well.

You would be adding the extra steps of checking the octree, moving the objects from octree to octree, handling weird cases like objects being on both sides of an octree.

Lastly, I'd recommend finding an octree implementation with unit tests and such. It isn't super easy to implement (as I remember) and there are a good amount of corner cases.