Hi everyone!

I’m making a 3D renderer and I’m trying to implement an Octree for frustum culling but I’m having a hard time trying to figure out how to update the AABB. Currently, vertex data is directly loaded into a vertex buffer and is not kept in client memory. I can create the AABB before loading the vertex data into the vertex buffer but since the mesh is likely to rotate the AABB I created beforehand will be invalidated at that point.

Some of the solutions I know are:

1. Keep vertex data on client memory and recreate the AABB when the object is rotated.
2. Don‘t keep vertex data on the client and read it back from the Vertex Buffer with glMapBuffer or a similar function.
3. Drop the AABB idea and use OOBB altogether (?)

This seems a memory vs CPU situation all over again but I want to know if there’s an accepted/standard way of dealing with this situation or what would be other alternatives?

1. Ideally compute the AABB from mesh vertices as far in advance as possible. Compute it when you build your assets and store it along with the mesh data. If that is not possible, then compute it once at the start when you have access to the memory on the CPU, e.g. by mapping vertex buffer.
2. Transform the AABB from local to world space every time the transform changes. This can be done efficiently, with some enlargement of the box if there is rotation.
3. Don't use an octree, use a BVH. BVH are better fitting to the objects, can be refit rather than rebuilt every frame, and are better for ray tracing, more suitable to SIMD implementations. The only advantage of octree is that it can be faster to build (morton codes), but it has many other drawbacks (fixed grid is inefficient, bad fit around objects, too many pointers in a node wastes space).
4. Consider whether frustum culling is a bottleneck before spending the effort on a complex tree-based culling solution. You may need to have >10,000 objects or so before the overhead from well-implemented brute force culling exceeds the time it takes to rebuild and query acceleration structures.
5. OOBB are hard because you need code for eigen decomposition of 3x3 matrix, which is not straightforward to implement (iterative solver). More expensive to do visibility checks than AABB. Not recommended for most uses.

I guess I would ask why are things likely to rotate? I also use an octree but it's generally for things that are static in world space. Are meshes really moving independently of each other? Depending on the number of meshes you also have the option of putting them in an array with their bounding objects, and just running through them linearly instead of using a tree. That might be better for moving objects. Also, OOBB might be better, however my go to bounding object is just a sphere. No matter which way you rotate the object, the sphere is still valid and while it may not be the cheapest check, it is a single check. The best solution will probably depend on the details of your typical usage.

Sorry for the super delayed response guys, I wasn‘t notified about your replies for some reason :(.

For the sake of completion. I found the answer on the Real-Time Collision Detection book and basically it says what @aressera said “2. Transform the AABB from local to world space…”. The book comes with an algorithm for updating a box when a rotation is involved (scaling and translation are not a real issue) at the cost of not having a tight box anymore.

@gnollrunner @aresera About your comments on whether or not the octree is a good idea actually make sense. First, I forgot to mention that I’m making a Real-Time 3D Renderer (my bad there). Second, my scene is not that large for the moment, so maybe a brute-force approach might be enough right now. Third, I would like to make a DS that can support Frustum Culling and physics on the future.

@aressera about BVH… I was looking at them actually but I decided to go with Octrees because:

1. For dynamic scenes the insertion method is basically the only option for BVH.
2. On BVH if the object moves we will have to move the hierarchy too (seems odd to do a bunch of updates and based on preliminary research that seems expensive)
3. Octrees are locked to the “world“ (might need a refit if and object is outside of the volume but we can always limit the movement space to the root node limits)
4. Technically, Loose Octrees could have O(1) insertion and deletion, thus making them a better fit for dynamic scenes.
5. Found more information about octrees for dynamic scenes compared to BVH.

I would like to make disclaimer about Octrees tho as I’m getting stuck on that O(1) insertion.

Loose Octrees claim to have O(1) insertion but the algorithm seems to be forgotten XD. I found the specific algorithm on Thatcher Ulrich (Game Programming Gems 1, 2000, p. 444-452). The algorithm goes as follows:

// W is the worlds length, it is expected that the Octree is a cube.

// R is the radius of the bounding volume.

// k = 2 - i.e. loosenesses factor.

S(depth) => W / 2 ^ depth 

// Depth is the depth at which the object can be inserted. It is guaranteed
// that the node doesn’t have a variation + 1 child node, this is, a tightest
// node is either at that depth or one more.
depth = floor(log2(W/R))

// Expects the root Node octree to be centered on the origin (0,0,0)
index = floor((object.center + (W/2))/S(depth))

Now, there seems to be to be a caveat on this algorithm:

If you precompute your octree and you stop at an upper level than the one specified on the depth (i.e. MAXLEVEL < depth) then you seem to loose the advantage of the Loose Octree. In that case either you insert it on the MAX_LEVEL and on the node that’s closets to your object or you do a normal descent-insertion i.e. partition your node, go down to the child that’s closes to your object until you reach the desired Depth, insert. Thus making it a log/O(1) insertion when the depth is not created.