매치무브(MatchMove)에 대해 아무것도 모르면서 이런 글을 쓴다는 것 자체가 어불성설이겠지만, 그래도 영상처리, 컴퓨터 비전을 하는 사람으로서 매치무브(MatchMove)가 무엇인지 개인적 호기심이 발동하여 여기저기 인터넷을 뒤져가며 글을 적게 되었습니다.

아무래도 VFX 쪽에 대해서는 전혀 모르는 상태에서 영상처리, 컴퓨터 비전 입장에서만 쓴 글이기 때문에 조금씩 틀리거나 부족한 부분이 있을 수 있습니다. 

매치무브(MatchMove)

매치무브(MatchMove)란 영화제작 과정 중 3D VFX(Visual FX, Visual effects, 시각 효과) 파이프라인(pipeline)에서 가장 중요한 작업 단계중 하나로서, 영화 씬이나 비디오로부터 이 장면을 찍은 카메라의 위치(궤적)를 복원, 추적해 내는 일을 말합니다.

그리고 매치무브(MatchMove) 작업을 하는 사람들을 매치무브 아티스트 또는 트레킹(tracking) 아티스트라고 부릅니다.

어쩌면 이 아티스트라는 호칭 때문에 더 호기심을 느낀건지도 모르겠습니다. 사실 공학쪽은 아무리 뛰어나도 아티스트라고는 하지 않기 때문에 막연한 동경 같은 것인지도 모르겠습니다.

<유투브에서 찾은 MatchMove 동영상>

VFX는 현대 영화에서 빼놓을 수 없는 요소이며 해리포터, 라이프 오브 파이, 엑스맨, 도둑들, 국가대표 등 대부분의 영화에 3D VFX가 들어갑니다.

VFX는 결국 실사 영상에 실제로는 없는 가상의 캐릭터, 사물, 또는 배경을 삽입하여 마치 실사 영상과 동일한 영상물을 창조해 내는 것이라 볼 수 있으며, 매치무브(Matchmove)-모델링(Modeling)-텍스처(Texture)-애니메이션(Animation)-크리처(Creature)-라이팅(Lighting)-렌더링(Rendering)-컴포지팅(Compositing)-VFX편집 등의 일련의 파이프라인을 거쳐 작업이 진행된다고 합니다.

이러한 실사 영상에 가상의 모델이 자연스럽게 녹아들도록 합성(composite)하기 위해서는 먼저 실사 영상을 촬영했던 카메라를 3차원 세계에서 다시 그대로 창조해 내야 하는데 이러한 작업이 매치무브(MatchMove)입니다.

즉, 매치무브는 일련의 실사 영상으로부터 촬영당시 사용된 카메라의 3D 시점, 줌, 내부 파라미터, 왜곡 등 카메라에 대한 모든 것을 복원, 추적해 내는 작업이라고 볼 수 있습니다.

실제로 매치무브 아티스트들은 마야라이브, 매치무버, PFTrack, 3D 이퀄라이저, boujou 등의 다양한 3D 소프트웨어 툴들을 이용하여 이러한 복원, 추적 작업을 해낸다고 합니다.

매치무브(MatchMove) & 3D 비전 기술

비디오로부터 3D 카메라를 복원해내기 위한 가장 기본적인 단계는 연속된 이미지들 사이의 2D 매칭을 통한 포인트 tracking 입니다.

이론상으로, 동일한(또는 overlap되는) 장면에 대한 서로 다른 두 시점에서의 영상이 있고 이 두 이미지 사이의 매칭 쌍들을 알면 카메라와 매칭 점들 사이의 3D geometry 관계를 복원할 수 있습니다.

여기서 3D 관계를 복원한다는 의미는 두 장의 매칭되는 2D 이미지로부터 원래의 3D 공간을 재구성할 수 있으며 또한 복원된 3D 공간에서의 카메라의 3D 시점(3차원 위치 및 방향)을 알아낼 수 있다는 의미입니다 (단, 복원된 공간의 스케일은 알지 못합니다). 이와 같이 비전에서 매칭되는 두 영상 사이의 기하 관계를 다루는 것을 epipolar geometry라고 하는데, 이에 대한 간략한 소개는 http://darkpgmr.tistory.com/83 글을 참조하시기 바랍니다.

