Publications

Aiming at robust surface structure recovery, we extend the powerful optimization technique of variational shape approximation by allowing for several different primitives to represent the geometric proxy of a surface region. While the original paper only considered planes, we also include spheres, cylinders, and more complex rollingball blend patches. The motivation for this choice is the fact that most technical CAD objects consist of patches from these four categories. The robust segmentation and global optimization properties which have been observed for the variational shape approximation carry over to our hybrid extension. Hence, we can use our algorithm to segment a given mesh model into characteristic patches and provide a corresponding geometric proxy for each patch. The expected result that we recover surface structures more robustly and thus obtain better approximations with a smaller number of primitives, is validated and demonstrated on a number of examples.

We are proposing a multiresolution representation which uses a subdivision surface as a smooth base surface with respect to which a high resolution mesh is defined by normal displacement. While this basic representation is quite straightforward, our actual contribution lies in the automatic generation of such a representation. Given a high resolution mesh, our algorithm is designed to derive a subdivision control mesh whose structure is properly adjusted and aligned to the major geometric features. This implies that the control vertices of the subdivision surface not only control globally smooth deformations but in addition that these deformations are meaningful in the sense that their support and shape correspond to the characteristic structure of the input mesh. This is achieved by using a new decimation scheme for general polygonal meshes (not just triangles) that is based on face merging instead of edge collapsing. A face-based integral metric makes the decimation scheme very robust such that we can obtain extremely coarse control meshes which in turn allow for deformations with large support.

There are two major approaches for converting a tessellated CAD model that contains inconsistencies like cracks or intersections into a manifold and closed triangle mesh. Surface oriented algorithms try to fix the inconsistencies by perturbing the input only slightly, but they often cannot handle special cases. Volumetric algorithms on the other hand produce guaranteed manifold meshes but mostly destroy the structure of the input tessellation due to global resampling. In this paper we combine the advantages of both approaches: We exploit the topological simplicity of a voxel grid to reconstruct a cleaned up surface in the vicinity of intersections and cracks, but keep the input tessellation in regions that are away from these inconsistencies. We are thus able to preserve any characteristic structure (i.e. iso-parameter or curvature lines) that might be present in the input tessellation. Our algorithm closes gaps up to a user-defined maximum diameter, resolves intersections, handles incompatible patch orientations and produces a feature-sensitive, manifold output that stays within a prescribed error-tolerance to the input model.

Current surface-based methods for interactive freeform editing of high resolution 3D models are very powerful, but at the same time require a certain minimum tessellation or sampling quality in order to guarantee sufficient robustness. In contrast to this, space deformation techniques do not depend on the underlying surface representation and hence are affected neither by its complexity nor by its quality aspects. However, while analogously to surface-based methods high quality deformations can be derived from variational optimization, the major drawback lies in the computation and evaluation, which is considerably more expensive for volumetric space deformations. In this paper we present techniques which allow us to use triharmonic radial basis functions for real-time freeform shape editing. An incremental least-squares method enables us to approximately solve the involved linear systems in a robust and efficient manner and by precomputing a special set of deformation basis functions we are able to significantly reduce the per-frame costs. Moreover, evaluating these linear basis functions on the GPU finally allows us to deform highly complex polygon meshes or point-based models at a rate of 30M vertices or 13M splats per second, respectively.

Because of their conceptual simplicity and superior flexibility, point-based geometries evolved into a valuable alternative to surface representations based on polygonal meshes. Elliptical surface splats were shown to allow for high-quality anti-aliased rendering by sophisticated EWA filtering. Since the publication of the original software-based EWA splatting, several authors tried to map this technique to the GPU in order to exploit hardware acceleration. Due to the lacking support for splat primitives, these methods always have to find a trade-off between rendering quality and rendering performance. In this paper, we discuss the capabilities of today's GPUs for hardware-accelerated surface splatting. We present an approach that achieves a quality comparable to the original EWA splatting at a rate of more than 20M elliptical splats per second. In contrast to previous GPU renderers, our method provides per-pixel Phong shading even for dynamically changing geometries and high-quality anti-aliasing by employing a screen-space pre-filter in addition to the object-space reconstruction filter. The use of deferred shading techniques effectively avoids unnecessary shader computations and additionally provides a clear separation between the rasterization and the shading of elliptical splats, which considerably simplifies the development of custom shaders. We demonstrate quality, efficiency, and flexibility of our approach by showing several shaders on a range of models.

Surface splatting enables high quality and ecient rendering algorithms for dense point-sampled datasets. However, with increasing data complexity, the need for multiresolution models becomes evident. For triangle meshes, progressive or continuous level of detail hierarchies have proven to be very effective when it comes to (locally) adapt the resolution level of the 3D model to the application-dependent quality requirements. In this paper we transfer this concept to splat-based geometry representations. Our progressive splat decimation procedure uses the standard greedy approach but unlike previous work, it uses the full splat geometry in the decimation criteria and error estimates, not just the splat centers. With two improved error metrics, this new greedy framework offers better approximation quality than other progressive splat decimators. It comes even close to the recently proposed globally optimized single-resolution sub-sampling techniques while being faster by a factor of 3.

