1. 서 론

이차원 공간에 점들이 임의의 위치에 놓여 있을 때 이 들 점들을 빠짐없이 연결하여 모서리 이외에는 겹치지 않는 삼각형들의 집합을 구성하는 것을 삼각화(triangulation)라 한다. 삼각화는 여러 가지 형태가 존재하는데, 그 중 딜러 니 삼각화(Delaunay triangulation)는 보로노이 다이어그램 (Voronoi diagram)의 쌍대(dual) 구조인데, 삼각화를 구성 하는 삼각형들 사이의 최소 각을 최대화 하는 특성을 가 지고 있어 품질 높은 삼각형 메시(mesh)를 생성한다. 이 런 이유로 컴퓨터 그래픽스, 3D 프린팅, 역공학, CAE해 석 등 다양한 응용 분야에서 널리 이용되고 있다[3, 10, 11]. 그러나 딜러니 삼각화 역시 주어진 점들의 상대적인 위치에 따라서 품질이 낮은 삼각형이 생성될 수도 있다. 이러한 문제의 해결을 위하여 주어진 꼭지점들의 위치를 이동시키거나 꼭지점들을 추가하여 삼각화를 개선하거나 최적화하는 방법이 존재한다[14].

딜러니 개선 알고리듬(Delaunay refinement algorithm) 이란 딜러니 삼각화가 주어져 있을 때, 품질 낮은 삼각형 의 외접원 중심에 새로운 점을 추가하여 해당 삼각형 주 변의 삼각화를 개선하고, 이를 반복적으로 수행하여 전 체 딜러니 삼각화를 개선하는 방법이다. Chew와 Ruppert 의 연구를 시작으로 많은 연구가 진행되고 있으며[1, 2, 6, 12, 13, 14], 개념 및 알고리듬이 단순하고 품질 높은 삼각형 메시(quality triangular mesh)를 효율적으로 생성 할 수 있기 때문에 여러 응용 분야에 이용되고 있다.

그 중 Ruppert의 알고리듬은 삼각형들의 최소 각이 주 어진 값 이상이 될 때까지 딜러니 개선 과정을 반복한다. 이를 통해 전체적으로 정삼각형에 가까운 삼각형들로 이 루어진 삼각화를 얻을 수 있게 된다. 본 논문에서 제안하 는 보로노이 곡면의 삼각화 방법은 Ruppert의 알고리듬 을 기반으로 하는데, 보로노이 곡면의 고유한 특성을 반 영하도록 수정하여 3차원 곡면의 품질 높은 삼각화를 구 성하는 방법을 제안하고 구현 결과를 보여준다.

삼차원 구의 보로노이 다이어그램은 구들이 삼차원 유 클리드 공간에 주어져 있을 때, 공간을 각각의 주어진 구에 가장 가까운 영역으로 분할한 구조를 말한다. 모든 물질은 입자로 이루어져 있고, 원자나 분자는 구의 형태로 모델링 할 수 있기 때문에 재료과학, 분자 생물학 등의 많은 문제 들은 구와 매우 밀접한 관련이 있다고 할 수 있다. 일단 구의 보로노이 다이어그램이 구해져 있다면 빈 공간의 분 석, 특정 구가 영향을 미치는 영역 등과 같은 구와 관련된 공간의 분석을 매우 효율적으로 수행할 수 있다. 유클리드 공간의 구 보로노이 다이어그램의 알고리듬, 응용문제 등 과 관련해서는 다음의 문헌을 참고하기 바란다[5, 7, 8].

구의 보로노이 다이어그램에 대한 보로노이 곡면의 삼 각화 방법론으로 Will의 연구가 있다[15]. Will은 각각의 보로노이 영역에 대하여 이를 구성하는 보로노이 모서리 들을 생성자의 중심에 위치한 단위 구에 사영하여 영역을 분할한 후, 분할된 구면을 삼각화하고 보로노이 곡면에 사영하여 곡면을 삼각화 하였다. 이를 통해 각 보로노이 영역을 가시화하고 영역이 차지하는 부피의 분포를 분석 하였다[15]. Kim 등은 단백질에서의 상호작용면을 정의 하고 분석하기 위하여 단백질을 구성하는 구의 보로노이 다이어그램을 이용하였다[4]. 이때 Kim 등은 상호작용면 을 보로노이 곡면의 부분 집합으로 정의하였고 이를 가시 화하기 위하여 해당 보로노이 곡면을 삼각화하였다.

