9512.net

甜梦文库

甜梦文库

当前位置：首页 >> >> # Abstract Linear Rotation-invariant Coordinates for Meshes

Linear Rotation-invariant Coordinates for Meshes

Yaron Lipman Olga Sorkine David Levin Tel Aviv University ? Daniel Cohen-Or

Abstract

We introduce a rigid motion invariant mesh representation based on discrete forms de?ned on the mesh. The reconstruction of mesh geometry from this representation requires solving two sparse linear systems that arise from the discrete forms: the ?rst system de?nes the relationship between local frames on the mesh, and the second encodes the position of the vertices via the local frames. The reconstructed geometry is unique up to a rigid transformation of the mesh. We de?ne surface editing operations by placing user-de?ned constraints on the local frames and the vertex positions. These constraints are incorporated in the two linear reconstruction systems, and their solution produces a deformed surface geometry that preserves the local differential properties in the least-squares sense. Linear combination of shapes expressed with our representation enables linear shape interpolation that correctly handles rotations. We demonstrate the effectiveness of the new representation with various detail-preserving editing operators and shape morphing. Keywords: rigid-motion invariant shape representation, local frames, mesh editing, shape blending

coordinates are obtained from the local frames by integration, also expressed as a solution of a linear system. We demonstrate that posing additional constraints, guided by interactive manipulation of the mesh, de?nes linear least-squares systems for surface editing. Using advanced numerical solvers allows interactive reconstruction. The main contributions of this paper are: ? A rigid-motion invariant mesh representation based on discrete forms de?ned at each vertex. ? A linear surface reconstruction scheme that restores the geometry from the discrete forms. ? An interactive editing mechanism that strives to preserve local differential properties based on the surface reconstruction method. ? A linear shape interpolation technique which minimizes elastic distortion.

1.1

Related work

1

Introduction

In this paper we introduce a rigid motion invariant mesh representation. The new representation describes the surface by its local properties, while ?ltering out the global spatial location and orientation. The representation consists of two discrete forms de?ned directly on the mesh. Reconstructing mesh geometry from locally de?ned quantities is a fundamental mechanism which allows editing a mesh while preserving its local appearance under some global constraints or boundary conditions. The focus here is on the local surface details rather than the spatial embedding. Our mesh representation implicitly de?nes a local frame at each vertex, where the discrete forms encode the changes between adjacent frames. The key point is that the transitions between adjacent frames are expressed in relative coordinates. This relative encoding does not contain any global information that depends on the position and orientation of the mesh. The choice of local frames can be arbitrary. However, we de?ne them analogously to the adapted frames [O’Neill 1969] or Cartan’s moving frames [Guggenheimer 1963; Stoker 1989], that is, such that the third vector in the frame triplet is the normal to the surface. Such a de?nition enables intuitive decomposition of the representation into normal and tangential components. The reconstruction of local frames from the discrete forms is expressed as a sparse linear system of equations. The global surface

? e-mail:{lipmanya|sorkine|levin|dcor}@tau.ac.il

Interactive mesh editing is becoming a prominent ?eld in geometric modeling due to the abundance of surface data in the form of irregular triangular meshes, originating mainly from 3D scanning devices. In the past years several mesh editing techniques were introduced [Zorin et al. 1997; Kobbelt et al. 1998; Guskov et al. 1999; Lee 1999; Bendels and Klein 2003; Botsch and Kobbelt 2004; Lipman et al. 2004; Sheffer and Kraevoy 2004; Sorkine et al. 2004; Yu et al. 2004; Zayer et al. 2005]. The main goals of interactive editing tools are an intuitive interface and preservation of surface details. Multiresolution approaches [Zorin et al. 1997; Kobbelt et al. 1998; Guskov et al. 1999; Botsch and Kobbelt 2004] enable detailpreserving deformations by decomposing the surface into several frequency bands. Roughly speaking, details are de?ned as the differences 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 and Kobbelt 2004] work on a two-band decomposition: the smooth base mesh and the details, encoded in the local frames of the base mesh. This approach can be viewed as equivalent to the recent methods that work directly on the original mesh [Lipman et al. 2004; Sorkine et al. 2004; Yu et al. 2004]. The latter methods de?ne details in a more implicit way, and do not require explicitly setting the smooth base level; on the other hand, the local frame orientation then needs to be handled explicitly. These methods strive to preserve certain differential properties, such as the discrete Laplacians [Lipman et al. 2004; Sorkine et al. 2004] or the gradients of the mesh coordinate functions [Yu et al. 2004]. These differential entities are vectors encoded in the global coordinate system this time, and therefore the main challenge of these techniques is to correctly modify the local frames to accommodate user-de?ned constraints and deformations. This is done by implicitly including a linearized version of the local frame transforms in the Laplacian ?tting formulation [Sorkine et al. 2004], by explicitly assigning the local frames by propagating the user-de?ned transformation of the handle [Yu et al. 2004] or heuristically approximating the local rotations [Lipman et al. 2004]. In [Zayer et al. 2005] the transformation of the handle is interpolated over the mesh by using harmonic ?elds,

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 permissions@acm.org. ? 2005 ACM 0730-0301/05/0700- 0479 $5.00

479

