자료보관함‎ > ‎가마수트라‎ > ‎

분할표면 만들기


저작권 정보

현재 가마수트라가 번역허가를 내주고 있지 않은 관계로 원문의 링크만을 제공합니다. 하지만 영어에 도움이 필요하신 분들을 위해 아래에 해석을 달아놓았습니다. 원문을 읽으시다가 모르시는 부분이 있으시다면 비교하면서 읽어보시길 바랍니다.


원문 정보


개관

Quake3를 사랑하는 분들은 아마 Quake3의 고품질 그래픽과 라이트 맵, 그리고 캐랙터 애니메이션에 깊은 감명을 받으셨을 것입니다. Quake3를 제작하는데 있어 세밀한 텍스쳐를 만드는 효율적인 작업을 했음에도 불구하고 대부분의 캐랙터들은 단지 수천개의 삼각형들로만 구성되어 있습니다. 그렇기 때문에 아주 세밀한 기하를 표현할 수가 없습니다. 최근 몇 년동안 분할 표면 기법이 학계와 산업현장에서 많은 주목을 받아왔습니다. 영화 산업에 있는 산업들 조차도 복잡한 캐랙터 생성과 고품질의 세밀하고 부드러운 애니메이션을 만들기 위해 분할 표면을 적용했습니다. 이 기사는 가장 대중적으로 널리 쓰이고 있는 표현 방법중의 하나인 삼각형 메쉬들을 분할 표면들로 변환하는 방법에 대해서 설명하고 있습니다.

분할 표면이란?


분할 표면 아이디어는 1978년에 캣트멀& 클락(Catmull & Clark)과 두&사빈(Doo & Sabin)이라는 사람에 의해서
처음으로 소개되었습니다.  전통적인 스플라인 곡면과 다르게 분할 표면은 알고리즘적으로 정의됩니다.
<pre>역자주 – 스플라인 곡면은 매개변수식으로 곡면이 정의됩니다.</pre>
컴퓨터 그래픽 연구 커뮤니티에서 활발한 연구 활동으로 인해 렌더링,텍스쳐 매핑,애니메이션과 분할 표면 압축에 대해서 상당한 진보가 이루어졌습니다. 이러한 연구 결과를 바탕으로 분할 표면 기법은 게리 게임과 벅스 라이프에 사용되었으며 게리 게임의 경우에는 게리의 손,머리,자켓이 각각 분할 표면을 사용해서 하나로 모델링 되었습니다. 프릭(Flick)과 호퍼(Hopper)의 손과 얼굴도 또한 분할 표면으로 모델링 되었습니다.
이렇듯 컴퓨터 보조 기하 설계(CAGD)에 모델링 프리미티브중에 하나인 분할 표면을 만들수 있도록 구성되고 있는것이 현재 추세입니다.

왜 분할 표면인가?

분할 표면은 폴리곤 메쉬와 곡면 패치 사이에 있으며 폴리곤 메쉬와 곡면 패치사이의 가장 좋은 장점들 몇가지를 제공하고 있습니다. 좋은 점을 설명하자면 분할 표면은 정돈된(well-defined) 표면 법선 벡터를 이용해서 폴리곤 기하에서 각진 면들이 보여짐이 없이 부드럽게 렌더링할수 있습니다. 또한 분할 표면은 두개의 곡면(패치)이 서로 연결되서 합쳐지기 전에 행과 열의 수가 같아야 한다는 곡면의 구속조건을 가지지 않으면서도 임의의 위상(구멍과 경계를 가지는)을 가지는 부드러운 표면을 표현할수가 있습니다.

이러한 분할 표면은 분할(splitting)과 평균화(averaging) 과정을 재귀 호출을 통해서 쉽게 만들수 있습니다.
여기서 분할이라고 하는것은 이전 면을 제거해서 4개의 새로운 면을 생성하는 것을 말하며 평균화는 새로운 정점을 위해 이웃하는 정점들의 가중치 평균을 구하는 것을 말합니다. 기본적인 연산은 단순하기 때문에 구현하기가 매우 쉬우며 효율적으로 실행될수 있습니다. 또한 재귀 호출의 특성상 적응적(adaptive) 분할을 통해서 세부 상세 수준(Level Of Detail)을 자연스럽게 제어할수 있습니다. 적응적 분할은 좀더 세밀하게 보여질 필요가 있는 부분은 삼각형을 더 분할할수 있게 해주는 방법을 말합니다.

