1.7.1 Previous Work in Manipulation of Boolean Equations

Lee and Jea [1988] discuss a method for manipulating the structure of a CSG tree by moving branches up and down the tree structure. They limit the operators to union and subtraction, and assume the operators are regularized. They argue that for feature recognition using CSG, it is necessary to move nodes up the CSG tree to be compared. Although they do not pose a feature recognition algorithm, they do suggest that various nodes may be moved up the CSG to partially overcome the global, and uniqueness problems of the CSG representation. Their algorithm is based on transformation tables for CSG branch forms. These tables are pictured in Figure 1.4 Transformation Tables for Moving Node A up CSG Trees. The reader should note that 16 basic input states have been given by Lee and Jea, and there are a number of possible output states associated by form. In the tables given, each of the 16 states are listed in each of the four tables. There are four tables to indicate the four possible states for parents of the subtree containing A, B, and C. The work is of particular interest to this thesis because of the use of equation forms to manipulate tree structures. Their work also supports the idea of manipulating the CSG structure to achieve various interpretations of a part.

 

Figure 1.4 Transformation Tables for Moving Node A up CSG Trees

(Read the tables as a form in the left hand column is equivalent to that in the right hand column)

When attempting to eliminate redundant primitives in a CSG tree, a Null Object Detection (NOD) algorithm may be used. (Please note that the assumption with this technique is that unused and redundant primitives are undesirable). The algorithm attempts to locate primitives that cancel each other out. Tilove [1984] describes his use of Boolean algebra properties to design algorithms to detect null objects. This is done through a set of five algorithms he presents, which look for positive, and negative redundancy by direct examination of the tree. Tilove also describes previous algorithms that were not based on CSG methods and required greater access to computational resources. As an aside, he also states that the NOD algorithm can be used as the basis for Same Object Detection (SOD). This is useful when trying to ascertain if two objects are indeed similar.

1.7.2 Boolean Algebra Manipulation of Data Structures

As discussed before, we may store and manipulate the Boolean expressions. The data structures discussed in the previous section did not discuss the addition of Boolean algebra whereas this section will. A set of routines were written to apply the rules of Boolean algebra to manipulate the equations. The fundamental operations are given in Figure 1.5 Fundamental Boolean Operations. All but Identity and Duality have been implemented in the software.

 

Figure 1.5 Fundamental Boolean Operations

These operations are set up so that they may be applied in a parametric manner (see Mendelson [1989], for more information on Boolean algebra). In other words, there may be a term ‘(+ A B C)’. The law of Commutivity says that the expression may have up to six (3! = 3*2*1) forms; ‘(+ A B C)’, ‘(+ A C B)’, ‘(+ C B A)’, ‘(+ B A C)’, ‘(+ B C A)’, and ‘(+ C A B)’. Therefore the law of Commutivity can be applied to some term, a finite number of ways. By expressing the manipulation in this manner, the method of manipulating equations becomes similar to methods used in tree searches (i.e., the operator is a simple finite description). This becomes the first step to deriving an exhaustive method for equation manipulation. The list below shows all of the operations used, and gives examples of how they are applied.

• Idempotent

• Simplify - A + A = A, A & A = A

• Example equation ( & A B A C A A;e )

• In this expression there are n=6 terms, and therefore there are (n-1)(n-2)...(1) possible combinations for application. Of this there are only 3 that can be successfully performed in the example equation. This is between the first three ‘A’s. The last ‘A’ is considered different because it has a ‘;e’ appended.

• Possible results,

( & A B C A A;e )

( & A B A C A;e )

( & B A C A A;e )

• Complicate - A = A + A, A = A & A

• Example equation ( + A B C )

• In this expression there are n=3 possible terms to apply the members to.

• Possible results,

( + A A B C )

( + A B B C )

( + A B C C )

• Associative

• Simplify - A + ( B + C) = A + B + C, A & ( B & C) = A & B & C

• Example equation ( & A B ( + C D ) ( & E;x F );y )

• There are n=4 possible candidates for this operation of which two are bracketed, and one of those two has the same sign. The ‘( & E F )’ term can be ‘popped’ because it has the same operation as the parent term.

• Possible result,

( & A B ( + C D ) E;x;y F;y )

• Complicate - A + B + C = A + ( B + C ), A & B & C = A & ( B & C )

• Example equation ( & A;x B ( ~ C ) )

• For this operation it was chosen to allow each possible commutation (see commutative operator). This gives a total n!(n!) possible permutations that are acceptable for this operation.

• Possible results,

( & ( & A;x B ) ( ~ C ) )

( & ( & B A;x ) ( ~ C ) )

( & ( ~ C ) ( & A;x B ) )

( & ( ~ C ) ( & B A;x ) )

( & ( & A;x ( ~ C ) ) B )

( & ( & ( ~ C ) A;x ) B )

( & B ( & A;x ( ~ C ) ) )

( & B ( & ( ~ C ) A;x ) )

( & ( & B ( ~ C ) ) A;x )

( & ( & ( ~ C ) B ) A;x )

( & A;x ( & B ( ~ C ) ) )

( & A;x ( & ( ~ C ) B ) )

• Commutative

