Efficiently Computing and Representing Aspect Graphs of Polyhedral Objects

Ziv Gigus and John F. Canny and Raimund Seidel

EECS Department, University of California, Berkeley

Technical Report No. UCB/CSD-88-432

, 1988

http://www2.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},
    Year= {1988},
    Month= {Aug},
    Url= {http://www2.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://www2.eecs.berkeley.edu/Pubs/TechRpts/1988/6048.html
%F Gigus:CSD-88-432