BSP-Tree

Basic principles

BSP (Binary Space Partitioning) is a method of space subdivision. It exists for a long time and proved to be very effective in 3D games.

The point is that polygons are stored in a binary tree. Every polygon forms a node of the tree. One subtree of a node contains all polygons, that are behind the node's polygon plane, other subtree contains all polygons that are in front of the node's polygon plane. This structure lets to determine how polygons occlude each other. This is necessary for effective Z-sorting and correct view of intersected 3D models. BSP is also used in collision detection algorithms.

Let's have an overview of BSP-tree building. At first, we have a number of polygons. We choose one of them which divides space on a two subspaces by its plane. It becomes the root tree node. Other polygons form two groups depending on their subspace. Then we choose space dividing polygons in both groups again, and continue this procedure recursively until all the polygons will get into the tree.

Alternativa3D implementation features

Nodes contain several polygons

Every BSP-tree node contains one ore more polygons. If there are coplanar opposite polygons in a same node plane (like thin wall), they're placed in separate storages in the node, that lets to speed up invisible faces cutoff during scene rendering.

Mobility

There is a mobility value for every 3D object on scene. Mobility defines how close to the root will the object be placed. Less mobile objects are closer to the root, more mobile – deeper in the branches. This lets to lower the quantity on nodes being rebuilt during some changes in scene (objects position and configuration). Every object has own and effective mobilities. Own mobility is defined by object's nature (say, by its size, mass etc.) It can be changed by developer anytime. Effective mobility is a sum of object's own mobility and all it's parents' own mobilities in scene hierarchy. Object's place in a tree is defined by effective mobility.

Here is an example: a table (mobility 1) is standing on a ground, and it has an apple (mobility 2) on it. Effective mobility for table is 1, for apple is 3. In BSP-tree table's polygons will be closer to the root, and apple's polygons will be deeper. Let's imagine that apple fall from the table (so it changed it's parent from table to ground). Apple's effective mobility will change to 2, which is still more than table's. After BSP re-sorting apple will be still farther than table from the root. Let's say that table is loaded to a car, which has mobility = 3. Then table's effective mobility will become 4, which is more than apple's 3, so table polygons will move farther from the root, than apple.

Splitter analysis

When building the scene, developer may want to minimize splits (and thus minimize polygons count) or to make BSP-tree more balanced (which is useful for collision detection and invisible nodes cutoff). To manage BSP-tree structure there is a splitter quality analysis mechanism. Adjusting quality parameter, you can vary your tree from "most balanced" to "less polygons". Just remember that it takes more time to make BSP-tree building when this mode is ON.

Fast branch deletion

When removing polygons from BSP-tree, engine looks if their nodes have to be deleted too. If that nodes are not empty, there is no deletion. If some nodes are empty, they are being deleted. If so, engine analyzes if there is fast branches removing ability (say, if deletion touches root node, all the tree will be rebuilt in one attempt). Engine also takes into account an ability to remove node without it's child branches being rebuilt (so called "re-attach").

Polygons store their fragments

Splitted polygon fragments store information about their parent and each other. This lets to partly build polygons from fragments instead their full re-attaching.

Animation

With same objects mobility, animated object goes deeper into the lower nodes during first changes, and further animation doesn't touch static objects with the same mobility.

Tips and tricks

Minimize BSP usage for geometry animation

Even with all the optimizations, mass animation will cause BSP to rebuild constantly. This means fragments assembly, splitter analysis, and branches building. This may take a lot of CPU time (depending on polygon count and tree structure) and cause visible performance problems. We plan to implement simple Z-sorting and local BSP-trees soon.

Set mobility

Using mobility advantages lets to control BSP-tree building.

There are five polygonal objects on scene: gray, red, yellow, green and blue. You can see on pictures, how BSP-tree structure changes depending on objects mobilities.

Use auxiliary geometry

• For more control on BSP-tree it is really helpful to use invisible (with no materials) geometry with low mobility values. Say, having complex object, you can forcibly divide it to parts, so fragments will form in their boundaries.
• If small part of the scene changes often, you can limit this part by invisible geometry. This will divide this part into separate branch. So, animation will not touch other parts of the scene. Say, you can create invisible polygons to separate outer walls architecture from inner furniture geometry fragmentation.