基于OpenGL生成TI N的程序研究

■闵盛彪 寇攀

（四川省林业科学研究院 四川 成都610081）

基于OpenGL生成TI N的程序研究

■闵盛彪 寇攀

（四川省林业科学研究院 四川 成都610081）

TIN可以用来实现复杂物体表面的逼近以及地形起伏变化的模拟，在三维可视化和地理信息系统中得到了广泛的应用。本文主要介绍了TIN、TIN的生成算法以及离散点凸包的生成，同时以VC++6.0为平台，调用OpenGL库函数实现了TIN网的绘制和TIN形成区域的绘制，最后通过导入不同的实验数据以验证本文所述方法的可行性。

TIN；凸包；VC++6.0；OpenGL；地形模拟

0 引言

在现实世界里，地球表面呈现出的是一种不规则连续变化的曲面，为此我们在对地球表面进行模拟时，只能利用一系列的微小曲面，通过逼近的方法来实现仿真显示。利用数字高程模型（DEM）对地球表面地形做数字描述和模拟可以很好的解决从现实物体到计算机的模数转化，因此在测绘工程，三维可视化，虚拟现实等领域中得到了广泛的应用。DEM有三种主要的表示模型：规则格网模型，等高线模型和不规则三角网。规则网格模型GRID，只适用于地形平坦的地方，存在大量的数据冗余，且在不改变网格大小的情况下很难表达复杂多变的地物。而不规则三角网TIN在减少数据冗余的同时能够根据地形起伏变化来改变采样点的密度和位置，使得表面建模更为方便灵活。利用TIN不但便于空间分析中的计算，而且还能按地形特征点如山脊，山谷线，地形变化线等来表示数字高程等特征，与GRID相比，更能表现地形细节[1]。

VC是一门功能强大易于理解和掌握的计算及编程语言，而OpenGL是一个定义了跨语言、跨平台的编程接口的规格，是一个专业的图形程序接口，其多功能且便于调用的底层图形库是整个技术的主要支撑。本文主要介绍的就是利用三角网生成算法生成TIN并调用OpenGL库函数在VC6.0环境下的实现绘制的过程。

1 TIN生成算法及其特点

1.1 Delaunay三角网法则

一个任意的三角剖分并非是理想的三角剖分，利用随机分布的离散高程采样点建立连续覆盖整个区域的TIN的技术关键就是确定哪三个点可以构成一个最佳三角形，并使得每个离散采样点均为三角形的顶点。通常构建的三角网并没有考虑到地性线（山脊线、山谷线）的框架作用，而一些地区存在大面积水域等内部不需要构网的区域，因此要对三角网的构建进行约束。Delaunay三角形具有良好的特性，利用它可以在垂直投影的地面点中根据实际情况构造最佳三角形，该方法应当满足如下的法则：Delaunay三角网为相互邻接且互不重叠的三角形的集合，每一个三角形的外接圆内不包含其他点。Delaunay三角网由对应Voronoi多边形的点连接而成。Delaunay三角形有三个相邻点连接而成，这三个相邻顶点对应的Voronoi多边形有一个公共的顶点，此顶点是Delaunay三角形外接圆的圆心。

根据Delaunay三角网的实现过程的不同，可以分为逐点插入法、分治算法、凸包算法、三角网生长算法等。本文主要讨论了三角网生长算法，并用该算法实现TIN的绘制。

1.2 三角网生长算法

三角网生长算法的基本思路是：首先找出离散点集中相距最短的两点，连线成为TIN的初始基线；然后按D-TIN的判断方法找出包含此基线的Delaunay三角形的第三个端点，该端点应该位于基线的右侧；连接新点与原来的两点形成两条新边；再按D-TIN的判断方法找出包含此两边的另外两个Delaunay三角形的第3端点；依此循环处理所有的新生成的边，直到所有的离散点均为D-TIN的端点。例如在离散数据中任意选择一点A作为第一个三角形的第一个端点，然后寻找距离其最近的一点B作为第二个顶点，对AB附近的点C计算其余弦值，如果最小则C为第三个顶点。寻找C点关于AB异侧的点，在所有的备选点中，按照角度最大原则选择一点D作为AB边上新生成三角形的第三个顶点。同理对所有的三角形进行扩展，直到所有的点被添入到不规则三角网中。

2 离散点的凸包生成

2.1 最小二维凸包

