三角网格剖分

三角网格剖分（精选八篇）

三角网格剖分 篇1

土壤地球化学成图中利用网格化处理主要目的是为空白区插值, 化探采样中经常会由于网格间距变化或者弃样现象的发生, 造成某区域数据空白, 为了成图需要必须对采样点进行空间插值, 近而使相邻点数据变化有过渡过程, 化探采样时常采用的方法有规则网和自由网, 规则网常用于较大比例尺 (大于1∶10000) 土壤地球化学测量时, 而自由网则常用于小比例尺测量过程中。

规则网测量能够更好地反映数据空间分布特征, 该方法已成为目前地球化学成图的主要数据形式。网格化是对这些数据的变化特征建立模型过程。目的就是构建空间数据场, 把空间上不规则、分散分布的采样点数据通过某一种插值方法建立相互之间的联系, 而自由网由于在空间距离上具有随机性, 使得在建立模型过程中增加了未知参数, 成图过程中会出现数据变化过渡性较差, 但成控矿效果上看, 自由网不受构造方向影响, 不容易漏掉矿化线索。

绘制地球化学图时, 需要根据不同的网度和测量方法选择合适的网格化方法, 现阶段常用化探成图软件Sufer、Mapgis、Geo IPAS主要采用三角剖分法、克里格法、加权反距离插值法、最小曲率法、最近邻点法等网格化形式[1], 本文主要就最常用的不规则三角剖分法和克里格法网格化进行对比研究。

1 不规则三角剖分法

不规则三角网是通过一系列互不交叉、互不重叠、连接在一起的三角面来逼近, TIN三角网模型具有精度高、速度快、效率高和容易处理断线和空穴等优点。

由于采用所有的数据点构造三角形, 为了让原数据能得到很好的体现, 给定三角形内的全部节点都要受三角形的限制。该方法速度快, 适合大数据, 均匀分布的数据网格化, 图面上稀疏区域将会形成截然不同的三角面。当数据足够时, 该方法对断线的保留具有其他方法不可比拟的优势。

三角剖分法是一种严格的插值使用最佳的Delaunay三角形, 通过直线连接各数据点形成一系列三角形, 并且所有的三角形互相不相交, 但每个三角形内的网络节点值由该三角平面决定。Delaunay三角化对平面上散乱点进行分割后, 将具有公共域的散乱点相连形成三角剖分, 之后对三角网格进行优化, 平面三角剖分最常用的优化准则有Thisessen区域准则, 最小内角最大准则、空外接圆准则, 最短距离准则, 张角最大准则, 面积比准则和对角线准则, 目的就是要使三角网格整体上尽量均匀, 避免出现狭长三角形。

在同一原则下由不同位置开始建立三角网络, 其最终的形状和结构是相同的。首先进行一次初始三角剖分, 最后根据最小内角最大化准则判断初始三角剖分形成凸四边形的共边三角形是否满足优化准则, 如果不满足, 就交换四边形的两条对角线, 多次循环直到所有的三角形都满足最小内角最大化准则为止。

化探数据分布一般可分为规则网和自由网, 自由网的数据不规律且可能存在数据在空间上不均匀现象, 在形成Delaunay三角网时一般通过以下三种方法完成。

1.1 域分割合并算法

先将数据分割成有利于三角化的点子集, 之后对每个子集分别三角化, 并由局部优化法 (LOP) 优化成Delauna三角网, 之后对每个子集的三角网进行连接, 最终等到完整的Delauna三角网。

1.2 三角网的连接法

找出点数据中相距最短的两个点连接成一条Delaunay边, 之后按Delaunay三角网的判别法则找出包含此边的Delauna三角形的另一端点, 按照这一规律循环, 最终完成整体网格化。

1.3 逐点插入算法

在包含所有数据点多边形中建立初始三角网, 然后将余下的逐一插入, 使得形成的Delaunay三角网满足局部优化法。

2 克里格法

克里格法最初是由南非金矿地质学家克里格根据南非金矿的具体情况提出的计算矿产储量的方法, 应用在化探数据成图中时, 是按照采样点空间位置和相关程度来计算空白区各元素含量, 理论上逼近真实值。之后法国学者马特隆对克里格法进行了详细的研究, 使之公式化和合理化。

克里格方法的基本原理是根据相邻点化探数据值 (各元素含量值) , 通过建立变差函数揭示的区域化探数据的内在联系来估计空白区元素含量;该方法总是尽可能地去描述原数据所隐含的趋势特征, 以已知网格数据为基础, 以变差函数为主要工具, 在保证研究对象的估计值满足无偏性条件和最小方差条件的前提下求得估计值。

克里格法是用原始的测量数据计算的网格数据来确定的, 其中每个网格的数据是由周边的原始数据的大小和距离决定的, 如果在很理想的地质条件下, 矿 (化) 体所形成的地球化学场应该是很有规律的, 而不是单个孤立的点异常, 而克里格法就是通过新生成的网格数值来圈出异常的趋势, 使原始相邻的突变变得平缓, 缓慢过渡, 使异常更接近理论模型。

现阶段克里格方法现已发展为多种类型, 如简单克里格 (simple Kriging) , 普通克里格 (ordinary Kriging) , 泛克里格 (universal Kriging) , 协同克里格 (cokriging) 等;不仅克里格法函数的形式多种多样, 其应用范围也多种多样, 通常在满足二阶平稳假设时可用普通克里格法;在非平稳 (或说有漂移存在) [2]现象中可用泛克里格法;当区域单元素分析数据变化服从对数正态分布时, 可用对数克里格法;当数据较少, 分布不大规则时, 对估计精度要求不太高时, 可用随机克里格法, 在解决实际问题中如果变量满足平稳性假设, 可直接用点或块段克里格方法, 这两种方法也称普通克里格。如果是非平稳的, 需要采用协同克里格方法。

要实现克里格法网格化一般需要分两步, 首先是对空间已知数据进行分析, 在充分理解数据变化特征的前提下, 建立多元变异函数模型, 进一步生成变异函数和协方差函数;目的是计算化探数据之间的相关参数;第二步是在已建立模型的基础上进行克里格计算, 对空白区进行插值;在这一过程中, 计算变异函数是克里格插值法的关键所在。由于变异函数对空间结构特性和随机分布特性都有着较好地反映, 所以利用该方法进行空间数据插值可以满足化探数据成图需要。

3 结论

通过TIN三角网和克里格法 (Kriging) 网格化成图对比发现:

(1) 克里格法 (Kriging) 网格化成图优点是线段圆润, 自然无突变现象。其缺点是图面异常范围与实际范围有位移, 且对高值区有贫化作用;因为在插值成图的过程中把插值区域个别低值变高, 或者个别高值变低。

(2) IN三角网成图优点是高值点和低值点位置准确且无位移, 异常浓集中心位置准确, 可信度高, 有利于后期异常检查, 缺点是图面效果差, 区块棱角多, 欠美观。

综合上述情况, 实际操作中根据工作的需要可以选择不同的方法成图, 如应用于成果研究和成矿条件分析时利用克里格法成图既美观又可以反映异常变化特征, 而真正在异常查证过程中利用三角剖分法成图更有利于我们寻找矿化蚀变线索。

摘要：绘制地球化学图时, 需要根据不同的勘查比例尺和测量方法选择合适的网格化方法, 现阶段常采用三角剖分法、克里格法、加权反距离插值法、最小曲率法、最近邻点法等常用网格化方法对数据进行处理、每种方法适用范围及参数设置均有所不同。

关键词：三角剖分,克里格法,网格化,化探

参考文献

[1]刘兆平, 杨进.地球物理数据网格化方法的选取[J].物探与化探, 2010, 34 (1) .

网格线中的三角函数问题 篇2

一、补形的策略

例1 （2015·山西）如图1，在网格中，小正方形的边长均为1，点A、B、C都在格点上，则∠ABC的正切值是（ ）.

A.2 B.[255] C.[55] D.[12]

【方法探究】如何把∠ABC放在某个直角三角形中是解决本题的关键，仔细观察可以发现：AB在小正方形的对角线上，能联想到45°角，只要连接AC即可构造出直角，然后在直角三角形中运用三角函数的定义求解.

【过程展示】如图2，连接AC，则∠CAB=90°，在Rt△ABC中，tan∠ABC=[ACAB]=[12].故选D.

例2 （2016·福建福州）如图3，6个形状、大小完全相同的菱形组成网格，菱形的顶点称为格点.已知菱形的一个角（∠O）为60°，A、B、C都在格点上，则tan∠ABC的值是 .

【方法探究】观察网格的特点，首先考虑如何将∠ABC放到一个直角三角形中，这是解决问题的关键.

【过程展示】如图4，连接DA，DC，则点B、C、D在同一直线上，设菱形的边长为a，由题意得∠ADF=30°，∠BDF=60°，∴∠ADB=90°，

AD=[3a]，DB=2a，tan∠ABC=[ADBD]=[3a2a]=[32]，故答案为[32].

二、转化的思想

例3 （2012·江苏泰州）如图5，在由边长相同的小正方形组成的网格中，点A、B、C、D都在这些小正方形的顶点上，AB、CD相交于点P，则tan∠APD的值为 .

