Streaming Large World Using KdTree


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:

  1. When loading the scene, add the position of the nodes that are higher in the scene hierarchy in a kdtree index.
  2. When the scene is loaded, build the kdtree index.
  3. Before traversing the scene, perform a nearest neighbor search based on the player position and build a temporary node holding the result.
  4. Perform the culling stage (CullingVisitor for those familiar with OSG) on the result.
  5. 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.


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:


One thought on “Streaming Large World Using KdTree

  1. Pingback: Modern Planet Rendering : Editor, Physics and Clouds | hiredk's blog

Leave a Reply

Fill in your details below or click an icon to log in: Logo

You are commenting using your account. Log Out /  Change )

Google+ photo

You are commenting using your Google+ account. Log Out /  Change )

Twitter picture

You are commenting using your Twitter account. Log Out /  Change )

Facebook photo

You are commenting using your Facebook account. Log Out /  Change )


Connecting to %s