블렌드쉐입을 위한 다수 삼각 메쉬의 동시 단순화 기법

지금까지 다양한 얼굴 애니메이션 기술이 개발되어 왔다. 그 중전통적인 방식인 키프레임 사이에 선형 보간법을이용하여 중간 프레임을 생성하는 방식은 Parke와 Frederick [3]가 처음으로제안하였다. Lewis 등 [4]은 블렌드쉐입 기법을위상적으로 일치하는 여러 형상의 선형 가중치 합으로 설명하면서 슬라이더인터페이스를 이용하여 가중치를 조절하는 예를 보여주었다. 타겟쉐입의 모델수가 많거나 모델의 삼각형 수가 많은 경우 얼굴 애 니메이션을 가속화하기 위한 몇몇 연구도 진행되었다. Seo 등 [5]은 대용량의 블렌드쉐입 모델을 압축하여 하드웨어 가속 애니메이션을 수행하는 방법을 다루었으며, 행렬 블록 재정렬(roworder reordering)과 HSS (hierarchically semi-separable) 표현에 기반한행렬 압축 기법을 제시하였다. Costigan 등 [6]은 GPU에 블렌드쉐입 모델을 저장함으로써 속도가 향상되는 애니메이션 기법을제시하였다. 아직까지는 얼굴 애니메이션 처리를 가속화하기 위한 타겟쉐입을 동시적으로 단순화하는 연구는 진행되지 않은 상황이다.

본 논문에서 제시하는 알고리즘의 목표는다수의 폴리곤모델을동시에 단순화하며 위상을 같게 유지하는 것이다. 지금까지 많은 종류의 메쉬 단순화 알고리즘이 제안되었다. Schroeder 등 [7] 은 국소적 지오메트리를 검사하면서 정점을 점진적으로 제거하였다. [8]에서는 메쉬표면 위에 새로운 정점을 생성하고곡률이높은 영역에서 많은 정점을 분포시키며메쉬를 재구성(re-tiling)하는 방법을 제시하였다. 이 방식은 날카로운 모서리를 가진 메쉬보다는 비교적 매끄러운 표면으로 이루어진 메쉬에 적합하다. Kalvin과 Taylor [9]는 삼각형을 병합하는 방식으로 단순화를 수행했다. 이 방식은 얼굴 모델보다는 날카로운 모서리를 많이 가진 모델에 더 적합하다. Garland와 Heckbert [10]가 처음으로 2차에러 측정법을이용하여 폴리곤 모델을 단순화하는 알고리즘이제시하였다. [11]에서는 메쉬의 볼륨이 선형적으로 변화하며 단순화가 진행된다. Cignoni 등 [12]은이전 알고리즘의 성능을 분석 비교한 결과를 제시하였다. 메쉬 단순화 알고리즘의 정확도는메쉬의 기하학적 구조나 위상정보 등에 따라 크게 좌우된다. 이후Pauly 등 [13]은 곡률이 높은 영역에 더 많은 정점을유지시키기위해 국소 변이 추정과 2차 에러 측정법을 사용하였다. 그러나 이기법은 메쉬 단순화를 포인트 클라우드 기반에서 수행한다는 점에서 멀티레벨 스무딩, 다중 해상도 모델링과같은 포인트 기반프로세싱 어플리케이션에 더 적합하다. Kim 등 [14]은 곡률이 높고 형상이 얇은 영역에서는 2차 에러 측정법이 정확한 기하학적오차를 측정하는 것이 어렵다는 점을 보완하여 날카로운 형상의영역을 보존하기 위한 단순화 기법을 제안하였다. Ran 등 [15]이제시한 방법은 메쉬의 날카로운 특징을잘 보존한다는 장점이있지만 지역적 들로네(delaunay) 조건이유지되어야 한다는 점에서제한적이다. 본 논문에서는 많은 문헌에서소개된 2차 에러 측정법을이용한 메쉬 단순화를 간략히 소개하고, 다수의 삼각 메쉬에대해 확장하는 기법을 제안한다.

3차원 공간의 한 점 v = [x y z 1]^T 에서 임의의 평면 π: ax+by+cz + d = 0 까지 거리의 제곱(squared distance)은 다음과같이 2차식으로 표현될 수 있다:

