Abstract:
|
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 such as Active Zones, Geometric
Bounds and the Extended Convex Differences Tree.
Boxes are the most common geometric bounds studied but other
bounds such as spheres, convex hulls and prisms have also been
proposed.
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 allows 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. |