queue 1: frustum checks, only do these 1-4 times per 60 frames, reset the timer when the camera of player moves and perform the check each time the timer is 0 (zero)

the frustum check is special for a huge scene
1. use some sort of grid, make a profile to find out which gridsize works best
dont try any trees
the grid must be the simplest thing you can possibly add, use a global 3d array to make the grid sphere-like by not testing stuff not TRUE from that 3d array (makes the world rounder)

2. iterate grid using a major-direction scheme, ie. "the player is facing this particular direction the most" such as +x or -x or +z
iterate the grid outwards from player using this scheme, it will make occlusion testing godlike

3. frustum checks blabla

4a. find out what objects are render-able

4b. find out what objects are to be worked on, cap this additional queueing limitation to match a 60 fps schedule
stop adding at a certain number, dont add more than you can work through in 60 frames

queue 2: 4-8 times per frame, each time this queue is worked on clear the render queue, must be performed on a frustum change
work on objects that arent maybe-hidden
add everything renderable to a renderq by sorting them by shader (if you are using texture arrays) or by texture (if you arent), make sure you preserve the major direction scheme as much as possible (important!)

use a variable gluint, call it occlusionrobin, or something
round-robin each texture id, if there are no textures in the frustum with <id>, try next <id> until successful, or you reach the end, then set it to 0
make sure never to reset this number any other way, as it will disrupt occlusion culling

queue 3: the actual rendering
use occlusion queries in a round-robin style (using the variable above)
render as normal sorted by whichever algorithm the previous queue decided
make sure never to bind the same vbo twice, keep tabs
make sure never to bind same shader/texture twice etc.

next frame:
check if the result of a rendered object is available
check result if available and set the object as occluded (or not)
if frustum changed, render all objects regardless

remember frameskipping is king
and despite the player moving the camera, there are at least 10-20 frames between even a continous movement of camera

i hope this helps, if its not too complicated
but the results dont need an explanation

The reason it doesnt work well is because it breaks up your ability ( or makes it EXTREMLY difficult) to do instance calls and state changes as well. Some objects all use similiar textures, shaders, depth states, etc. When rendering using a tree you will end up having to do double work most of the time, while getting very little in return.

Sometimes overdraw is faster than heavy culling so I always found it important to keep the culling system relatively light.

When using a Quadtree I found the following the most efficient:

- Keeping the levels low. Theres no point testing 12 levels of nodes when there's one object sitting at the bottom. You don't need 1m accuracy anyway.

- Using aabbox-node or sphere-node rather than frustrum-node. You can use frustrum-node on the lowest nodes containing objects if you really want to.

-Using an array rather than a linked tree structure. It's more cache friendly, it's easier to directly access nodes, it's easier to find neighbouring nodes for object movement, and it gives less mem fragging. The functions might be a bit less readable and it uses more initial memory but system memory is cheap and plentiful.

- Instead of using the tree-traversal to render the objects, use this as a sorting pass. When finding a visible object, extract its meshes and put them into buckets based on potential state (texture, shader, whatever). Then in the render step everything is already sorted by state and draw calls are minimised.

You can also use that adding-to-bucket stage to order your transparent objects.

(I really like the 3D array idea from [color="#2B3730"]Kaptein, I will have to try this.)

D

If your scene traversal is the bottleneck you running into (most probably) problems due to cache misses as 10 000 object is nothing for an even average scene graph to take care of. I would say go with Hodgman's proposal of laying the octree linearly in memory and making sure your nodes are svelte (contain very few bytes). Then think about SIMD.