We present a fully automatic technique which converts an inconsistent input mesh into an output mesh that is guaranteed to be a clean and consistent mesh representing the closed manifold surface of a solid object. The algorithm removes all typical mesh artifacts such as degenerate triangles, incompatible face orientation, non-manifold vertices and edges, overlapping and penetrating polygons, internal redundant geometry as well as gaps and holes up to a user-defined maximum size. Moreover, the output mesh always stays within a prescribed tolerance to the input mesh. Due to the effective use of a hierarchical octree data structure, the algorithm achieves high voxel resolution (up to 4096^3 on a 2GB PC) and processing times of just a few minutes for moderately complex objects. We demonstrate our technique on various architectural CAD models to show its robustness and reliability.

We present a method for scattered data approximation with subdivision surfaces which actually uses the true representation of the limit surface as a linear combination of smooth basis functions associated with the control vertices. A robust and fast algorithm for exact closest point search on Loop surfaces which combines Newton iteration and non-linear minimization is used for parameterizing the samples. Based on this we perform unconditionally convergent parameter correction to optimize the approximation with respect to the L² metric and thus we make a well-established scattered data fitting technique which has been available before only for B-spline surfaces, applicable to subdivision surfaces. We also adapt the recently discovered local second order squared distance function approximant to the parameter correction setup. Further we exploit the fact that the control mesh of a subdivision surface can have arbitrary connectivity to reduce the L^? error up to a certain user-defined tolerance by adaptively restructuring the control mesh. Combining the presented algorithms we describe a complete procedure which is able to produce high-quality approximations of complex, detailed models.

Allowing for copyright protection and ownership assertion, digital watermarking techniques, which have been successfully applied for classical media types like audio, images and videos, have recently been adapted for the newly emerged multimedia data type of 3D geometry models. In particular, the widely used spread-spectrum methods can be generalized for 3D datasets by transforming the original model to a frequency domain and perturbing the coefficients of the most dominant basis functions. Previous approaches employing this kind of spectral watermarking are mainly based on multiresolution mesh analysis, wavelet domain transformation or spectral mesh analysis. Though they already exhibit good resistance to many types of real-world attacks, they are often far too slow to cope with very large meshes due to their complicated numerical computations. In this paper, we present a novel spectral watermarking scheme using new orthogonal basis functions based on radial basis functions. With our proposed fast basis function orthogonalization, while observing similar persistence with respect to various attacks as other related approaches, our scheme runs faster by two orders of magnitude and thus can efficiently watermark very large models.

We present several non-linear 4-point interpolatory schemes, derived from the "classical" linear 4-point scheme. These new schemes have variable tension parameter instead of the fixed tension parameter in the linear 4-point scheme. The tension parameter is adapted locally according to the geometry of the control polygon within the 4-point stencil. This allows the schemes to remain local and in the same time to achieve two important shape-preserving properties - artifacts elimination and convexity-preservation. The proposed schemes are robust and have special features such as "double-knot" edges corresponding to continuity without geometrical smoothness and inflection edges support for convexity-preservation. Convergence proof is given and experimental smoothness analysis is done in detail, which indicates that the limit curves are C^1.

Building intuitive user-interfaces for Virtual Reality applications is a difficult task, as one of the main purposes is to provide a ''natural'', yet efficient input device to interact with the virtual environment. One particularly interesting approach is to track and retarget the complete motion of a subject. Established techniques for full body motion capture like optical motion tracking exist. However, due to their computational complexity and their reliance on pre-specified models, they fail to meet the demanding requirements of Virtual Reality environments such as real-time response, immersion, and ad hoc configurability. Our goal is to support the use of motion capture as a general input device for Virtual Reality applications. In this paper we present a self-calibrating framework for optical motion capture, enabling the reconstruction and tracking of arbitrary articulated objects in real-time. Our method automatically estimates all relevant model parameters on-the-fly without any information on the initial tracking setup or the marker distribution, and computes the geometry and topology of multiple tracked skeletons. Moreover, we show how the model can make the motion capture phase robust against marker occlusions by exploiting the redundancy in the skeleton model and by reconstructing missing inner limbs and joints of the subject from partial information. Meeting the above requirements our system is well applicable to a wide range of Virtual Reality based applications, where unconstrained tracking and flexible retargeting of motion data is desirable.

In this work we introduce a new method for representing and evolving snakes that are constrained to lie on a prescribed surface (triangle mesh). The new representation allows to automatically adapt the snake resolution to the surface tesselation and does not need any (unstable) back-projection operations. Furthermore, it enables efficient and robust collision detection and gives us complete control on the topological behaviour of the snakes, i.e. snakes may split or merge depending on the intended task. Possible applications include enhanced mesh scissoring operations and the detection of constrictions of a surface.

Mario Botsch, David Bommes, Leif Kobbelt

The use of polygonal mesh representations for freeform geometry enables the formulation of many important geometry processing tasks as the solution of one or several linear systems. As a consequence, the key ingredient for efficient algorithms is a fast procedure to solve linear systems. A large class of standard problems can further be shown to lead more specifically to sparse, symmetric, and positive definite systems, that allow for a numerically robust and efficient solution. In this paper we discuss and evaluate the use of \emph{sparse direct solvers} for such kind of systems in geometry processing applications, since in our experiments they turned out to be superior even to highly optimized multigrid methods, but at the same time were considerably easier to use and implement. Although the methods we present are well known in the field of high performance computing, we observed that they are in practice surprisingly rarely applied to geometry processing problems.