Quad-Subdivision을 이용한 Delaunay 삼각화 알고리즘 개발

박시형,이성수 한국공작기계학회 2000 한국공작기계학회 추계학술대회논문집 Vol.2000 No.-

Delaunay triangulation is well balanced in the sense that the triangles tend toward equiangularity. And so, Delaunay triangulation hasn't some slivers triangle. It's commonly used in various field of CAD applications, such as shape reconstruction, solid modeling and volume rendering. In this paper, an improved Delaunay triangulation is proposed in 2-dimensions. The suggested algorithm subdivides a uniform grids into sub-quad grids, and so efficient where points are non-uniform distribution. To get the mate from quad-subdivision algorithm, the area where triangulation-patch will be most likely created should be searched first.

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

Donguk Kim 한국산업경영시스템학회 2018 한국산업경영시스템학회지 Vol.41 No.4

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.

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

김동욱 한국산업경영시스템학회 2018 한국산업경영시스템학회지 Vol.41 No.4

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.

기하학적 해싱을 이용한 딜러니 개선 알고리듬의 가속화

김동욱(Donguk Kim) (사)한국CDE학회 2017 한국CDE학회 논문집 Vol.22 No.2

Delaunay refinement algorithm is a classical method to generate quality triangular meshes when point cloud and/or constrained edges are given in two- or three-dimensional space. It computes the Delaunay triangulation for given points and edges to obtain an initial solution, and update the triangulation by inserting steiner points one by one to get an improved quality triangulation. This process repeats until it satisfies given quality criteria. The efficiency of the algorithm depends on the criteria and point insertion method. In this paper, we propose a method to accelerate the Delaunay refinement algorithm by applying geometric hashing technique called bucketing when inserting a new steiner point so that it can localize necessary computation. We have tested the proposed method with a few types of data sets, and the experimental result shows strong linear time behavior.

병렬 프로그래밍을 위한 지역적 삼각형 메쉬 생성 알고리즘

감동욱(Dong-Uk Kam),이건우(Kunwoo Lee) (사)한국CDE학회 2014 한국 CAD/CAM 학회 학술발표회 논문집 Vol.2014 No.8

In this paper, we propose a method for computing localized 2-dimensional Delaunay triangulation. To do so, we first get a polygon from a given vertex by points search method, namely, this polygon bounds a given vertex. Then, we consider voronoi condition at each edge of a polygon. If an edge doesn’t guarantee voronoi condition, we reconstructed polygon by adding a points inside of the voronoi circumcircle. After all, each edge of a polygon guarantees voronoi condition, and we just get mesh information from this polygon. We computed this process for all of given vertices. When we have a unique voronoi circumcircle, which has more than three vertices in circumcircle boundary, we just take special vertex for each case. This algorithm can be implemented to more efficient parallel meshing process.

Constrained Delaunay Triangulation을 적용한 3차원 균열 모델링 알고리즘 개발

김연희(Yeounhee Kim),김평화(Pyunghwa Kim),박정선(Jungsun Park) 항공우주시스템공학회 2023 항공우주시스템공학회 학술대회 발표집 Vol.2023 No.05

Two-Dimensional Boundary Recovery Procedure for Non-Manifold and Intersecting Boundaries

Chaoyan Zhu,Zhoufang Xiao,Lijuang Zeng 보안공학연구지원센터 2015 International Journal of Multimedia and Ubiquitous Vol.10 No.8

To ensure all boundary edges of each region are retained in the final mesh during mesh generation, a procedure suitable for non-manifold with intersecting boundaries is proposed to recover the non-manifold and intersecting boundaries. In the procedure, Steiner points are inserted directly on the interFigure of missing boundaries and mesh edges from a triangulation. Based on the boundary recovery procedure, Delaunay triangulation algorithms for the domain with interior constraints and for the non-manifold are proposed, and the latter can be used as a new effective polygon Boolean operations algorithm.

Method for automatically generating a two-dimensional triangular mesh of a bone from a CT image considering its density heterogeneity

Byung Chul Kim,Junho Lee,Ki Youn Kwon 대한기계학회 2020 JOURNAL OF MECHANICAL SCIENCE AND TECHNOLOGY Vol.34 No.7

To perform numerical analyses, such as bio-mechanical analyses, on bones, it is necessary to construct the mesh model of the shape of the bone. In previous studies, the mesh has been generated by assuming that bones are homogeneous in terms of material distribution. However, bones are inherently heterogeneous. Therefore, the mesh has to be generated by considering the variation of the properties of bones. In this study, we propose a method for automatically generating a bone mesh by considering its heterogeneity. However, only twodimensional triangular meshes are considered. In the proposed method, the boundary polylines of a bone are extracted from its computed tomography (CT) image using the marching squares method. Nodes are randomly generated on and inside the boundary polylines, and triangles are generated from the nodes by Delaunay triangulation. When the nodes are generated on and inside the boundary polylines, the density of the nodes is controlled by threshold functions defined by the magnitude of the gradient vector of the Hounsfield unit values of the CT image. The proposed method was implemented using C++ and visualization toolkit, and experiments were performed using CT images on the right femur, hip bones, and vertebra. We also verified that the proposed method can generate meshes reflecting the variation of the properties of bones.

A Divide-and-conquer Delaunay Triangulation Algorithm with a Vertex Array and Flip Operations in Two-dimensional Space

양상욱,최영,정창교 한국정밀공학회 2011 International Journal of Precision Engineering and Vol. No.

Divide-and-conquer algorithms provide computational efficiency for constructing Delaunay triangulations; however, their implementation is complicated. Most divide-and-conquer algorithms for Delaunay triangulation utilize edge-based structures, because triangles are frequently deleted and created during the merge process. However, as our proposed divide-and-conquer algorithm does not require existing edges to be deleted in the merge process, a simple array-based data structure can be used for the representation of the triangulation topology. Rather than deleting the edges of the conflicting triangles, which was used in previous methods, the Delaunay property is also preserved with a new flip propagation method in the merge phase. This array-based data structure is much simpler than the commonly used edge-based data structures and requires less memory allocation. The proposed algorithm arranges sites into a permutation vector that represents a kdtree with an array; thus, the space partitioning information is internally represented in the array without any additional data. Since the proposed divide-and-conquer algorithm is compact, the implementation complexity of conventional divideand-conquer triangulation algorithms can be avoided. Despite of the simplicity of this new algorithm, the experimental results indicate that the computational efficiency is comparable to the previous divide-and-conquer algorithms.

Adaptive finite elements by Delaunay triangulation for fracture analysis of cracks

Dechaumphai, Pramote,Phongthanapanich, Sutthisak,Bhandhubanyong, Paritud Techno-Press 2003 Structural Engineering and Mechanics, An Int'l Jou Vol.15 No.5

Delaunay triangulation is combined with an adaptive finite element method for analysis of two-dimensional crack propagation problems. The content includes detailed descriptions of the proposed procedure which consists of the Delaunay triangulation algorithm and an adaptive remeshing technique. The adaptive remeshing technique generates small elements around the crack tips and large elements in the other regions. Three examples for predicting the stress intensity factors of a center cracked plate, a compact tension specimen, a single edge cracked plate under mixed-mode loading, and an example for simulating crack growth behavior in a single edge cracked plate with holes, are used to evaluate the effectiveness of the procedure. These examples demonstrate that the proposed procedure can improve solution accuracy as well as reduce total number of unknowns and computational time.