Entity-based aspect graphs: Making viewer centered representations more efficient

The aspect graph, a graphical representation of an object's characteristic views has been widely developed by several researchers. However, researchers have stated that aspect graphs are limited due to their high complexity and computational cost. A simple non-convex object, such as a step, has 71 distinct characteristic views (nodes in the aspect graph); more complicated objects could have thousands of characteristic views (nodes). Many characteristic views of an aspect graph are not necessary for many applications. In this paper, a new entity-based aspect graph, EAG, is proposed based on the observation that, for most applications, the visibility of only some of the entities on the object is important. The objects of interest are polyhedral solids. We present algorithms for constructing new entity-based aspect graphs based on the faces, edges and vertices of the object, and for combining and contracting previously constructed EAGs in a database to generate EAGs for new objects. The computation time for construction is reduced, yet sufficient information is provided to the application.