A generic algorithm for constructing hierarchical representations of geometric objects Page: 3 of 9
This article is part of the collection entitled: Office of Scientific & Technical Information Technical Reports and was provided to Digital Library by the UNT Libraries Government Documents Department.
The following text was automatically extracted from the image on this page using optical character recognition software:
Submitted to 1996 IEEE Int'l Conf on Robotics and Automation
ing volumes. Their algorithm is similar to a "top-down"
version of ours, but it has less control over the structural
and spatial balance and depends on randomization for
protection against "badly ordered data". One motiva-
tion for the presented work was to ensure desirable tree
To speed collision detection, Quinlan [Qui94] con-
structs hierarchies of spheres using a divide-and-
conquer method off-line. Earlier work by DelPobil,
et al [dPSL92] constructs a representation with a given
number of spheres, but restricts the input. Hubbard
[Hub94] directly optimizes the tightness of the approx-
imate representation at each level and includes bounds
on the distance between each sphere and the object. His
use of a medial-axis computation slows the method con-
siderably, but it appears useful for off-line processing.
Related spatial-subdivision algorithms fall into two
categories: those based on binary space partitioning
(BSP) trees [FKN80] and those based on octrees. BSP
trees and variants such as Vanecek's B-Rep Index have
been used effectively in clash detection and modeling
[NAT90, Nay92, Van91]. However, these structures
have not yet been shown to be efficient for distance
computation or the creation of general progressive-
refinement hierarchies. Octrees for representing 3D ge-
ometric objects have been in the literature for at least a
decade and a half; see [Man88] for a review. Extended
octrees (see [BN90], for example) are more economi-
cal and permit exact representations. Octrees have also
been used to create initial structures in generating other
hierarchies [Hub93]. Non-uniform hierarchical space
subdivisions based on balancing the number of primi-
tives on each side of a cutting plane have also been used
to create hierarchies, as reported by Zachmann and Fel-
ger [ZF95]. Although this type of partitioning is very
fast, our previous experiments with a similar algorithm
showed that the hierarchical representations were more
prone to grouping artifacts than what we present here.
2 Building Hierarchies Via A Clus-
2.1 Basic Idea: A Hierarchical Clustering
We now describe the Grouping Phase of our algorithm.
Recall that the general idea is to use a heuristic clus-
tering technique to build a Subset Tree whose leaves
contain the input primitives. Because of the need to
handle inputs of size 103 to size 105, we must rule out
any algorithm with an expected runtime of O(N2) or
more. While we can't minimize cost (1) because of un-
known distributions, we still want to have some control
over spatial balance, structural balance, and coherence.
Intuitively, this points to some sort of bottom-up con-
Specifically, we had the following basic idea:
" Maintain a collection of nodes without parents.
" Until this collection contains just one node (the
root of the Subset Tree), do the following: consider
the convex hulls of the contents of pairs of nodes,
and make a parent for the pair whose convex-hull
diameter is minimal.
We call making two nodes the children of a new node
merging them. This also entails conceptually combining
the sets that corresponding to the node and creating a
new p-set wrapper for the resulting set.
One problem with this approach is it appears to be
at least O(N2log N) because of the number of node
pairs that need to be considered. In addition, it lacks
control over coherence; it ignores the heuristic that it
is qualitatively better to merge two nodes if they are
spatially contiguous or close than if they are slightly
smaller but not contiguous.
Our solution to both problems is based on the obser-
vation that the diameter of new parent grows monotoni-
cally. Let us assume that the primitives are not long and
skinny (or flat) and not closely packed like uncooked
spaghetti. Then, suppose we set a diameter limit, and
only consider pairs of nodes with p-set wrappers that
have smaller diameters and centers that are closer than
this diameter; when the queue is empty, we simply dou-
ble the diameter limit. If the limit is set appropriately,
this greatly cuts the number of nodes any given node
could merge with. In fact, if we bound the aspect ra-
tios of the primitives, then each node can merge with at
most a constant number of others. This cuts the length
of the queue of pairs of parent-less nodes to O(N).
Furthermore, by spatially hashing the parent-less nodes,
we make constant the time it takes to determine which
nodes another node can merge with.
Here’s what’s next.
This article can be searched. Note: Results may vary based on the legibility of text within the document.
Tools / Downloads
Get a copy of this page or view the extracted text.
Citing and Sharing
Basic information for referencing this web page. We also provide extended guidance on usage rights, references, copying or embedding.
Reference the current page of this Article.
Xavier, P.G. A generic algorithm for constructing hierarchical representations of geometric objects, article, October 1, 1995; Albuquerque, New Mexico. (digital.library.unt.edu/ark:/67531/metadc664081/m1/3/: accessed April 26, 2018), University of North Texas Libraries, Digital Library, digital.library.unt.edu; crediting UNT Libraries Government Documents Department.