본 논문은 다음과 같이 구성되어 있다. 제 2장에서는 배경 이론이 되는 보로노이 다이어그램과 딜러니 개선 알고리듬에 대해 개략적인 설명을 하고, 제 3장에서는 삼 차원 구의 보로노이 곡면의 삼각화 방법을 제안한다. 제 4장과 제 5장에서는 제안하는 알고리듬의 구현 방법 및 실험 결과를 설명하고, 제 6장에서는 결론을 제시한다.

2. 배경 이론

본 절에서는 본 논문에서 다루고 있는 삼차원 구의 보 로노이 다이어그램과 보로노이 곡면의 삼각화를 위해 이 용되는 딜러니 개선 알고리듬을 설명한다.

2.1 구의 보로노이 다이어그램

3차원 공간에서 유클리드 거리 기반의 구의 보로노이 다이어그램은 다음과 같이 정의된다. 보로노이 생성자 (generator) s_i는 중심이 P_i = (x_i, y_i, z_i )이고 반지름이 r_i인 구로 정의된다. 생성자 집합 S = {s_i, i = 1, ⋯, n}으로 정 의한다. 보로노이 생성자 s_i의 보로노이 영역은 V ( s i ) = { P ‖ P − P i ‖ − r i ≤ ‖ P − P j ‖ − r j , ∀ j ≠ i } 으로 정의된다. 단, ‖ ⋅ ‖는 두 점 사이의 유클리드 거리를 나타낸다. 삼차원 구 의 보로노이 다이어그램은 VD ( S ) = { V ( s i ) , i = 1 , ⋯ , n } 으로 정의할 수 있다. 삼차원에서 구의 보로노이 다이어그 램의 알고리듬, 성질 및 구현에 관해서는 다음의 문헌을 참고하기 바란다[5, 8].

보로노이 곡면은 보로노이 영역의 경계를 이루는데, 가장 가까운 두 구 사이의 거리가 동일한 점들의 집합으 로 정의된다. 두 구 s_i와 s_j사이에 보로노이 곡면이 존재 한다면, 보로노이 곡면은 V F ( s i , s j ) = { P ‖ P − P i ‖ − r i = ‖ P − P j ‖ − r j } 으로 정의된다. 점의 보로노이 다이어그램 VD(P)에서 보로노이 영역의 경계는 평면이 되는 것과는 달리 구의 보로노이 다이어그램의 보로노이 영역의 경계 는 곡면을 이루며, 2엽 쌍곡면(two-sheet hyperboloid)의 일부가 된다는 성질은 잘 알려져 있다[5, 9].

보로노이 곡선은 가장 가까운 세 구와의 거리가 동일 한 점들의 집합으로 정의된다. 보로노이 곡선은 보로노 이 곡면의 경계를 이루며, 기하학적 형태는 이를 정의하 는 세 구의 상대적인 위치에 따라 직선, 쌍곡선, 포물선, 또는 타원의 형태가 된다. 이는 쌍곡면(보로노이 곡면)과 평면과의 교점으로도 정의할 수 있다.

2.2 딜러니 개선 알고리듬

딜러니 개선 알고리듬은 <Figure 1>에서와 같이 꼭지 점 집합과 세그먼트(segment) 집합을 입력으로 할 때, 새 로운 꼭지점을 세그먼트의 중심 또는 기존 삼각형의 외 접원 중심에 추가하여 사용자가 요구하는 품질 조건을 만족하는 딜러니 삼각화를 구성하는 방법이다. 최종 삼 각화의 꼭지점은 입력 꼭지점들을 모두 포함해야 하며, 삼각화의 모서리가 놓이는 영역은 입력된 세그먼트의 영 역을 모두 포함해야 한다. 또한 만족시켜야 하는 품질 조 건의 예로는 삼각화를 구성하는 모든 삼각형들 중 최대 모서리 길이, 최소 각도(minimum angle), 삼각형의 최대 크기 등이 가능하다.

<Figure 1>은 딜러니 개선 알고리듬의 입력 요소들과 수행된 결과의 예를 보여준다. <Figure 1(a)>의 파란색 점은 입력 꼭지점을, 붉은색인 선분은 세그먼트를 나타 낸다. <Figure 1(b)>는 알고리듬 수행 결과를 보여주는데, 최종 삼각화는 초기 꼭지점을 모두 포함하며, 초기 세그 먼트는 여러 개의 하위 세그먼트로 분할될 수 있으며, 각 세그먼트는 삼각화를 구성하는 삼각형의 모서리를 이루 어야 한다. 새로이 추가된 꼭지점들은 그림에서 녹색으 로 표시하였고, 초기 입력된 꼭지점 이외에 세그먼트 위 9개와 나머지 3개의 꼭지점이 추가된 것을 알 수 있다. <Figure 1(b)>는 최소 각 30°를 품질 조건으로 적용한 결 과이다. 그리하여 모든 삼각형들에 대하여 최소 각은 30° 이상이 된다.

