Boolean Operations and Spatial Complexity of Face Octrees.

Abstract

Most of the existing representation schemes of free form surfaces or objects with free form boundary are not capable to compute efficiently boolean operations and other usual geometric interrogations. Classical octrees, proposed to overcome this drawback, require large amounts of memory. Face Octrees was a proposal suitable in the case of smooth surfaces or objects with smooth boundary. In this paper, different aspects of this model are discussed. In fact, it is focussed on the description of boolean operation algorithms using this model, proving that it solves the first problems, and on the computation of spatial complexity bounds. These bounds allow an evaluation of the fitness of each of the existing octree models in a given situation, showing the advantage of Face Octrees when the boundaries are smooth (curvatures are small).