해야할 것은?

간단한 분할 과정은 일반적으로 거친 컨트롤 메쉬로부터 시작해서 분할 과정을 몇번 거친후에 준-정규(semi-regular) 메쉬를 만드는 것입니다. 삼각 메쉬인 경우에 한 정점에 이웃한 정점들의 개수가 6인 경우와 사각 메쉬인 경우 이웃한 정점들의 개수가 4라고 하면 이 정점을 정규(regular)라고 합니다. 정규가 아닌 정점들은 비 정규(extraordinary)라 합니다. 표준 모델링 툴에서 생성되거나 3D 스캐닝 디바이스에서 나온 메쉬들은 일반적으로 정규 구조를 가지고 있지 않습니다. 그래서 리메싱(remeshing)이라고 알려진 과정를 통해서 비정규 메쉬를 준-정규 메쉬로 변환할 필요가 있습니다.

프로그래밍 시작시 준비사항

알고리즘을 설명하기 전에 먼저 입력부터 한번 살펴보도록 하겠습니다. 입력은 임위의 삼각화된 다양체(manifold) 메쉬입니다. 임위란 말은 메시가 구멍이나 경계를 가질수 있다는 것을 의미하며 삼각화된 다는 말은 표면이 삼각형 리스트에 의해서 근사화/디지타이즈화 됐다는 것을 의미하며 다양체란 말은 위상정보의 불일치를 가지고 있지 않는다는 것을 의미합니다. 위상정보의 불일치라는 것은 한 에지가 두개의 삼각형보다 많은 것을 공유하거나 하나의 정점에서 만나는 모서리 부분 두개 이상인 것을 의미합니다. 따라서 여러분은 입력 모델로 좋고 깨끗한 메쉬를 준비하셔야 할것입니다.



알고리즘 개요

변환 알고리즘은 두개의 주요한 단계로 구성됩니다. 첫번째 단계는 메쉬 단순화라고 합니다. 메쉬 단순화란 게임 개발자들에게 LOD나 다른 대역폭을 제공하는 것으로 알려져 있습니다. 대부분의 시간은 모델의 복잡성과 상호작용사이에서의 상호절충(trade-off)입니다. 예를 들어서 높은 프레임 율을 필요로 하는 경우는 일반적으로 단순/거친 모델로 변환됩니다. 이 알고리즘에서 메쉬 단순화는 재샘플링/리메싱을 할수 있도록 기본 도메인(base domain)을 추출할수 있도록 해주는 도구로만 사용됩니다. 따라서, 개발자들은 원하는 메쉬 단순화 알고리즘을 자유롭게 선택할수 있습니다.
저는 Michael Garland가 제안한 쿼드릭(에러 평가 기준- quadric –2차) 단순화 알고리즘을 추천합니다. 이것을 추천하는 이유는 오픈 소스이며 이해하기 쉽기 때문입니다.

두번째 단계는 리메싱 단계입니다. 리메싱의 목표 원래 메쉬로부터 샘플링된 삼각형(geometry)에서 분할 메쉬를 생성하는 것입니다. 앞에서 언급했던 것처럼, 컨트롤 메쉬를 분할하는 것은 메쉬에 부가적인 정보를 추가하는 것이 아니라 모델의 복잡성만을 증가시키는 것입니다. 따라서, 그림 1처럼 원래 메쉬에 근접하게 정점들이  퍼져나가(perturb)는 방법을 알수 있게 하기 위해서 첫번째 단계에서부터 매핑 정보를 사용할 필요가 있습니다.

그림1. 알고리즘은 두 단계로 구성됩니다. 첫번째로 단순화 과정으로 기본 도메인이라고 하는 컨트롤 메쉬를 만들고 이 기본 도메인에 대해서 매핑을 계산합니다. 두번째 단계는 기하 재샘플링(리메싱)입니다. 리메싱의 목적은 기본 도메인의 분할을 통해 연결성을 가진 분할을 얻는 것이며 동시에 원래 메쉬로 근사화하게 만드는것입니다.


