형상차이 기반홀 패치의 파라미트릭 블렌딩 기법

오직 한 개의 인접한 삼각형을 갖는 에지를 경계 에지라고 부른다. 만약 정점에연결된 에지들 중 경계 에지가 존재한다면 그 정점은 경계 정점이라고 부른다. 홀은 경계 에지들로 이루어진 닫힌 경로이다. 한 개의 정점에 연결된 모든 에지들을 그 정점의 1-링 에지라고 부른다. 정점의 1-링 에지들이 갖는 정점들(자기 자신 제외)을 그 정점의 1-링 정점이라고 부른다. 2-링 정점은 1-링 정 점들 중 각 정점의 1-링 정점을 조사함으로써 구할 수 있다. 이와 유사하게, 경계의 N-링 정점 또한 구할 수 있다(Figure 2 참조). 알고리즘을위해 본 논문에서는 경계의 1, 2-링 정점을 살펴본다. 원래 메쉬와 홀을 채우는 메쉬는 각각 주변 메쉬와 홀 패치라고 부른다. 본 논문에서는 다양체(manifold) 메쉬만을 다룬다. 또한 삼각 메쉬를 표현하기 위해 Kettner [19]가 제안한 하프에지(half edge) 자료구조를 활용한다. 삼각 메쉬에 대한 하프에지 자료구 조는 메쉬의 기하학적 연결 정보를 실시간으로 빠르게 얻을 수 있다. 앞서 설명한 개념들을 이용하면 메쉬의 홀을 빠르고 쉽게 검출할 수 있다. 특히, Pernot [14] 등은 만족스럽지 않은 홀 패 치가 생성될 것을 방지하기 위해 홀을 채우기 전에 홀 경계를 다 듬었다. 하지만 본 논문에서 제시된 기법은 복잡한 홀을 다룰 수 있기 때문에 홀 삼각화를 위한 전처리 단계를 생략할 수 있다.

Figure 2: A hole and N-ring vertices.

Download Original Figure

홀 검출이 완료되면, 홀에 완전히 맞는 초기 홀 패치를 생성하기 위한 삼각화 과정을 시작한다. 본 논문에서는 AFM 기법 [12]의 간략화된 버전을 사용하는데, 이는 다음과 같이 몇 가지 단계로 구성된다.

이 방식을 사용함으로써 우리는 복잡하고 곡률이 큰 경계에 꼭 맞는 패치를 빠르고 쉽게 생성할 수 있다. 새롭게 생성되는 패치 안의 삼각형들은 거칠지만, 이어지는 세분화 단계에서 이러한 문제점은 자동적으로 해결된다. Figure 1(c)는 거친 삼각형들을 규칙적으로 만든 결과를 보여준다.

초기 패치 메쉬의 품질 향상을 위해 세분화 과정을 진행한다. 경계 에지를 제외한 내부 에지들은 매우 길며, 삼각형들은 비등방성 성질을 갖는다. 우리는 이러한 문제점을 해결하기 위해 점진적 리메싱 알고리즘을 채택한다 [3, 20, 21]. Algorithm 1은 목표 에지 길이를 입력으로 취하고, 에지 분할, 에지 제거, 에지 플립, 정점 이동을 순차적으로 수행한다.

목표 에지 길이 l은 경계 에지의 평균 길이로 정하고, 세분화후 패치와 주변 메쉬를 병합하기 위해 경계 에지를 분할 후보에서 제외한다. 에지 분할 단계에서는 임계 길이 high보다 긴 에지를 분할한다. 에지 제거 단계에서는 임계 길이 low보다 짧은 에지는 제거하고, 만약 제거하여 임계 길이 high보다 긴 에지가 생성될 경우, 에지를 제거하지 않는다. 모든 에지 길이가 l에 근접하고 삼각형 밀도가 주변 메쉬와 비슷하며 규칙적인 삼각형을 가진 패치를 얻을 때까지 알고리즘을 반복 수행한다. 품질이 향상된 홀 패치는 공정화 단계의 입력으로 사용된다. Figure 3은 알고리즘의 반복 수행 결과를 보여준다.

