High-Quality, Large-Scale Mesh Deformation Methods

Intensively studied in the field of computer graphics, mesh deformation techniques are widely used in many applications such as geometric modeling, animation, virtual reality, film production and video games. Current research focuses on the controllability, performance and scalability of deformation algorithms, as well as the quality of deformation results. However, existing methods all have their cons in the above aspects, unable to meet the requirements of graphics industry.Based on simple schemes such as interpolation and forward reconstruction, Skeleton Sub-space Deformation (SSD), Free-form Deformation (FFD) and multiresolution deformation tech-niques usually achieve real-time performance, but cannot preserve geometry to the fine details. Detail-preserving mesh deformation methods obtain optimal deformation results via (repeatedly) solving linear equations, which means higher memory complexity, may not handle out-of-core meshes. Using traditional optimization schemes, these methods optimize nonlinear deformation constraints inefficiently, thus do not allow for interactive design of high-quality, large-scale defor-mation of detailed meshes. Finally, the above methods focuses on generating static poses, leaving intricate physical motion details void.This thesis first analyzes the limitations of the numerical methods used in current mesh de-formation techniques, then proposes several novel numerical methods with highly improved con-vergence rate and scalability. Finally, novel deformation approaches are developed based on the proposed numerical methods to generate high-quality, large-scale deformation results with fine geometry and physical details. The main contributions are:Propose cascading optimization scheme, which effectively optimize multiple nonlinear de-formation constraints by creating multiple threads and having each thread optimize one more constraint than its previous thread. Such scheme converges an order of magnitude faster than traditional optimization schemes, and leverages the now widely equipped multi-core proces-sors to achieve real-time performance. Based on such scheme, we propose mesh puppetry, a variational framework for detail-preserving mesh deformation through a set of high-level, intuitive design tools. New poses and animations are created by specifying a few desired con- straints on either vertex positions, balance of the character, length and rigidity preservation, or joint limits, inducing pleasing and realistic poses.Present dynamic skinning, an approach to enrich skeleton-driven animations with physically-based secondary deformation in real time. To achieve this goal, a novel, surface-based de-formable model is proposed to interactively emulate the dynamics of both low-and high-frequency volumetric effects. Waterfall optimization scheme is proposed to a set of motion parameters of the material from a surface mesh and a few sample sequences of its physical behavior, as an alternative to tuning the parameters manually. Compared to traditional op-timization schemes (i.e., Gauss-Newton method), such scheme achieves faster convergence rate by consider only a reasonable amount of frames of the sample sequences, and is com-putationally more efficient when implemented in parallel on multi-core PCs.Present a streaming multigrid solver for solving the Poisson equation defined over gigan-tic meshes. This enables gradient-domain operations(e.g., deformation, editing, merging, smoothing) on out-of-core meshes with irregular connectivity. Taking a streaming mesh and boundary constraints as input, our solver builds a multigrid hierarchy and refines the multi-grid solution progressively by performing all operations as streaming computations. Differ-ent from traditional multigrid methods that have linear memory growth with respect to the number of mesh vertices, our approach achieves a sublinear memory complexity. Our im-plementation handles meshes with 14M vertices using merely 84MB of memory, while an equivalent in-core multigrid implementation fails to fit into 2GB memory space.This work not only provides solid theoretical analysis on numerical methods currently used in mesh deformation, but also presents several novel numerical methods with better convergence rate and scalability. Novel mesh deformation techniques are proposed to perform high-quality, large-scale mesh deformation.