딜러니 개선 알고리듬을 이용한 삼차원 구의 보로노이 곡면 삼각화
Triangulation of Voronoi Faces of Sphere Voronoi Diagram using Delaunay Refinement Algorithm
0
조회
0
다운로드
0
인용
0
참고문헌
키워드
초록
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.
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.
참고문헌 (15)
- Chew, L.P., "Guaranteed-Quality Mesh Generation for Curved Surfaces", Proceedings of the 9th Annual Symposium on Computational Geometry, pp.274~280 (1993)
- Guaranteed-Quality Triangular Meshes, "Chew, L. P.", Cornell University, ~, pp.Technical Report TR-89-983 (1989)
- de Berg, M., "Computational Geometry : Algorithms and Applications" (2000), Springer
- Kim, C. -M., "Interaction Interfaces in Proteins via the Voronoi Diagram of Atoms", Computer-Aided Design, 38(11), pp.1192~1204 (2006)
- Kim, D., "Region-Expansion for the Voronoi Diagram of 3D Spheres", Computer-Aided Design, 38(5), pp.417~430 (2006)
- 김동욱, "기하학적 해싱을 이용한 딜러니 개선 알고리듬의 가속화", 한국CDE학회 논문집, 22(2), pp.110~117 (2017), 한국CDE학회[DOI]
- 김동욱, "응용문제에서 보로노이 다이어그램과 파워 다이어그램의 사용성 비교", 한국산업경영시스템학회지, 35(4), pp.235~243 (2012), 한국산업경영시스템학회[DOI]
- Kim, D. -S., "Euclidean Voronoi Diagram of 3D Balls and Its Computation via Tracing Edges", Computer-Aided Design, 37(13), pp.1412~1424 (2005)
- Kim, D. -S., "Voronoi Diagram of a Circle Set from Voronoi Diagram of a Point Set : II. Geometry", Computer Aided Geometric Design, 18, pp.563~585 (2001)
- CAM, "Principles of CAD", pp.Addison-Wesley, CAE Systems
- Okabe, A., "Spatial Tessellations : Concepts and Applications of Voronoi Diagrams" (2000), John Wiley & Sons
- Ruppert, J., "A Delaunay Refinement Algorithm for Quality 2-Dimensional Mesh Generation", Journal of Algorithms, 18(3), pp.548~585 (1995)
- Shewchuk, J. R., "Delaunay Refinement Algorithms for Triangular Mesh Generation", Computational Geometry-Theory and Applications, 22, pp.21~74 (2002)
- Shewchuk, J. R., "Lecture Notes on Delaunay Mesh Generation", pp.2012
- Will, H. -M., "Computation of Additively Weighted Voronoi Cells for Applications in Molecular Biology", Ph.D., pp.1999