【方法探究】直接求∠APD的正切值比较困难，可以考虑利用线段的平移对∠APD进行转化，找出它的“替身”，然后进行求解，以达到化难为易的目的.

【过程展示】如图6，取小正方形的顶点E，连接AE、BE，由图可知CD∥BE，∴∠APD=∠ABE，在Rt△ABE中，tan∠ABE=2，∴tan∠APD=2.

例4 （2016·山东淄博）图7是由边长相同的小正方形组成的网格，A、B、P、Q四点均在正方形网格的格点上，线段AB、PQ相交于点M，则图中∠QMB的正切值是（ ）.

A.[12] B.1 C.[3] D.2

【方法探究】如果直接求tan∠QMB可考虑连接AP、BQ，运用△APM∽△BQM求出AM或BM，然后在Rt△APM或Rt△BQM中求解；如果间接求解，应考虑对∠QMB进行转化，最好的思路是考虑线段的平移.①如图8，平移AB至A′Q，在Rt△A′PQ中求tan∠Q；②如图9，平移AB至PB′，在Rt△B′PQ中求tan∠P；③如图10，平移PQ使其经过线段AB中点D，然后在Rt△ACD中求tan∠ADC.

【过程展示】以第①种平移为例，如图8，平移AB至A′Q后，∠Q=∠QMB，在Rt△A′PQ中，tan∠Q=[A′PA′Q]=2，所以tan∠QMB=2.故选D.

三、等积法

例5 （2015·四川乐山）如图11，已知△ABC的三个顶点均在格点上，则cosA的值为（ ）.

A.[33] B.[55] C.[233] D.[255]

【方法探究】通过作三角形的高构造直角三角形，先利用等积法（或勾股定理）求出高，然后运用余弦的定义解答.

【过程展示】如图11，设小正方形的边长为1，过点B作AC边上的高BD.

由勾股定理得：AC=[32]，AB=[10]，

由等积法可得：[12]BC?h=[12]?AC?BD，

即[12]×2×3=[12]×[32]?BD，解得BD=[2]，由勾股定理，得AD=[AB2-BD2]=[22]，

∴cosA=[ADAB]=[2210]=[255].故选D.

例6 （2014·广西贺州）如图12，网格中的每个小正方形的边长都是1，△ABC每个顶点都在网格的交点处，则sinA= .

【方法探究】在替换与∠A相等的角比较困难的情况下，可以考虑通过作高进行构造，把∠A放在某个直角三角形中进行求解.

【过程展示】如图12，过点C作CE⊥AB，垂足为E，连接AD，则AD⊥BC，从不同的角度把△ABC的面积计算两次得：

S△ABC=[12]AB?CE=[12]BC?AD，

所以[12]×[25]×CE=[12]×[22]×[32]，

所以CE=[655]，在Rt△ACE中，

sin∠CAE=[CEAC]=[65525]=[35].

由此可见，遇到网格中的锐角三角函数求值问题，我们通常有两种思路：一是原地不动，想办法构造直角三角形求解；二是转移该角，如利用平行线进行转化.一般情况下，遇到求三角函数问题优先考虑转化，在没有好的转化思路的情况下再考虑如何构造.

点云三角剖分的软件实现 篇3

空间散乱点集的三角化被广泛应用在计算机视觉、逆向工程、自由曲面设计、计算机辅助制造(CAGD/CAD)设计和地球信息系统(GIS)等许多领域,是当前的一个研究热点。纵观当前众多三角剖分文献,大体上存在一些不足:

1) 大多数三角剖分算法[1,4,5,6]对点云具有选择性,即算法只能适用于某一类或某几类特定形状的点云,致使三角剖分算法的适用性受到限制;

2) 少数三角剖分算法[3,7]能适用于较多不同形状的点云,但这些算法都是经过复杂的剖分算法来实现的,在算法效果检验时往往只使用较小的点云数据进行试验,而对海量点云数据的处理仍然存在运行速度的瓶颈限制;

3) 三角剖分文献一般都只提出三角剖分算法,很少有真正提及三角剖分软件实现的内容,致使三角剖分算法到实际软件程序的应用还有一段距离;

4) 三角剖分算法中的相关参数基本由程序内定,没有积极的人机交互,同时运行的相关数据和图像也没有及时的显示,致使算法缺少良好的图形用户界面。

基于以上原因的思考,笔者试图实现一种软件,该软件是实用的软件,不但可以对多种不同类型点云实现三角剖分操作,而且该操作是快速的、流畅的、简单的、友好的,并且剖分结果是正确的、优质的。

1相关数据结构

三角剖分的过程中用到一些保存数据的对象,其中包括用以保存空间点的点类C3DPoint对象;用以保存点云几何尺寸、空间位置和方位等相关数据的点云盒子类CCube对象;用以保存初始剖分三角形的结构体Tri对象;用以保存点云待连接点的精简点类CMarkPoint对象;用以保存结果三角形的三角形类CTriangul对象和用以保存三角形边信息的边类Cline对象等等。

2软件实现

软件的实现大体上包括点云数据的读入、点云数据的显示、剖分方法的选择、具体三角剖分算法的实现、剖分结果的显示、三角面片的全体优化、畸形三角面片的删除和三角剖分结果的保存等步骤。详细软件实现流程如图1所示。

2.1读入点云数据并显示

点云读入时,根据点云数据文件的大小分为两种情况对待:对于较小点云数据(几十万个点以下),采用一次性读取再显示的方法处理;对于较大点云数据(百万个点以上),采用的处理方法是先间隔读取部分点云数据并显示,然后读入其余点云数据并更新显示,以减少用户等待的时间。点云数据的读入过程中同时完成点云相关参数(点云的空间尺寸、空间位置和点云的的方位)的寻找。然后将保存有读入点云数据的点数组m_3DPtArray和点云参数对象m_Cubed一起送往View类进行显示。

为了将点云数据显示在屏幕的中央并且不被边界裁剪,在View类中进行显示时,需要进行点云中央坐标的平移和点云长轴长度归一化等操作。图2为两种不同点云读入结果的显示,其中图2(a)中的高尔夫球头点云(38777点)是一次性读入的结果,图2(b)中部分脸盆点云(约756696点)分两次读入,当前显示的为第一次读入点云的结果。屏幕右侧的控制窗口中显示的为打开点云的相关参数。

2.2剖分方法的选择

三角剖分方法的选择包括两步,第一步是总体剖分方法的选择,包括空间部分点云的剖分和空间闭合点云的剖分;第二步是具体剖分方法的选择,空间部分点云的剖分可采用平面剖分方法中的网格剖分或者增量剖分方法,空间闭合点云的剖分可采用空间分割剖分方法或空间切片剖分方法。用户选择结果通过对话框中的单选按钮向程序内部传递。图3为剖分方法选择的两个步骤。

2.3具体剖分算法和初始剖分显示

2.3.1 平面网格三角剖分算法

平面网格三角剖分算法的基本思想是将空间点云投影到一个恰当平面上的网格中去,对网格中的投影点选择并连接,最后将平面的三角形连接反映射到空间点上形成空间点云的三角连接。其详细步骤参见图4中的流程图。

1) 相关参数的设定

当用户选择平面网格剖分方法后,要求首先对点云投影平面的选择。投影面的选择可以通过程序寻找最大投影平面来自动选择,也可以由用户通过观察显示点云的空间位置来自主选择。然后对话框会弹出已选的剖分方法和投影平面供用户确认。相关界面参见图5所示。

选择投影平面后,用户还将设定网格的数目。网格的数目直接决定剖分精度,网格数目越多,三角剖分的精度就越高,但也可能造成剖分的空洞现象。当用户设定的网格数目使每个网格中平均分不到1个点(或超过50个点或网格边长超过18个单位)时,程序就提示网格数目设定过多(或者过少)。当用户选择提示对话框的取消按钮时就可以重新设定网格参数,否则就按照当前设定的网格参数进行剖分。图6为网格参数设定过多的示例界面。

2) 点云的投影和精简

网格参数设定好后,就可以按照点云参数的空间位置和轴长将网格排列在投影平面上,然后按照点云中各个点的坐标将其划归于不同网格数组中。将各网格中位置最中央的点选出作为三角待连接点,并将有待连接点的网格对象(MarkPoint类的对象)中的EmIs标记记为FALSE。

3) 修补网格空洞

逐行扫描网格对象,对少于三个连续网格的空洞进行修补。修补时,从边缘向中央修补,空洞网格中添加的待连接点坐标采用其周围相邻网格中待连接点的坐标的均值代替,同时修改该空洞网格中的EmIs标记值。

4) 三角连接

逐行扫描网格对象EmIs标记值,根据当前扫描网格与相邻网格中的EmIs标记值的不同情况对该网格与其相邻网格中的待连接点进行相应情况的三角连接。在三角连接的过程中通过最小角最大化优化准则保证每个三角连接在其网格附近局部最优。三角连接后立即记录当前网格对象中的三角形分类情况(tri1,tri2,tri3,tri4)。

5) 边信息和三角形信息的记录

逐行扫描网格中点的三角形连接分类情况,根据相邻网格中三角形连接的分类情况找出相邻三角形的公共边并记录入边信息对象中。同时将各个三角形及其法向量一同存入三角形数组对象(CTriangul类数组对象)中,然后通过OPENGL进行显示。图7所示为平面网格剖分的结果。

