>>2006,LI Fengchun,3DTIN Surface Reconstruction Algorithms & Application in Geosciences Modeling

---

Abstract

Three dimensional(3D) surface modeling is an essential task in the establishment of virtual geographic environments(VGE) for planning, management, and various applications. With the development of three dimensional spatial data collection techniques(Light Detecting And Ranging, aerial photogrammetry, surveying, GPS and geophysical prospecting method), the needs for a fast and efficient method of surface reconstruction are rapidly increasing. How to fast and accurately construct surface model from unorganized points has always been concerned by the researchers from the fields of computer vision, computer graphics and geosciences. As a basic model for representing three dimensional objects, triangulated irregular network (TIN) has been well known for geosciences simulation. The difficulties with this “2.5D” model are also well known, in particular the fact that the distribution of the triangular mesh is defined in the 2D plane and the Z-value of the surface points is not taken into account by the Delaunay empty circle criterion at all. This limitation results in the inability to reconstruct building, cliffs, faults, caves or hole, which are required to represent complex 3D surface models. There is no a universal approach of 3D TIN generation so far. Though exsisting algorithms for 3D TIN generation work nicely on dense and smooth data sets, they face the difficulties of low algorithm reliability and efficiency currently. If the data contain unsampling, sharp edges and areas with high curvature, in most cases these algorithms produce holes or overlap-patches in the vicinity of the poor regions. Based on the analysis of wide variety of 3D TIN generation methods, the research of this thesis is focused on following aspects: characteristics of data source, intrinsic properties of the unorganized points, the framework and strategy of surface reconstruction for geographic environments, 3D Delaunay triangulation, constrained boundary recovery for 3D Delaunay triangulations, surface extraction with arbitrary topology under the guide of intrinsic property of the data source and constrained information. The main work of this thesis can summarized as follows:

• The establishment of characteristic discription model and surface extraction strategy. This part first summarizes the existing methods of surface reconstruction, complexity representation and reconstruction strategy. The characteristic description and reconstruction strategy play vital role in complex environments simulation from multiple data sources. The reasoning of surface topology is far from enough only with spatial adjacency relationship. Both spatial adjacency relationship and enfored constrained conditions are necessary for accurate surface reconstruction absolutely. So, the characteristic discription model and the framework of geosciences surface modeling are given based on the analysis of characteristics of data sources.

• A true three-dimensional TIN modeling algorithm for constrained lines is investigated in this dissertation. For the purpose of surface reconstruction from serial constrained lines, the spatial distribution characteristics of complicated constrained lines are analyzed, and an efficient algorithm is proposed for true three-dimensional TIN modeling concerned with the reference plane. Starting with a seed edge, the new point of triangle is selected based on the local flatness of surface and minimum-weight triangulation. Not only the shape of triangle patch but also the spatial relationship between triangle and neighbor points are considered in the triangulation criterion. This method guarantees to produce non self-intersect surface and the reconstructed surfaces are then close to the actual surface.

• A region-growing algorithm concerned constrained conditions for surface reconstruction from 3D irregular points is investigated in this dissertation. Firstly, a novel method is designed for neighboring triangle location. The method take the full advantage of surface normals and local umbrella conditions to extract a preliminary set of candidate triangles. Since the local geometric and topological property can be clearly described with its neighboring triangles for a arbitrary edge, the method can efficiently locate a valid triangle for current edge. Secondly, a method for local geometric integrity test is discussed to ensure topological correct reconstruction at postprocessing step. The algorithm can automatically detect, locate the boundary of the holes and repair the surface to fill up the holes. Thus, the reconstructed surface has only small topological difference from the surface of the original object. Our algorithm shows efficency and robustness compared with Points2Polys software. Ours output water-tight surface TIN removing the overlapped triangles and holes. The improved growing algorithm can serve as a basis for many applications including virtual geographic environments, computer vision, and reverse engineering.

• On the base of theoretical studies, an experimental system are conducted to verify the methods we presented and to test the reliability and efficiency of algorithms. The results of our experiments are illustrated with different data sets. According to the results of experiments, the practicability and validity are validated. Currently, some successful applications are made in the field of earth physics exploration.

 

Key Words

Three-dimensional Surface Reconstruction, Three-dimensional Triangulated Irreguar Network, Three-dimensional Delaunay Triangulation, Geosciences Modeling，Three-dimensional Geographic Information System(3D GIS)