Differential Mesh Processing

Since 1980s, we have witnessed two major breakthroughs in the field of geometric modeling. The first one happened in 1980s, called free-form deformation, edits geometric models via modifying a proxy. The second one happened in 1990s, named multi-resolution editing, processes geometric models by manipulating a coarse shape. Geometric modeling has been promoted by these two breakthroughs significantly. In particular, free-form deformation becomes so mature that has been an indispensable component of commercial modeling softwares.Today, the rapid advance of 3D scanning techniques have made geometric models with hundreds of thousands of primitives ubiquitous. On one hand, the more primitives a model contains, the more accurate its geometric feature can be figured out. On the other hand, scanned models pose new challenges to geometric processing, i.e., it is rather difficult to preserve geometric details during editing. To meet this challenge, other research teams and us introduce novel geometry representations as well as computational models for scanned models. We call these new approaches differential domain methods (DDMs). Comparing with previous methods, DDMs have the remarkable feature that geometric details can be well-preserved during editing. Therefore, DDMs are particular suitable for processing scanned models. Currently, DDMs have been a hot research topic and have been considered as the third breakthrough by some foreign researchers. Our work, as presented in this dissertation, are one of major parts of this new breakthrough.Unlike traditional methods, our technique regards 3D geometry as scalar fields defined on the common domain mesh instead of continuous/discrete point sets defined in Euclidean space. Consequently, we process geometric models via implicitly manipulating differential properties. Vertex positions do not have the ability to describe local intrinsic features while differential properties do have. Therefore, DDMs are superior to editing methods that manipulate vertex positions explicitly in the way that geometric details can be well-preserved during processing.The theoretical foundation of our technique is the Poisson equation. In our framework, editing a model can be achieved by modifying its gradient field and boundary condition, and a succeeding reconstruction using the Poisson equation. The motivation of this approach is twofold. First, the gradient is a differential property that can be modified locally. Subsequent reconstruction from the modified gradient can give rise to a global effect which would otherwise require a larger amount of user interaction. Secondly, artifacts introduced during local editing can be removed during reconstruction because least-squares minimization tends to distribute errors uniformly across the function. Therefore, our framework can generate high-quality results with less user interactions.Our framework supports several applications, ranging from deformation, object merging, smoothing to interpolation. The common research problem of these applications is how to effectively transform user interactions into gradient field manipulations as well as modifications of boundary conditions. Comparing with previous methods, results generated by our algorithms have higher quality. For example, under the same user interactions, for scanned models, our deformation results are better than those obtained byfree-form deformation tool WIRE in commercial software Maya? (Confirmed by Karan Singh, the designer of the WIRE algorithm). Another example is key-frames can be significantly reduced with the help of our shape interpolation algorithm, since it can handle the relative rotation between models correctly.Since our technique requires solving a sparse linear system, it can be the bottleneck of our framework. To speed up the computation, we propose a two-level acceleration technique. The first level is based on the Cholesky decomposition. With it, the coefficient matrix is pre-factorized. After that, the Poisson equation can be solved efficiently by back substitution. This scheme makes today's PC can process moderate meshes. The second level is a progressive solver for meshes that are so large that solving Poisson equations defined on them directly will be unaffordable (Too many unknowns may cause the Poisson equation exceeds the memory capability). Firstly, the original mesh is simplified according to user-specified threshold. During simplification, geometric details between successive surface levels are recorded by a set of similarity-invariant coefficients. After the base mesh is deformed, the high-resolution result will be obtained via a series of local Poisson-based reconstruction procedures.Image processing softwares advanced a large step by incorporating the concept of layer. However, arbitrary topology and irregular sampling prevent the application of layer to mesh editing systems. Our powerful technique makes it possible to upgrade the architecture of mesh editing system. Based on differential mesh representation, we propose a novel surface representation and editing system leveraged by geometric layer. Specifically, we present algorithms for surface decomposition, detail encoding, layer attributes manipulation and surface composition. With the help of geometric layers, comprehensive editing tasks can be decomposed into several independent layer-based operations, which makes our editing system flexible and efficient. Finally, we list the major contributions of the dissertation:? We introduce a novel mesh representation based on differential properties and a general mesh processing framework based on this representation.? We propose several mesh processing algorithms, ranging from deformation, object merging, smoothing and shape interpolation, based on gradient field manipulation and the Poisson equation.? We propose a progressive Poisson solver for large meshes, which consists of a novel similarity-invariant detail representation and a local Poisson-based reconstruction algorithm.? We propose a unified mesh representing and editing framework based on geometric layers, and implement a layered-based prototyped editing system.