Copyright © 2005 by the Association for Computing Machinery, Inc. Permission to make digital or hard copies of part or all of this work for personal or classroom use is granted without fee provided that copies are not made or distributed for commercial advantage and that copies bear this notice and the full citation on the first page. Copyrights for components of this work owned by others than ACM must be honored. Abstracting with credit is permitted. To copy otherwise, to republish, to post on servers, or to redistribute to lists, requires prior specific permission and/or a fee. Request permissions from Permissions Dept, ACM Inc., fax +1 (212) 869-0481 or e-mail [email protected]. © 2005 ACM 0730-0301/05/0700-0479 $5.00 Linear Rotation-invariant Coordinates for MeshesYaron Lipman Olga Sorkine David Levin Daniel Cohen-OrTel Aviv University∗AbstractWe introduce a rigid motion invariant mesh representation basedon discrete forms defined on the mesh. The reconstruction of meshgeometry from this representation requires solving two sparse lin-ear systems that arise from the discrete forms: the first system de-fines the relationship between local frames on the mesh, and thesecond encodes the position of the vertices via the local frames. Thereconstructed geometry is unique up to a rigid transformation of themesh. We define surface editing operations by placing user-definedconstraints on the local frames and the vertex positions. These con-straints are incorporated in the two linear reconstruction systems,and their solution produces a deformed surface geometry that pre-serves the local differential properties in the least-squares sense.Linear combination of shapes expressed with our representation en-ables linear shape interpolation that correctly handles rotations. Wedemonstrate the effectiveness of the new representation with vari-ous detail-preserving editing operators and shape morphing.Keywords: rigid-motion invariant shape representation, localframes, mesh editing, shape blending1 IntroductionIn this paper we introduce a rigid motion invariant mesh represen-tation. The new representation describes the surface by its localproperties, while filtering out the global spatial location and orien-tation. The representation consists of two discrete forms defineddirectly on the mesh. Reconstructing mesh geometry from locallydefined quantities is a fundamental mechanism which allows edit-ing a mesh while preserving its local appearance under some globalconstraints or boundary conditions. The focus here is on the localsurface details rather than the spatial embedding.Our mesh representation implicitly defines a local frame at eachvertex, where the discrete forms encode the changes between adja-cent frames. The key point is that the transitions between adjacentframes are expressed in relative coordinates. This relative encodingdoes not contain any global information that depends on the posi-tion and orientation of the mesh. The choice of local frames canbe arbitrary. H owever, we define them analogously to the adaptedframes [O’Neill 1969] or Cartan’s moving frames [Guggenheimer1963; Stoker 1989], that is, such that the third vector in the frametriplet is the normal to the surface. Such a definition enables intu-itive decomposition of the representation into normal and tangentialcomponents.The reconstruction of local frames from the discrete forms is ex-pressed as a sparse linear system of equations. The global surface∗e-mail:{lipmanya|sorkine|levin|dcor}@tau.ac.ilcoordinates are obtained from the local frames by integration, alsoexpressed as a solution of a linear system. We demonstrate that pos-ing additional constraints, guided by interactive manipulation of themesh, defines linear least-squares systems for surface editing. Us-ing advanced numerical solvers allows interactive reconstruction.The main contributions of this paper are:• A rigid-motion invariant mesh representation based on dis-crete forms defined at each vertex.• A linear surface reconstruction scheme that restores the geom-etry from the discrete forms.• An interactive editing mechanism that strives to preserve lo-cal differential properties based on the surface reconstructionmethod.• A linear shape interpolation technique which minimizes elas-tic distortion.1.1 Related workInteractive mesh editing is becoming a prominent field in geomet-ric modeling due to the abundance of surface data in the form ofirregular triangular meshes, originating mainly from 3D scanningdevices. In the past years several mesh editing techniques were in-troduced [Zorin et al. 1997; Kobbelt et al. 1998; Guskov et al. 1999;Lee 1999; Bendels and Klein 2003; Botsch and Kobbelt 2004; Lip-man et al. 2004; Sheffer and Kraevoy 2004; Sorkine et al. 2004; Yuet al. 2004; Zayer et al. 2005]. The main goals of interactive edit-ing tools are an intuitive interface and preservation of surface de-tails. Multiresolution approaches [Zorin et al. 1997; Kobbelt et al.1998; Guskov et al. 1999; Botsch and Kobbelt 2004] enable detail-preserving deformations by decomposing the surface into severalfrequency bands. Roughly speaking, details are defined as the dif-ferences between successive levels in the multiresolution hierarchy,and are encoded with respect to the local frames of the lower level,in a rotation-invariant manner.Some multiresolution techniques [Kobbelt et al. 1998; Botsch andKobbelt 2004] work on a two-band decomposition: the smooth basemesh and the details, encoded in the local frame s of the base mesh.This approach can be viewed as equivalent to the recent meth-ods that work directly on the original mesh [Lipman et al. 2004;Sorkine et al. 2004; Yu et al. 2004]. The latter methods define de-tails in a more implicit way, and do not require explicitly settingthe smooth base level; on the other hand, the local frame orienta-tion then needs to be handled explicitly. These methods strive topreserve certain differential properties, such as the discrete Lapla-cians [Lipman et al. 2004; Sorkine et al. 2004] or the gradientsof the mesh coordinate functions [Yu et al. 2004]. These differ-ential entities are vectors encoded in the global coordinate systemthis time, and therefore the main challenge of these techniques isto correctly modify the local frames to accommodate user-definedconstraints and deformations. This is done by implicitly includinga linearized version of the local frame transforms in the Laplacianfitting formulation [Sorkine et al.