de?ned via the same Laplacian operator that is used in the editing operation itself. The inherent problem of the above methods is that the local quantities, which constitute the surface representation, are not rotation invariant, and thus local rotations must be explicitly handled to achieve geometric shape preservation. Sheffer and Kraevoy [2004] represent the mesh by rotation-invariant pyramid coordinates. They achieve intuitive editing results for large deformation constraints, but the reconstruction process is not linear. The surface representation we present is truely rotation-invariant, which avoids the explicit handling of local frame transforms altogether, and the reconstruction is formulated as a sparse linear problem.

i x4

i x3

N

i x ?4 i x ?5

i i x ?2 i x ?1

i ?3 x ?i x

i x2

xi

i x5 i x1

i x ?4

i x ?3

i x ?2 i x ?1

parameter space

i x ?5

embedded manifold

1.2

Overview

Figure 1: The 1-ring setting. Vertices in the parameter domain are ? i . The denoted by xi and the corresponding positions in R3 by x edge towards the kth neighbor of i is xi . Mesh edges in R3 are k ?i denoted by x , and their projection onto the tangent plane by xi k k. We de?ne a piecewise inner product in Ui by assigning each parai metric triangle i k (formed by vertex x and its kth and (k + 1)th neighbors) the standard inner product of its corresponding triangle i i in the tangent plane Ti M . Let ? = ?1 xi k + ?2 xk+1 be a vector in k . Then we de?ne the ?rst discrete form I as:

di ?1

We describe our surface representation in the following section. We then proceed to formulate the surface equations that enable to reconstruct the surface geometry from our representation (Section 3). Mesh manipulation applications (detail-preserving editing and shape blending) are presented in Section 4. Finally, we discuss our method in Section 5 and conclude in Section 6.

I i (·) :

i k k=1

?→ R.

2

Discrete Forms

I i (? ) = = ?, ?

R3

In this section we introduce the ?rst and second discrete forms I and II for meshes. These discrete quantities are invariant to rotation and translation of the mesh and contain enough information to reconstruct the mesh uniquely (up to rotation and translation). Let M = (G, P) be a 2-manifold triangular mesh; G = (V, E , F ) is a graph where V , E , and F are the vertices, edges, and faces, respectively, and P is the geometry associated with each vertex in V . ? i . Note that each vertex and its 1-ring can Vertex i is placed at x be locally parameterized. The valence of a vertex, denoted by di , is the number of edges which emanate from this vertex. The 1-ring neighborhood of each vertex is decomposed into the tangential part, represented by the ?rst discrete form, and the normal part, which is represented by the second discrete form. The method for computing the tangent plane at each vertex should be invariant under rigid transformations of the mesh. In other words, if the mesh is transformed by some rigid transformation, the normal should be transformed by the same transformation. There are several advanced methods for computation of normals, such as [Meek and Walton 2000; Meyer et al. 2002; Cazals and Pouget 2003; Cohen-Steiner and Morvan 2003]. For our application, it is suf?cient to de?ne a vertex normal as the weighted average of the normals of the adjacent triangles, where the weights are proportional to the triangles’ areas. We denote the tangent plane at vertex i by Ti M and its normal by Ni . ? i , we denote by x ?i ?i ?i Given a vertex i positioned at x 1, x 2, . . . , x di the ? i to its neighbors. We denote vectors emanating from the vertex x i ?i by xi k the projection of x k onto the tangent plane Ti M , and by x i and x i in a parameterization U of ? ? and xi the representation of x i k k the 1-ring in the plane, respectively 1 (illustrated in Figure 1). Note that all the following de?nitions and constructions are valid even if the projection of the 1-ring onto Ti M is not injective. If some edge is parallel to the normal at the vertex, one can perturb the normal to avoid this singularity. In practice we have never encountered such a situation.

use a hat (∧) for mesh vertices and edges embedded in R3 and tilde (?) for vertices and edges projected onto the tangent plane.

1 We

i i i = ?1 xi k + ?2 xk+1 , ?1 xk + ?2 xk+1

R3

=

2 i 2 i ?1 gk,k + 2 ?1 ?2 gi k,k+1 + ?2 gk+1,k+1 ,

i i i i i where gi k,k = xk , xk R3 and gk,k+1 = xk , xk+1 R3 . We also denote i i i i i indicates the oriOk := sign det(xk , xk+1 , N ) . The quantity Ok i i i entation of the triplet (xk , xk+1 , N ). 0 Note that I i (·) is a quadratic form in each triangle i k with a C connection between adjacent triangles. Also note that the quantii ties gi k,m and Ok give a full parameterization of the tangent plane. Furthermore, the invariance of the ?rst discrete form to different parameterizations can be easily veri?ed. The ?rst discrete form can be described by the lengths of the projected edges and the signed angles between every two adjacent projected edges.

The ?rst discrete form lacks information in the normal direction of the 1-ring neighborhood of a vertex. We de?ne the second discrete form as a piecewise linear form which is actually the height function of the 1-ring neighborhood of a vertex above the tangent plane: II (·) :

k=1 i Let ? = ?1 xi k + ?2 xk+1 ∈ i ?i II (? ) := ?1 x k, N i R3 i. k i di ?1 i k

?→ R.

Then,

R3 i i + ?2 Lk = ?1 Lk +1 , R3 .

i ?i + ?2 x k+1 , N

i = x i ?i where we introduce the coef?cients Lk k, N

