As-Rigid-As-Possible Deformation

전체 글

(1)

As-Rigid-As-Possible

Surface Modeling

Wanho Choi

(wanochoi.com)

(2)

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

(3)
(4)
(5)

deformation

(6)
(7)

S: initial triangle mesh (given input mesh)

S : deformed mesh (output mesh to be computed)

n: # of vertices

pi: the i-th vertex position of S

pi: the i-th vertex position of S

(8)

n: # of vertices

pi: the i-th vertex position of S

pi: the i-th vertex position of S

Ni: one-ring neighbor vertices of the vertex i

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

(9)

S: initial triangle mesh (given input mesh)

S : deformed mesh (output mesh to be computed)

n: # of vertices

pi: the i-th vertex position of S

pi: the i-th vertex position of S

Ni: one-ring neighbor vertices of the vertex i

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

pi − ′pj = Ri

(

pi − pj

)

, ∀j ∈Ni

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

Ei = wij

(

pi − ′pj

)

− Ri

(

pi − pj

)

2

j∈Ni

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

(10)

n: # of vertices

pi: the i-th vertex position of S

pi: the i-th vertex position of S

Ni: one-ring neighbor vertices of the vertex i

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

pi − ′pj = Ri

(

pi − pj

)

, ∀j ∈Ni

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

Ei = wij

(

pi − ′pj

)

− Ri

(

pi − pj

)

2

j∈Ni

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

let eij = pi − pj & eij = ′pi − ′pj

(

)

= wij eij− Rieij 2

j∈Ni

(11)

Ei = wij eij− Rieij 2

j∈Ni

(12)
(13)

Ei = wij eij− Rieij 2 j∈Ni

pi p α β wij

(14)

p α β wij wij = 1 2

(

cotα + cotβ

)

= wji

(15)

Ei = wij eij− Rieij 2 j∈Ni

pi p α β wij wij = 1 2

(

cotα + cotβ

)

= wji

(16)

p α β wij wij = 1 2

(

cotα + cotβ

)

= wji

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

(17)

Ei = wij eij− Rieij 2 j∈Ni

pi pj α β wij = 1 2

(

cotα + cotβ

)

= wji

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

[Jacobson and Sorkine 2012]

wij

(18)
(19)

Ei = wij eij− Rieij 2 j∈Ni

= wij

(

eij− Rieij

)

T

(

eij− Rieij

)

j∈Ni

p⋅p = pTp = p 2

(20)

= wij

(

eij− Rieij

)

(

eij− Rieij

)

j∈Ni

= wij

(

eij′T − eijTRiT

)

(

eij − Rieij

)

∈N

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

(21)

Ei = wij eij− Rieij 2 j∈Ni

= wij

(

eij− Rieij

)

T

(

eij− Rieij

)

j∈Ni

= wij

(

eij′T − eijTRiT

)

(

eij − Rieij

)

j∈Ni

= wij

(

eij′Teij′ − ′eijTRieij − eijTRiTeij+ eijTRiTRieij

)

∈N

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

(22)

= wij

(

eij− Rieij

)

(

eij− Rieij

)

j∈Ni

= wij

(

eij′T − eijTRiT

)

(

eij − Rieij

)

j∈Ni

= wij

(

eij′Teij′ − ′eijTRieij − eijTRiTeij+ eijTRiTRieij

)

j∈Ni

= wij

(

eij′Teij′ − 2 ′eijTRieij + eijTRiTRieij

)

∈N

∵pT Aq= p

(

TAq

)

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

(23)

Ei = wij eij− Rieij 2 j∈Ni

= wij

(

eij′Teij′ − 2 ′eijTRieij + eijTeij

)

∈N

= wij

(

eij− Rieij

)

T

(

eij− Rieij

)

j∈Ni

= wij

(

eij′T − eijTRiT

)

(

eij − Rieij

)

j∈Ni

= wij

(

eij′Teij′ − ′eijTRieij − eijTRiTeij+ eijTRiTRieij

)

j∈Ni

= wij

(

eij′Teij′ − 2 ′eijTRieij + eijTRiTRieij

)

