Fast Updating of Delaunay Triangulation of Moving Points by Bi‐cell Filtering |
| |
Authors: | Yuanfeng Zhou Feng Sun Wenping Wang Jiaye Wang Caiming Zhang |
| |
Affiliation: | 1. Department of Computer Science, The University of Hong Kong, Hong Kong, China;2. School of Computer Science and Technology, Shandong University, Jinan, China |
| |
Abstract: | Updating a Delaunay triangulation when data points are slightly moved is the bottleneck of computation time in variational methods for mesh generation and remeshing. Utilizing the connectivity coherence between two consecutive Delaunay triangulations for computation speedup is the key to solving this problem. Our contribution is an effective filtering technique that confirms most bi‐cells whose Delaunay connectivities remain unchanged after the points are perturbed. Based on bi‐cell flipping, we present an efficient algorithm for updating two‐dimensional and three‐dimensional Delaunay triangulations of dynamic point sets. Experimental results show that our algorithm outperforms previous methods. |
| |
Keywords: | I 3 5 [Computer Graphics]: Computational Geometry and Object Modeling— Geometric algorithms languages and systems |
|