﻿ :: Journal of Society of Korea Industrial and Systems Engineering ::

• For Contributors +
• Journal Search +
Journal Search Engine
ISSN : 2005-0461(Print)
ISSN : 2287-7975(Online)
Journal of Society of Korea Industrial and Systems Engineering Vol.41 No.4 pp.123-130
DOI : https://doi.org/10.11627/jkise.2018.41.4.123

# Triangulation of Voronoi Faces of Sphere Voronoi Diagram using Delaunay Refinement Algorithm

Donguk Kim
Department of Industrial and Management Engineering, Gangneung-Wonju National University
Corresponding Author : donguk@gwnu.ac.kr
12/11/2018 07/12/2018 10/12/2018

## Abstract

Triangulation is one of the fundamental problems in computational geometry and computer graphics community, and it has huge application areas such as 3D printing, computer-aided engineering, surface reconstruction, surface visualization, and so on. The Delaunay refinement algorithm is a well-known method to generate quality triangular meshes when point cloud and/or constrained edges are given in two- or three-dimensional space. In this paper, we propose a simple but efficient algorithm to triangulate Voronoi surfaces of Voronoi diagram of spheres in 3-dimensional Euclidean space. The proposed algorithm is based on the Ruppert’s Delaunay refinement algorithm, and we modified the algorithm to be applied to the triangulation of Voronoi surfaces in two ways. First, a new method to deciding the location of a newly added vertex on the surface in 3-dimensional space is proposed. Second, a new efficient but effective way of estimating approximation error between Voronoi surface and triangulation. Because the proposed algorithm generates a triangular mesh for Voronoi surfaces with guaranteed quality, users can control the level of quality of the resulting triangulation that their application problems require. We have implemented and tested the proposed algorithm for random non-intersecting spheres, and the experimental result shows the proposed algorithm produces quality triangulations on Voronoi surfaces satisfying the quality criterion.

# 딜러니 개선 알고리듬을 이용한 삼차원 구의 보로노이 곡면 삼각화

김동욱
강릉원주대학교 산업경영공학과

## 초록

Gangneung-Wonju National University

## 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) si는 중심이 Pi = (xi, yi, zi )이고 반지름이 ri인 구로 정의된다. 생성자 집합 S = {si, i = 1, ⋯, n}으로 정 의한다. 보로노이 생성자 si의 보로노이 영역은 $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].

보로노이 곡면은 보로노이 영역의 경계를 이루는데, 가장 가까운 두 구 사이의 거리가 동일한 점들의 집합으 로 정의된다. 두 구 sisj사이에 보로노이 곡면이 존재 한다면, 보로노이 곡면은 $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

• 딜러니 삼각화 DT(V) 계산

• 다음을 위반하는 세그먼트가 없고, 품질조건 q를 만족 할 때까지 반복

1. 모든 위반 세그먼트에 대하여 반복적으로 split_segment

2. 품질조건 q를 만족하지 않는 삼각형 t에 대하여 t의 외접원의 중심점을 포함하는 모든 위반 세그먼트들 에 대해 split_segment

3. 위반 세그먼트가 없다면 split_triangle(t) 출력 : 현재의 삼각화

## 3. 방법

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

### 3.1 보로노이 곡면의 삼각화

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

#### 3.1.1 표준 공간(Canonical Space)

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

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

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

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

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

$‖ P − F s ‖ = ‖ P − F b ‖ − r$
(1)

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

$x 2 + y 2 + ( z − d ) 2 = x 2 + y 2 + ( z + d ) 2 − r$
(2)

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

$4 r 2 x 2 + 4 r 2 y 2 + ( 4 r 2 − 16 d 2 ) z 2 + 4 r 2 d 2 − r 4 = 0$
(3)

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

$f ( x , y ) = 1 2 r 2 ( 4 x 2 + 4 y 2 + 4 d 2 − r 2 ) − r 2 + 4 d 2$
(4)

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

$κ ( r , d ) = 2 r 4 d 2 − r 2$
(5)

#### 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>에서와 같이 삼각형의 외심을 Pc라 할 때, Pc를 통과하면서 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

