BSP dynamic scenes
From CGAFaq
So far the discussion of BSP tree structures has been limited to handling objects that don't move. However, because the hidden surface removal algorithm is so simple and efficient, it would be nice if it could be used with dynamic scenes too. Faster animation is the goal for many applications, most especially games.
The BSP tree hidden surface removal algorithm can easily be extended to allow for dynamic objects. For each frame, start with a BSP tree containing all the static objects in the scene, and reinsert the dynamic objects. While this is straightforward to implement, it can involve substantial computation.
If a dynamic object is separated from each static object by a plane, the dynamic object can be represented as a single point regardless of its complexity. This can dramatically reduce the computation per frame because only one node per dynamic object is inserted into the BSP tree. Compare that to one node for every polygon in the object, and the reason for the savings is obvious. During tree traversal, each point is expanded into the original object.
Implementation notes
Inserting a point into the BSP tree is very cheap, because there is only one front/back test at each node. Points are never split, which explains the requirement of separation by a plane. The dynamic object will always be drawn completely in front of the static objects behind it.
A dynamic object inserted into the tree as a point can become a child of either a static or dynamic node. If the parent is a static node, perform a front/back test and insert the new node appropriately. If it is a dynamic node, a different front/back test is necessary, because a point doesn't partition three dimesnional space. The correct front/back test is to simply compare distances to the eye. Once computed, this distance can be cached at the node until the frame is drawn.
An alternative when inserting a dynamic node is to construct a plane whose normal is the vector from the point to the eye. This plane is used in front/back tests just like the partition plane in a static node. The plane should be computed lazily and it is not necessary to normalize the vector.
Cleanup at the end of each frame is easy. A static node can never be a child of a dynamic node, since all dynamic nodes are inserted after the static tree is completed. This implies that all subtrees of dynamic nodes can be removed at the same time as the dynamic parent node.
Caveats
Recent discussion on comp.graphics.algorithms has demonstrated some weaknesses with this approach. In particular, an object modelled as a point may not be rendered in the correct order if the actual object spans a partitioning plane.