2.3.2 平面增量三角剖分算法

平面增量三角剖分算法的基本思想是在一个恰当的平面上寻找2个初始包围三角形将空间点云在该平面上的所有投影点都包围在其中,然后用各个投影点与其相应的包围三角形形成新的三角形,直到所有的投影点都完成该动作后,将与初始包围三角形相关的假三角连接删除,就得到点云相应的三角形连接。其详细步骤见图8中的流程图。

1) 形成包围剖分三角形

用户选择平面增量三角剖分方法也需要对投影平面进行选择,其选择方式与图5所示情况一样。根据点云参数的相关信息,在点云投影平面找到四个边界上的投影点并向外移动一点,得到可以包围整个点云投影点的矩形。将这个矩形剖分,形成两个初始包围三角形,将它们存入临时三角形链表(TTL)中,同时也将这两个初始三角形的公共边的信息加入不同的边链表(BL)中。

2) 逐点加入

在点云数组中随机取出一点,搜索三角形链表,当该点都处于某一有向三角形三条边的左侧时,就找到包围该点的三角形,再用该点和找到的三角形三条边形成三个新的三角形。形成新三角形后删除点云数组中该新加入点,同时删去三角形链表中找到的包围三角形,并添加新形成的三个三角形。

3) 局部优化、更新信息

新形成的三个三角形和原来找到的三角形相邻的三角形之间可能不是最优剖分,将新形成的三角形分别与其原来找到的三角形相邻的三个三角形进行局部优化(优化准则是最小角最大化准则)。然后增加新形成三个三角形三条公共边的信息,如果优化过程中三角形连接情况有改变,还要更改三角形链表中的信息和边链表中的信息。循环完成加点、局部优化和信息更新,直到点云数组为空(即所有点都加入)。

4) 去除初始包围三角形相关信息

初始包围三角形的顶点并不是点云中的点,所以要将包含有这些顶点的信息全部删除。遍历三角形链表,逐一检查每一三角形顶点中是否有初始包围三角形的顶点,有就将该三角形信息删除,同时将该三角形的边信息也一并找到删除。

5) 形成法向量加入三角形数组

将三角形链表中的所有三角形及其法向量一并加入三角形数组对象中,然后显示。图9为平面增量剖分的结果。

2.3.3 空间分割三角剖分算法

空间分割三角剖分算法的基本思想是在恰当的位置将空间闭合点云分割成八个子点云,这些子点云通过适当的旋转后再调用平面网格剖分算法进行剖分,最后将各个子点云进行缝合构成整体点云的三角剖分结果。该算法的详细步骤见图10中的流程图。

1) 参数设定

该参数设定包括X、Y、Z三个方向的网格数目设定。参数设定后也对设定的参数合理性进行判断,与图5中的情况相同。图11为空间分割三角剖分参数设定的对话框。

2) 最佳分割平面寻找和点云分割

该步骤影响整体剖分的质量和成败,如果分割平面选取不当,会使子点云的不同部分在平面投影时造成重叠,使剖分发生错误。本算法通过空间点云的相关参数寻找3个分割平面,例如利用点云的X向和Y向的4个极值点在空间拟合成一平面作为XOY分割平面。根据每个空间点相对于3个分割平面的位置,就可以将整个点云分割进入8个子点云数组中。

3) 子点云的三角剖分

点云表面可能会与投影平面垂直或者会有一些凹坑,为获得更好的剖分结果,各个子点云进行三角剖分前需要进行一点角度的旋转,例如将第一象限的子点云分别绕X轴和Y轴分别旋转45度。经过旋转的各个子点云分别利用设定的参数调用平面网格三角剖分算法,获得各个子点云的三角剖分结果。图12中显示的是各个子点云三角剖分的结果。

4) 边界的寻找和缝合

逐行扫描子点云投影网格,对于某行(两端)相对与相邻行突出部分的待连接点作为该行的边界,否则就将该行最左(或最右)待连接点作为该行边界。加入边界点时要注意沿逆时针方向加入,即加点顺序为第一行待连接点、中间行右侧边界、最后行待连接点、中间行左侧边界。各子点云的边界寻找到后,将他们沿转折点(就是边界中与分割平面交线最近的三个点)分成三部分,再将这些分割后的边界与相邻子点云的相应部分边界按最小角最大化准则进行缝合,形成整体点云的三角剖分结果。

5) 形成法向量加入三角形数组

将三角形链表内的三角形连同各自的法向量加入三角形数组对象中,然后显示。图13中为经过边缝合后整体鼠标点云三角剖分的结果。

2.3.4 空间切片三角剖分算法

空间切片三角剖分算法的基本思想是将空间点云划归到不同切片当中,然后对这些切片进行缝合,对于两端的切片进行平面增量三角剖分后与相邻切片进行缝合,得到整体点云三角剖分的结果。其详细步骤见图14中的流程图。

1) 参数设定

该参数设定包括点云切片的总切片数目设定,左右两端合并切片数目设定和空间空洞识别参数设定。

这些参数在参数对话框弹出时都会带一个经验推荐值。当用户输入这些参数后,程序也会检查参数设定的合理性。图15为空间切片三角剖分参数设定对话框。

2) 点云切片的划分

根据用户设定的点云切片总数、点云最长轴长度和点云的空间位置,将点云中各点加入相应的切片数组中。对某一切片数组加入点时,只是将点与点之间距离大于0.8倍切片宽的点加入切片中。每个切片数组是根据用户的设定值来动态建立的,以最大限度节省内存空间。

3) 中间切片的处理

中间切片的处理包括中间切片中每个切片中点的排序和它们之间的相互缝合三角化。中间切片中的点排序是将每个中间切片中的点按逆时钟进行排序,同时将相邻两点中心夹角小于一定值(本算法为1度)的点删除。缝合从两切片中距离最近点开始,按照优化准则选择左下点或右下点形成新的三角形,如将形成的三角形边长大于用户设定的空洞识别参数时,就直接跳到下点继续进行其他三角形连接,直到回到起始连接点。在每次进行三角连接时,同时完成相应边信息的添加。图16是按照图15中参数设定值进行剖分时某两切片之间的缝合图像。

4) 左右两端切片的处理

左、右两端的切片点云处理方法相似,这里仅介绍左端切片中点云的处理,右端的以此类推。首先按照用户对端切片数目设定值(假设为5),将左端五片切片的点云进行合并,然后是调用平面增量剖分算法将左端这些合并点云进行三角剖分。为实现左端切片和中间切片的缝合连接,在中间切片的缝合时已经将第5片和第6片进行相应缝合。图17为左右两端切片中点云三角剖分结果的显示。图18为整个空间闭合点云利用空间切片方法获得的三角剖分结果。

2.4全体优化和结果显示

经过各种剖分算法剖分得到的结果,其三角形质量还不高,需要进一步优化,以达到用户的要求或者显示上的“最优”。因为剖分结果中的三角形已经具有法向量,为使拟合表面更加光顺,这里采用曲率最小优化准则[2]进行优化。具体优化方法是遍历边链表(在各三角剖分算法中已经完成边信息的添加)中的每一条边,验证该边的两侧三角形是否满足曲率最小优化准则来决定是否改变这两个三角形的剖分情况,当不满足时就改变剖分,同时更新三角形链表和边链表中的相应信息。当然这样每进行一次完整的遍历并没有真正达到全局最优,而只是在每条边两侧很小的区域内进行了相应的优化,所以需要进行多次这种优化,使前一次的优化在第二次优化中能得到累加和向周围扩散,直到全局最优。每次优化都会给出相应的优化结果信息,包括优化次数、遍历边数、当前优化修改三角形次数、优化结果精度和获得三角形个数。当优化精度达到0.99(笔者认为可接受的优化精度——最优)后,用户再次进行优化时,程序提示达到最优,无需再次优化。

每次优化后的更新显示是一个需要注意的问题,如果每一次显示都让OPENGL重新创建一组显示列表,每组显现列表预留十万个三角形空间时,当创建第三组显示列表时,程序已占用了1.86G的内存空间,计算机几乎处于停滞状态。为解决这个问题,笔者通过清除原三角形数组,清除原显示列表,初始化相关显示参数来重新装入三角形数组,重新创建三角形显示列表来实现显示的动态更新,这时内存占用情况始终维持在675M左右。图19为图9中剖分结果的第6次优化结果的显示,图像右侧是优化参数的显示。

2.5畸形三角形的删除

经过全体优化的三角剖分结果虽然相邻三角形之间没有再次优化的可能了,但图19中显示仍存在细长的畸形三角形,它们必须去除以再次提高三角剖分的质量。在删除畸形三角形前用户需要设定删除指数(1～10间的任何值,程序提供推荐数值为5)。删除指数越大,删除条件越苛刻,删除的三角形也越多,甚至可能造成表面空洞;反之,则畸形三角形删除不彻底。实际操作需要用户反复尝试和用户的要求决定。图20展示了畸形三角形删除操作的参数设定、删除结果显示等界面。

2.6三角剖分结果保存

