一种新的三角网格划分算法研究

杜丽美

（长治学院 计算机系，山西 长治 046011）

一种新的三角网格划分算法研究

杜丽美

（长治学院 计算机系，山西 长治 046011）

基于三角网格划分在三维重建中的重要性，提出了一种新的三角网格划分算法。算法的主要思想是：首先使用最近的点构造出首个三角形；然后以首个三角形为基础，采用异位法寻找新的顶点构造出新的三角形，直到满足结束条件时停止寻找。

首个三角形；距离；夹角；异位法；迭代

1 引言

三维物体重建技术是计算机动画、计算机视觉、医学图像处理等方面的核心技术。目前为止进行三维重建的方法主要有两种：第一种是直接用相应的软件来重建现实生活中物体，对应的软件有3DMAX、AutoCAD、Maya等，此种方法较为简单，其关键是对相应的软件的熟练程度；第二种方法相对复杂，需要一定的数学基础和编程能力。下面主要介绍使用此种方法进行三维重建的过程。

首先从真实物体表面获取相应的离散数据点，这些数据点的获取可以借助相应的仪器设备来进行。只要借助这些设备在真实物体表面扫一圈，相应的三维数据点就可以读入计算机存储设备中。

接着将这批数据点在计算机中进行处理。处理即将得到的这批数据点进行归一化处理，使得整体数据可以显示在计算机屏幕的指定位置上。

最关键的技术是使用什么样的算法对这批数据点进行三角网格的划分。进行三角网格划分的目的是重建出与真实物体表面一样的虚拟物体，因此三角网格划分算法选取的好坏直接影响物体的重建效果。

最后使用OpenGL函数对三角网格模型进行光照、材质、纹理、雾化等效果的设置，从而虚拟出真实物体。

2 算法的提出

文章主要针对二维平面上的散乱数据点来研究相应的三角网格划分算法。到目前为止已经有许多研究提出了各种三角网格划分算法，最常见的有区域生长算法、分治算法、细分算法等，这些算法[1-4]各有各的优缺点。算法类似区域生长算法，但和区域生长算法又有些不同，其中首个三角形的选取采取就近原则（即取决于数据点在相应数组中的存储顺序），以首个三角形为基础向外扩展其它三角形的过程中采用异位寻找法。

3 算法主要思想

1.1 数据的存储

因为文章只研究二维数据点，所以应选用合适的数组来存储这些从物体表面提取到的数据点。这里采用结构体数组来存储这些数据，相应的结构体数组的定义如下：

在此数组结构的定义中主要定义了每一个数据点（x，y）的坐标信息，并将此数组定义为Vertex [N]，其中N为已知给定的常数，表明此数组的长度为N（N即表示所有数据点的数目）。当找到三角形时，对三角形的三个顶点采用链表的形式存储，这样做的好处是可以动态分配存储空间，其对应的数据结构如下：

此结构中的num表示构造出的三角形的编号也可以理解为构造出的三角形的数目，V1[2]、V2 [2]、V3[2]表示第num个三角形的三个顶点坐标，*T_before为指向第num-1个三角形的指针，*T_after为指向第num+1个三角形的指针。

1.2 寻找首个三角形

从离散点数组Vertex[N]中取出第一个二维数据点（Vertex[1].x，Vertex[1].y），将此点作为首个三角形的第一个顶点，并将此顶点在数组Vertex[N]中的位置标记为flag1，因为这里选取的是Vertex[N]中的第一个点，所以这里flag1=1。然后在剩下的N-1个点中寻找与flag1这点距离最近的点，式（3.1）为两点的距离公式（其中i=2，3....N），若第m个点Vertex [m]与flag1最近，则标记flag2=m，表明首个三角形的第二个顶点已找到。

接下来寻找首个三角形的第三个顶点，主要在剩下的N-2个点中寻找（除去第1个和第m个点）。主要思想是：先使用公式（3.2）求出flag1与flag2的中点坐标Mid（mx，my），然后在这N-2个点中找到与Mid距离最近的点，具体公式为（3.3）所示，其中j=2，3…N且j≠m。假若第n个点Vertex[n]与Mid最近，则标记flag3=n，表明首个三角形的第三个顶点已找到。

Figure 3-1 looking for the first triangle图3-1 首个三角形的寻找

到此为止首个三角形的三个顶点全部找到，标号分别为flag1、flag2和flag3，最后将这三个点依次存入数组triangle[1].V1、triangle[1].V2、triangle[1].V3中，并将num的值记为1，表明所找到的为第一个三角形。如图3-1中的（a）为数组Vertex[N]中的N个数据点，图中的1、2、3…N表示数据点在数组Vertex[N]中的存储位置，（b）为采用本小节的方法找到的第一个三角形。

1.3 采用异位法扩充三角形

首个三角形已经找到，记为△1。现在以△1的三条边为基础向外扩展出新的三角形[5-6]，为方便描述，还是借助图3-1(b)为基础来进行，并将首个三角形的三个顶点记为a、b和c，如图3-2(a)所示。总体思想为：先以△1的一条边ab所在直线为基础，寻找处在c点异侧的那些点c1、c2、c3…，如图3-2（b）所示；然后计算∠acib的大小（其中i=1，2，3…），如图3-2（c）所示，在c1、c2、c3…中找到一点c'使得∠ac'b最大，c'即为将要扩展的点，因此第二个三角形△2已找到，△2的三个顶点为a、b和c'；将这三个点存入数组triangle[2].V1、triangle[2].V2、triangle [2].V3中，并且num+1；接下来采用同样的办法找到边ac所对的点b'，以及边bc所对的点a'，如图3-2（d）所示，分别将△3和△4存入triangle[3]和triangle[4]中，相应的num+1。

