As-Rigid-As-Possible Deformation

As-Rigid-As-Possible

Surface Modeling

Wanho Choi

(wanochoi.com)

Olga Sorkine and Marc Alexa TU Berlin, Germany

Abstract

Modeling tasks, such as surface deformation and editing, can be analyzed by observing the local behavior of the surface. We argue that defining a modeling operation by asking for rigidity of the local transformations is useful in various settings. Such formulation leads to a non-linear, yet conceptually simple energy formulation, which is to be minimized by the deformed surface under particular modeling constraints. We devise a simple iterative mesh editing scheme based on this principle, that leads to detail-preserving and intuitive deformations. Our algorithm is effective and notably easy to implement, making it attractive for practical modeling applications.

Categories and Subject Descriptors(according to ACM CCS): I.3.5 [Computer Graphics]: Computational Geometry and Object Modeling – geometric algorithms, languages, and systems

1. Introduction

When we talk about shape, we usually refer to a property that does not change with the orientation or position of an object. In that sense, preserving shape means that an object is only rotated or translated, but not scaled or sheared. In the context of interactive shape modeling it is clear, how-ever, that a shape has to to be stretched or sheared to satisfy the modeling constraints placed by the user. Users intuitively expect the deformation to preserve the shape of the object locally, as happens with physical objects when a smooth, large-scale deformation is applied to them. In other words, small parts of the shape should change as rigidly as possible. Our goal is to create a shape deformation framework that is directly based upon the above principle. When local sur-face deformations induced by modeling operations are close to rigid, surface details tend to be preserved. This is a highly important property for surface editing schemes that are meant to be applied to complex, detailed surfaces, such as those coming from scanning real 3D objects or from sophis-ticated virtual sculpting tools. Recently, detail-preserving surface editing techniques have been receiving much atten-tion in geometric modeling research [Sor06,BS07], thanks to the increasing proliferation of such detailed models, which usually come in the form of irregular polygonal meshes.

We propose the following conceptual model derived from the principle of local rigidity: The surface of the object is covered with small overlapping cells. An ideal deformation seeks to keep the transformation for the surface in each cell as rigid as possible. Overlap of the cells is necessary to avoid surface stretching or shearing at the boundary of the cells.

Figure 1: Large deformation obtained by translating a single vertex constraint (in yellow) using our as-rigid-as-possible technique.

For this modeling framework to become practical we shall define how rigidity is measured in each of the cells. A nat-ural choice is to estimate the rigid transformation for each cell based on corresponding points on the initial and the de-formed surfaces, then apply this rigid transformation to the original shape and measure the deviation to the deformed shape. Note that estimating a linear transformation from the corresponding surface points and then measuring its non-orthogonality is not a good measure of rigidity: an optimal approximate linear transformation of an arbitrary deforma-tion could well be orthogonal. Consequently, in order to de-fine locally shape-preserving deformation, a direct optimiza-tion of the rigid transformaoptimiza-tion should be performed instead. Assuming we can measure deviation from rigidity in each cell, setting up the modeling framework requires deciding on the size and placement (or, equivalently, overlap) of

deformation

S: initial triangle mesh (given input mesh)

′

S : deformed mesh (output mesh to be computed)

n: # of vertices

p_i: the i-th vertex position of S ′

p_i: the i-th vertex position of S′

n: # of vertices

p_i: the i-th vertex position of S ′

p_i: the i-th vertex position of S′

N_i: one-ring neighbor vertices of the vertex i

if S → ′S : rigid transformation, there exists a 3× 3 rotation matrix R_i per each vertex such that ′

S: initial triangle mesh (given input mesh)

′

S : deformed mesh (output mesh to be computed)

n: # of vertices

p_i: the i-th vertex position of S ′

p_i: the i-th vertex position of S′

N_i: one-ring neighbor vertices of the vertex i

if S → ′S : rigid transformation, there exists a 3× 3 rotation matrix R_i per each vertex such that ′

p_i − ′p_j = R_i

(

p_i − p_j

)

, ∀j ∈N_i

when the deformation is not rigid, we can still find the best approximating rotation R_i such that

E_i = w_ij

(

p′_i − ′p_j

)

− R_i

(

p_i − p_j

)

2

j∈N_i

∑

: the score (or energy) indicating how much difference between them to be minimized

n: # of vertices

p_i: the i-th vertex position of S ′

p_i: the i-th vertex position of S′

N_i: one-ring neighbor vertices of the vertex i

if S → ′S : rigid transformation, there exists a 3× 3 rotation matrix R_i per each vertex such that ′

p_i − ′p_j = R_i

(

p_i − p_j

)

, ∀j ∈N_i

when the deformation is not rigid, we can still find the best approximating rotation R_i such that

E_i = w_ij

(

p′_i − ′p_j

)

− R_i

(

p_i − p_j

)

2

j∈N_i

∑

: the score (or energy) indicating how much difference between them

let e_ij = p_i − p_j & e′_ij = ′p_i − ′p_j

(

)

= w_ij e_ij′ − R_ie_ij 2

j∈N_i

E_i = w_ij e_ij′ − R_ie_ij 2

j∈N_i

E_i = w_ij e_ij′ − R_ie_ij 2 j∈N_i

∑

p_i p α β w_ij

p α β w_ij w_ij = 1 2

(

cotα + cotβ

)

= wji

E_i = w_ij e_ij′ − R_ie_ij 2 j∈N_i

∑

p_i p α β w_ij w_ij = 1 2

(

cotα + cotβ

)

= wji

p α β w_ij w_ij = 1 2

(

cotα + cotβ

)

= wji

: cotangent edge weight [Pinkall and Polthier 1993] ⇒ discrete Laplace-Beltrami operator

E_i = w_ij e_ij′ − R_ie_ij 2 j∈N_i

∑

p_i p_j α β wij = 1 2

(

cotα + cotβ

)

= wji

: cotangent edge weight [Pinkall and Polthier 1993] ⇒ discrete Laplace-Beltrami operator

[Jacobson and Sorkine 2012]

w_ij

E_i = w_ij e_ij′ − R_ie_ij 2 j∈N_i

