Set Operation Evaluation Using Boolean Octree

Set operation evaluation is an important component of Geometric Modeling System (GMS). Input data can be a CSG (Constructive Solid Geometry) representation with solid primitives approximated by polyhedra. This representation is a powerful tool for solid object description. Output data will be the unique resulting polyhedral object which provides an efficient data structure in display field. With no use of spatial coherency, computational complexity of set operation is quadratic. In this paper, we are introducing a new space subdivision scheme called Boolean Octree which performs set operations on polyhedra in an efficient way. This structure aims at limiting set operation evaluation in a ‘minimal space of calculation’ where primitive boundaries intersect each other and where resulting evaluation participates in the construction of the final resulting object. Boolean Octree computes set operations in a local level providing a linear complexity for geometric calculations. During space subdivision, Boolean Octree has a global view on local CSG tree (projection of the CSG tree in local space) taking into account simplifications of the boolean expression, avoiding evaluation and subdivision for the object parts out of the ‘minimal space of calculation’.