여기서 p = [a b c d]^T 는 단위법선(a² + b² + c² = 1)을 갖는 평면π의 동차좌표(homogeneous coordinates) 표현이고, K는다음과같이 계산되는 대칭행렬이다:

Figure 2에서 삼각 메쉬 위의 한 정점 v_i을 공유한 n개의 삼 각형을 가정하자. 메쉬 외부의 한 점 v에서 삼각형을 포함한 각평면까지의 거리 제곱의 합은 다음과같이 계산될 수 있다:

Figure 2: Sum of squared distances between a vertex and planes.

Download Original Figure

여기서 K_j는 각 삼각형을 포함한 평면으로부터 식 (1)을 통해 계산되는 행렬이며, $Q_i={\displaystyle {\sum }_{j=1}^n{K}_j}$는 정점 v_i에서 정의되는 QEM (quadratic error metric) 행렬이라고 한다. 메쉬 단순화 기법에서행렬 Q_i는 한 점 v에서 정점 v_i주변의 메쉬까지의 형상의 차이(에러)를 측정하기 위해서 사용된다.

삼각 메쉬에서 반복적으로 에지를 제거(collapse)함으로써 단순화된 메쉬를 얻을 수 있다. Figure 3은 v₁과 v₂를 양 끝점으로 하는 에지 e = (v₁, v₂)를 제거하는 과정을 나타낸다. 에지 제거 과정은 (1) v₁과 v₂를 v′으로 병합하고, (2) v₂와 연결된 에지를 v₁에연결하고, (3) 사용되지 않는 삼각형을 제거하는단계로 구성된다.

Figure 3: Edge collapse operation.

Download Original Figure

에지 제거로 단순화된 메쉬(Figure 3(b))는 제거 전 메쉬(Figure 3(a))와 형상의 차이를 갖는다. 이러한 형상의 차이는 에지 제거에 따른 비용으로 정의될 수 있으며, 이는 v′에서 제거 전 메 쉬의 삼각형을 포함한 평면들까지의 거리 제곱의 합으로 다음과 같이 계산될 수 있다:

여기서 Q₁과 Q₂는 각각 정점 v₁과 v₂에서 계산된 QEM 행렬이다. 에지 제거 비용은 정점 v′의 위치에 따라 달라지므로 최소의제거 비용을 갖는 v′의 위치는 $\frac{\partial C}{\partial x}=\frac{\partial C}{\partial y}=\frac{\partial C}{\partial z}=0$ 를만족하는해 (x̂, ŷ, ẑ)를 구하여 찾을 수 있다.

메쉬를 구성하는 각각의 에지 e_i에 대하여 제거 위치와 비용으 로 구성된 에지 제거 정보 (e_i, v′_i, C_i)를 구하여 최소힙(min heap)에 저장한다. 최소힙은 에지 제거 비용이 가장 적은 에지를 루트에 유지하므로, 최소힙에서 순차적으로 에지 제거 정보를 꺼내어해당 에지를 제거하면 원본 삼각 메쉬와 형상의 차이를 최소로하는단순화 메쉬를 얻을 수 있게 된다. Algorithm 1은 단일 메쉬에 대한 단순화 알고리즘을 나타내고, Figure 4는 얼굴 메쉬에단순화 기법을 적용한 결과를 나타낸다.

Figure 4: Results of mesh simplification: (a) original mesh, (b) 50% simplicification, (c) 25% simplification and (d) 12% simplification.

Download Original Figure

일반적으로 블렌드쉐입 모델은 중립(neutral) 표정을 갖는 메쉬에서 변형된 다양한 표정을 갖는 메쉬들로 구성된다. 블렌드쉐입을구성하는 메쉬들은 하나의 메쉬에서 변형되었기 때문에 동일한정점의 수와 연결 정보를 공유한다. 다양한 표정들을 갖는 메쉬들을 가중치를 기반으로 선형결합을 하면 새로운 표정을 갖는메쉬를 생성 할 수 있다. 본 논문에서 제안하는 동시 단순화 기법은이러한 제약 조건 즉, 동일한 정점의 수와 연결 정보를 갖는다수의 메쉬들을 대상으로 한다. Figure 5은 본 논문에서 사용한블렌스쉐입 모델의일부 메쉬들을 나타내다.

