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.

Due to advances in computer hardware, virtual environments become significantly larger and more complex. Therefore the modeling of virtual worlds, e.g. for computer animation and games becomes increasingly time and resource consuming.

In architectural settings façade features are influenced by the underlying geometrical structure or even by other façade structures, e.g. façade edges made of large stones influence the adjacent walls. To achieve an aesthetic look of the façade adjacent structures must be seamlessly aligned.

The modeling of such structures is a tedious work. With our approach only a few basic parameters are needed to create highly detailed façades. This relieves the designer of the burden of difficult modeling tasks and gives him more high level control.

In this paper we present a strategy for a floor plan representation that permits arbitrary floor plan outlines. This simplifies the roof generation for different roof types in an easy way to achieve an aesthetic goal. Based on the floor plan representation we describe a hierarchical decomposition of architectural façade features. With an order relation on it we represent the interdependencies between the façade features and introduce a geometry generator for them.

With our approach every building in a large VR city will look different but can have a high level on architectural details.

This paper describes a system for dynamic simulation of linked rigid bodies in real-time. The system was developed to simulate mechanical behaviour in VR applications. An extension for a 3D modelling tool was developed which provides the possibility to model a VR scene including the geometries and mechanical parameters of all rigid bodies and the properties of the joints between them easily. For the dynamic simulation an impulse-based method is used. The distinguishing feature of this method is that all kind of constraints are satisfied with the iterative computation of impulses. The advantage of this iterative technique is that it is fast and accurate results can be achieved. The dynamic simulation system uses efficient collision detection methods. For every collision that is detected a contact region between the objects is determined to provide an accurate collision response.

At first we will give a short introduction to the new impulse-based method for dynamic simulation. Up till now impulses were frequently used to resolve collisions between rigid bodies. In the last years we have extended these techniques to simulate constraint forces. Important properties of the new impulse method are: (1) Simulation in Cartesian coordinates, (2) complete elimination of drift as known from Lagrange multiplier methods, (3) simple integration of collision and friction and (4) real time performance even for complex multibody systems like six legged walking machines. In order to demonstrate the potential of the impulse-based method, we report on numerical experiments. We compare the following dynamic simulation methods: (1) Generalized (or reduced) coordinates, (2) Lagrange multipliers without and with several stabilization methods like Baumgarte, velocity correction and projection method, (3) impulse-based methods of order 2, 4, 6, 8, and 10. We have simulated the mathematical pendulum, the double and the triple pendulum with all of these dynamic simulation methods and report on the attainable accuracy.

First, we will provide a short introduction to the impulse-based method for dynamic simulation. Till now, impulses were frequently used to resolve collisions between rigid bodies. In the last years, we have extended these techniques to simulate constraint forces. Important properties of the new impulse method are: (1) Simulation in Cartesian coordinates, (2) complete elimination of the constraint drift known from Lagrange multiplier methods, (3) simple integration of collision and friction and (4) real-time performance even for complex multibody systems like six-legged walking machines. In order to demonstrate the potential of the impulse-based method, we report on numerical experiments. We compare the following dynamic simulation methods: (1) Generalized (or reduced) coordinates, (2) the Lagrange multiplier method with and without several stabilization methods like Baumgarte, the velocity correction and a projection method, (3) impulse-based methods of integration order 2, 4, 6, 8, and 10. We have simulated the mathematical pendulum, the double and the triple pendulum with all of these dynamic simulation methods and report on the attainable accuracy. It turned out that the impulse methods of higher integration order are all of O(h^3) but have very small factors and are therefore relatively accurate. A Lagrange multiplier method fully stabilized by impulse-based techniques turned out to be the best of the Lagrange multiplier methods tested.

Impulse-based dynamic simulation using the iterative method results in relatively simple algorithms which are easy to implement. However, two important theoretical questions have so far still remained open: (1) In what situations does the iterative procedure converge or diverge, and how can divergence be avoided? (2) Does the impulse-based simulation converge towards the exact solution of the dynamics problem as the step size is reduced? We will completely answer both questions in this paper. First we simplify the argumentation in that we prove that for every multibody system there is a dynamically and kinematically equivalent point mass system. Hence, our results on point mass systems also apply to multibody simulations. Next we show how to replace the iterative procedures by solving systems of linear equations. We prove that the matrices of these equation systems are non-singular if redundant constraints are removed from the point mass system in question. We prove further that the solution generated by the impulse-based procedure converges towards the exact solution of the dynamics problem as the step size is reduced towards zero. The proof is based on a detailed comparison of the impulse-based integration expression and the Taylor series solution. It is well known that the latter converges to the exact solution of the dynamics problem if a Lipschitz condition is satisfied.

Comparison with the standard numerics on the basis of Lagrange multipliers shows significant advantages for the impulse-based method because the latter is completely free of drift problems, and stabilizations in the sense of Baumgarte are unnecessary. Because of the existence of methods of higher order, we can finally conclude that the impulse-based method is superior to the method with Lagrange multipliers.

In this paper, we address the problem of detecting pedestrians in crowded real-world scenes with severe overlaps. Our basic premise is that this problem is too difficult for any type of model or feature alone. Instead, we present a novel algorithm that integrates evidence in multiple iterations and from different sources. The core part of our method is the combination of local and global cues via a probabilistic top-down segmentation. Altogether, this approach allows to examine and compare object hypotheses with high precision down to the pixel level. Qualitative and quantitative results on a large data set confirm that our method is able to reliably detect pedestrians in crowded scenes, even when they overlap and partially occlude each other. In addition, the flexible nature of our approach allows it to operate on very small training sets.

Pedestrian detection in real world scenes is a challenging problem. In recent years a variety of approaches have been proposed, and impressive results have been reported on a variety of databases. This paper systematically evaluates (1) various local shape descriptors, namely Shape Context and Local Chamfer descriptor and (2) four different interest point detectors for the detection of pedestrians. Those results are compared to the standard global Chamfer matching approach. A main result of the paper is that Shape Context trained on real edge images rather than on clean pedestrian silhouettes combined with the Hessian-Laplace detector outperforms all other tested approaches.

In this paper we compare the performance of local detectors and descriptors in the context of object class recognition. Recently, many detectors / descriptors have been evaluated in the context of matching as well as invariance to viewpoint changes [20]. However, it is unclear if these results can be generalized to categorization problems, which require different properties of features. We evaluate 5 stateof-the-art scale invariant region detectors and 5 descriptors. Local features are computed for 20 object classes and clustered using hierarchical agglomerative clustering. We measure the quality of appearance clusters and location distributions using entropy as well as precision. We also measure how the clusters generalize from training set to novel test data. Our results indicate that extended SIFT descriptors [22] computed on Hessian-Laplace [20] regions perform best. Second score is obtained by Salient regions [11]. The results also show that these two detectors provide complementary features. The new detectors/descriptors significantly improve the performance of a state-of-the art recognition approach [16] in pedestrian detection task.

Category detection is a lively area of research. While categorization algorithms tend to agree in using local descriptors, they differ in the choice of the classifier, with some using generative models and others discriminative approaches. This paper presents a method for object category detection which integrates a generative model with a discriminative classifier. For each object category, we generate an appearance codebook, which becomes a common vocabulary for the generative and discriminative methods. Given a query image, the generative part of the algorithm finds a set of hypotheses and estimates their support in location and scale. Then, the discriminative part verifies each hypothesis on the same codebook activations. The new algorithm exploits the strengths of both original methods, minimizing their weaknesses. Experiments on several databases show that our new approach performs better than its building blocks taken separately. Moreover, experiments on two challenging multi-scale databases show that our new algorithm outperforms previously reported results.

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.