∑

= w_ij

(

e_ij′ − R_ie_ij

)

T

(

e_ij′ − R_ie_ij

)

j∈N_i

∑

∵p⋅p = pTp = p 2

= w_ij

(

e_ij′ − R_ie_ij

)

(

e_ij′ − R_ie_ij

)

j∈N_i

∑

= w_ij

(

e_ij′T − e_ijTR_iT

)

(

e′_ij − R_ie_ij

)

∈N

∑

∵p⋅p = p p = p ∵(AB)T = BT AT

E_i = w_ij e_ij′ − R_ie_ij 2 j∈N_i

∑

= w_ij

(

e_ij′ − R_ie_ij

)

T

(

e_ij′ − R_ie_ij

)

j∈N_i

∑

= w_ij

(

e_ij′T − e_ijTR_iT

)

(

e′_ij − R_ie_ij

)

j∈N_i

∑

= w_ij

(

e_ij′Te_ij′ − ′e_ijTR_ie_ij − e_ijTR_iTe_ij′ + e_ijTR_iTR_ie_ij

)

∈N

∑

∵p⋅p = pTp = p 2 ∵(AB)T = BT AT ∵(aT + bT )(a+ b) = aTa+ aTb+ bTa+ bTb

= w_ij

(

e_ij′ − R_ie_ij

)

(

e_ij′ − R_ie_ij

)

j∈N_i

∑

= w_ij

(

e_ij′T − e_ijTR_iT

)

(

e′_ij − R_ie_ij

)

j∈N_i

∑

= w_ij

(

e_ij′Te_ij′ − ′e_ijTR_ie_ij − e_ijTR_iTe_ij′ + e_ijTR_iTR_ie_ij

)

j∈N_i

∑

= w_ij

(

e_ij′Te_ij′ − 2 ′e_ijTR_ie_ij + e_ijTR_iTR_ie_ij

)

∈N

∑

∵pT Aq= p

(

TAq

)

T = qTATp ∵p⋅p = p p = p ∵(AB)T = BT AT ∵(aT + bT )(a+ b) = aTa+ aTb+ bTa+ bTb : scalar

E_i = w_ij e_ij′ − R_ie_ij 2 j∈N_i

∑

= w_ij

(

e_ij′Te_ij′ − 2 ′e_ijTR_ie_ij + e_ijTe_ij

)

∈N

∑

= w_ij

(

e_ij′ − R_ie_ij

)

T

(

e_ij′ − R_ie_ij

)

j∈N_i

∑

= w_ij

(

e_ij′T − e_ijTR_iT

)

(

e′_ij − R_ie_ij

)

j∈N_i

∑

= w_ij

(

e_ij′Te_ij′ − ′e_ijTR_ie_ij − e_ijTR_iTe_ij′ + e_ijTR_iTR_ie_ij

)

j∈N_i

∑

= w_ij

(

e_ij′Te_ij′ − 2 ′e_ijTR_ie_ij + e_ijTR_iTR_ie_ij

)

j∈N_i

∑

∵pT Aq= p

(

TAq

)

T = qTATp ∵Ri : orthonormal⇒ Ri T R_i = I ∵p⋅p = pTp = p 2 ∵(AB)T = BT AT ∵(aT + bT )(a+ b) = aTa+ aTb+ bTa+ bTb : scalar

∵pT Aq= p

(

TAq

)

T = qTATp ∵Ri : orthonormal⇒ Ri T R_i = I ∵p⋅p = p p = p ∵(AB)T = BT AT ∵(aT + bT )(a+ b) = aTa+ aTb+ bTa+ bTb = w_ij

(

e_ij′Te_ij′ − 2 ′e_ijTR_ie_ij + e_ijTe_ij

)

j∈N_i

∑

= w_ij

(

e_ij′ − R_ie_ij

)

(

e_ij′ − R_ie_ij

)

j∈N_i

∑

= w_ij

(

e_ij′T − e_ijTR_iT

)

(

e′_ij − R_ie_ij

)

j∈N_i

∑

= w_ij

(

e_ij′Te_ij′ − ′e_ijTR_ie_ij − e_ijTR_iTe_ij′ + e_ijTR_iTR_ie_ij

)

j∈N_i

∑

= w_ij

(

e_ij′Te_ij′ − 2 ′e_ijTR_ie_ij + e_ijTR_iTR_ie_ij

)

j∈N_i

∑

∴E

_i

=

w

_ij

(

e

_ij

′

T

e

_ij

′

− 2 ′

e

_ijT

R

_i

e

_ij

+ e

_ijT

e

_ij

)

j∈N

∑

: scalar

E_i = w_ij

(

e_ij′Te_ij′ − 2 ′e_ijTR_ie_ij + e_ijTe_ij

)

j∈N_i

E_i = w_ij

(

e_ij′Te_ij′ − 2 ′e_ijTR_ie_ij + e_ijTe_ij

)

j∈N_i

∑

It is an energy minimization problem! We'd like to get E_i as little as possible.

It is an energy minimization problem! We'd like to get E_i as little as possible.

E_i = w_ij

(

e_ij′Te_ij′ − 2 ′e_ijTR_ie_ij + e_ijTe_ij

)

j∈N_i

∑

argmin R E_i

It is an energy minimization problem! We'd like to get E_i as little as possible.

= argmin R w_ij

(

e_ij′Te_ij′ − 2 ′e_ijTR_ie_ij + e_ijTe_ij

)

∈N

∑

∵Ei = wij e′ij T ′ e_ij − 2 ′e_ijTR_ie_ij + e_ijTe_ij

(

)

j∈N

∑

∵The terms that do not contain Ri

are constant in the minimization and therefore can be dropped.

It is an energy minimization problem! We'd like to get E_i as little as possible.

= argmin R_i w_ij

(

e_ij′Te_ij′ − 2 ′e_ijTR_ie_ij + e_ijTe_ij

)

j∈N_i

∑

= argmin R_i w_ij

(

−2 ′e_ijTR_ie_ij

)

j∈N_i

∑

∵Ei = wij e′ij T ′ e_ij − 2 ′e_ijTR_ie_ij + e_ijTe_ij

