Publications

We present a versatile and complete free-form shape modeling framework for point-sampled geometry. By combining unstructured point clouds with the implicit surface definition of the moving least squares approximation, we obtain a hybrid geometry representation that allows us to exploit the advantages of implicit and parametric surface models. Based on this representation we introduce a shape modeling system that enables the designer to perform large constrained deformations as well as boolean operations on arbitrarily shaped objects. Due to minimum consistency requirements, point-sampled surfaces can easily be re-structured on the fly to support extreme geometric deformations during interactive editing. In addition, we show that strict topology control is possible and sharp features can be generated and preserved on point-sampled objects. We demonstrate the effectiveness of our system on a large set of input models, including noisy range scans, irregular point clouds, and sparsely as well as densely sampled models.

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.

Active contour models are an efficient, accurate, and robust tool for the segmentation of 2D and 3D image data. In particular, geometric deformable models (GDM) that represent an active contour as the level set of an implicit function have proven to be very effective. GDMs, however, do not provide any topology control, i.e. contours may merge or split arbitrarily and hence change the genus of the reconstructed surface. This behavior is inadequate in settings like the segmentation of organic tissue or other objects whose genus is known beforehand. In this paper we describe a novel method to overcome this limitation while still preserving the favorable properties of the GDM setup. We achieve this by adding (sparse) topological information to the volume representation at locations where it is necessary to locally resolve topological ambiguities. Since the sparse topology information is attached to the edges of the voxel grid, we can reconstruct the interfaces where the deformable surface touches itself at sub-voxel accuracy. We also demonstrate the efficiency and robustness of our method on synthetic as well as on real (MRT) scan data.

We propose a new representation for multiresolution models which uses volume elements enclosed between the different resolution levels to encode the detail information. Keeping these displacement volumes locally constant during a deformation of the base surface leads to a natural behaviour of the detail features. The corresponding reconstruction operator can be implemented efficiently by a hierarchical iterative relaxation scheme, providing close to interactive response times for moderately complex models. Based on this representation we implement a multiresolution editing tool for irregular polygon meshes that allows the designer to freely edit the base surface of a multiresolution model without having to care about self-intersections in the respective detailed surface. We demonstrate the effectiveness and robustness of the reconstruction by several examples with real-world data.

The signed distance field of a surface can effectively support many geometry processing tasks such as decimation, smoothing, and Boolean operations since it provides efficient access to distance (error) estimates. In this paper we present an algorithm to compute a piecewise linear, not necessarily continuous approximation of the signed distance field for a given object. Our approach is based on an adaptive hierarchical space partition that stores a linear distance function in every leaf node. We provide positive and negative criteria for selecting the splitting planes. Consequently the algorithm adapts the leaf cells of the space partition to the geometric shape of the underlying model better than previous methods. This results in a hierarchical representation with comparably low memory consumption and which allows for fast evaluation of the distance field function.

In the last years point-based rendering has been shown to offer the potential to outperform traditional triangle based rendering both in speed and visual quality when it comes to processing highly complex models. Existing surface splatting techniques achieve superior visual quality by proper filtering but they are still limited in rendering speed. On the other hand the increasing availability and programmability of graphics hardware lead to the developement of very efficient hardware-accelerated rendering methods. However, since no filtered splats are used, these approaches trade visual quality for rendering speed. In this paper we propose a rendering framework for point-based geometry providing high visual quality as well as efficient rendering. Our approach is based on a two-pass splatting technique with Gaussian filtering, resulting in a visual quality comparable to existing software rendering systems. Using programmable graphics hardware we delegate all expensive rendering tasks to the GPU, thereby minimizing data transfer and saving CPU resources. The proposed system renders up to 28M mid-quality or up to 10M high-quality surface splats per second on the latest graphics hardware.

In this paper, we present general closed form equations for directly computing the position of a vertex at different subdivision levels for both triangular and quadrilateral meshes. These results are obtained using simple computations and they lead to very useful applications, especially for adaptive subdivision. We illustrate our method on Loop's and Catmull-Clark's subdivision schemes.

We present an out-of-core mesh decimation algorithm that is able to handle input and output meshes of arbitrary size. The algorithm reads the input from a data stream in a single pass and writes the output to another stream while using only a fixed-sized in-core buffer. By applying randomized multiple choice optimization, we are able to use incremental mesh decimation based on edge collapses and the quadric error metric. The quality of our results is comparable to state-of-the-art highquality mesh decimation schemes (which are slower than our algorithm) and the decimation performance matches the performance of the most efficient out-of-core techniques (which generate meshes of inferior quality).

The most important concepts for the handling and storage of freeform shapes in geometry processing applications are parametric representations and volumetric representations. Both have their specific advantages and drawbacks. While the algebraic complexity of volumetric representations S = {(x, y, z) | f (x, y, z) = 0} is independent from the shape complexity, the domain OMEGA of a parametric representation f : OMEGA to S usually has to have the same structure as the surface S itself (which sometimes makes it necessary to update the domain when the surface is modified). On the other hand, the topology of a parametrically defined surface can be controlled explicitly while in a volumetric representation, the surface topology can change accidentally during deformation. A volumetric representation reduces distance queries or inside/outside tests to mere function evaluations but the geodesic neighborhood relation between surface points is difficult to resolve. As a consequence, it seems promising to combine parametric and volumetric representations to effectively exploit both advantages.
In this talk, a number of applications is presented and discussed where such a combination leads to efficient and numerically stable algorithms for the solution of various geometry processing tasks. These applications include surface remeshing, mesh fairing, global error control for mesh decimation and smoothing, and topology control for levelset surfaces.

In this paper we propose an alternative method to build Active Shape Models. It avoids the use of explicit landmarks since it represents shapes by normal displacements relative to an average (domain) contour. By this we reduce the redundancy of the model and consequently the number of parameters in our representation. The resulting models have a significantly lower algebraic complexity compared to those based on landmarks. Additionally we show how to automate the generation of ASMs form sets of unprocessed training contours in arbitrary representation.