2D 경우

3D 매핑 알고리즘을 시작하기전에 2D 곡선의 경우에 대해서 잠깐 살펴 볼것입니다. 여기서는  분할 연결성(subdivision connectivity)에 대한 개념이 적용되기가 적절하지는 않습니다. 그러나 변환 과정은 이중(dyadic)점들의 정규 샘플링으로 말할수 있습니다. 단순화(그림 2에서 보여지는 것처럼 각 단계에서 하나씩 거른 정점들을 제거)는 선분(빨간색으로 표시된 기본 도메인)을 추출하는데 사용됩니다. 그림 3에서 두번째 부분을 만들기 위해서 (기하 재샘플링 과정과 유사한) 중간점들은 두개의 가장 가까운 근접 점들 사이에 선형 보간을 수행해서 각 선분의 중간에 삽입됩니다.

그림2. 이 그림은 알고리즘의 첫번째 부분을 적용한 결과를 보여주고 있습니다. 아이디어는 매번 다른 정점들을 제거해서 곡선의 단순화를 하는 것입니다. 각 단순화 과정 단계에서 제거되는 정점은 아크-길이(arc-lenth) 비율에 의해서 결정된 단순화된 곡선으로 매핑됩니다.

그림 3. 이것은 2D에서 변환 알고리즘의 두번째 부분입니다. 노란색 원은 (삼각형 분할경우에 중심점과 유사한) 기본 도메인 선분의 중간 점들입니다. 좌표는 두개의 인접한 녹색 정점들의 선형 보간에 의해서 계산됩니다.


2D 곡선 재샘플링 과정은 다음과 같이 요약할수 있습니다. 먼저 그림3에서 빨간 선분위의 중간점(노란색 원 – 이중점)을 삽입해서 빨간 선분위의 원래 곡선으로부터 매핑된 두 점들 사이의 가장 가까운 점을 알아냅니다. 그때, 두개의 녹색 원들내에서 노란색 원의 비율을 계산합니다. 녹색 원의 원래 기하와 이 비율을 가지고 우리는 선형적으로 좌표들을 보간할수 있으며 원래 곡선위에 노란색 점들의 재 샘플링된 기하를 얻을수 있습니다.

자! 지금까지 설명한 단순한 아이디어를 머리속에 담아두고 이제 3D로 확장해 봅니다.

3D 메쉬 단순화


알고리즘을 보여주기 위해서 저는 Mike Garland의 효율적인 단순화 알고리즘을 사용했습니다. 이 소스 코드는 다음의  http://graphics.cs.uiuc.edu/~garland/software/qslim.html 주소로부터 다운로드 할수 있습니다. 그의 단순화 방법의 좋은 점은 앞에서도 말했다시피 빠르고 구현하기가 쉽다라는 것입니다. 그의 방법은 고해상도의 다각형들을 신뢰할만한 적은 수의 다각형으로 자동으로 단순화 시켜줍니다. 이 알고리즘의 핵심은 로컬 표면 형상의 특성을 주기위해서 쿼드릭(quadric) 에러 척도라고 하는 에러 척도를 적용하는 것입니다. 쿼드릭 에러 척도는 평가가 빠르며 많은 메모리를 차지 하지 않습니다. 이 알고리즘에 대한 좀더 자세한 내용은 다음의 사이트 http://graphics.cs.uiuc.edu/~garland/research/thesis.html 에서 보실 수 있습니다.

그림 4. 정점 v1 을 제거하면  에지 v1v2이 사라지고 v1 에 인접한 삼각형들(전(old)에 있던 삼각형들)도 제거될것입니다. 따라서, 구멍이 생성되서 다시 재 삼각화를 수행하게 됩니다. (이때 새로운 삼각형들이 생겨납니다.)


매핑 정보 전달하기

