I'm still implementing my scene graph (see this question). Now, I wonder if a spatial representation such as a Kd-Tree or Octree to do View Frustum Culling (VFC) only makes sense with static geometry. The reason for my doubt is that usually dynamic geometry is a small part of the scene, while static geometry can be very large, and dynamic geometry forces to handle updates in the spatial representation at each frame.

Your opinions?



1 Answer 1


Generally I've used a separate partition tree for static and dynamic objects, or just disregarded it altogether for dynamic objects. This provides the benefits of both worlds:

  • Static objects require no recalculation of the tree each frame
  • Dynamic objects only require the recalculation of a minimal tree

If drawing your dynamic objects all the time doesn't provide too much of a performance hit, it can sometimes be better to just dispense with recalculating a tree for them every frame.

Another optimization is to only recalculate the tree when objects have moved a certain distance or are traveling at sufficiently high speeds, otherwise you'll probably end up with the same tree every frame anyway.

  • \$\begingroup\$ Great answer, I expected something like this. Do you usually use different data structures for dynamic and static geometry? Is there any ad-hoc procedure to make the two structures "meet" when doing collision detection between static and dynamic objects? \$\endgroup\$
    – tunnuz
    Commented Aug 12, 2010 at 15:54
  • 2
    \$\begingroup\$ Using the same data structure is usually easiest because the implementation is already written, and therefore there is also less of an opportunity for bugs to crop up. Sometimes however bounding sphere checks is enough for dynamic objects compared to the overhead of building an entire tree, especially if the objects are moving a lot. Along those lines, it may be beneficial to write a less aggressive partitioning system for dynamic objects to keep calculation times down and use a more aggressive but calculation intensive algorithm for static objects. \$\endgroup\$
    – Sean James
    Commented Aug 12, 2010 at 16:02
  • 2
    \$\begingroup\$ I found grids work particularly well for dynamic objects. They are simple and fast. \$\endgroup\$
    – Toad
    Commented Aug 14, 2010 at 13:40

You must log in to answer this question.

Not the answer you're looking for? Browse other questions tagged .