As-Rigid-As-Possible Surface Modeling (2007)

Abstract

모델링 태스크( surface deformation and editing)는 surface의 local한 변형을 관찰하면 분석할 수가 있다.

Local transformation의 rigidity를 요구하는 operation이 굉장히 유용하다.

그런 formulation은 non-linear하지만 개념적으로 간단한 에너지 formulation으로 이어진다.

그 E formulation을 최소화 해서 특정 모델링 제약조건 하에서 surface를 deform한다.

얘네는 간단한 iterative mesh editing scheme을 제안한다.

얘네가 제안하는 방법은 detail-preserving 하고, 직관적인 deformation을 할 수 있다.

얘네의 알고리즘은 효과적이고, implement하기 쉬우며, 실용적이다.

1. Introduction

우리가 Shape이라고 말 할 때, 우리는 물체를 돌리거나 위치를 옮겨도 변하지 않는 property를 말합니다.

그래서 preserving shape이라고 하면 object는 rotation/translation만 있고, 크기가 변하거나(scale) 뒤틀리지 않는(shear)것을 의미합니다.

그런데 user가 interactive 하게 모델링을 하는 경우, object는 늘어나기도 하고, 뒤틀리기도 하는데, 그래도 large-scale deformation이 적용되었을 때 local한 shape은 보존되기를 기대합니다. 그림 1에서 보듯이 노란 점을 잡아서 아래로 당기는 경우에도, 특정 부분은 늘어날 수 있겠으나, 부분적인, 디테일들이 변하기를 원하지는 않습니다.

다시 말하면 그런 작은 부분들, local한 부분들의 shape은 as rigid as possible 하게 변해야 합니다. 최대한 scale이나 shear가 되지 않아야 합니다.

그래서 이 논문의 목표는, shape deformation framework를 만드는 것인데, 그 중에서도 특히 local surface deformation을 rigid 하게 만들어서 표면 detail을 보존하는 것입니다.

이런 기술은 특히 세세한 부분이 많은 복잡한 실제 3D object들에서 아주 중요합니다.

이 논문에서는 object의 표면을 덮는 작은 cell들을 정의하고, 그 cell들이 as- rigid- as possible하게 deformation 되도록 합니다.

그러면 각 cell들마다 얼마나 rigid한지 측정할 기준이 필요하겠죠. 제일 자연스러운 방법은 변형 전 상태와 변형 후 상태가 있을 때 1) 그 사이의 rigid transformation을 구하고, 2) 얘를 original shape에다 적용했을 때 나온 shape 과 3)실제 변형된 shape 간의 차이 deviation을 구하는 것입니다. 그럼 Locally shape- preserving deformation을 하기 위해서는 1) rigid transformation을 optimize하는 것이 필요합니다.. 3)차이가 작아야 하니까

자 그러면 이 차이를 구하는 방법이 있다고 하고, 그러면 모델링 프레임워크에서는 cell의 size와 placement(overlap)을 결정해야 합니다.

일단

1) cell들의 크기는 비슷해야 합니다./ 아니면 cell 크기에 따라 가중치를 다르게 줘야 합니다.

2) 그리고 얼마나 오버랩 될지 결정해야 하는데, 한 mesh triangle이 있다면 얘 위에 올라올 수 있는 셀의 개수는 같아야 합니다. 그러니까 overlap이 있더라도 같은 개수의 cell에게 overlap 되어야 한다는 것.

1) Cell 크기는 비슷해야 한다. (아니면 면적따라 가중치 줘야함)
2) Surface의 부분들에서 overlap 되는 cell 개수는 같아야 한다.

이제 앞으로는 triangular mesh를 사용할 건데, 위에서 말한 방법들이 결국은 놀랍게도!

수렴을 개런티하고, 구현도 쉬운 직관적인 iterative procedure로 이어진다.

그리고 Laplacian modeling의 improvement로 해석되어질 수 있다.

1.1 Background

Local Rigidity는 surface deformation model의 governing principle로 해석할 수 있는데

Shell Energy : 두 shape간의 차이를 측정하는 제일 클래식한 탄성 에너지는 Shell Energy이다.
변형전 surface S, 변형 후 S'이 있을 때 그 에너지는 변형이 rigid 일때 minimize 된다. 이건 글로벌하게나 local하게나 true인데, 여기서 정의하는 Fundamental form은 표면을 locally, unique하게 정의하는데, rigid transformation이 일어나게 되면 local shape은 당연히 보존 됨.

사실 surface deformation 시나리오에서 완벽하게 local rigidity를 만족할 수는 없는데, 왜냐면 완벽하게 local rigidity를 만족한다는 말은 결국 object 자체가 rigid라는 뜻이기 때문이다. 아예 변형이 일어나지 않는 상태가 complete local rigid 하다는 말임. 그래서 결국 어느 정도의 변형은 있기 마련이고, 그때 그 변형과 변형이 일어나지 않은 사이의 shape distance는 완전히 0이 아니라 충분히 작은 value가 될 것임.

