EUROGRAPHICS 2002 / G. Drettakis and H.-P. Seidel(Guest Editors)Volume 21 (2002), Number 3Surface reconstruction based on a dynamical systemN.N.AbstractWe present an efficient algorithm that computes a manifold triangular mesh from a set of unorganized samplepoints in3. The algorithm builds on the observation made by several researchers that the Gabriel graph of thesample points provides a good surface description. However, this surface description is only one-dimensional. Weassociate the edges of the Gabriel graph with index 1 critical points of a dynamical system induced by the samplepoints. Exploiting also the information contained in the critical points of index 2 provides a two-dimensionalsurface description which can be easily turned into a manifold.1. IntroductionSurface reconstruction is a powerful modeling paradigm. Tocreate a model of some solid in3one can just sample itssurface and apply a surface reconstruction algorithm to thesample. Hence the task in the surface reconstruction problemis to transform a finite sample into a surface model. There areseveral obstacles a surface reconstruction algorithm mightface. The sample could very large, noisy or to sparse toocapture all the features of the solid.The different approaches to the surfaces reconstructionproblem can be divided broadly into two classes. Algorithmsin the first class provide implicit surface models while the al-gorithms in the second class provide explicit surface models.An implicit surface model is a function f :3suchthat the zero set of f , i.e. f1 0, is a surface that interpo-lates or approximates the sample. The signed distance func-tion was introduced to this respect by Hoppe et al.11. Thisfunction or smoothed variants of it are used frequently in theimplicit approach to surface reconstruction61415. For ren-dering purposes an implicit surface is likely to be tranformedinto a triangular mesh.Most of the explicit approaches to surface reocnstructioncompute a triangular mesh directly123410. Here we wantto have a closer look on two of these algorithms.The algorithm of Mencl and Müller1213consists of threesteps. In the first step the Euclidean minimum spanning treeof the sample points is computed. Then this tree is extendedto the so called surface description graph. Finally the con-tours of the surface description graph are filled with trian-gles.The Euclidean minimum spanning tree of the samplepoints is a subgraph of the Gabriel graph on the same setof points. Two sample points p and q are connected by aGabriel edge if the open ball with diameterpqthat hasp and q in its boundary does not contain any sample point.The sample points together with the Gabriel edges build theGabriel graph.The algorithm of Attene and Spagnuolo5also builds onthe observation that the Gabriel graph and the Euclideanminimum spanning tree provide a fairly good surface de-scription. It removes Delaunay tetrahedra from the three-dimensional Delaunay triangulation if they are removable.The property to be removable is defined via the Gabrielgraph of the sample points.The approach we are going to present in this paper is ex-plicit. But it also makes use of a distance function. As thesigned distance function this function is defined using theVoronoi diagram of the sample points. But in contrast tothe signed distance function we cannot use only the zeroset of the function. Instead we are going to study all of itscritical points, i.e. local minima, local maxima and saddlepoints. We provide a one-to-one correspondence between theGabriel edges and some critical points of the distance func-tion. It turns out that the Gabriel edges correspond to the in-dex 1 saddle points of this function. We further show that thesaddles of index 2 correspond to surfaces with boundaries.These boundaries consists of Gabriel edges. The collectionof all these surfaces together with the Gabriel edges is a sim-plicial complex. This complex provides a two-dimensionalsurface description though not a manifold in general. Build-ing on results of Edelsbrunner on critical points we showhow to transform the complex into a manifold.The main contributions of this paper are new insights insubmitted to EUROGRAPHICS 2002.2 N.N. / Surface reconstructiona natural distance function associated with a set of sam-ple points. These insights lead to an efficient and robust al-gorithm for surface reconstruction. We have implementedthe algorithm and evaluated its applicability. The algorithmturned out to be very robust. It is able to cope even withnoisy and/or undersampled data where other explicit algo-rithms leave unpleasant holes. Our insights should be valu-able also for other tasks in sample based modeling like sam-ple decimation or feature extraction.The paper is organized as follows. In the second sectionwe introduce a distance function and its critical points. Thedistance function is defined via a set of sample points. Thedependency on the sample points makes it suitable for ouruse in surface reconstruction. In the same section we intro-duce the notions of Voronoi diagram and Delaunay trian-gulation of a set of sample points. The third section intro-duces a dynamical system associated with the height func-tion and the sample points. This dynamical system is usedin the fourth section to define the flow complex. The flowcomplex is a simplicial complex on the sample points thatalmost provides a reconstruction of a solid if the points aresampled from the surface of this solid. In the fifth section wetransform the flow complex into the reduced flow complexby using the concepts of pairing and cancellation. The re-duced flow complex provides us with the reconstruction weare looking for. In the sixth section we report on an imple-mentation of our reconstruction algorithm and present someexperimental results.2. Distance function and critical pointsLet P be a set of unorganized points sampled from thesurface of a solid embedded in3. The distance functionh :3assigns to every point in3its least distance toany of the sample points, i.e.h xminpPxpIn contrast to the signed distance function which was studiedby11in the context of surface reconstruction we cannot useonly the zero set of h to determine the reconstruction. Thezero set of h is the set P of sample points. This is also the setof local minima of h, i.e. the points in P are critical pointsof h. We are interested in all critical points of h.