当点云经过剖分、全体优化和畸形三角形删除等步骤后,获得的最终剖分结果需要保存,以备后续相关工作的需要。用户通过点击保存按钮(或菜单项),就可以将三角形数组中的每个三角形的顶点和三角形的法向量保存。如果用户忘记保存剖分结果而直接点击关闭所有文件按钮时,程序将弹出提示对话框提示用户是否保存剖分结果。

2.7进行新点云操作

为节省内存开销,提高程序运行速度,同时也为防止各个点云操作数据之间的相互串扰,用户在进行新点云操作前应该点击关闭所有文件按钮(或菜单项)。关闭所有文件是将文档类和视类中所有点云、边和三角形等信息的数组和链表全部清空或者删除,同时还将相关的参数进行初始化。图21中展示的是关闭所有文件前后内存占用情况,关闭所有文件前所有进程共占用612M,关闭所有文件后所有进程共占用420M。这样对于6237个点的点云相关信息关闭就可以清空近200M内存空间。

3实验结果

为检验本软件程序的实用性,笔者对每一种剖分方法都进行实际点云剖分。利用平面网格剖分对部分车座点云进行剖分的相关信息见图22中相关数据;利用平面增量剖分对完整车座点云进行剖分的相关信息见图23中相关数据;利用空间分割剖分对完整鼠标点云进行剖分的相关信息见图24中相关数据;利用空间切片剖分对完整高尔夫球头点云进行剖分的相关信息见图25中相关数据。本程序对点云的三角剖分是分步骤完成的,每个步骤的实际运行时间不长,几乎都是立即得到结果,所以笔者没有对程序的每个步骤的运行时间进行测定。(程序运行环境:CPU主频2.29GHz×2,内存为888MB、533MHz)。

4结语

根据程序实现的步骤和程序剖分的结果可知该程序(算法)具有以下特点:

1) 程序中集成4种不同的三角剖分方法(算法),可以对不同点云采用不同的三角剖分方法,扩大了程序对点云的适用范围。

2) 程序中三角剖分的分步骤完成,使实际每个子步骤运行的时间很短,同时采用了大点云数据分次读取,读取点云中同时采样点云参数特征,采用分区对边和三角形链表存取等方法减少相关寻找和优化等操作的时间,从而减少用户的等待时间,使程序运行流畅。

3) 程序运行中的相关参数不是程序中内定的定值,而是通过用户自己设定的,提高了程序运行的灵活性和与用户交换的友好性。

4) 子步骤操作中会有相关操作的数据和结果显示,使用户能够及时了解相关操作的信息,同时使操作的结果立即显示在屏幕上,即所见即所得,提高了程序界面的友好性。

5) 程序中通过用户任意多次的全体三角形光顺优化和畸形三角形删除操作,直到剖分三角形的质量达到 “最优”或者用户满意为止,提高了剖分三角形的质量。从最终剖分三角形的放大图中可以看到剖分三角形的质量较高。

6) 此程序的剖分方法尚需要进一步改进和完善的是对复杂点云分支情况的识别、分割功能的研究。

摘要：空间点云的三角化是机器视觉等领域中的一个共同的研究热点,研究的终极目标是对任何空间散乱点云都可以进行任何指定精度的、快速的、正确的三角剖分。软件(算法)通过多种三角剖分算法的集成提高软件对不同空间点云的适用性;通过多次三角形的全体优化和畸形三角形的删除保证三角剖分结果的正确性和优质性;通过采用大点云数据分次读取、合并点的读取和盒子参数提取、程序分阶段完成等措施提高程序运行的流畅性;通过参数设置对话框、操作结果数据对话框,操作结果的即时显示提高人机交互性和程序界面的友好性。实验证明该软件(算法)是实用的、正确的、快速流畅的、友好的软件(算法),其功能达到应用软件相应要求。

关键词：散乱点云,三角剖分,用户互动,优化

参考文献

[1]刘湘梅,邵建兴,侯维娜,等.基于波前法的球面三角剖分算法[J].重庆邮电大学学报:自然科学版,2010,22(3):229-344.

[2]张永春,达飞鹏,宋文忠.基于一种曲率最小优化准则的散乱点三角剖分[J].东南大学学报:自然科学版,2004,11(6):851-856.

[3]魏永超,苏显渝.基于方向角的散乱点云三角剖分算法[J].四川大学学报:工程科学版,2009,41(4):202-207.

[4]陈新河.八象限法三角化[J].巢湖学院学报,2008,12(5):51-53.

[5]陈新河.改进的切片法三角化[J].巢湖学院学报,2009,5(3):67-72.

[6]陈定造,林奕新,刘东峰.三维Delaunay三角剖分快速点定位算法研究[J].计算机工程与科学,2009,31(5):79-97.

三角网格剖分 篇4

逆向工程通过三维光学扫描仪获取物体形貌数据,该数据通常是海量的三维点,在数据处理中,需要经过三角化、光滑曲面重建才能为正向CAD软件所采用。点云三角化网格重建是数据由离散点域向面域求解的第一步,是后续光滑曲面重构的基础。其重构方法主要有基于Delaunay三角剖分的方法[1,2]、基于区域扩张的方法[3,4]和基于实体布尔差运算的方法[5,6],其中生长法是最常用的Delaunay三角剖分法[7]。目前,已有诸多学者开始采用隐式曲面法[9-11]构造三角剖分。尽管如此,作为三角剖分的基础,Delaunay法仍然集成于主流算法和商品化软件之中,尤其是在国内,Delaunay三角网格构造仍然是一个热点研究问题。作为一个三角网格剖分的基础和共性问题,本文对Delaunay三角剖分中的生长法进行分析,针对Delaunay算法的计算速度问题,设计一种顺序存贮的Hash数据结构,实现临时单纯形对象的快速存取、插入和删除等操作。此外,本文还提出基于微切平面的生长法,将基于空间四面体的空球搜索降维至局部二维的空圆搜索,提高三角剖分的时间效率。

1 Delaunay三角剖分

代数拓扑中,n-单纯形(n-simplex)拓扑等价于n-球面,每个n-单纯形是n维带边界流形。n-单纯形是三角形和四面体的一种泛化,一个n维单纯形是指包含n+1个节点的凸多面体。其精确定义是:n-simplex是某个n维以上的欧氏空间Rd(d≥n)中的n+1个仿射无关的点集的凸包。例如,0-simplex就是点,1-simplex就是线段,2-simplex就是三角形,3-simplex就是四面体。将构成单纯形的各点称为单纯形的顶点(vertex)。进一步地,将单纯形的k+1个顶点的凸包组合所构成的单纯形称为k维面(k-face),如点是0-face,边是1-face,三角面是2-face。

拓扑空间可以通过单纯形组合构造,人们希望把一个拓扑对象剖分成许多个小的单纯形,并要求任何两个相邻单纯形的相交部分仍是一个单纯形———这种剖分称为单纯剖分。在曲面情形,就是三角剖分。

R3空间中面的剖分是2-simplex,即三角形的组合,则相邻单纯形的相交部分为1-face,即为边。三角化过程就是以边为基础,逐步向外扩展生成三角形,新三角形的边将作为继续生长的基础。三角形生长应遵循一定的规则,Delaunay三角剖分规定了两项重要规则:

1)空圆特性:任一Delaunay三角形的外接圆内不会有其他点存在,如图1(a)所示;

2)最大化最小角特性:在点集P可能形成的三角剖分中,Delaunay剖分形成的三角形的最小角最大,如图1(b)所示。

图1 Delaunay三角剖分中的两个重要特性

2 生长法

生长法[12]是Delaunay三角剖分最直接的方法,算法设计直接由Delaunay三角剖分定义而来,算法简单明了。根据拓扑定义,Rn空间可由n维(及n维以下)单纯形组合构造,相邻两个单纯形的相交部分为n-1维面。生长法是以面为基础,在生长规则的控制下,为面加入顶点,构造新的单纯形。生长法三角剖分流程如图2所示。

传统的生长法[13,14]采用递归过程实现,Triangulation算法为递归生长法的C语言伪代码:

Triangulation算法以一输入面f0为基础,使用Find Next Vertex函数查找一个顶点v,使用f0和v构造单纯形s。接下来遍历s中的每个面f,重新调用Triangulation构造下一个单纯形。print语句打印输出新构建的单纯形,如果需要存贮输出,则只需设置一个列表,顺序存贮即可。

3 改进生长法

Triangulation算法是一个递归算法,容易理解和实现,但是大数据量计算的算法时域和空域特性差,因此需进行消去递归。据此,本文从数据结构上改进递归生长法,设计了一个(n-1)维面列表FList,用于动态存贮各面,从而消除递归。

3.1 数据结构设计

数据结构设计上,队列能够实现顺序存取和快速查找,但是删除操作效率低。为了提高算法性能,尤其是实现随机位的快速搜索和删除操作,采用哈希表进行数据操作。常规哈希表中数据的存贮位是随机的,因此还必须设计顺序存贮的哈希表结构。本文使用C++标准库的list容器作为顺序存贮器,结合Boost库的非排序类容器unordered中的unordered_set哈希模板,构造顺序存贮的哈希表。