The discrete forms at a vertex de?ne the geometry of its 1-ring neighborhood up to a rigid transformation, as explained in the following lemma. Lemma 2.1. Given the discrete form coef?cients and the orientation bits at vertex i, the 1-ring neighborhood of i is de?ned up to a rigid transformation. Fixing the position of vertex i at some

480

? i ∈ R3 , and ?xing the direction of one edge emanating from point x vertex i (or its projection onto the tangent plane) and the normal Ni , uniquely de?nes all the rest of the 1-ring vertex positions. Proof. Assume w.l.o.g. that we ?x the ?rst edge xi 1 in the tangent plane. Denote by n the unit length vector which is orthogonal to i i Ni and to xi 1 and such that the ordered triplet (x1 , n, N ) forms a right-hand orthogonal basis. Then, ?i x 2 = xi 2, xi 1 xi 1 xi i i 1 ?i + xi 2, n n + x 2, N N = xi 1 ? n + L2 Ni , g11 g22

x ? n k+1

i x ?k+1

i

x ?m k x ?k

i

ni

x ?

i nk

x ?i

=

g12 i x + Oi 1 g11 1

k x ?m+1

ni

where ? = g11 g22 ? g2 12 . ? 3 , ..., x ? di . In the same manner one can compute x Note that the discrete forms are not affected by the choice of the local parameterization because we compute their coef?cients directly from the mesh. However, the parametric de?nition can be used to prove convergence of the discrete forms to continuous differential properties (see [Lipman 2004]). The main strength of these de?nitions is that they allow us to de?ne discrete linear surface equations that represent the mesh by local quantities which are invariant under rigid transformations, as shown in the next section. It should be emphasized that the discrete forms are not scale- or shear-invariant.

Figure 2: Illustration for Theorem 3.1. The vertex notations are in gray and the edge vector notations are black. Proof. Note that equations (1) can be written in the following equivalent way: b1 b2 Nj

j j

= = =

i,2 i i i i Γij,,1 1 + 1 b1 + Γ j,1 b2 + A j,1 N i,2 i i i i Γij,,1 2 b1 + Γ j,2 + 1 b2 + A j,2 N i,2 i i i i Γij,,1 3 b1 + Γ j,3 b2 + A j,3 + 1 N .

(2)

3

Discrete surface equations

We use the de?nitions from Section 2 to introduce a surface representation. We de?ne a discrete frame at vertex i ∈ V as the i i i i triplet (bi 1 , b2 , N ), where b1 ∈ Ti M is a unit vector parallel to x1 , i , such that the triplet bi ∈ T M is a unit vector orthogonal to b i 2 1 i i (bi 1 , b2 , N ) forms a right-hand orthonormal basis. Note that the i choice of the vector x1 is arbitrary. Assume (i, j) ∈ E . We de?ne the difference operator δ on the discrete frame vectors: δ j (bi 1) δ j (bi 2) δ j (Ni ) = = =

j b1 ? bi 1 j b2 ? bi 2 j i

These equations simply encode a discrete frame in the basis of an adjacent discrete frame. Thus, to calculate the coef?cients of the above equations, one should represent the discrete frame at vertex j in the coordinates of the discrete frame at vertex i. For convenience, let us take the discrete frame at vertex i as the coordinate vectors, i i that is, bi 1 = (1, 0, 0), b2 = (0, 1, 0), N = (0, 0, 1). Note that we are not interested to ?nd the actual discrete frame at j in the global coordinate system, but only its representation with respect to the frame at i. Denote the index of the kth neighbor of vertex i by ni k. nik Assume j = ni k . First let us ?nd the normal N . Note that

i i ?i ? nk ? x ? i = xi x k =x k + Lk N .

i

Since

i i ?i ? nk+1 ? x ? i = xi x k+1 + Lk+1 N , k+1 = x

i

we also have i i i i i i i ? nk+1 ? x ? nk = xi x k+1 + Lk+1 N ? xk ? Lk N . ? nk+1 ? x ? nk and x ?i ? x ? nk are the vectors x ? mk and x ? mk+1 Next, note that x i n k for some 1 ≤ m ≤ dni (see Figure 2), so ?nding N reduces to solvk ing the following linear 2 × 2 system: ? mk , Nnk x ? mk+1 , Nnk x

ni

i i i i

ni

ni

N ?N .

Finally, we lay out the discrete surface equations: ? i, j ∈ V s.t. (i, j) ∈ E δ j (bi 1) δ j (bi 2) δ j (N )

i

ni

i

= =

i nk i i xi + Lk k+1 ? xk , N +1 ? Lk i nk Ni , Nnk . ? xi ? Lk k, N

i i

i

Ni , Nnk (3)

i

= = =

i,2 i i i i Γij,,1 1 b1 + Γ j,1 b2 + A j,1 N i,2 i i i i Γij,,1 2 b1 + Γ j,2 b2 + A j,2 N i,2 i i i i Γij,,1 3 b1 + Γ j,3 b2 + A j,3 N .

(1)

The above discrete surface equations encode the difference between adjacent discrete frames corresponding to adjacent vertices of the mesh. The difference is encoded in the discrete frame of one of the vertices. The key observation is that the quantities Γij,,lm and Aij,m can be expressed by the coef?cients of the discrete forms only. Theorem 3.1. The coef?cients Γij,,lm and Aij,m of the discrete surface equations can be expressed by the discrete forms.

