[논문리뷰] Mean Value Coordinates for Closed Triangular Meshes

논문: Mean Value Coordinates for Closed Triangular Meshes

저자: Tao Ju, Scott Schaefer, Joe Warren

 

https://people.eecs.berkeley.edu/~jrs/meshpapers/meanvalue.pdf

 

대학원 인턴 생활을 하게 되었습니다.
연구 baseline에서 자주 사용되는 MVC에 대한 개념을 이해하고, 이를 직접 구현해본 경험을 아래 작성해두었습니다.

 

---

컴퓨터 그래픽스에서 mesh는 본질적으로 vertex들의 집합으로 볼 수 있습니다. 그렇기에 많은 정보들 (위치, uv, ...)이 버텍스별로 할당되어 있고, 이 값들을 "확장" 혹은 "보간" 하는 것은 그래픽스에서 근본적이고, 중요한 목표입니다. 대표적으로 상단의 그림에서 outline으로 표시된 제어 메쉬 (앞으로는 Cage, 케이지 라고 부르겠습니다.)를 변형하면 내부의 모델(정보) 들 또한 변형된 케이지를 바탕으로 보간시키는 Mesh Deformation을 구현하는데 사용될 수 있습니다.

이 논문에서 제안하는 3D MVC는 이런 목표를 달성할 수 있게 해주는 강력한 도구입니다.

기존에 볼록(convex)한 도형에서는 Wachpress 좌표계등이 사용되었지만, 해당 좌표계는 도형 외부에서는 정의되지 않고, 오목한 도형에서는 내부에서도 정의되지 않는 한계가 있었습니다. 이런 문제를 해결하기 위해서 https://www.mn.uio.no/math/english/people/aca/michaelf/papers/barycentric.pdf

위 논문에서 2D에서 적용되는 Mean Value Coordinate 라는 개념이 제시되었고, 이는 오목,볼록한 모든 도형들에 대해서 잘 적용될 뿐만 아니라 도형 외부에서도 매끄럽게 보간되는 특성을 지니고 있었습니다.

Floater's interpolant weight function

위에 제시된 가중치를 보시면 거리가 멀수록 영향력이 줄어들고, 이웃한 정점들과의 사잇각이 클수록 (평평한 구간에 있을수록) 영향력이 높아지는 걸 알 수 있습니다 . 현재 리뷰중인 Mean Value Coordinates for Closed Triangular Meshes 논문은 이 개념을 3D로 확장시키는 방법을 제시했습니다.

 

3차원 공간에 존재하는 Closed Surface P가 있을때 p[x]는 해당 표현을 parameterization한 표현이라고 정의하겠습니다. 이 문단에선 x는 2차원 벡터입니다. (예: 위도, 경도로 지구 위의 한 점을 표현할 수 있듯이 x벡터를 다루는 p[x]로 표면을 정의할 수 있습니다) 우리의 목표는 표면상에서 f[x]로 표현되는 어떤 임의의 함수를 표면이 아닌 곳(v로 표기하겠습니다), 곧 v값을 만들어 내는 함수를 만드는 것입니다. 이 함수는 원본 위치 p[x]를 넣으면 f[x]가 나와야하는 성질을 만족해야 합니다

임의의 점 위에서 동작하는 hat{f}[v]

 

이 논문에서의 핵심 아이디어는 해당 값을 계산하기 위해서 가중 평균 형태로 일반화하고, 그 가중치를 v와 표면까지의 거리의 역수로 사용한다는 것입니다. 이 말은 가까운 표면상의 f[x] 가 더 많은 영향을 끼지고, 먼 표면상의 f[x]일수록 영향을 적게 미친다는 의미입니다

가중치 w

논문은 가중치와 f[x]의 곱을 v를 중심으로 한 단위구 S에 투영시킨 뒤 뒤 해당 값을 적분하고, affine invariance(p[x]가 이동, 회전, 크기 변형이 되어도 동일한 값이 나오는 성질) 를 만족시키기 위해 가중치의 합으로 나눕니다. 