最小凸包计算在地理信息系统中有着广泛的应用，如进行区域裁剪，获得数字地面模型等空间分析模型的有效计算区域等。在本次程序设计中，生成离散点的凸包主要是为了绘制出TIN的区域边界。在给定平面上的一个点集中找出一个最小点集顺次连结形成一个凸多边形，使得点集中的点皆在此多边形内或此多边形上，这个凸多边形就是给定点集的最小二维凸包。

2.2 卷包裹算法

经过长期的研究，计算机科学家们推出了一系列的凸包生成算法，比较著名的有Graham扫描算法、快速凸包算法以及卷包裹算法等。在此我们探究通过卷包裹算法，来实现最小二维凸包的寻找。

卷包裹算法是凸包问题的最直观的一种解法，它是Chand和Kapur于1970年提出的，其基本思想如下：首先过y坐标最小的点p1，画一水平直线AB，显然该点是凸包的一个顶点。然后AB绕p1按逆时针方向旋转，碰到S中的第二个点p2时，直线AB改绕p2按逆时针方向旋转而在p1与p2之间留下一条线段，该线段为凸包的一条边。继续旋转下去，最后直线AB旋转360°回到p1，便得到所要求的凸包。直线AB绕点pi的旋转是通过如下方法实现的：首先连接pi与非凸顶点pj得到线段pipj，然后求这些线段与AB与pipj的夹角，组成最小夹角的另一端点pi+1即凸包顶点。

3 TIN的程序设计及实现

3.1 数据结构

在程序实现TIN的绘制过程中，首先要针对不规则三角网自身的特点进行数据结构的设计，在此主要的数据结构有记录离散数据的点数据结构，记录边信息的线数据结构，存储三角形的三角形数据结构，以及在凸包形成过程中所使用到的节点数据结构等。

（1）离散点数据结构。程序中使用vectorT1数组，用来记录离散数据的坐标信息，通过数组自身带有的部分函数来实现对数据的操作。

（2）线数据结构。主要记录三角形边两端点的坐标信息，用数组vectorT2记录形成的三角形边，数据结构如下：

struct Line//储存直线的两个端点

（3）三角形数据结构。vectorT3存储了所有生产的三角形的顶点，顶点的高程以及相关边的信息，具体的数据结构为：

（4）在所有离散点的凸包的形成过程中，根据算法的要求不但要记录位于凸包线上点的坐标而且还要记录该点与下点连线与旋转线的夹角，使用数组vectorpoints对凸包点做记录，其数据结构如下：

3.2 程序的实现

3.2.1 数据的读取和显示

考虑到在实际中用来构成TIN的离散点数据量比较大，因此在该程序中数据是以*.TXT文件的形式存储于硬盘上，当程序运行时，通过调用CstdioFile类构建的对象，对文件进行操作，并通过函数WriteString()逐行将数据读取到内存中。在状态栏中分别显示了读取点的个数以及在构网之后形成三角形的个数，该功能可以通过构建CstatusBar类对象来实现。

3.2.2 TIN的绘制

根据算法，TIN的生成可以分为这样几步，首先确定基线从右边开始找点，然后调用函数GetThirdPoint(CPoint p1,CPoint p2)找到第三个点形成三角形，并将其存储到数组vectorT3中，其顶点和边分别存储到数组vectorT1和数组vectorT2中，如此递归，直到生成所有的三角形。最后从T3中读出三角形的顶点坐标，调用OpenGL画线函数，绘制出三角网。以下就是绘制TIN的部分代码：

3.2.3 绘制离散点的凸包

根据卷包裹算法，在求离散数据凸包上点的时候需要用数据结构Node来记录当前点坐标以及与下点连线同旋转线之间的夹角。首先找到Y值最大的一个凸包极点做基点，然后求出所有点与旋转线之间的夹角，快速排序找出夹角小的那一个点作为凸包点，最后转到下一个点，以该点为基点，重复寻找，直到形成一个封闭的凸多边形。部分代码如下：

3.2.4 程序演示

本实验中，以一个存有1000个离散点的文件为例，先打开文件导入数据，点击按钮生成TIN，再点击按钮绘制出TIN的生成区域，在文档视图的状态栏里，可以看到当前点的个数以及生成三角形的数量。经过验证，发现生成的TIN网满足最大最小化原则，符合实际应用的要求，生成结果可以图片的形式导出，如下图所示程序研究效果。

TU195[文献码]A

1000-405X（2016）-12-240-3