Building and Using Polyhedral Hierarchies

Abstract:

This animation shows the techniques used to build a hierarchy of
polyhedra as a preprocessing step for intersection detection
algorithms. We show here how the hierarchy is created from a polyhedron
and animate an algorithm for detecting the intersection between a
polyhedron and a plane.
The hierarchical data structure gives a concise representation for
polyhedra that is useful in various searching tasks. Given a
polyhedron, P, we build a hierarchy
P0 = P, P1 , ... ,Pk such
that Pk is a tetrahedron.
Each Pi+1 is the convex hull of a
subset of the vertices of its parent Pi.
Pi+1 is formed by
removing in turn each vertex in
V(Pi+1) - V(Pi). The cone of
faces attached to the vertex is also removed. This leaves a hole in
the polyhedron. This hole is retriangulated in convex fashion. By
removing an independent set of vertices, we assure that the apexes of
removed cones are not connected. As a result we can reattach one or
many cones and retain a convex object. We only remove vertices of
degree less than 12. As a result, the hierarchy has logarithmic
depth. Computing the hierarchy requires linear time and it can be
stored in linear space. The initial segment of the video shows the
creation of a 6 level hierarchy from a convex polyhedron built on 30
vertices. Colors are used to code the levels .
The hierarchy has been constructed as a search tool. We demonstrate
its use in searching during the final segments of the video. We begin
with the task of determining if a polyhedron intersects a plane. This
is done by determining if the polyhedron at each level of the
hierarchy intersects the plane and finding the closest vertex if there
is no intersection. At the initial level, this computation can be
done in constant time by enumeration. The hierarchy was constructed
to simplify growth between levels. In particular, we need only
consider growth affecting two edges adjacent to the closest vertex.
This amounts to a maximum of 4 cones reattached at each level. Since
the cones are formed from vertices of bounded degree, this growth can
be done in constant time, also. As a result, a preprocessed
polyhedron's intersection with a plane can be detected in O(log ~ n)
time. We trace the hierarchical growth by highlighting the closest
vertex and extremal edges. We also display the separating plane.
Watching the cones return to the polyhedron we are able to see the
algorithm determine if a near vertex is closest or new edges are
extremal.
This video was prepared in the computer science department at
Princeton University. Animation software was attached to code for
computing the hierarchy and detecting intersections. The programs
were written in C to run under UNIX on a Silicon Graphics Iris.
Recording was done at the Interactive Computer Graphics Lab at
Princeton and editing was done with the assistance of the Princeton
Department of Media Services.
We thank Copper Giloth for helping with various artistic aspects of
the animation. Kirk Alexander and Mike Mills led us through many
difficult tasks in helping us produce the final video.

This technical report has been published as

Building and Using Polyhedral Hierarchies. David P. Dobkin and
Ayellet Tal, Symposium on Computational
Geometry, 1993 in Video Review, edited by Brown
and Hershberger.