² Huai-Yu Wu, "3D Visual Shape Processing based on Discrete Differential Geometry", Lambert Academic Publishing, ISBN: 978-3659903960, Germany, 2016.
Preprint version: Download (35 MB)
Buy this book on: Amazon
The multimedia revolution has encompassed three types of data so far: sound, image, and video. With the increase in the number of 3D scanned shapes, 3D shape processing is becoming popular in the fields of computer vision, computer graphics, computer aided design (CAD), etc. Digital Geometry Processing (DGP) is a new and much needed application area. Its goal is the research of mathematical and computational foundations needed for the next wave of multimedia data: geometry. Unlike previous data types, we cannot rely on existing theoretical and algorithmic tools since geometric data has intrinsic properties, such as topology, curvature, and non-uniform sampling that render most traditional tools useless. The distinction to the previous three waves of multimedia is fundamental and cannot be overcome by simple adaptation of existing machinery.
Thanks to nearly two-decade efforts of many researchers, much of basic theoretical problems in the field of DGP have been solved until about 2010. This book aims to present the techniques and applications of 3D Visual Shape Processing (VSP) based on discrete differential geometry. The book considers the ”perception” of the geometry in the views both of globality (Part I) and locality (Part II).
In Part I, we explore some research work on shape analysis and processing based on manifold harmonics. Manifold harmonics (i.e. the eigenfunctions of the Laplace-Beltrami operators defined on the surface) not only naturally generalizes spherical harmonics on spherical domain and classical Fourier analysis on 2D domain onto arbitrary 3D surfaces, but also provides hierarchical function representations for surfaces, both of which are extremely useful for the understanding about the globality of 3D shapes.
The main contents of this part can be summarized as following.
First, considering that the main applications we focus on are shape correspondence and similarity comparison, some related work on the two topics are introduced. We show that the isometry property and the locality property are two important issues which are not well concerned by existing methods yet.
Second, after the presentation of some basic knowledge about manifold harmonics, we point out that some detailed issues should be carefully considered when handling non-regular and nonuniform-sampling 3D meshes. Accordingly, we propose the dual Laplace-Beltrami spectral embedding and the symmetric mean-value representation to address these difficulties.
Third, as the first application of our manifold harmonic system, a novel framework is presented to construct dense and high-quality consistent correspondence between non-rigid surfaces. Our correspondence framework exploits the dual Laplace-Beltrami spectral embedding to capture global characteristics of objects, and converts two originally different and complex shapes into two similar and simple shapes to facilitate the correspondence. Since our method completely avoids the computation of geodesic distances, it is robust to local topology changes. By exploiting the excellent properties of the dual domain, our dual spectral framework can robustly construct Laplace-Beltrami embeddings even on highly non-regular 3D meshes. After generating 3D dual spectral meshes for input shapes, we first perform the initial non-rigid matching in the dual Laplace-Beltrami spectral domain. Then, we return 3D spatial domain and apply a shape-preserving non-rigid deformation to produce the final dense consistent correspondence. Meanwhile, a novel shape-preserving gradient operator is proposed, which achieves much better deformation performance than the up-to-date method. We show that our framework is well suitable for non-rigid consistent correspondence, and the high-quality correspondence results are achieved.
Fourth, as the second application of our manifold harmonic system, we propose a novel framework for 3D shape similarity comparison and partial matching. First, we propose a novel symmetric mean-value representation to robustly construct high-quality manifold harmonic bases on nonuniform-sampling meshes. Then, based on the manifold harmonic bases constructed, a novel shape descriptor is presented to capture both of global and local features of 3D shape. This feature descriptor is isometry-invariant, i.e., invariant to rigid-body transformations and non-rigid bending. After characterizing 3D models with the shape features, we perform 3D retrieval by adopting a up-to-date discriminative kernel. This kernel is a dimension-free approach to quantifying the similarity between two unordered feature-sets, thus especially suitable for our high-dimensional feature data. Experimental results show that our framework can be effectively used for both comprehensive comparison and partial matching among non-rigid 3D shapes.
In Part II, based on local differential operators, we develop new methods for efficient, reliable and scalable tools for cross-parameterization (consistent correspondence), mesh deformation and editing, mesh segmentation, mesh faring and many other types of DGP operations. This provides a complete mesh processing pipeline to allow for easy and efficient manipulation of 3D mesh models. The main contributions of this part can be summarized as following.
First, we propose a novel retargetting method, called model transduction, to directly transfer pose between different meshes, without the need of building the skeleton configurations for meshes. Different from previous retargetting methods, such as deformation transfer, model transduction does not require a reference source mesh to obtain source deformation, thus effectively avoids unsatisfying results. Moreover, we show that the transduction method also can be used for pose correction after various mesh editing operations.
Second, we propose a novel framework for consistent correspondence between arbitrary manifold meshes. Different from most existing methods, our approach directly maps the connectivity of the source mesh onto the target mesh without needing to segment input meshes, thus effectively avoids dealing with unstable extreme conditions (e.g. complex boundaries or high genus).
Third, we propose a sketch-based interactive framework for real-time mesh segmentation. With an easy-to-use tool, the user can freely segment a 3D mesh while needing little effort or skill. In order to meaningfully segment the mesh, two dimensionless feature sensitive metrics are proposed, which are independent of the model and part size. We show that these metrics give the clear physical meaning to illustrate discrete differential geometric features, such as the curvature tensor and the curve length of Gaussian image.
Fourth, we propose a novel scheme for shape-preserving "divide and rule" cross-parameterization between 3D meshes. First, based on two scale-independent feature sensitive metrics, we present an easy-to-use tool to produce meaningful mesh segmentation as cross-parameterization's prerequisite. Then we construct convex hull for each part of segmented meshes, and adopt our convex hull cross-parameterization method to generate compatible meshes. Our scheme exploits the excellent properties of convex hull, e.g. good approximating ability and linear convex representation for interior vertices.
Finally, based on the novel mean-value manifold operator, we present a general framework for performing mesh processing tasks. The mean-value manifold operator is a shape-preserving operator defined on manifold meshes (including detailed and highly irregular meshes), and furnishes a variety of processing applications, such as mesh editing, mesh fairing, cross-parameterization and model transduction. Specifically, first, based on this linear operator, our mesh editing method produces visually pleasing deformation results under large angle rotations or big-scale translations of handles. Furthermore, our mesh fairing method performs feature preserving smoothing for various models. The resulting quadratic formulation can be efficiently minimized by fast solving the sparse linear system. We show that our methods fit nicely in a unified framework, where the similar type of linear operator is applied in all phases.
List of Symbols
PART I THE GLOBAL VIEW: 3D SHAPE ANALYSIS BASED ON MANIFOLD HARMONICS
1 Introduction to Manifold Harmonics
1.1 Surface Shape Representation: Why We Choose Manifold Harmonics?
1.2 Main Contributions to the Field of Manifold Harmonics
1.3 Manifold Harmonics for Consistent Correspondence between 3D Shapes
1.4 Manifold Harmonics for 3D Non Rigid Shape Retrieval
2 Related Work of Manifold Harmonics
2.1 Manifold Harmonics for Shape Analysis
2.2 Consistent Correspondence between 3D Shapes
2.3 Non Rigid 3D Shape Retrieval
3 The Manifold Harmonic Analysis on 3D Shape
3.1 The Laplace Beltrami Differential Operator
3.2 Manifold Harmonics
3.2.1 The Continuous Setting
3.2.2 The Discrete Setting
3.3 Reconstructing the Geometry from the Eigenfunctions
3.4 The Symmetric Mean Value Laplace Beltrami Representation
4 Consistent Correspondence Framework Based on the Dual Laplace Beltrami eigenfunctions
4.1 The Dual Laplace Beltrami Spectral Embedding
4.1.1 The Laplace Beltrami Operator vs. the Dual Laplace Beltrami Operator
4.1.2 The Dual Laplace Beltrami Eigenfunctions
4.1.3 3D Dual Laplace Beltrami Spectral Mesh
4.2 Non Rigid Matching in Dual Laplace Beltrami Spectral Domain
4.3 Shape Preserving Consistent Correspondence in 3D Spatial Domain
4.4 Results and Discussion
5 3D Shape Comparison and Partial Matching
5.1 Describing Shape Features Globally and Locally
5.1.1 Manifold Harmonics: to "Think" Globally
5.1.2 The Augmented Descriptor: to Further "Percept" Locally
5.1.3 Evaluation Comparison: the Sampling Strategy vs. the Simplifying Strategy
5.2 Kernel based 3D Shape Retrieval with the Global and (Augmented) Local Shape Descriptor
5.2.1 3D Shape Comparison
5.2.2 Partial Shape Matching
5.3 Results and Discussion
5.4 Summary of Manifold Harmonics
PART II THE LOCAL VIEW: DIGITAL GEOMETRY PROCESSING BASED ON DISCRETE DIFFERENTIAL GEOMETRY
6 Introduction to Digital Geometry Processing
6.1 The Representation of Digital Geometric Model
6.2 Overview of Digital Geometry Processing
6.2.1 Acquisition, Registration and Reconstruction of 3D model
6.2.2 Repairing of Geometry and Topology
6.2.3 Mesh Smoothing and Denoising
6.2.4 Remeshing and Subdivision
6.2.5 3D Mesh Compression
6.2.6 Mesh Segmentation
6.2.7 Mesh Paramerization
6.2.8 Cross Parameterization (Consistent Correspondence)
6.2.9 Mesh Deformation, Editing and Animation
6.2.10 Retargetting of 3D Data
6.2.11 Structure Design and Shape Optimization for 3D printing
6.3 Frameworks of Digital Geometry Processing
7 A Sketch Based Framework for Real Time Mesh Segmentation
7.1.2 Definitions and Scheme Overview
7.2 Background and Related Work
7.3 Generating Vertex Parts with Angle Based Diffusion Metric
7.4 Generating Facet Parts with Angle Based Feature Sensitive Metric
7.5 Refining Boundaries
7.5.1 Adjusting Facet Parts by Convex Property
7.5.2 Adjusting Facet Parts by Visual Angle Property
7.6 Experimental Results
8 Model Transduction for Triangle Meshes
8.2 Model Transduction
8.2.1 Step One: Generating the Matching Mesh
8.2.2 Step Two: Obtaining the Pose "Mesh"
8.2.3 Step Three: Translating Pose Triangles with the Detail Preserving Constraint and the Smoothness Constraint
8.3 More Applications of Model Transduction
8.3.1 Additional Application I: Pose Correction of 3D Model After Various Editing Operations
8.3.2 Additional Application II: Skeleton Free Deformation Animation with 3D Mocap Data
8.4 Results and Discussion
9 Consistent Correspondence between Arbitrary Manifold Surfaces
9.1.1 Related Works
9.1.2 Notations and Definitions
9.2 Consistent Correspondence Framework
9.2.1 Mean value Laplacian Fitting Scheme
9.2.2 Critical Vertices
9.2.3 Vertex Relocation and Projection Scheme
9.3 Results and Discussion
10 Partwise Cross Parameterization via Nonregular Convex Hulls
10.3 Algorithm Overview
10.4 Constructing Nonregular Domains
10.4.1 3D Convex Decomposition
10.4.2 Sketch Based Segmentation Tool
10.5 Partwise Convex hull Cross parameterization Method
10.5.1 Mean Value Laplacian Convex Approximation Scheme
10.5.2 Handling the Boundaries
10.5.3 Reconstructing the Compatible Mesh
10.6 Results and Discussion
11 Mean Value Manifold Operator for Shape Preserving Processing
11.2 Mesh Editing with the Mean Value Manifold Operator
11.3 Shape preserving Mesh Smoothing
11.4 Results and Discussion
A Gradient Descent
B Newton Method
C To Solve the Linear Least Square Problem
D To Solve the Nonlinear Least Square Problem
List of Figures
List of Tables