각 단순화 단계에서 정점들을 제거하고 제거된 정점 주위의 삼각형들을 없애고 구멍 부분을 재삼각화를 하기 때문에  에지들이 무너지게(collapse) 됩니다. 그림 4에서 에지 v1v2 가 무너지면서 v1 이 제거됩니다. 이웃한 수준들 사이에서 매핑의 형태를 보존하기 위해서 저는 4개의 튜플 (a, b, g, T)을 계산할것입니다. 각 요소들을 설명하면 먼저 v1 이 없어지면서 새롭게 생성된 삼각형들 중 v1 이 포함된 삼각형을 T라고 하며 (a, b, g)는 v1 이 삼각형 T의 베리센트릭 좌표를 나타냅니다. <pre>역자주 - 여기서 a : alpha, b : beta, g : gamma를 말합니다.</pre> 각 단순화 단계에 대해서 이러한 4개의 튜플값을 계산하기 위해서 2D 평면위로 v1 의 1 –ring(그림 5참조)을 펼칩니다. 이 평면 펼치기는 za 맵을 계산해서 구할수 있습니다. za 맵은 v1 에서의 각도의 합이 2 phi나 phi가 되도록 각도를 스케일링해서  v1 과 연결된  엣지들에 거듭제곱 a를 해서 에지의 길이를 늘립니다.

4- 튜플은 그림 5에서 처럼 계산됩니다.


그림 5. 4- 튜플을 계산하기 위해서, 먼저 v1  주위로 3D 1-링(one-ring)을 펼쳐서 2D 평면으로 만듭니다. 스케일 인자는 각도의 합이 2 phi 가 되는지를 확인하는데 사용되며 길이가 a의 거듭제곱으로 스케일되는데에도 사용됩니다. 1-링이 펼쳐지면, 새로운 삼각형에서 v1의 위치를 계산합니다.

코드 조각들

RemoveVertex( Vertex V ) {
   PlanarFlatten( V );
   Valid = TryRetriangulate( V );
   if ( Valid ) {
       AssignParameter( V );
       Reparameterize( V );
       DoTriangulate( V );
   };
};


정점 제거의 기본적인 뼈대는 아주 단순합니다. 먼저 그림 5에서 기술한것처럼 정점 V(우산)의 인접 3D 1-링을 평면으로 펼쳐지게 해서 2D 평면상에 놓이게 합니다. 예) 각도와 에지 길이를 스케일링 우산을 펼쳐지게 한후에  전 (old) 삼각형을 제거하고 새로운 삼각형을 추가하기 위해서 재삼각화 루틴(예: 디러니(delaunay) 삼각형)을 사용합니다.

그 다음 새로운 삼각형이 메쉬에서 존재하는 삼각형에 서로 겹쳐지지 않도록 확인과정을 수행합니다. 만약 삼각형이 서로 겹쳐진다면 위상 불일치를 생기게 되서 메쉬가 다양체가 되지 않을 것입니다.(예. 에지를 두개 이상의 삼각형들이 공유) 서로 겹쳐지지 않은 경우에는 정점 V에 대해서 4-튜플을 계산합니다. 계산과정은 두 단계로 구성되는데 첫번째 단계는 정점 V에 대해서 4-튜플을 매개변수를 할당하는 과정입니다. 이 과정은 그림 6에서 나타내는 것처럼 베리센트릭 좌표를 계산하는 과정과 정점 V와 연관된 삼각형을 구하는 과정입니다. 두번째 단계는 현재 전(old) 삼각형과 연관된 정점들의 매개변수 값을 갱신하는 것입니다.  함수 CalcNewParameters( Vi ) 는 그림 7에서처럼 관련된 갱신을 수행합니다.


AssignParameter( Vertex V) {
   Tuple = CalcBaryCoord( V );
   InsertTuple( V, Tuple );
};
Reparameterize( Vertex V ) {
   ForEachFaceAroundVertex( V , Fi ) {
       ForEachAssociatedVertex( Fi , Vi ) {
           NewTuple = CalcNewParameters( Vi );
           UpdateTuple( Vi , NewTuple );
       };
   };
};


그림 6. 이 그림에서 v1 은 녹색 삼각형에 매핑되고 베리센트릭 좌표(a, b, g)와  v1 과 관련된 새로운 삼각형을 계산합니다.


그림 7. 1-ring 삼각형들을 제거할 때 전에 새로운 삼각형들과 관련된 정점들의 매개변수 값들을 갱신합니다. 이 예제들은 새로운 삼각형에서 정점들의 매개변수화 과정을 보여주고 있습니다.