이 value는 변형 전과 후 사이의 transformation이 as-rigid-as possible할 때 얻어짐.

이 shell 에너지는 non-linear라서 실제로 쓰기는 어렵고, linearized , discrete version에 관한 연구가 많이 있음. 이게 빠르긴 한데 아티팩트를 만듦. (local detail distortion, general shape distortion, large deformation에서) 그래서 그 아티팩트를 또 줄이려고, local distortion에 대해서는 multi-resolution surface representation을 사용하는데. 이제 스무스한 surface를 먼저 변형한 후에 detail을 그 위에 add 하는 것임. 근데 이건 벤딩 해버리면 self-collision 문제가 있음.

As-rigid-as-possible deformation은 shape interpolation에서는 성공적으로 적용이 되었는데,

Source - target이 있을때 그 사이의 intermediate deformation을 as-rigid-as-possible하게 구했음.

Polar decomposition을 통해서.

근데 shape editing에서는 target surface가 unknown 상태이기 때문에 더 어려움.

한가지 가능한 approach는 local rigidity transformation을 optimize하고, coordinates 보존을 동시에 하는 것인데. 이 optimization도 non-lineargka. 그래서 similarity transformation은 가능한데, …

아무튼 이런 방법들이 있는데 제일 중요한건 얘네꺼지

얘네는 이제 직접적으로 as-rigid-as-possible editing 방식을 만드는데, 이 에너지 formulation도 non-linear이지만, iterative 하게, 반복해서, 최소화하는 방법을 제시합니다.

최근에 나온 Laplacian editing의 경우 iterative 한 방식은 비슷하지만 specific한 에너지 formulation은 하지 않음.

위의 non-linear approach들은 꽤 좋은 결과를 보이는데, 얘네 방법의 장점은 iterative minimizing scheme이 구현이 쉽고, 수렴을 개런티한다는 것이다.

2. Discrete surfaces setup

