We introduce a construction of subspaces of the spaces of tangential vector, n-vector, and tensor fields on surfaces. The resulting subspaces can be used as the basis of fast approximation algorithms for design and processing problems that involve tangential fields. Important features of our construction are that it is based on a general principle, from which constructions for different types of tangential fields can be derived, and that it is scalable, making it possible to efficiently compute and store large subspace bases for large meshes. Moreover, the construction is adaptive, which allows for controlling the distribution of the degrees of freedom of the subspaces over the surface. We evaluate our construction in several experiments addressing approximation quality, scalability, adaptivity, computation times and memory requirements. Our design choices are justified by comparing our construction to possible alternatives. Finally, we discuss examples of how subspace methods can be used to build interactive tools for tangential field design and processing tasks.

@en

The research field of geometry processing is concerned with the representation, analysis, modeling, simulation and optimization of geometric data. In this thesis, we introduce novel techniques and efficient algorithms for problems in geometry processing, such as the modeling and simulation of elastic deformable objects, the design of tangential vector fields or the automatic generation of spline curves. The complexity of the geometric data determines the computation time of algorithms within these applications. The high resolution of modern meshes, for example, poses a big challenge when geometric processing tools are expected to perform at interactive rates. To this end the goal of this thesis is to introduce fast approximation techniques for problems in geometry processing. One line of research to achieve this goal will be to introduce novel model order reduction techniques to problems in geometry processing. Model order reduction is a concept to reduce the computational complexity of models in numerical simulations, energy optimizations and modeling problems. New specialized model order reduction approaches are introduced and existing techniques are applied to enhance tools within the field of geometry processing. In addition to introducing model reduction techniques, we make several other contributions to the field. We present novel discrete differential operators and higher order smoothness energies for the modeling of tangential (n-)vector fields. These are used, to develop novel tools for the modeling of fur, stroke based renderings or anisotropic reflection properties on meshes. We propose a geometric flow for curves in shape space that allows for the processing and creation of animations of elastic deformable objects. A new optimization scheme for sparsity regularized functionals is introduced and used to compute natural, localized deformations of geometrical objects. Lastly, we reformulate the classical problem of spline optimization as a sparsity regularized optimization problem.@en

We introduce the Reduced Immersed Method (RIM) for the real-time simulation of two-way coupled incompressible fluids and elastic solids and the interaction of multiple deformables with (self-)collisions. Our framework is based on a novel discretization of the immersed boundary equations of motion, which model fluid and deformables as a single incompressible medium and their interaction as a unified system on a fixed domain combining Eulerian and Lagrangian terms. One advantage for real-time simulations resulting from this modeling is that two-way coupling phenomena can be faithfully simulated while avoiding costly calculations such as tracking the deforming fluid-solid interfaces and the associated fluid boundary conditions. Our discretization enables the combination of a PIC/FLIP fluid solver with a reduced-order Lagrangian elasticity solver. Crucial for the performance of RIM is the efficient transfer of information between the elasticity and the fluid solver and the synchronization of the Lagrangian and Eulerian settings. We introduce the concept of twin subspaces that enables an efficient reduced-order modeling of the transfer. Our experiments demonstrate that RIM handles complex meshes and highly resolved fluids for large time steps at high framerates on of-the-shelf hardware, even in the presence of high velocities and rapid user interaction. Furthermore, it extends reduced-order elasticity solvers such as Hyper-Reduced Projective Dynamics with natural collision handling.

@en

We introduce a variational approach for modeling n-symmetry vector and direction fields on surfaces that supports interpolation and alignment constraints, placing singularities and local editing, while providing real-time responses. The approach is based on novel biharmonic and m-harmonic energies for n-fields on surface meshes and the integration of hard constraints to the resulting optimization problems. Real-time computation rates are achieved by a model reduction approach employing a Fourier-like n-vector field decomposition, which associates frequencies and modes to n-vector fields on surfaces. To demonstrate the benefits of the proposed n-field modeling approach, we use it for controlling stroke directions in line-art drawings of surfaces and for the modeling of anisotropic BRDFs, which define the reflection behavior of surfaces.

