## Binary Space Partitioning Tree Tutorial## Contents## Overview
This tutorial gives a brief introduction to the
BSP tree data structure and its use in
## Introduction
Binary space partitioning (BSP) trees are a geometric data structure used throughout The main function of BSP trees is the recursive partitioning of space. The partitioning is performed by hyperplanes, which can be pictured as generalizations of the idea of planes in Euclidean 3D space. For example, lines in Euclidean 2D space and great circles in spherical 2D space are both hyperplanes. Hyperplanes split the space around them into 3 parts: (1) points that lie on the "plus" side of the hyperplane, (2) points that lie on the "minus" side, and (3) points that lie on the hyperplane itself. Each node in a BSP tree can be associated with a hyperplane that splits the space of the node into two smaller spaces, each of which is assigned to a child node. This splitting hyperplane is called the node's "cut" hyperplane. If a node does not have a cut, it is a leaf node. In the case of BSP trees representing regions, each node is also assigned a location attribute indicating whether or not that node lies inside or outside of the region being represented. The full region then consists of the union of all of the spaces represented by the "inside" leaf nodes.
The best way to get a feel for BSP trees is to see how they are constructed. The next two sections construct the
same 2D region using two separate approaches: direct cutting of tree nodes (bottom-up) and insertion of region
boundaries (top-down). We will use Euclidean 2D space since it is the easiest to visualize, however, the techniques
demonstrated apply to all spaces and dimensions in ## Bottom-Up ConstructionIn this section, we will construct a BSP tree representing a 2D shape that I refer to as a "skewed bow tie". This will give us a good idea of how BSP trees work and how their internal structure is used to represent regions of space.
We will start our BSP tree building adventure by constructing a simple but essential object:
a DoublePrecisionContext. Nearly all code that uses DoublePrecisionContext precision = new EpsilonDoublePrecisionContext(1e-6); Our next step is to create an actual BSP tree instance. We will use the RegionBSPTree2D class since we want to represent a region in Euclidean 2D space. Our tree will start out empty, meaning that it contains only a single node (the root node) with a region location of "outside". RegionBSPTree2D tree = RegionBSPTree2D.empty();
The image below shows a visualization of our tree. The portion on the left shows the region represented by the
tree with the "inside" parts of the region shaded in gray. The portion on the right shows the internal structure
of the tree. As you can see, our tree has only one node, which we've labeled Now, let's add an inside to our region. We will use the Lines factory class to create a 2D hyperplane (a Line) and use it to cut the root node of our tree. Line rootCut = Lines.fromPointAndDirection(Vector2D.ZERO, Vector2D.Unit.PLUS_X, precision); RegionNode2D a = tree.getRoot(); a.cut(rootCut); Our tree now looks like this:
We now have something moderately interesting to look at. Our root node - The cut of
`a`is**infinite**. Even though the image shows a line segment, the cutting line subset extends to infinity in both directions. This is a very important point:**when a node is cut, the cut partitions the node's**Since the root node represents the entire 2D space, which is infinite, the root node cut is also infinite.*entire*space. - The inside of the region lies on the left side of the line when looking in the line direction. This is a convention
and not a geometric property. When a cut is inserted into a tree, the convention is to mark the node on the
minus side of the hyperplane as being inside and the node on the plus side of the hyperplane as being outside.
It just so happens that the left side of a line is considered to be the minus side (see
Line),
so
`b`is marked as inside. This behavior can be changed by explicitly passing a RegionCutRule when cutting the node.
Continuing with tree construction, we can cut the b.insertCut(Lines.fromPoints(Vector2D.of(1, 0), Vector2D.of(-1, 1), precision));
Our inside region is now restricted to only the Adding another line, we finally obtain a finite region. d.insertCut(Lines.fromPointAndDirection(Vector2D.of(-5, 1), Vector2D.Unit.MINUS_Y, precision)); The next two cuts produce similar results on the plus side of the root node. c.insertCut(Lines.fromPoints(Vector2D.of(-1, 0), Vector2D.of(1, -1), precision)); h.insertCut(Lines.fromPointAndDirection(Vector2D.of(5, -1), Vector2D.Unit.PLUS_Y, precision)); We now have a nicely balanced tree representing our non-convex "skewed bow tie" region.
Before moving on to top-down tree construction, let's take another look at the orange lines representing the
region boundaries. Note that the region boundaries always lie directly on the cut hyperplane of an internal
node. However, as mentioned before, they do not necessarily extend the entire length of the cut. In fact,
the root node ## Top-Down ConstructionIn the previous section, we constructed a BSP tree using the bottom-up approach of cutting leaf nodes with hyperplanes. In this section, we will construct the same region using the top-down approach of inserting hyperplane convex subsets into the top of the tree. This is the most typical construction technique. The first question you may ask here is "What is a hyperplane convex subset?" That is a very good question. The name is quite long only because it is intended to be very generic and apply equally well to all spaces and dimensions. Taking the name exactly at face value it means a subset of a hyperplane that is convex, i.e. the shortest path between any two points in the subset also lies in the subset. Since our 2D hyperplanes are Lines, our hyperplane convex subsets include Segments and Rays along with the less frequently used ReverseRays and subsets containing an entire line, created with Line.span(). In order to construct our wonderful "skewed bow tie" this time, we will insert hyperplane convex subsets representing the region boundaries into the top of the tree. These will propagate down through the tree, being split as needed at each internal node, until they hit a leaf node. That leaf node (or nodes) will then be cut as demonstrated in the bottom-up construction section using the hyperplane of the hyperplane convex subset. Let's start by constructing our precision context and empty tree and inserting our first boundary, which will be the line segment [(-5, 0), (-1, 0)]. DoublePrecisionContext precision = new EpsilonDoublePrecisionContext(1e-6); RegionBSPTree2D tree = RegionBSPTree2D.empty(); Segment firstBoundary = Lines.segmentFromPoints(Vector2D.of(-5, 0), Vector2D.of(-1, 0), precision); tree.insert(firstBoundary); This first boundary insertion gives us the following BSP tree:
"Wait a minute!" you may be saying. "I specifically requested that a line segment be inserted into the tree and
now I have an entire line span!" This is true. However, if we go back to one of the important notes from the previous
section, we will be reminded that node cuts always fill the Let's continue inserting boundaries for the left side of the shape and we will begin to feel our sanity returning. tree.insert(Lines.segmentFromPoints(Vector2D.of(1, 0), Vector2D.of(-5, 3), precision)); tree.insert(Lines.segmentFromPoints(Vector2D.of(-5, 3), Vector2D.of(-5, 0), precision)); The tree now looks exactly as it did halfway through our bottom-up construction exercise. Let's insert the remainder of the tree boundaries, this time using a LinePath to simplify construction of the line segments. LinePath path = LinePath.fromVertices(Arrays.asList( Vector2D.of(-1, 0), Vector2D.of(5, -3), Vector2D.of(5, 0), Vector2D.of(1, 0)), precision); tree.insert(path); We have now completed our "skewed bow tie" shape. The represented region and the internal BSP tree structure are identical to that constructed in the previous section but required far less code. Unless a very specific internal tree structure is required, this top-down construction approach will generally be the preferred one. ## Convex Regions and Tree PerformanceAstute observers may notice something interesting in our examples after the first triangle portion of the shape is inserted: the tree is completely unbalanced. All of the internal nodes lie on the minus side of their parent, effectively converting the tree into a linked list. This property is not unique to this example but in fact occurs any time region boundaries are used to construct a BSP tree for a convex region. For example, take the hexagon below. No matter what order the region boundaries are inserted, the resulting tree will always degenerate into a simple linked list. This unbalanced hexagon example will not cause any performance issues because it only contains a small number of nodes. However, if we were to construct a convex polygon with a much larger number of sides (1000, for example) then we will most definitely run into issues. This is due to the fact that most BSP tree operations require some sort of traversal from a node to the root or vice versa. When the tree becomes very tall, performance suffers, with the amount of degradation directly related to the height of the tree. So, how do we improve performance here? The main thing we want to do is decrease the height of the tree while keeping the represented region intact. We can do this by inserting cuts into the tree that do not affect the region but only serve to partition the space so the tree is more balanced. We can call such cuts "structural cuts". We will first insert these cuts directly and then take a look at a helper class designed for just this issue. If you recall earlier, we discussed how the RegionCutRule enum can be used to specify which side of a cut node is marked as inside and which side is marked as outside. The default value for cut operations is MINUS_INSIDE which marks the minus side of the cut as inside. There is also the special value INHERIT, which is specifically designed for our use case here. When cutting nodes with this rule, both the plus and minus sides of the cut are assigned the same region location as the parent node. This means that the cut does not affect the region represented by the tree. In order to construct a more balanced version of our hexagon above, we will start by inserting a cut using this rule that will split our hexagon in two. DoublePrecisionContext precision = new EpsilonDoublePrecisionContext(1e-6); RegionBSPTree2D tree = RegionBSPTree2D.empty(); tree.insert(Lines.fromPointAndDirection(Vector2D.ZERO, Vector2D.Unit.PLUS_X, precision).span(), RegionCutRule.INHERIT); As you can see, we now have a cut in our tree but the represented region is still completely empty. If we insert the hexagon boundaries now, we end up with a more balanced, and therefore more performant, tree than before. One issue with directly inserting structural cuts is that if a region boundary lies directly on a structural cut, the child nodes for that boundary will not be set correctly. Therefore, direct insertion of structural cuts as demonstrated above is only practical when we have knowledge of the boundaries to be inserted and can guarantee that no boundaries lie on a structural cut. In other situations, we can use the PartitionedRegionBuilder2D class. This builder class allows arbitrary structural cuts to be inserted before region boundaries and handles edge cases like the one just described that may affect the region output. The example below uses this builder class to insert a grid of structural cuts centered on the shape centroid before inserting the region boundaries. DoublePrecisionContext precision = new EpsilonDoublePrecisionContext(1e-6); LinePath path = LinePath.fromVertexLoop(Arrays.asList( Vector2D.of(-4, 0), Vector2D.of(-2, -3), Vector2D.of(2, -3), Vector2D.of(4, 0), Vector2D.of(2, 3), Vector2D.of(-2, 3) ), precision); RegionBSPTree2D tree = RegionBSPTree2D.partitionedRegionBuilder() .insertAxisAlignedGrid(path.getBounds(), 1, precision) .insertBoundaries(path) .build(); ## Boolean Operations
A highly useful feature of the region BSP trees in
The example below computes the union of two triangles to form a non-convex region, which we might call a
"standard bow tie". A convenience method is used to directly convert the
LinePath
instances to BSP trees. The result of the operation is written to
DoublePrecisionContext precision = new EpsilonDoublePrecisionContext(1e-6); RegionBSPTree2D a = LinePath.fromVertexLoop(Arrays.asList( Vector2D.of(2, 0), Vector2D.of(-4, 3), Vector2D.of(-4, -3) ), precision).toTree(); RegionBSPTree2D b = LinePath.fromVertexLoop(Arrays.asList( Vector2D.of(-2, 0), Vector2D.of(4, -3), Vector2D.of(4, 3) ), precision).toTree(); RegionBSPTree2D result = RegionBSPTree2D.empty(); result.union(a, b); In the above example, the input trees were left unmodified. If we no longer need one of the input trees in its original form, we can save some memory by writing the result of the operation back into one of the inputs. The next example uses this approach to perform an xor operation. DoublePrecisionContext precision = new EpsilonDoublePrecisionContext(1e-6); RegionBSPTree2D result = LinePath.fromVertexLoop(Arrays.asList( Vector2D.of(2, 0), Vector2D.of(-4, 3), Vector2D.of(-4, -3) ), precision).toTree(); RegionBSPTree2D other = LinePath.fromVertexLoop(Arrays.asList( Vector2D.of(-2, 0), Vector2D.of(4, -3), Vector2D.of(4, 3) ), precision).toTree(); result.xor(other); |