unordered_set<T1,T2,T3>模板主要有三个参数:T1、T2和T3分别代表存贮对象、Hash编码函数(hash_value)和等值判断函数(equal)。其中hash_value函数为一个存贮对象生成哈希键值(key),当两个对象有相同的key值而产生访问冲突时,就会调用equal函数对两个对象作进一步比较。为了提高程序的可读性和可维护性,通常在对象类中定义hash_value和equal函数,然后以函数指针方式传入Hash表中进行调用。但unordered_set不能直接以函数指针为模板参数,因此将函数指针封装为结构体,以结构体参数形式传入。

数据结构定义:

接下来,就可以自定义顺序哈希表。为了便于用户使用,以list为外部容器,用于输入输出。在数据结构内部使用hash容器存贮对象并生成对应key值,用于搜索定位,两者内部的读写操作要保证一致。如下为自定义接口IListed Hash的过程:

1)以对象类为模板参数定义该接口类:

ctemplate<class TValue>class IListed Hash;

2)以TValue为list参数,定义list接口类:

typedef std::list<TValue>IList;

3)定义哈希表接口类:

typedefboost::unordered_set;

<TValue,THash Func,TEqual Func>IHash;

4)定义迭代器,其中hash迭代器为内部迭代器,list迭代器为外部迭代器:

typedef typename I Hash::iteratoriterator_in;

typedef typename IList::iteratoriterator;

5)定义内部数据存贮变量:

IListlistdata和IHash hashdata;

6)定义与list类似的各项操作,主要有insert、find、erase等操作和begin、end等迭代器操作方法,在实现上保证listdata和hashdata数据的同步读写。

采用以上设计的哈希表进行数据操作,对Triangulation算法进行消去递归,改进后为Triangulation2算法。

Triangulation2算法的伪代码为:

上述代码表示中有三个哈希表的操作函数:Extact Hash、Delete Hash和Insert Hash,它们分别对面列表执行读取、删除和插入操作,自定义Update Hash函数对面进行更新操作。为了避免重复生长,读取f0的Extract Hash函数中包含了f0的DeleteHash操作。算法以面列表FList为输入,循环判断是否为空,每次循环从FList中读取一个面f0,构建单纯形s,遍历s中的每个面f,如果已存在于列表,则从FList中删除,否则,插入f0,算法直至FList为空时结束。

3.2 三角剖分的详细过程

三角化算法的核心语句是Find Next Vertex函数中满足Delaunay规则的点的搜索。为了叙述方便,本文给出如下两个定义:

定义1由多个三角形或者两条边界边完全封闭的点为死点;反之,未被完全封闭的点称为活点。

定义2相邻三角形的共有边或边界边为死边;其他边称为活边。

设点集为P,当前遍历面为边e(v0,v1),其中v0,v1∈P是e的两端点,以边e为基础,采用以下生长规则搜索第三点v2:

只对邻域点进行搜索

此规则用于确定总体搜索范围。设点v0和v1的邻域分别为Neib0和Neib1,则搜索范围确定为Neib01=Neib0∪Neib1。

只对活点进行搜索

在图3中,粗线边v5v7和边v7v8为已确定的边界边。以v0为端点的边,以及边v5v4、v4v7、v4v8均为死边,两条边界边v5v7、v7v8亦为死边,其他边均为活边。显然,死边是当前搜索状态下的内部边,不能作为基础边再行生长,需要从面列表FList中删除;相对应地,活边作为外部边,应作为生长边进入FList。

为了准确表述,用点或边的使用频次f表示点或边的活性。在构网过程中,一条边只能为边界边,或者为相邻两个三角形的共有边,因此边的活性取值范围为{0,1,2}。点的使用频次与其构边的次数有关,设与点v关联的边集为E∈FList,则f的计数规则是:如果E=Ø,则置f=-1;否则f=E.size。由于E是FList的子集,因此f值和E的增减都在FList中体现:v的每次构边都将通过Insert Hash加入FList,相应有f++;每次提取边构建三角形时都将使用Extract Hash从FList中删除边,相应有f--。

生长点必须位于近邻三角形的右侧

此规则用于限定生长方向。为了定义三角形的生长方向,一般统一定义为逆时针(或顺时针)方向为三角面正向。这也延伸定义了构面边为有向边,其方向与面的方向一致。如图4所示,已构三角形面v0v1v2为逆时针方向,三条边v0v1、v1v2、v2v0亦为逆时针方向。此时,若对边v1v2搜索新的生长点,为了避免出现交叉三角形,必须限定生长点位于边v1v2的“右侧”。二维情形下,边v1v2将平面划分为左右两个半平面;三维空间中,假想经过边v1v2创建一个与三角面v0v1v2垂直的平面,该平面将整个空间划分为两个半空间,分别记为HS-和HS+。边v1v2是两个半空间的一条交界边,为了满足三角面方向统一的要求,在搜索空间HS+中,对边v1v2进行扩展时,应取其反向边v2v1。本规则限定了生长点必须位于HS+空间,该规则下,图3的备选点集{v3,v4,v5}中只有{v4,v5}为合法生长点集。

限定三角形的最小角度Amin

此规则避免出现狭长三角形,用于满足Delaunay最大化最小角特性。推荐Amin=5°~30°。

三角形外接圆半径与当前边的比值大于限定值Rmin

此规则用于外接圆半径,即缩小待建三角形的影响范围,旨在满足Delaunay空圆特性。

3.3 基于微切平面的生长法

在三维点云空间中,对邻域点的搜索实际是基于四面体的空球搜索,搜索速度和精度以及编程难度比二维点云大。对此,考虑将三维空间降维至二维,将三维点投影至微切平面,在二维平面内构建三角形。之后通过空间点与投影点的映射关系将平面三角网映射回空间,从而实现三角形的空间构网。算法可简单描述为以下四个步骤:

1)由当前遍历面为边e(v0,v1)的邻域Neib01=Neib0∪Neib1构建微切平面T,构造UV二维坐标系;

2)边e向T投影得e';邻域点集Neib01向T投影,转化为二维点集Neib'01;

3)在平面T内,按照Delaunay规则在Neib'01范围内搜索边e'的生长点,记最优生长点为v'2;

4)将v'2映射至对应的空间点v2,v2即为边e的生长点。

4 实例分析

采用C++语言编程在Microsoft visual studio 2008上实现以上算法,并且调用Open GL库函数显示点云,实验所用的计算机配置为Intel Core 2.30 GHz CPU,1.19 GB内存。对汽车挡泥板、兔子、马鞍模型进行三角剖分,其点云数量分别是:6408、34 834、56 780个。为便于叙述,将Triangulation算法称为方法1,Triangulation2为方法2,基于微切平面的生长法为方法3。方法1、方法2三角剖分思路相同,不同的是数据结构操作以及递归过程。三种方法对三种模型的三角化结果和耗时比较如表1和图5-图7所示。图5-图7中(a)是点云模型,(b)是方法1、方法2三角剖分结果,(c)是方法3结果。从表1和图5-图7中得出,方法1-方法3的三角化结果相同,但从耗时比较上来看,方法2三角剖分速度比方法1快,尤其是当点云数据较大时,方法2耗时几乎是方法1的一半。此外,本文提出的基于微切平面的生长法即方法3耗时更小,与方法2相同数据结构实现方法3时耗时比传统的生长法(方法2)耗时更小,对大数据点云模型,本文的生长法三角剖分效率更高。

表1 3个模型的实验数据

图5 挡泥板模型三角化结果

图6 兔子模型三角化结果

图7 马鞍模型三角化结果

5 结语

本文对Delaunay三角剖分算法中的生长法进行了详细的分析,设计了一种顺序存贮的Hash数据结构,实现临时单纯形对象的快速存取、插入和删除等操作,采用Hash数据结构消去递归的生长法执行时间更短。此外,本文提出了基于微切平面的生长法,将基于空间四面体的空球搜索降维至局部二维的空圆搜索,同样采用Hash数据结构对基于微切平面法的生长法进行操作。微切平面生长法三角剖分效果与传统方法效果相同,但微切平面生长法速度更快。对数据量为30 KB的兔子模型,三种方法的计算时间分别是8.5、4.3、3.2 s。

摘要：针对Delaunay算法的计算速度问题,从数据结构和算法两个方面加以改进。对Delaunay三角剖分的代数拓扑分析,设计一种顺序存贮的Hash数据结构,实现临时单纯形对象的快速和顺序存取、查询、插入和删除等操作;以单纯形边对象的活性分析为核心,以Hash数据结构进行操作,消去生长法的递归过程;此外,提出基于微切平面的生长法,将基于空间四面体的空球搜索降维至局部二维的空圆搜索。对汽车挡泥板和兔子模型进行三角剖分实验,实验结果表明,消去递归的生长法和基于微切平面的生长法和传统的生长法三角剖分效果相同,但是计算速度比传统方法效率更高。

三角网格剖分 篇5

在递归分割曲面的拼接中, 由于某些原因, 如边界破损引起的数据缺失、海量数据的压缩、边界的重复测量、测头打滑等, 多边形网格需要拼接的部分不一定会有完全相同的边界线或边界点。现有曲面造型软件如3Dmax虽能提供曲面融合的功能, 但只能对相同边界形状和边界点的曲面进行拼接。曲面的扩展是曲面建模软件必不可少的功能, 而三角曲面的扩展算法由于起步较晚, 还在研究之中。本文通过边界轨迹优先生成和点的有效性判断等约束条件对已有散乱点的三角剖分算法进行了改进, 以实现递归分割曲面拼接、扩展的编辑功能, 保证了拼接边界和扩展边界网格拓扑的正确性, 多次递归后可得到光滑连续的曲面。