j∈Ni

∵pT Aq= p

(

TAq

)

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

(24)

∵pT Aq= p

(

TAq

)

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

(

eij′Teij′ − 2 ′eijTRieij + eijTeij

)

j∈Ni

= wij

(

eij− Rieij

)

(

eij− Rieij

)

j∈Ni

= wij

(

eij′T − eijTRiT

)

(

eij − Rieij

)

j∈Ni

= wij

(

eij′Teij′ − ′eijTRieij − eijTRiTeij+ eijTRiTRieij

)

j∈Ni

= wij

(

eij′Teij′ − 2 ′eijTRieij + eijTRiTRieij

)

j∈Ni

∴E

i

=

w

ij

(

e

ij

T

e

ij

− 2 ′

e

ijT

R

i

e

ij

+ e

ijT

e

ij

)

j∈N

: scalar

(25)

Ei = wij

(

eij′Teij′ − 2 ′eijTRieij + eijTeij

)

j∈Ni

(26)
(27)

Ei = wij

(

eij′Teij′ − 2 ′eijTRieij + eijTeij

)

j∈Ni

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

(28)

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

(29)

Ei = wij

(

eij′Teij′ − 2 ′eijTRieij + eijTeij

)

j∈Ni

argmin R Ei

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

= argmin R wij

(

eij′Teij′ − 2 ′eijTRieij + eijTeij

)

∈N

∵Ei = wij eij T ′ eij − 2 ′eijTRieij + eijTeij

(

)

j∈N

(30)

∵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 Ei as little as possible.

= argmin Ri wij

(

eij′Teij′ − 2 ′eijTRieij + eijTeij

)

j∈Ni

= argmin Ri wij

(

−2 ′eijTRieij

)

j∈Ni

∵Ei = wij eij T ′ eij − 2 ′eijTRieij + eijTeij

(

)

j∈Ni

argmin Ri Ei

(31)

∵The terms that do not contain Ri

are constant in the minimization and therefore can be dropped.

Ei = wij

(

eij′Teij′ − 2 ′eijTRieij + eijTeij

)

j∈Ni

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

= argmin Ri wij

(

eij′Teij′ − 2 ′eijTRieij + eijTeij

)

j∈Ni

= argmin Ri wij

(

−2 ′eijTRieij

)

j∈Ni

∵Ei = wij eij T ′ eij − 2 ′eijTRieij + eijTeij

(

)

j∈Ni

= argmin R −2wijeij′TRieij

(

)

∈N

∵wij is a scalar argmin Ri Ei

(32)

∵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 Ei as little as possible.

= argmin Ri wij

(

eij′Teij′ − 2 ′eijTRieij + eijTeij

)

j∈Ni

= argmin Ri wij

(

−2 ′eijTRieij

)

j∈Ni

∵Ei = wij eij T ′ eij − 2 ′eijTRieij + eijTeij

(

)

j∈Ni

= argmin Ri −2wijeij′TRieij

(

)

j∈Ni

= argmin R −wijeijTRieij

(

)

∈N

∵wij is a scalar ∵min(−2E) = min(−E) argmin Ri Ei

(33)

∵The terms that do not contain Ri

are constant in the minimization and therefore can be dropped.

= argmax R wijeij′TRieij

(

)

∈N

Ei = wij

(

eij′Teij′ − 2 ′eijTRieij + eijTeij

)

j∈Ni

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

= argmin Ri wij

(

eij′Teij′ − 2 ′eijTRieij + eijTeij

)

j∈Ni

= argmin Ri wij

(

−2 ′eijTRieij

)

j∈Ni

∵Ei = wij eij T ′ eij − 2 ′eijTRieij + eijTeij

(

)

j∈Ni

= argmin Ri −2wijeij′TRieij

(

)

j∈Ni

= argmin Ri −wijeijTRieij

(

)

j∈Ni

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

(34)

∵The terms that do not contain Ri

are constant in the minimization and therefore can be dropped.

= argmax Ri wijeij′TRieij

(

)

j∈Ni

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

= argmin Ri wij

(

eij′Teij′ − 2 ′eijTRieij + eijTeij

)

