Georgia Tech inventors have created a simple, linear cost algorithm for converting positive-form expressions to their Optimized Blist Form (OBF). This invention transforms an arbitrary positive-form Boolean expression E of n literals into its OBF. The inventions includes a direct CSG rendering, where a candidate surfel stored at a pixel is classified against an arbitrarily complex Boolean expression using only 6 stencil bits; the new Logic Matric (LM); and the new Logic Pipe (LP), which uses n gates that are connected by a pipe. The process involved a preprocessing phase and a conversion phase that associates three integer labels with each literal in the expression. The OBF then may be used to compute the truth-value of E.
- Eliminates the possibility of causing exponential growth
- Simplified solution
- Computer science
Any Boolean expressions may be converted into positive-form, which has only union and intersection operators. Assuming that the truth-values of the literals are read one at a time. The numbers s(n) of steps (operations) and b(n) of working memory bits (footprint) needed to evaluate E depend on E and on the evaluation technique. A recursive evaluation performs s(n)=n–1 steps but requires b(n)=log(n)+1 bits. Evaluating the disjunctive form of E uses only b(n)=2 bits, but may lead to an exponential growth of s(n).