# 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 hierarchyP0 = P, P1 , ... ,Pksuch

thatPkis a tetrahedron.

EachPi+1is the convex hull of a

subset of the vertices of its parentPi.Pi+1is formed by

removing in turn each vertex inV(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 inO(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, edited by Brown

Geometry, 1993 in Video Review

and Hershberger.