>> 李逢春，2006，三维TIN表面重建算法及其在地学模拟中的应用
摘 要
随着三维空间数据获取技术的发展，特别是数字摄影测量、高分辨率遥感、激光扫描系统（Laser Range Scanner）以及地球物理探测技术的发展，包含被测目标更多细节的大范围数字地表模型和局部区域空间特征的数据获取成为可能，日益增长的三维应用对快速准确地建立大规模三维表面模型提出了越来越高的要求。作为联系前端空间数据获取和后端分析应用的桥梁，三维TIN建模方法是地球信息科学领域研究的重要内容，同时这个问题也是计算机视觉、计算机图形图象领域研究的热点和难点。从离散点群中恢复三维结构包含着内在复杂机理并且还远远没有得到很好的解决。与计算机图形学领域所面临问题不同的是，首先，地球信息科学领域不但关注微观的几何对象重建，而且更关注于宏观的地形景观模型与地下工程。其次，地球信息科学领域所面临的问题更加复杂。除了千变万化的不规则地貌如陡坎，悬崖，还有各种复杂人工地物。再次，限于大规模数据获取方式，地球信息科学领域数据获取的条件相对较差。所有这些情况表明，基于离散点群的三维表面重构在地学领域所面临的问题更加严峻。
针对以上问题，本文的研究主要集中在以下三个方面：现有的数据获取方式、数据源内在机理的认识及地学目标真三维表面模拟的策略和方法；离散点集的三维Delaunay剖分，约束特征的恢复方法；在点集内在性质和辅助约束信息引导下的任意拓扑表面重建方法。本文力图将计算几何、计算机图形图像领域中最新的三维重建理论方法引入到地学目标的真三维重建框架之中，同时尽可能充分发掘地学多源数据的内在性质，在此基础之上提出并实现了一些新的思路和算法。论文的主要贡献和创新点如下：
-
提出了一种顾及局部平展特性的空间邻接约束线的真三维TIN生成算法。针对邻接约束线的空间分布特征，算法在递增生成表面过程中，利用了加权最小三角化方法，同步建立动态参考基准面，将三角面片自身形态和局部邻接约束线的相对空间关系有机的结合起来，从而避免了面片的遮掩重叠和自相交，较好的解决了复杂邻接约束线的对应匹配问题。实验结果表明，该算法重建出来的三维表面细部清楚，过渡更光滑、自然、更接近实际的表面形态。
-
提出一种顾及约束条件的三维点集表面重建的区域生长方法。该方法充分挖掘了数据源离散点集的内在性质，在表面法向信息、局域拓扑伞形特征以及强制约束条件的引导下，采用由粗到精“局部－全局－局部”的提取策略，减少了候选表面三角形的数量，降低了三角形扩张过程中因为拓扑不确定性所带来的定位难度，从而显著提高表面重构的整体效率和可靠性。实验结果表明，该方法解决了传统算法的重叠面片和表面空洞等问题，不但可以重构具有任意拓扑的复杂目标，而且重构的三角网格表面与重建目标的拓扑差别最小。
-
将本文成果应用于生产实践。针对目前真三维快速重建的应用需求，作者根据本文提出的基本思路和算法，开发了原型系统来实现真三维数字表面建模功能。经过对各种类型实际数据的处理，证明了本文相关算法不仅在理论上是正确的，而且在实践上也是可行的。目前，本文部分成果已经成功应用到了地球物理勘探领域。
关键词：
三维表面重建，三维TIN，三维Delaunay剖分，地学模拟，三维地理信息系统
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)
黄铎