Speaker: Jarek Rossignac, Professeur Georgia techs

Title :  Efficient evaluation of large Boolean expressions

Abstract :

Although explicit (triangle meshes) representations of 3D shapes are popular, there are significant benefits of using implicit CSG (Constructive Solid Geometry) models: guaranteed validity, compactness, ease of parameterization and animation. Highly complex CSG models may be rendered quickly on the GPU using per-pixel SIMD parallelization, where fragments are classified against all n solid primitives in parallel and the classification results are combined according to a given Boolean expression. Using a stack to evaluate that expression may require log2(n) bits of storage per pixel. Hence, 6 stencil bits per pixel will only suffice to guarantee that all Boolean expressions of up to 64 literals can be evaluated. The Boolean expression can be converted in linear time into an equivalent Ordered Boolean List (OBL), which can be evaluated using only 5 bits of memory for all Boolean expressions with AND, OR, and NOT operators and less than 6.4 billion literals. We will also discuss two potential applications of OBL to digital circuit design: (1) The OLM (Ordered Logic Matrix) uses a matrix of 32 lines and 3n columns, and evaluates a Boolean expression in one clock cycle and (2) the Ordered Logic Pipe (OLP) contains a row of n OLM modules connected by a 5-line address pipe and produces one value per cycle, assuming that the input vectors are staggered.