A unified framework for isotropic meshing based on narrow-band Euclidean distance transformation

In this paper, we propose a simple-yet-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 high-quality...

Full description

Saved in:
Bibliographic Details
Published in:Computational visual media (Beijing) 2015-09, Vol.1 (3), p.239-251
Main Authors: Leung, Yuen-Shan, Wang, Xiaoning, He, Ying, Liu, Yong-Jin, Wang, Charlie C. L.
Format: Article
Language:English
Subjects:
Algorithms
Artificial Intelligence
Computer Graphics
Computer Science
Euclidean geometry
Image Processing and Computer Vision
Meshing
Performance enhancement
Research Article
Tessellation
Three dimensional models
User Interfaces and Human Computer Interaction
Voronoi graphs
Citations: Items that this one cites
Items that cite this one
Online Access:Get full text
Tags: Add Tag
No Tags, Be the first to tag this record!
Description
Summary:In this paper, we propose a simple-yet-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 high-quality 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 2048 3 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-of- the-art techniques, but is significantly faster than conventional CPU-based implementations.
ISSN:2096-0433
2096-0662
DOI:10.1007/s41095-015-0022-4