1 拼接算法的实现

如图1所示, 对于要拼接的曲面片A和曲面片B, 先将A的边界点、边提取出来, 分别存储到点表和边表当中;再把B中包含拼接边界点的三角形去除, 将新生成的边界点、边存储到点表和边表当中, 此时存储在点表中的点具有稀疏散乱点性质, 对其进行三角网格化, 生成一个新曲面C;此时A (基曲面) 与C (补曲面) 、B (调节曲面) 与C具有相同的边界线和边界点, 所以能够通过C对A、B进行桥接, 融合成为整张曲面。

1.1 数据结构的建立

为了实现拼接操作, 建立了如下两种数据类型:

(1) 散乱点类型。其操作程序如下:

(2) 剖分边类型。其操作程序如下:

同时建立3个链表存储相应的变量:

list L_SpellNode //存储所有的散乱点

list L_SpellLine //存储边界边和剖分生成的边

list L_TriSpell //存储剖分成的三角形

1.2 曲面的预处理

曲面预处理完成离散点的获取、曲面平移等准备操作, 其具体步骤如下:①交互指定基曲面中需要拼接的边界;②提取基曲面中指定的边界边, 并存储在L_SpellLine当中, 提取出基曲面中指定边的界点, 将heredity标识置为1, 并存储在L_SpellNode当中;③计算出基曲面中拼接边界点的平均坐标, 记为NodeA;④交互指定调整曲面中需要拼接的边界;⑤计算出调整曲面中所有拼接点的中心坐标, 记录在NodeB中;⑥先把调整曲面中所有包含拼接点的三角形删除, 再将新生成的边界边存储在V_SpellLine当中, 将新边界点的heredity标识设为2, 并存储到L_SpellNode当中;⑦计算平移量, 进行曲面平移, 将调整曲面中的点及散乱点链表中来自调整曲面的点平移到指定位置。

1.3 递归分割曲面的拼接算法

通过拼接边界预处理, 得到存储边界边的边表和存储散乱点的点表, 接着要采用三角剖分的方法构造一个与两个拼接曲面有相同边界边和边界点的补曲面, 具体过程请见本文三角剖分算法的改进。

2 扩展算法的实现

先在以边界中心点为中心的正方形区域内均匀布点, 然后去除边界封闭区域内部的点, 最后对剩下的新增节点和原有边界点做平面内的、带边界的三角剖分。此时得到一个有正方形外边界、均匀、无交叉、无重叠的三角曲面片。这个曲面片的内边界与原曲面上需要扩展的边界完全相同, 能够很容易地融合成整张曲面, 从而实现了递归分割曲面的平面扩展。

同是采用三角剖分的方法解决递归分割曲面的编辑问题, 所以使用了与文中1.1完全相同的数据结构和链表, 不再建立新的数据结构。

扩展算法的实现过程如下:

(1) 手动选择需要扩展的边界。

(2) 判断选择的边界是否在某一平面内, 如果在则转到步骤 (4) , 否则转到步骤 (3) 。

(3) 根据曲面自身特点决定是进行平面裁剪还是投影, 以保证边界的共面, 并将平面上新生成的边界指定为需要扩展的边界。曲面边界投影方法如图2所示。对于边界边L_ab, 做端点a、b在指定平面内的投影点d、c, 然后对四边形abcd按最小内角最大准则分割成Δabd和Δbcd。

(4) 把需要扩展的边界边存储在边表L_SpellLine中, 用来限定扩展区域的内边界;相对应边界点存储在点表L_SpellNode中, 计算所有边界点的中心坐标, 记为Node_c。

(5) 输入决定新增节点的行列数n和平面扩展系数faction。

(6) 根据步骤 (5) 输入的参数, 确定以Node_c为中心的正方形布点区域。

(7) 在确定的正方形区域内均布n2个离散点。

(8) 查找出在封闭区域外部的所有点, 为后面的三角剖分提供数据。这里选择了夹角之和检验法作为判断依据。

(9) 在多边形外侧所有点中, 某些点可能与原边界边距离过近, 易产生狭小三角形, 不符合散乱点三角剖分要求, 因此还要对部分新增节点进行调整。如图3中点d、e、f虽然在多边形的外侧, 但不能满足三角剖分的要求, 需要删除。

(10) 将在多边形外侧的所有新增点存储到点表L_SpellNode当中, 将L_SpellNode中的点当作稀疏散乱点, 进行三角剖分。

使用从初始三角形向外推进逐步三角化的方法, 不仅能够很好地实现平面散乱点、空间散乱点的三角剖分, 而且适应性相对较强, 只要增加一定的约束条件就可以将曲面拼接问题和平面扩展问题统一处理。

3 三角剖分算法的改进

为了更好地对带边界条件的散乱点进行三角剖分, 在平面多边形的三角剖分算法基础上增加了两个约束条件:

(1) 边界优先生成。将存储在L_SpellLine中的边视为边界边, 并以这些边为初始边做三角剖分。在拼接操作中从边界边开始向内进行三角剖分;在曲面扩展操作中以边界边为内部边界向外进行三角剖分。由于边界边使用次数设为“1”, 所以只能够被一个三角形包含, 从而保证三角剖分区域的边界轮廓。

(2) 点的有效性判断。有效点是指能够与当前剖分边构成三角形的点。在拼接操作中规定来源标识相同的3个点不允许组成三角形;在扩展操作中规定对于一条直线L, 如果其两个端点与第3点的连线不和任意一条边界边相交, 且3点平均坐标在扩展区域内, 则称第3点为有效点。如图4所示, 对于边Lab来说, 点d为无效点, 但是点c有效;同理对于边Lef来说, g点为无效点。点的有效性约束进一步保证了剖分区域的边界轮廓。

三角剖分中最优点的查找规则、二次剖分原理及具体剖分过程, 采用的是环边界三角形向外逐层扩展的方法。由于引进新的约束条件, 程序的整体流程产生了相应的变化, 图5为改进后的三角剖分算法流程。

4 扩展操作的应用实例

本文只给出了改进算法扩展操作的实例。

图6 (a) 是初始的光照模型;图6 (b) 是扩展后的曲面光照模型;图6 (c) 是利用带约束的三角剖分算法构造出的扩展平面;图6 (d) 是扩展后的整张曲面的网格模型。为保证扩展边界点在同一平面内, 事先对图6 (a) 进行了边界平面投影。从图6可见, 应用本文提出的扩展算法不仅能够得到具有均匀网格的扩展曲面, 而且对带有凹边界的曲面进行扩展时不会出现交叉和重叠。

扩展系数faction=0.1, 增加节点数为10×10

5 结论

本文采用增加约束条件的办法改进三角剖分算法, 成功地解决了凸边界或凹边界曲面的拼接和平面扩展问题。

摘要：对递归分割曲面在编辑方面的拼接和平面扩展问题的散乱点的三角剖分算法进行了研究。通过边界轨迹优先生成和点的有效性判断等约束条件对原有剖分算法进行了改进, 顺利实现了递归分割曲面的拼接和平面扩展, 并保证了拼接边界和扩展边界网格拓扑的正确性。

关键词：散乱点,三角剖分算法,曲面拼接,曲面扩展

参考文献

[1]Choib K, Shinh Y, Yoon Y I, et al.Triangulatiscattered data in 3D space[J].Computer-Aided Design, 1988, 20 (5) :239-248.

[2]Zhou Xiaoyun, Zhu Xinxiong.A sufvery of triangulationmethods for scatter data points[J].Journa of EngineeringGraphics, 1993 (1) :48-54.

[3]张永春, 达飞鹏, 宋文忠.基于一种曲率最小优化准则的散乱点三角剖分[J].东南大学学报 (自然科学版) , 2004, 34 (6) :851-856.

[4]李小冬.基于递归分割的曲面建模方法及其应用[D].哈尔滨:哈尔滨工业大学, 2004:12-23.

[5]Ren Bing-Yin, Li Xiao-Dong.Local sharp featuregeneration and shape control of recursive subdivisionsurface[J].JSME International Journal Series C, 2005, 48 (2) :170-175.

[6]孙肖霞, 孙殿彪.散乱数据点的快速三角剖分算法[J].中国机械工程, 2006, 17 (s1) :245-248.

三角网格剖分 篇6

简单多边形的三角剖分在计算几何、科学计算可视化、图像处理、地学等领域都有广泛的应用,许多专家学者在此领域做了大量有益的探索[1,2,3,4]。文献[3]给出了一个任意多边形的Delaunay三角剖分算法,其时间复杂性为O(N2)。文献[1,4]提出的算法思想都是基于凹凸顶点判定法:首先按顶点的凹凸性将多边形三角化,然后按最大-最小内角准则,通过多次循环进行局部变换,得到Delaunay三角剖分网,虽然这两种算法得到的网形比较好,但要通过多次循环进行局部优化,从而加大了算法的复杂度,也降低了算法的执行效率。又由于在OpenGL下不支持凹多边形的填充,要达到该目标,必须将多边形三角化。笔者鉴于上述情况,提出一种简单多边形三角剖分算法,该算法稳定性好,执行效率高,并应用该算法,在OpenGL下快速实现了地层的剖面图快速生成。

