Multiresolution hierarchies on unstructured triangle meshes

The use of polygonal meshes for the representation of highly complex geomet ric objects has become the de facto standard in most computer graphics appl ications. Especially triangle: meshes are preferred due to their algorithmi c simplicity, numerical robustness, and efficient display. The possibility to decompose a given triangle mesh into a hierarchy of differently detailed approximations enables sophisticated modeling operations like the modifica tion of the,global shape under preservation of the detail features, so far, multiresolution hierarchies have been proposed mainly for meshes with subd ivision connectivity. This type of connectivity results from iteratively ap plying a uniform split operator to an initially given coarse base, mesh. In this paper we demonstrate how a similar hierarchical structure can be deri ved for arbitrary meshes with no restrictions on the connectivity. Since sm ooth (subdivision) basis functions are no longer available in this generali zed context, we use constrained energy minimization to associate smooth geo metry with coarse levels of detail. As the energy minimization requires one to solve a global sparse system, we investigate the effect of various para meters and boundary conditions in order to optimize the performance of iter ative solving algorithms. Another crucial ingredient for an effective multi resolution decomposition of unstructured meshes is the flexible representat ion of detail information, We discuss several approaches. (C) 1999 Elsevier Science B.V. All rights reserved.