(

)

j∈N_i

∑

argmin R_i E_i

∵The terms that do not contain Ri

are constant in the minimization and therefore can be dropped.

E_i = w_ij

(

e_ij′Te_ij′ − 2 ′e_ijTR_ie_ij + e_ijTe_ij

)

j∈N_i

∑

It is an energy minimization problem! We'd like to get E_i as little as possible.

= argmin R_i w_ij

(

e_ij′Te_ij′ − 2 ′e_ijTR_ie_ij + e_ijTe_ij

)

j∈N_i

∑

= argmin R_i w_ij

(

−2 ′e_ijTR_ie_ij

)

j∈N_i

∑

∵Ei = wij e′ij T ′ e_ij − 2 ′e_ijTR_ie_ij + e_ijTe_ij

(

)

j∈N_i

∑

= argmin R −2w_ije_ij′TR_ie_ij

(

)

∈N

∑

∵wij is a scalar argmin R_i E_i

∵The terms that do not contain Ri

are constant in the minimization and therefore can be dropped.

It is an energy minimization problem! We'd like to get E_i as little as possible.

= argmin R_i w_ij

(

e_ij′Te_ij′ − 2 ′e_ijTR_ie_ij + e_ijTe_ij

)

j∈N_i

∑

= argmin R_i w_ij

(

−2 ′e_ijTR_ie_ij

)

j∈N_i

∑

∵Ei = wij e′ij T ′ e_ij − 2 ′e_ijTR_ie_ij + e_ijTe_ij

(

)

j∈N_i

∑

= argmin R_i −2w_ije_ij′TR_ie_ij

(

)

j∈N_i

∑

= argmin R −w_ije′_ijTR_ie_ij

(

)

∈N

∑

∵wij is a scalar ∵min(−2E) = min(−E) argmin R_i E_i

∵The terms that do not contain Ri

are constant in the minimization and therefore can be dropped.

= argmax R w_ije_ij′TR_ie_ij

(

)

∈N

∑

E_i = w_ij

(

e_ij′Te_ij′ − 2 ′e_ijTR_ie_ij + e_ijTe_ij

)

j∈N_i

∑

It is an energy minimization problem! We'd like to get E_i as little as possible.

= argmin R_i w_ij

(

e_ij′Te_ij′ − 2 ′e_ijTR_ie_ij + e_ijTe_ij

)

j∈N_i

∑

= argmin R_i w_ij

(

−2 ′e_ijTR_ie_ij

)

j∈N_i

∑

∵Ei = wij e′ij T ′ e_ij − 2 ′e_ijTR_ie_ij + e_ijTe_ij

(

)

j∈N_i

∑

= argmin R_i −2w_ije_ij′TR_ie_ij

(

)

j∈N_i

∑

= argmin R_i −w_ije′_ijTR_ie_ij

(

)

j∈N_i

∑

∵wij is a scalar ∵min(−2E) = min(−E) ∵min(−E) = max(E) argmin R_i E_i

∵The terms that do not contain Ri

are constant in the minimization and therefore can be dropped.

= argmax R_i w_ije_ij′TR_ie_ij

(

)

j∈N_i

∑

It is an energy minimization problem! We'd like to get E_i as little as possible.

= argmin R_i w_ij

(

e_ij′Te_ij′ − 2 ′e_ijTR_ie_ij + e_ijTe_ij

)

j∈N_i

∑

= argmin R_i w_ij

(

−2 ′e_ijTR_ie_ij

)

j∈N_i

∑

∵Ei = wij e′ij T ′ e_ij − 2 ′e_ijTR_ie_ij + e_ijTe_ij

(

)

j∈N_i

∑

= argmin R_i −2w_ije_ij′TR_ie_ij

(

)

j∈N_i

∑

= argmin R_i −w_ije′_ijTR_ie_ij

(

)

j∈N_i

∑

∵wij is a scalar ∵min(−2E) = min(−E) ∵min(−E) = max(E)

∴our goal: argmax

R_i

w

_ij

e

_ij

′

T

R

_i

e

_ij

(

)

j∈N

∑

argmin R_i E_i

argmax R_i w_ije_ij′TR_ie_ij

(

)

j∈N_i

∑

argmax R_i w_ije_ij′TR_ie_ij

(

)

j∈N_i

∑

= argmax R_i Tr w_ijR_ie_ije_ij′T j∈N_i

∑

⎛ ⎝⎜ ⎞ ⎠⎟ Why e_ij′TR_ie_ij = Tr R

(

_ie_ije_ij′T

)

?

pTAq= ⎡ α_β ⎣ ⎢ ⎢ ⎤ ⎦ ⎥ ⎥ T a b c d ⎡ ⎣ ⎢ ⎤ ⎦ ⎥⎡ γ_δ ⎣ ⎢ ⎢ ⎤ ⎦ ⎥ ⎥= α β ⎡ ⎣ ⎢ ⎢ ⎤ ⎦ ⎥ ⎥ T aγ + bδ cγ + dδ ⎡ ⎣ ⎢ ⎢ ⎤ ⎦ ⎥ ⎥ =α

(

aγ + bδ

)

+β

(

cγ + dδ

)

Why e_ij′TR_ie_ij = Tr R

(

_ie_ije_ij′T

)

?

pTAq= ⎡ α_β ⎣ ⎢ ⎢ ⎤ ⎦ ⎥ ⎥ T a b c d ⎡ ⎣ ⎢ ⎤ ⎦ ⎥⎡ γ_δ ⎣ ⎢ ⎢ ⎤ ⎦ ⎥ ⎥= α β ⎡ ⎣ ⎢ ⎢ ⎤ ⎦ ⎥ ⎥ T aγ + bδ cγ + dδ ⎡ ⎣ ⎢ ⎢ ⎤ ⎦ ⎥ ⎥ =α

(

aγ + bδ

)

+β

(

cγ + dδ

)

