基于OpenGL和离散点的三维建模可视化探讨

肖 坤，杨曦晔

（95685部队，云南昆明650500）

基于OpenGL和离散点的三维建模可视化探讨

肖 坤，杨曦晔

（95685部队，云南昆明650500）

OpenGL是当今使用最广泛的三维底层图形库。本文以GPS原始三维观测离散点为数据基础，通过读取存储离散点的文本文件，运用生长算法对空间散乱点进行Delaunay三角剖分，将离散点群数据有效地转化为三维模型数据。通过OPenGL技术实现了其三维可视化效果，实现放大、缩小、漫游、旋转等功能。在此基础之上叠加该区域的遥感影像图像，效果逼真，加之实测数据使其精度更加精确。

OpenGL；离散点；生长算法；三维可视化

0 引 言

随着计算机科学技术的发展，事物和景观的三维可视化表现已成为发展的趋势。三维建模可视化是模拟人类双眼处理物体的方式。往往容易获取物体、景观和地形等的一些离散点信息，而很难把它们在计算机中再次重新真实的表现或者模拟重建出来。Delaunay三角网结构良好，数据结构简单，数据冗余度小，可以适应各种分布密度的数据[1］。因此对这些散乱的三维点进行三角剖分，用许多的小三角形组成的表面近似物体表面。这样就相当于给散乱的三维点集搭起一个立体的网状骨架模型。能更加真实的表现物体的结构特征。Delaunay三角剖分采用生长算法，为了使算法的效率更快点，在寻找弧段对应的扩展最佳点时候，可以提前用弧段和第三点判断弧段另一侧的点，然后就从这些点中去寻找扩展三角形所需要的最佳点。OpenGL是一个跨编程语言、跨平台的专业图形编程接口，是最为广泛接纳的2D/3D图形API[2］。采用OpenGL技术进行三维的表达显示。叠加遥感影像图片增加其真实感。快速构建出真实的三维地形场景模型。本文对于计算机三维仿真、三维模拟、三维分析、虚拟现实和数值模拟等具有一定的参考和借鉴意义。

1 三角网生长算法简介

三角网生长算法的基本流程，如图1所示。

图1 生长法构建Delaunay三角网 （a）形成第一个三角形；（b）扩展生成第二个和第三个三角形

1）在所有离散数据点中取任意一点1（一般从离散点群几何中心附近开始），寻找距离此点1最近的点2，相连后作为初始基线1－2；

2）在初始基线右边运用Delaunay法则搜寻第三点3，形成第一个Delaunay三角形；

3）并以此三角形的两条新边（2－3，3－1）作为新的初始基线；

4）重复步骤2）和3）直至所有离散数据点处理完毕为止。

该算法主要的工作是在大量数据点中搜寻给定基线符合要求的邻域点。一种比较简单的搜索方法是通过计算三角形外接圆的圆心和半径完成对邻域点的搜索。使用外接圆的搜索方法限定了基线的待选邻域点，因而降低了用于搜寻Delaunay三角网的计算时间。

2 改进算法

三角剖分必须满足以下准则和特性：

1）空圆特性：Delaunay三角网的唯一性，在三角网的任意一个三角的外接圆内都不存在其他点。

2）最大化最小角特性：在相邻的三角形构成的凸多边形的对角线，在交换后，六个内角的最小角不再增大（也就是每个三角形的最小内角尽可能最大化）[3］。

针对该算法在寻找第三点时运算量较大。这个算法的实现中，为了使生成的三角形彼此间不交叉，而且新生成的三角形中不存在其余的离散点，此时采取的是寻找对应弧段的最佳点。在寻找弧段对应的扩展最佳点时候，可以提前用弧段和第三点判断弧段另一侧的点，然后就从这些点中去寻找扩展三角形所需要的最佳点。

3 离散点的三维可视化系统构建

3.1 离散点的读取

三维离散点存储成文本文件形式是目前的通用形式，它具有很好的跨平台性。通过读取文件file的形式将其读入此系统中，并利用OpenGL三维图形包将三维点群绘制。本系统利用GPS在某山区采集的三维离散点群进行实验。

3.2 散点的三维剖分和基本功能实现

为了实现Delaunay三角剖分和所需要的功能，并且记录下结果数据，需要定义如下的结构体：

针对该算法的核心程序需要定义如下函数进行实现：

Void Nearpoint（Trianglepoint＊ypoint，Trianglepoint＊all，int n）//寻找距离起始点距离最近点

Void jiline（Trianglepoint p1，Trianglepoint p2，Trianglepoint p3，Trianglepoint＊all，int n，int＊m）

//计算基线方程，判断符合条件的点

Int findfirst（Trianglepoint p1，Trianglepoint p2，Trianglepoint＊all，int n）

//找到原始三角形的第三点的编号

bool judgeTriangle（Trianglepoint p1，Trianglepoint p2，Trianglepoint p3，Trianglepoint＊all，int n）//判定三角形的合法性

bool judgeTritrue（Triangle＊all，Triangle kuozhan，int m）//判定新生成的三角形的唯一性

运用三角网递归生长算法的定义和本文中对算法进行的改进构建Delaunay三角网。对构网过程中生成的每个三角形投影面积、周长、三角形出现的顺序及凸包的面积数据存储于文本文件txt.如图2所示，对于生长算法构网的过程研究具有详细的指导意义。对于构建的三维Delaunay三角网如图3所示。

图2 存储数据的文本

三维可视化模型已经初步建立，通过OpenGL函数包中定义的平移矩阵、旋转矩阵和缩放矩阵，可以方便的对三维模型进行放大、缩小、漫游、旋转等功能的交互式操作。使三维模型更加具有真实感和操作性。将离散点群数据有效的转化为三维模型数据。

图3 三维Delaunay三角网 （a）三角网俯视图；（b）三角网侧视图

图4 效果图

4 三维地形可视化系统构建

三维场景基础就是地形数据，它是建筑物、小品的载体，可以表达地物特征与地貌特征。通过上述算法已经建立基本的地形模型，再在表面叠加遥感影像数据，使其真实感大大增强。既保证了地形数据在细节上的精确性，又保证了效果上的真实感。图4为效果图。

5 结束语

追求虚拟现实是未来计算机发展的必然趋势，三维重建首当其冲[4］。本文以最为常见的三维离散点群为数据基础，利用Delaunay三角网的结构良好、数据冗余度小、适应各种分布密度的数据等一系列优点[5］。采用目前最为流行的三维重建工具OPenGL对构建的三维模型进行绘制。开发出一套三维地形场景的快速和精确构建系统，并及时记录点计算和三角网构建过程中的数据，对于地形离散点的三维可视化研究具有一定的指导和参考意义。对于离散点群的三维仿真、三维模拟、三维分析、虚拟现实和数值模拟等具有一定的参考价值。

[1]童 庆，张敬谊，陈 诚，等.高分辨率图像特征提取和VG重构技术研究[J］.计算机应用与软件，2013，30（7）：116－118.

[2]李东阳.基于虚拟现实技术的虚拟农场的研究和实现[J］.微计算机信息，2012（10）：7.

[3]刘学军，龚健雅.约束数据域的Delaunay三角剖分与修改算法[J］.测绘学报，2001，30（1）：82－88.

[4]李国超，刘 爽，张延超，等.VC环境下基于OpenGL与3DS的三维场景重建[J］.电脑知识与技术，2010，6（35）：10131－10133

[5]代 莉，陈春华，聂 焱.在AutoCAD环境下不规则三角网构建及等高线生成[J］.地理空间信息，2011，9（2）：40－42.

Discussion on 3D Visualization Modeling Based on OPenGL and Discrete Points

XIAO Kun，YANG Xiye
（Unit 95685，Kunming650500，China）

OpenGL is one of the most widely used 3Dgraphic library of low－level.In this paper，three dimensional discrete points is the data base，by reading the stored discrete points of the text file，use the growth algorithm for scattered points by Delaunay triangulation.The triangulation of each triangle generated projection area，perimeter and the sequence of records.And the calculation of the discrete points in the future process of triangulation complete convex hullarea and number of boundary points，Through the 3Dvisualization of OPenGL technology to achieve the effect，to realize the function such as amplification，narrow，roaming and rotation.And images in the area of remote sensing image，the effect is clear，and the measured data to make it more accurate precision.

OpenGL；discrete points；growth algorithm；3Dvisualization

TP319

A

1008－9268（2015）01－0094－04

10.13442/j.gnss.1008－9268.2015.01.022

肖 坤（1987－），男，硕士，助理工程师，主要从事GIS三维可视化研究。

杨曦晔（1986－），男，助理工程师，主要从事GIS三维可视化工作或研究。

2014－11－10

金川公司－兰州交通大学预研基金（编号：JCYY2013015）

联系人：肖坤E－mail：xk5035＠163.com