Figure 3-2 Looking for the first triangle图3-2 异位法扩充过程

以寻找c'为例，下面介绍判断点c与点c'处在直线ab异侧的方法。设a点坐标（x1，y1），b点坐标（x2，y2），则直线ab所在的方程为式（3.4）所示。若c与c'处在直线ab的异侧，则将c与c'的坐标代入式（3.4）的左边后所得结果应该异号，若c与c'处在直线ab同侧，则代入式（3.4）的左边后所得结果应该同号。设c点坐标（cx，cy），c'点坐标（cx'，cy'），则将c点坐标代入式（3.4）左边所得结果k1如式（3.5）所示，将c'点坐标代入式（3.4）左边所得结果k2如式（3.6）所示；接下来计算∠ac'b的大小，所用公式为（3.7）。

1.4 迭代

上一小节是以首个三角形的三边为基础向外扩展出了三个新的三角形△2、△3和△4，接下来再以△2的三边为基础向外扩展三角形。同样△3和△4的边也采用同样的方法向外扩充，总体来说就是反复的使用3.3小节的方法来逐步扩充，但是在扩充过程中难免会遇到新扩充出来的三角形其实就是以前已经存在的三角形的情况，所以每扩充一个新的三角形都要检查一下这个新三角形的三边是否和以前已经存在的三角形的三边一样。若一样，则去掉新扩充出来的这个三角形；若不一样，则保留此新三角形，并将三个顶点存入数组triangle中，三角形数目num加1。

结束条件：当以新生成的三角形的边再向外扩充时，所扩充出来的三角形全部都是已经存在的三角形且不存在单个的离散数据点时，停止扩充。到此已将给定的数组Vertex[N]中的全部数据点进行了三角网格划分。

4 试验结果与分析

根据文章算法，在windowsXP系统下使用VC6. 0进行编程证明了本算法的有效性。程序中窗体视点的定位以及点与点之间的连线借助OpenGL中的函数来完成[7]。图4-1中的（a）（b）（c）（d）（e）是采用文章所提出的算法分别对50、100、200、500、1000个数据点进行三角网格划分的结果，其中每张图中的数据点的横纵坐标都在0到150之间随机取值，所以生成的三角网的大小也在150*150的区域内，从图中可以看出，利用本算法可以很有效地对二维平面上的离散数据点进行三角网的划分。表4-1是对图4-1中的五种结果的分析，所分析的内容包括离散数据点数目、生成的三角网格的三角形数目以及运行时间。

Figure 4-1 Triangulation division using different data points图4-1 不同的数据点的三角网划分结果

Table4-1 Triangulations of index parameters表4-1生成的三角网的各指标参数

2 总结与展望

文章提出了一种新的三角网格划分算法，该算法的优点在于最终划分的三角网中的三角形大多数都是锐角三角形，只有很少一部分是钝角三角形。原因是文章在采用异位法扩充三角形时，对于点的选取采取夹角最大的原则。另外本算法虽是针对二维平面上的离散点进行的三角网格划分，但是对于三维空间[8-10]中具有平滑的凸曲面形态的离散点同样适用，只需将满足这种条件的三维离散点投影到二维平面上，再利用本算法进行三角网格的划分即可。可见本算法是有一定的优越性的，但是本文所提算法也有其自身的缺陷，对于三维空间中的复杂多变的离散数据点的三角网格划分还无法实现，这是今后有待解决的问题。

［1］谢增广.平面点集Delaunay三角剖分的分治算法［J］.计算机工程与设计.2012,33(07):2652-2658.

［2］吴晶,姚琪.平面任意区域的Delaunay三角剖分及其加密［J］.水利科技与经济.2006,12(02): 132-133.

［3］全红艳,张田文.基于区域生长的网格模型分割技术［J］.计算机辅助设计与图形学学报,2006,7 (7):2100-2106.

［4］宋晓宇,戚爰伟等.基于最大外接圆的约束Delaunay三角剖分算法［J］.沈阳建筑大学学报(自然科学版).2008,24(06):1094-1098.

［5］谢伙生.计算Delaunay三角剖分的新算法［J］.福州大学学报(自然科学版).2000,28(05):13-17.

［6］Tsai V J D.Delaunay Triangulations in TIN Creation:anOverviewandaLinear-time Algorithm［J］.Int.J.of GIS,1993,7(6):501-524.

［7］徐文鹏等.计算机图形学［M］:第1版.机械工业出版社,2009.201-204.

［8］施逸飞等.改进的三角网格表面近似测地线算法［J］.计算机工程.2014,40(11):225-228.

［9］王宏志.离散数据点集的3D三角划分算法研究［J］.工具技术.2008,42(04):85-89.

［10］熊英,胡于进等.基于映射法和Delaunay方法的曲面三角网格划分算法［J］.计算机辅助设计与图形学学报.2002,14(01):56-60.

（责任编辑 张剑妹）

TP391.41

A

1673-2015（2015）05-0031-04

长治学院校级科研课题(201419)。

2015—07—26

杜丽美（1983—）女，山西大同人，讲师，硕士，主要从事计算机图形学与图像处理研究。