j∈Ni

= argmin Ri wij

(

−2 ′eijTRieij

)

j∈Ni

∵Ei = wij eij T ′ eij − 2 ′eijTRieij + eijTeij

(

)

j∈Ni

= argmin Ri −2wijeij′TRieij

(

)

j∈Ni

= argmin Ri −wijeijTRieij

(

)

j∈Ni

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

∴our goal: argmax

Ri

w

ij

e

ij

T

R

i

e

ij

(

)

j∈N

argmin Ri Ei

(35)

argmax Ri wijeij′TRieij

(

)

j∈Ni

(36)
(37)

argmax Ri wijeij′TRieij

(

)

j∈Ni

= argmax Ri Tr wijRieijeij′T j∈Ni

⎛ ⎝⎜ ⎞ ⎠⎟ Why eij′TRieij = Tr R

(

ieijeij′T

)

?

(38)

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

(

aγ + bδ

)

(

cγ + dδ

)

Why eij′TRieij = Tr R

(

ieijeij′T

)

?

(39)

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 Ri wijeij′TRieij

(

)

j∈Ni

= argmax Ri Tr wijRieijeij′T j∈Ni

⎛ ⎝⎜ ⎞ ⎠⎟ Why eij′TRieij = Tr R

(

ieijeij′T

)

?

(40)

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 eij′TRieij = Tr R

(

ieijeij′T

)

?

(41)

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 Ri wijeij′TRieij

(

)

j∈Ni

= argmax Ri Tr wijRieijeij′T j∈Ni

⎛ ⎝⎜ ⎞ ⎠⎟ Tr Aqp

(

T

)

(

aγ + bδ

)

(

cγ + dδ

)

Why eij′TRieij = Tr R

(

ieijeij′T

)

?

(42)
(43)

argmax Ri wijeij′TRieij

(

)

j∈Ni

= argmax Ri Tr wijRieijeij′T j∈Ni

⎛ ⎝⎜ ⎞ ⎠⎟ = argmax Ri Tr Riwijeijeij′T j∈Ni

⎛ ⎝⎜ ⎞ ⎠⎟ ∵wij : scalar

(44)

= argmax Ri Tr Riwijeijeij′T j∈Ni

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

⎛ ⎝⎜ ⎞ ⎠⎟ ∵Ri : constant

(45)

argmax Ri wijeij′TRieij

(

)

j∈Ni

= argmax Ri Tr wijRieijeij′T j∈Ni

⎛ ⎝⎜ ⎞ ⎠⎟ = argmax Ri Tr Riwijeijeij′T j∈Ni

⎛ ⎝⎜ ⎞ ⎠⎟ ∵wij : scalar = argmax Ri Tr Ri wijeijeij′T j∈Ni

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

(

iSi

)

∵let Si = wijeijeij′ T ∈N

(46)

= argmax Ri Tr Riwijeijeij′T j∈Ni

⎛ ⎝⎜ ⎞ ⎠⎟ ∵wij : scalar = argmax Ri Tr Ri wijeijeij′T j∈Ni

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

(

iSi

)

∵let Si = wijeijeij′ T j∈Ni

= argmaxTr R

(

iUiΣiViT

)

(47)

argmax Ri wijeij′TRieij

(

)

j∈Ni

= argmax Ri Tr wijRieijeij′T j∈Ni

⎛ ⎝⎜ ⎞ ⎠⎟ = argmax Ri Tr Riwijeijeij′T j∈Ni

⎛ ⎝⎜ ⎞ ⎠⎟ ∵wij : scalar = argmax Ri Tr Ri wijeijeij′T j∈Ni

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

(

iSi

)

∵let Si = wijeijeij′ T j∈Ni

= argmax Ri Tr R

(

iUiΣiViT

)

= argmaxTr (R

(

iUi)(ΣiViT)

)

(48)

= argmax Ri Tr Riwijeijeij′T j∈Ni

⎛ ⎝⎜ ⎞ ⎠⎟ ∵wij : scalar = argmax Ri Tr Ri wijeijeij′T j∈Ni

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