@en

The spectrum and eigenfunctions of the Laplace-Beltrami operator are at the heart of effective schemes for a variety of problems in geometry processing. A burden attached to these spectral methods is that they need to numerically solve a large-scale eigenvalue problem, which results in costly precomputation. In this paper, we address this problem by proposing a fast approximation algorithm for the lowest part of the spectrum of the Laplace-Beltrami operator. Our experiments indicate that the resulting spectra well-approximate reference spectra, which are computed with state-of-the-art eigensolvers. Moreover, we demonstrate that for different applications that comparable results are produced with the approximate and the reference spectra and eigenfunctions. The benefits of the proposed algorithm are that the cost for computing the approximate spectra is just a fraction of the cost required for numerically solving the eigenvalue problems, the storage requirements are reduced and evaluation times are lower. Our approach can help to substantially reduce the computational burden attached to spectral methods for geometry processing.

@en

We present a method for the real-time simulation of deformable objects that combines the robustness, generality, and high performance of Projective Dynamics with the efficiency and scalability offered by model reduction techniques. The method decouples the cost for time integration from the mesh resolution and can simulate large meshes in real-time. The proposed hyper-reduction of Projective Dynamics combines a novel fast approximation method for constraint projections and a scalable construction of sparse subspace bases. The resulting system achieves real-time rates for large subspaces enabling rich dynamics and can resolve general user interactions, collision constraints, external forces and changes to the materials. The construction of the hyper-reduced system does not require user-interaction and refrains from using training data or modal analysis, which results in a fast preprocessing stage.

@en

We propose a framework for the spectral processing of tangential vector fields on surfaces. The basis is a Fourier-type representation of tangential vector fields that associates frequencies with tangential vector fields. To implement the representation for piecewise constant tangential vector fields on triangle meshes, we introduce a discrete Hodge–Laplace operator that fits conceptually to the prominent cotan discretization of the Laplace–Beltrami operator. Based on the Fourier representation, we introduce schemes for spectral analysis, filtering and compression of tangential vector fields. Moreover, we introduce a splinetype editor for modeling of tangential vector fields with interpolation constraints for the field itself and its divergence and curl. Using the spectral representation, we propose a numerical scheme that allows for real-time modeling of tangential vector fields.@en

The natural vibration modes of deformable objects are a fundamental physical phenomenon. In this paper, we introduce compressed vibration modes, which, in contrast to the natural vibration modes, are localized (“sparse”) deformations. The localization is achieved by augmenting the objective which has the vibration modes as minima by a L1 term. As a result, the compressed modes form a compromise between localization and optimal energy efficiency of the deformations. We introduce a scheme for computing bases of compressed modes by solving sequences of convex optimization problems. Our experiments demonstrate that the resulting bases are well-suited for reduced-order shape deformation and for guiding the segmentation of objects into functional parts.@en

e introduce techniques for the processing of motion and animations of non-rigid shapes. The idea is to regard animations of deformable objects as curves in shape space. Then, we use the geometric structure on shape space to transfer concepts from curve processing in R n to the processing of motion of non-rigid shapes. Following this principle, we introduce a discrete geometric flow for curves in shape space. The flow iteratively replaces every shape with a weighted average shape of a local neighborhood and thereby globally decreases an energy whose minimizers are discrete geodesics in shape space. Based on
the flow, we devise a novel smoothing filter for motions and animations of deformable shapes. By shortening the length in shape space of an animation, it systematically regularizes the deformations between consecutive frames of the animation. The scheme can be used for smoothing and noise removal, e.g., for reducing jittering artifacts in motion capture data. We introduce a reduced-order method for the computation of the flow. In addition to being efficient for the smoothing of curves, it is a novel scheme for computing geodesics in shape space. We use the scheme to construct non-linear “Bézier curves” by executing de Casteljau’s algorithm in shape space.@en