Freeform Shape Representations for Efficient Geometry Processing
The most important data structures for handling and storage of free form shapes in geometry processing applications and computer graphics can be classified according to the dimensionality of their basic structural elements: point-sets, polygon meshes, as well as volumetric representations are well established concepts to describe the shape of arbitrarily complex objects. On the other hand, algorithms to process a given geometric object can be classified according to the dominant access operation which can be of the type evaluation (sampling), query (e.g. inside/outside tests), or modification (of the geometry or the topology). On a more abstract level, we can in principle distinguish between unstructured geometry representations which do not imply any global regularity and uniformly structured representations or even hierarchically structured representations. All these different types of shape representations will be presented in this talk and the respective strengths and disadvantages will be discussed in detail. For a given application we can analyse which types of access operations are the most critial ones and then design a custom data structure according to the usage profile. In some cases it turns out that a proper combination of two different representations provides the optimal performance or robustness. We will present a couple of important geometry processing problems such as topology control for deforming implicit surfaces, mesh decimation and smoothing with global error control, and mesh restoration where this combination of geometry data representations leads to superior algorithms compared to the standard approaches.