(

iSi

)

∵let Si = wijeijeij′ T j∈Ni

= argmax Ri Tr R

(

iUiΣiViT

)

= argmax Ri Tr (R

(

iUi)(ΣiViT)

)

(49)

argmax Ri wijeij′TRieij

(

)

j∈Ni

= argmax Ri Tr wijRieijeij′T j∈Ni

⎛ ⎝⎜ ⎞ ⎠⎟ = argmax Ri Tr Riwijeijeij′T j∈Ni

⎛ ⎝⎜ ⎞ ⎠⎟ ∵wij : scalar = argmax Ri Tr Ri wijeijeij′T j∈Ni

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

(

iSi

)

∵let Si = wijeijeij′ T j∈Ni

= argmax Ri Tr R

(

iUiΣiViT

)

= argmax Ri Tr (R

(

iUi)(ΣiViT)

)

= argmax Ri Tr (

(

ΣiViT)(RiUi)

)

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

(

ΣiViTRiUi

)

(50)

= argmax Ri Tr Riwijeijeij′T j∈Ni

⎛ ⎝⎜ ⎞ ⎠⎟ ∵wij : scalar = argmax Ri Tr Ri wijeijeij′T j∈Ni

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

(

iSi

)

∵let Si = wijeijeij′ T j∈Ni

= argmax Ri Tr R

(

iUiΣiViT

)

= argmax Ri Tr (R

(

iUi)(ΣiViT)

)

= argmax Ri Tr (

(

ΣiViT)(RiUi)

)

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

(

ΣiViTRiUi

)

= argmaxTr

(

ΣiMi

)

∵let Mi=Vi T RiUi

(51)

argmax Ri

Ei = argmax

Ri

(52)

ViT, Ri, and Ui are all orthonormal matrices

(

)

Mi: orthonormal matrix

(53)

ViT, Ri, and Ui are all orthonormal matrices

(

)

Mi: orthonormal matrix

when mij is the j-th column vector of Mi ⇒ mij 2 = mijTmij = 1

ΣiMi = σ1 0 ! 0 0 σ2 ! 0 ! ! " ! 0 0 ! σn ⎡ ⎣ ⎢ ⎢ ⎢ ⎢ ⎢ ⎤ ⎦ ⎥ ⎥ ⎥ ⎥ ⎥ m11 m12 ! m1n m21 m22 ! m2n ! ! " ! mn1 mn2 ! mnn ⎡ ⎣ ⎢ ⎢ ⎢ ⎢ ⎢ ⎤ ⎦ ⎥ ⎥ ⎥ ⎥ ⎥ = σ1m11 σ1m12 ! σ1m1n σ2m21 σ2m22 ! σ2m2n ! ! " ! σnmn1 σnmn2 ! σnmnn ⎡ ⎣ ⎢ ⎢ ⎢ ⎢ ⎢ ⎤ ⎦ ⎥ ⎥ ⎥ ⎥ ⎥ argmax Ri Ei = argmax Ri Tr

(

ΣiMi

)

Mi=ViTRiUi

(54)

ViT, Ri, and Ui are all orthonormal matrices

(

)

Mi: orthonormal matrix

when mij is the j-th column vector of Mi ⇒ mij 2 = mijTmij = 1

∴Tr Σ

(

M

)

mm +!+σ m ≤σ +σ +!+σ ΣiMi = σ1 0 ! 0 0 σ2 ! 0 ! ! " ! 0 0 ! σn ⎡ ⎣ ⎢ ⎢ ⎢ ⎢ ⎢ ⎤ ⎦ ⎥ ⎥ ⎥ ⎥ ⎥ m11 m12 ! m1n m21 m22 ! m2n ! ! " ! mn1 mn2 ! mnn ⎡ ⎣ ⎢ ⎢ ⎢ ⎢ ⎢ ⎤ ⎦ ⎥ ⎥ ⎥ ⎥ ⎥ = σ1m11 σ1m12 ! σ1m1n σ2m21 σ2m22 ! σ2m2n ! ! " ! σnmn1 σnmn2 ! σnmnn ⎡ ⎣ ⎢ ⎢ ⎢ ⎢ ⎢ ⎤ ⎦ ⎥ ⎥ ⎥ ⎥ ⎥