AqpT = a b c d ⎡ ⎣ ⎢ ⎤ ⎦ ⎥⎡ γ_δ ⎣ ⎢ ⎢ ⎤ ⎦ ⎥ ⎥ α β ⎡ ⎣ ⎢ ⎢ ⎤ ⎦ ⎥ ⎥ T = a b c d ⎡ ⎣ ⎢ ⎤ ⎦ ⎥⎡ γ_δ ⎣ ⎢ ⎢ ⎤ ⎦ ⎥ ⎥⎡⎣ α β ⎤⎦ = a b c d ⎡ ⎣ ⎢ ⎤ ⎦ ⎥⎡ α_{αδ βδ}γ βγ ⎣ ⎢ ⎢ ⎤ ⎦ ⎥ ⎥ = a b c d ⎡ ⎣ ⎢ ⎤ ⎦ ⎥⎡ αγ βγ_{αδ βδ} ⎣ ⎢ ⎢ ⎤ ⎦ ⎥ ⎥ = aαγ + bαδ aβγ + bβδ cαγ + dαδ cβγ + dβδ ⎡ ⎣ ⎢ ⎢ ⎤ ⎦ ⎥ ⎥ = α

(

aγ + bδ

)

β

(

aγ + bδ

)

α

(

cγ + dδ

)

β

(

cγ + dδ

)

⎡ ⎣ ⎢ ⎢ ⎤ ⎦ ⎥ ⎥ argmax R_i w_ije_ij′TR_ie_ij

(

)

j∈N_i

∑

= argmax R_i Tr w_ijR_ie_ije_ij′T j∈N_i

∑

⎛ ⎝⎜ ⎞ ⎠⎟ Why e_ij′TR_ie_ij = Tr R

(

_ie_ije_ij′T

)

?

pTAq= ⎡ α_β ⎣ ⎢ ⎢ ⎤ ⎦ ⎥ ⎥ T a b c d ⎡ ⎣ ⎢ ⎤ ⎦ ⎥⎡ γ_δ ⎣ ⎢ ⎢ ⎤ ⎦ ⎥ ⎥= α β ⎡ ⎣ ⎢ ⎢ ⎤ ⎦ ⎥ ⎥ T aγ + bδ cγ + dδ ⎡ ⎣ ⎢ ⎢ ⎤ ⎦ ⎥ ⎥ =α

(

aγ + bδ

)

+β

(

cγ + dδ

)

AqpT = a b c d ⎡ ⎣ ⎢ ⎤ ⎦ ⎥⎡ γ_δ ⎣ ⎢ ⎢ ⎤ ⎦ ⎥ ⎥ α β ⎡ ⎣ ⎢ ⎢ ⎤ ⎦ ⎥ ⎥ T = a b c d ⎡ ⎣ ⎢ ⎤ ⎦ ⎥⎡ γ_δ ⎣ ⎢ ⎢ ⎤ ⎦ ⎥ ⎥⎡⎣ α β ⎤⎦ = a b c d ⎡ ⎣ ⎢ ⎤ ⎦ ⎥⎡ α_{αδ βδ}γ βγ ⎣ ⎢ ⎢ ⎤ ⎦ ⎥ ⎥ = a b c d ⎡ ⎣ ⎢ ⎤ ⎦ ⎥⎡ αγ βγ_{αδ βδ} ⎣ ⎢ ⎢ ⎤ ⎦ ⎥ ⎥ = aαγ + bαδ aβγ + bβδ cαγ + dαδ cβγ + dβδ ⎡ ⎣ ⎢ ⎢ ⎤ ⎦ ⎥ ⎥ = α

(

aγ + bδ

)

β

(

aγ + bδ

)

α

(

cγ + dδ

)

β

(

cγ + dδ

)

⎡ ⎣ ⎢ ⎢ ⎤ ⎦ ⎥ ⎥ Tr Aqp

(

T

)

=α

(

aγ + bδ

)

+β

(

cγ + dδ

)

Why e_ij′TR_ie_ij = Tr R

(

_ie_ije_ij′T

)

?

pTAq= ⎡ α_β ⎣ ⎢ ⎢ ⎤ ⎦ ⎥ ⎥ T a b c d ⎡ ⎣ ⎢ ⎤ ⎦ ⎥⎡ γ_δ ⎣ ⎢ ⎢ ⎤ ⎦ ⎥ ⎥= α β ⎡ ⎣ ⎢ ⎢ ⎤ ⎦ ⎥ ⎥ T aγ + bδ cγ + dδ ⎡ ⎣ ⎢ ⎢ ⎤ ⎦ ⎥ ⎥ =α

(

aγ + bδ

)

+β

(

cγ + dδ

)

AqpT = a b c d ⎡ ⎣ ⎢ ⎤ ⎦ ⎥⎡ γ_δ ⎣ ⎢ ⎢ ⎤ ⎦ ⎥ ⎥ α β ⎡ ⎣ ⎢ ⎢ ⎤ ⎦ ⎥ ⎥ T = a b c d ⎡ ⎣ ⎢ ⎤ ⎦ ⎥⎡ γ_δ ⎣ ⎢ ⎢ ⎤ ⎦ ⎥ ⎥⎡⎣ α β ⎤⎦ = a b c d ⎡ ⎣ ⎢ ⎤ ⎦ ⎥⎡ α_{αδ βδ}γ βγ ⎣ ⎢ ⎢ ⎤ ⎦ ⎥ ⎥ = a b c d ⎡ ⎣ ⎢ ⎤ ⎦ ⎥⎡ αγ βγ_{αδ βδ} ⎣ ⎢ ⎢ ⎤ ⎦ ⎥ ⎥ = aαγ + bαδ aβγ + bβδ cαγ + dαδ cβγ + dβδ ⎡ ⎣ ⎢ ⎢ ⎤ ⎦ ⎥ ⎥ = α

(

aγ + bδ

)

β

(

aγ + bδ

)

α

(

cγ + dδ

)

β

(

cγ + dδ

)

⎡ ⎣ ⎢ ⎢ ⎤ ⎦ ⎥ ⎥ ∴pTAq=Tr Aqp

(

T

)

argmax R_i w_ije_ij′TR_ie_ij

(

)

j∈N_i

∑

= argmax R_i Tr w_ijR_ie_ije_ij′T j∈N_i

∑