딜러니 개선 알고리듬에서 두 가지 기본 연산은 split_ triangle과 split_segment 연산이다. Split_triangle은 가장 핵 심이 되는 연산으로, <Figure 2(a)>에서와 같이 얇은 삼각 형 t가 있을 때 삼각형의 외접원 중심 υ를 새로운 꼭지점 으로 추가하고 지역적으로 수정하여 새로이 개선된 딜러 니 삼각화를 구성한다. 본 연산을 수행하면 삼각형 t의 최 소 각이 두 배가 되어 지역적으로 더 나은 삼각화를 얻을 수 있으며, 품질이 좋지 않은 삼각형들에 반복적으로 적용 하면 전체적으로 높은 품질의 삼각화를 얻게 된다.

Split_segment 연산은 세그먼트 중심에 새로운 꼭지점 을 추가하여 두 개의 세그먼트로 분할한다. 이후 지역적 으로 수정하여 새로운 딜러니 삼각화를 개선하는 것을 말 한다. <Figure 2b>에서와 같이 세그먼트를 지름으로 하는 원을 세그먼트원(segment circle)이라 하고, 세그먼트원이 다른 꼭지점을 포함하면 해당 세그먼트는 위반한다고 표 현한다. Split_segment 연산은 위반 세그먼트에 대하여 실 행하며, 위반 세그먼트가 없어질 때까지 반복한다. 이러 한 과정을 <Figure 2(b)>에서 설명하고 있다. 첫 번째 그 림에서 세그먼트원이 다른 두 꼭지점을 포함하기 때문에 split_segment 연산을 수행하여 가운데의 결과를 얻었고, 가운데 그림의 아래 세그먼트가 또다시 위반하기 때문에 split_segment 연산을 한 번 더 수행하여 우측의 결과를 얻었다. 딜러니 개선 알고리듬을 요약하면 다음과 같다.

딜러니 개선 알고리듬

입력 : 꼭지점 집합 V , 세그먼트 집합 S , 품질조건 q

3. 방법

이번 절에서는 보로노이 곡면의 삼각화 방법을 제안 한다.

3.1 보로노이 곡면의 삼각화

보로노이 곡면은 두 구와 동일한 거리를 가지는 점들 중에서 주어진 두 구를 가장 가까운 쌍으로 하는 점들의 집합으로 정의된다. 이는 두 구의 중심을 초점으로 하는 2엽 쌍곡면(two-sheet hyperboloid, 이후 쌍곡면으로 표현 함) 중 반지름이 작은 구에 가까운 곡면의 일부가 되며 반지름이 큰 구의 방향으로 볼록하다. 두 구의 반지름을 동일한 크기만큼 줄여도 해당 쌍곡면은 그대로 유지가 되는데, <Figure 3>은 두 구의 반지름을 작은 구의 반지 름 크기만큼 각각 줄였을 때의 쌍곡면을 보여준다. 만약 두 구의 크기가 동일하다면 두 구는 모두 점으로 줄어들 것이고 해당 곡면은 평면이 된다.

3.1.1 표준 공간(Canonical Space)

각각의 보로노이 곡면은 삼차원 상에서 임의의 방향 으로 존재하지만, 이를 표준화된 공간에 위치시키면 삼 각화 계산이 매우 편리해진다.

표준 공간은 다음과 같이 정의된다. 대상이 되는 보로 노이 곡면을 f라 하자. 또한 f를 정의하는 두 구를 s_b = (P_b, r_b), s_s = (P_s , r_s)라 하자. 이때, P_b와 P_s는 구의 중 심을 나타내고, r_b와 r_s는 반지름이며 r_b ≥ r_s ≥ 0이다. 두 구의 중심 P_b와 P_s의 중점을 P_m이라 하자. 이때 표준 공간이란 (1) P_m을 해당 공간의 원점으로 평행 이동 후, (2) 큰 구의 중심인 P_b를 음의 z축 상으로 작은 구의 중 심을 양의 z축 상으로 위치시키는 회전 변환을 통하여 이동한 공간으로 정의된다.

