Ssong

반갑습니다 :)

[논문] Surface Simplification Using Quadric Error Metrics

Date:     Updated:

카테고리:

태그:


산학연계를 위한 공부를 하던 도중 좋은 논문을 추천해주셔서 공부하면서 정리하려고한다.
요약을 한다고 했지만 워낙 생소한 내용들이 많아 사실상 논문을 번역해 정리했다고 해야하는것 같다.
Abstract부분이 이 논문에서 말하고자 하는 내용을 먼저 설명하기 때문에 요약한 내용과 핵심 키워드들을 가지고 보면서 이해하면 도움이 될 것이다.

Abstract

우리는 다각형 모델의 고품질의 근사치를 빠르게 생성할 수 있는 Surface simplification Algorithm을 발전시켜왔다.
알고리즘은 Vertex pair의 반복적인 축약을 사용하고 Surface error approximation을 quadric matrix를 사용해서 유지한다.
임의의 Vertex pair를 축약하면서 모델의 연결되지 않은 영역도 연결시킬 수 있다.
이것은 시각적으로나 geometric error에 관해서나 approximation을 수월하게 한다.
topological joining을 위해서 우리의 시스템은 non-manifold surface model을 지원한다.

1.Introduction

컴퓨터 그래픽의 응용 프로그램은 설득력있는 사실성을 위해서 매우 복잡하고 디테일한 모델을 요구한다.
따라서 모델들은 이러한 디테일을 만족시키기 위해 고해상도로 만들어지거나 획득된다.
하지만 항상 그러한 복잡한 모델이 요구되는것은 아니다. 왜냐하면 그것의 복잡성은 모델을 사용하는 Cost에 대해 직접적인 관련이 있기 때문이다.
그렇기 때문에 복잡한 모델의 간단한 버전을 사용하는것이 유용하다.
그래서 최근 Surface simplification Algorithm에 대한 연구는 이러한 목적에 초점이 맞춰져있다.

우리는 다각형 모델의 simplification에 집중할것이다. 우리는 모델이 삼각형으로만 이루어졌다고 가정한다. 이것이 일반성의 상실을 의미하는것이 아니다. 원본 모델의 모든 다각형은 전처리 단계를 거쳐서 삼각형으로 표현될수가 있기 때문이다.

우리는 그러한 다각형 모델의 간단한 버전을 생성하는 알고리즘을 개발했다. 우리의 알고리즘은 vertex pairs의 반복적인 축약(edge 축약의 일반화)을 기반으로 한다. 알고리즘을 진행하면서 기하학적 오차 근사는 현재 모델의 각 정점에 유지된다. 이 오차 근사는 quadric matrices를 사용으로 나타낸다. 우리 알고리즘의 주요 이점은 다음과 같다:

  • 효율성: 알고리즘은 복잡한 모델을 꽤 빠르게 단순화할 수 있다.

  • 품질: 알고리즘에 의해 생성되는 근사는 원본에 충실하게 유지된다.
    모델의 주요 특징들은 상당한 단순화 후에도 유지된다.

  • 일반성: 대다수의 다른 표면 단순화 알고리즘과는 다르게 우리는 aggregation 과정을 통해 연결되어 있지 않은 지역도 연결시킬 수 있다. 물체의 topology를 유지하는것이 중요한 관심사가 아니라는 것이 많은 비연결 요소를 가진 모델의 근사를 수월하게 해준다. 또한 우리의 알고리즘은 non-manifold모델 적용도 가능하다.

다각형 표면 단순화의 목적은 다각형 모델 Input을 단순화된 모델 Output으로 발생시키는것이다. 이때의 Input model은 삼각화되어 있다고 가정한다.
target approximation은 원하는 면의 개수 또는 최대 허용 오차와 같은 목표 기준을 만족해야한다.
우리는 multiresolution modeling을 위한 렌더링 시스템에서 사용될 수 있는 Surface simplification Algorithm에 관심이 있다.

예를들어 메디컬 영상 같은 곳에서 물체의 topology를 유지하는것이 중요할 수 있지만 렌더링같은 분야에서의 topology는 전반적인 appearance보다는 덜 중요하다. 알고리즘은 topological holes을 닫는 것뿐만 아니라 비연결 영역도 연결시킬수 있다.