1 算法涉及的数据

为了提高算法的执行效率,对多边形三角剖分,设计了两类数据结构,一是组成多边形的点数据结构,二是三角形数据结构。详细定义如下。

(1) 组成多边形的顶点结构定义

struct vertex

{ float x,y,z; //顶点的坐标

float angle; //顶点的内角

bool flag; //能否连成三角形标记

vertex* proVertex,*nextVertex //该点的前点和后点

};

(2) 三角形数据结构定义

struct triangle

{ vertex v[3]; //三角形的三顶点

}

(3) CArray<vertex,vertex>pAry; //存储多边形的顶点的数组

2 简单多边形的三角剖分

2.1 约 定

为了便于算法的描述,本文有如下约定:

约定1 设P1,P2,…,Pn是给定多边形的n个顶点,顶点Pi(i=1,2,…,n)按逆时针顺序排列,对于点Pi,Pi+1称为Pi的前点,Pi-1称为Pi的后点,如图1所示。

约定2 顶点Pi 的内角定义如下:以Pi为中心点,Pi与它的前一顶点Pi-1组成的边为径边,顺时针方向转到PiPi+1方向上时,所经过的角度,把它约定为顶点Pi的内角,即Pi的内角为α,如图1所示。

2.2 点在三角中的判定

由于多边形三角剖分算法中有点在三角形中的判定,本文约定,点落在三角形边上的情况也属于点在三角形中,提出了判定的两种方法:

方法1 根据点与三角形的关系进行判定

该方法思路是假定三角形的点按逆时针方向存储,如果某点都在三角形三条边的左侧或落在某边上,说明该点在三角形中;否则,该点在三角形外。

方法2 根据面积判定

该方法的思路是,将待定点P与三角形的三顶点相连,则可以得到三个三角形,分别是PAB、PBC和PCA,如图2所示。如果点在三角形中,则这三个三角形的面积之和等于该三角形ABC的面积,包括点在边上的情况;如果不等说明点P在三角形ABC中。计算公式如下:

$\begin{array}{l}S{}_{{\rm P}AB}+S{}_{{\rm P}BC}+S{}_{{\rm P}CA}=\\ S{}_{{\rm P}AB}+S{}_{{\rm P}BC}+S{}_{{\rm P}CA}\ne \end{array}\}S{}_{ABC}\begin{array}{l}\text{点}\text{在}\text{三}\text{角}\text{形}\text{中}\\ \text{点}\text{在}\text{三}\text{角}\text{形}\text{外}\end{array}$

2.3 简单多边三角剖分算法

根据上述数据结构及约定,笔者设计的简单多边形三角剖分的算法详细描述如下:

(1) 计算每个顶点的内角,并记录每个顶点的前点及后点,同时将所有顶点能否连成三角形的标记flag置为真,将组成多边形的顶点按逆时针方向存储在pAry中,然后取任一点作为待处理点,并记为点P。

(2) 对顶点P进行处理。处理过程如下:如果P点满足以下二个条件中的任一条,则停止P的处理,转(4);否则,转(3)。其中条件一是顶点的内角大于或等于180度;条件二是顶点的flag为假。

(3) 判断P点与它的前点(记为Q)、后点(记为O点)组成的三角是否包含其它顶点,如果不包含其它顶点,转(4);否则,将该顶点能否连成三角形标记flag置为假,转(5)。

(4) 将该顶点连成三角形(即△OPQ),此时需要将O点的前点改为Q(原来为P点),Q的后点改为O(原来为P),重新计算O、Q两点的内角,并将O、Q两点flag置为真,并从顶点数组中去除顶点P,转(5)。

(5) 取下一顶点进行处理,并将它重新记为P,重复步骤(2),直至pAry中的顶点数为3,结束多边形的三角剖分,并将该三顶点连成三角形。

该算法在每个顶点设置一个能否连成三角形标记flag,避免了对顶点能否连接成三角形的重复计算,算法的复杂度为O(nlogn),如果想进一步加速度剖分速度,可以将组成多边形的顶点分成点数大致相等的两部分,然后分别采用上述算法实现三角剖分。

3 算法的应用实例

为了验证算法的稳定性及执行效率,在VC++ 6.0编程语言对算法给予实现,并用一系列数

据对算法进行了测试,实验结果之一如图3所示。笔者借助于OpenGL,开发了地层三维建模系统中,应用上述简单多边形剖分算法,在该系统中实现了剖面图生成。由于地层模型是通过多层DEM建立的,剖面图是先通过剖切面与地层模型求交运算,在相邻的两层面TIN上可以得到一系列的交点,按顺序连接这些交点就组成一个简单多边形,然后将该多边形三角化,最后用颜色进行充填,就生成了剖面图。图4中的(a)是剖切面与地层模型,(b)是(a)对应的简单多边形三角剖分后,并用相应的颜色属性充填后得到的剖面图,(d)是(c)的地层模型的多面剖切的结果。算法生成的三角形态虽然不是最佳,但算法的执行效率很高,在地层剖面的生成中,考虑的首要因素是如何快速得到剖面图,与剖分生成的三角形形态没有关系,所以采用了该算法。当然,如果要提高三角形的形态,可以采用空外接圆准则进行LOP优化处理。

4 实验及结论

本文对简单多边形三角剖分算法进行了研究,提出了一种适用于简单多边形三角剖分的快速算法。该算法的主要关键点在于对内角进行动态断定,如果满足条件,就连成三角形,并修改它的前点及后点的相应信息,然后将该顶点去除。按该思想实现了简单多边形的快速三角剖分,算法剖分的执行效率高,思路简单,易于程序实现。最后将该算法应用于地层的剖面生成中,有效实现了地层信息的获取。

参考文献

[1]杨杰.基于凹凸顶点判定的简单多边形的三角剖分[J].小型微型计算机系统,2000,21(9):974-975.

[2]Turk G.Re-tiling polygonal surface[C].computer Graphics,1992,26(2).

[3]闵卫东,唐泽圣.二维任意域内点集的D elaunay三角划分的研究[J].计算机学报,1995,18(5):357-364.

三角网格剖分 篇7

Delaunay三角剖分实际应用中, 离散点数据都有一些特殊的要求。此时, 可以考虑把这些约束边强行嵌入到三角网中, 以满足实际的需要。

2 算法思想

约束边强行嵌入的Delaunay三角剖分算法就是把约束边嵌入到已有的Delaunay三角网中, 把约束边强行嵌入到Delaunay三角网中共分为两步: (1) 移除与嵌入边相交三角形, 剩余区域以约束边为界限分为左右两个伪多边形; (2) 对这两个伪多边形分别三角化。

3 移除相交三角形

要移除与约束边相交的三角形, 需要先确定约束边起点所在的三角形。可采用文献[1]中最速点定位的方法来定位起点所在的三角形。确定了起点所在的三角形后, 就可在计算约束边相交的第一个三角形, 由于三角网中, 一个顶点为多个三角行所共享, 鉴于三角网中点、边、三角形具有拓扑结构, 只需绕起点所在的三角形顺时针旋转一周, 并对滑过的三角形中起点的对边与约束边做相交测试, 如果相交, 则该三角形即为起始三角形。

确定首三角形后, 接下来计算与约束线段相交的三角形组成约束线段的影响域。如图1所示, 沿着约束线段边向前, 判断与约束线段相交三角形。

设ab为约束线段, t为首三角形, MTU为约束边左边的顶点链表, MTL为约束边右边的顶点链表, 计算约束线段的影响域算法如下:

Step1 初始化v为起点a, 置MTU、MTL为空;

Step2 若v不等于b, 转到step3, 否则转到step7;

Step3 计算与三角形t相邻且与顶点v相对的三角形tseq;

Step4 计算两相邻三角形t、tseq中三角形tseq不与三角形t共享的顶点vseq;

Step5 如果vseq在ab边的左边, 把t与tseq共享, 且在ab边左边的顶点赋值给v, 并把v添加到MTU中, 转到step2;

Step6 如果vseq在ab边的右边, 把t与tseq共享, 且在ab边右边的顶点赋值给v, 并把v添加到MTL中, 转到step2;

Step 7算法结束。

4 三角化伪多边形

对伪多边形三角化是基于分治法的策略来进行的。主要思想是首先分别对约束边左侧和右侧的的多边形进行三角化, 然后再连接合成所生成的两部分三角网。伪多边形三角化步骤如下:

设P为多边形的顶点链表, ab为嵌入边:

Step1 如果P只有一个元素元素c, 转到Step4 , 如果P中元素多于一个, 从P中找到一个能与ab构成合法三角形的点, 记为c;

Step2 以c为中点, 把P分为PE、PD两部分;

Step3分别对PE、ac和PD、cb两个多边形递归重复Step1, Step2;

Step4以abc形成一个三角形。

5 数据结构

本文算法用到如下的数据结构:

(1) 有序点表

(2) 有向边表

