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.

본 연구에서는 무요소법의 일종인 element-free Galerkin 방법(EFGM)을 이용한 새로운 적응적 해석법을 제안하였다. 이 방법의 핵심은 Delaunay 삼각화에 기초를 둔 적분 격자를 기초로 수치적분과 적응적인 절점의 추가 및 소거를 수행하는 것이다. 이러한 적응적 해석법은 적분격자의 분할이나 이를 위한 추가적인 정보에 대한 관리가 필요 없이 간편하게 적응적 해석을 수행할 수 있다. 또한 균열의 진전과 같은 다단계 적응적 해석에 있어서도 매 해석단계별로 평가된 오차에 기초를 둔 최적 해석모델이 Delaunay 삼각화에 의해 구성되도록 하였다. 이러한 특성은 요소의 구성으로부터 자유로운 무요소법의 장점을 최대한 활용하여 해석모델의 구축을 보다 원활하게 수행할 수 있다. 적응적 해석에 기초가 되는 해석 후 오차평가는 계산된 응력과 투영응력과의 차이를 오차로 추정하는 투영응력법을 이용하였다. 균열진전을 포함하는 2차원예제의 해석을 수행한 결과 제안된 해석법의 타당성과 적용성을 입증할 수 있었다.

본 연구에서는 기존의 곡면 삼각화 방법들이 많은 수의 삼각형 메쉬를 사용하면서도 정확하게 표현하기가 힘들었던, 날카로운 모서리를 가지는 곡면을 처리할 수 있는 trammed NURBS곡면 삼각화 방법을 제안, 구현하였다. 기존의 매개변수영역에서의 삼각화의 문제점인 3차원공간상의 삼각형 메쉬를 계산할 때의 왜곡현상을 해결하기 위해서 곡면의 펼친영역을 근사적으로 계산하여 삼각화 하는 방법을 사용했다. 곡선, 곡면의 날카로운 점과 모서리를 자동으로 인식하기 위해서 1차미분 연속조건을 이용하였고, 이를 제약조건으로 constraint Delaunay 삼각화방법을 사용하여 곡면의 날카로운 형상(sharp shape)을 유지하면서 삼각화를 수행할 수 있었다. 제안된 삼각화 방법은 기존의 삼각화 방법에 비하여 적은수의 삼각형 메쉬로 곡면의 날카로운 모서리를 보다 정확하게 표현 할 수 있는 장점을 가지고 있어서 삼각형의 개수에 따라 가시화 성능이 큰 영향을 받는 컴퓨터게임 같은 분야에 도움을 줄 수 있으리라 예상된다.