3.3. Boolean Operations

In solid modeling, a very frequent task is to compute the intersection or union of a pair of objects. More generally , given two objects A and B, we want to compute C := A op B , where op ˆˆ { ˆ , ˆ , \ , – } (see Figure 3.5). This can be computed efficiently using the BSP representation of objects [Naylor et al. 90, Naylor 96]. Furthermore, the algorithm is almost the same for all of these operations. Only the elementary step that processes two leaves of the BSPs is different.

Figure 3.5: Using BSPs, we can efficiently compute these Boolean operations on solids.

We will present the algorithm for Boolean operations bottom-up in three steps. The first step is a subprocedure for computing the following simple operation: given a BSP T and a plane H , construct a new BSP whose root is H , such that , (see Figure 3.6). This basically splits a BSP tree by a plane and then puts that plane at the root of the two halves . Since we will not need the new tree explicitly, we will describe only the splitting procedure (which is the bulk of the work anyway).

Figure 3.6: The fundamental step of the construction is this simple operation, which merges a BSP and a plane.

First, we need to define some nomenclature :

Finally, we would like to define a node T by the tuple ( H _T , p _T , T ^ˆ , T ⁺ ), where H is the splitting plane and p is the polygon associated with T (with p H ).

Algorithm 3.1 shows the pseudocode for this first step. It is organized into eight cases, four of which are illustrated in Figure 3.7. This might look a little confusing at first sight, but it is really pretty simple. If T is a leaf, then everything is trivial. The case where T s splitting plane H _T and H are coincident (i. e., same plane and same or opposite direction) is trivial, too. The only case, where it actually needs to do some work is the mixed case, in which H ˆ R ( T ) intersects with H _T ˆ R ( T ).

Figure 3.7: The main building block of the algorithm consists of these four cases (plus analogous ones).

The polygon P is needed only to find the case applying at each recursion. Computing P ˆ R ( T ⁺ ) might seem very expensive. However, it can be computed quite efficiently by computing P ˆ , which basically amounts to finding the two edges that intersect with H _T . See [Chin 92] for more details on how to detect the correct case.

Algorithm 3.1: The first building block of the algorithm for Boolean operations is the procedure that splits a BSP.

  split-tree(   T   ,   H   ,   P   )    (  T   , ^{T   ) {  P  =  H     R  (  T  )}  case   T  is a leaf :  return (   T   ,  T   )   (  T, T  )  case  anti-parallel and on :  return (   T   ,  T   )   (  T  ⁺ ,  T   )  case  pos./pos. :           (  T  ⁺  ,  T  ⁺ )   split-tree(  T  ⁺  , H  )  T     (  H  _T  , p  _T  , T    , T  ⁺ )  T      T  ⁺   case  mixed :           (  T  ⁺ ,  T  ⁺ )   split-tree(  T  ⁺  , H, P     R  (  T  ⁺ ))           (  T   , ^{T   )   split-tree(  T    , H, P     R  (  T   ))  T     (  H  _T  , p  _T    H    , T   ,  T  ⁺ )  T     ^{(  H  _T  , p  _T    H  ⁺  , T    , T  ⁺ )  return (   T   , ^{T   )  end case}}}}

It might seem surprising at first sight that Algorithm 3.1 does almost no workit just traverses the BSP tree, classifies the case found at each recursion, and computes p ˆ H ⁺ and p ˆ H ^ˆ .

The previous algorithm is already the main building block of the overall Boolean operation algorithm. The next step towards that end is an algorithm that performs a so-called merge operation on two BSP trees T ₁ and T ₂ . Let _i denote the set of elementary cells of a BSP, i. e., all regions R ( L _j ) of tree T _i where L _j are all the leaves. Then the merge of T ₁ , T ₂ yields a new BSP tree T ₃ such that , (see Figure 3.8).

Figure 3.8: Computation of Boolean operations is based on a general merge operation.

The merge operation consists of two cases. The first, almost trivial, case occurs when one of the two operands is a leaf: then at least one of the two regions is homogenous, i. e., completely inside or outside. In the other case, both trees are not homogenous over the same region of space: then, we just split one of the two with the splitting plane from the root of the other, and we obtain two pairs of BSPs, which are smaller and still cover the same regions in space. Those two pairs can be merged recursively (see Figure 3.9). This recursive procedure is described more formally by the pseudocode in Algorithm 3.2.

Figure 3.9: A graphical depiction of the merge step in the algorithm for Boolean operations on objects represented by BSP trees.

The third, and last, step is the subprocedure cell -op , which is called at the base of the recursion in Algorithm 3.2. This is the only place where the semantic of the general merge operation is defined, i. e., whether it should perform a union, an intersection, or anything else. When we have reached that point, then we know that one of the two cells is homogeneous, so we can just replace it by the other nodes subtree suitably modified according to the Boolean operation. The following table lists the details of this function ( assuming that T ₁ is the leaf):

Operation	T ₁	Result
ˆ	in	T ₁
ˆ	out	T ₂
ˆ	in	T ₂
ˆ	out	T ₁
\	in
\	out	T ₁
–	in
–	out	T ₂

Furthermore, we would like to point out that the merge algorithm is symmetric: it does not matter whether we partition T ₂ with H ₁ or, the other way around, T ₁ with H ₂ the result will be the same.

Algorithm 3.2: The second building block for Boolean operations merges two BSPs.

   merge(     T   ₁   ,       T   ₂   )         T   ₃  if   T  ₁ or  T  ₂ is a leaf  then  perform the  cell-op  as required by the Boolean operation to be constructed (see                below)  else  (    ,    )   Split-tree(  T  ₂ ,  H  ₁ ,   )      merge (    ,    )      merge (    ,    )  T  ₃   (  H  ₁ ,    ,    )  end if