The left-hand sides of the above equations are the second discrete nik nik form coef?cients at vertex ni k : Lm and Lm+1 . By writing Eq. 3 in the discrete frame at vertex i we get an under-determined system i for Nnk in that basis. Taking a unit length solution to this system i results in the coordinate vector of Nnk with respect to the discrete frame at vertex i (the choice between the two possible solutions of norm 1 is determined by the orientation bits). Next, since we i i ni ? nk , the normal Nnk and one edge x ? mk , all have the vertex position x expressed in the coordinates of the discrete frame of i, the whole 1-ring of vertex ni k is determined by Lemma 2.1. By the de?nition of the discrete frame, it is set by the 1-ring neighborhood of a vertex and its normal, therefore we have the representation of the discrete frame of ni k in the coordinates of the frame of i.

481

(a)

(b)

(c)

(d)

(e)

Figure 3: Examples of basic editing operations. (a) Rotation of the handle discrete frame. The top curve is the original curve. We constrain the leftmost discrete frame (red) to remain the same and rotate the rightmost discrete frame by 90? . (b) The original circle model. (c) Uniform scaling (×2). (d) Uniform shrink constraint (×0.3). (e) Shear constraint. We constrained the discrete frames and the positions of the brown vertices to remain the same, and placed the editing constraint on the red discrete frames.

(a)

(b)

(c)

(d)

(e)

Figure 4: (a) The original Armadillo model (172974 vertices). (b) Scaling (×3) a few discrete frames on the nose, while ?xing the body. (c) Scaling the same frames by 2.5 while ?xing only the legs. (d–e) Bending the Bunny’s head while ?xing the rear part. Note the preservation of the fur details. The set of equations (1) forms an over-determined sparse linear system. To argue that the discrete forms indeed give rise to a representation of the mesh up to rigid motion, we point out the following two arguments. Theorem 3.2. Given an initial discrete frame at an arbitrary veri0 i0 0 tex i0 , (bi 1 , b2 , N ), such that the triplet is a right-hand orthonormal basis, and given that the ?rst and second discrete forms with the orientation bits are taken from an existing mesh, there exists a unique solution to the set of equations (1) such that vertex i0 has the initial discrete frame, and this unique solution constitutes the original surface discrete frames (rotated to match the initial discrete frame at vertex i0 ). Theorem 3.3. Given the solution to the discrete surface equations, namely, the discrete frames at each vertex, there exists a unique embedding of the vertices of the mesh in R3 up to a translation, such that the resulting mesh has the given discrete forms and discrete frames. In other words, the mesh is uniquely determined, up to translation, by its discrete frames and the coef?cients of its discrete forms. For the proof of Theorem 3.2, note that the existence of a solution is obvious (the original discrete frames of the mesh rotated to ?t the given initial condition). For uniqueness, note that by Eq. 2, ?xing a single discrete frame uniquely de?nes all others. To prove Theorem 3.3, we reconstruct the geometry of the mesh from the original discrete form coef?cients and the discrete frames we got by solving Eq. 1. We construct the following difference equations:

i i i ?i x k = xk + Lk N ,

Since we have the discrete frame at vertex i and the ?rst discrete 1/2 . We also have Ni and thus i i i form, we can ?nd xi 1 as x1 = b1 (g1,1 ) we can ?nd all xi , 2 ≤ k ≤ d (see the proof of Lemma 2.1). Therei k fore the right-hand side of the above equations is known. Next, note ?i ?j ?x ? i where j is the kth neighbor of vertex i. The unthat x k =x ? i , i ∈ V , are the positions we are looking for. Combining knowns x the above with the proof of Lemma 2.1 and Eq. 4, we get:

i i i i i i i i i ? j ?x ? i = xi x k + Lk N = xk , b1 b1 + xk , b2 b2 + Lk N , ?(i, j) ∈ E

(5)

i where the coef?cients xi k , bk are computed from the original discrete forms. These equations obviously have a unique solution which is the original mesh, up to translation. This proves Theorem 3.3.

It should be noted that when the mesh is edited (Section 4), more constraints are added to the surface equations (1) and (5). Although it is clear that the reconstruction will produce a new triangular mesh, it is not guaranteed that self-intersection will not occur. The user can always de?ne an extreme deformation constraint for which self-intersection would be inevitable.

3.1

Mesh representation

i ∈ V, k = 1, . . . , di .

(4)

As proved above, one can represent the mesh (up to rigid transformation) using the ?rst and second discrete form coef?cients with orientation bits. Below we summarize how to construct this representation. Given a mesh in Cartesian coordinates, we orthogonally

482

(a)

(b)

(c)

(d)

Figure 5: Smooth rotation of discrete frames. In (a), the original model is shown; the red part is ?xed and the yellow part serves as a handle. (b) The result of constraining a 90? rotation about the yellow axis on the discrete frames of the handle. (c) The pseudocolor visualizes the gradual change of the discrete frames; the color coding corresponds to the Frobenius norm of the difference between the original discrete frame and the discrete frame after the editing operation. Note that regular shading due to the light source was disabled here, thus the smooth gradient of the Frobenius norm coloring shows that the rotations of the discrete frames vary smoothly on ?at parts of the model as well as on the details. (d) Same rotation applied twice more.

project the edges emanating from each vertex i onto the tangent plane Ti M , which results in the following decomposition:

i i i i i i i ?i ?i ?i ?i x k =x k? x k, N N + x k , N N = xk + Lk N .

4

Mesh editing