⎛ ⎝⎜ ⎞ ⎠⎟ Tr Aqp

(

T

)

=α

(

aγ + bδ

)

+β

(

cγ + dδ

)

Why e_ij′TR_ie_ij = Tr R

(

_ie_ije_ij′T

)

?

argmax R_i w_ije_ij′TR_ie_ij

(

)

j∈N_i

∑

= argmax R_i Tr w_ijR_ie_ije_ij′T j∈N_i

∑

⎛ ⎝⎜ ⎞ ⎠⎟ = argmax R_i Tr R_iw_ije_ije_ij′T j∈N_i

∑

⎛ ⎝⎜ ⎞ ⎠⎟ ∵wij : scalar

= argmax R_i Tr R_iw_ije_ije_ij′T j∈N_i

∑

⎛ ⎝⎜ ⎞ ⎠⎟ ∵wij : scalar = argmax R Tr R_i w_ije_ije_ij′T ∈N

∑

⎛ ⎝⎜ ⎞ ⎠⎟ ∵Ri : constant

argmax R_i w_ije_ij′TR_ie_ij

(

)

j∈N_i

∑

= argmax R_i Tr w_ijR_ie_ije_ij′T j∈N_i

∑

⎛ ⎝⎜ ⎞ ⎠⎟ = argmax R_i Tr R_iw_ije_ije_ij′T j∈N_i

∑

⎛ ⎝⎜ ⎞ ⎠⎟ ∵wij : scalar = argmax R_i Tr R_i w_ije_ije_ij′T j∈N_i

∑

⎛ ⎝⎜ ⎞ ⎠⎟ ∵Ri : constant = argmaxTr R

(

_iS_i

)

∵let Si = wijeijeij′ T ∈N

∑

= argmax R_i Tr R_iw_ije_ije_ij′T j∈N_i

∑

⎛ ⎝⎜ ⎞ ⎠⎟ ∵wij : scalar = argmax R_i Tr R_i w_ije_ije_ij′T j∈N_i

∑

⎛ ⎝⎜ ⎞ ⎠⎟ ∵Ri : constant ∵Si =UiΣiVi T : SVD = argmax R_i Tr R

(

_iS_i

)

∵let Si = wijeijeij′ T j∈Ni

∑

= argmaxTr R

(

_iU_iΣ_iV_iT

)

argmax R_i w_ije_ij′TR_ie_ij

(

)

j∈N_i

∑

= argmax R_i Tr w_ijR_ie_ije_ij′T j∈N_i

∑

⎛ ⎝⎜ ⎞ ⎠⎟ = argmax R_i Tr R_iw_ije_ije_ij′T j∈N_i

∑

⎛ ⎝⎜ ⎞ ⎠⎟ ∵wij : scalar = argmax R_i Tr R_i w_ije_ije_ij′T j∈N_i

∑

⎛ ⎝⎜ ⎞ ⎠⎟ ∵Ri : constant ∵Si =UiΣiVi T : SVD = argmax R_i Tr R

(

_iS_i

)

∵let Si = wijeijeij′ T j∈Ni

∑

= argmax R_i Tr R

(

_iU_iΣ_iV_iT

)

= argmaxTr (R

(

_iU_i)(Σ_iV_iT)

)

= argmax R_i Tr R_iw_ije_ije_ij′T j∈N_i

∑

⎛ ⎝⎜ ⎞ ⎠⎟ ∵wij : scalar = argmax R_i Tr R_i w_ije_ije_ij′T j∈N_i

∑

⎛ ⎝⎜ ⎞ ⎠⎟ ∵Ri : constant ∵Si =UiΣiVi T : SVD = argmax R_i Tr R

(

_iS_i

)

∵let Si = wijeijeij′ T j∈Ni

∑

= argmax R_i Tr R

(

_iU_iΣ_iV_iT

)

= argmax R_i Tr (R

(

_iU_i)(Σ_iV_iT)

)

argmax R_i w_ije_ij′TR_ie_ij

(

)

j∈N_i

∑

= argmax R_i Tr w_ijR_ie_ije_ij′T j∈N_i

∑

⎛ ⎝⎜ ⎞ ⎠⎟ = argmax R_i Tr R_iw_ije_ije_ij′T j∈N_i

∑

⎛ ⎝⎜ ⎞ ⎠⎟ ∵wij : scalar = argmax R_i Tr R_i w_ije_ije_ij′T j∈N_i

∑

⎛ ⎝⎜ ⎞ ⎠⎟ ∵Ri : constant ∵Si =UiΣiVi T : SVD = argmax R_i Tr R

(

_iS_i

)

∵let Si = wijeijeij′ T j∈Ni

∑

= argmax R_i Tr R

(

_iU_iΣ_iV_iT

)

= argmax R_i Tr (R

(

_iU_i)(Σ_iV_iT)

)

= argmax R_i Tr (

(

Σ_iV_iT)(R_iU_i)

)

∵tr(AB) = tr(BA) = argmaxTr

(

Σ_iV_iTR_iU_i

)

= argmax R_i Tr R_iw_ije_ije_ij′T j∈N_i

∑

⎛ ⎝⎜ ⎞ ⎠⎟ ∵wij : scalar = argmax R_i Tr R_i w_ije_ije_ij′T j∈N_i

∑

⎛ ⎝⎜ ⎞ ⎠⎟ ∵Ri : constant ∵Si =UiΣiVi T : SVD = argmax R_i Tr R

(

_iS_i

)

∵let Si = wijeijeij′ T j∈Ni

∑

= argmax R_i Tr R

(

_iU_iΣ_iV_iT

)

= argmax R_i Tr (R

(

_iU_i)(Σ_iV_iT)

)

= argmax R_i Tr (

(

Σ_iV_iT)(R_iU_i)

)

∵tr(AB) = tr(BA) = argmax R_i Tr

(

Σ_iV_iTR_iU_i

)

= argmaxTr

(

Σ_iM_i

)

∵let Mi=Vi T R_iU_i

argmax R_i

E_i = argmax

R_i

∵V_iT, R_i, and U_i are all orthonormal matrices

(

)

M_i: orthonormal matrix

