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

• 영문명: Triangulation of Voronoi Faces of Sphere Voronoi Diagram using Delaunay Refinement Algorithm
• 발행기관: 한국산업경영시스템학회
• 저자명: 김동욱(Donguk Kim)
• 간행물 정보: 『산업경영시스템학회지』제41권 제4호, 123~130쪽, 전체 8쪽
• 주제분류: 경제경영 > 경영학
• 파일형태: PDF
• 발행일자: 2018.12.30

영문 초록

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.

목차

1. 서 론

2. 배경 이론

3. 방법

4. 구현 및 실험

5. 실험 결과 및 고찰

6. 결 론

키워드

Voronoi Diagram Voronoi Face Delaunay Refinement Algorithm Triangulation