BSP boolean operations
From CGAFaq
There are two major classes of solid modeling methods with BSP trees. For both methods, it is useful to introduce the notion of an in/out test.
An in/out test is a different way of talking about the front/back test we have been using to classify points with respect to planes. The necessity for this shift in thought is evident when considering polytopes instead of just polygons. A point can not be merely in front or back of a polytope, but inside or outside. Somewhat formally, a point is inside of a convex polytope if it is inside of, or in back of, each hyperplane which composes the polytope, otherwise it is outside.
Incremental construction
Incremental construction of a BSP Tree is the process of inserting convex polytopes into the tree one by one. Each polytope has to be processed according to the operation desired.
It is useful to examine the construction process in two dimensions. Consider the following figure:
A B
+-------------+
| |
| |
| E | F
| +-----+-------+
| | | |
| | | |
| | | |
+-------+-----+ |
D | C |
| |
| |
+-------------+
H G
Two polygons, ABCD, and EFGH, are to be inserted into the tree. We wish to find the union of these two polygons. Start by inserting polygon ABCD into the tree, choosing the splitting hyperplanes to be coincident with the edges. The tree looks like this after insertion of ABCD:
AB
-/ \+
/ \
/ *
BC
-/ \+
/ \
/ *
CD
-/ \+
/ \
/ *
DA
-/ \+
/ \
* *
Now, polygon EFGH is inserted into the tree, one edge at a time. The result looks like this:
A B
+-------------+
| |
| |
| E |J F
| +-----+-------+
| | | |
| | | |
| | | |
+-------+-----+ |
D |L :C |
| : |
| : |
+-----+-------+
H K G
AB
-/ \+
/ \
/ *
BC
-/ \+
/ \
/ \
CD \
-/ \+ \
/ \ \
/ \ \
DA \ \
-/ \+ \ \
/ \ \ \
/ * \ \
EJ KH \
-/ \+ -/ \+ \
/ \ / \ \
/ * / * \
LE HL JF
-/ \+ -/ \+ -/ \+
/ \ / \ / \
* * * * FG *
-/ \+
/ \
/ *
GK
-/ \+
/ \
* *
Notice that when we insert EFGH, we split edges EF and HE along the edges of ABCD. this has the effect of dividing these segments into pieces which are inside ABCD, and outside ABCD. Segments EJ and LE will not be part of the boundary of the union. We could have saved our selves some work by not inserting them into the tree at all. For a union operation, you can always throw away segments that land in inside nodes. You must be careful about this though. What I mean is that any segments which land in inside nodes of the pre-existing tree, not the tree as it is being constructed. EJ and LE landed in an inside node of the tree for polygon ABCD, and so can be discarded.
Our tree now looks like this:
A B
+-------------+
| |
| |
| |J F
| +-------+
| | |
| | |
| | |
+-------+-----+ |
D |L :C |
| : |
| : |
+-----+-------+
H K G
AB
-/ \+
/ \
/ *
BC
-/ \+
/ \
/ \
CD \
-/ \+ \
/ \ \
/ \ \
DA \ \
-/ \+ \ \
/ \ \ \
* * \ \
KH \
-/ \+ \
/ \ \
/ * \
HL JF
-/ \+ -/ \+
/ \ / \
* * FG *
-/ \+
/ \
/ *
GK
-/ \+
/ \
* *
Now, we would like some way to eliminate the segments JC and CL, so that we will be left with the boundary segments of the union. Examine the segment BC in the tree. What we would like to do is split BC with the hyperplane JF. Conveniently, we can do this by pushing the BC segment through the node for JF. The resulting segments can be classified with the rest of the JF subtree. Notice that the segment BJ lands in an out node, and that JC lands in an in node. Remembering that we can discard interior nodes, we can eliminate JC. The segment BJ replaces BC in the original tree. This process is repeated for segment CD, yielding the segments CL and LD. CL is discarded as landing in an interior node, and LD replaces CD in the original tree. The result looks like this:
A B
+-------------+
| |
| |
| |J F
| +-------+
| |
| |
| L |
+-------+ |
D | |
| |
| |
+-----+-------+
H K G
AB
-/ \+
/ \
/ *
BJ
-/ \+
/ \
/ \
LD \
-/ \+ \
/ \ \
/ \ \
DA \ \
-/ \+ \ \
/ \ \ \
* * \ \
KH \
-/ \+ \
/ \ \
/ * \
HL JF
-/ \+ -/ \+
/ \ / \
* * FG *
-/ \+
/ \
/ *
GK
-/ \+
/ \
* *
As you can see, the result is the union of the polygons ABCD and EFGH.
To perform other boolean operations, the process is similar. For intersection, you discard segments which land in exterior nodes instead of internal ones. The difference operation is special. It requires that you invert the polytope before insertion. For simple objects, this can be achieved by scaling with a factor of -1. The insertion process is then conducted as an intersection operation, where segments landing in external nodes are discarded.
Initial content for this page from the BSP tree FAQ, included with permission of its maintainer, Bretton Wade.