(55)

ViT, Ri, and Ui are all orthonormal matrices

(

)

Mi: orthonormal matrix

when mij is the j-th column vector of Mi ⇒ mij 2 = mijTmij = 1

∴Tr Σ

(

iMi

)

1m112m22 +!+σnmnn ≤σ12 +!+σn Tr

(

Σ M

)

is maximized when M = I ΣiMi = σ1 0 ! 0 0 σ2 ! 0 ! ! " ! 0 0 ! σn ⎡ ⎣ ⎢ ⎢ ⎢ ⎢ ⎢ ⎤ ⎦ ⎥ ⎥ ⎥ ⎥ ⎥ m11 m12 ! m1n m21 m22 ! m2n ! ! " ! mn1 mn2 ! mnn ⎡ ⎣ ⎢ ⎢ ⎢ ⎢ ⎢ ⎤ ⎦ ⎥ ⎥ ⎥ ⎥ ⎥ = σ1m11 σ1m12 ! σ1m1n σ2m21 σ2m22 ! σ2m2n ! ! " ! σnmn1 σnmn2 ! σnmnn ⎡ ⎣ ⎢ ⎢ ⎢ ⎢ ⎢ ⎤ ⎦ ⎥ ⎥ ⎥ ⎥ ⎥ argmax Ri Ei = argmax Ri Tr

(

ΣiMi

)

Mi=ViTRiUi

(56)
(57)

argmax Ri Ei = argmax Ri Tr

(

ΣiMi

)

Mi=ViTRiUi Tr

(

ΣiMi

)

is maximized when Mi = I

(58)

Tr

(

ΣiMi

)

is maximized when Mi = I

(59)

argmax Ri Ei = argmax Ri Tr

(

ΣiMi

)

Mi=ViTRiUi Tr

(

ΣiMi

)

is maximized when Mi = I

⇔ Tr Σ

(

iMi

)

is maximized when I=ViTRiUi

∵Vi −1 = V i T

(

)

U −1 = U T

(

)

I=ViTRiUi ⇔ Vi=RiUi ⇔ R = VU T

(60)

Tr

(

ΣiMi

)

is maximized when Mi = I

⇔ Tr Σ

(

iMi

)

is maximized when I=ViTRiUi

∵Vi −1 = V i T

(

)

Ui−1 = UiT

(

)

I=ViTRiUi ⇔ Vi=RiUi ⇔ Ri = ViUiT ⇔ Tr Σ

(

M

)

is maximized when R = VU T

(61)

argmax Ri Ei = argmax Ri Tr

(

ΣiMi

)

Mi=ViTRiUi Tr

(

ΣiMi

)

is maximized when Mi = I

⇔ Tr Σ

(

iMi

)

is maximized when I=ViTRiUi

∴ R

i

= V

i

U

i

T

∵Vi −1 = V i T

(

)

Ui−1 = UiT

(

)

I=ViTRiUi ⇔ Vi=RiUi ⇔ Ri = ViUiT ⇔ Tr Σ

(

iMi

)

is maximized when Ri = ViUiT

(62)
(63)

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

= w1 j e1 j− Rie1 j 2 j∈N1

+ w2 j e2 j − Rie2 j 2 j

∈N2 +!+ wnj enj− Rienj 2 j

∈Nn Ei = wij eij− Rieij 2 j∈Ni

⇐ Ri = ViUiT

(64)

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

= w1 j e1 j− Rie1 j 2 j∈N1

+ w2 j e2 j − Rie2 j 2 j

∈N2 +!+ wnj enj− Rienj 2 j

∈Nn

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

( )

S′ with respect to the positions p .

(65)

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

= w1 j e1 j− Rie1 j 2 j∈N1

+ w2 j e2 j − Rie2 j 2 j

∈N2 +!+ wnj enj− Rienj 2 j

∈Nn

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. pi.

Ei = wij eij− Rieij 2

j∈Ni

⇐ Ri = ViUiT