∵V_iT, R_i, and U_i are all orthonormal matrices

(

)

M_i: orthonormal matrix

when m_ij is the j-th column vector of M_i ⇒ m_ij 2 = m_ijTm_ij = 1

Σ_iM_i = σ₁ 0 ! 0 0 σ₂ ! 0 ! ! " ! 0 0 ! σ_n ⎡ ⎣ ⎢ ⎢ ⎢ ⎢ ⎢ ⎤ ⎦ ⎥ ⎥ ⎥ ⎥ ⎥ m₁₁ m₁₂ ! m_1n m₂₁ m₂₂ ! m_2n ! ! " ! m_n1 m_n2 ! m_nn ⎡ ⎣ ⎢ ⎢ ⎢ ⎢ ⎢ ⎤ ⎦ ⎥ ⎥ ⎥ ⎥ ⎥ = σ₁m₁₁ σ₁m₁₂ ! σ₁m_1n σ₂m₂₁ σ₂m₂₂ ! σ₂m_2n ! ! " ! σ_nm_n1 σ_nm_n2 ! σ_nm_nn ⎡ ⎣ ⎢ ⎢ ⎢ ⎢ ⎢ ⎤ ⎦ ⎥ ⎥ ⎥ ⎥ ⎥ argmax R_i E_i = argmax R_i Tr

(

Σ_iM_i

)

M_i=V_iTR_iU_i

∵V_iT, R_i, and U_i are all orthonormal matrices

(

)

M_i: orthonormal matrix

when m_ij is the j-th column vector of M_i ⇒ m_ij 2 = m_ijTm_ij = 1

∴Tr Σ

(

M

)

=σ m +σ m +!+σ m ≤σ +σ +!+σ Σ_iM_i = σ₁ 0 ! 0 0 σ₂ ! 0 ! ! " ! 0 0 ! σ_n ⎡ ⎣ ⎢ ⎢ ⎢ ⎢ ⎢ ⎤ ⎦ ⎥ ⎥ ⎥ ⎥ ⎥ m₁₁ m₁₂ ! m_1n m₂₁ m₂₂ ! m_2n ! ! " ! m_n1 m_n2 ! m_nn ⎡ ⎣ ⎢ ⎢ ⎢ ⎢ ⎢ ⎤ ⎦ ⎥ ⎥ ⎥ ⎥ ⎥ = σ₁m₁₁ σ₁m₁₂ ! σ₁m_1n σ₂m₂₁ σ₂m₂₂ ! σ₂m_2n ! ! " ! σ_nm_n1 σ_nm_n2 ! σ_nm_nn ⎡ ⎣ ⎢ ⎢ ⎢ ⎢ ⎢ ⎤ ⎦ ⎥ ⎥ ⎥ ⎥ ⎥

∵V_iT, R_i, and U_i are all orthonormal matrices

(

)

M_i: orthonormal matrix

when m_ij is the j-th column vector of M_i ⇒ m_ij 2 = m_ijTm_ij = 1

∴Tr Σ

(

_iM_i

)

=σ₁m₁₁ +σ₂m₂₂ +!+σ_nm_nn ≤σ₁ +σ₂ +!+σ_n Tr

(

Σ M

)

is maximized when M = I Σ_iM_i = σ₁ 0 ! 0 0 σ₂ ! 0 ! ! " ! 0 0 ! σ_n ⎡ ⎣ ⎢ ⎢ ⎢ ⎢ ⎢ ⎤ ⎦ ⎥ ⎥ ⎥ ⎥ ⎥ m₁₁ m₁₂ ! m_1n m₂₁ m₂₂ ! m_2n ! ! " ! m_n1 m_n2 ! m_nn ⎡ ⎣ ⎢ ⎢ ⎢ ⎢ ⎢ ⎤ ⎦ ⎥ ⎥ ⎥ ⎥ ⎥ = σ₁m₁₁ σ₁m₁₂ ! σ₁m_1n σ₂m₂₁ σ₂m₂₂ ! σ₂m_2n ! ! " ! σ_nm_n1 σ_nm_n2 ! σ_nm_nn ⎡ ⎣ ⎢ ⎢ ⎢ ⎢ ⎢ ⎤ ⎦ ⎥ ⎥ ⎥ ⎥ ⎥ argmax R_i E_i = argmax R_i Tr

(

Σ_iM_i

)

M_i=V_iTR_iU_i

argmax R_i E_i = argmax R_i Tr

(

Σ_iM_i

)

M_i=V_iTR_iU_i Tr

(

Σ_iM_i

)

is maximized when M_i = I

Tr

(

Σ_iM_i

)

is maximized when M_i = I

argmax R_i E_i = argmax R_i Tr

(

Σ_iM_i

)

M_i=V_iTR_iU_i Tr

(

Σ_iM_i

)

is maximized when M_i = I

⇔ Tr Σ

(

_iM_i

)

is maximized when I=V_iTR_iU_i

∵Vi −1 _{= V} i T

(

)

∵U −1 = U T

(

)

I=V_iTR_iU_i ⇔ V_i=R_iU_i ⇔ R = VU T

Tr

(

Σ_iM_i

)

is maximized when M_i = I

⇔ Tr Σ

(

_iM_i

)

is maximized when I=V_iTR_iU_i

∵Vi −1 _{= V} i T

(

)

∵U_i−1 = U_iT

(

)

I=V_iTR_iU_i ⇔ V_i=R_iU_i ⇔ R_i = V_iU_iT ⇔ Tr Σ

(

M

)

is maximized when R = VU T

argmax R_i E_i = argmax R_i Tr

(

Σ_iM_i

)

M_i=V_iTR_iU_i Tr

(

Σ_iM_i

)

is maximized when M_i = I

⇔ Tr Σ

(

_iM_i

)

is maximized when I=V_iTR_iU_i

∴ R

_i

= V

_i

U

_i

T

∵Vi −1 _{= V} i T

(

)

∵U_i−1 = U_iT

(

)

I=V_iTR_iU_i ⇔ V_i=R_iU_i ⇔ R_i = V_iU_iT ⇔ Tr Σ

