Fast Updating of Delaunay Triangulation of Moving Points by Bi-cell Filtering
No Thumbnail Available
Date
2010
Journal Title
Journal ISSN
Volume Title
Publisher
The Eurographics Association and Blackwell Publishing Ltd
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.
Description
@article{10.1111:j.1467-8659.2010.01812.x,
journal = {Computer Graphics Forum},
title = {{Fast Updating of Delaunay Triangulation of Moving Points by Bi-cell Filtering}},
author = {Zhou, Yuanfeng and Sun, Feng and Wang, Wenping and Wang, Jiaye and Zhang, Caiming},
year = {2010},
publisher = {The Eurographics Association and Blackwell Publishing Ltd},
ISSN = {1467-8659},
DOI = {10.1111/j.1467-8659.2010.01812.x}
}