Orthogonal polyhedra as geometric bounds in constructive solid geometry
A. Aguilera, Dolors Ayala · 1997
Set membership classification and, specifically, the evaluation of a CSG tree, are problems of a certain complexity.Several techniques to speed up these processes have been proposed.This include Active Zones, Geometric Bounds and the Extended Convex Differences Tree.Boxes are the most commonly studied geometric bounds, although other bounds such as spheres, convex hulls and prisms have also been proposed.On the other hand, there is an extended bibliography dealing with convex polyhedra and solving problems for this class of polyhedra.Orthogonal polyhedra are also a class of polyhedra and several problems have been solved for them.In this work we propose orthogonal polyhedra as geometric bounds in the CSG model.CSG primitives are approximated by orthogonal polyhedra, and the orthogonal bound of the object is obtained by applying the corresponding boolean algebra.A specific model for orthogonal polyhedra is presented that facilitates a simple and robust boolean operations algorithm between orthogonal polyhedra.This algorithm has linear complexity (is based on a merging process) and avoids floating-point computation.