carrier image

Well-centered Planar Triangulation-An Iterative Approach

VanderZee, Evan, Anil N. Hirani, Damrong Guoy, and Edgar Ramos

Proceedings, 16th International Meshing Roundtable, Springer-Verlag, pp.121-138, October 14-17 2007


16th International Meshing Roundtable
Seattle, Washington, U.S.A.
October 14-17, 2007, Department of Mathematics, Department of Computer Science, Center for Simulation of Advanced Rockets, Department of Computer Science
University of Illinois at Urbana-Champaign

We present an iterative algorithm to transform a given planar triangle mesh into a well-centered one by moving the interior vertices while keeping the connectivity fixed. A well-centered planar triangulation is one in which all angles are acute. Our approach is based on minimizing a certain energy that we propose. Well-centered meshes have the advantage of having nice orthogonal dual meshes (the dual Voronoi diagram). This may be useful in scientific computing, for example, in discrete exterior calculus, in covolume method, and in space-time meshing. For some connectivities with no well-centered configurations, we present preprocessing steps that increase the possibility of finding a well-centered configuration. We show the results of applying our energy minimization approach to small and large meshes, with and without holes and gradations. Results are generally good, but in certain cases the method might result in inverted elements.

Download Full Paper (PDF Format)

Contact author(s) or publisher for availability and copyright information on above referenced article