We introduce a geometric multigrid method for solving linear systems arising from variational problems on surfaces in geometry processing, Gravo MG. Our scheme uses point clouds as a reduced representation of the levels of the multigrid hierarchy to achieve a fast hierarchy construction and to extend the applicability of the method from triangle meshes to other surface representations like point clouds, nonmanifold meshes, and polygonal meshes. To build the prolongation operators, we associate each point of the hierarchy to a triangle constructed from points in the next coarser level. We obtain well-shaped candidate triangles by computing graph Voronoi diagrams centered around the coarse points and determining neighboring Voronoi cells. Our selection of triangles ensures that the connections of each point to points at adjacent coarser and finer levels are balanced in the tangential directions. As a result, we obtain sparse prolongation matrices with three entries per row and fast convergence of the solver. Code is available at https://graphics.tudelft.nl/gravo_mg.@en

Research in geometry processing concerns the design of algorithms and mathematical models for the analysis and manipulation of geometric data. Examples of its applications are shape projection (e.g. smoothing and filtering), shape correspondence (e.g. functional maps), shape descriptors (e.g. heat and wave kernel signatures), segmentation, and surface parameterization. A set of tools that have proven to be useful for solving such tasks are spectral methods. In general, spectral methods solve geometry processing problems by taking the benefit of the spectra and the eigenfunctions of the Laplacian operator defined on a surface mesh. This allows us to extend the notion of Fourier analysis from signal and image processing to surface processing, a theoretically sound and well-researched concept. In practice, the decomposition of the Laplacian operator into a diagonal matrix of eigenvalues and a rectangular matrix of eigenvectors enables efficient treatment of a broad range of geometry processing problems. A main adversity in spectral geometry processing is the expensive computational cost attached to the eigendecomposition of the Laplacian operator, before we can use the spectra and the eigenfunctions for the applications. Since analytical solutions are not known, one needs to opt for a numerical method to solve the eigenvalue problem. It is a numerically expensive computation, especially for a complex mesh. Another challenge comes from the storage requirement. Considering that the Laplace--Beltrami operator has global support, it takes a dense matrix to represent the eigenvectors. Therefore, the memory requirement for saving the eigenbasis can be high, particularly when a large number of eigenfunctions need to be stored. These challenges hinder the use of spectral methods for geometry processing applications. In this thesis, we introduce new methods addressing the aforementioned challenges. In Chapter 2, we propose a fast algorithm that allows for approximating the smallest eigenvalues and the corresponding eigenvectors of the Laplace--Beltrami operator in just a fraction of the time needed to solve the original eigenvalue problem. We construct subspaces of the space of all functions that include low frequency functions and restrict the solution of the eigenproblem to the subspace. It enables the fast approximation of the eigenproblem, independent of the size of the original problem. Our novel scheme also enables significantly more efficient storage of the approximated eigenfunctions. We show that the approximated spectra are close to the reference spectra and that the fast approximation method benefits geometry processing applications, such as shape classification, geodesic distance computation, shape projection (e.g. filtering), and vibration modes of deformable objects. We consider localized eigenfields of the Hodge--Laplacian, which serve as a sparse basis for the efficient design and processing of tangential fields, in Chapter 3. The basis spans subspaces of the spaces of tangential vector, $n$-vector, and tensor fields on a surface mesh. Restricting the design and processing of tangential fields to the subspace allows us to decouple the degrees of freedom we use for design and processing tasks from the complexity of the mesh representation. The construction is scalable, so we can efficiently compute and store subspaces for large meshes. We evaluate the performance of the novel method on various modeling and processing tasks in vector fields (fur design), n-vector fields (n-field design and hatching/line-art design), and tensor fields (curvature fields smoothing) and show that the computation time decreases up to two orders of magnitude compared to that of the original problem. Chapter 4 introduces a novel multigrid method for numerically solving the Laplace--Beltrami eigenproblems on a surface mesh. Our new technique, the Hierarchical Subspace Iteration Method (HSIM), works on a hierarchy of nested vector spaces, in which the solution of the coarser level is used as an initial solution on the finer level. We construct the coarsest level such that the eigenproblems can be solved efficiently using a dense eigensolver. On every level, the prolongation operator maps the solution from the coarser to the finer level. The result then can be used as an initialization for subspace iterations to approximate the eigenpairs. This approach significantly reduces the number of iterations at the finest level, compared to the non-hierarchical subspace iteration method. We show that HSIM outperforms the Locally Optimal Block Preconditioned Conjugate Gradient method and the state-of-the-art Lanczos-based eigensolvers, such as Matlab's eigs, Manifold Harmonics, and SpectrA. In summary, each of the chapters in this thesis proposes efficient algorithms for computing the eigendecompositions of Laplace--Beltrami and Hodge--Laplace operators, mainly using model order reduction and multigrid approaches. These methods reduce computational costs (Chapter 1-3) and storage requirements (Chapter 1-2) for the spectral processing of scalar functions and tangential fields on surface meshes.@en

Sparse eigenproblems are important for various applications in computer graphics. The spectrum and eigenfunctions of the Laplace–Beltrami operator, for example, are fundamental for methods in shape analysis and mesh processing. The Subspace Iteration Method is a robust solver for these problems. In practice, however, Lanczos schemes are often faster. In this article, we introduce the Hierarchical Subspace Iteration Method (HSIM), a novel solver for sparse eigenproblems that operates on a hierarchy of nested vector spaces. The hierarchy is constructed such that on the coarsest space all eigenpairs can be computed with a dense eigensolver. HSIM uses these eigenpairs as initialization and iterates from coarse to fine over the hierarchy. On each level, subspace iterations, initialized with the solution from the previous level, are used to approximate the eigenpairs. This approach substantially reduces the number of iterations needed on the finest grid compared to the non-hierarchical Subspace Iteration Method. Our experiments show that HSIM can solve Laplace–Beltrami eigenproblems on meshes faster than state-of-the-art methods based on Lanczos iterations, preconditioned conjugate gradients, and subspace iterations.@en

Learning from 3D point-cloud data has rapidly gained momentum, motivated by the success of deep learning on images and the increased availability of 3D~data. In this paper, we aim to construct anisotropic convolution layers that work directly on the surface derived from a point cloud. This is challenging because of the lack of a global coordinate system for tangential directions on surfaces. We introduce DeltaConv, a convolution layer that combines geometric operators from vector calculus to enable the construction of anisotropic filters on point clouds. Because these operators are defined on scalar- and vector-fields, we separate the network into a scalar- and a vector-stream, which are connected by the operators. The vector stream enables the network to explicitly represent, evaluate, and process directional information. Our convolutions are robust and simple to implement and match or improve on state-of-the-art approaches on several benchmarks, while also speeding up training and inference.@en

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 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