Note that the only terms in E

( )

S

(66)

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

+ wji eji − Rjeji 2 ∈N

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

= w1 j e1 j− Rie1 j 2 j∈N1

+ w2 j e2 j − Rie2 j 2 j

∈N2 +!+ wnj enj− Rienj 2 j

∈Nn

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. pi. Note that the only terms in E

( )

S

(67)

∂E( ′S ) ∂pi = ∂∂pi wij eij− Rieij 2 j∈Ni

+ wji eji − Rjeji 2 j∈Ni

⎛ ⎝⎜ ⎞ ⎠⎟

(68)

= ∂ ∂pi wij (pi − ′pj)− Ri(pi − pj) 2 j∈Ni

+ wji (pj − ′pi)− Rj(pj − pi) 2 j∈Ni

⎛ ⎝⎜ ⎞ ⎠⎟

(69)

∂E( ′S ) ∂pi = ∂∂pi wij eij− Rieij 2 j∈Ni

+ wji eji − Rjeji 2 j∈Ni

⎛ ⎝⎜ ⎞ ⎠⎟ = ∂ ∂pi wij (pi − ′pj)− Ri(pi − pj) 2 j∈Ni

+ wji (pj − ′pi)− Rj(pj − pi) 2 j∈Ni

⎛ ⎝⎜ ⎞ ⎠⎟ = 2wij

(

(pi − ′pj)− Ri(pi − pj)

)

∈N

2wji

(

(pj − ′pi)− Rj(pj − pi)

)

∈N

(70)

= ∂ ∂pi wij (pi − ′pj)− Ri(pi − pj) 2 j∈Ni

+ wji (pj − ′pi)− Rj(pj − pi) 2 j∈Ni

⎛ ⎝⎜ ⎞ ⎠⎟ = 2wij

(

(pi − ′pj)− Ri(pi − pj)

)

j∈Ni

2wji

(

(pj − ′pi)− Rj(pj − pi)

)

j∈Ni

= 2wij

(

(pi − ′pj)− Ri(pi − pj)

)

∈N

2wij

(

(pj − ′pi)− Rj(pj − pi)

)

∈N

∵wij = wji

(71)

∂E( ′S ) ∂pi = ∂∂pi wij eij− Rieij 2 j∈Ni

+ wji eji − Rjeji 2 j∈Ni

⎛ ⎝⎜ ⎞ ⎠⎟ = ∂ ∂pi wij (pi − ′pj)− Ri(pi − pj) 2 j∈Ni

+ wji (pj − ′pi)− Rj(pj − pi) 2 j∈Ni

⎛ ⎝⎜ ⎞ ⎠⎟ = 2wij

(

(pi − ′pj)− Ri(pi − pj)

)

j∈Ni

2wji

(

(pj − ′pi)− Rj(pj − pi)

)

j∈Ni

= 2wij

(

(pi − ′pj)− Ri(pi − pj)

)

j∈Ni

2wij

(

(pj − ′pi)− Rj(pj − pi)

)

j∈Ni

∵wij = wji = 2wij

(

(pi − ′pj)− Ri(pi − pj)

)

∈N

+ 2wij

(

(pi − ′pj)− Rj(pi − pj)

)

∈N

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

(72)

= ∂ ∂pi wij (pi − ′pj)− Ri(pi − pj) 2 j∈Ni

+ wji (pj − ′pi)− Rj(pj − pi) 2 j∈Ni

⎛ ⎝⎜ ⎞ ⎠⎟ = 2wij

(

(pi − ′pj)− Ri(pi − pj)

)

j∈Ni

2wji

(

(pj − ′pi)− Rj(pj − pi)

)

j∈Ni

= 2wij

(

(pi − ′pj)− Ri(pi − pj)

)

j∈Ni

2wij

(

(pj − ′pi)− Rj(pj − pi)

)

j∈Ni

∵wij = wji = 2wij

(

(pi − ′pj)− Ri(pi − pj)

)

j∈Ni

+ 2wij

(

(pi − ′pj)− Rj(pi − pj)

)

j∈Ni

= 4wij(pi − ′pj) ∈N

