Optimizing 3D triangulations using discrete curvature analysis

Nira Dyn, Kai Hormann, Sun-Jeong Kim, David Levin

2001 · 140 citations · 9 references

Concepts

Abstract

Abstract. A tool for constructing a “good ” 3D triangulation of a given set of vertices in 3D is developed and studied. The constructed triangulation is “optimal ” in the sense that it locally minimizes a cost function which measures a certain discrete curvature over the resulting triangle mesh. The algorithm for obtaining the optimal triangulation is that of swapping edges sequentially, such that the cost function is reduced maximally by each swap. In this paper three easy-to-compute cost func-tions are derived using a simple model for defining discrete curvatures of triangle meshes. The results obtained by the different cost functions are compared. Operating on data sampled from simple 3D models, we com-pare the approximation error of the resulting optimal triangle meshes to the sampled model in various norms. The conclusion is that all three cost functions lead to similar results, and none of them can be said to be supe-rior to the others. The triangle meshes generated by our algorithm, when serving as initial triangle meshes for the butterfly subdivision scheme, are

References

9