hat{f}[v]

보시면 이 수식은 적분으로 이루어져 있고, 다음과 같은 성질을 만족합니다

 

- Interpolation (보간) : v가 p[x]에 가까울수록 hat{f}[v]도 f[x]에 가까워집니다

- Smoothness (매끄러움) : 표면 P가 아니여도 잘 정의되어 있으며 매끄럽습니다

- Linear precision (선형 정밀도) : 모든 x에 대해서 p[x] = f[x] 라면 모든 v에 대해서 hat{f}[v]는 정확히 v입니다

 

이 공식은 수학적으론 훌륭하지만, 실제 컴퓨터에서 사용하려면 이를 이산적인 조각별 선형 형태 (discrete piecewise linear), 즉 closed-form solution으로 유도해야합니다

 

---

 

우선 저자들은 위에 표현된 공식이 맞는지 검증하기 위해 2D 다각형의 선분에 대해 적용해보겠습니다. 표면을 parametrize 하듯이 선분을다음과 같은 형태로 표현할 수 있습니다

 

2D에서의 증명이니 단위원 S_v를 사용하고, 선분 E를 단위원에 투영한 원호를 Bar{E} 라고 하겠습니다. 그럼 Bar{E}에 대해서만 적용된 적분 공식을 다음과 같이 작성할 수 있습니다

 

저자들은 여기서 w_i를 계산하기 위해서 다음과 같은 항등식을 도입합니다

 

이 수식을 잘 보시면 m은 원호 Bar{E}에 대한 바깥방향 유닛 노말(outward unit normal)의 적분임을 알 수 있습니다. 저자들은 이 m을 Bar{E}의 mean vector라고 부르기로 했습니다. (이 벡터를 원호의 크기로 나누면 원호의 centroid - 무게중심을 생성하기 때문입니다)

수식 5번의 항등식은 w_i에 4번에서 정의된 w_i를 집어넣어 보시면 유도 가능합니다.

 

이 m은 삼각법을 사용해서 다음과 같은 형태로 표현 가능합니다. 증명은 접은 글로 적어둘테니 필요하신 분들은 확인하시기 바랍니다

증명

 

m은 기하학적 대칭성때문에 두 단위벡터간 사잇각을 이등분하는 방향입니다.

이 말은 곧 m = k(u_1 + u_2) 로 표현 가능하다는 의미이기도 합니다 (u_1, u_2는 아래 수식에서 (p_i - v) / |p_i - v| 꼴로 표현된 단위벡터입니다)

 

보다 이해하기 쉽게 m을 x축에 오도록 좌표계를 회전시키면 u_1, u_2는 삼각함수에 의해 다음과 같은 꼴로 표현 가능합니다

u_1 = cos(-a/2), sin(-a/2)

u_2 = cos(a/2), sin(a/2)

이 합은 2cos(a/2), 0 으로 표현됩니다

 

이후 m을 실제로 적분해보면 x축 대칭이니 y 성분 적분은 0이 자명하므로 넘기도록 하고,

x축에 대해선 -a/2 부터 a/2까지의 cos적분이니 삼각함수의 적분공식에 의해서 sin(a/2) - sin(-a/2) = 2sin(a/2)입니다

 

k(2cos(a/2), 0) = 2sin(a/2), 0 이므로 k = sin(a/2) / cos(a/2) = tan(a/2)입니다 

이 공식을 다시 5번 수식에 집어넣으면 w_i 는 tan[a/2] / |p_i - v| 임을 알 수 있고, 이건 수식 2번, Floater의 가중치 함수 중 한개의 선분어치의 표현과 잘 들어맞습니다. (수식 2번은 한개의 점 p[j]가 제공하는 최종 가중치이고 이는 곧 점에 연결된 두 선분에서의 각 가중치의 합입니다)

