TMI(Triangle Mesh Information) Project #2 - Mesh를 표현하는 여러가지 Data Structure들

 

 

 이전 포스팅에서는 컴퓨터가 Mesh Data를 읽기 위해서는 어떠한 과정이 있고 무엇이 저장되어야 하는지에 대해서 알아보았습니다.

1. 현실세계에 있는 물체를 컴퓨터 세상에서 표현하고 싶다면 컴퓨터가 읽을 수 있는 Model로 만들어야 한다는 것(모델링)

2. 모델링된 Model은 vertex와 edge, face로 구성되어 있다는 것

3. 이런 내용들을 저장하기 위한 format으로 많은 format이 있지만 대표적으로 OFF, OBJ, STL이 있다는 것

이렇게 크게 3가지에 대해서 알아보았습니다. 오늘은 그 다음으로 이 Mesh를 표현하는 내용물들을 어떻게 담아서 사용할건지에 대해서 알아보도록 하겠습니다.

 

이번 포스팅에서는 총 3가지의 Data Structure들에 대해 알아보는 시간을 가져볼텐데요. 각각의 이름은 아래와 같습니다. 그럼 하나씩 살펴보도록 하겠습니다.

 - Face-Vertex

 - Shared Vertex

 - Half-Edge

 

1. Face-Vertex

 첫 번째는 Face Vertex Lists 입니다. Face Vertex Lists는 Face를 기준으로 쭉 나열하되, 각 Face마다 Face를 이루는 vertex를 3개씩(Triangle Mesh기 때문) 나열 하는 것입니다. 우리가 이전 포스팅에서 봤던 file format 중 STL이 이 방법으로 이루어 진 것을 확인하실 수 있습니다.

 아래 그림은 이전 포스팅에서 보셨던 STL file format 내용입니다. 내용을 보시면 facet normal Line부터 endfacet 라인까지 하나의 Face 정보를 담고 있으며, 그 안에 Face를 이루는 각각의 vertex에 대한 좌표정보를 담고 있습니다.

STL File Format

그림으로 쉽게 표현해보자면 아래 그림처럼 표현 할 수 있습니다. 한 줄이 하나의 Face이고 Face를 이루는 Vertex들의 좌표정보가 저장되어 있는 것을 확인할 수 있습니다.

이 Data Structure의 장단점을 살펴보면 아래와 같습니다.

 장점 - 직관적이고 간단하다.

 단점 - 인접 정보(연결성 정보)가 없다. 쓸데없는 정보가 있다.

 

 먼저 장점은 적힌 그대로 가장 직관적으로 Mesh의 정보를 담을 수 있다는 점입니다.

 하지만 단점은 각 Face를 개별적으로 저장하다보니 인접 점이나 인접Face에 대한 정보를 알 수 없습니다. 또한, 개별 Face를 저장하다보니 같은 Vertex를 공유하고 있는 Face들도 공유하고 있는 Vertex를 하나로 저장하는게 아니라 개별로 저장하기 때문에 쓸데없는 정보가 남게 됩니다.

 예를 들어 (0, 0, 0)에 있는 Vertex를 공유하는 Face가 3개가 있다면 3개의 Face가 각자 (0, 0, 0)의 Vertex를 저장하고 있게 됩니다.

 

2. Shared-Vertex

 그래서 이러한 문제를 해결하기 위해 사용되는 Data Structure가 Shared Vertex 입니다. Shared Vertex는 각 Vertex마다 고유의 Index를 지정해서 중복되는 Vertex를 Index로 가져오는 개념입니다. 우리가 이전 포스팅에서 다뤘던 file format은 OFF와 OBJ file format이 이 방법을 사용합니다.

 아래 그림은 이전 포스팅에서 보셨던 OFF file format 내용입니다. 내용을 보시면 3번 Line부터 Vertex 정보가 각각 중복없이 담겨 있고 3번 Line부터 0번 + Line Index를 가지게 됩니다. 따라서 11번 Line의 첫번째 Face는 0, 1, 3번의 Vertex 즉 (-1, -1, -1), (-1, 1, -1), (1, -1, -1) 이 3개의 Vertex로 Face가 이루어져 있음을 알 수 있습니다.

 이 구조도 그림으로 표현해보면 아래 그림처럼 표현할 수 있습니다. Face 정보에는 Vertex의 Index가 담겨져 있고, 담겨진 Index를 따라 Vertex 정보에서 찾으면 됩니다.

이 Data Structure는 이제 Face Vertex List의 단점을 보완하게 됩니다. Vertex를 공유하기 때문에 쓸데없는 정보도 줄였고 Face들이 공유 Vertex로 연결이 되었기 때문에 나와 같은 Vertex를 공유하는 Face를 찾을 수 있게 되었습니다. 하지만 시간 복잡도는 O(N)이 걸리게 됩니다.(모든 Vertex를 확인해야하기 때문)

 