위의 변환을 통하면 d = ‖ P b − P m ‖ 이라 할 때, 큰 구 s_b의 중심은 표준 공간에서 (0, 0, -d)에 놓이게 되고, 작 은 구 s_s의 중심은 (0, 0, d)에 놓이게 된다. <Figure 3>은 표준 공간을 그림으로 설명하고 있다. 그림에서와 같이, 표준 공간에서는 반지름의 차이 r = r_b - r_s은 0보다 크거 나 같으며, 만약 양수(r > 0)인 경우 보로노이 곡면은 항 상 z > 0 공간에 존재하게 된다.

3.1.2 표준 공간에서 보로노이 곡면의 수식

표준 공간에서 보로노이 곡면 위의 점 P = (x, y, z) 라 하고, 변환된 두 구의 중심을 F_s = (0, 0, d)와 F_b = (0, 0, -d)라 할 때, 다음의 수식이 성립한다.

식 (1)을 풀어 쓰면 다음과 같이 정리된다.

식 (2)에서 양 변의 거듭제곱을 통하여 근호를 제거하 면 다음과 같은 음함수 형태의 수식으로 정리할 수 있다.

식 (3)은 표준 공간에서 xy-평면에 대칭인 2엽 쌍곡면이 되는데, 보로노이 곡면은 두 장의 곡면 중 z > 0의 공간에 놓이는 것이기 때문에 다음의 함수로 정리할 수 있다.

표준 공간에서 보로노이 곡면의 곡률(curvature)은 x = y = 0에서 다음과 같이 정의된다.

3.1.3 표준 공간에서 보로노이 곡면의 삼각화

보로노이 곡면은 쌍곡면의 일부이기 때문에 한쪽으로 만 볼록한 형태를 띠며, 표준 공간에서는 <Figure 3>에서 와 같이 z축의 음의 방향으로 볼록하다. 그렇기 때문에 보로노이 곡면 위의 점들이 주어져 있을 때, 곡면의 삼각 화는 삼차원 공간에서 곡면 위의 점들에 대한 볼록다면 체(convex hull)를 구한 후 xy-평면에서 z축 방향으로 보 이는 경계 면들만을 취하면 얻을 수 있다. 또한 이는 표 준 공간에서 보로노이 곡면 위의 점들을 xy-평면으로 사 영한 후 딜러니 삼각화를 계산한 결과와 동일하다[11].

그렇기 때문에 제안하는 알고리듬은 표준 공간에서 보 로노이 곡면 위의 점들을 xy-평면으로 사영한 후 딜러니 개선 알고리듬을 통하여 요구 품질을 만족하는 삼각화를 계산한 후, 이를 다시 식 (4)를 통하여 보로노이 곡면 위 로 평행 이동하여 곡면의 삼각화를 얻는다.

3.1.4 평면에서의 삼각화와 차이점

2차원 평면에서는 삼각화의 품질 척도로는 삼각형의 최소각, 삼각형의 면적, 삼각형의 개수 등 여러 가지가 있을 수 있다. 이 중 딜러니 개선 알고리듬에서 주로 삼 각형의 최소각이 삼각화의 품질을 조절하는 파라미터의 역할을 한다.

본 논문에서 대상으로 하는 삼각화는 3차원 공간에서 곡면 위에서 이루어진다. 그렇기 때문에 2차원 평면에서 와 마찬가지로 뾰족한 삼각형을 개선하여 더욱 정삼각형 에 가까운 삼각형들로 구성되게 하는 것이 중요하다. 이 와 더불어 본 논문에서는 보로노이 곡면을 근사화하는 것이기 때문에 대상 곡면과 결과 삼각화와의 오차가 품 질을 결정하는 매우 중요한 요소가 된다.

3.2 삼각화 오차의 정의

보로노이 곡면을 삼각화하면 곡면과 삼각화 사이의 오차가 존재한다. 본 논문에서 제안하는 알고리듬은 곡 면 오차의 허용치를 입력 값으로 받은 다음 이를 만족하 는 삼각화를 생성하기 때문에 오차의 정의가 삼각화의 품질을 조절하는데 있어 매우 중요하다. 이러한 곡면의 오차는 다양한 방식으로 정의할 수 있다. 오차를 정의하 는데 있어서 고려해야 하는 사항으로 두 가지를 들면 다 음과 같다. (1) 실제 오차를 잘 반영해야 하며, (2) 계산 이 쉬워야 한다. 이러한 사항을 고려하여 본 논문에서는 다음의 방식을 제안한다.

