Optimized Blist Form (OBF)

Abstract

Any Boolean expressions may be converted into positive-form, which has only union and intersection operators. Let E be a positive-form expression with n literals. Assume 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). We propose a new Optimized Blist Form (OBF) that requires only s(n)=n steps and b(n)=⌈log2j⌉ bits, where j=⌈log2(2n/3+2)⌉. We provide a simple and linear cost algorithm for converting positive-form expressions to their OBF. We discuss three applications: (1) Direct CSG rendering, where a candidate surfel stored at a pixel is classified against an arbitrarily complex Boolean expression using a footprint of only 6 stencil bits; (2) the new Logic Matrix (LM), which evaluates any positive form logical expression of n literals in a single cycle and uses a matrix of at most n×j wire/line connections; and (3) the new Logic Pipe (LP), which uses n gates that are connected by a pipe of ⌈log2j⌉ lines and when receiving a staggered stream of input vectors produces a value of a logical expression at each cycle.