Figure 3: Process of incremental remeshing: (a) initial patch, (b) 1 iteration, (c) 3 iteration, (d) 5 iteration.

Download Original Figure

세분화후홀 패치 정점의위치를 재조정하고 부드럽게 만들기위한 공정화(fairing) 과정을 시작한다. 공정화는 공정 에너지(fairness energy)를 최소화함으로써 곡면을 가능한한 부드럽게 만드는 기술이다. 최소화하려는 공정 에너지 함수에 따라 최종적으 로 원하는 곡면을 생성할 수 있다 [3]. 본 논문에서는 멤브레인 (membrane) 에너지, 씬플레이트(thin-plate) 에너지, 곡률 변화율 (curvature variation) 에너지중에서 곡률 변화율 에너지에 초점을 맞춘다.

매개변수 곡면 x(u, v) : Ω → S의 멤브레인 에너지는 다음식으로 표현될 수 있으며 디리클레(Dirichlet) 에너지라고도 불린 다:

여기서 x_u = ∂x/∂u 이고 x_v = ∂x/∂v이다. 곡면의 좌표 함 수 x(u, v)를 삼각 메쉬 정점의 좌표 x = (x₁,…, x_n)^T 로 대체하고, 이산 라플라스-벨트라미(Laplace-Beltrami) 연산자를 사용함으로써 위의 연속적인 영역의 공식을 삼각 메쉬로 이산화한다. 따라서 미지의 정점의 좌표 x에 대하여 다음이산 라플라스 방정 식을 풀 수 있다:

여기서 Δ는 이산 라플라스-벨트라미 연산자이며 x^*는 경계 조건 ∂Ω을 만족하는 알려진 정점의 좌표이다. Figure 4에서 삼각 메쉬 위의 한 정점 v_i를 공유한 n개의 삼각형을 가정하자. 국소 영역 [22] A_i를 갖는 v_i에 대한 이산 라플라스-벨트라미 연산자는 다음과같이 정의된다:

Figure 4: Local area and angles for the Laplace-Beltrami operator.

Download Original Figure

f는 정점의 좌표의 x, y, z 성분 중 하나가 될 수 있다.

만약, 곡면의 곡률을 최소화하는 것이 목적이라면 다음 씬플레 이트 에너지 함수를 사용한다:

Ẽ_TP(x)를 최소화 하기 위한 이산 라플라스 방정식은 Δ²x = 0, x |_∂Ω = x^* |_∂Ω 이다. 또한, 곡률의 변화율이 최소화된 곡면을 얻기 위해 Moreton 등 [23]이 제시한 곡률 변화율 에너지를 사용할 수 있다:

여기서 κ₁, κ₂는 주곡률이고 t₁, t₂는 그에 대응되는 주방향이다. Ẽ_CV(x)를 최소화 하기 위한 이산 라플라스 방정식은 Δ³x = 0, x |_∂Ω = x^* |_∂Ω이다.

Figure 5은 홀 패치 메쉬의 공정화 결과를 보여준다. Figure 5(a) 에서는 홀 패치의 경계 정점들이 고정되어 C⁰ 경계 조건이 만족 되고, Figure 5(b)에서는 경계 정점과 경계의 1-링 정점이 고정 되어 C¹ 경계 조건이 만족되고, Figure 5(c)에서는 경계 정점과 경계의 1, 2-링 정점이 고정되어 C² 경계 조건이 만족된다. 우리 는 이 중에서 주변 메쉬의 형상을 가장 잘 반영하는 곡률의 변 화율이 최소화된 곡면(Figure 5(c))을 블렌딩을위한 타겟 패치로 사용한다.

Figure 5: (a) A hole patch by minimizing memebrane energy(Δx = 0), (b) A hole patch by minimizing thin-plate energy(Δ²x = 0), (c) A hole patch by minimizing curvature variation energy(Δ³x = 0).

Download Original Figure

타겟 패치에 라플라시안 스무딩을 적용하여 블렌딩을 위한 소스 패치를 생성한다. 타겟 패치 각각의 정점 v_i에 대하여 다음 umbrella 연산자를 사용하여 정점의위치 v′_i을 계산한다:

