Implementation:

This implementation is using the Composite/Visitor Pattern (based on OpenSceneGraph). In order to get descent performance on large scene I had to figure out a way to retrive the nodes closer to the player without having to do a entire scene traversal. I found a solution using kdtree, it goes like this:

When loading the scene, add the position of the nodes that are higher in the scene hierarchy in a kdtree index.
When the scene is loaded, build the kdtree index.
Before traversing the scene, perform a nearest neighbor search based on the player position and build a temporary node holding the result.
Perform the culling stage (CullingVisitor for those familiar with OSG) on the result.
Finally render the scene.

I also split the scene into areas, each holding it’s own kdtree. This way it’s possible to do a quick distance check before doing the actual nearest neighbor search on a area.

Result:

When building a scene you can specify the number of area on the x/z axis and a resolution. To test things out, I made a 8×8 scene with a resolution of 4096, each area holds 8000 “parent” node that each holds 4 children node, giving us a total of 4096000 nodes. The scene is running at an average of ~550 FPS when disabling the actual rendering calls. Right now there’s no frustum culling and I’m rendering the cube using deprecated opengl so I’m getting around ~260 FPS with rendering, it should improve later on). This approach is mostly CPU bound and searching with a radius too large can drastically decrease performance so I’m thinking of holding the nodes that can be seen from far away (a terrain per instance) in a different group in order to keep a far view. Also I’m currently using alpha blending as a fog to avoid nodes popping on the screen. Here’s the result: