Topologically exact evaluation of polyhedra defined in CSG with loose primitives

Abstract

Floating point round-off causes erroneous and inconsistent decisions in geometric modelling algorithms. These errors lead to the generation of topologically invalid boundary models for CSG objects and significantly reduce the reliability of CAD applications. Previously known methods that guarantee topological consistency by relying on arbitrary precision rational arithmetic or on symbol-manipulation techniques are too expensive for practical purposes. This paper presents a new solution which takes as input a "fixed precision" regularized Boolean combination of linear half-spaces and produces a polyhedral boundary model that has the exact topology of the corresponding solid. Each half-space is represented by four homogeneous coefficients in fixed precision format (La bits for the three direction cosines and Ld bits for the constant term, i.e. the distance from the origin). Exact answers to all topological and ordering questions are computed using a fixed length, 3 La, + Ld + 2 bits, integer format. This new guaranteed tight limit on the number of bits necessary for performing intermediate calculations is achieved by expressing all of the topological decisions based on geometric computations in terms of the signs of 4 by 4 determinants of the input coefficients. The coordinates of intersection vertices are not required for making the correct topological decisions and hence vertices and lines are represented implicitly in terms of planes.