여기서 이고, $W(v_i)={\displaystyle \sum _{{\text{v}}_j\in N_1\left({\text{v}}_i\right)}w(v_i,v_j)}$이다. 본 논문에서는 타겟 패치의 삼각형의 모양을유지시키기 위해 다음과같은 cotangent 가중치 [24]를 사용하였다(Figure 4 참조):

타겟 패치의 삼각형 모양을 유지시켜주는 라플라시안 스무딩을 적용하여 소스 패치를 생성함으로써 패치간 자연스러운 블렌딩 방향을 설정할 수 있다.

소스와 타겟 패치 메쉬를 각각 S와 T 라고 하자. S와 T 의 형상 차이를 계산하기 위하여 각각의 메쉬에 대해 이산 곡률 분석을 할필요가 있다. 메쉬 위의 한 정점 v_i 의 좌표가 x_i일 때 v_i 에서의 평균 곡률의 절대값 H_i 은 다음과같이 계산될 수 있다:

여기서 Δ는 이산 라플라스-벨트라미 연산자이다. 그리고 S 와 T 는 동일한 정점의 수와 연결 정보를 가지며 정점간의일대일 대응 관계가 성립한다. 대응되는 정점 v_i 와 v′_i 의 형상 차이는 다음과 같이 계산될 수 있다:

여기서 Δκ_i는 두 정점의 곡률 차이 $(\Vert H_i^S-H_i^T\Vert )$이고, d_i는 정 점간 변위$(\Vert p_i^S-p_i^T\Vert )$이다. 0 ≤ α ≤ 1는 사용자 정의 파라미 터이다. 만약 α = 0이라면 형상 차이는 오직 곡률의 차이에만 비례한다. 반면 α = 1이라면 형상 차이는 오직 변위에만 비례한 다. 사용자는 α를 조절함으로써 패치간의 형상 차이를 계산할 수 있다. Figure 6는 홀에서 생성된 소스-타겟 패치와 그 둘의 형상 차이를 컬러맵을이용하여 가시화한 결과를 보여준다.

Figure 6: (a) Target patch T (right) by fairing, source patch S by applying Laplacian smoothing to target patch(left), (b) Color-coded shape difference between S and T

Download Original Figure

소스-타겟 패치는 형상은 다르지만 모든 정점에 대해 일대일 대 응관계가 성립하기 때문에 형상 블렌딩이 가능하다. 제어 파라미터 w 에 따라 소스 패치 S 와 타겟 패치 T 사이에 다음 선형 블렌딩을 적용하면 새로운 패치 P 를 합성해낼 수 있다:

제어 파라미터 w가 0 ≤ w ≤ 1 인 경우, P 는 S 와 T 의 보간법 (interpolation) 의해합성된다. 반면 w < 0 또는 w > 1인 경우, P는 S와 T 의 보외법(extrapolation)에 의해합성된다. 본 논문에서는 제어 파라미터 w 를 정점별로 재매개화하여 변형 파라미터 ${\widehat{w}}_i$ 를 정의하였다:

적절한 ${\widehat{w}}_i$를 설정하기 위해 각각의 정점 v_i에 대하여 패치 사이의 형상 차이 σ_i를 계산한다. 만약 형상 차이 σ_i가 크다면, 이는 정점 v_i 주변에서 패치 메쉬의 형상의 변화가 크다는 것을 유추할 수 있다. 형상 차이가 큰 정점 v_i는 상대적으로 홀 패치의 중요한 특 징을 표현한다고 해석 할 수 있다. 따라서 이러한 정점들은 변형 파라미터를 더 크게하여 블렌딩 과정에서 더욱 강조되도록 한다. 만약 한 정점에서 σ_i = 0, 즉 형상차이가 거의 없다면 변형 파라 미터 ${\widehat{w}}_i$는 w와 같다. 반면 σ_i = 1, 즉 형상차이가 큰 정점에서는 ${\widehat{w}}_i$ = 2w이므로 소스-타겟간 형상 차이가 강조된다(Figure 7참 조).

Figure 7: 3D graph of reparameterization by shape difference σ.

Download Original Figure