전 삼각형과 관련된 정점들이 있다면 우리는 재 삼각화 때문에 정점들의 매개변수값들을 또한 갱신해야합니다. (전 삼각형들이 제거) 갱신은 앞 단계와 비슷한 방법으로 계산될수 있습니다.

단순화 과정의 끝에서는 기본 도메인이라고 하는 단순한 컨트롤 메쉬가 생성될 것입니다. 단순화 계층구조에서 제거된 각 정점들은 베리센트릭 좌표와 연관된 기본 도메인 삼각형을 나타내는 4-튜플을 가지게 될것입니다. 이것으로 알고리즘의 첫번째 단계가 끝났습니다.

알고리즘의 실행 예


다음 이미지들은 3개의 구멍이 있는 원환체에 대해서 첫번째 단계를 수행한 결과를 보여주고 있습니다. 이 모델이 약간 단순해보임에도 불구하고 이것은 genus-3 오브젝트를 다룰수 있는 알고리즘의 일반성을 보여주고 있습니다.
<pre>역자주 - genus-3 , genus-4 원환체에 구멍이 3개나 4개 있는것들을 말하며
아마도 알고리즘의 일반성을 검증하는 용도로 쓰여지는것으로 보여집니다.</pre>



첫번째 이미지는 원래 삼각 메쉬를 보여주고 있으며 두번째 이미지는 단순화 루틴에서부터 기본 도메인에 가는 과정을 보여주며 세번째 이미지는 기본 도메인상에 각 정점을 매핑한 화면을 보여주고 있습니다. 그래서 4-튜플을 가지고 있는 각 정점들을 가진 기본 도메인상에 수축-와핑한 원래 메쉬가 보여집니다. 네번째 이미지는 기본 도메인을 분할해서 원래 메쉬에 매우 근사화하도록 새로운 정점들을 전달되도록 한 결과 화면입니다.

기하 재샘플링

이 시점에서 매핑계산이 끝났습니다. 매핑을 보는 한가지 방법은 각 정점이 기본 도메인 삼각형내에 위치와 연관된 기본 도메인 삼각형이 어떤것인지를 알려주는 4-튜플을 보는 것입니다. 매핑을 가시화 하는 또 다른 방법은 기본 도메인의 위에 원래 메쉬 삼각형(그래프로 처리되는)을 축약/래핑 하는 것을 상상하는 것입니다.

컨트롤 메쉬 분할

분할 연결성을 가진 메쉬를 생성하기 위해서 단순히 전 삼각형을 4개의 새로운 삼각형으로 짜르는 과정을 몇번 분할 하는 것입니다. 새로운 에지 정점들은 이중(dyadic) 점이라고 한다. 1-4 분할은 6개의 이웃하는 정점을 생성한다는 것에 유의해야 합니다. 생성된 새로운 정점들 모두는 정규가 됩니다. 대부분 흔하게 사용되는 분할 스키마는 루프(loop) 분할과 캣트멀 클럭분할입니다. 루프 분할은 삼각메쉬에서 사용되는 스키마인 반면에 캣트멀 클럭분할은 사각메쉬에서 사용되는 구조입니다. 이 기사는 루프 분할 방법에 대해서 보여주고 있으며 이것은 삼각메쉬인 경우에서는 말할필요도 없이 당연한 것입니다. 최종 분할 표면은 비정규 정점를 제외하고는 C2연속성을 가진 부드러운 표면이 될것입니다. 

다음 단계는 분할 메쉬를 원래 메쉬에 근접하다록 정점들을 전파(perturb)시키는 것입니다.

이 과정을 기하 샘플링이라고 말합니다.

정점 좌표 전파하기

원래 메쉬 기하에 근접하도록 분할 정점을 이동하는 방법에 대해서 언급하기 전에 알고리즘을 이해하기 위해 에지 용어를 도입할 것입니다. 그리고 나서 몇가지 표기에 대해서 설명하고 나서 진행할 것입니다.
기본적으로 메쉬에서 에지는 원점 정점(e.Org),목적지 정점(e.Dest), 목적지 정점에서의 전 에지(e.Dprev)와 원점 정점에서 다음 에지(e.Onext)를 나타내는 방향성 에지들로 표현됩니다. 


