Linear search vs Octree (Frustum cull)

Question

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.

Answer 1

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
   * @param radius The radius 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:

• Easier to multithread
• 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.

Code: http://pastebin.com/7i4wknx7

Answer 2

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.

Answer 3

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).

Answer 4

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.