2D SHAPE DECOMPOSITION AND THE AUTOMATIC GENERATION OF HIERARCHICAL REPRESENTATIONS
Maryann Simmons, Carlo H. Séquin · International Journal of Shape Modeling · 1998
Many of the tasks that are performed with objects in a virtual environment, such as collision detection, rendering, and visibility culling, are based on the geometric structure of the objects. These operations are most efficient when the objects are represented with well-balanced trees of hierarchical components that reflect the geometric structure of the object at resolution levels appropriate for the particular task. This paper presents a framework for automatically generating hierarchical 2D object representations specialized for geometric tasks. The approach first constructs a multi-resolution representation that encapsulates the salient geometric features of an object, as well as its topological decomposition into parts. The main components of the representation are a Cell-Based Representation that provides spatial filtering at the desired feature resolution, and an Axial Shape Graph that captures local shape information as well as global information about the overall geometric structure of the object. Using the Axial Shape Graph, the task of shape decomposition is reduced to a graph partitioning problem whose solution results in a well-balanced part hierarchy. We show that this structure can be utilized to generate hierarchical representations specialized for the task of Collision Detection in 2D environments.