(

_iM_i

)

is maximized when R_i = V_iU_iT

∴E( ′S )= E_i i=1 n

∑

= w_{1 j} e_{1 j}′ − R_ie_{1 j} 2 j∈N₁

∑

+ w_{2 j} e′_{2 j} − R_ie_{2 j} 2 j

∑

∈N₂ +!+ w_nj e_nj′ − R_ie_nj 2 j

∑

∈N_n E_i = w_ij e_ij′ − R_ie_ij 2 j∈N_i

∑

⇐ R_i = V_iU_iT

∴E( ′S )= E_i i=1 n

∑

= w_{1 j} e_{1 j}′ − R_ie_{1 j} 2 j∈N₁

∑

+ w_{2 j} e′_{2 j} − R_ie_{2 j} 2 j

∑

∈N₂ +!+ w_nj e_nj′ − R_ie_nj 2 j

∑

∈N_n

In order to compute optimal vertex positions from given rotations, we compute the gradient of E

( )

S′ with respect to the positions p .′

∴E( ′S )= E_i i=1 n

∑

= w_{1 j} e_{1 j}′ − R_ie_{1 j} 2 j∈N₁

∑

+ w_{2 j} e′_{2 j} − R_ie_{2 j} 2 j

∑

∈N₂ +!+ w_nj e_nj′ − R_ie_nj 2 j

∑

∈N_n

In order to compute optimal vertex positions from given rotations, we compute the gradient of E

( )

S′ with respect to the positions p .′

Let us compute the partial derivatives w.r.t. p′_i.

E_i = w_ij e_ij′ − R_ie_ij 2

j∈N_i

∑

⇐ R_i = V_iU_iT

Note that the only terms in E

( )

S′

∴ ∂E(S )′ ∂p = ∂∂p wij eij′ − Rieij 2 ∈N

∑

+ w_ji e′_ji − R_je_ji 2 ∈N

∑

⎛ ⎝⎜ ⎞ ⎠⎟ ∴E( ′S )= E_i i=1 n

∑

= w_{1 j} e_{1 j}′ − R_ie_{1 j} 2 j∈N₁

∑

+ w_{2 j} e′_{2 j} − R_ie_{2 j} 2 j

∑

∈N₂ +!+ w_nj e_nj′ − R_ie_nj 2 j

∑

∈N_n

In order to compute optimal vertex positions from given rotations, we compute the gradient of E

( )

S′ with respect to the positions p .′

Let us compute the partial derivatives w.r.t. p′_i. Note that the only terms in E

( )

S′

∂E( ′S ) ∂p_i = ∂∂p_i wij eij′ − Rieij 2 j∈N_i

∑

+ w_ji e′_ji − R_je_ji 2 j∈N_i

∑

⎛ ⎝⎜ ⎞ ⎠⎟

= ∂ ∂p_i wij (p′i − ′pj)− Ri(pi − pj) 2 j∈N_i

∑

+ w_ji (p′_j − ′p_i)− R_j(p_j − p_i) 2 j∈N_i

∑

⎛ ⎝⎜ ⎞ ⎠⎟

∂E( ′S ) ∂p_i = ∂∂p_i wij eij′ − Rieij 2 j∈N_i

∑

+ w_ji e′_ji − R_je_ji 2 j∈N_i

∑

⎛ ⎝⎜ ⎞ ⎠⎟ = ∂ ∂p_i wij (p′i − ′pj)− Ri(pi − pj) 2 j∈N_i

∑

+ w_ji (p′_j − ′p_i)− R_j(p_j − p_i) 2 j∈N_i

∑

⎛ ⎝⎜ ⎞ ⎠⎟ = 2w_ij

(

(p′_i − ′p_j)− R_i(p_i − p_j)

)

∈N

∑

− 2w_ji

(

(p′_j − ′p_i)− R_j(p_j − p_i)

)

∈N

∑

= ∂ ∂p_i wij (p′i − ′pj)− Ri(pi − pj) 2 j∈N_i

∑

+ w_ji (p′_j − ′p_i)− R_j(p_j − p_i) 2 j∈N_i

∑

⎛ ⎝⎜ ⎞ ⎠⎟ = 2w_ij

(

(p′_i − ′p_j)− R_i(p_i − p_j)

)

j∈N_i

∑

− 2w_ji

(

(p′_j − ′p_i)− R_j(p_j − p_i)

)

j∈N_i

∑

= 2w_ij

(

(p′_i − ′p_j)− R_i(p_i − p_j)

)

∈N

∑

− 2w_ij

(

(p′_j − ′p_i)− R_j(p_j − p_i)

)

∈N

∑

∵wij = wji

∂E( ′S ) ∂p_i = ∂∂p_i wij eij′ − Rieij 2 j∈N_i

∑

+ w_ji e′_ji − R_je_ji 2 j∈N_i

∑

⎛ ⎝⎜ ⎞ ⎠⎟ = ∂ ∂p_i wij (p′i − ′pj)− Ri(pi − pj) 2 j∈N_i

∑

+ w_ji (p′_j − ′p_i)− R_j(p_j − p_i) 2 j∈N_i

∑

⎛ ⎝⎜ ⎞ ⎠⎟ = 2w_ij

(

(p′_i − ′p_j)− R_i(p_i − p_j)

)

j∈N_i

∑

− 2w_ji

(

(p′_j − ′p_i)− R_j(p_j − p_i)

)

j∈N_i

∑

= 2w_ij

(

(p′_i − ′p_j)− R_i(p_i − p_j)

)

j∈N_i

∑

− 2w_ij

(

(p′_j − ′p_i)− R_j(p_j − p_i)

)

j∈N_i

∑

∵wij = wji = 2w_ij

(

(p′_i − ′p_j)− R_i(p_i − p_j)

)

∈N

∑

+ 2w_ij

(

(p′_i − ′p_j)− R_j(p_i − p_j)

)

∈N

∑

∵−(a − b) = (b − a)

= ∂ ∂p_i wij (p′i − ′pj)− Ri(pi − pj) 2 j∈N_i

∑

+ w_ji (p′_j − ′p_i)− R_j(p_j − p_i) 2 j∈N_i