우선 삼각화를 구성하는 각각의 삼각형에 대하여 보로 노이 곡면과의 오차를 정의할 수 있다. 삼각화를 구성하 는 임의의 삼각형을 t라고 할 때, t의 세 꼭지점은 정의에 의해서 보로노이 곡면 위에 위치한다. <Figure 4>에서와 같이 삼각형의 외심을 P_c라 할 때, P_c를 통과하면서 t에 수직인 직선을 l이라 하자. 직선 l과 곡면 f의 교차점을 P^*라 할 때, 삼각형 t의 곡면 오차 є_t는 두 점 사이의 거리 ‖ P * − P c ‖ 로 정의한다. 이때, P^*는 삼각형 t가 split_triangle (t) 연산에 의해 분할될 때 새로운 꼭지점의 위치로 이용 된다. 그리고 P^*를 xy-평면에 사영한 점이 DT(V)의 새 로운 꼭지점이 된다.

제안하는 방법은 삼각형의 외심을 계산한 후 외심을 통과하는 직선과 곡면의 교점만을 계산하면 가능하므로 계산이 매우 간단한 장점이 있다. 또한 공간에서의 삼각 화가 실제 곡면에 가까워질수록 삼각형과 교점 사이의 거리가 줄어들기 때문에 오차를 매우 잘 반영한다고 할 수 있다.

3.3 삼각화 알고리듬

보로노이 곡면의 삼각화 알고리듬은 곡면을 표준 공간 으로 변환한 후, 경계모서리들을 분할하여 세그먼트를 구 성하고 이들을 xy-평면으로 사영한다. 전처리 과정으로 사영된 세그먼트들을 입력으로 하는 초기 삼각화를 xy- 평면에서 구성한 후, 반복적인 딜러니 개선 과정을 통하 여 허용 오차를 만족시키는 삼각화를 구한다. 이를 요약 하면 다음과 같다.

보로노이 곡면 삼각화

입력 : 보로노이 곡면 f, 경계 모서리 리스트 E , 허용오차 є_b

[전처리]

[반복]