전통적으로 컴퓨터 비전 분야에서는 비디오 영상으로부터 3D 공간 및 카메라 시점을 복원하는 연구는 mono SLAM (여기서 mono의 의미는 단일 카메라라는 의미임)을 통해 이루어져 왔는데, 영국 임페리얼 칼리지의 Andrew Davison 이 이 분야의 대표적인 연구자입니다 (홈페이지: http://www.doc.ic.ac.uk/~ajd/, 논문: "MonoSLAM: Real-Time Single Camera SLAM", PAMI 2007).

<그림> mono SLAM

또한 영국 옥스포드 대학의 Active Vision Group 에서는 2007년도에 이 분야의 프레임을 바꿀 수 있는 PTAM (Parallel Tracking And Mapping) 이라는 기술을 발표하였는데, PTAM이 나온 뒤로 기존의 Visual SLAM(Simultaneous Localization And Mapping)에 대한 연구 흐름이 크게 바뀌게 되었습니다.

PTAM을 이용하면 손으로 들고 찍은 단일 카메라 영상으로부터 3D 공간이 구축되면서 상대적인 카메라의 3D 시점이 복원되며, 매끄러운 증강현실(Augmented Reality)이 가능할 정도의 성능을 자랑합니다 (PTAM에 대한 내용은 나중에 기회가 되면 별도로 포스팅할 예정입니다) => PTAM(Parallel Tracking and Mapping)과 PTAMM

<PTAM 데모 동영상>

위 유투브 동영상을 보면, 컴퓨터 비전 분야에서의 PTAM 기술이 결국 VFX에서 매치무브(MatchMove)를 통해 하고자 하는 것과 거의 유사함을 알 수 있을 것입니다.

이런 관점에서 보면 매치무브에 사용되는 상용 3D 소프트웨어 툴들도 결국 기본적으로는 컴퓨터 비전 그룹에서 하는 visual tracking 기술, 3D mapping, structure from motion 기술 등을 기반으로 함을 알 수 있습니다.

마지막으로 공학쪽에서의 역할은 그러한 소프트웨어를 잘 만드는 것일 터인데, 그러한 소프트웨어를 활용하는 매치무브 아티스트에게 있는 공학 이상의 것은 어떤 것일까에 대한 호기심은 여전히 남습니다.

또한 3D 비전을 전공한 사람이 매치무브 아티스트로서의 길을 가는게 가능한지에 대한 것도 궁금증으로 남습니다.

☞ 예전에 한 현직 매치무브 아티스트분으로부터 이메일(그냥 블로그 잘 보고 있다는 간단한 인사말 정도의 내용)을 받은 적이 있었는데, 그 뒤로 죽 관심을 가지고 있다가 문득 생각이 나서 관련 글을 작성해 보았습니다.

by 다크 프로그래머

예전에 한 카메라에서 지원하는 출력 이미지 포맷 중에서 raw Bayer data 라는게 있어서 이게 뭘까 ? 하면서 찾아봤던 기억이 납니다.

그러면서 raw 베이터 패턴(Bayer pattern) 데이터를 그대로 출력하면 카메라의 데이터 전송량을 엄청나게 줄일 수 있음을 알게 되었습니다.

카메라에서 촬영한 이미지 데이터는 케이블(웹 카메라의 경우는 USB 케이블)을 타고 외부로 전송됩니다. 그런데, 케이블의 데이터 전송용량 (bandwidth)에는 한계가 있기 때문에 고해상도로 이미지를 보내려면 fps(frames per second)가 떨어지게 됩니다. 예를 들어, 웹 카메라처럼 USB 2.0 인터페이스를 사용할 경우 초당 30 MB/s 정도가 한계입니다 (이론상 최대속도는 60MB/s).

만일 카메라에서 R,G,B 칼라 영상을 내보낸다고 하면 이미지 해상도가 1,024 x 1,024일 경우 이미지 한장 당 3 MB 의 데이터 전송이 필요합니다. 하지만, raw Bayer pattern 데이터를 그대로 내보내면 색상 손실없이 1 MB의 데이터만 전송하면 됩니다. 즉, 카메라의 fps를 3배 정도 높일 수 있습니다.

우리가 흔히 어떤 카메라가 5백만화소라고 하면,

이 카메라의 이미지 해상도는 최대 2,500 x 2,000 정도이고 R, G, B 색을 감지할 수 있는 화소가 5백만개 포함된 이미지 센서를 사용하는 것으로 생각합니다.

그런데, 화소수가 5백만개인 것은 맞지만 각 화소는 실제로는 칼라(color)를 감지하는 화소가 아닌 단지 흑백의 밝기만을 감지하는 monochrome 화소이며 R, G, B 필터중 어느 하나와 결합된 형태입니다.

<그림> 이미지 센서의 필터 구조 (출처: 위키피디아)

즉, 이미지 센서는 화소수 만큼 배열된 mono 셀들 위에 R, G, B 색상 필터들이 특정한 패턴을 가지고 배치된 것이라고 볼 수 있습니다. 여기서 R 필터는 red만을, G 필터는 green만을, B 필터는 blue 만을 투과시키는 광학필터입니다.

그런데 하나의 센서 셀(cell)에는 R, G, B 필터 중 어느 하나만 결합되기 때문에, 하나의 이미지 화소는 R, G, B 중 한가지 색만을 감지할 수 있습니다.

(카메라 중에는 한 화소에서 R,G,B를 모두 감지하는 것도 있다고 합니다. 이에 대한 내용은 http://zero-gravity.tistory.com/28 '포베온 센서와 베이어패턴 센서' 글에 잘 정리되어 있습니다)

전통적인 CMOS, CCD 이미지 센서에서는 R, G, B 필터들이 일정한 패턴을 가지고 배치되는데, 인간의 시각 특성을 따라서 G가 50%, R과 B가 각각 25%가 되도록 아래 그림과 같이 교차 배치되며 이를 베이어 패턴(Bayer pattern)이라 부릅니다.

<그림> 베이어 필터 패턴

이와 같이 실제 이미지 센서는 각 화소에서 R, G, B 중 어느 한 색만을 감지할 수 있지만, 우리가 보는 카메라 영상에서는 각 화소마다 R,G,B 전체 색상을 보여줍니다.

이것이 가능한 이유는 소프트웨어적으로 각 화소마다 주변 셀들의 색상값을 보간(interpolation)하여 색을 구성하기 때문입니다.

따라서, 보간된 칼라 이미지를 받으면 화소별로 3 바이트가 필요하지만 원래의 raw Bayer pattern 데이터를 그대로 받은 후 PC 단에서 이미지를 보간하면 데이터 전송량을 크게 줄임으로써 프레임수를 늘릴 수 있게 됩니다.

raw Bayer 데이터로부터 화소별 색상을 보간하는 방법에는 여러 가지가 있으며 어떤 방법을 사용했느냐에 따라 최종 이미지의 화질이 크게 좌우된다고 합니다.

raw Bayer 데이터로부터 화소별 색을 보간하는 것을 demosaicing이라고 하는데, 아래 참고문헌을 바탕으로 가장 기본적인 방법 2가지만 적어봅니다. 보다 자세한 내용 및 그 외의 진보된 demosaicing 방법은 아래 참고문헌을 참조하시기 바랍니다.

참고문헌 : "Image Demosaicing: A Systematic Survey" by Xin Li

방법1. Pixel Doubling Interpolation

가장 기본적인 방법이지만 화질은 좋지 않다고 합니다. 그림 자체에 워낙 설명이 잘 되어 있어서 설명은 생략합니다.

방법 2. Bilinear Interpolation

이 방법 또한 직관적으로 생각해 낼 수 있는 기본적인 방법이며 pixel doubling 보간보다는 훨씬 화질이 좋습니다.

그림출처: http://www.unc.edu/~rjean/demosaicing/demosaicing.pdf

☞ 요즘 나오는 카메라들은 전통적인 베이터 패턴과는 다른 자신들만의 독특한 필터 패턴을 개발하여 사용하는 경우도 있다고 합니다. 자세한 내용은 위키피디아를 참조하세요.

☞ Mosaicing 방법 중 진보적인 방법은 카메라의 포커스가 항상 맞는 것은 아니라는 점을 이용해서 즉, 자신으로 와야 할 색 정보가 주변 cell에도 포커싱 정도에 따라 흩어져 포함되어 있다는 점을 이용한다고 합니다.

by 다크 프로그래머

들로네 삼각분할(Delaunay Triangulation)과 보로노이 다이어그램(Voronoi diagram)이 무엇인지? 어디에 쓰이는지? 그리고 어떻게 구하는지에 대한 글입니다.

1. 참고 문헌(자료)

참고한 주요 자료들입니다.

[1] 위키피디아(Wikipedia): Delaunay triangulation, Voronoi diagram

[2] Steve Oudot의 그래픽스 강의자료: Delaunay Triangulation I & II (강추)

[3] O'Reilly, Learning OpenCV

2. 용어

Delaunay triangulation은 들로네 삼각분할, 들로네 삼각망, 들로네 삼각형 등으로 불리며 Voronoi diagram(보로노이 다이어그램)은 Voronoi tessellation(보로노이 테셀레이션), Voronoi decomposition, Voronoi partition라고도 불립니다.

3. 들로네 삼각분할(Delaunay triangulation)이란?

들로네 삼각분할은 평면위의 점들을 삼각형으로 연결하여 공간을 분할할 때, 이 삼각형들의 내각의 최소값이 최대가 되도록 하는 분할을 말합니다.

<그림 1>

예를 들어, 위 그림 (a)와 같이 점들이 있을 때 이 점들을 연결하여 삼각형을 만드는 방법은 (b), (c)와 같이 다양합니다. 들로네 삼각분할은 이러한 여러 삼각분할 중에서 (b)와 같이 각각의 삼각형들이 최대한 정삼각형에 가까운 즉, (c)와 같이 길쭉하고 홀쭉한 삼각형이 나오지 않도록 하는 분할을 말합니다.

들로네 삼각분할의 가장 중요한 특징중 하나는, "어떤 삼각형의 외접원도 그 삼각형의 세 꼭지점을 제외한 다른 어떤 점도 포함하지 않는다" 입니다 (이를 empty circumcircle property라고 부릅니다). 삼각형이 홀쭉하고 길수록 외접원도 커짐을 생각하면 됩니다. 위 그림에서 (b)는 이 조건을 만족하고 (c)는 만족하지 않음을 쉽게 확인할 수 있습니다.

4. 보로노이 다이어그램(Voronoi Diagram)이란?

보로노이 다이어그램은 어떤 시드 점(seed point)들과의 거리에 따라서 평면을 분할한 그림으로서, 평면위에 주어진 시드 점 p1, p2, ..., pn에 대한 보로노이 다이어그램은 평면위의 점들이 어떤 pi와 가장 가까운지에 따라서 영역을 분할한 다이어그램을 말합니다.

예를 들어, 아래 왼쪽 그림과 같은 사각형 공간에 10개의 시드 점 (검은색 점들)을 주면 오른쪽 그림과 같은 보로노이 다이어그램이 나옵니다.

<그림 2> 그림출처: 위키피디아[1]

쉽게 생각하면 어떤 주어진 땅이 있고 그 땅 위에 있는 10개의 국가간의 국경선을 나눈다고 했을 때, 각 지역이 어떤 나라와 가장 가까운지에 따라서 영토를 나눈 것이 보로노이 다이어그램입니다. 이러한 관점에서 보면 각각의 보로노이 영역은 각 시드 점의 세력권을 나타낸다고 볼 수 있으며 그 경계선은 힘과 힘의, 세력과 세력의 균형점을 나타낸다고 볼 수 있습니다.

5. 들로네 삼각분할과 보로노이 다이어그램의 관계

들로네 삼각분할과 보로노이 다이어그램은 서로 듀얼 이미지(dual image) 관계에 있으며 어느 하나를 알면 다른 하나도 곧바로 구할 수 있습니다.

[들로네->보로노이]

보로노이 다이어그램의 각 seed 점들을 가지고 들로네 삼각분할을 구한 후에, 구해진 삼각형들의 외접원들의 중심을 연결하면 보로노이 다이어그램이 나옵니다.

좀더 상세하게 말하면, 어떤 점을 공통의 꼭지점으로 하는 들로네 삼각형들의 외접원들의 중심을 순서대로 연결하면 이 공통점을 seed로 하는 보로노이 영역이 나옵니다.

[보로노이->들로네]

서로 인접한 보로노이 영역들간의 seed 점들을 연결하면 이 seed 점들에 대한 들로네 삼각분할이 얻어집니다.

<그림 3> 그림출처: 참고문헌 [3]

이와 같이 Delaunay triangulation과 Voronoi diagram은 서로 dual 관계에 있으며 어느 하나를 알면 다른 하나를 곧바로 구할 수 있기에 그 응용이나 계산 알고리즘도 거의 같은 거라고 생각하면 됩니다.

보로노이 다이어그램을 정의한 Voronoi와 들로네 삼각형을 고안한(1934) Delaunay 두 사람 모두 러시아 수학자입니다. 

<그림 4> 그림출처: 참고문헌 [2]

6. 자연에 존재하는 Delaunay triangulation / Voronoi diagram 예

<그림 5> 그림출처: 참고문헌 [2]

7. 응용

[데이터 클러스터링]

주어진 데이터 분포에서 유의미한 클러스터(cluster)를 뽑아내는 것은 data mining, classification 등에서 매우 어려운 문제 중 하나입니다 (특히 클러스터의 개수를 모르고 있을 때).

<그림 6> 그림출처: "an adaptive spatial clustering algorithm based on delaunay triangulation", CEUS 2011.

들로네 triangulation을 이용하면 이러한 클러스터링을 효과적으로 할 수 있는데, 먼저 데이터 점들을 Delaunay triangulation으로 연결한 후에 일정한 길이 이상의 긴 변들을 제거하고 남은 연결된 성분들을 구하면 됩니다.

[데이터 분포 밀도]

평면에 흩뿌려진 점들의 밀도를 수치화하는 용도로 사용되는 경우

<그림 7> DTFE(그림출처: 위키피디아[1])

그 방법은 어떤 점 p에서의 밀도를 점 p를 꼭지점으로 하는 주변 Delaunay 삼각형들의 면적의 합의 역수(밀도 = c/(s1+s2+...+sk))로 정의합니다. 그리고 이들 점에서의 밀도값을 보간(interpolation)함으로써 또한 공간 전체에서 밀도를 수치화하는 것입니다. 이러한 분포 밀도 수치화 방법을 Delaunay tessellation field estimator (DTFE)라고 하며, 주 응용은 우주 천체를 분석하는 용도라 합니다만 자세한 건 잘 모릅니다.

구체적인 예는 떠오르지 않지만 컴퓨터 비전에서도 나름 유용하게 활용될 수 있을 거라는 느낌이 듭니다.

[도로망 설계]

도시와 도시를 연결하는 도로망을 설계할 때, Delaunay triangulation이 하나의 참조모델로 활용될 수 있습니다.

<그림 8> 고대 로마의 도로망 (그림출처: 네이버 지식백과)

만일 n개의 도시가 있을 때 모든 도시와 도시를 직접 직선도로로 연결할 경우에는 총 nC2 = n(n-1)/2개의 도로가 필요합니다. 하지만, 모든 도시를 서로서로 직접 연결하는 것은 너무 비효율적이기 때문에 실제로는 일부 도로만을 연결하여 전체 도시들이 연결되도록 해야 할 것입니다.

이 경우 도시 A에서 도시 B로 이동할 때 직접 연결된 도로가 없다면 다른 도시들을 우회해서 이동해야 할 것입니다. 그런데, 이 때 중요한 점은 도시 A에서 도시 B로 이동하기 위해 이동한(우회한) 총 이동거리가 A-B 사이의 직선거리에 비해 최소화되도록 도로망을 설계하는 것일 것입니다.

만일 삼각분할 형태로 도로망을 설계한다고 했을 때, 들로네 삼각화를 이용하여 도로를 연결하면 우회에 따른 이동거리의 증가를 최소화할 수 있습니다.

[Minimum Spanning Tree(MST)]

Minimum Spanning Tree (MST)는 n개의 지점을 모든 점들이 서로 도달 가능하면서 전체 거리의 합이 최소가 되도록 연결한 트리 구조의 그래프입니다. MST는 주어진 지점들을 연결하는 최소 비용의 네트워크 회선망이나 파이프 망을 찾을 때 활용될 수 있습니다. 또한 잘 알려진 TSP (Traveling Salesman Problem 즉, n개의 도시를 최단 거리로 순회할 수 있는 방문 경로를 찾는 문제)도 MST를 활용하면 최적해 길이의 2배 이내에서의 근사해를 찾을 수 있습니다.

<그림 9> MST (그림출처: 위키피디아[1])

MST를 구하는데 들로네 triangulation을 활용하는 방법은, 먼저 주어진 점들에 대한 들로네 triangulation을 구하고 그 결과 그래프를 MST 구하는 알고리즘의 입력으로 사용하는 것입니다. 이렇게 하면 fully linked graph에서 직접 MST를 구하는 것보다 훨씬 효율적으로 MST를 구할 수 있게 됩니다. 단, 이는 들로네 triangulation이 항상 MST를 포함함을 전제로 하고 있는데 그 증명은 위키피디아를 참조하시기 바랍니다.

[Convex Hull 구하기]

어떤 점들의 집합에 대한 Convex Hull 이란 쉽게 생각하면 그 점들을 실로 팽팽하게 둘러쌌을 때 생기는 볼록(convex) 다각형입니다 (아래 그림에서 주황색 도형).

<그림 10>

Delaunay triangulation을 이용해서 convex hull을 구하는 방법은, 원래의 점들의 집합에 외부의 점 3개를 추가하여 들로네 삼각분할을 구한 후 어떤 점들이 새로 추가된 외부의 점과 삼각형을 이루었는지를 조사하면 됩니다. 그래서 새로 추가한 외부의 점과 삼각형을 형성한 점들을 연결하면 원래 점들에 대한 convex hull이 나옵니다. 단, 외부의 점을 잡을 때에는 원래 점들이 외부 점들을 잊는 삼각형에 모두 포함될 수 있도록 멀리 떨어진 점들로 잡아야 합니다.

[Nearest Neighbor 구하기]

어떤 점들의 집합에 대한 들로네 삼각분할이 있으면 nearest neighbor를 곧바로 구할 수 있게 됩니다. 예를 들어, 아래 그림에서 p의 nearest neighbor를 구하고 싶으면 점 p와 연결된 edge들만 조사하면 이들 중에 nearest neighbor가 존재하게 됩니다.

<그림 11> 그림출처: 참고문헌[2]

즉, 원래는 모든 점들과 일일히 거리를 비교해 봐야 하겠지만 들로네 삼각분할이 있으면 그 점과 연결된 점들과의 거리만 조사하면 된다는 의미입니다.

또한 k-nearest neighbor를 구할 때에도 들로네 삼각망에서 직접 연결된 점들로부터 시작해서 tree 형태로 점차 탐색범위를 확장해가면 됩니다.

[Reconstruction]

포인트 클라우드(point cloud)로부터 물체의 3D 입체를 모델링하여 복원할 때에도 Delaunay triangulation이 활용될 수 있습니다. 하지만 이 경우에는 삼각형은 사면체로, 원은 구로 확장된 버전의 Delaunay triangulation을 이용해야 합니다.

<그림 12> 그림출처: 참고문헌 [2]

[물체에 대한 polygon mesh 생성]

들로네 삼각분할의 본연(?)의 응용이라 볼 수 있습니다. 3D 입체 물체의 표면을 폴리곤으로 모델링할 때 들로네 triangulation을 이용하면 표면위의 점들의 집합으로부터 nice(?)한 폴리곤 메쉬를 얻을 수 있습니다. 3D 입체 표면을 폴리곤으로 모델링하는 이유는 빠른 랜더링(rendering)이 가능하기 때문입니다.

<그림 13> 그림출처: N. Aghdaii et. al., "5-6-7 Meshes," Proc. of Graphics Interface, 2012.

[3D 일러스트레이션]

Jonathan Puckey라는 사람이 2008년도에 개발한 방법으로 Delaunay Raster라는 그래픽 툴이 있습니다. 이 기법은 Delaunay triangulation을 이용하여 입력 사진으로부터 입체감을 갖는 3D 일러스트를 생성하는 것으로서, 사용자가 사진위에 입력한 점들로부터 들로네 삼각분할을 이용한 폴리곤 메쉬를 생성하고 그 색상값을 삼각형 내의 평균 색상으로 설정하는 방법입니다 (관련 URL: http://jonathanpuckey.com/projects/delaunay-raster/)

<그림 14> 그림출처: http://jonathanpuckey.com/projects/delaunay-raster/

[로봇 네비게이션]

로봇이 길을 찾고 목적지까지 이동할 때, 주변 장애물과 부딪히지 않고 안전한 길을 찾는 것이 무엇보다도 중요합니다. 보로노이 다이어그램을 이용하여 이동경로를 생성하면 공간의 가장 빈 곳을 따라서 이동하기 때문에 안전성을 확보할 수 있습니다.

<그림 15> 그림출처: 참고문헌 [2]

8. 들로네 삼각분할 알고리즘

들로네 삼각분할을 구하는 알고리즘은 크게 incremental 알고리즘과 divide and conquer 알고리즘으로 나눌 수 있습니다. 두 알고리즘의 속도는 O(n log n)이라고 합니다.

Incremental 알고리즘은 점들을 하나씩 추가해 가면서 점진적으로 분할을 완성하는 방식이고, divide & conquer 방식은 입력 점들을 recursive하게 두 그룹으로 나누고 각각의 그룹에 대한 들로네 삼각분할을 얻은 후에 다시 두 그룹을 합치는 방식입니다.

Divide & conquer 방식이 들로네 삼각분할 알고리즘 중 가장 빠른 방식이라고 합니다. 하지만 사용자와 인터렉티브하게 mesh 작업을 할 때에는 incremental 방식이 보다 적합할 것입니다.

8.1 Incremental 알고리즘

incremental 알고리즘을 이해하기 위해서는 먼저 flipping에 대해 알아야 합니다. 어떤 사각형을 대각선을 따라 두개의 삼각형으로 나누는 방법은 2가지가 있습니다. 이 때, 만일 어느 한 분할이 Delaunay 조건을 만족하지 않는다면 다른 대각선 방향으로의 분할은 반드시 Delaunay 조건을 만족하게 됩니다. 이와 같이 분할 방향을 바꾸어서 Delaunay 조건을 만족시켜 나가는 것을 flipping이라고 합니다.

<그림 16> 그림출처: 위키피디아[1]

가장 기본적인 incremental 알고리즘은 앞서 설명한 Convex Hull 구하기 응용에서처럼 먼저 원래 점들로부터 무한히 멀리 떨어진 외부의 3 점(아래 그림의 녹색 점들)을 설정한 후에, 하나씩 원래 점들을 추가하면서 Delaunay triangulation 조건을 만족하도록 삼각분할을 조정하는 형식으로 진행합니다.

<그림 16>

먼저, 현재 새로 추가된 점을 포함하는 삼각형의 세 꼭지점과 새로 추가된 점을 연결하여 새로운 분할을 만듭니다 (그림의 오렌지 색). 이후 새로 추가된 삼각형들과 맞닿은 삼각형들에 대해 차례로 flip 알고리즘을 적용하여 모든 삼각형들이 Delaunay 조건을 만족하도록 합니다 (empty circumcircle condition). 예를 들어, 위 그림에서 ABCD에 대해 조건을 검사해서 만족하지 않는다면 분할 방향을 BD에서 AC로 바꾸어 줍니다. 분할 방향이 변경된 경우에만 변경된 삼각형들과 인접한 삼각형들에 대해서 flipping 검사가 전파됩니다.

8.2 Divide and Conquer 알고리즘

Divide and conquer 방식은 원래의 입력 점들을 하나의 직선을 경계로 두 그룹으로 나누고, 각각의 그룹은 또 다른 직선으로 다시 세부 그룹으로 나누는 방식으로 recursive하게 그룹을 나누되, 각 그룹에 속한 점의 개수가 3개 이하일 때까지 분항을 진행합니다.

<그림 17> 그림출처: 참고문헌 [2]

이후, 각 그룹에서 들로네 삼각분할을 구한 후, 그룹들을 다시 합쳐나가면서 전체적으로 들로네 조건을 만족하도록 분할을 구하는 방식입니다. 두 그룹의 Delaunay 삼각분할을 합치는 세부적인 내용에 대해서는 관련 논문 등을 참고하시기 바랍니다.

☞ 참고로 저는 그래픽스 쪽 전공이 아니며 이 글에 있는 내용 이상은 잘 알지 못합니다. 한 방문자분의 요청의 의해 작성한 글로서 관련 내용이 흥미로운 점이 많아서 저도 같이 공부를 할 겸해서 작성한 글입니다.

by 다크 프로그래머