(3) 三角形表

6 结语

本文算法在VC++6.0环境下, 采用Open GL作为图形绘制接口进行实现。图2是采用本文算法把大量约束边嵌入后的情况。实验结果表明本文所采用的算法是可行的。

参考文献

三角网格剖分 篇8

关键词：三维地质建模,限定Delaunay三角剖分,OpenGL,三维地层可视化系统,虚拟钻孔

0 引言

近些年,三维地质建模一直是地质、采矿、GIS、测绘和岩土工程等领域的研究热点[3,4,5,6,7]。所谓三维地质建模,就是运用现代空间信息理论来研究地层及其环境的信息处理、数据组织、空间建模与数字表达,并运用科学可视化技术来对其进行真三维再现和可视化交互的科学与技术[1]。相对于传统的二维表格和剖面图表达地质数据,三维地质模型能够更加直观地展示地下岩层的形态和空间分布,可广泛用于矿山生产、地质研究、工程应用、科普宣传及教育等领域,因此非常有必要对其进行深入研究。

在矿产开采、地质勘察和岩土工程等领域,从业人员普遍采用SurPac、DataMine、GOCAD、C-Tech和MicroLynx等国外商业地质建模系统进行建模工作,但这些系统的数据处理、建模及可视化流程往往十分烦琐和复杂,且价格都比较高。为解决这一问题,相关领域的专家采用GIS系统、OpenGL、IDL、VRML和Java3D等自行开发系统进行地质建模[2,3,4,5,6,7]。利用GIS系统、IDL和Java3D开发三维地质模型系统,虽然可以减少三维显示代码的编写,从而缩短系统开发周期,但其生成的软件体积较大,且程序和代码的移植都十分麻烦。 而VRML虽然可以构建桌面和网上三维地质可视化应用,但需要浏览插件的支持,且空间查询功能较弱。

地层表面三角剖分作为三维地质建模的关键技术,三角网格生成质量直接影响建模的精度和可视化效果。现有的基于约束三角网格剖分(Constrained Delaunay Triangulation,CDT)算法生成地层表面三角网格的方法,若不采用人工方法在边界填加虚拟钻孔的条件下,算法生成的网格质量较差,如图1所示,而人工填加虚拟钻孔操作十分烦琐。限定Delaunay算法的主要优势在于能够在建模区域内部和边界上自动生成细分点(虚拟钻孔点),典型的CDT算法分为边界细分算法(Boundary Division,BS)和基于控制圆的边界细分算法[8,9],可以完成任意边域和任意网格尺寸的地层层面三角剖分,如图1(b)所示,可以很好地解决这一问题。

OpenGL(Open Graphic Library)是一种开放性图形库,作为一种图形与硬件的接口和图形标准,OpenGL独立于硬件设备、窗口系统和操作系统,编写的软件非常容易在不同操作系统间移植。OpenGL包含许多实用的图形函数,开发人员可以用这些函数快速绘制三维模型,并进行实时交互,结合常用的VC++或VB开发工具,能够快速构建三维应用程序。综上分析,本文从系统开发的角度,将限定Delaunay三角剖分算法和OpenGL三维图形显示技术相结合,利用限定Delaunay三角剖分算法快速生成高质量的地层表面三角网格,通过开发OpenGL三维程序,实现对钻孔数据的可视化管理,三维地质模型的实时交互创建和可视化,最后以南京某地区三维地质调查项目获取的钻孔数据为例,对系统的功能进行了测试,取得了较好建模及可视化效果。

1 系统设计与开发环境

1.1 系统设计

1.1.1 建模及可视化流程

通过程序读取钻孔数据,采用人机交互方式选取钻孔三维模型生成建模区域边界。其次,通过调用插值算法对原始钻孔数据进行加密,生成建模区域内部虚拟钻孔。

其次,利用限定Delaunay三角剖分算法生成各地层表面三角网;然后,封闭各地层边界面构成地层的三维体模型。最后,调用OpenGL绘制命令实现模型的实时显示,建模及可视化流程如图2所示。

1.1.2 系统功能

为尽量简化系统的操作流程,便于用户学习和掌握,将系统功能划分为数据管理和地质建模两个主要功能模块,系统功能如图3所示。

1.2 开发环境

1.2.1 开放源代码软件

开放源代码(Open Source)软件是一种在软件开发中过程中提供最终产品的方法。开放源代码软件已经在互联网上获得广泛使用,大大提高了软件开发的生产效率。利用限定Delaunay三角剖分算法源代码[9],对其进行一定的修正和封装,为系统的主要功能的实现提供了技术保障。

1.2.2 关系数据库和泛型编程

数据库为系统开发提供数据存储支持,用其存储工程勘查获得的钻孔数据,使得数据和程序相互独立,有利于加快系统开发速度及系统的升级和维护。同时,由于系统开发涉及的数据结构和算法较复杂,利用泛型编程(Generic Programming, GP)编程技术,可以将数据类型独立于算法之外,使得系统各模块代码的编写尽可能通用,且代码更具有可重用性和健壮性[10]。

笔者采用C++的标准模板库(Standard Template Library, STL)进行系统编程实现,由于STL封装了许多数据结构和算法,可以显著提高系统开发速度。

2 系统实现

2.1 数据处理

钻孔资料保存于Excel工作簿中,其数据内容包括钻孔编号、顶层高程、底层高程、地层代号、地层岩性、高程、X投影坐标和Y投影坐标等信息。利用Microsoft Access关系数据库将其转换成DBF文件集中存储和管理,钻孔数据表内容如表1和表2所示。

2.2 钻孔对象拾取和插值

钻孔数据作为建模的数据源,它能够揭示地下各岩层的空间分布情况。在建模过程中,需要根据实际情况添加、删除或修改虚拟钻孔,若能在三维环境中,利用人机交互的方式管理钻孔数据,不仅可以减少数据维护的劳动强度,而且有助于进一步的地质解译、分析和建模工作。系统采用OpenGL对象拾取机制,实现了钻孔的可视化查询、编辑和空间分析功能,钻孔对象的拾取效果如图4(a)所示。

根据原始钻孔的地层代码,得到各岩层钻孔点的空间坐标, 然后采用插值算法生成建模区域内部虚拟钻孔,如图4(b)所示。供选择的插值算法有反距离插值法、自然邻域插值法、线性插值法、径向基函数插值法等。其中,反距离插值算法和克里金插值算法最为常用,用类封装这两种算法,并提供相应接口,供系统调用。

2.3 构建地层层面

利用多层DEM法[11]构建地层表面,其操作步骤为:通过利用鼠标圈定出建模区域的边界,并将其连同前面生成的原始钻孔点和虚拟钻孔点作为限定Delaunay三角剖分算法的输入;由于算法的输出结果除包括建模区域内网格加密点和边界细分点(虚拟钻孔点)外,还包括地层层面三角面集合,需利用插值算法重新计算地层三角面各顶点的高程值;然后,利用OpenGL的三角形绘制命令依次绘制出各地层三角网,可以通过调用OpenGL中的绘制三角形面的函数glBegin(GL_TRIANGLES)来实现,如图5所示。最后,将限定Delaunay算法源代码封装成动态连接库(Dynamic Link Library,DLL),并提供相应接口,供系统调用。

2.4 封闭地层边界成体

在构建完地层层面后,由于限定Delaunay三角剖分算法新生成的只是建模区域内部和边界上的离散点(虚拟钻孔点)的空间坐标。其中,后者缺少其与边界相邻钻孔点的拓扑关系,不利用于地层边界线自动封闭成面。

为解决算法的这一缺陷,利用鼠标指定地层边界点序号,如图6(a)所示,重新生成钻孔点和边界线的拓扑关系,然后利用同步跟踪算法生成地层边界三角网,从而构建完整的地层体三维模型,如图6(b)所示。

2.5 模型可视化

在生成地层的三维模型的基础上,系统提供模型的剖面、切割和开挖等功能操作,如图7所示。

(1)剖面模型

由于采样数据的有限性,系统通过自动生成虚拟钻孔提高数据密度,用户可以利用人机交互的方式,连接原始钻孔和算法沿剖面线生成的虚拟钻孔,生成三维剖面模型。

(2)切割模型

切割模型可以更加直观地展示岩层内部的空间分布情况,通过鼠标任意指定切割线的空间位置和方面,系统可以自动实现生成切割模型。

(3)开挖模型

开挖模型可以更加直观地展示岩层内部的空间分布情况,用户通过鼠标指定开挖多边形位置和多边形的形态,系统能够自动生成开挖立体模型。

3 应用实例

为验证系统建模及可视化的可操作性和可靠性,以南京某地区三维地质调查项目地质勘察获取的钻孔数据进行了实际建模操作,系统以用户熟悉的多视图三维模型设计的方法,构建地层的三维模型,系统界面如图8所示。

4 结论

采用限定Delaunay三角剖分算法与OpenGL三维图形平台相结合的三维地层可视化方法,充分发挥了限定Delaunay三角剖分算法的网格剖分能力,可以明显改善地层网格质量和模型的可视化效果。同时,系统采用多视图人机交互建模界面,实现钻孔数据的可视化管理和实时交互建模,是对现有三维地质建模方法的丰富和完善。