2wij

(

Ri(pi − pj)+ Rj(pi − pj)

)

∈N

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

(73)

∂E( ′S ) ∂pi = ∂∂pi wij eij− Rieij 2 j∈Ni

+ wji eji − Rjeji 2 j∈Ni

⎛ ⎝⎜ ⎞ ⎠⎟ = ∂ ∂pi wij (pi − ′pj)− Ri(pi − pj) 2 j∈Ni

+ wji (pj − ′pi)− Rj(pj − pi) 2 j∈Ni

⎛ ⎝⎜ ⎞ ⎠⎟ = 2wij

(

(pi − ′pj)− Ri(pi − pj)

)

j∈Ni

2wji

(

(pj − ′pi)− Rj(pj − pi)

)

j∈Ni

= 2wij

(

(pi − ′pj)− Ri(pi − pj)

)

j∈Ni

2wij

(

(pj − ′pi)− Rj(pj − pi)

)

j∈Ni

∵wij = wji = 2wij

(

(pi − ′pj)− Ri(pi − pj)

)

j∈Ni

+ 2wij

(

(pi − ′pj)− Rj(pi − pj)

)

j∈Ni

= 4wij(pi − ′pj) j∈Ni

2wij

(

Ri(pi − pj)+ Rj(pi − pj)

)

j∈Ni

= 4wij(pi − ′pj) ∈N

2wij

(

Ri + Rj

)

(pi − pj) ∈N

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

(74)

= ∂ ∂pi wij (pi − ′pj)− Ri(pi − pj) 2 j∈Ni

+ wji (pj − ′pi)− Rj(pj − pi) 2 j∈Ni

⎛ ⎝⎜ ⎞ ⎠⎟ = 2wij

(

(pi − ′pj)− Ri(pi − pj)

)

j∈Ni

2wji

(

(pj − ′pi)− Rj(pj − pi)

)

j∈Ni

= 2wij

(

(pi − ′pj)− Ri(pi − pj)

)

j∈Ni

2wij

(

(pj − ′pi)− Rj(pj − pi)

)

j∈Ni

∵wij = wji = 2wij

(

(pi − ′pj)− Ri(pi − pj)

)

j∈Ni

+ 2wij

(

(pi − ′pj)− Rj(pi − pj)

)

j∈Ni

= 4wij(pi − ′pj) j∈Ni

2wij

(

Ri(pi − pj)+ Rj(pi − pj)

)

j∈Ni

= 4wij(pi − ′pj) j∈Ni

2wij

(

Ri + Rj

)

(pi − pj) j∈Ni

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

(75)

∂E( ′S ) ∂pi = ∂∂pi wij eij− Rieij 2 j∈Ni

+ wji eji − Rjeji 2 j∈Ni

⎛ ⎝⎜ ⎞ ⎠⎟ = ∂ ∂pi wij (pi − ′pj)− Ri(pi − pj) 2 j∈Ni

+ wji (pj − ′pi)− Rj(pj − pi) 2 j∈Ni

⎛ ⎝⎜ ⎞ ⎠⎟ = 2wij

(

(pi − ′pj)− Ri(pi − pj)

)

j∈Ni

2wji

(

(pj − ′pi)− Rj(pj − pi)

)

j∈Ni

= 2wij

(

(pi − ′pj)− Ri(pi − pj)

)

j∈Ni

2wij

(

(pj − ′pi)− Rj(pj − pi)

)

j∈Ni

∵wij = wji = 2wij

(

(pi − ′pj)− Ri(pi − pj)

)

j∈Ni

+ 2wij

(

(pi − ′pj)− Rj(pi − pj)

)

j∈Ni

= 4wij(pi − ′pj) j∈Ni

2wij

(

Ri(pi − pj)+ Rj(pi − pj)

)

j∈Ni

= 4wij(pi − ′pj) j∈Ni

2wij

(

Ri + Rj

)

(pi − pj) j∈Ni

∵−(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

수치

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

Figure 1:

Large deformation obtained by translating a single vertex constraint (in yellow) using our as-rigid-as-possible technique. p.2
관련 주제 :