그림 8. 자료구조에서 방향성 에지 표기와 이웃 포인

에지에 대해서 정의가 되었다면 다음 단계로 진행합니다.


코드 조각


분할 정점에 대해서 정점 좌표를 계산하기 위해서 먼저 이중점(그림 3에서 2개의 녹색 원인 2D 경우가 유사)을 포함하는 기본 도메인상의 평평한 메쉬에 있는 삼각형을 알아내야 합니다. 삼각형 위치문제는 점 위치 문제로 축소됩니다. M을 기본 도메인상에서의 평평한 원래 메쉬로 정의하고  V는 빨간 이중 정점이라고 정의합니다. V를 포함하는 흰 삼각형은 리스팅 1에 있는 루틴을 사용해서 구할수 있습니다.

리스팅 1. 흰 삼각형 구하기
Edge PointLocation( V, M ) {

   e = randomEdge( M );
   if RightOf( V, e )
       e = e.Sym; /* e.Sym는 e반대 */
   while (1) {
       if (V == e.v1 || V == e.v2 )
           return e;
       else
           whichop = 0;
           if !RightOf(V, e.Onext)
               whichop += 1;
           if !RightOf(V, e.Dprev)
               whichop += 2;
           switch (whichop) {
           case 0:
               return e;
               break;
           case 1:
               e = e.Onext;
               break;
           case 2:
               e = e.Dprev;
               break;
           case 3:
               if (dist(e.Onext, V) < dist(e.Dprev, V))
                   e = e.Onext;
               else
                   e = e.Dprev;
               break;
           };
   };
};

이중점을 포함하는 원시메쉬에서 나온 삼각형을 구하면 선형 보간으로 재 샘플링된 위치를 구할수 있습니다.


P는 이중점이며 삼각형 ABC는 원래 기하를 가지는 원시 삼각형에서 나온 값입니다. (a, b, g)는 그래프에서 삼각형 ABC내에 있는 베리센트릭 좌표 P입니다. 그러므로 P는 구분적 선형 원래 메쉬를  재 샘플링한 점이 될 것입니다.  모든 정점들에 대해서 이 과정을 반복하면 분할 연결성 메쉬들이 전파되서 원래 기하에 거의 가깝게 됩니다. 다음의 예제들은 이러한 결과를 보여주는 화면입니다.

말과 비너스 결과물

그림 9. 첫번째 그림은 비정규 연결성을 가진 말이며 두번째 그림은 재 샘플링된 결과를 보여주고 있으며 세번째 그림은 기본 도메인을 보여주고 있습니다. 반면에, 네번째 그림은 기본 도메인에 대해서 원래 메쉬를 매개변수화 한것을 보여주고 있습니다.

그림 10. 알고리즘을 적용한 비너스 머리 예로서 첫번째 그림은 원시 메쉬를 나타내며 두번째 그림은 기본 도메인에서 분할된 패치들에 대해서 색을 입혀서 매개변수화 한 것을 보여주는 그림입니다.




이제 끝입니다. 간단히 정리하자면 이 기사는 삼각 메쉬를 분할 표면으로 변환하는 간단한 알고리즘에 대해서 설명하고 있습니다. 기하 샘플링으로 문제를 다시 바꾸고 단순 기본 도메인에 관련된 매핑(원시 메쉬의 매개변수화)을 계산하는 주요 알고리즘은 이해하기 쉬우며 구현하는 것 또한 쉽습니다. 따라서 여러분은 캐랙터 애니메이션,자유 형상 표면 설계와 효과적인 렌더링에 분할 표면 방법을 적용할수가 있을 것입니다. 이 기사의 다음 부분은 여러 분할 표면 방법들을 사용해서 설명한 방법에 적용해 보는것입니다. 계속 지켜봐 주세요!


번역문 정보

이것은 MAPS:Multiresolution Adative Parameteriaztion of Surface 논문을 게임 개발자가 이해하기 쉽게 풀어쓴 글입니다. - 이스
  • 번역: 이스

현재상태

  • 번역 완료 (2005년 7월 11일)



Comments