S: triangle mesh (n vertices, m triangles_

N(i): vertex I 의 one-ring neighbors

Cell을 overlap 해야 하기 때문에 vertex 위주로 cell을 정하고

변형 전후에 대하여 각 셀마다 가장 approximate rigid transformation 구하고
에너지 function을 만들어서 실제 rigid transformation 적용한 결과와 얼마나 차이 나는지 구하고
그 차이를 어떻게 줄이는지 optimize 한 후에 이걸 modeling operation에서 사용한다.

2.1 analyzing rigid transformation between two cells

변형 전후의 approximate rigid transformation이 있다는 것은 상응하는 Rotation matrix가 있다는 뜻임.

이건 점에서 뻗어나가는 edge들을 관찰해서 정의할 수 있는데,

만약 변형이 rigid 하지 않다면 가장 best approximate rotation을 다음과 같이 구할 수 있다는 뜻이다.

변형된거랑 변형 전에다가 best rotation을 구한걸 빼면 그 차를 최소화하면 됨.

아래 식은 별 거 없고 그냥 derivation 하면 이렇게 됨.

이때 R을 포함하는 식만 남기면 저런 식을 최대화하는 Ri를 구하면 됨.

옆에 저기는 Si로 표현 할 수 있는데 걔는 곧 weight를 대각성분에 포함하는 대각행렬과, pi의 곱으로 나타나게 됨.

트레이스 RiSi를 최대화 하는 Ri는 RiSi가 symmetric positive definie일 때 얻어진다고 합니다. 그래서 SVD를 사용하면 아래와 같이 Ri를 구할 수 있습니당. Shape matching problem 임.

2.2 The local Rigidity Energy

위에서 쓴 식은 이제 한 cell에 대한 rigidity를 측정한 거였다면 이제 모든 cell에 대해서 rigidity를 구해서 더하면 전체 mesh에 대한 식이 나오게 됨. 이때 wi는 cell마다 정해지는 weight값이고, wij는 한 cell 안의 각 edge마다 주어지게 되는 weight 값임.

잘 관찰해보면 이 에너지 function은 vertex position에 대해서만 의존한다는 것을 알 수 있음. 특히 변하는것은 p' 밖에 없고 Ri는 p'에 따라 변함. 따라서 이 에너지 function은 변형 후 vertex position인 p'에 따라 변함.

그리고 이 weight 값을 선택하는게 중요한데.

Edge 같은 경우는 cells의 non-uniformly shaped cell인 경우 보정을 좀 해줘야 하기 때문에 아래와 같은 코탄젠츠 웨이트를 줍니다. 여기서 알파 베타는 선택한 에지의 반대편에 있는 각이고, 이 각도가 구십도에 가까울수록 웨이트가 0에 가까워짐.

그리고 cell energy는 cell area에 비례하기 때문에 wi=1로 두거나, 아니면 voronoi area 값을 주고 wij를 1/A로 줘서 cancel out 시켜버림

3.Modeling Framework

E(S')을 최소화하기 위한 p'를 찾아야 하는데 사실 우리는 {Ri}도 모름. 그러니까 E(S')는 P', {Ri}에 대한 function이고, 이 두 set이 변함에 따라 minimum Energy를 찾아야 함.

자 그러기 위해서는 두 stage 으로 나눠서 푼다.

Ri optimization: p'가 주어졌다고 가정하고 {Ri}를 구한다 이건 앞에서 했던 거임.
P' optimization: {Ri}가 주어졌다고 가정하고 P'를 구한다. 이건 에너지 E(S')의 gradient를 구해서 해결하는데, E(S')를 P'에 대해서 편미분 하면 된다. 근데 잘 보면
이 에너지 Function은 원래 각 Pi를 중심으로 하는 셀 내부에 대한 식을 n개 다 합한 것인데
이때 Pi에 대해서 편미분하면 이 pi가 들어가는 식 말고는 다 0으로 날아가고, pi가 들어가는 식만 남게 됨.
그런데 overlap이 있기 때문에 pi는 자기가 중심인 cell 말고도 인접한 cell에서도 등장하게 됨.
그러니까 첫번째 텀은 pi가 중심인 cell에서 나온 텀이고 두번째 텀은 인접한 점들이 중심인 cell에서 하나씩 나온 애들을 모아서 표현한 것.
그래서 두개의 텀이 나오게 되고, 예를 미분해서 잘 정리하면 다음과 같은 식이 됨다.(8)

그러면 이 식은 Laplace-Beltrami operator를 적용한 것 과 같다.

그러면 Lp'=b 의 식으로 나타나게 됨.

그리고 이게 유저가 interactive하게 모델링하는 상황이기 때문에 constrained vertice가 있음. 잡고 움직이는 handle이랑 고정시켜둔 점이랑. 걔네는 왼쪽에서 해당하는 row, column 지우고, 오른쪽에는 값을 넣어주면 됨.

{Ri}가 오른쪽, 그러니까 linear system에서 b에만 영향을 미치기 때문에, L은 변하지 않는다는 것을 알 수 있는데, 그말인 즉슨, 시스템 매트릭스 L은 처음에 한번만 계산해두면 된다는 뜻임.

그리고 이 계산할 때 p'는 x,y,z 로 이루어진 3개의 column을 가지고 있으니까 3번의 back-substitution만에 계산이 가능하다고 한다.

이제 요약하면

Cotangent로 Weight 구하고
Sys matrix를 prefactorize하고
Initial guess로 p0를 정하면 Ri 구하고
Ri 써서 P1' 구하고. 반복
E Minimize 할 때 까지(수렴)

4. Result and Discussion

결과는 보시다시피, 자연스러운 deformation이 생겼음. 각 local파트마다 적절한 rotation이 계산되었기 때문. 그리고 최근 방식과 비교했을 때 잘 됨 특히 handle translation이 적용되었을 때.

푸아송 에디팅 방식과 비교하면 푸아송에서는 rotation 을 계산할 수 없음.그래서 detail destortion일어남.

얘네 최적화 안된 코드였고, 스피드업 하려면 이런 방법들 쓰면 됨

그리고 제일 중요한건 initial guess인데 이때 여러가지를 써볼 수 있음.

1) 이전 frame 값 이용

User interactive 하다는 뜻은 handle movement나 deformation이 continuous 하다는 뜻임. 그러므로 이전 프레임 값을 써도 문제가 없음

2) Naïve Laplacian Editing

비슷한 minimization을 쓰는데, 이걸 guess로 하면 large deformation에서는 distorted 결과가 나오지만 그래도 몇번 반복하면 회복함. 다만 심하게 distorted 된 경우는 시간이 오래 걸림

3) 그리고 핸들 자체가 회전할 떄는 이런방법들을 쓸 수있다.

흥미로운 property는 뭐냐면 Edge Length가 보존된다는 것이다.

그래서 에러를 측정해봄. Stretching involved 된 경우 빼면 에러 작다

5.Conclusion

결과적으로 튼튼하고 간단하고 효율적이다. 수렴하는게 중요한데 각 step에서 에너지가 증가하지 못하게 막아놨으므로 수렴한다. 그리고 수렴하는 데에 걸리는 iteration은 mesh 수가 증가할 수록 좀 불안정해지고 더 많은 iteration이 필요함. Volumetric cell로 바꾸는것도 쉬음.