##
A Scheme for Single Instance Representation in
Hierarchical Assembly Graphs

The Hierarchical Assembly Graph (HAG) is a common
representation method for geometric models. The HAG is a directed
acyclic graph. Nodes in the graph represent
objects, and arcs denote the sub-part relation between objects.
Affine transformations and other instantiation parameters
are attached to the arcs.
An * instance * of an object in a HAG is defined as a
* path * ending at its node.
Information common to all instances whose paths end at a given
node can be attached to this node.
Data associated with a * single * instance cannot be attached to any
single node or arc in the graph. Such private data
can be stored in an external list, hash table, or a partial expansion of
the graph into a tree, but all of these schemes have severe drawbacks in
terms of storage, access efficiency, or update efficiency.

In this paper we present
a scheme for representing single instances in the assembly graph
itself, by identifying an instance with the last node in its path when
the only way of reaching the last node is through a unique path
starting at the first node of the path.
We give an algorithm for * singling *
an instance in the graph, i.e. transforming the graph into an equivalent
one in which the instance can be identified with a node.
We also show how to undo an instance's singling when its private data is
no longer needed.

Falcidieno, B., Kunii T.L. (eds),
* Geometric Modeling in Computer Graphics, * pp. 213-224, Springer, 1993
(IFIP Conference on Geometric Modeling in Computer Graphics,
Genova, Italy, June 1993.) (An updated version is available.)