• Does not simplify or complicate - A + B = B + A, A & B = B & A

• Example equation ( + A ( & B C ) D )

• There are n! possible acceptable permutations for this operation. In simple words this operation only shuffles the order of the terms in the equation.

• Possible results,

( + A ( & B C ) D )

( + A D ( & B C ) )

( + D A ( & B C ) )

( + D ( & B C )A )

( + ( & B C ) A D )

( + ( & B C ) D A )

• Distributive

• Simplify - ( & A ( + B C ) ) = ( + ( & A B ) ( & A C ) ),

( + A ( & B C ) ) = ( + ( & A B ) ( + A C ) )

• Example equation ( + A ( + B;e C );f ( + D E ) ( & F G ) )

• There is only one possible permutation with this operation.

• Possible result,

( & ( + A F ( + B;e C );f ( + D E ) ) ( + A G ( + B;e C );f ( + D E )))

• Complicate - ( + ( & A B ) ( & A C ) ) = ( & A ( + B C ) ),

( & ( + A B ) ( + A C ) ) = ( + A ( & B C ) )

• Example equation ( & A B ( + C D ) ( + D E ) ( & F G ) )

• Again, this operation will only have one possible permutation for the purpose of simplicity.

• Possible result,

( & A B ( + D ( & C E ) ) ( & F G ) )

• Complement

• Simplify - ( ~ ( ~ A ) ) = A

• Example equation ( ~ ( ~ ( & A B );x );y ); z

• Again there is only one possible permutation possible here. If a double negative exists, then it is replaced with the doubly negated term

• Possible results,

( & A B );x;y;z

• Complicate - A = ( ~ ( ~ A ) )

• Example equation ( + A B C;x D )

• In this example there are n=4 possible permutations allowable.

• Possible results,

( + ( ~ ( ~ A ) ) B C;x D )

( + A ( ~ ( ~ B ) ) C;x D )

( + A B ( ~ ( ~ C;x ) ) D )

( + A B C;x ( ~ ( ~ D ) ) )

• DeMorgan’s

• Simplify - ( ~ ( & A B ) ) = ( + ( ~ A ) ( ~ B ) ),

( ~ ( + A B ) ) = ( & ( ~ A ) ( ~ B ) )

• Example equation ( + A B ( ~ ( ~ ( & C;x D );y );z ) )

• There are n=3 possible permutations possible, but only one of these three has the double negative required for this operation to be successful.

• Possible result,

( + A B ( & C;x D );y;z )

• Complicate - ( + ( ~ A ) ( ~ B ) ) = ( ~ ( & A B ) ),

( & ( ~ A ) ( ~ B ) ) = ( ~ ( + A B ) )

• Example equation ( + A B ( ~ C ) ( ~ D;x );y )

• There is only one possible permutation.

• Possible result,

( ~ ( & ( ~ A ) ( ~ B ) C D;x;y )

Obviously these methods can be used to simplify, or complicate an expression. In the next section the application of these operators will be addressed.

1.7.3 Automatically Generating Boolean Equations

The operators described in the last section were described using permutation parameters. To manipulate the equation the user must specify the i) operation of interest, ii) simplification or complication, and iii) the permutation of the operation desired. As these are specified, the equation may be changed. If they are applied blindly using an exhaustive search, the possible variations are enormous (actually infinite). A directed searches is one possible method for reducing the search space.

Exhaustive methods are the most dependable methods for finding any given term. But this reliability comes with a high cost on efficiency. In the case of simplifying the equation to a disjunctive normal form, the method is slow, but very effective. To reduce an equation to its simplest form, we need only to apply the operators discussed in the previous section, until all possible alternatives have been exhausted. It was found that to start with the most nested terms resulted in a more direct solution. The basic algorithm is described below.

1. Get a list of all terms in the equation, in hierarchical order. That is the last item on the list of terms, would be one of the first operations performed mathematically.

2. Pick the last term on the list, and begin testing to see if any simplifying operators can be applied. If no operators are fired, then remove the last item from the list, and begin step 2 again. If the list is empty, the equation is simplified, so quit.

3. If an operator was fired successfully, then return to 1.

For the software written, this Exhaustive Simplify operation takes a few seconds for an example with between 10 and 20 terms. If the code were optimized, the simplification would take less than a second.

Exhaustive Simplification has a goal, therefore making the algorithm easy. Exhaustive complication has no goals, but it continually expands an infinite tree systematically. More importantly, when simplifying, there is only one term at all times. But, when complicating, each new term must now be kept. This is obviously not very practical, but useful to note.

The exhaustive equation manipulations focus on complicating, and simplifying expressions. But, if we merely want to generate alternatives, we may use a more interesting algorithm. A Random Walk through equation space may be of use for obtaining novel equation forms. In this case a term in the equation is chosen at random, and one operator is randomly selected, and the operators permutation is also randomly selected. This would allow the equation to be made simpler in some cases, more complex in others, and change the topology of the equation. While this is sort of a blind technique, it does lay the groundwork for a more complex heuristic search.

At present the simplification technique is the only one used, but the future potential for this method is excellent. The advanced use of equation manipulation will be discussed more later with reference to Meta-knowledge.