Game Development Stack Exchange is a question and answer site for professional and independent game developers. Join them; it only takes a minute:

Sign up
Here's how it works:
  1. Anybody can ask a question
  2. Anybody can answer
  3. The best answers are voted up and rise to the top

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?


share|improve this question
up vote 9 down vote accepted

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.

share|improve this answer
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? – tunnuz Aug 12 '10 at 15:54
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. – Sean James Aug 12 '10 at 16:02
I found grids work particularly well for dynamic objects. They are simple and fast. – Toad Aug 14 '10 at 13:40

Your Answer


By posting your answer, you agree to the privacy policy and terms of service.

Not the answer you're looking for? Browse other questions tagged or ask your own question.