Fast Updating of Delaunay Triangulation of Moving Points by Bi-cell Filtering

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.