Tribox bounds for three-dimensional objects

A convex hull H(S) of a 3D set S is rarely used to accelerate interference detection or as a substitute for rendering small projection of S, because it typically has too many faces. An axis aligned bounding box B(S) is cheaper to display and more effective at detecting that two distant objects are clearly disjoint, but is a conservative approximation of S. We propose to use a tribox T(S) as a compromise. T(S) is a tighter bound that B(S) and is cheaper to display and to test for interference than H(S). T(S) is the intersection of three bounding boxes formed in three different coordinate systems, each obtained by rotating the global coordinate system by 45 degrees around one of the principal axes. T(S) has at most 18 polygonal faces. We present an algorithm for computing the boundary of T(S), given its 18 parameters - the endpoints of the intervals containing the projection of the vertices of S onto 9 directions. Given the 18 projection bounds, our algorithm requires only 24 shifts and at most 112 additions. We also describe a simple technique for building a hierarchical multi-resolution representation, which approximates a 3D shape at different level of details by unions of triboxes. (C) 1999 Elsevier Science Ltd. All rights reserved.