Centroidal Voronoi tessellations(CVTs) have become a useful tool in many applications ranging from geometric modeling,image and data analysis,and numerical partial differential equations,to problems in physics,astroph...Centroidal Voronoi tessellations(CVTs) have become a useful tool in many applications ranging from geometric modeling,image and data analysis,and numerical partial differential equations,to problems in physics,astrophysics,chemistry,and biology. In this paper,we briefly review the CVT concept and a few of its generalizations and well-known properties.We then present an overview of recent advances in both mathematical and computational studies and in practical applications of CVTs.Whenever possible,we point out some outstanding issues that still need investigating.展开更多
A novel construction algorithm is presented to generate a conforming Voronoi mesh for any planar straight line graph (PSLG). It is also extended to tesselate multiple-intersected PSLGs. All the algorithms are guarante...A novel construction algorithm is presented to generate a conforming Voronoi mesh for any planar straight line graph (PSLG). It is also extended to tesselate multiple-intersected PSLGs. All the algorithms are guaranteed to converge. Examples are given to illustrate its efficiency.展开更多
We present a novel algorithm for adaptive triangular mesh coarsening. The algorithm has two stages. First, the input triangular mesh is refined by iteratively applying the adaptive subdivision operator that performs a...We present a novel algorithm for adaptive triangular mesh coarsening. The algorithm has two stages. First, the input triangular mesh is refined by iteratively applying the adaptive subdivision operator that performs a so-called red-green split. Second, the refined mesh is simplified by a clustering algorithm based on centroidal Voronoi tessellations (CVTs). The accuracy and good quality of the output triangular mesh are achieved by combining adaptive subdivision and the CVTs technique. Test results showed the mesh coarsening scheme to be robust and effective. Examples are shown that validate the method.展开更多
High quality mesh plays an important role for finite element methods in science computation and numerical simulation.Whether the mesh quality is good or not,to some extent,it determines the calculation results of the ...High quality mesh plays an important role for finite element methods in science computation and numerical simulation.Whether the mesh quality is good or not,to some extent,it determines the calculation results of the accuracy and efficiency.Different from classic Lloyd iteration algorithm which is convergent slowly,a novel accelerated scheme was presented,which consists of two core parts:mesh points replacement and local edges Delaunay swapping.By using it,almost all the equilateral triangular meshes can be generated based on centroidal Voronoi tessellation(CVT).Numerical tests show that it is significantly effective with time consuming decreasing by 40%.Compared with other two types of regular mesh generation methods,CVT mesh demonstrates that higher geometric average quality increases over 0.99.展开更多
In this paper, we propose a simpleyet-effective method for isotropic meshing relying on Euclidean distance transformation based centroidal Voronoi tessellation(CVT). Our approach improves the performance and robustnes...In this paper, we propose a simpleyet-effective method for isotropic meshing relying on Euclidean distance transformation based centroidal Voronoi tessellation(CVT). Our approach improves the performance and robustness of computing CVT on curved domains while simultaneously providing highquality output meshes. While conventional extrinsic methods compute CVTs in the entire volume bounded by the input model, we restrict the computation to a 3D shell of user-controlled thickness. Taking voxels which contain surface samples as sites, we compute the exact Euclidean distance transform on the GPU. Our algorithm is parallel and memory-efficient,and can construct the shell space for resolutions up to 20483 at interactive speed. The 3D centroidal Voronoi tessellation and restricted Voronoi diagrams are also computed efficiently on the GPU. Since the shell space can bridge holes and gaps smaller than a certain tolerance, and tolerate non-manifold edges and degenerate triangles, our algorithm can handle models with such defects, which typically cause conventional remeshing methods to fail. Our method can process implicit surfaces, polyhedral surfaces, and point clouds in a unified framework. Computational results show that our GPU-based isotropic meshing algorithm produces results comparable to state-ofthe-art techniques, but is significantly faster than conventional CPU-based implementations.展开更多
基金supported by the US Department of Energy Office of Science Climate Change Prediction Program through grant numbers DE-FG02-07ER64431 and DE-FG02-07ER64432the US National Science Foundation under grant numbers DMS-0609575 and DMS-0913491
文摘Centroidal Voronoi tessellations(CVTs) have become a useful tool in many applications ranging from geometric modeling,image and data analysis,and numerical partial differential equations,to problems in physics,astrophysics,chemistry,and biology. In this paper,we briefly review the CVT concept and a few of its generalizations and well-known properties.We then present an overview of recent advances in both mathematical and computational studies and in practical applications of CVTs.Whenever possible,we point out some outstanding issues that still need investigating.
基金Supported by the Science Technology Development Program of Beijing Municipal Education Commission (KM200510011004)
文摘A novel construction algorithm is presented to generate a conforming Voronoi mesh for any planar straight line graph (PSLG). It is also extended to tesselate multiple-intersected PSLGs. All the algorithms are guaranteed to converge. Examples are given to illustrate its efficiency.
基金supported by the National Natural Science Foundation of China (No. 60773179)the National Basic Research Program (973) of China (No. 2004CB318000)
文摘We present a novel algorithm for adaptive triangular mesh coarsening. The algorithm has two stages. First, the input triangular mesh is refined by iteratively applying the adaptive subdivision operator that performs a so-called red-green split. Second, the refined mesh is simplified by a clustering algorithm based on centroidal Voronoi tessellations (CVTs). The accuracy and good quality of the output triangular mesh are achieved by combining adaptive subdivision and the CVTs technique. Test results showed the mesh coarsening scheme to be robust and effective. Examples are shown that validate the method.
基金Project(11002121) supported by the National Natural Science Foundation of ChinaProject(09QDZ09) supported by Doctor Foundation of Xiangtan University, China+2 种基金Project(2009LCSSE11) supported by Hunan Key Laboratory for CSSE, ChinaProject(2011FJ3231) supported by Planned Science and Technology Project of Hunan Province,ChinaProject(12JJ3054) supported by the Provincial Natural Science Foundation of Hunan,China
文摘High quality mesh plays an important role for finite element methods in science computation and numerical simulation.Whether the mesh quality is good or not,to some extent,it determines the calculation results of the accuracy and efficiency.Different from classic Lloyd iteration algorithm which is convergent slowly,a novel accelerated scheme was presented,which consists of two core parts:mesh points replacement and local edges Delaunay swapping.By using it,almost all the equilateral triangular meshes can be generated based on centroidal Voronoi tessellation(CVT).Numerical tests show that it is significantly effective with time consuming decreasing by 40%.Compared with other two types of regular mesh generation methods,CVT mesh demonstrates that higher geometric average quality increases over 0.99.
基金partially supported by Ac RF RG40/12MOE2013-T2-2-011+2 种基金partially supported by National Natural Science Foundation of China (Nos. 61432003 and 61322206)the TNList Cross-discipline Foundationpartially supported by HKSAR Research Grants Council (RGC) General Research Fund (GRF), CUHK/14207414
文摘In this paper, we propose a simpleyet-effective method for isotropic meshing relying on Euclidean distance transformation based centroidal Voronoi tessellation(CVT). Our approach improves the performance and robustness of computing CVT on curved domains while simultaneously providing highquality output meshes. While conventional extrinsic methods compute CVTs in the entire volume bounded by the input model, we restrict the computation to a 3D shell of user-controlled thickness. Taking voxels which contain surface samples as sites, we compute the exact Euclidean distance transform on the GPU. Our algorithm is parallel and memory-efficient,and can construct the shell space for resolutions up to 20483 at interactive speed. The 3D centroidal Voronoi tessellation and restricted Voronoi diagrams are also computed efficiently on the GPU. Since the shell space can bridge holes and gaps smaller than a certain tolerance, and tolerate non-manifold edges and degenerate triangles, our algorithm can handle models with such defects, which typically cause conventional remeshing methods to fail. Our method can process implicit surfaces, polyhedral surfaces, and point clouds in a unified framework. Computational results show that our GPU-based isotropic meshing algorithm produces results comparable to state-ofthe-art techniques, but is significantly faster than conventional CPU-based implementations.