The orthogonal component represents the second discrete form, that i = x i ?i is, Lk k , N . The ?rst discrete form is represented by the lengths of the projected edges and angles between adjacent projected edges. This sums to 3di scalars for each vertex: 2di scalars for the ?rst discrete form and di scalars for the second discrete form. These scalars are rigid motion invariant and describe only the differential properties around each vertex. In addition, we need the i , as de?ned in Section 2. orientation bits Ok Note that this differential representation is not intended to be compact. On the contrary, it contains redundant information, since the discrete surface equations (1) form an over-determined system, where at each vertex we hold enough information to reconstruct the mesh in any direction. To reconstruct the mesh given its discrete form coef?cients, an initial discrete frame and a position of one vertex in space: ? Construct the discrete surface equations (1): – For each vertex i and its k-th neighbor ni k: ? Solve Eq. 3 to obtain the normal N nk (Theorem 3.1) in the coordinates of the local frame of i;

i and N nk to ?nd the discrete frame of ? Use x ?k vertex ni k expressed in the frame of vertex i (Lemma 2.1);

i i

Our interactive mesh editing mechanism is based on the surface representation and the reconstruction process of the geometry introduced in Section 3. The editing operation is applied by adding linear constraints to the linear systems de?ned by Eqs. 1 and 5. As described in Section 3, the reconstruction of the geometry of the mesh from the discrete forms consists of two main stages: ? Reconstructing the discrete frames at each vertex by solving the discrete surface equations. ? Reconstructing the geometry at each vertex from the discrete forms and the discrete frames. In the ?rst stage, we solve the discrete surface equations (1), which form an over-determined sparse linear system. The coef?cients of the equations can be computed in two equivalent ways: either as described in Section 3.1 using only the discrete forms, or directly from the original mesh and the vertex normals by Eq. 2. In this case, since the geometry of the original mesh is known, the latter way is somewhat simpler. Editing is applied by constraining more discrete frames and solving in the least-squares sense. When constraining more than one discrete frame, there is no guarantee of an exact solution; hence we aim at obtaining the mesh which is as close as possible to satisfying the prescribed differential relations between the discrete frames under the posed conditions. Theorem 3.2 guarantees a unique solution given an initial discrete frame at some vertex, hence, the corresponding system in (1) with the added initial condition has full rank, and thus there exists a unique least-squares solution to the over-determined editing system. In the second stage, some spatial constraints on the geometry are added to Eq. 5, and the system is solved to reconstruct the mesh geometry. As before, Theorem 3.3 guarantees a unique least-squares solution of the system with the added spatial conditions. In our interactive editing system, we adopt the modeling metaphor established in previous works [Kobbelt et al. 1998; Botsch and Kobbelt 2004; Sorkine et al. 2004; Yu et al. 2004]. Namely, the user de?nes a region of interest (ROI) and a handle, which is some subset of the ROI vertices. The editing is performed by manipulating the handle and reconstructing the surface by applying the new constraints. The discrete frames and the positions of the vertices on the boundary of the ROI are constrained to remain the same, and surface reconstruction is performed on the ROI only, leaving the rest of the mesh unchanged. For speedup, the sparse matrices involved in the reconstruction are factored once per ROI (using sparse Cholesky decomposition [Toledo 2003]), and each time the constraints on the handle change, only an update of the right-hand side of the system and a solution by back-substitution is needed. Note

? Extract the coef?cients of Eq. 1 for i and j = ni k. ? Add the given initial discrete frame as an additional equation; ? Solve the augmented linear system in the least-squares sense to obtain the discrete frames; ? Construct the geometry difference equations (5): – Use the discrete frames obtained above and the original discrete forms to calculate the right-hand side of Eq. 5; ? Add the given initial vertex position as an additional equation; ? Solve the augmented linear system in the least-squares sense to get the positions of the vertices. In the next section, we describe an editing mechanism that uses the above steps.

483

(a)

(b)

(c)

Figure 6: Examples of editing operators. (a) The original Armadillo model. (b) rotation operator applied to the knee. The red region denotes the free vertices; the vertices of the foot are used as the handle. The close-ups show the details around the knee from an additional angle. Note that the details are well-preserved after the rotation. (c) Combination of several edits.

(a)

(b)

(c)

(d)

(e)

(f)

Figure 7: Comparison of our editing method to Poisson Editing and Laplacian Editing. The original Cactus model is shown in (a). The result of editing with our method is displayed in (b), where the red spheres mark the static anchors and the yellow spheres mark the handle vertices. (c) The “strength ?eld” resulting from marking a handle curve in the Poisson Editing application. Red denotes maximum and blue denotes minimum values. (d) The result achieved with Poisson Editing when rotating and translating the handle in approximately the same manner as in (b). Note that since the strength ?eld is weaker at the branches (which are geodesically far from the handle), the branches do not receive the same amount of rotation as the trunk. To compare to Laplacian Editing, we deformed the arm of the Octopus (the original surface is rendered in yellow). (e) shows the result of Laplacian Editing, whereas (f) is our result. It is evident that our new method handles large rotations better.

that we always use the original discrete forms of the mesh given the ROI, and thus the system matrices remain ?xed. Our editing application enables the user to edit ROIs containing tens of thousands of vertices at interactive frame rates. Different constraints on the handle result in various editing effects. The basic operation is a linear transformation A on the discrete frames of the handle. This can be done by manipulating an arcballlike control. For all the handle’s vertices i we add the following constraints to the system: bi l N