[전처리]

1. 곡면 fE의 모든 모서리들을 표준 공간으로 변환

2. 변환된 E의 모서리들을 표준 공간의 xy -평면으로 사영

3. 사영된 모서리들을 주어진 길이 이상의 선분으로 분 할 후 세그먼트 리스트 S 에 추가

4. 딜러니 삼각화 DT(V)계산

5. 모든 위반 세그먼트에 대하여 반복적으로 split_segment

[반복]

1. 6. 위반 세그먼트가 없고, 모든 삼각형의 곡면 오차가 єb 보다 작아질 때까지 다음을 반복

2. 6.1 곡면오차가 єb보다 큰 삼각형 t에 대하여 새로운 꼭 지점으로 인해 위반하는 모든 세그먼트들에 대해 split_ segment

3. 6.2 위반 세그먼트가 없으면 split_triangle(t)

출력 : 현재의 DT(V

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

## 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차 곡면에 대해서는 곧바로 적용 가능할 것으로 판단한다.

## Acknowledgement

This research was supported by the Research Grant of Gangneung-Wonju National University.

## Figure

Delaunay Refinement Algorithm : (a) Input Graph Consisting of 9 Vertices and 6 Segments, and (b) Resulting Triangulation with Minimum Angle of 30°

Two Primitive Operations of Delaunay Refinement Algorithm : (a) Split_Rriangle, and (b) Split_Segment

Voronoi Face Transformed to the Canonical Space

Approximation Error of a Triangle t to a Voronoi Surface f

The Sphere Set Used in the Experiment. 1,000 Non-Intersecting Random Spheres are Contained in a Big Spherical Container of Radius 27.65. Each Sphere’s Radius is Uniformly Distributed in the Range of [1, 2], and the Packing Density in the container is 0.178 Approximately. (a) 1,000 Random Spheres in a Container, and (b) One Voronoi Region with the Spheres

Voronoi Region with Respect to the Error Bounds

## Table

Statistics of Voronoi Faces of a Voronoi Region after Refinement with Error Bound of 0.005. The Voronoi Region is shown in <Figure 6>

## Reference

1. Chew, L.P., Guaranteed-Quality Mesh Generation for Curved Surfaces, Proceedings of the 9th Annual Symposium on Computational Geometry, 1993, pp. 274-280.
2. Chew, L.P., Guaranteed-Quality Triangular Meshes, Technical Report TR-89-983, Cornell University, 1989.
3. de Berg, M., van Kreveld, M., Overmars, M., and Schwarzkopf, O., Computational Geometry : Algorithms and Applications. Springer, Berlin, 2nd edition, 2000.
4. Kim, C.-M., Won, C.-I., Cho, Y., Kim, D., Lee, S., Bhak, J., and Kim, D.-S., Interaction Interfaces in Proteins via the Voronoi Diagram of Atoms, Computer- Aided Design, 2006, Vol. 38, No. 11, pp. 1192-1204.
5. Kim, D. and Kim, D.-S., Region-Expansion for the Voronoi Diagram of 3D Spheres, Computer-Aided Design, 2006, Vol. 38, No. 5, pp. 417-430.
6. Kim, D., Acceleration of Delaunay Refinement Algorithm by Geometric Hashing, Korean Journal of Computational Design and Engineering, 2017, Vol. 22, No. 2, pp. 110 117.
7. Kim, D., Using Voronoi Diagram and Power Diagram in Application Problems, Journal of Society of Korea Industrial and Systems Engineering, 2012, Vol. 35, No. 4, pp. 235-243.
8. Kim, D.-S., Cho, Y., and Kim, D., Euclidean Voronoi Diagram of 3D Balls and Its Computation via Tracing Edges, Computer-Aided Design, 2005, Vol. 37, No. 13, pp. 1412-1424.
9. Kim, D.-S., Kim, D., and Sugihara, K., Voronoi Diagram of a Circle Set from Voronoi Diagram of a Point Set : II. Geometry, Computer Aided Geometric Design, 2001, Vol. 18, pp. 563-585.