A generic algorithm for constructing hierarchical representations of geometric objects Page: 1 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
A Generic Algorithm for Constructing Hierarchical
Representations of Geometric Objects*
Patrick G. Xavier
Sandia National Laboratories, Albuquerque NM 87185-0951
OCT 1 1 1995
For a number of years, robotics researchers have
exploited hierarchical representations of geometri-
cal objects and scenes in motion-planning, collision-
avoidance, and simulation. However, few general
techniques exist for automatically constructing them.
We present a generic, bottom-up algorithm that uses
a heuristic clustering technique to produced balanced,
coherent hierarchies. Its worst-case running time
is O(N2logN), but for non-pathological cases it is
O(NlogN), where N is the number of input primitives.
We have completed a preliminary C++ implemen-
tation for input collections of 3D convex polygons and
3D convex polyhedra and conducted simple experiments
with scenes of up to 12,000 polygons, which take only
a few minutes to process. We present examples using
spheres and convex hulls as hierarchy primitives.
For a number of years, the robotics community has uti-
lized hierarchical geometric representations to avoid all
pairs comparisons in distance computations and col-
lision detection, with motion planning being the main
application. (For example, see [FT87, Qui94].) The
automatic generation of hierarchical geometric repre-
sentations, however, is still a research area, especially if
one wants to control properties such as spatial balance,
structural balance, coherence, and tightness.
*This research was supported by DOE Contract DE-ACO4-
94AL85000, and by the Laboratory Directed Research and Devel-
opment Office of Sandia National Laboratories.
DISTRIBUTION C)- THIS DOCUMENT IS UNM M
We present a practical generic algorithm for gener-
ating hierarchical representations. Our algorithm is
generic in that it can be applied to collections of any con-
vex primitive, e.g., a scene of composed of convex poly-
gons or polyhedra. The core of the algorithm is a greedy
bottom-up clustering technique that constructs a tree of
sets. Tuning parameters allow control of the balance
of desirable properties. A hierarchy of convex solids
is then constructed by walking the tree. Our algorithm
is practical in that is runs in time roughly O(N log N);
our preliminary C++ implementation takes less than five
minutes to construct hierarchical groupings from inputs
of over 10,000 polygons. Building a hierarchy of solids
takes seconds to minutes, depending on the solids and
the desired tightness of the geometrical approximation.
Geometric query algorithms (e.g., distance) frequently
take tree-structured representations as input. A typical
representation is a tree whose nodes each contain a ge-
ometric primitive, such as a sphere, convex polygon, or
convex polyhedron. The subtree rooted at a node repre-
sents the union of the primitives at its leaves. We require
that each node of a hierarchical geometric representa-
tion contain a conservative approximation, or wrapper,
of the object represented by its subtree.
A typical branch-and-bound algorithm to answer a
query about the geometric object represented by such a
tree does a partial traversal, making a local query about
the wrapper or primitive at each node it visits. Thus, a
optimal tree would minimize
where cl(a) is the cost of answering the local query to
'~ ,2~., ~
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/1/: accessed July 23, 2018), University of North Texas Libraries, Digital Library, digital.library.unt.edu; crediting UNT Libraries Government Documents Department.