3. Half-Edge

 다음은 Half-Edge Data Structure 입니다. 지금까지 소개한 위의 두 Data Structure는 Face에 집중하고 있는 반면 이번 Data Structure는 Edge에 집중을 하고 있습니다. 

 먼저 Half Edge란 방향성을 가지는 Edge를 뜻합니다. 따라서 하나의 Vertex는 본인의 Position과 자기자신에서 Next Vertex로 향하는 Half Edge 한개를 가지게 됩니다. 우리는 그것을 Outgoing Half Edge라고 하고, 다른 Vertex에서 자기자신으로 오는 Half Edge는 Incoming Half Edge라고 합니다. 아래 그림을 참고하면 이해하기 쉬울 것 같습니다.

 다음은 하나의 Halfedge가 가지는 정보에 대해서 이야기해보겠습니다. 아래 그림과 같이 하나의 Half Edge가 있다면 그 Half Edge는 Start Vertex와 End Vertex를 가지고 있습니다. 그리고 자기 자신에게 들어오는 Half Edge를 Prev Half Edge라고 부르고, 다음으로 연결되는 Half Edge를 Next Half Edge 마지막으로 자신의 반대편에 있는 Half Edge를 Opposite Half Edge라고 합니다. 그래서 하나의 Face는 Prev-Half Edge- Next 이렇게 3개의 Half Edge로 이루어져 있습니다. 그렇기 때문에 현재 Half Edge와 접해있는 Face를 찾고 싶다면 Opposite Half Edge로 가서 Prev Next를 찾게 되면 반대편에 있는 Face도 쉽게 찾을 수 있습니다.

 위에서 이야기 한 것 처럼 Half Edge Data Structure는 인접 정보를 빠른 시간에 찾기가 용이합니다. 따라서 2번째에서 이야기한 Shared Vertex에서 하나의 Vertex를 공유하는 Face를 모두 찾는데 걸리는 시간이 O(N)이었다면 Half Edge 구조를 사용하면 O(1)로 시간 복잡도가 줄어들게 됩니다.

 

 

 

 오늘은 이렇게 총 3가지의 Triangle Mesh Data Stuctrue에 대해 알아보았습니다. 다음 포스팅에서는 대표적인 Mesh Library 중 하나인 VTK에 대해서 알아보고 VTK를 사용하는 간단한 방법에 대해서도 알아보도록 하겠습니다.

v Eng



1.v

[약어] (vs 특히 美) 스포츠·소송에서 …대(versus)

2.v.

valve; [수학] vector; velocity; verb; verse; version; versus ((L = against)); very; vicar; vice; vice-; vide ((L = see)); village

3.v.

volt(s); voltage

4.v

variable; velocity; vicinal; victory; 〈전기〉 volt(s).

5.V

[명사] 브이(영어 알파벳의 스물둘째 글자)

6.scalar triple product

[명사] (수학) 스칼라 삼중적(三重積): 3차원의, 주어진 세 개의 벡터 u, v, w를 세 변(邊)으로 하는 평행 육면체의 체적. 기호 u·v·w.

7.Roman numerals

I, V, X 등의 로마 숫자

8.six-color photometry

6색측광. J. 스테빈스(1878-1966)에 의해 시작된 U(유효파장 3550Å), V(4200Å), B(4900Å), G(5700Å), R(7200Å), I(10300Å)필터에 의한 광전측광.

9.Valentine Number

V# (Coins)

10.대7 對

(대비·대립의 상태) versus ((abb.)v., vs.)

 

{"mean":["v<br/><br/>[약어]\n\t\t \t\t(vs 특히 美)\n\t\t 스포츠·소송에서\n\t\t \t\t…대(versus)","v.<br/><br/>valve; [수학] vector; velocity; verb; verse; version; versus ((L = against)); very; vicar; vice; vice-; vide ((L = see)); village","v.<br/><br/>volt(s); voltage","v<br/><br/>variable; velocity; vicinal; victory; 〈전기〉 volt(s).","V<br/><br/>[명사]\n\t\t \t\t브이(영어 알파벳의 스물둘째 글자)","scalar triple product<br/><br/>[명사]\n\t\t (수학)\n\t\t \t\t스칼라 삼중적(三重積): 3차원의, 주어진 세 개의 벡터 u, v, w를 세 변(邊)으로 하는 평행 육면체의 체적. 기호 u·v·w.","Roman numerals<br/><br/>I, V, X 등의 로마 숫자","six-color photometry<br/><br/>6색측광. J. 스테빈스(1878-1966)에 의해 시작된 U(유효파장 3550Å), V(4200Å), B(4900Å), G(5700Å), R(7200Å), I(10300Å)필터에 의한 광전측광.","Valentine Number<br/><br/>V#\n\t\t (Coins)","대7\n \t\t\t對<br/><br/>(대비·대립의 상태) versus ((abb.)v., vs.)"],"word":"\n\t\t\t\t\t\tv\n \t\t\t\n\t \t\n\t ","soundUrl":"https://dict-dn.pstatic.net/v?_lsu_sa_=39b8ad5ecd5b3d36e39eb17d3544c8fafd93630595074fdf6be268727bda67e18b5457296d653e77793462154e2a109c5f33378698ff2a567abaddf7d870f652c8eed0c75ffba9268387d5cef4840bf40f618cf9da728391022ee97603e750001690b83b4833b7806bcc3e8d71cc58c587c8c15a10ef10b5f4fd8dff99413429","phoneticSymbol":""}