CG - 10. Triangle Mesh

1. Triangle Mesh

- 가장 널리 쓰이는 modeling 기법중 하나인 triangle mesh를 깊게 알아보자.

- rendering 이외의 다른 operation이 필요할 수 있다. 예를들면 인접한 mesh들을 탐색하는 경우가 이에 해당한다.

- 이런 여러 operation에 용이한 mesh의 data structure은 어떻게 생겨야 할까?

- 첫째, compactness : 최소한의 storage로 정보를 저장할 수 있어야 한다.

- 둘째, generality : 다양한 operation들이 필요한 정보들을 얻을 수 있어야 한다.

- 셋째, computation : 더 효율적이 연산이 가능해야 한다.

- traingle이 특히 많이 쓰이는 이유는 항상 하나의 평면을 구성하기 때문이다.

2. Generality

- 보편적인 물체들을 표현하는데 문제가 없는지?를 의미한다.

- -> 방향으로 개선, 제약하면서 generality를 확보한다

- 삼각형, 사각형 등의 polygon soup

-> polygon soup에서 좀더 구체적인 형태를 정의, 제한된 삼각형만을 사용

-> 하나의 edge에 최대 두개의 삼각형만 연결되는 2-manifold형태로 제한. 더 구체적으로는 물체 표면의 특정 점을 중심으로 하는 구를 그렸을때 물체와의 intersect하는 부분만 잘라보자. 그 부분을 전개도로 펼쳐서 open disk가 만들어지면 2-manifold한 것이다.

만약 이렇게 하나의 edge에 여러 삼각형이 있으면 open disk로 deform할 수 없다.

 

-> orientable, 삼각형의 vertex들이 동일한 방향을 갖고 있도록 제한, counter-clockwise winding을 한다. 즉 삼각형을 정의할 때 vertex들을 0,1,2 순서로 반시계로 그린다는 것이다. 특정한 점을 시작으로 삼각형을 그릴때는 항상 반시계 방향으로 그린다.

-> closed mesh,  mesh에 구멍이 존재하지 않도록 한다.

3. Representation for Triangle meshes

seperate triangle

- triangle 간의 connectiveness가 없는 표현 방법, triangle soup과 비슷하다.

- 랜더링만 할거면 상관없지만 vertex normal을 계산한다고 하면 vertex에 인접한 삼각형들을 normal vector를 알아야 하는데 이런 표현방법에서는 vertex에 인접한 삼각형들을 알아내는 것이 쉽지 않다.

- 삼각형들의 세 좌표들을 그냥 나열한 것

- float[삼각형 수][3][3] 3차원 array 필요 (72byte per vertex)

- orientation은 유지한다.

- vertex의 중복이 많이 생긴다.

- roundoff 때문에 crack이 생길 수 있다. 

 

Indexed Triangle set

- vertices list에 index정보를 추가해서 중복되는 일 없이 vertex를 공유할 수 있게 된다.

- triangle이 어떤 vertex로 구성되는지 알 수 있다.

- 하지만 마찬가지로 vertex normal을 구하는 operation의 경우 삼각형 list를 전부 돌면서 찾아야 하는 등 여전히 어려움이 있다. (하나의 삼각형이 어떤 점들로 구성되는지 알고 있기때문에 약간의 인접정보를 알 수 있지만 삼각형 리스트를 돌면서 인접 삼각형이 누가 있는지 결국은 돌면서 찾아야 한다.)

- 하나의 vertex당 약 36byte를 쓰는 셈이다. 좀더 compact하다.

- topoloy와 geomerty를 분리해서 저장한다. 즉 point cloud와 connectivity info를 분리해서 저장하는 것이다.

 

Triangle neighbor data structure

- adjacency에 대한 정보를 추가적으로 저장하는 자료 구조이다.

- vertex들의 이웃 정보 혹은 한 점에서 인접한 triangle list를 알 수 있다.

 

winged-edge data structure

- 모든 adjacency 정보를 O(1)만에 알 수 있도록 한 자료구조이다.

- vertices list, triangle list, edge list를 가지고 있다.

- vertices list에는 연결된 edge들의 정보를 갖고 있고 edge list에는 연결된 vertex, triangle, edge의 정보를 가지고 있다.

 

triangle strip, triangle fan

- 첫 삼각형을 그리는데는 3개의 점이 필요하지만 두번재부터는 하나의 점만 있어도 삼각형을 그릴 수 있다.

- 효율적이고 컴팩트하게 삼각형을 그릴 수 있다.

- strip , fan 형태가 있을 수 있다.

4. Data on mesh

- 이제가지는 vertex 좌표, connectivity만을 저장하는 모습만 봤지만 더 많은 정보들이 저장될 수 있다.

- 이런 여러 데이터들을 face, vertices, edges list 마다 저장할 수 있다.

- 가장 많이 사용되는 방법은 vertex마다 추가적인 정보들을 저장하는 것이다. 

- vertex마다 여러 데이터를 지정하면 interpolation으로 매끄러운 구현이 쉽다.

1. vertex의 좌표,

2. illumination을 구하기 위한 surface normal vector

3. texture coordinate

4. color

5. illumination 계산을 위한 material property (kd, ks, ka, n 등)

등의 정보을 가지고 vertex interpolation으로 최종 pixel의 정보로 전달된다.

- 이 mesh에 대한 data들을 file에 저장해서 사용하는데 파일 형식으로는 .obj를 많이 사용한다.