• 검색 결과가 없습니다.

As-Rigid-As-Possible Deformation

N/A
N/A
Protected

Academic year: 2021

Share "As-Rigid-As-Possible Deformation"

Copied!
81
0
0

로드 중.... (전체 텍스트 보기)

전체 글

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

참조

관련 문서

 The curl of the velocity field of a rotating rigid body has the direction of the axis of the rotation,.  and its magnitude equals twice the angular speed

As the seventh elective-centered curriculum focuses on outlining the broad base of the national curriculum, it is possible for general high schools to

• The fundamental relation between the forces acting on a rigid body in plane motion and the acceleration of its mass center and the angular acceleration of the body

If the the bond to the leaving group is broken and the bond to the nucleophile is formed simultaneous, then bond to the nucleophile is formed simultaneous, then rxn

 Action causing unsteady flow takes place over a period of many 2 L/a time intervals, then it would be more appropriate to use rigid water column theory..  On the

Reference 7 contains a derivation (also by the Newtonian method) of a system of nonlinear equations for the elastic bending and rigid pitching motion of a cantilever rotor

The blade is assumed rigid and it undergoes a single degree pitch motion about the feathering axis.. There is a torsional spring at the root

출처 : IAEA 발표 자료(Comprehensive inspection exercise at bulk handling facilities, “U-235 Enrichment measurements by gamma-ray spectroscopy”) 13.  Uranium