Many 3D modeling and rendering programs utilize a Binary Space Partition tree (BSP tree) to make rendering go faster. Sometimes these programs will even have customizable settings for the BSP tree. But it’s hard to customize a BSP tree when you don’t know what it is!
Let’s demystify the BSP tree with a simple explanation, and learn what you can do to make the most of these settings when you see them.
BSP Concepts
A BSP tree is a way of grouping data so it can be processed faster. It’s used in many computer science applications, not just VFX rendering.
The grouping process starts with data of some kind, and divides it into two parts. Then the two parts are divided into two parts, and so on until the parts at the end contain the smallest piece of data you want to work with.
As a very simple example, let’s take the word “kangaroo” and partition it with a BSP tree. For this example, a single letter of the alphabet is the smallest possible element.
Reading across the bottom of the BSP tree, you can see the word “kangaroo” split up into its letters.
Let’s look at some terminology that will come in handy as we further explore the BSP tree:
- Tree – A diagram of such a splitting looks like an upside-down tree, which is where the word tree comes from.
- Binary – Each part is always divided into two parts, not three or four or some other number. That is why it’s called a binary space partition tree.
- Node – A chunk along the way as the tree is split.
- Leaf – A node at the end of the tree.
- Branch – Each non-leaf node is split into two branches.
- Root node – The first (topmost) node in the tree is the root node.
BSP Tree Depth
In areas of your renderer that use BSP trees, your software might have a setting for maximum tree depth. The levels of the tree are counted downward from the top, starting with 0. The number of levels is the tree’s depth.
You can figure out the maximum number of leaves by calculating 2 to the power of the depth. In the tree above, 23 = 8, which is the maximum number of leaves for a table with a depth of 3.
BSP Tree in Computer Graphics
That’s all great for simple things like words and letters, but what about the use of the BSP tree in computer graphics? The BSP tree comes in handy when a renderer is trying to make things go faster.
Let’s back up for a minute and take a look at how renderers work.
When a renderer is figuring out how to render a scene, the location of each polygon in 3D space and the direction in which it faces are very important. Just a few of the things the renderer needs to figure out are:
- Is the polygon visible in the view being rendered?
- How much light strikes the polygon, and at what angle?
In a scene with millions of polygons, figuring this out for each and every polygon would take a massive amount of time. To save time in rendering, the renderer splits polygons into groups. These groups become the branches of the BSP tree. Then the algorithm is able to traverse the tree (move over branches and nodes) to find polygons with similar characteristics, and treat them as a group rather than individually.
In the tree below, the entire object (a cube) has been split into its faces.
Note that in this BSP tree, the number of faces doesn’t neatly fit into a power of 2. That’s okay; not all trees are full down to the depth. The nodes at the end of the shorter branches are still considered leaves.
Does a BSP Tree Actually Store Polygons?
A BSP tree stores numerical data, not a graphical format as we’ve shown here. The data itself is stored in a table or database. The BSP tree diagram is just a tool that developers use to visualize the data.
In computer graphics, a face is stored as a series of three or four points (vertices) in 3D space. When you “connect the dots”, you get a face with three vertices. Two coplanar faces, and you get a polygon. The sets of points are what is stored in a BSP data structure.
How Does a BSP Tree Save Rendering Time?
The polygon BSP tree shown above wouldn’t save much rendering time, as the object has been subdivided down to one face per leaf. Where a BSP tree does save time is when not all polygons make it into the tree, or when several polygons are grouped in a single leaf.
One of the most basic ways a BSP tree is used is to figure out which polygons are visible in the rendering. The renderer starts at the back of the scene (as viewed from the rendering view) and loads up the polygons into the BSP tree. Then the renderer steps toward the front of the scene and looks at the polygons there. When another polygon is found that blocks a polygon that’s already in the tree, the blocked polygon is thrown out of the tree and replaced by the polygon in front. At the end of the partitioning process, what’s left in the tree is only polygons that are visible from the rendering view. Then the rendering software can look at this data, and render only what’s left.
A BSP tree also has many other applications: ray tracing, lighting, shadows, and collision detection, just to name a few. The idea is to break up the scene so that only the relevant polygons are in the tree, or the scene can be worked on in chunks rather than on every single face one by one.
Companies that write software work hard to come up with a BSP scheme that will work better and faster, improving the method with each new release. The exact manner in which they do it is considered a trade secret. In other words, we know they do it, but we don’t always know exactly how.
How Can I Use This Information?
The size of the BSP tree can dramatically affect the speed of your rendering. For ray tracing, shadows, or any number of other rendering activities, your software might have settings for the following types of attributes:
Max tree depth – The maximum depth of the BSP tree. Note that increasing this number by 1 doubles the number of leaves. For example, a BSP tree depth of 10 has 1024 leaves (210) , while adding just one more level increases the number of leaves to 2048 (211).
Max leaf size – The term “size” often refers to the number of polygons or faces in the leaf. If a leaf’s size is above this amount, the algorithm will keep dividing the nodes. You can sometimes increase performance by making this number larger, because the algorithm will stop building the tree sooner and there won’t be so many leaves to process. But you might also get less accurate results because polygons that aren’t exactly alike will be treated as the same.
Armed with this information, you can now experiment with different settings and see what works for your scene. And the next time you come across BSP tree settings in your software, you can take control instead of running away.
