Optimising 3D triangulations: Improving the initial triangulation for the butterfly subdivision scheme

This work is concerned with the construction of a "good" 3D triangulation of a given set of points in 3D, to serve as an initial triangulation for the generation of a well shaped surface by the butterfly scheme. The optimisation method is applied to manifold meshes, and conserves the topology of the triangulations. The constructed triangulation is "optimal" in the sense that it locally minimises a cost function. The algorithm for obtaining a locally-optimal triangulation is an extension of Lawson's Local Optimisation Procedure (LOP) algorithm to 3D, combined with a priority queue. The first cost function designed in this work measures an approximation of the discrete curvature of the surface generated by the butterfly scheme, based on the normals to this surface at the given 3D vertices. These normals can be expressed explicitly in terms of the vertices and the connectivity between them in the initial mesh. The second cost function measures the deviations of given normals at the given vertices from averages of normals to the surface generated by the butterfly scheme in neighbourhoods of the corresponding vertices. It is observed from numerical simulations that our optimisation procedure leads to good results for vertices sampled from analytic objects. The first cost function is appropriate for analytic surfaces with a large proportion of convex vertices. Furthermore, the optimisation with this cost function improves convex regions in non-convex complex models. The results of optimisation with respect to the second cost function are satisfactory even when all the vertices are non-convex, but this requires additional initial information which is obtainable easily only from analytic surfaces.