수식 4번을 다시 보시면 적분을 이산적인 표현으로 바꾸어 내신걸 보실 수 있습니다. 이걸 모든 선분 k에 대해서 적용한다면 임의의 점 v에서의 가중치는 다음과 같이 표현할 수 있습니다.

 

이로써 우리는 closed form으로 표현된 hat{f}[v] 계산식을 얻게 되었습니다. 이제 저희의 목표는 2D가 아닌 3D로 넘어가 closed mesh에 대해서도 적용됨을 증명하는 것입니다. 이 부분이 이 논문의 핵심 기여입니다.

 

---

2D와 비슷하게 저희는 단위구 S에 대한 삼각형 T 투영에서부터 시작합니다

저흰 이걸 직접적으로 적분 계산하지 않기 위해 수식 5번을 거꾸로 뒤집어, 다음과 같은 수식으로 표기합니다.

이제 우리의 목표는 mean vector m을 표현할 수 있는 explict한 표현을 찾는것이고, 이는 아래 Theorem에서 증명됩니다

 

Theorem 3.1. 곡면 삼각형T에서 θ_i 를 i번째 원호의 길이, n_i를 i번째 원호에 대한 inward 단위 법선이라고 하면 다음과 같이 곡면 삼각형 T의 바깥 방향 단위 법선의 적분, m을 정의할 수 있습니다.

증명은 접은 글에 적어두겠습니다

증명

 

Figure 3.b를 이루는 구면 삼각형을 포함한 입체 도형에선 기본 정리에 따라 (가우스의 발산 정리에서 파생됨, 더 자세히 알고 싶으시다면 논문의 레퍼런스를 확인해주세요) outward unit normal의 적분값은 항상 0입니다. 우리는 단위구 투영면에 대한 적분값은 모르지만 옆면의 적분값은 부채꼴의 넓이공식에 의해 (S = 1/2rl) 구할 수 있습니다. 한 면의 넓이는 곧 1/2(θ_i)(-n_i) 이고 이 값들의 합과 m의 합은 0이여야 하므로 m -∑{1/2}{θ_i}{n_i} = 0 이 성립합니다

증명완료

위 수식을 보시면 2D에서도 m은 inward unit normal의 가중합으로 표현되듯이 3D에서도 쐐기면의 inward unit normal의 가중합으로 표현되는 것을 알 수 있습니다. 3D에서의 가중치 θ_i의 길이는 해당 원호를 이루는 p_{i-1} 와 p_{i+1}의 유닛 벡터가 이루는 각으로 표현되고 n_i 는 유닛 벡터들의 cross product(외적)으로 형성됩니다. 이제 우리는 7번 수식을 역행렬 계산 없이 다음과 같은 형태로 표현 가능하게 되었습니다!

 

여기서 주의할 점은 S_v에 삼각형을 투영할때 메쉬 외부에 있거나 오목한 지점에 있다면 방향이 뒤집히게 되는데요, linear precision 속성을 보장하려면, 이런 뒤집힌 삼각형들은 반드시 음수의 가중치를 가져야합니다. 만약 삼각형이 항상 일관된 순서로 유지된다면 (예: 반시계 방향) 

- 단위구 투영시 orientation이 유지된다면 m은 T를 향하는 방향으로 뻗어나갑니다

- 단위구 투영시 orientation이 뒤집힌다면 m의 방향이 정반대로 뒤집혀 T랑 멀어지는 방향으로 뻗어나가게 됩니다 (쐐기면 안쪽으로 m이 뒤집히게 됩니다)

결국 가중치가 올바른 부호를 가지게 되는 것이죠.

 

---

이제는 위에서 꺼내온 수식들을 어떻게 계산할지를 다루도록 하겠습니다.

우리는 이제 다음과 같은 순서로 계산하면 됩니다

 

1. 수식 8을 통해 mean vector m을 계산합니다

2. 수식 9를 통해 weight를 계산합니다.

