Concepts and Algorithms for the Deformation, Analysis, andCompression of Digital Shapes

Abstract

We propose new model reduction techniques for the construction of reducedshape spaces of deformable objects and for the approximation ofreduced internal forces that accelerate the construction of a reduced dynamicalsystem, increase the accuracy of the approximation, and simplifythe implementation of model reduction. Based on the model reduction techniques, we propose frameworks fordeformation-based modeling and simulation of deformable objects thatare interactive, robust and intuitive to use. We devise efficient numericalmethods to solve the inherent nonlinear problems that are tailored tothe reduced systems. We demonstrate the effectiveness in different experimentswith elastic solids and shells and compare them to alternativeapproaches to illustrate the high performance of the frameworks. We study the spectra and eigenfunctions of discrete differential operatorsthat can serve as an alternative to the discrete Laplacians for applicationsin shape analysis. In particular, we construct such operators asthe Hessians of deformation energies, which are in consequence sensitiveto the extrinsic curvature, e.g., sharp bends. Based on the spectraand eigenmodes, we derive the vibration signature that can be used tomeasure the similarity of points on a surface. By taking advantage of structural regularities inherent to adaptive multiresolutionmeshes, we devise a lossless connectivity compression thatexceeds state-of-the-art coders by a factor of two to seven. In addition,we provide extensions to sequences of meshes with varying refinementthat reduce the entropy even further. Using improved context modelingto enhance the zerotree coding of wavelet coefficients, we achieve compressionfactors that are four times smaller than those of leading codersfor irregular meshes.