i

ures 4(d–e), 6, 9, 13, where it can be seen that the details are preserved under the editing operations, including sharp features. The above examples contain transformation constraints on the local frames as well as translation constraints on the vertex positions. We apply the same transformation A and the same translation to all vertices of the handle. It should be noted that extreme rotation constraints (e.g., by 180 degrees) on the discrete frames may cause unintuitive results. However, less ambiguous rotation constraints can be easily performed; see Figure 10, where the top of the bar is rotated by 170 degrees. Note that the solution of the augmented system for the discrete frames does not guarantee that the resulting discrete frames will be orthonormal triplets. On the contrary, with scaling and shearing editing operations A, the system produces scaled and sheared frames. When A is orthogonal, the frames tend to stay orthonormal in practice. In this case, it is possible to normalize each frame vector of the solution. It is important to mention that the orthogonality of the discrete frames is not a necessary condition for the discrete surface equations framework to work. We compare the capabilities of our editing mechanism to other recent approaches in Figure 7. The Poisson editing system, proposed by Yu et al. [2004], propagates the transformation of the handle to the rest of the ROI using geodesic distances as weights. As a result, protruding features that are “far” from the handle get less

= =

? i ), A(b l ? A(Ni ),

l = 1, 2

?i ,b ?i ? i where (b 1 2 , N ) denotes the discrete frame of vertex i in the original mesh. A simple example is shown in Figure 5, where A is a rotation. In 5(b) one can see that the surface bends according to the rotation of the handle, and the details are preserved and maintain their relative orientation with respect to the surface. This happens because our surface representation is rotation-invariant, and thus the local frames of the ROI are rotated in the reconstruction. Figures 3 and 4(a–c) show other types of transformations A: uniform scale and shear. In all these cases the reconstruction process preserves the differential representation as much as possible under the constraints. More examples are shown in Fig-

484

Figure 8: The positional constraints on the vertices and the transformation constraints on the local frames need to be compatible. The left image shows the result of compatible constraints, where the local frames are ?rst appropriately rotated and then the handle is translated (the original mesh is shown in light yellow). The right image shows incompatible constraints: the handle is only translated. As a result, the local frames are not rotated appropriately and the deformation looks less natural.

Figure 10: Example of extreme rotation. Left: the handle (in yellow) is rotated by 170? . The red vertices mark the static constraints. Right: rotation by 315? performed in three steps.

possible to the original surface curvatures. Indeed, in the smooth case, if we consider a frame ?eld {(b1 , b2 , N)}, where N is the surface normal, a curve on the surface with arc-length parameter s yields the following equations [Guggenheimer 1963]: ? ? ? ?? ? kg kn b1 d ?b1 ? ? 0 = ?kg tr ? ?b2 ? , 0 b2 ds

N ?kn ?tr 0 N

Figure 9: Rotating the top vertices on the bar while ?xing the bottom; then bending the top. The editing preserves the sharp edges.

where kg is the geodesic curvature, kn is the normal curvature and tr is the relative torsion. In our discrete case, the coef?cients of the surface equations (1) approximate the curvature quantities, as in the matrix above. This can be shown by dividing both sides of Eq. 1 by the length of the corresponding edges. Hence, when the deformation constraint A does not change the edge lengths (when A is orthogonal), minimizing the difference between the coef?cients in Eq. 1 approximately minimizes the curvature differences between the original and the edited mesh. Of course, when A is strongly distorting the edge lengths, the curvature error is large, which is unavoidable in this case.

rotation, and the editing result might look unnatural. Observe the Cactus model in Figure 7(a–d), where the tips of the branches are further from the handle than their bases, which causes the branches to almost stay in place when the handle is rotated. In contrast, our rotation-invariant representation yields a plausible editing result, naturally rotating the branches. The Laplacian editing approach [Sorkine et al. 2004] handles local rotations in an implicit manner in the same system that solves for the vertex positions. However, to pose the editing in a linear way, 3D rotations must be linearized. This causes errors when the required rotation of the handle is large. See Figure 7(e–f), where a large rotation of the Octopus arm looks smooth with our approach, whereas the Laplacian editing result is “broken” into several parts of smaller rotation. An important observation is that the linear transformation constraints are added to the discrete surface equations (1), while the positional constraints are added to the system (5), so that actually, the discrete frames are determined before the positional constraints are considered. The positional and the linear transformation constraints of the handle should be compatible. Figure 8 shows an example of compatible constraints and incompatible ones. In future work, we would like to consider solving the two sets of equations again to obtain a better correspondence between the linear and the positional constraints. In addition, it would be interesting to infer the transformation of the discrete frames from the translational movement of the handle. By solving the augmented surface equations in the least-squares sense, we minimize the differences between the coef?cients in the discrete surface equations (1) of the original mesh and the corresponding coef?cients of the edited mesh. We argue that such a solution strives to keep the curvatures of the edited mesh as close as

4.1

Shape interpolation

Our rigid-motion invariant surface representation is readily suitable for interpolation between different shapes. It has been shown that a proper shape interpolation should minimize redundant distortions, or in other words, that it should be as rigid as possible [Cohen-Or et al. 1998; Alexa et al. 2000]. This can be achieved by applying a rigid-elastic decomposition to the transformation. The elastic component is de?ned as the residual of applying the rigid transformation ?rst. Such decomposition minimizes the elastic component, and consequently, the redundant distortion. This effect comes for free with rigid-motion invariant representation, since the rigid part is factored out. Assume M1 and M2 are two meshes with identical connectivity and different geometries, where the geometries are represented by the discrete forms. Simple linear interpolation between the discrete forms coef?cients of M1 and M2 yields the “as-rigid-as-possible” effect. To preserve the property that the sum of angles in the tangent plane around each vertex is 2π , we interpolate the angles themselves, rather than their cosines (g12 ). Our method can be regarded as a generalization of the 2D interpolation technique of [Sederberg et al. 1993], which interpolates the edge lengths and the angles between consecutive edges of polygonal curves. Examples of such shape interpolation are demonstrated in Figures 11 and 12, where we show a number of intermediate shapes for different parameters t . It is evident that linear interpolation between our rigid-invariant representations yields intuitive rotations of the source shape towards the target shape, whereas, for comparison, the linear interpolation clearly does not accommodate local rotations. Note that linear interpolation of relative coordinates, such as the

485

source

t = 0.2

t = 0.4

t = 0.6

t = 0.8

target

Figure 11: Linear shape interpolation sequence of the Bar mesh (1600 vertices) using our representation. Note the natural rotation of the in-between shapes.

source

t = 0.2

t = 0.4

t = 0.6

t = 0.8

target

Figure 12: Shape interpolation sequence of the Camel mesh, 39074 vertices. The top row shows the results of linear interpolation of the discrete forms, and the bottom row shows linear interpolation of the Cartesian coordinates. Clearly, the interpolation using our rigid motion invariant shape representation (top row) yields natural rotations of the in-between shapes.

Laplacian coordinates [Alexa 2003; Sorkine et al. 2004], does not yield different results, since the coordinates are linearly dependent on the Cartesian coordinates. Furthermore, our shape interpolation does not involve any non-linear optimizations, neither in the interpolation nor in the reconstruction. We believe that our results have the same quality as the advanced morphing methods, such as [Alexa et al. 2000; Xu et al. 2005], where the ?rst requires meshing the interior of the model, and the second involves non-linear interpolation of the Poisson mesh representation.

6

Conclusions

We have presented a discrete framework on triangular meshes that furnishes a rigid motion invariant representation of the mesh. We obtain a linear surface reconstruction method by taking two steps: ?rst, solving for the local frames of the surface, and then solving for the positions of the vertices. The reconstructed mesh can be regarded as the natural global shape de?ned by local descriptors de?ned at each vertex. Our framework enables detail-preserving surface editing and shape interpolation. In future work, it might be interesting to experiment with other interactive tools that directly manipulate the local frames on the surface. We would also like to improve the co-existence of constraints on the local frames and the vertex positions, as mentioned in Section 4. Another interesting application could be to use our representation for detail editing, such as detail enhancement and other modi?cations.

5

Discussion

The mesh representation presented in the previous sections has an interesting link to classical differential geometry in the following sense. Classical differential geometry de?nes two quadratic forms on the surface, that is, the ?rst and second fundamental forms, which locally describe the tangential and normal components of the surface. Combining these two forms furnishes a good local approximation of the surface. Furthermore, Bonnet theorem ensures that locally, the surface can be reconstructed given the fundamental forms which hold some compatibility conditions (Gauss-CodazziMainardi equations, see [Stoker 1989]). The Bonnet theorem is constructive and consists of two stages: ?rst, a ?rst-order linear PDE describing the changes of the local Frenet frames on the surface is solved, and second, the frames are integrated, which leads to a parameterization of the surface. Our algorithm has a very similar concept: we also write a linear system which describes the changes of the local frames and then “integrate” the changes to solve for the geometry. The reason we use a least-squares solution instead of incrementally “growing” a solution from an initial frame is that the latter approach equally distributes the error across the mesh.

Acknowledgements

We are grateful to Alon Lerner for helping with the video, to Kun Zhou for providing the Poisson Editing software, to Andrew Nealen for proofreading and to Gershon Elber and Leif Kobbelt for their valuable comments and suggestions. The Bunny and Armadillo are courtesy of of Stanford University, the Octopus is courtesy of Mark Pauly. This work was supported in part by grants from the Israel Science Foundation (founded by the Israel Academy of Sciences and Humanities) and the Israeli Ministry of Science.

486

¨ L IPMAN , Y., S ORKINE , O., C OHEN -O R , D., L EVIN , D., R OSSL , C., AND S EIDEL , H.-P. 2004. Differential coordinates for interactive mesh editing. In Proceedings of Shape Modeling International, IEEE Computer Society Press, 181–190. L IPMAN , Y. 2004. Differential geometry of piecewise-linear surfaces. Tech. rep., Tel Aviv University, December. M EEK , D. S., AND WALTON , D. J. 2000. On surface normal and Gaussian curvature approximations given data sampled from a smooth surface. Computer Aided Geometric Design 17, 6, 521– 543. ¨ M EYER , M., D ESBRUN , M., S CHR ODER , P., AND BARR , A. H. 2002. Discrete differential-geometry operators for triangulated 2-manifolds. In Proceedings of VisMath. O’N EILL , B. 1969. Elementary Differential Geometry. Academic Press, New York. S EDERBERG , T. W., G AO , P., WANG , G., AND M U , H. 1993. 2-D shape blending: an intrinsic solution to the vertex path problem. In Proceedings of ACM SIGGRAPH 93, 15–18. S HEFFER , A., AND K RAEVOY, V. 2004. Pyramid coordinates for morphing and deformation. In Proceedings of 2nd International Symposium on 3D Data Processing, Visualization, and Transmission, IEEE Computer Society Press, 68–75. S ORKINE , O., L IPMAN , Y., C OHEN -O R , D., A LEXA , M., ¨ R OSSL , C., AND S EIDEL , H.-P. 2004. Laplacian surface editing. In Proceedings of the Eurographics/ACM SIGGRAPH Symposium on Geometry Processing, Eurographics Association, 179–188. S TOKER , J. J. 1989. Differential Geometry. Wiley, New York. T OLEDO , S. 2003. TAUCS: A Library of Sparse Linear Solvers, version 2.2. Tel-Aviv University, Available online at http://www.tau.ac.il/?stoledo/taucs/, Sept. X U , D., Z HANG , H., WANG , Q., AND BAO , H. 2005. Poisson shape interpolation. In ACM Symposium on Solid and Physical Modeling, to appear. Y U , Y., Z HOU , K., X U , D., S HI , X., BAO , H., G UO , B., AND S HUM , H.-Y. 2004. Mesh editing with Poisson-based gradient ?eld manipulation. In Proceedings of ACM SIGGRAPH 2004, ACM Press, 641–648. ¨ Z AYER , R., R OSSL , C., K ARNI , Z., AND S EIDEL , H.-P. 2005. Harmonic guidance for surface deformation. In Computer Graphics Forum, Proceedings of Eurographics 2005, to appear. ¨ Z ORIN , D., S CHR ODER , P., AND S WELDENS , W. 1997. Interactive multiresolution mesh editing. In Proceedings of ACM SIGGRAPH 97, ACM Press/Addison-Wesley Publishing Co., 259– 268.

Figure 13: Another example of interactive editing. We folded the Gargoyle’s wings and bent its head.

References

A LEXA , M., C OHEN -O R , D., AND L EVIN , D. 2000. Asrigid-as-possible shape interpolation. In Proceedings of ACM SIGGRAPH 2000, ACM Press/Addison-Wesley Publishing Co., 157–164. A LEXA , M. 2003. Differential coordinates for local mesh morphing and deformation. The Visual Computer 19, 2, 105–114. B ENDELS , G. H., AND K LEIN , R. 2003. Mesh forging: editing of 3D-meshes using implicitly de?ned occluders. In Proceedings of the Eurographics/ACM SIGGRAPH Symposium on Geometry Processing, Eurographics Association, 207–217. B OTSCH , M., AND KOBBELT, L. 2004. An intuitive framework for real-time freeform modeling. In Proceedings of ACM SIGGRAPH 2004, ACM Press, 630–634. C AZALS , F., AND P OUGET, M. 2003. Estimating differential quantities using polynomial ?tting of osculating jets. In Proceedings of the Eurographics/ACM SIGGRAPH Symposium on Geometry Processing, Eurographics Association, 177–187. C OHEN -O R , D., L EVIN , D., AND S OLOMOVICI , A. 1998. Threedimensional distance ?eld metamorphosis. ACM Trans. Graph. 17, 2, 116–141. C OHEN -S TEINER , D., AND M ORVAN , J.-M. 2003. Restricted delaunay triangulations and normal cycle. In Proceedings of the 19th annual symposium on computational geometry, ACM Press, 312–321. G UGGENHEIMER , H. 1963. Differential Geometry. McGraw–Hill, New York. ¨ G USKOV, I., S WELDENS , W., AND S CHR ODER , P. 1999. Multiresolution signal processing for meshes. In Proceedings of ACM SIGGRAPH 99, ACM Press/Addison-Wesley Publishing Co., 325–334. KOBBELT, L., C AMPAGNA , S., VORSATZ , J., AND S EIDEL , H.-P. 1998. Interactive multi-resolution modeling on arbitrary meshes. In Proceedings of ACM SIGGRAPH 98, ACM Press, 105–114. L EE , S. 1999. Interactive multiresolution editing of arbitrary meshes. Computer Graphics Forum (Proceedings of Eurographics 1999) 18, 3, 73–82.

487

赞助商链接

- Mean value coordinates for closed triangular meshes
- Recent advances in compression of 3D meshes
- Mean value coordinates for arbitrary planar polygons
- Motion synthesis from annotations
- Adaptively sampled distance fields A general representation of shape for computer graphics
- Vector boosting for rotation invariant multi-view face detection
- An FFT-based technique for translation, rotation, and scale-invariant image registration
- Translation, scale, and rotation invariant texture descriptor for texture-based image retrieval
- Rotation invariant constitutive relation for Reynolds stress structure parameter
- Completed Local Binary Count for Rotation Invariant Texture Classification
- A translation, rotation and scale invariant transform for grey scale images a parallel impl
- Session F4E A MATLAB GRAPHICAL USER INTERFACE FOR LINEAR QUADRATIC CONTROL DESIGN Abstract
- Dimensional perturbation theory for vibration-rotation spectra of linear triatomic molecule
- Scale-Rotation Invariant Pattern Entropy for Keypoint-Based Near-Duplicate Detection
- ABSTRACT Efficient Model Selection for Regularized Linear Discriminant Analysis

更多相关文章：
更多相关标签：