많은 이전의 단순화 알고리즘은 그들의 입력 표면이 manifold 표면으로 남아야 한다고 명시적으로 또는 함축적으로 가정했다. 하지만 우리의 알고리즘은 그러한 가정을 하지 않는다. 왜냐하면 aggregation의 과정에서 non-manifold 영역은 정기적으로 생성되기 떄문이다.

2.1 Surface Simplification

최근 몇년간 표면 단순화의 문제와 multiresolution modeling의 더 일반적인 문제에 대한 관심이 증가하고 있다. 표면 단순화를 위한 몇개의 다른 알고리즘은 공식화 되었다. 그중 우리의 업무와 가장 연관된 알고리즘은 대략 3가지로 분류할 수 있다.

Vertex Decimation

반복적으로 없앨 정점 선택 → 면의 모든 접점 삭제 → 결과를 다시 삼각화

image

장점

  • 합리적인 효율성과 품질을 제공

단점

  • vertex classfication과 삼각화 방식 둘 다 manifold surfaces에 한정되고 모델의 topology를 유지한다.


일부 분야에서 topology 유지는 매우 중요한 특징이지만 multiresolution 렌더링 시스템에서는 제한사항이다.

Vertex Clustering

원래 모델을 격자로 나눈다. → 격자안의 정점들을 단일 정점으로 합친다 → 모델의 면은 그에 맞춰 업데이트된다

image

장점

  • 임의의 다각형 Input을 처리할 수 있다.

단점

  • 구체적인 면의 개수를 설정하는 것이 어렵다. (면의 개수는 격자안에서 결정되는 것)

  • 단순화 결과를 향상시킬 수 있지만, 원하는 품질과 컨트롤을 제공하지 않는다.

Iterative Edge Contraction

몇개의 알고리즘은 Edge의 반복적인 축약에 의해 단순화 된 모델을 발표했는데 이러한 것들과 본질적인 차이는 축약할 Edge를 선택하는 방식에 있다.

image

장점

  • 물체에 있는 hole을 닫을 수 있다.

단점

  • Edge Contraction이 non-manifold면 에서 적용이 가능함에도 불구하고 이러한 알고리즘들은 모두 manifold면에서 사용하기 위해 설계되었다.

  • 연결되지 않은 영역을 연결하지 못한다.

우리가 원하는 효율성, 품질 그리고 일반성을 만족하는 알고리즘은 개발된적이 없다.

  • Vertex Decimation algorithm : 모델 위상을 유지하고 manifold geometry에 기반한다.

  • Vertex Clustering : 일반적이고 계산이 빠르지만 결과를 제대로 컨트롤하지 못하고 품질이 낮을 수 있다.

  • Edge Contraction : aggregation을 제공하지 않는다.

이처럼 앞서 나온 알고리즘들은 저마다의 단점이 있다.

하지만 우리는 단점은 제하고 아래의 장점들을 모두 포함한 aggregation과 높은 품질의 근사치를 보장하는 알고리즘을 개발했다.

  • Vertex Clustering의 일반성
  • Iterative Contraction algorithms의 고품질과 통제능력
  • 고품질의 방법보다 빠른 단순화

3. Decimation via Pair Contraction

우리의 단순화 알고리즘은 Iterative Edge Contraction을 기반으로 한다.

