Hierarchical triangulations: Dobkin/Kirpatrick Hierarchies

Resources:

1. O'Rourke (``Computational Geometry in C''), section 7.5
2. D. Dobkin and D. Kirpatrick, ``Fast detection of polyhedral intersections', Journal of Algorithms, 6, 381-192, 1995.
3. D. Dobkin and D. Kirpatrick, ``Determining the separation of preprocessed polyhedra -- a unified approach'', ICALP-90, LNCS 443, 400-413, Springer Verlag, Berlin, 1990.

Why?

• One problem with all of the other hierarchical space indexing structures that we have looked at is they do not provide ``easy'' nearest nieghbours.
• It is an exact structure, unlike the other ``binning'' methods.  Donkin hierarchies exactly capture the bounds of a group of points, unlike quadtree/octrees/kd trees.

What:

• Start with a group of points of interest, then create a Delaunay triangulation.  We can make this a constrained triangulation, e.g. we have some segments or triangles in the world that we are interested in.
• Now every point is directly connected to all of its nearest neighbours.
• The triangles formed here form what will be the leaves of a hierarchical tree.

Now remove independent sets of nodes, to build the triangulation at the next level up in the tree:

The only problem is that the new regions at this level are not neccessarily valid triangulations, although the previous level was.  We must retriangulate:


Repeat this node removal and triangulation until there is only one large triangle at the top.  Here is one possible next step for this triangulation, hierarchy, which does not require retriangulation after removing the node:

Linking into a hierarchy

	Each parent triangle has multiple children triangles in the previous level of the hierarchy.
	At the same time, each child triangle can have multiple parent triangles -- compare this to quadtrees or kd-trees, where each child has only one parent.

We link the levels through the node that was removed. When we retriangulate the region after removing a node V, connect each new ``parent'' face to that node V whose removal caused the face to be created.

At each level, faces that remain from the last level are simply connected through to the same face in that level.

For each level, every node is also connected to its adjacent faces. Thus, since parent nodes are connected to the vertex V whose removal from the previous level caused the parent to be created, each parent is connected to a (non-disjoint) set of children triangles via V's adjacency links at the previous level.

 

Analysis:

Uses:

• Locating points in 2D.   Start with the coarsest triangulation (the ``last'', or top level of the hierarchy).  A point will fall into only one of the children triangles of this top level triangulation; recurse on that triangle's children until a leaf triangle is encountered.
• Object collision in 3D.  We can represent a convex polyhedron in 3D with the 3D version of this hierarchy. This can be used for detection with a plane, for example, or determining the closest point to the plane, in O(log n) where the polyhedra has n vertices..
• We start with the simplest level of the hierarchy.
• Then, we descend the hierarchy, only considering children regions/nodes in the direction of the plane. In the figure below, the plane we are trying to intersect with is the plane at the top of the cube. At each step of the descent, we complicate the triangulation by adding more nodes, edges, and faces; but, we only add the extra nodes and faces in the direction that we are interested in.