∑

⎛ ⎝⎜ ⎞ ⎠⎟ = 2w_ij

(

(p′_i − ′p_j)− R_i(p_i − p_j)

)

j∈N_i

∑

− 2w_ji

(

(p′_j − ′p_i)− R_j(p_j − p_i)

)

j∈N_i

∑

= 2w_ij

(

(p′_i − ′p_j)− R_i(p_i − p_j)

)

j∈N_i

∑

− 2w_ij

(

(p′_j − ′p_i)− R_j(p_j − p_i)

)

j∈N_i

∑

∵wij = wji = 2w_ij

(

(p′_i − ′p_j)− R_i(p_i − p_j)

)

j∈N_i

∑

+ 2w_ij

(

(p′_i − ′p_j)− R_j(p_i − p_j)

)

j∈N_i

∑

= 4w_ij(p′_i − ′p_j) ∈N

∑

− 2w_ij

(

R_i(p_i − p_j)+ R_j(p_i − p_j)

)

∈N

∑

∵−(a − b) = (b − a)

∂E( ′S ) ∂p_i = ∂∂p_i wij eij′ − Rieij 2 j∈N_i

∑

+ w_ji e′_ji − R_je_ji 2 j∈N_i

∑

⎛ ⎝⎜ ⎞ ⎠⎟ = ∂ ∂p_i wij (p′i − ′pj)− Ri(pi − pj) 2 j∈N_i

∑

+ w_ji (p′_j − ′p_i)− R_j(p_j − p_i) 2 j∈N_i

∑

⎛ ⎝⎜ ⎞ ⎠⎟ = 2w_ij

(

(p′_i − ′p_j)− R_i(p_i − p_j)

)

j∈N_i

∑

− 2w_ji

(

(p′_j − ′p_i)− R_j(p_j − p_i)

)

j∈N_i

∑

= 2w_ij

(

(p′_i − ′p_j)− R_i(p_i − p_j)

)

j∈N_i

∑

− 2w_ij

(

(p′_j − ′p_i)− R_j(p_j − p_i)

)

j∈N_i

∑

∵wij = wji = 2w_ij

(

(p′_i − ′p_j)− R_i(p_i − p_j)

)

j∈N_i

∑

+ 2w_ij

(

(p′_i − ′p_j)− R_j(p_i − p_j)

)

j∈N_i

∑

= 4w_ij(p′_i − ′p_j) j∈N_i

∑

− 2w_ij

(

R_i(p_i − p_j)+ R_j(p_i − p_j)

)

j∈N_i

∑

= 4w_ij(p′_i − ′p_j) ∈N

∑

− 2w_ij

(

R_i + R_j

)

(p_i − p_j) ∈N

∑

∵−(a − b) = (b − a)

= ∂ ∂p_i wij (p′i − ′pj)− Ri(pi − pj) 2 j∈N_i

∑

+ w_ji (p′_j − ′p_i)− R_j(p_j − p_i) 2 j∈N_i

∑

⎛ ⎝⎜ ⎞ ⎠⎟ = 2w_ij

(

(p′_i − ′p_j)− R_i(p_i − p_j)

)

j∈N_i

∑

− 2w_ji

(

(p′_j − ′p_i)− R_j(p_j − p_i)

)

j∈N_i

∑

= 2w_ij

(

(p′_i − ′p_j)− R_i(p_i − p_j)

)

j∈N_i

∑

− 2w_ij

(

(p′_j − ′p_i)− R_j(p_j − p_i)

)

j∈N_i

∑

∵wij = wji = 2w_ij

(

(p′_i − ′p_j)− R_i(p_i − p_j)

)

j∈N_i

∑

+ 2w_ij

(

(p′_i − ′p_j)− R_j(p_i − p_j)

)

j∈N_i

∑

= 4w_ij(p′_i − ′p_j) j∈N_i

∑

− 2w_ij

(

R_i(p_i − p_j)+ R_j(p_i − p_j)

)

j∈N_i

∑

= 4w_ij(p′_i − ′p_j) j∈N_i

∑

− 2w_ij

(

R_i + R_j

)

(p_i − p_j) j∈N_i

∑

∵−(a − b) = (b − a) = 0

∂E( ′S ) ∂p_i = ∂∂p_i wij eij′ − Rieij 2 j∈N_i

∑

+ w_ji e′_ji − R_je_ji 2 j∈N_i

∑

⎛ ⎝⎜ ⎞ ⎠⎟ = ∂ ∂p_i wij (p′i − ′pj)− Ri(pi − pj) 2 j∈N_i

∑

+ w_ji (p′_j − ′p_i)− R_j(p_j − p_i) 2 j∈N_i

∑

⎛ ⎝⎜ ⎞ ⎠⎟ = 2w_ij

(

(p′_i − ′p_j)− R_i(p_i − p_j)

)

j∈N_i

∑

− 2w_ji

(

(p′_j − ′p_i)− R_j(p_j − p_i)

)

j∈N_i

∑

= 2w_ij

(

(p′_i − ′p_j)− R_i(p_i − p_j)

)

j∈N_i

∑

− 2w_ij

(

(p′_j − ′p_i)− R_j(p_j − p_i)

)

j∈N_i

∑

∵wij = wji = 2w_ij

(

(p′_i − ′p_j)− R_i(p_i − p_j)

)

j∈N_i

∑

+ 2w_ij

(

(p′_i − ′p_j)− R_j(p_i − p_j)

)

j∈N_i

∑

= 4w_ij(p′_i − ′p_j) j∈N_i

∑

− 2w_ij

(

R_i(p_i − p_j)+ R_j(p_i − p_j)

)

j∈N_i

∑

= 4w_ij(p′_i − ′p_j) j∈N_i

∑

− 2w_ij

(

R_i + R_j

)

(p_i − p_j) j∈N_i

∑

∵−(a − b) = (b − a) = 0

∴

w

_ij

(

p

′

_i

− ′

p

_j

)

j

∈N

_i

∑

=

w

ij

2

(

R

i

+ R

j

)

(p

i

− p

j

)

j

∈N

_i

∑