# Efficiently Computing and Representing Aspect Graphs of Polyhedral Objects

### Ziv Gigus, John F. Canny and Raimund Seidel

###
EECS Department

University of California, Berkeley

Technical Report No. UCB/CSD-88-432

August 1988

### http://www.eecs.berkeley.edu/Pubs/TechRpts/1988/CSD-88-432.pdf

The aspect graph is one of the approaches to representing of 3-D shape for the purposes of object recognition. In this approach, the viewing space of an object is partitioned into regions, such that in each region the topology of the line drawing of the object does not change. The viewing data of an object is the partition of the viewing space together with a representative view in each region. We present an efficient algorithm for computing the viewing data for line drawings of polyhedral objects under orthographic projection. For an object of size
*O*(
*n*) whose partition of size
*O*(
*m*), the algorithm runs
*O*(
*n*^4 log
*n* +
*m* log
*m*) time. Using a novel data structure, we construct the set of all views in optimal
*O*(
*m*) time and space.

BibTeX citation:

@techreport{Gigus:CSD-88-432, Author = {Gigus, Ziv and Canny, John F. and Seidel, Raimund}, Title = {Efficiently Computing and Representing Aspect Graphs of Polyhedral Objects}, Institution = {EECS Department, University of California, Berkeley}, Year = {1988}, Month = {Aug}, URL = {http://www.eecs.berkeley.edu/Pubs/TechRpts/1988/6048.html}, Number = {UCB/CSD-88-432}, Abstract = {The aspect graph is one of the approaches to representing of 3-D shape for the purposes of object recognition. In this approach, the viewing space of an object is partitioned into regions, such that in each region the topology of the line drawing of the object does not change. The viewing data of an object is the partition of the viewing space together with a representative view in each region. We present an efficient algorithm for computing the viewing data for line drawings of polyhedral objects under orthographic projection. For an object of size <i>O</i>(<i>n</i>) whose partition of size <i>O</i>(<i>m</i>), the algorithm runs <i>O</i>(<i>n</i>^4 log <i>n</i> + <i>m</i> log <i>m</i>) time. Using a novel data structure, we construct the set of all views in optimal <i>O</i>(<i>m</i>) time and space.} }

EndNote citation:

%0 Report %A Gigus, Ziv %A Canny, John F. %A Seidel, Raimund %T Efficiently Computing and Representing Aspect Graphs of Polyhedral Objects %I EECS Department, University of California, Berkeley %D 1988 %@ UCB/CSD-88-432 %U http://www.eecs.berkeley.edu/Pubs/TechRpts/1988/6048.html %F Gigus:CSD-88-432