Institute for Data Analysis and Visualization

We present a highly efficient, automatice method for the generation of hierarhical surface triangulations. Given a set of scattered points in three-dimensional space, without connectivity information, our method reconstructs a valid triagulated surface model in a two-step prodcedure. First, we apply clustering to the set of given points and identify point subsets in locally nearlly planar regions. Second, we construct a surface triangulation from the output of the clustering step. The output of the clustering step is a set of of 2-manifold tiles, which locally approximate the underlying, unknown surface. We construct the triangulation of the entire surface by triangulating the individual tiles and triangulating the ''gaps'' between the tiles. Since we apply point clustering in a hierarchical fashion we can gereate model hierarchies by triangulating various levels resulting from the hierarchical clusting step.