Figure 5. A set of mesh models for blend shape.

Download Original Figure

제 3절에서 정의한 에지 제거 비용은 에지 주변의 메쉬 형상에따라 달라진다. 따라서 N개의 메쉬가 동일한 정점의 수와 연결정보를 갖더라도, 메쉬의 기하학적 형상이 다르면 각 에지의 제거비용은 메쉬에 따라 서로 다르게 된다. 결과적으로 기존의 메쉬단순화 기법을 브렌드쉐입을 구성하는 각각의 메쉬에 개별적으로 적용할 경우, 제거되는 에지의 순서가 메쉬마다다르기 때문에최종적으로 단순화된 메쉬들은 서로 다른 연결 정보를 갖게 된다. 이러한 결과 메쉬들에 대하여 블렌드쉐입 기법 즉, 가중치를 이용한 선형 결합을 적용할 경우원하지 않는 결과를 초래하게 된다. 본 논문에서는 이러한 문제를 해결하기 위해 N개의 메쉬의 형상을 동시에 고려하여 확장된 에지 제거 정보를 구성하고, 이를기반으로 모든 메쉬에서 동일한 순서로 에지를 제거하는 기법을제시한다.

동일한 정점의 수와 연결 정보를 갖는 N개의 메쉬 집합 𝒨 = {M¹, M², …, M^N}을 가정하자. 메쉬 M^j의 에지 e_i의 제거 비용을 $C_i^j$라고 하면, 모든 메쉬를 고려한 에지 e_i의 제거 비용 C_i는다음과같이 계산될 수 있다:

여기서 w_j는 메쉬 M^j에 대한 에지 e_i의 제거 비용에 대한 가중 치이다. 모든 메쉬에 대하여 가중치가 w_j = 1인 경우, 에지 e_i의제거 비용은 단순히 모든 메쉬에서 해당 에지의 제거 비용을 합한결과와 같다. 본 논문에서는 에지 e_i의 제거 비용의 가중치를 각 메쉬마다 다르게 적용한다. 적절한 가중치 w_j를 설정하기 위해 각각의 메쉬 M^j에 대하여에지 e_i의 제거 비용 $C_i^j$를 계산한다. 만약 제거 비용 $C_i^j$가 모든 메쉬 모델에 대하여 동일하거나 거의유사하다면, 이러한 결과는 에지 e_i주변에서 각 메쉬의 형상이 크게 변형되지 않기 때문이다. 반면, 에지 e_k는 메쉬 모델에 따라 제거 비용 $C_k^j$의 변화가 크다고 하면, 이는 에지 e_k주변에서 각메쉬의 형상의 변화가 크다는 것을유추할 수 있다. 제거 비용의변화가 큰 에지 e_k는 e_i에 비해 상대적으로 각 메쉬들에서 형상의 중요한 특징을 표현한다고 해석 할 수 있다. 따라서 이러한 에지들은 제거 비용을 더 크게하여 단순화 과정에서 제거되지 않도록한다.

각 메쉬에 대하여 에지 e_i의 제거 비용의 표준 편차(standard deviation)를 σ_i라고 하자. σ_i가 작은 에지 e_i는 각 메쉬에서 형상의 변화가 적은 부분에 포함되는 에지이므로 낮은 가중치를 할당하여에지 제거의 순위를 높일 수 있다. 반면, 제거 비용의 표준편차가 큰 에지는 높은 가중치를 할당하여 해당 에지가 제거되지않도록 할 수 있다. 이러한 원리를 적용하기 위해 본 논문에서는다음과같은 표준 편차에 따른 가중치 함수를 이용하였다:

여기서 σ_max는 사용자가 정한 에지 제거 비용의 최대 편차를 나 타내고, 가중치는 0.1 ≤ w ≤ 1의 범위에 포함된다. 확장된 에지 제거 정보는 Figure 6와 같이 각 모델에 대한 에지 제거 비용과가중치 그리고 모든 메쉬를 고려한 제거 비용으로 구성된다. Algorithm 2은 확장된 에지 제거 비용을이용하여 다수의 메쉬에대한 동시 단순화 알고리즘을 나타낸다.

Figure 6. Data structure for extended edge collapse information.

Download Original Figure