Pair contraction : (\(v_1, v_2\)) → \(v'\)

  1. Vertices \(v_1\) 와 \(v_2\)를 새로운 위치인 \(v'\)으로 옮긴다.
  2. 연결되어있는 Edge를 \(v_1\)으로 연결
  3. Vertex \(v_2\) 삭제

contraction의 효과는 작고 굉장히 localized 되었다.

  1. 만약 (\(v_1, v_2\))가 하나의 edge라면 적어도 1개 이상의 면이 사라진다.
  2. 그렇지 않으면 떨어져있는 영역을 연결시킨다.

image

[Notion of contraction]
여러개의 정점 집합을 단일 정점으로 축약할 수 있다 : (\(v1,v2,..., v_k\)) → \(v'\)
이러한 축약 형태는 pair contraction 뿐만 아니라 vertex clustering까지 일반화된 연산의 형태이다.
하지만 우리는 우리의 알고리즘의 끊임없는 연산을 위해 가장 세밀한 연산을 하는 pair contraction을 사용한다.

초기 모델 \(M_n\)으로 시작해 단순화 목표가 만족되고 최종 근사치 \(M_g\)이 생성될때 까지 계속 pair contraction이 사용된다.
각 축약이 local incremental modification of the current model이므로, 알고리즘은 사실상 모델 시퀀스 : \(M_n, M_{n-1}, M_n,...,M_g\)까지 만들어낸다.
따라서 한번의 실행으로 엄청 많은 수의 근사치 또는 aggressive mesh 같은 multiresolution representation을 생성할 수 있다.

3.1 Aggregation

일반적인 Vertex pair contraction 사용

  • 주된 이익 : 모델의 비연결 지역을 연결시킬 수 있다.
  • 부수적인 이익 : 원본 모델의 메쉬 연결성에 덜 민감하게 한다.

렌더링같은 몇몇 어플리케이션에서는 전반적인 appearance가 topology보다 더 중요하다.

아래의 그림처럼 100개의 큐브들이 reqular 격자에 있는데, 우리가 이 모델에 대해 simplification apporximation을 하고싶다고 가정해보자.

물체의 hole을 닫을수는 있지만 비연결 요소를 연결시키지는 못한다. 하지만 Pair contraction은 individual component를 single object로 병합할 수 있다. 이런 aggregation이 non-manifold surface를 서포트한다. 두 개의 분리된 부분이 붙으면서 non-manifold region이 만들어지기 때문이다.

image

3.2 Pair Selection

좋은 근사화에서 점들은 그들의 원래 위치에서 멀리 움직이지 않는다는 가정을 기반으로 한다.

만약 다음중 하나를 만족하면 Pair (\(v_1, v_2\))가 축약을 위한 유효한 쌍이라고 할 수있다.

  1. (\(v_1, v_2\)) is an edge, or
  2. \(|| v_1, v_2 || < t\) , where t is threshold parameter

t = 0 임계값 사용은 Simple Edge Contraction Algorithm을 제공한다.
이러한 임계값은 신중하게 골라야하는데 만약 너무 높다면 넓게 분리된 부분들이 원치 않게 연결될 수 있다. 그리고 그것은 \(O(n^2)\)의 쌍을 만들어 낸다.

반복적인 축약 과정으로 유효한 쌍의 세트를 추적해야 한다.
(\(v_1, v_2\)) → \(v'\)으로 축약을 진행할 때 \(v_1\)이 \(v_2\)에 연결되어 있던 모든 Edge와 연결될 뿐만 아니라 \(v_2\)의 쌍의 집합 또한 병합이 된다.
유효 쌍 안의 \(v_2\)에서 일어나는 것은 \(v_1\)에 의해 대채되고 복제된 쌍은 제거된다.

4. Approximating Error With Quadrics

반복 수행할 Contraction Vertex pairs를 선택하기 위해서 축약의 Cost를 위한 개념을 정의한다.

정의를 하기 위해서 우리는 각 정점의 Error 특징화를 시도한다 :

  1. 각 정점에 대해 4 x 4 대칭행렬 Q를 구한다.
  2. Vertex \(v = \begin{bmatrix}v_x&v_y&v_z&1\\ \end{bmatrix}\) 에서의 error를 quadratic form(\(Δ(v) = v^TQ_v\))으로 정의한다.

image

주어진 축약 (\(v_1, v_2\)) → \(v'\)에서 우리는 \(v'\)에서의 Error를 근사치로 구하는 새로운 Matrix \(Q'\)을 얻어야만 한다.
이때 \(Q' = Q1 + Q2\)라는 간단한 덧셈 규칙을 이용한다. (Q1, Q2는 각각 v1, v2에 해당하는 Q matrix)

(\(v_1, v_2\)) → \(v'\)로 축약을 하기 위해서 \(v'\)의 position을 골라야한다.
간단한 방법으로는 \(v_1, v_2\) 또는 \((v_1, v_2)/2\) 중에 \(Δ(v')\)을 최소화하는 값을 고를 수 있다.
\(Δ(v')\)를 최소화하는(error를 최소화하는) \(v'\)의 position을 찾는 것이 최선이다. 오차함수 Δ는 quadratic이기 때문에 최소를 찾는것은 linear문제이다.
그래서 우리는
image

위 식을 만족하는 \(v'\)를 찾으면 된다. 이것은

image
이것을 푸는것과 동일하다.

\(v'\)는 항상 homogenerous vector이기 때문에 bottom row는 empty이다. 이 matrix가 invertible하다고 가정하면 우리는 segement v1v2를 따라서 최적의 정점을 찾으려고 할 것이다.
만약 이것 또한 실패하면 우리는 다시 돌아가서 endpoint와 midpoint 사이에 있는 \(v'\)를 선택할 것이다.

image

4.1 Algorithm Summary

우리의 Simplification algorithm은 pair contraction과 error quadrics를 중심으로 해서 만들어 졌다.

알고리즘은 다음과 같이 요약할 수 있다:

  1. 모든 초기 정점들의 Q matrices를 계산한다.
  2. 모든 유효 쌍을 선택한다.
  3. 각각의 유효쌍을 위한 최적의 축약 타겟 \(v'\)을 계산한다. 타겟 정점의 error \(v'^T\)(Q1 + Q2)\(v'\) 는 그 쌍의 축약 비용이 된다.
  4. 모든 쌍을 힙에 위치시키고 최소의 비용인 쌍을 꼭대기에 올린다
  5. 반복적으로 최소비용이 나올때까지 pair(v_1,v_2)를 없애가면서 v1에 관련된 모든 유효쌍의 비용을 업데이트한다.

이제 남은 이슈는 error metric Δ를 만드는 초기 Q matrices를 어떻게 구하는지이다.

5. Deriving Error Quadrics

원본 모델에서 각 Vertex는 평면 집합의 교차점, 즉 해당 정점에서 만나는 삼각형의 평면의 교점임을 알 수 있다.
평면들의 집합을 각 Vertex와 연결할 수 있으며, 이 집합에 대한 Vertex의 Error를 평면에 대한 거리제곱의 합으로 정의할 수 있다.

image

위의 Error metric은 최대값이 아닌 합계를 사용한다.
또한 Vertex의 set of planes는 vertex에서 만나는 삼각형 평면이라고 초기값을 준다.

image

Fundamental Error Quadric Kp는 plane P와 공간 상 어느 점과의 거리의 제곱을 계산하기 위해 사용된다. 그 Fundamental Quadrics를 다 더해서 set of planes를 single matrix Q로 표현한다.

만약 Q1과 Q2로 표현된 집합이 서로소라면 Q1과 Q2의 합집합으로 표현할 수가 있다.
하지만 서로소가 아니라면 서로 겹치는 부분이 생길수도 있는데 각 평면이 삼각형이기 때문에 단일 평면은 최대 3번까지만 겹친다.
이것이 Error측정에 부정확성을 유발할 수 있지만 이점도 있다.

  • 평면 집합을 추적하기 위해 4 x 4 대칭행렬만 있으면 가능하다.
  • 근사치 업데이트 비용이 그러한 행렬을 2번만 더하면 된다.
  • 만약 추가적인 저장공간이 필요하다면 inclusion-exclusion 공식을 사용해 다중 계산을 제거해 공간을 제공할 수 있다.

초기의 Q를 계산하기 위해 Pair Contraction Algorithm이 필요하다, 각 정점은 정점에서 만나는 삼각형 평면을 축적해야한다. 초기에 각 정점은 동일한 삼각형 평면위에 있기 때문에 초기의 Error가 0이다.
각 정점에 대한 평면 집합은 fundamental error quadrics Kp를 정의한다. 그리고 그 Kp의 합이 이 정점에 대한 Error quadrics Q이다.

5.1 Geometric Interpretation

평면 기반 Error quadrics는 꽤 높은 품질의 근사치를 생성한다. 게다가 그것은 또한 기하학적 의미도 가지고있다.

이러한 Quadrics의 The Level Surfaces는 거의 항상 타원체이다. 어떠한 환경에서는 Level Surfaces가 생성이 안 될 수도 있다.

예를 들어 평행한 두 평면은 두개의 평행한 Level Surfaces를 만들고 선분과 평행한 평면은 원통형 Level Surfaces을 만든다.

최적의 정점 위치를 찾는데 쓰이는 행렬은 Level Surfaces가 타원체를 발생시키지 않는한 바뀔 수 있다. 이 경우 \(v'\)는 타원체의 중심일 것이다.

6. Additional Details

알고리즘은 대다수의 모델에서 잘 동작하지만 특정 모델, 특히 열린 경계가 있는 평면 모델에서 성능을 더 향상시키는 개선사항이 있다.

Preserving Boundaries

생성된 Error quadrics는 열린 경계를 허용하지 않는다.
하지만 어떤 모델은 형태 단순화 중에 경계 곡선을 유지할 필요가 있다.

처음에 모든 Edge를 Normal 또는 Discontinuity로 라벨링을 한다. 그리고 Discontinuity Edge로 둘러싸인 면은 그 Edge를 수직으로 관통하는 면을 생성한다.

이러한 제약이 있는 평면은 많은 패널티 요인이 있는 quadrics로 전환된다. 그리고 Edge의 끝점에 있는 초기의 quadrics로 더해진다.

Preventing Mesh Inversion

Pair contrations는 축약의 영역에서의 면의 방향을 보존하는 것이 필요하지 않다.
예를 들어 Edge를 축약해 어떤 이웃하는 면의 Flip이 가능하다.

image

일반적으로 이러한 Mesh Inversion을 피하는 것이 좋다.

축약이 가능하다고 고려되면 우리는 각각 이웃한 면의 법선을 축약 전후로 비교한다.
만약 법선이 Flip되면 축약은 패널티를 가지거나 허락되지 않는다.

6.1 Evaluating Approximations

근사치의 품질을 평가하기 위해 다음과 같은 모델을 정의한다.

image

Xn과 Xi는 모델 Mn과 Mi에서 각각 샘플링 된 점의 집합이다. 거리 d(v,M)은 v로부터 M의 가장 가까운 면까지의 최소 거리이다.

7. Results

우리의 알고리즘은 꽤 짧은 시간내에 원본에 충실한 근사화가 가능하다.

image

왼쪽 그림은 논문에서 예시로 보여준 모델을 사용해 구현한 시간이다.
오른쪽 그림은 샘플의 근사화 순서를 보여주는데, 많은 단순화에도 뿔과 같이 인식할만한 특징이 남아있는것에 주목해야한다. 오직 극도의 낮은 단계에서 디테일이 사라지기 시작한다.

우리는 최적의 정점 배치를 사용하는것이 더 좋은 형태의 Mesh를 생산하는 경향이 있는것을 발견했다.

image

우리의 알고리즘은 축약 후 정점의 위치 최적화를 시도한다.
극히 낮은 수준의 디테일에서 효과는 미미하지만, 합리적인 단계의 디테일에서 효과가 상당하다. 최적의 정점 배치는 약 50%까지 Error를 줄일수 있다.

더 큰 모델에서의 알고리즘 수행을 증명한다.

image

모델의 상당한 단순화를 나타내지만 원본의 모든 주요 디테일은 남아있다.
특히 귀 안쪽의 윤곽과 뒷다리 주변의 큰 윤곽이 보존됐다.
image

모델의 대부분의 디테일이 사라졌지만 원본의 기본 구조는 여전히 온전하다.
매우 단순화됐음에도 불구하고 머리, 다리, 꼬리, 귀와 같은 주요 특징은 분명하다.

Simplification동안 축적된 Error quadrics의 성질

image

각 단계의 표면에는 정점을 중심으로 하는 타원체가 있다. 이때 정점은 타원체 안에서 어디로든 이동이 가능하다.

타원체의 특징

  • 모델 표면의 형태를 잘 표현
  • 평면적인 부분 : 크고 평평
  • 불연속적인 선 : 가늘고 긺

타원체는 정점 주변 지역 표면의 형태에 대한 정보를 축적한다.

Pair Contraction을 통한 Aggregation의 진짜 이익

image

원본 모델은 많은 부분으로 나누어진다. 이때 3가지의 근사화 방식과 비교가 가능하다.

  • Uniform Vertex Clustering
  • Edge Contractions
  • Pair Contractions

image

Edge Contractions만 사용을 하면 비 연결 지역의 연결이 불가능 하기 때문에 발가락의 끝 부분이 사라진다.

image

Pair Contractions를 사용하면 비연결 지역의 연결이 가능하기 때문에 분리된 뼈 조각들을 합칠 수 있다.

Aggregation의 객관적으로 더 낮은 근사화 Error 생성

image

어떤 값을 선택해도 Edge Contraction(t = 0) 보다 더 나은 근사치를 생성한다.

이때 t의 증가가 꼭 더 나은 근사치를 생성 하는 것은 아니다.

8. Discussion

우리의 알고리즘은 기존의 알고리즘에서는 찾을 수 없었던 효율성, 품질, 일반성 모두를 제공한다.

임의의 다각형 모델을 단순화할 수 있는 유일한 알고리즘인 정점 클러스터링은 고품질의 근사치를 안정적으로 생성하지 못한다.

[2] : Andre Gueziec의 <Surface simplification with variable tolerance>
[3] : Hugues Hoppe의 <Progressive meshes>
[7] : Remi Ronfard and Jarek Rossignac의 <Full-range approximation of triangulated polyhedra>

고품질로 생성가능한 방법인[2, 3, 7]은 Aggregation을 지원하지 못한다.
[2, 3] 둘 다 우리의 알고리즘보다 더 많은 시간을 소요한다.
[7]의 결과는 우리와 유사한 Error 근사 방식을 사용하기 때문에 비슷하다.

하지만 우리의 시스템은 평면 집합을 추적하는데 더 효과적인 수단을 사용하고 경계 보존과 같은 개선사항이 있다.

우리 알고리즘은 개선할 수 있는 다양한 측면이 남아 있다.

  • 개선점 : 색상과 같은 표면속성 문제를 다루지 않는다.
  • 해결책 : 각 정점을 벡터로서 다룬다. 7 x 7 quadrics를 만들고 단순화한다.
  • 문제점 : 더해진 사이즈와 복잡성은 기존의 알고리즘보다 덜 매력적으로 만든다.

우리 알고리즘의 명백한 약점

  • 첫째 : 평면 집합까지의 거리로 Error 측정은 적절한 지역적 이웃에서만 잘 작동한다.

  • 둘째 : Quadrics에서의 축적된 정보는 본질적으로 내재되어있어서 문제가 될때가 있다.

    예를들어 두 개의 정육면체를 결합하고 지금은 없어진 내부 면과 관련된 평면을 제거하려고 한다.

    • 일반적으로 어떤 면이 없어졌는지 확인이 어려움
    • Quadrics에서 적절한 평면을 안정적으로 제거하는 명확한 방법도 없음

그 결과로 우리의 알고리즘은 우리가 원하는 만큼의 Aggregation과 단순화를 잘 하지 못한다.

9. Conclusion

우리는 다각형 모델의 근사치를 원본에 충실하고 빠르게 생산할 수 있는 표면 단순화 알고리즘을 설명했습니다.
알고리즘은 모델을 단순화하기 위해 Iterative Pair Contraction을 사용했고, 단순화될 모델의 근사치 Error를 추적하기 위해 Quadric Error Metrics를 사용합니다.

우리의 알고리즘은

  • 고품질의 결과를 유지하면서 연결되지 않은 모델 섹션을 연결
  • non-manifold 처리 및 단순화
  • 정점 클러스터링과 같은 매우 빠르지만 저품질인 방법과 메쉬 최적화와 같이 매우 느리지만 고품질인 방법 사이에 유용한 중간 지점을 제공합니다.

맨 위로 이동하기

IAC 카테고리 내 다른 글 보러가기

댓글남기기

최근 글 10 개 :)