3. 수식 6에 정의된 hat{f}[v] 의 분자와 분모를 계산된 weight를 사용해 업데이트 합니다.

 

이대로 잘 풀리면 좋겠지만 두가지 해결해야 할 문제가 있습니다. 우선 첫번째, 임의의 점이 삼각형을 포함하는 평면상에 존재한다면 분모가 0이 되는 상황이 발생합니다 [공면] . 두번째, 단위구에 삼각형이 너무 작게 투영되면 노말들이 거의 공면상에 존재하게 되고, 이 수치가 수식 8, 9 같은 곳에 적용될때 부동소수점 표현의 한계 때문에 유효한 숫자가 상쇄되거나 분모가 0에 가까운 숫자가 되는 현상이 발생할 수 있습니다 [수치적 안정성]. 이런 문제를 해결하기 위해서 논문에서 저자들은 각 문제를 다음과 같은 방법들로 해결합니다.

 

수치적 안정성 문제를 해결하기 위해서 저자들은 9번 수식에 8번 수식을 집어넣어 버리고 삼각법을 이용해 아래와 같은 안정적인 수식을 도출해냅니다. 아래 공식에서 ψ_i 는 구면삼각형의 각을 의미합니다. 이 공식을 증명하는 과정은 구면삼각법에 대한 이해가 필요하니 이번 리뷰에선 넘어가도록 하겠습니다.

저자들은 코사인 값을 유닛 노말 계산 없이 이끌어 내기 위해 구면삼각형에서의 반각 공식을 활용해서 도출하는 방법 또한 제시했습니다.

 

이렇게 되면 저희는 가중치 w를 계산하기 위해서 오로지 |p_i - v| 와 θ_i만 필요하게 되었습니다. 참고로 코드 상에서 각도를 구할땐 아크사인을 사용했는데요, 이게 작은 각에서도 안정적으로 동작한다고 합니다.

 

공면 문제를 해결하기 위해 저자들은 공면 상황을 두개로 나누었습니다. 우선 삼각형 내부에 임의의 점이 존재한다면 이건 그냥 일반적인 삼각형 내부에서의 보간 공식을 사용합니다 (barycentric coordinate). 공면이긴 하지만 삼각형 외부에 임의의 점이 존재한다면 아래의 수식처럼 적분으로 표현된 가중치 표현에서 단위구에 투영된 삼각형은 선분(정확히는 원호) 혹은 점이 되므로 d\Bar{T} 가 0이 되어 가중치 자체를 0으로 처리하면 됩니다.

단위구 투영이 원호면 적분 영역이 0이 되어 곧 적분값 w_i 또한 0이 됩니다.

 

위 내용이 적용된 수도코드는 다음과 같습니다

 

파이썬으로 구현한 코드는 아래 리포지토리에서 mean_value_coordinate.ipynb 의 MVC_weight_vectorized 함수를 확인해보실 수 있습니다.
https://github.com/Junhyung-Choi/Mesh-editing-with-pyopengl

GitHub - Junhyung-Choi/Mesh-editing-with-pyopengl: experiments for mesh editing

 

 

해당 논문은 대표적으로 케이지 기반 메시 변형에 사용될 수 있는데요, 엉성한 메시(케이지)와 변형하고 싶은 메시(소스)를 준비합니다. 이후 f[x]를 p[x]로 설정하고 뒤에 소스 메시의 버텍스별로 전부 MVC를 활용해 가중치를 미리 계산해두면 f[x]값에 변형된 p[x]를 넣어서 그에 맞춰서 같이 소스 메시를 변형시킨 결과를 확인할 수 있는것이죠! 

 

 

---

 

이렇게 첫 논문 리뷰를 작성해 보았습니다. 처음 해보는 대학원 생활에 처음 해보는 논문 리뷰라 부족한 점이 많은 것 같습니다.

더 열심히 해야겠다고 다짐이 드는 하루입니다