출력 : 현재의 DT(V

경계 모서리를 통하여 생성된 세그먼트의 개수를 m이 라 할 때, 전처리과정은 5번 과정에서 최악의 경우 O(m²) 시간이 소요될 수 있다. 반면 6번 과정은 허용오차에 의 해 반복 횟수가 결정되는데, 1회 반복 시 최대 O(m) 시 간이 소용될 수 있다. 그러나 참고문헌[6]에 소개된 버킷 구조를 활용한다면 전처리 과정은 평균적으로 O(m) 시 간에, 반복 과정은 1회당 평균 O(1) 시간에 계산 가능하 게 된다. 보로노이 곡면은 대부분의 경우 10개 미만의 경계 모서리를 가지고 있으므로 이론상 최악의 경우인 O(m²) 시간이 요구된다 하더라도 실제로는 매우 빠르게 계산된다.

4. 구현 및 실험

본 연구에서 제안하는 보로노이 곡면의 삼각화 알고리 듬을 C++로 구현하여 실험하였다. 실험을 위하여 <Figure 5>에서와 같이 1,000개의 구를 컨테이너라 불리는 원점 이 중심인 가상의 큰 구에 포함되도록 랜덤하게 생성하였 다. 생성된 구들은 서로 교차가 없고 구들의 반지름은 범 위[1, 2]에 확률적으로 균등하게 분포하도록 하였다. 컨테 이너 구의 반지름은 대략 27.65이며, 생성된 구들의 밀도 는 대략 0.178이다.

보로노이 영역을 제안하는 방법으로 계산하기 위해서 는 먼저 구의 보로노이 다이어그램을 계산한다. 실험에 서는 모서리 추적 알고리듬[8]을 통하여 계산하고 모서 리의 수식을 계산하였다. 그런 다음 각각의 보로노이 곡 면에 대하여 전처리 작업인 초기 삼각화를 계산하고 주 어진 허용오차를 만족시키기 위하여 딜러니 개선 과정을 반복한다.

5. 실험 결과 및 고찰

결과를 가시화하고 오차를 측정하기 위하여 <Figure 5(b)>에서와 같이 하나의 구를 임의로 선택하였고, 해당 구의 보로노이 영역을 구성하는 보로노이 곡면을 다른 구들과 함께 가시화 하였다. 그림의 보로노이 영역은 21 개의 보로노이 곡면으로 구성되어 있고, 구들의 볼록 다 면체(convex hull) 내부에 위치하기 때문에 닫혀있다. 21 개 곡면들의 곡률의 분포는 0과 1.11사이에 분포한다.

<Figure 6>에는 허용오차 є_b를 1, 0.1, 0.01, 0.001로 설 정하고 이에 대한 삼각화 결과를 가시화 하였다. 그림에 서 보여지듯이 허용오차가 작아질수록 더욱 많은 수의 삼각형으로 분할되며, 실제 쌍곡면에 가까워짐을 알 수 있다.

실험에서의 보로노이 영역은 서로 다른 곡률을 가지 는데, 동일한 허용오차에 대해서도 곡률이 큰 곡면일수 록 삼각형의 분포가 더욱 조밀해짐을 알 수 있다. 또 한 가지 주목할 점은 비록 제안하는 알고리듬이 생성된 삼 각형의 최소 각을 입력값으로 받지 않음에도 불구하고 생성된 삼각형들은 곡률이 비교적 큰 곡면에 대하여 정 삼각형에 가까워짐을 알 수 있다. 이는 뾰족한 형태의 나 쁜 삼각형들은 비교적 길이가 길기 때문에 오차가 커지 기 때문이며 딜러니 개선 과정에서 새로 생기는 꼭지점 이 삼각형의 무게 중심 부근에 위치하게 되어 새로 생기 는 삼각형의 최소각이 기존의 것보다 커지게 되기 때문 이다.

<Table 1>은 실험에서의 보로노이 영역을 구성하는 곡 면들의 허용오차를 є_b = 0.005로 설정했을 때, 초기 삼각 화와 제안하는 방법으로 새롭게 구성한 삼각화의 데이터 를 보여준다. 총 21개 곡면에 대하여 곡률의 내림차순으 로 정렬하였고, 곡률은 두 구의 반지름 차이와 중심 사이 의 거리에 의해 결정되며 식 (5)를 이용하여 계산하였다.

<Table 1>에서 초기 삼각화의 최대 오차는 곡면 번호 1에서 0.14314이며, 이는 <Figure 6(a)>의 є_b = 1보다 작다. 그러므로 이 그림은 초기 삼각화와 일치하게 된다. <Figure 6(b)>에서 허용 오차는 є_b = 0.1인데, 이를 만족하 지 못하는 곡면은 곡면 번호 1만 해당하며, 나머지 곡면은 딜러니 개선 과정을 진행할 필요가 없다. <Figure 6(b)>에 서 정면 상단의 넓은 곡면이 곡면 번호 1에 해당하며 가장 곡률이 크다. 하나의 꼭지점이 딜러니 개선 과정을 통하 여 새로이 추가되어 개선된 것을 그림으로 확인할 수 있 다. 곡면 번호 15부터 21까지의 7개 곡면은 상대적으로 작 은 곡률을 가지게 되어 초기삼각화의 최대 오차가 허용오 차보다 작게 되어 추가적인 딜러니 개선 작업이 필요하지 않다. 그리고 곡면 번호 8과 10은 상대적으로 큰 곡률을 가지고 있으나 보로노이 곡면이 되는 부분이 중심(즉, 표 준 공간에서 z축)에서 먼 곳에 위치해 있고 그 넓이가 작 아 최대 오차가 허용오차보다 작다.

6. 결 론

본 논문에서는 삼차원 구의 보로노이 다이어그램의 보로노이 곡면의 삼각화 방법을 제안하였다. 제안하는 방법은 보로노이 곡면을 표준 공간으로 변환한 후 초기 딜러니 삼각화를 구성한 후 딜러니 개선 알고리듬을 허 용오차를 만족할 때까지 반복한다. 실제 곡면과 삼각화 된 곡면 사이의 오차를 근사화하는 정의하는 새로운 방 법을 제시하여 적용하였다. 그 결과 주어진 허용오차를 만족하는 삼각화된 보로노이 곡면을 효과적으로 구할 수 있었다. 제시하는 방법론은 간단한 기초 연산인 split_segment과 split_triangle만을 이용하기 때문에 구현이 쉽고 수치적으로 안정적인 장점이 있다. 또한 제안하는 방법 은 보로노이 곡면뿐만 아니라 일반적인 자유 곡면의 삼 각화에도 적용 가능할 것으로 기대하며, 특히 하나의 평 면으로 투영 가능한 2차 곡면에 대해서는 곧바로 적용 가능할 것으로 판단한다.