EFFICIENTLY COMPUTING AND REPRESENTING ASPECT GRAPHS OF POLYHEDRAL OBJECTS

We present an efficient algorithm and a new data structure for computing and representing the aspect graph of polyhedral objects under orthographic projection. The aspect graph is an approach to representing 3-D objects by a set of 2-D views, for the purpose of object recognition. In this approach, the viewpoint space is partitioned into regions such that in each region the qualitative structure of the line drawing does not change. The viewing data of an object is the partition of the viewpoint space together with a representative view in each region. The algorithm computes the viewing data for line drawings of polyhedral objects under orthographic projection. For an object of n vertices whose partition is of size m, the partition is constructed in O(n4 log n + m log m) time. After computing the partition, given a view of the object in one region, we use a novel data structure to construct the set of all views in O(C(T)) time and space, where C(T) is the sum of the number of changes between all pairs of neighboring views. A view of size s can be retrieved from this data structure in O(log C(T) + s) time.