物联网工程就业方向-雷锋名言

工学硕士学位论文
基于点云的三维重建技术研究
蔡宽
哈尔滨工业大学< br>2010年6月

国内图书分类号：TP391.41
国际图书分类号：6 81
学校代码：10213
密级：公开
工学硕士学位论文
基于点云的三维重建 技术研究
硕士研究生：蔡宽
导师：唐好选副教授
申请学位：工学硕士
学科、专 业：计算机科学与技术
所在单位：计算机科学与技术学院
答辩日期：2010年6月
授 予学位单位：哈尔滨工业大学

ClassifiedIndex：TP391.41U.D.C.:681
DissertationfortheMasterDegreeinEn gineering
STUDYON3DRECONSTRUCTION
BASEDONPOI NTCLOUD
Candidate：
Supervisor：
AcademicDe greeAppliedfor：
Specialty：
Affiliation:
D ateofDefence：
Degree-Conferring-Institution：
：
CaiKuan
oxuan
MasterofEngineering
C omputerScienceandTechnology
SchoolofComputerSci enceand
Technology
June,2010
HarbinInstit uteofTechnology

哈尔滨工业大学工学硕士学位论文
摘要
三维重建技术是计算机视觉、逆向工程、虚拟现实等研究领域中的一个
重要问题，是计算机图形学的重 要组成部分。随着科学技术的不断发展，传
统的基于图像的三维重建方法由于在精确度上、重建速度上、 算法适用性上
都有着不可避免的缺陷，已很难满足人们对高精度、真实感三维模型建模和
绘制的 要求，而基于点云的三维重建技术可以直接通过物体表面离散点简单
快捷地重构出高度真实的三维模型， 因此已成为当前三维重建技术研究的热
点，也是其中的重点和难点。
本文采用基于点的三维重建 技术，对物体进行三维网格表面重建。通过
三维激光扫描仪采集物体表面点云，接着对采样点云进行简化 处理，进而对
简化后的点云采用网格前沿生成算法进行三角网格化，从而恢复出具有真实
感的三 维物体网格表面模型。
为了减少用于三角网格化的点的数量，本文首先对散乱点云进行简化处
理 。针对点云简化过程中常用的
K
近邻搜索算法的搜索效率不能适应海量
空间散乱点云这 一问题，提出了一种可控参数
K
近邻快速搜索算法。通过
以测点X、Y、Z坐标值为中 心，每隔步长个点搜索与中心坐标值差值小于偏
移量的点，取交集中的前
K
个点建立测 点的
K
近邻，然后采用法向精度法
对散乱点云进行简化，使得在曲率变化大的地方保留 了较多的点，而曲率变
化小的地方保留了较少的点，为后续的三角网格化操作打下了良好的基础。
在得到简化后的三维物体表面点后，由于这些点是离散分布的，所以需
要对点云进行三角网格化。针对 以往的散乱点云空间直接三角剖分算法比较
少且生成的网格质量和算法效率普遍不高的问题，本文提出一 种改进的网格
前沿生成算法。首先建立候选点的搜索标准，并生成一个初始三角形，然后
不断沿 着初始三角形的边界搜索扩展边的最佳候选点，并判断最佳候选点是
否是扩展边的前面和后面一些边的最 佳候选点，以此生成物体的三维网格表
面模型。
最后，本文依据所提出的算法及标准设计并实现 了一个空间散乱点云
三维重建系统，进一步验证了所提算法的可行性和有效性。
-IV-

哈尔滨工业大学工学硕士学位论文
关键词三角剖分；三维表面重建；点云简化；
K
近邻；空间散乱点云
-V-

哈尔滨工业大学工学硕士学位论文Abstract
Asanimportantcomponentofcomputergrap hics,3Dreconstructionisakey
probleminthefieldof reverseengineering,computervisualization,virtualre ality,
edevelopmentofscienceandtechnology,thetr aditionalimages
based3Dreconstructionalgorithms canhardlysatisfytherequirementsof
modelingandre nderingofhighprecisionandreal3Dmodulesfortheirdefa ults
inprecision,r,pointcloudbased
3Dreconst ructionalgorithmscandirectlyconstructreal3Dmodelth rough
tly,researchonpointcloud3Dreconstructioni sa
focusof3Dreconstruction,adifficultyin3Drecon structionandakeyto3D
reconstruction.
Thispap ergotthemeshesofobjectsusingpointcloudbased3D
n tcloudsofobjectswerecollectedby3Dlaser
facemesh esofobjectsweregotfromsimplificationand
triangu lationofpointclouds.
Toreducethenumberofpointsf orlattertriangulation,wesimplifyscattered
eprob lemthatthetraditional
K
nearestsearching
algorithms’efficiencyarenothighenoughtoprocessvast spacescatteredpoint
clouds,aparameterscontrolla ble
K
nearestneighborssearchingalgorithmisgorithmsearchespointswithstepanddeviationin
t hemiddleofcoordinatevaluesofmeasuringpointsanduses the
K
nearestpoints
y,weusenormalprecisio nmethodtosimplifypointclouds
andkeepmorepointsi nhighcurvatureandlittlepointsinlowones.
Afterge ttingthesimplifiedscatteredsurfacepointsofobjects, wemake
eproblemthatdirecttriangulationalgorithm sorientedto
spacescatteredpointcloudsarerareand inefficientandthequalitiesoftarget
esisproposes animprovedmeshfrontieralgorithmto
gorithmsetsup thecriterionof
candidatepointsandgeneratesanini tialtriangleatfirstandgets3Dsurface
meshesofobj ectsbyrepeatingsearchingthebestcandidatepointofext endable
edgeandjudgingwhetherthebestcandidatepo intisthebestcandidatepointof
-VI-

哈尔滨 工业大学工学硕士学位论文
theadjacentedgesofextendableedge.< br>Finally,werealizethescatteredpointclouds3Drecon structionsystem
basingonthealgorithmsandcriteri aapprovedfromthisthesisandfurther
demonstrateth efeasibilityandvalidityofthepresentedalgorithms.Keywordstriangulation;3Dsurfacereconstruction;po intcloudssimplification;
K
nearestneighbors; spacescatteredpointclouds
-VII-

哈尔滨工业 大学工学硕士学位论文
目
摘
录
要.................... .................................................. .................................................. IV
Abstract.................................... .................................................. ................................VI
第1章绪论....... .................................................. .................................................. ..1
1.1论文研究的目的及意义.............................. .................................................. .1
1.2点云三维重建技术及其研究现状........................... ......................................2
1.2.1点云 曲面重建.............................................. .............................................2
1.2.2点云三角网格化...................................... ................................................4< br>1.3论文的主要研究内容及其组织结构............................. ................................6
第2章点云的特征及获取技术 .................................................. ............................8
2.1引言............ .................................................. .................................................. ...8
2.2点云的特征.................................. .................................................. ..................8
2.3点云获取技术.................. .................................................. ..............................9
2.3.1点云数据采集.... .................................................. .....................................9
2.3.2Lec iaHDS6000高清测量系统................................... ...........................11
2.3.3LeciaCyclone 软件................................................ .................................12
2.4本章小结.... .................................................. .................................................. 13
第3章可控参数
K
近邻快速搜索算法.................... ...........................................14
3 .1引言.............................................. .................................................. .................14
3.2典型的散乱点云简化算法............. .................................................. ............14
3.2.1点个数简化法..................... .................................................. ..................14
3.2.2点间距离简化法.............. .................................................. ....................15
3.2.3法向精度简化法............ .................................................. ......................15
3.2.4包围盒法............. .................................................. ..................................16
3.3可控参数
K
近邻快速搜索算法.................................... ..............................17
3.3.1传统的
K< br>近邻搜索策略......................................... ..............................17
3.3.2算法基本思想及算法 实现................................................ ....................18
3.3.3实验效果............... .................................................. ................................21
3.4本章小结..... .................................................. .................................................2 2
第4章散乱点云三角网格化................................. ...............................................23< br>4.1引言.......................................... .................................................. .....................23
VIII--

哈尔滨工业大 学工学硕士学位论文
4.2基本概念.............................. .................................................. ........................23
4.3几种典型的散乱点云三角网格化算法. .................................................. ...24
4.3.1局部Delaunay三角剖分算法.................... ..........................................24
4. 3.2散乱点云螺旋边三角剖分算法.................................. ..........................25
4.3.3非封闭曲面散乱点云直接三角 剖分算法...........................................27< br>4.4可控参数网格前沿生成算法................................ .......................................28
4.4.1 候选点的选择标准.......................................... ......................................29
4.4.2局 部网格优化准则........................................... .....................................30
4.4.3数据 结构及算法实现........................................... .................................30
4.4.4最佳候选点搜 索................................................. ...................................36
4.4.5实验结果 及性能分析............................................. ...............................40
4.5本章小结...... .................................................. ................................................42
第5章散乱点云三维重建系统设计实现............................. ...............................44
5.1引言........ .................................................. .................................................. .....44
5.2点云三维重建系统的构成......................... .................................................. 44
5.3点云三维重建系统的流程.............................. .............................................46
5.4重建系统测试........................................ .................................................. ......48
5.5本章小结............................... .................................................. .......................52
结论................... .................................................. .................................................. .53
参考文献....................................... .................................................. ...........................55
攻读学位期间发表的学术论文.... .................................................. ........................59
哈尔滨工业大学硕士学位论文原创性声明.. .................................................. ......60
哈尔滨工业大学硕士学位论文使用授权书.................... ......................................60
哈尔滨工业大 学硕士学位涉密论文管理....................................... .......................60
致谢................... .................................................. .................................................. .....61
-IX-

哈尔滨工业大学工学硕士学位论文
第1章绪论
1.1论文研究的目的及意义
众所周知，现实世界中的物体都是以三维立体形式存在的，物体本 身的
数据中包含着三维外形、透明度、颜色和纹理等表面结构信息。目前，对物
体表面结构信息 的记录方式主要有两种：一种是二维的图形、图像，另一种
是点云，相应的用于重建物体表面结构信息的 方法分为了两大类：基于图像
的三维重建和基于点云的三维重建。传统的图像记录方式由于丢失了相位等
立体信息，使得无法对物体进行多角度观察与分析研究；而点云则广泛存在
现实世界的各个领域 ，可以真实地记录物体表面的各种三维立体信息。因
此，对基于点云的三维重建技术进行研究就显得十分 迫切和必要。
基于点云的三维重建技术是计算机图形学、虚拟现实、计算机视觉等多
个学科交叉 的一个研究领域。其主要研究的是如何将点云记录的三维物体的
几何信息恢复成图形、图像，并通过计算 机显示出来，由此可以方便、快速
地对物体进行定量的分析、显示和处理等。基于点云的三维重建技术广 泛应
用于以下领域：计算机图形学领域，如影视特技、三维动画制作、三维游戏
模型的建立等； 医学领域，有医疗修复、医学检测与模拟、医学仿生、整形
美容及正畸的模拟与评价等；逆向工程领域， 有CAD模型重构、快速造
型、有限元分析等；刑事侦查领域，有弹痕、脚印、工具痕迹数据采集及建< br>模等；工业检测领域，有零件探伤、产品解析等。
近年来，随着科学技术的高速发展，基于激光和 结构光的三维数据采集
技术和硬件设备也日趋完备。这些测量设备可以很容易地从物体表面获取数
万、几十万甚至几百万的测量数据，而且往往包含大量的冗余信息。如果直
接对这些海量点云进行三维 重建，将导致重建效率极其低下。因此，如何高
效地对海量点云进行简化，已经成为基于点云的三维重建 技术研究的热点问
题之一，受到了越来越多的关注。另一方面，随着各领域科学研究的不断深
- 1-

哈尔滨工业大学工学硕士学位论文
入，需要重建的物体呈现出多样化、特殊 化和拓扑结构和形状任意性(如多
值曲面、带孔洞曲面等)等特点，所要求体现的细节也越来越精细。这 些都
对基于点云的三维重建算法的适应性、执行效率及生成的结果网格的质量提
出了很高的要求 。
1.2点云三维重建技术及其研究现状
基于点云的三维重建的基本任务是对测量设备采集得到 的点云进行曲面
重建，生成物体的三维实体模型。但由于测量得到的点云数据可能是散乱
的，也 可能是均匀的，目标网格的质量又有优劣之分，因此基于点云的三维
重建并没有统一的建模流程。但大体 上有如下的基本流程：使用测量设备对
待重建物体进行点云数据采集；然后对采集到的点云数据进行预处 理，包括
去噪声点、简化，得到物体的点云模型；接着对空间点云进行网格化和优
化，得到重建 的网格模型；最后对网格进行纹理处理，得到物体的三维实体
模型。
1.2.1点云曲面重建< br>在逆向工程、三维动画制作、有限元分析、工业检测等应用领域，常常
需要从一个离散的数据点集 出发，重构点集所属的原有曲面，这就是曲面重
建问题。曲面重建的基本思想是：对于给定的一组散乱采 样点集
P
={
Vi
}(
i
=1,2,...,
n< br>)，假定它位于三维空间中的一个未知面
U
，根据
P
构造
出一 个近似
U
的重建曲面
M
。假定
U
是三维空间中的一个光滑的 简单封闭
曲面。一个正确的曲面重建需要满足：
M
与
U
具有相同的拓 扑结构；曲面
上点的位置和曲面法向量的误差在允许的小范围之内。
曲面重建算法种类繁杂，可 按不同的标准分类如下：
(1)按采样数据点的数据形式可分为：散乱点云曲面重建算法和和结构
化点云曲面重建算法。前一算法中的点除了其空间位置信息是已知的以外，
没有任何其他的信息，而后 一算法则能够考虑点集的附加信息(例如折线)。
(2)按网格的拓扑要求可分为：有固定拓扑结构的算 法和使用结构和方
-2-

哈尔滨工业大学工学硕士学位论文
位信息的算 法。前者假定表面的拓扑类型事先是知道的(例如，平面，柱体
和球体)，后者则利用数据的结构来进行 表面重建。
(3)按曲面表示方式可分为：单形体表示算法、参数化表示算法和隐式
表示算法。 单形体表示是一个简单单形体的集合，包括点、边和三角形。这
一组包括Alpha形状和壳算法。根据 表示的方式，能够产生近似的或插值的
表面。参数化表示是用大量的参数表面片来表示表面。隐式表示算 法
[1]
试图
找到一个光滑函数来通过所有的点。
(4)按重建对象可分为： 面向表面的曲面重建算法和面向体的曲面重建
算法。前者在开表面和比表面没有区别，后者只适用于闭曲 面，而且一般基
于给定采样点集的Delaunay四面体化
[2]
。
(5) 按曲面重建的形式可分为：离散型曲面重建和函数型曲面重建算
法。前者要求输出曲面具有正确的拓扑结 构并且随着采样密度的增加而收敛
到原始曲面，其常用方法是建立离散点集的平面片逼近模型。
(6)按采样点集与重建曲面之间的关系可分为：插值法和逼近法。前者
要求拓扑结构已知，其重建曲面 通过输入的原始数据点，后者对采样没有特
别要求，但无法保证重建曲面通过输入的原始点云。下面分别 对两类曲面重
建算法进行简单介绍：
插值(Interpolation)法：一般采用二维D elaunay三角剖分进行三维曲面
重建。算法思想比较简单、直接。现有的比较典型的插值法有：3 D
Bowyer
[3]
、3DWaston
[4]
、Boisson nat
[5]
、
β
-skeeleton法
[6]
、a-s hape法
[2]
、r-
graphs法
[7]
、crust法[8]
、Umbrella-Filter法
[9]
等，这些算法都是先对点云进
行四面体剖分，然后按照特定规则不断查找相关三角网格，直至完成整个拓
扑搜索，其优点是能 构造出通采样物体表面拓扑一致的网格拓扑，其缺点是
四面体剖分时间长，难以适应大规模点云的网格拓 扑重建；Brinkley
[10]
，
Schmitt等
[11]
， Bolle和Vemuri
[12]
等算法，这些算法的曲面重建过程是：先
将三维数 据映射到二维参数域上在二维平面中进行曲面重建，然后将重建结
果映射回三维空间，这类方法只能重建 简单拓扑的曲面形状，如平面、球
面、柱面等，且算法复杂，难以实现，因此，实际中很少用到。
-3-

哈尔滨工业大学工学硕士学位论文
逼近(Approximation )法：重建曲面是原始曲面的一个近似。Amenta
[7]
将
逼近法分为以下3类：
(1)基于距离函数的曲面重建算法
这类方法的基本思路是：构造点到物体表面的(有向)距离 场，该距离场
的零等值面即为重建曲面
[13]
。华盛顿大学的Hoppe
[ 13][14]
在研究了大规模散
乱测量数据的曲面重构问题的基础上，于1992年和199 4先后提出了分片线性
和分片光滑的曲面模型。他主要是通过初始曲面估计、网格优化、分段光滑
曲面片进行曲面重建。其优点是，重建过程是自动进行的，使用十分简单、
方便，且能够识别曲面边界 。其缺点是要求点云的采样密度密且较均匀，重
建过程中涉及到复杂的法向一致性检查和等值面抽取，重 建非常耗时，重建
表面需要经优化处理
[14]
才能使用，且不能精确地表示二次规则 曲线曲面(如
球体、圆柱等)。
(2)基于空间细分的曲面重建算算法
这类方法的基本 思想是：首先建立一个包围点云的最小立方体，然后不
断地将最小立方体细分为分离的小单元(例如球、 四面体、立方体)，并搜索
和物体表面相关的小单元，最终找出属于物体表面的小面片,或者直接用含< br>有曲面片的小单元代替物体表面。
(3)基于增量的曲面重建算法
这类方法又称为区域增 量法
[15][16]
、曲面轮廓绘制法，其基本思想是：
从一个种子网格开始，不断 地按照指定的规则在点云中确定一个点与已构造
网格边生成新的三角网格，直至完成整体网格构造。算法 的关键是确定合适
的规则以构造新网格。其优点是原理简单，容易实现，且能实现在线性时间
内 构造完整的网格拓扑，重建速度快，因此常用于对散乱点云进行曲面重
建，其缺点是不易保证构造网格物 体表面的拓扑一致性。
1.2.2点云三角网格化
散乱点云三角剖分
[17]
(又称为三角网格化)的基本原理是将一组平面或空
间中的散乱数据点通过平面三角剖分或空间三角剖分 算法以三角形相互连
-4-

哈尔滨工业大学工学硕士学位论文
接，从而 获得一张关于原始数据集的优化的平面或空间三角网格。其实质是
以三角网格反映数据点与其邻近点间的 拓扑连接关系。目前主要存在两类散
乱点云三角剖分算法
[18][19]
，即投影域 三角剖分算法和空间直接三角剖分算
法。投影域三角剖分算法先将空间散乱点云分块投影到平面域内，然 后利用
平面三角剖分算法获得各块的平面三角网格，再将个平面三角网格映射成空
间三角网格。 空间直接三角剖分算法直接在空间中将散乱点云连接成一个优
化的空间三角网格，避免了散乱数据分块投 影的操作。空间直接三角剖分算
法中应用最广泛的是网格前沿生成法，下面对其研究现状进行简单介绍：
网格前沿生成法(又称为波前法)是一种典型的增量重建算法。其基本算
法思路是以剖分域的边 界为网格初始前沿，按设定的网格单元的形状，尺度
等要求向域内生成节点，连成单元，同时更新网格前 沿，如此逐层向剖分域
内推进，直到所有的空间都被剖分。网格前沿生成法的突出特点是提供了控
制网格密度和质量的手段，能够处理比较复杂的对象。但是网格前沿中存在
大量的查询操作以及网格前 沿的相交检测，这些操作是很浪费时间的。
网格前沿生成算法的前身是波前算法。波前法
[13 ]
是一种全自动网格生
成方法。这种方法最主要的特点是从物体的边界开始，定义一个“前沿” 。
在前沿上满足一定条件的地方生成一个单元，同时更新“前沿”，如此不断
重复，直到前沿变 空，网格生成结束。在生成过程中，前沿就像波浪一样往
前推进，直至消失，这就是此方法命名的由来。 波前法能够生成的单元类型
较多，对复杂物体的适应性强，它的最大优点是边界上单元的质量很好，它< br>的缺点是效率低，有时甚至会因为生成单元的条件限制太苛刻而不能进行到
底。George最早 提出了波前算法的思想，之后有许多人都提出相同或类似
的思想以及算法
[20][21][2 2]
。1985年，法国学者SHLo在其文献中提出了网格
前沿法的雏形，但他只是将网格前 沿作为节点连元的方法，没有与节点生成
同时考虑。1987年，英国学者e，i，.等实现了按
方向细化的网格前沿法，其按方向细化的特点特别适合于三维可压缩流的优
化算法。
近年来， 国内对网格前沿生成算法进行了大量的研究，出现了大量改进
-5-

哈尔滨工业 大学工学硕士学位论文
的网格前沿生成算法，其中较典型有：2003年，浙江大学躏宏伟
[2 3]
博士在
其毕业论文离散几何信息处理点到面中，根据点云的内在的性质进行网格前
沿生成，其处理点云采用的方法十分灵活，值得学习。2005年，董辰世、
汪国昭
[24]< br>等提出了一种利用法矢的散乱点的三角剖分算法，该算法的基本
思路是：先根据点云的有向法矢量 生成一层新的点云，之后采用了delaunay
三角剖分，然后在所有的delaunay三角形的集 合中根据平滑性选择需要的
三角形最终生成网格。他们采用的方法本质上是基于delaunay的三角 剖分
算法，且在选择三角形的过程中考虑了点云的内在性质，算法效果相当不
错；熊歆斌，宁涛 ，唐荣锡
[25]
等人提出了一种改进的波前法，为了避免剖
分过程中因曲率过大产生 不良局部网格，他们采用了在曲率变化大的地方停
止搜索的方法，大大提高了生成网格的质量；刘志刚< br>[26]
提出了一种改进的
螺旋边三角剖分算法，该算法综合螺旋边三角剖分算法和局部 Delaunay三
角剖分算法优点同时避免了其它们的不足。2007年，张鼎林
[27]< br>提出了一种
基于网格前沿生成法的空间曲面上散乱数据点的快速三角剖分算法，该算法
对 匹配点的选择施加严格的限制条件，使得整个三角剖分过程中始终只有一
个边界环，只适用于空间曲面是 连通的情况；黄淼、张海朝
[28]
提出了一种
非封闭曲面上的散乱点云三角剖分算法 ，该算法以非封闭曲面上点云的边界
为剖分起点，由边界向点云内部逐步收缩剖分，其优点是每轮搜索可 以生成
多个三角形，大大提高了三角剖分速度，但是，由于其在剖分是仅采用了点
对边的可见性 标准进行三角形生成，使得目标三角网格的质量不高，且该算
法不能用于闭曲面三角网格化。
1 .3论文的主要研究内容及其组织结构
本论文主要的研究内容是针对空间散乱点云三维重建的流程，分析 和评
价已有
K
近邻搜索算法、点云简化算法及散乱点云直接三角剖分算法的优
劣，并通过组合、改进已有算法实现物体表面的高质量、快速计算机建模。
第一章阐述了论文研究的目的 和意义，概述了曲面重建算法、点云三角
网格化算法的国内外研究现状，给出了本文研究的主要内容和结 构安排。
-6-

哈尔滨工业大学工学硕士学位论文
第二章首介绍了点云 数据的特点、分类、获取技术，描述了本文所使用
的LeciaHDS6000高清激光测量系统、Cy clone软件的技术参数和功能。
第三章的主要内容是对海量空间散乱点云进行简化。首先总结了一些 典
型的散乱点云简化算法，然后提出了一种可控参数
K
近邻快速搜索算法，
并 将这种算法应用于海量散乱点云简化，给出了点云简化算法的基本流程，
最后结合实验结果分析算法性能 。
第四章主要研究了空间散乱点云三角网格化问题。首先总结了三类典型
的空间散乱点云三角剖 分算法，然后提出了一种改进的网格前沿生成算法：
可控参数网格前沿生成算法，分析了候选点的选择标 准及局部三角网优化准
则，最后对算法的实验结果进行了分析。
第五章基于VC++平台利用O penGL设计并实现了一个点云三维重建系
统，重建物体的三维表面点和网格模型，进一步验证前面章 节所提算法的有
效性。
-7-

哈尔滨工业大学工学硕士学位论文
第2章点云的特征及获取技术
2.1引言
为了实现基于点云的三维重建，首先需要通过测量技 术获取所需要的点
云数据，才能够在此基础上进行三维重建的研究。本课题采样Lecia
HD S6000高清测量系统进行手骨点云数据采集。
2.2点云的特征
点云是使用各种三维测量设 备进行数据采集得到的一系列三维空间坐标
点的集合，它记录了物体表面在离散点上的各种物理参量，如 离散点的坐
标、大小、法向量，表面的颜色、透明度、纹理特征等。测量所得到的点云
按离散点 的分布密度可分为高密度点云和低密度点云。坐标测量机(CMM)
测量所得点云为低密度点云，通常有 几十到几千个离散点。而计算机断层扫
描法(CT)和光学测量方法所得到的点云为高密度点云，一般可 达几百万点。
此外，为了高效地处理不同形式的点云，根据点云中点的密度、排列方式等
分布特 征可将其分为以下四类：
(1)散乱点云
此类点云中的点没有明显的几何分布特征，呈散乱无序 状态。激光测量
机多次测量、坐标测量机(CMM)随机扫描所得到的点云即属此类。
(2)扫 描线点云
此类点云由一系列扫描线组成，扫描线上所有的点位于扫描平面内。激
光三角测量系统 、坐标测量机(CMM)直线扫描线所得到的点云和结构光扫
描所得到的点云均属此类。
(3) 网格化点云
此类点云中所有点都与参数域中一个均匀网格的顶点对应。投影光栅测
量系统、坐标 测量机(CMM)、激光扫描系统及立体视差法测量得到的数据
经过网格化插值后所得到的点云即属此类 。
-8-

哈尔滨工业大学工学硕士学位论文
(4)多边形点云
此类点云中的点分布在一组平行平面内。若用线段将同一平面内距离
最小的若干相邻点依次连接可形成一 组有嵌套的平面多边形。计算机断层扫
描(CT)、磁共振成像、莫尔等高线测量、层去法等系统测量所 得到的点云即
属此类。
在本文中，我们的研究对象是散乱点云，且点云仅包含离散点的三维空间坐标信息。
2.3点云获取技术
2.3.1点云数据采集
通过三维测量系统快 速、精确地采集物体的外形数据是点云三维重建的
基础也是其中一个重要的研究内容。近年来随着三维测 量技术的不断发展，
出现了很多点云数据采集方法
[29][30]
。常见的点云数据 采集方法基本分为接
触式和非接触式两大类。下面对两类测量方法的原理、优点和局限性进行简
要介绍和分析：
(1)
接触式测量方法
接触式测量方法的基本原理是通过测量设备的探 头接触被测物体的表面
来进行数据测量。根据探头接触方式的不同，该方法又可分为力触发式和连
续扫描式两种。接触式测量方法的优点是测量精度高、适应性强，缺点是测
量效率低，且无法测量软质 表面。
常用的接触式测量设备是坐标测量机(CMM)。坐标测量机的探头可以
在三个互相垂直 的导轨上滑动测量，三个导轨的位置测量系统经数据处理器
或计算机计算出被测物体表面各点的坐标。其 优点是测量精度和可靠性高，
对被测物体的材质、颜色、反射性没有特殊要求，对不具有复杂内部型腔、
特征几何尺寸多、只有少量特征曲面的零件，是一种非常有效可靠的三维数
字化手段，但不适合 对软质、易碎、易变形、超薄样件进行测量，对尺寸小
于测头直径的细微部分的测量受到限制。由于采用 接触式测量，导致测量速
-9-

哈尔滨工业大学工学硕士学位论文
度慢 、测量数据密度低，测量过程需人工干预，还需要对测量结果进行探头
探伤及探头半径补偿，这些不足大 大限制了其应用范围。
(2)非接触式测量
[31]
方法
非接触式测量方法的 原理是利用光、声、磁的物理特性，将一定的物理
模拟量通过适当的算法转化为样件表面的坐标。其优点 是效率高，缺点是测
量精度不高，不过近年来这种情况有了明显改善。
典型的非接触式测量方法 有计算机断层扫描法(CT)、立体视差法、结构
光法、激光三角形法、激光测距法、超声波测量法等。
计算机断层扫描法是以测量物体对X射线的衰减系数为基础，采用数
学方法经过计算机处理而重 建断层图像。这种方法目前已广泛应用于医疗和
工业领域。它是目前最先进的非接触式检测方法，可对物 体的壁厚、内部结
构进行测量，但存在空间分辨率较低，数据采集时间较长，重建图像计算量
大 、造价高，且只能获得一定厚度截面的平均轮廓等缺点。
立体视差法是根据物体表面同一个点在左右图像 中成像点的位置的不同
计算出物体上对应点的空间坐标。这种方法的主要问题是多幅图像上同名点
的搜索及自动匹配较为困难。
结构光法是将一定模式的光，如条形光、栅格光，投射到被测物体表面，并捕获光被曲面反射后的图像，通过图像的分析获得三维点坐标。结构
光法又可分为激光点扫描 法、激光线扫描法和光栅投影法。其中激光线扫描
法在测量精度和速度两方面都优于其余两种方法。激光三角形法利用光源与影像感应装置(如摄像机)间的位置与角度来推
算点的空间坐标；激光测距 法是将激光束的飞行时间转化为被测点与参考平
面间的距离。超声测量法是利用声音遇到被测物体产生回 声的时间计算点与
声源间的距离。
这些非接触式测量方法的优点是测量速度快、自动化程度高、 不受样件
材质和厚薄的影响。测量得到的数据量大，且排除了摩擦力和接触压力引起
的模型变形 测量误差，能充分反映被测量样件的表面形状信息，适于各种复
杂模型的三维高速测量。缺点是易受样件 反射特性和环境光的影响。
-10-

哈尔滨工业大学工学硕士学位论文
一般情况下，在对一个物体进行点云数据采集时，往往需要使用测量设
备从不同的视点对其进行多次测量 ，得到多片点云，因此获取的原始点云数
据还需要经过配准来形成一个整体。
2.3.2Lec iaHDS6000高清测量系统
本课题中我们使用瑞士Lecia公司开发的HDS6000高清测量 系统进行
点云数据采集。扫描仪的外观如图2-1所示。
图2-1LeciaHDS6000高 清测量系统
Figure2-1LeciaHDS6000highdefinitionsurvey system
LeciaHDS6000高清测量系统是新一代超高速相位式三维激光扫描仪，
它集三维激光扫描仪、外部数码相机、控制器、数据存储器、标准附件、选
件等于一体。其采集的数据可 与全球标准的坐标系融合(在使用GPS的情况
下)，并可以以多种不同的格式输出。LeciaHDS 6000高清测量系统可以进
行水平360度，垂直310度的快速扫描，分辨率可高达毫米量级。LeciaHDS6000扫描获取的数据可以直接与装有Cyclone软件的便携式
电脑接口连 接。在于电脑的数据传输上，高清测量系统可以采用串并口方式
传输，也可以采用TCPIP协议传输。 在采用串口方式传输时电脑对高清测
量系统的控制信息是通过串口从电脑传到高清测量系统的，而高清测 量系统
获得的数据是通过并口传给电脑的。操作者可以用Cyclone软件进行如传感
器参数 调节、数据获取、数据显示、数据处理和数据存档等操作。Cyclone
可以在Windows200 0，XP等操作系统上使用。
-11-

哈尔滨工业大学工学硕士学位论文
2.3.3LeciaCyclone软件
本课题使用瑞士Lecia公司的LeciaCyclon e软件对扫描得到的多部分点
云数据进行点云拼接和文件格式转换。其外观如图2-2所示。
图 2-2Cyclone
Figure2-2Cyclonesoftware
Cyclone是 Lecia公司为HDS(高清晰激光扫描)型三维激光扫描仪这一
系列扫描仪，如LeciaHDS2 500、LeciaHDS3000、LeciaHDS4500、Lecia
HDS6000、Lec iaScanStation等开发的软件。LeciaCyclone软件功能强大，
可以根据我们的 需要，为我们提供极为丰富的三维立体空间模型，立体影像
及三维定量分析。它不但具有强大的扫描仪工 作控制和数据配准功能，能够
将模型导出几种比较通用的文件格式，而且对点云的后期处理能力也很强< br>大，其特点如下：
(1)
扫描控制。可以方便地对扫描密度、扫描区域、空气校正参数等 扫
描参数进行设置，允许用户定制经纬网格线。
(2)可导入全站仪、GPS等外部测量设备的 测量数据，提高测量精度，
-12-

哈尔滨工业大学工学硕士学位论文
方便进行各种坐标系转换。
(3)坐标系转换。可自动计算扫描仪与数码相机坐标系之间的转换关系系。
(4)点云拼接。可以实现严格的标靶拼接，也可以进行高效的点云拼接
(尤其在工厂 扫描工程中)，但不具备数据融合功能。
(5)视图控制。包括点云视图的选择、平移、缩放，点云视图 参数化，
点云视图纹理映射和纹理渲染等。
(6)点云数据库管理。可以实现点云数据均匀化， 创建、管理、标记和
分层点云。
2.4本章小结
本文首先介绍了点云的特征、分类；然 后阐述了两种点云获取技术：接
触式测量和非接触式测量；最后对本课题所使用的LeciaHDS60 00高清测量
系统和Cyclone软件进行了简单介绍。
-13-

哈 尔滨工业大学工学硕士学位论文
第3章可控参数
K
近邻快速搜索算法
3.1引 言
三维测量设备采集得到的点云十分密集，且存在大量冗余数据点，从而
为进一步的建模、优化 等都增加了很多困难。因此，为了提高本文后期处理
的效率，在此先对点云进行简化处理，以尽可能地剔 除其非关键信息点而保
留了其关键信息点。
3.2典型的散乱点云简化算法
不同类型的 点云，其简化算法也不同。由于本文算法主要研究的是散乱
点云的三维重建，因此在此只讨论散乱点云的 简化。目前，根据简化的标准
不同，可以将散乱点云的简化算法分为以下几类：点个数简化法、点间距离
简化法、法向精度简化法、包围盒法。
3.2.1点个数简化法
点个数法
[3 2][33]
的基本思想是：按给定数据点个数进行简化，其关键是
要保证按严格的优先队列进 行简化，直到数据点达到预先指定的个数。算法
实现步骤如下：
①初始化，令MinDista nce=一个大数，NumExist=初始数据集中的
数据点数，NumTarget=预先指定的简 化后的数据点数，SimDelete[i]=
FALSE，i=0,1,…,n。
②如果Nu mExist>NumTarget，转③。否则将SimDelete数组中所有
标记为TRUE的点 从原始点的一维数组中删除，算法结束。
③对每个测量点
x
i
，如果SimD elete[i]等于TRUE，则查看下一个点，
否则查找与
x
i
相邻的< br>K
个邻接链表中第一个没有被标记为删除过的点，即
SimDelete[index] 等于FALSE的边节点。如果相应的distance则MinDist ance=distance，并记录IndexToBeDelete=index。对所有测点循
- 14-

哈尔滨工业大学工学硕士学位论文
环，就可找到未被删除的测点中距离最 近的两个点。置
SimDelete[IndexToBeDelete]=TRUE，NumExis t=NumExist–1,转②。
3.2.2点间距离简化法
点间距法
[32][3 3]
直接以测量点间的距离作为是否进行简化的判定依据，
算法实现步骤如下：
①初始 化，令SimDistance=预先指定的简化后的数据点间的最小距
离，SimDelete[i] =FALSE，i=0，1，…，n。
②对每个测量点
x
i
，如果SimDe lete[i]等于TRUE，则查看下一个点，
否则遍历与
x
i
相邻的K邻 接链表，如果某个边结点所连接的另外一个测量
点的SimDelete[index]等于FALSE ，且该边结点中相应的distance<
SimDistance，则置SimDelete[ind ex]=TRUE。对所有测点进行这样的检查
与遍历，就可以将整个点集中距离小于SimDista nce的两点中的一个做删除
标记。
③将SimDelete数组中所有标记为TRUE的点从 原始点云的一维数组中
删除，算法结束。
3.2.3法向精度简化法
法向精度法
[32][33][34][35][36]
是以删除一点后在曲面法向引起的误差作为判
断 是否删除该点的依据。算法实现步骤如下：
①初始化，令NormalDistance=预先指定的删 除一点在曲面法向方向
引起的误差,SimDelete[i]=FALSE，i=0，1，…，n。< br>②是否所有的点都遍历完毕，如果是则转④，如果否则转③。
③对每个测点
x
i
，计算删除后在曲面法向方向引起的误差
d
i
=|(
x
i< br>−
o
i
)*
n
i
|
。如果di④将SimDelete数组中所有 标记为TRUE的从原始点云的一维数组中删
除点，算法结束。
-15-

哈尔滨工业大学工学硕士学位论文
3.2.4包围盒法
包围盒法依
[37]
据所采用的简化标准又可分为平均距离法、均匀方格法
和三坐标轴切片法。
平均距离法是以一点 为中心的边长为d的立方体中所有点与该点的距离
的平均值作为判断删除该点的依据。算法实现步骤如下 ：
①构造点云的最小包围盒。
②将最小包围盒分割成m×n×l个边长为d的小立方体。
③将每个测点分别标记到相应的小立方体中，并初始化NumScale=预
先指定的数据精简百分比 ，AvgDistance[i]=0.0，i=0，1，…，n。
④计算以每个点为中心的边长为d的 立方体中所有点与该点的距离的平
均值AvgDistance[i]。
⑤将AvgDelet e中平均距离最小的NumScale个点从原始点云的一维数
组中删除，算法结束。
均匀方格 法
[38][39]
是以一点为中心的边长为d的立方体中与该点距离最
小的点作为判 断删除依据。算法步骤如下：
①求出点云的最小包围盒。
②将最小包围盒分割成m×n×l个边 长为d的小立方体。
③将每个测点分别标记到相应的小立方体中，并初始化每一点为
SimDe lete[i]=FALSE，i=0，1，…，n。
④取每个小立方体中离中心点最近的点，标记为S imDelete[i]=TRUE。
⑤将SimDelete数组中所有标记为TRUE的从原始点云 的一维数组中删
除点，算法结束。
三坐标轴切片法是沿X，Y，Z轴的正方向对点云数据进行切 片。在X
轴方向，将长方体包围盒中的点云数据投影到X向切片，在Y和Z方向分
别作类似处理 。算法的主要步骤如下：
①构造点云数据的最小包围盒。
②将最小包围盒沿X轴分割成n个小长 方体Bxi。
-16-

哈尔滨工业大学工学硕士学位论文
③求出每个过 小长方体X向中点(即X轴坐标为X=(Xi+Xi+1)2的点)
且平行于YOZ平面的切片，则可以 得到一组切片Dxi，并将该小长方体中
的所有数据点投影到该切片上。
④对Y向和Z向分别作 类似处理，可得两组切片Dyi和Dzi。
⑤将各小方块中的点云在该X、Y、Z三个方向上的投影进行 叠加。
⑥利用跟踪中轴线的方法对各层上的点云数据进行简化，算法结束。
3.3可控参数K
近邻快速搜索算法
3.3.1传统的
K
近邻搜索策略
传统的< br>K
近邻搜索策略是：首先对原始点云数据集S={Vi}(i=1,2,…,n)
进行分 块，按照空间位置邻近的原则设定点Vi的近邻区域，然后在近邻区
域中计算距离并排序，最后取距离V i最近的
K
个点作为其
K
近邻。由于我
们要处理的点云在数量上往往 是海量的，少则几万个点、几十万个点，多者
几百万个点甚至更高，因此将其精确分块是非常耗费时间的 ，而要将分块记
录下来也需要使用复杂的数据结构、占用大量的存储空间。
文献
[40 ]
提出了一种基于单坐标轴排序的
K
近邻搜索算法，其基本思路
是：每次在同 一个坐标方向上某个中心点前后各取M个点，三个坐标方向
都取完后删除重复的点再计算这些点到中心点 的距离。M太大则算法计算
量过大，M太小又不能保证取到全部近邻。由于不同的点云在规模和精度上差距比较大，因此该参数不太容易确定。该算法不能保证在一个坐标方向
上依据可调参数M搜索后 就已经取到了全部的近邻。
文献
[41]
对上述算法进行了改进，其基本思想是：首先 对点的X、Y、Z
坐标排序，然后用一个适当的距离阈值DISC分别在X、Y、Z方向上取位
于中心点坐标前后的点，得到一个包含中心点的K近邻的点的子集，最后
取距离中心点最近的
K
个点作为其
K
近邻。该算法可保证第一次在一个坐
标方向上依据参数DISC 取值后就已经取到了全部可能的近邻，其它两个坐
标方向搜索后只保留重复的点，进一步减少了最终参与 计算三维距离的点的
-17-

哈尔滨工业大学工学硕士学位论文
数量， 提高了算法效率。该算法中距离阈值DISC始终保持不变，DISC的
值取为扫描时设定的角分辨率精 度3-4倍，只适用于扫描时设定的角分辨率
精度是已知的情况。
鉴于上述算法的不足，本文作 出如下改进：将距离阈值DISC设定为可
控参数，其值可以根据读入点的坐标值的估计精度手动调整， 可以用于任意
情况下的点云
K
近邻搜索。下面对本文改进的可控参数
K
近邻快速搜索算
法进行介绍。
3.3.2算法基本思想及算法实现
可控参数
K
近邻快速搜索算法采用的可控参数有：近邻数量
K
、偏移
量Distanc e、步长NUM。其基本思想是：在整个点云中搜索到以中心点为
中心，边长为2*Distance( 偏移量)的立方体内的点，然后在这个小范围内计
算点到中心点的距离，取距离最近的K个点为K近邻。
可控参数
K
近邻快速搜索算法中存储点及其邻接关系的数据结构：
struc tPXYZNode
{
intindex;
doublexyz;
}
structPoint
{
intindex;
doublex,y,z;
i ntnum;
boolused;
}
可控参数
K
近邻快速搜索算的实 现步骤如下：
(1)读取原始点云数据，存入一个vector类型的容器pvec，并 初
-18-
邻接点的索引
可用来存储点的x,y,z坐标值及记录点与点间的距离点的索引
点的三维坐标
简化过程中可作点删除标记，剖分过程中作死边标记
点的邻 接表，存储邻接点及点间距离
简化过程中可过滤重复点，剖分过程中可删除内点
vector< PXYZNode>k;

哈尔滨工业大学工学硕士学位论文
始化各点的num为 0。同时把点的索引值和x,y,z三个坐标值存入三个
vector类型的容器 xvec，yvec,zvec。
(2)定义比较函数compare(PXYZNodea,PXYZ Nodeb)，调用
sort((),(),compare)，sort((),(),
co mpare)，sort((),(),compare)，以完成xvec,yvec,zvec按
x yz值由小到大进行排序，并将排序结果分别存入xa[]，ya[]，za[]。
(3)令i=0。< br>(4)以点xa[i].index为中心点，分别在ya[]，za[]中查找xa[i].index 所在
的位置索引，记为j，k。
(5)在xa[]中，对于给定的偏移量Distance，从 i点开始分别向前向后每
隔NUM个点计算一次x方向到i点的距离，将小于Distace的点的nu m值
增1，如果某个方向上点的搜索个数不足NUM个，则将全部点的num值
增1，xa[] 中所有num=1的点即为中心点xa[i].index在x方向上的近邻
点。
(6)同理在 ya[]，za[]中分别以j，k为基点查找中心点xa[i].index在y
方向和z方向上的近 邻点。
(7)xa[]中所有num=3的点即为中心点xa[i].index在x，y，z方向上近
邻点的交集，这个交集包含最终的
K
近邻点。计算xa[]中所有num=3的
点到中心点xa[i].index的距离，存入一个vector类型的容器rt中，同时恢复所有点的num=0。
(8)调用sort((),(),compare)，以完成 rt按邻接点与中心点间
的距离xyz由小到大排序，rt中前
K
个点即为中心点xa [i].index的
K
近邻。
(9)i++。如果i<数据点总数？，则转(4)。 否则算法结束。
结合上述可控参数
K
近邻算法的基本思想和实现步骤，下面给出其流< br>程图如下：
-19-

哈尔滨工业大学工学硕士学位论文
开始读入点的X、Y、Z坐标值
三坐标值及索引递增排序
初始化 i = 0
查找Y和 Z序列中i对应的索
引j和k
按步长搜索i、j、k前后差值
小于偏移量的点
i++
求i、j、k所搜索点的交集并
按距离递增排序
取交集前
K
个 点作为第i点的
K
近邻
是
i<数据点总数？
否
结束
图3-1可控参数
K
近邻快速搜索算法流程图
Figure3-1Diagramof parameterscontrollable
K
nearestneighborssea rchingalgorithm
-20-

哈尔滨工业大学工学硕士学位论文< br>3.3.3实验效果
本文对手骨、龙、兔子点云进行简化。实验结果如图：3-2，3-3，3- 4
所示：
(a)手骨点云(b)简化后的手骨点云
图3-2手骨简化
Figu re3-2handpointcloudsimplification
(a)龙点云(b)简化后的 龙点云
图3-3龙简化
Figure3-3dragonpointcloudsimplif ication
(a)兔子点云(b)简化后的兔子点云
图3-4兔子简化
Figur e3-4rabitpointcloudsimplification
兔子实验与文献[41]的实 验结果对比如表3-1所示：
-21-

哈尔滨工业大学工学硕士学位论文
表3-1本算法与文献[41]算法的实验结果对比
NUM(步长)
500
550< br>800
800
1200
2000
点数
1000
500 0
10000
20000
50000
100000
本算法运行时间( s)
0.089
0.712
1.395
3.504
19.74676.729
文献[41]算法运行时间(s)
0.094
0.734
1 .515
3.635
19.992
79.61
对比上述实验结果可以看出：算 法中步长NUM确定起来比较困难，只
能根据输出结果作动态调整；本算法的浮点数运算次数随着点数的 增加基本
呈线性增长，算法效率较高。
3.4本章小结
本章主要论述了散乱点云简化算 法的分类、可控参数K近邻快速搜索算
法的的基本思路及算法实现，并实现了法向精度法简化散乱点云， 通过实验
结果验证，可以看到对散乱点云的快速简化，取得了令人满意的结果。
-22-

哈尔滨工业大学工学硕士学位论文
第4章散乱点云三角网格化
4.1引言为了获得物体的真实感三维表面模型，在对点云进行简化处理后，还需
要对其进行三角网格化。散乱点云三角网格化主要解决的问题是对于给定的一个散乱数据点集合
P
，如何将各数据点 之间以三角形相互连接，形成一张由空间既不重叠又无
间隙的紧邻四面体集组成的空间三角网格
[29]
，并使网格质量较优。该问题
的解是
P
的一个三角剖分。一般而言， 对
P
的三角剖分剖分结果不是唯一
的，但只有部分结果的三角剖分网格的形态较优，能 够满足实际应用的需
求。我们所追求的剖分目标是使剖分所得的三角网格尽量接近最优Delaunay
三角网。
4.2基本概念
(1)凸包、三角剖分：对于给定的一个点集{
P< br>i
}(
i
=1,2,...,
n
)的任意子集
L，如 果存在一个包含L的最小的子集
P
s
，则称
P
s
为L的凸包 。给定空间内的
n个顶点的集合
S
={
V
i
}(
i
=1,2,...,
n
)，用不相交的直线段连接
V
i
，< br>V
j
，
1≤
i
,
j
≤
n
，
i
≠
j
，使得n个点的凸包内每一个区域是一个三角形，这一过程
称 为三角剖分(又称为三角网格化)。
(2)候选点、最佳候选点：三角剖分过程中满足特定标准、能够用 来构
造新三角形的0个、1个或多个点称为候选点，最后被选择用来构造新三角形
的候选点称为 最佳候选点。
(3)边界边、待扩展边、扩展边、死边、内边：在三角剖分进行中，构
成网格边 界的边称为边界边，尚未向外搜索候选点生成新边的边称为待扩展
边，而正在向外搜索最佳候选点的边称 为扩展边，经历一次搜索候选点生成
新边过程的边称为死边，而三角剖分结果中被两个三角形公用的边称 为内
边。
-23-

哈尔滨工业大学工学硕士学位论文
(4)边 界环、边界点：网格化过程中由一系列边界边按逆时针或顺时针
首尾相连构成的多变形称为边界环。边界 环上的点称为边界点。
(5)外点、内点：在剖分进行中没有被选择过的点称为外点，又称为孤
立点，所有相连边都是内边的点称为内点。
(6)邻近点集、邻接点集、邻接环、有效邻接环
[ 42][43]
：以某种算法搜索
到的散乱数据点
V
i
附近的K个散 乱数据点的集合，称为
V
i
的邻近点集。
V
i
的
邻 近点集中与中心
V
i
具有直接的拓扑连接关系的那部分散乱数据点的集合称
为 邻接点集，又称为自然邻近点集。邻接点集以正确的拓扑关系相连接构成
的环称为邻接环，邻接环上仅包 含边界点和孤立点的那部分环称为有效邻接
环。
4.3几种典型的散乱点云三角网格化算法散乱点云的三角剖分算法大体上可分为投影域三角剖分算法和空间直接
三角剖分算法两大类。投影域 三角剖分算法本质上是平面三角剖分。这类算
法具有简单、易实现、运行效率高、生成的三角网格接近最 优Delaunay网
格、适应性强等优点，是目前应用最广泛的散乱点云三角剖分算法。空间直
接三角剖分算法大致分为三类：基于雕塑的方法、距离函数法和网格前沿生
成法三大类。其中基于雕塑 的方法是基于3DDelaunay三角剖分的，只能对
三维的凸包进行剖分且处理效果不理想，而我们 经常遇到的是非凸包情形；
距离函数法的改进算法MC方法在医学领域中有一定应用；网格前沿生成法< br>能够处理复杂空间曲面点云，而且实现起来比较简单，速度快，因此在工程
中被广泛的应用。有鉴 于此，本论文对网格前沿生成算法提出了改进。下面
分别对几个典型的散乱点云三角剖分算法进行了介绍 。
4.3.1局部Delaunay三角剖分算法
局部Delaunay三角剖分算法
[26]
是一种利用2DDelaunay三角剖分算法间
接实现散乱点云三角剖分的投影域三 角剖分算法。其突出特点是其2D
Delaunay三角剖分是三维空间中局部区域的逼近。局部Del aunay三角剖分算
-24-

哈尔滨工业大学工学硕士学位论文
法的 基本思想是首先在切平面上对散乱点及其邻近点集进行2DDelaunay三
角剖分，得到局部拓扑关 系，然后将局部拓扑关系映射回三维空间中，最后
将所有的局部三维空间散乱点的拓扑关系拼接成一整张 三角网。
局部Delaunay三角剖分算法的实现步骤如下：
(1)数据预处理。其主要任务 是：搜索出每一个散乱点的K邻近点集
并估计出各散乱点的法矢和切平面。对于给定的一组空间散乱数据 点集
S
={
V
i
}(
i
=1,2,...,
n
)，
V
i
的坐标为(
x
i
,
y
i
,
z
i
)，K邻近点集为
R
={
Q
j
}(
j
=1,2,...,
n
)
,利用最小二乘法经过简单 计算得到关于
V
i
的K邻近点的
一个3×3矩阵C，把C的最小特征值对应的 特征向量单位化即可作为法矢N
的近似值。由
V
i
的坐标及法矢N求得
V
i
处的切平面。其中：
C
=
∑
(
Q
i
−
V
)
T

(
Q
i
−
V
)
i
=1
k
(4-1)
(2)局部Delaunay三角剖 分。即将每一个散乱点及其K邻近点集投影到
切平面上，然后运用2DDelaunay三角剖分算法得 到点与点之间的拓扑连接
关系，最后将剖分后的连接关系映射回三维空间中，就形成了
V
i
点及其K个
邻近点的空间三角剖分，生成了物体表面在
V
i
点的 局部三角网格。
(3)网格拼接。就是将每一个散乱点及其K个邻近点的拓扑连接拼接成
一个整 体的三维网格，使其接近最优的Delaunay网格。
局部Delaunay三角剖分算法剖分后的网 格空洞较多，网格重叠较为严
重。其原因主要是：剖分过程需要人工进行数据分块，分块的准确性及一致
性难以保证，且在边界处没有剖分信息，或者信息不统一，致使网格拼接的
难度增加，而网格拼 接直接决定着整体网格的质量。
4.3.2散乱点云螺旋边三角剖分算法
散乱点云螺旋边三角剖 分法
[26]
是一种局部Delaunay三角剖分算法和生长
三角剖分算法相结合的 方法。其突出特点是以边界环为基础向外生长。散乱
点云螺旋边三角剖分的主要思想是以包围盒算法搜索 边界点的邻近点集，估
计边界点的法向量，将边界点及其邻近点集投影到切平面上并进行局部二维
-25-

哈尔滨工业大学工学硕士学位论文
Delaunay三角剖分
[44]
，从而确定边界点的自然邻近点集，最后将自然邻近点
集以适当的方式添加到边界环 上。这样既可以避免网格拼接问题又能搜索到
自然邻近点集，三角剖分后的网格基本上接近最优Dela unay网格。
散乱点云螺旋边三角剖分算法的主要步骤如下：
(1)数据预处理。主要是确定 个散乱点的邻接点集，并设置各散乱数据
点初始为孤立点。建立散乱数据点的包围盒，即
K邻域；搜索散乱点的
K
邻
近点集；估计法向量，投影邻近点集；二维Delaun ay三角化，确定邻近点
集。
(2)种子点初始三角剖分。主要是选取一个恰当的散乱点作为种 子点，
并以其邻接点集对其进行初始三角剖分，生成初始的边界环，最后更改相关
散乱点的属性 。计算出散乱点集的中心位置，然后用包围盒算法找到距离该
中心位置最近的散乱点，将该点作为初始三 角剖分的种子点。初始化时，若
种子点被全包围，置种子点属性为内点；若种子点被部分包围，置种子点 属
性为边界点。
(3)生长三角形。生长过程：①对于边界环上的每一个当前边界点及
其邻接点集，确定其有效邻接环，将其有效邻接环分类，判断其邻接环
是否需要反向，然后将其以适当的 方式将有效邻接环添加到边界环上，
最后更新边界环和更改相关散乱点的属性。②遍历边界环一圈后判断 有无
新添加的孤立点，若有，则说明实际情况下的散乱点云数据点的三角剖分尚
未完成，重复生 长过程，若为否，则说明散乱数据点被充分三角剖分，应退
出循环，转(4)。
(4)后续处理 。主要是提取剖分后点云对象的边界重新估计个散乱点的
法向量。三角剖分完成后，最后的边界环就是散 乱点云对象的边界。提取该
边界环就可以得到三角剖分后散乱点云对象的边界。另外，由于中心点及其< br>自然邻近点集的拓扑连接通常就是该局部区域的正确连接。所以，以中心点
及其自然邻近点集重新 估计的法向量更为精确。为此，必须以自然邻近点集
再次估计中心点的法向量。
散乱点云螺旋边 三角剖分算法的运行速度较局部Delaunay三角剖分算法
-26-

哈尔滨 工业大学工学硕士学位论文
和生长三角剖分算法有一定程度的提高；剖分的散乱数据点对象接近最优Delaunay三角剖分，三角形“肥大”，基本满足“最小内角最大化”原则；
除局部区域外， 该算法能避免“重叠”和“空洞”现象；该算法能高效地三
角剖分数目较大的不规则和规则的散乱点云数 据。不足之处有局部区域有少
许三角形“重叠”；生成的结果网格可能有较严重的空洞。其原因在于：< br>“病态”情况的判别准则是在当前边界点的切平面上完成的，这与三维空间
的实际情况可能有所差 别。此外，边界环上不连续的邻接点集添加到边界环
后，也会造成“重叠”和“空洞”现象。
4 .3.3非封闭曲面散乱点云直接三角剖分算法
非封闭曲面散乱点云直接三角剖分算法
[28]
的基本思想是：由初始三角
形的边界开始，向未剖分区域逐步扩展边界环形成新三角形，直至三 角网格
覆盖整张曲面。其特点是由空间非封闭曲面边界向内中心区域进行边扩展，
成内螺旋方式 生长。如图4-1所示。
图4-1非封闭曲面散乱点云直接重建
Figure4-1Direc treconstructionofnonclosedsurfacepointcloud
非封闭 曲面散乱点云直接三角剖分算法的主要步骤是：
(1)数据预处理，建立数据点的K邻域。
(2 )构造边界环，生成初始三角网格。过程如下：任取非封闭曲面边界
的一点
P
1
,按顺时针或逆时针方向，依次搜索与
P
1
相距一定步长的另一边界
点P
2
，…，与
P
n
−1
相距一定步长的另一边界点P
n
，直到
P
n
+1
点与
P
1
重合。然
后依次生成边界边
PP
12
，…，
P
n
−1
P
n
，
P
n
P
1
，并标记
P
1
，…，
P
n
−1
，
P
n
为已处
理点，得到边界环。从边界边链表EL中取一条边界边
PP
12
作为扩展边， 从点
-27-

哈尔滨工业大学工学硕士学位论文
链表VL中未处理的点 里搜索
PP
12
的最佳候选点
P
i
，逆时针连接
P
1
、
P
i
、
P
2
即生成初始三角形
tri
0
，同时标记点
P
i
及三角形
tri
0< br>的内部点位已处理点。
(3)网格收缩。从边界边链表EL中取一条边界边
PP
12
，向边界内区域搜
索
PP
12
的最佳候选点P。判断P与
PP
12
的上一条边Epre否构成逆时针，若是，
则连接生成三角形
tr i
1
,并将其加入三角形链表TL，再判断P与Epre的下一条
边是否构成逆时针， 若是，则重复本步骤；否则判断点P与
PP
12
的下一条边
Enxt是否构成 逆时针，若是，则连接生成三角形
tri
2
,并将其加入三角形链表
TL，再 判断P与Enxt的下一条边是否构成逆时针，若是，则重复本步骤；否
则，依次判断P和边界环中与< br>PP
12
、Epre、Enxt不相邻的边界边构成逆时
针，若是，则生成三角 形
tri
3
，将边界环分裂为两个并调整边界环链表。如
果当前边界环链表尚 有待扩展边，则取本边界环中下一条待扩展边，否则从
边界环链表中取下一个未处理的边界环，同上处理 ，直到边界环链表空为
止。
4.4可控参数网格前沿生成算法
可控参数网格前沿法是对 网格前沿生成算法的一种改进，其改进点是：
将候选点的选择标准设定为可控参数，可根据需要组合不同 的标准实现网格
化；候选点搜索过程中加入了对候选点与扩展边所形成的三角形与扩展边所
在三 角形及其前一三角形和后一三角形的夹角阈值；可同时处理闭曲面和非
闭曲面两种情况。其突出特点是按 方向细化，由中心向边缘沿外螺旋方式生
长。其基本思想是通过任意一点开始，获得一个初始三角形，以 初始三角形
的边界边作为扩展边，搜索扩展边的最佳候选点，将最佳候选点与扩展边及
其邻近的 前一些和后一些边界边连接以构成多个新的三角形，同时不断修正
边界，并将扩展边向后推移，直至所有 散乱数据点剖分完毕。
4.4.1候选点的选择标准
可控参数网格前沿生成算法的关键是如何进 行最佳候选点的搜寻。候选
点的最佳与否，直接关系到网格的拓扑关系是否正确，以及网格划分是否合< br>-28-

哈尔滨工业大学工学硕士学位论文
理。本文在深入研究已有网格 前沿生成算法的基础上，归纳总结出了以下候
选点的选择标准：
(1)候选点必须满足的基本标 准：
①搜索范围标准：候选点必须是位于在包围盒子内的点。且最好应该是
在扩展边的两个端点 的26个包围盒中的公共包围盒内。
②空间三角面不相交标准：候选点与扩展边所构成的三角形不能穿越 已
有的三角形，且一条边最多属于2个相邻三角形，不能出现交叉。此标准适
用于曲面曲率变化 比较小的情况。
③空间三角面夹角标准：空间中任意两个三角面之间的夹角必须大于给
定的阈值 min(一般取10
0
≤min≤15
0
)，这主要是为了避免顶点共线、共 面以
及曲率匹配的问题；相邻的三角面之间的夹角必须小于给定的阈值max(一
般取0≤ma x≤90
0
)，这主要是尽可能保证三角面光滑，无尖锐夹角变化。
(2)候选点的可 选标准：
①逆时针标准：对于空间三角形∆
PPP
，仅当∆
PPP
的 法线方向在Z轴
012012
的投影大于零时，即∆(
P
,
P
,
P
)>0时，
P
、
P
、
P
才按逆时针 排列。其中
012012
∆(
P
,
P
,
P
)
如公式(4-2)所示。若所有三角形按逆时针排列，可以避免重复查
012
找，提 高扩展速度。
x
∆(
P
,
P
,
P
)=y
012
0
0
x
y
z
1
1
x
y
z
2
2
(4-2)
z
012
②候选点到 扩展边的距离标准：候选点与待扩展边的距离满足点到边的
距离阈值的限制，一种阈值选择是候选点距离 扩展边最近，等价于候选点与
扩展边2个端点构成的2条边的张角最大(或次大)。这样能保证搜寻的候 选点
是最优的。
③三角形标准：候选点与扩展边构成的三角形接近正三角形，这要能获
得较高的网格质量，但此时并不一定满足上一个标准。
在本文所提出的可控参数网格前沿生成算法中，我 们主要采用了以下候
选点选择标准：逆时针判断、最长边长度阈值、最小内角阈值、相邻三角面
-29-

哈尔滨工业大学工学硕士学位论文
夹角阈值、新生边长度和阈值等可选 参数，可以根据需要选择其中的若干个
参数进行网格生成。
4.4.2局部网格优化准则
在对散乱点云进行三角剖分时，为了生成接近最优Delaunay三角网格的
目标网格，往往需要采 用一些优化准则对三角网格进行优化，其目标是尽量
避免三角形出现太尖的情况，以提高逼近精度。目前 ，空间散乱点云的直接
三角剖分主要采用以下几个准则：
(1)局部lawson优化准则：L awson根据平面Delaunay三角形最小内角最
大化的原则，提出了经典的局部优化算法LOP (LocalOptimization
Procedure)，又称为lawson优化准则，其基本 思想是：在相邻三角形构成的
凸四边形中，通过交换四边形的对角线，保留短的那条对角线，可使三角网
中所有三角形的最小内角最大化。
(2)内点删除准则：在三角剖分过程中，为了避免出现交叉 重叠现
象，规定每一条边的使用次数不能超过2此，即每一条扩展边最多只能被两
个三角形所共 用。如果一个点的所有邻接边的使用次数都为2次，即是内
点，那就不能再进行三角形扩展，而应将其删 除。
在本文的可控参数网格前沿生成算法中，我们同时采用了局部lawson优
化准则和内点 删除准则进行对生成的局部网格进行优化处理。
4.4.3数据结构及算法实现
可控参数网格前 沿生成算法所采用的数据结构如下：
structPoint
{
intindex;点 的索引
doublex,y,z;点的空间坐标
intnum;记录边的使用次数为2次的边的 个数
boolused;点是不是内点
-30-

哈尔滨工业大学工学硕 士学位论文
vectork;邻接点表
listel;邻接 边链表
}
structEdge
{
ints;
inte;
边 的起点
边的终点
intnum;边的使用次数
boolused;边是否是死边
}；
structTriangle
{
ints;三角形的起始点，逆时针存储inte;三角形的中间点
intt;三角形的尾部点
}
本算法主要是针对封闭曲 面上的散乱点云进行角剖分，为此我们分别建
立了点链表listpl，点的邻接边链表 listel、三角形链表
listtl、边界边链表listbl、边界环链表list>cl。
可控参数网格前沿法的主要步骤如 下：
(1)数据预处理。用包围盒算法建立散乱数点云的K邻近点集，为后续
最佳候选点的搜索 提供搜索空间。
(2)生成初始三角形。具体算法过程如下：从点链表pl中任意选取一点
P< br>1
，搜索距
P
1
最近的点
P
2
，连接生成待 扩展边
PP
12
，然后搜索到
P
1
、
P
2
的距
离和最短的点
P
3
，与
P
1
、
P
2
连接生成待扩展边
P
2
P
3
、
P< br>3
P
1
，最后将点
P
1
、
P
2、
P
3
沿逆时针连接构成一个三角形，记为
∆
PP
12
P
3
，此即为初始三角形
tri
0
。将点链表pl中点P
1
、
P
2
、
P
3
的used的初始 值置为TRUE，用以标记它们
已是处理过的点；将边∆
PP
12
P
3
的三条边依次插入点链表pl中点
P
1
、
P
2
、
P
3
的
邻接边链表el中、边界边链表bl中、三角形链表tl中，并记bl 中的边所构成的
-31-

哈尔滨工业大学工学硕士学位论文
边界环为< br>b
0
，初始化
b
0
的边界边数量num=3；将
b< br>0
插入边界环链表cl中。
(3)三角网格扩展。具体算法过程如下：
①判断边 界环链表cl是否为空，是，则算法结束；否，则判断边界边链
表cl中是否只有一个边界环且所有边界 点的num=2，是，则转④；否，则判
断在最近N(一般去N>5)轮搜索中，是否不断有三角形加入 ，但没有新点加
入(病态情况)，是，则算法病态结束；否，则从边界环链表cl中取出一个未
处理的边界环
b
0
。若
b
0
的边界边的数量num=3，则 由此三边直接生成一个
三角形，否则若num=4，连接四边形的对角线生成两个三角形，此时边界环
b
0
封闭，需要清空
b
0
的边界边链表bl，否则， 执行下一步。
②从边界边链表bl中取一条扩展边extEdge，从点链表pl中extEdge两端
点的邻接边链表el内取一个未处理的点P。判断P是否为extEdge的最佳候选
点P，若 是，则将其与extEdge的两个端点分别连接生成2条新边和一个三角
形，从边界边链表bl中删除 extEdge，并将其中一条新边插入extEdge所在位
置，同时标记点P及三角形的内部点为已 处理。判断点P是否为扩展边
extEdge的上一条边preEdge1的最佳候选点，若是，则连接 生成三角形，接
着判断P是否为preEdge1的上一条边preEdge2的最佳候选点，重复本步 骤；
若不是，则判断P是否为扩展边extEdge的下一条边的nxtEdge1的最佳候选
点，若是，则连接生成三角形，接着判断点P是否为nxtEdge1的下一条边的
nxtEdge2的 最佳候选点，重复本步骤；若不是则执行下一步。
③依次判断点P是否为边界边链表bl中与extEd ge、preEdege1、
nextEdge1不相邻的边界边的最佳候选点。若是，则连接生成三角 形，此时
边界环
b
0
被新生成的三角形分隔成两个边界环
b
1
、
b
2
，可以用
b
1
代替
b
0
，将
b
2
放入边界环链表的末尾，转①；若不是，并且extEdge不是边 界边链表bl
的尾结点，则取边界边链表bl中extEdge的下一条邻接边，转②，否则若
extEdge已到达边界边链表bl的尾部，则转①。
④此为边界环封闭的情况，处理过程如下：若< br>b
0
的边界边的数量num
=3，则由此三边直接生成一个三角形，否则若nu m=4，连接四边形的对角
线生成两个三角形，此时边界环
b
0
封闭，需要清 空
b
0
的边界边链表bl，否
-32-

哈尔滨工业大 学工学硕士学位论文
则，判断边界环
b
0
中某条边界边搜索的最佳候选点P是 否处于该边界环上所
有边界边的包围盒中，若是，则直接连接点P与边界环
b
0
中的所点；若否，
则搜索边界环
b
0
中相互最为接近的边界点P和不以该点 为端点的边界边
extEdge，连接点P和extEdge的两个端点生成2个新三角形，将边界环< br>b
0
分裂
成两个边界环
b
1
和
b
2
，再分别在环
b
1
和
b
2
的最狭窄处进行分裂，重 复上述过
程，直至所有边界环的边界边数位num=3为止。然后将所有边界环的三条边
界边连 接形成一个三角形，加入三角形链表。边界环的封闭处理过程如图4-
2所示，其中红线表示边界环上的 边界边，蓝线表示新生成的边。


P11


P12


P13
P4


P14



P15



P16
P1
b0
P5
P7


P10
P6


P9


P11


P12
b0


P13
P4


P14



P15



P16
P1
P5
P7


P10
P6


P9
P8
P3


P2
P8
P3


P2


P0
b0
P


P0
b0
P
(a)封闭前
图4-2边界环封闭
(b)封闭后
Figure4-2Closeofboundarycircle
初始三角网格生成和网格扩 展的流程图如图4-3，4-4所示：
-33-

哈尔滨工业大学工学硕士学位论 文
开始
从点链表中取一点
P
0
搜索距离
P
0
最近的点
P
1
连接生成一条扩展边
P
0
P
1搜索与
P
0
P
1
的两端点距离之
和最小的点
P
2
否
∆(
P
0
,
P
1
,
P
2
)>0
？
是
生成初始三角形
∆
P
0< br>P
2
P
1
生成初始三角形
∆
P
0
P
1
P
2
结束
图4-3初始三角形生成流程图
Figure4 -3Diagramofconstructionofthefirsttriangle
-34-< /p>

哈尔滨工业大学工学硕士学位论文
开始
取边界环链表中一条边界环
取边界环中一条扩展边
搜索扩展边的最佳候选点P
P是前面的边
的最佳候选点？否
P是后面的边
的最佳候选点？
否
生成三角形并更
新相关链表< br>P与扩展边及
上下边相邻？
否
否
扩展边是边
界环的尾边？是
否
边界环上的所
有边都是死边？
是
边界环封闭处理
否
边界环链表为空？
是
结束
是
是
是
边界环分裂，更新 相
关链表
图4-4三角网格扩展流程图
Figure4-4Diagramofmes htriangulation
-35-

哈尔滨工业大学工学硕士学位论文4.4.4最佳候选点搜索
最佳候选点搜索的搜索过程如下：判断扩展边是否是内边，若是则将其< br>从边界边链表bl中删除，若不是，则遍历扩展边两个端点的el，搜索其最佳
候选点。若最佳候 选点存在，则记录最佳候选点的索引值，同时将新生成的
三角形加入tl，更新扩展边的两个顶点及最佳 候选点的el。按逆时针方向依
次遍历新生成的三角形三个端点的边表判断它们是否是内点，若为内点则 将
其从点链表中删除。若没有搜索到最佳候选点，则把扩展边标记为死边，沿
边界边继续下一条 待扩展边的最佳候选点搜索。最佳候选点搜索可能出现不
同的情况，具体如下：
(1)生成2条 边。此时有两种情况：①最佳候选点是外点。此时会产生
2条新边，在bl中把前一条插入到扩展边的后 面，后一条插入到前一条的后
面，删除扩展边。把新得到的三角形加到tl中。同时应把当前搜索边标记
为死边，在下一轮搜索时直接跳过。②边界环分裂。在边界环扩展过程
中，当扩展边与当前边界 环的边界区域相遇时，即最佳候选点是位于当前边
界环的一点，此时可能会发生边界环分裂，一个边界环 分裂成两个边界环。
此时产生2条新边，这两条新边把边界环就会一分为二。此时，应将新边加
入到bl中，更新cl。边界环的分裂过程如下：依次判断点P是否为边界环中
与extEdge、pr eEdge1、nxtEdge1不相邻的边界边extEdgei的最佳候选点,并记
extEdge i的上一边为preEdgei1、下一边nxtEdgei1。若是，则生成2条新边，
新边newE dgei、新的extEdgei,将其插入bl,同时生成一个三角形
T
i
,将原边 界
环
b
0
分裂成两个边界环
b
1
和
b2
，更新cl，用
b
1
代替
b
0
，将
b
2
放入bl的末尾。
如图4-5所示。③边界环合并。在边界环扩展过程中，如果两 个不同的边界
环相遇时，则会发生边界环合并。合并过程，除了考察对象是其他边界环中
的边界 边、结果是生成的三角形
T
j
将边界环
b
0
和某个边界环< br>b
i
连接起来生成
一个新的边界环
b
0
外。如图4- 6所示。
(2)生成1条边。在边界环有凹陷时，可能会出现以下情况：最佳候选
点是当前边界 环上与其直接相邻的上一点或下一点。此时会产生1条新边。
-36-

哈尔滨工 业大学工学硕士学位论文
如图4-7，4-8所示。产生1条新边时，在bl中把新边加到扩展边的后面 ，把扩
展边和扩展边的上一条边删掉。在pl中删掉内点。在tl末尾加入新三角形。
(3)生 成0条边。此时最佳候选点不存在，需标记扩展边死边，继续bl中
下一条扩展边的最佳候选点搜索。< br>

P11


P12
b0


P10
P6
P5
P7


P9


P11


P12
b0


P10
P6
P5
b2
P7


P9


P13

P4

P14


P3
P15



P16

P1 P2


extEdge


P0
P8


P3
P15



P16

P1 P2


extEdge


P0


P13
P4


P14
P8
(a)分裂
图4-5分裂过程
Figure4-5Processofsplit


P11


P12
b0


P10
P6
P5
P7


P9



P11

P12
b0


P13
P4


P14


P15
(b)结果


P10
P6
P5
P7


P9


P13
P4


P14


P15




P16
P1


extEdge


P0


P2
P8
P3
P8
P3


P2




P16
P1
b1
P


P0
b0
P
(a)合并
图4-6合并过程
(b)结果
Figure4-6Processofcombination
-37-

哈 尔滨工业大学工学硕士学位论文


b0

extEdge

P13
P4


P14


P15



P11

P12


P10

P6

P9
P7


P11


P10

P6

P9
P7
P5
b0


P13
P4


P14


P15
P5
P8
P3


P2
P8
P3


P2




P16
P1




P16
P1


P0


P0
(a)最佳候选点为上一点(b)上一点扩展结果
图4-7最佳候选点是与扩展边直接相邻的边界环上的点
Figure4-7Thebestcandi catepointistheadjacentpointofextendableedge



P11

P12
b0


P10

P6

P9
P7



P11

P12
b0


P10

P6

P9
P7



P13

P4
extEdge


P14


P15




P16
P1


P0
P5


P13
P5
P4
P8
P3


P2


P15




P16
P1


P0
P8
P3


P2
(a)最佳候选点为下一点(b)下一点扩展结果
图4-8最佳候选点是与扩展边直接相邻 的边界环上的点
Figure4-8Thebestcandicatepointistheadja centpointofextendableedge
最佳候选点的搜索流程图如图4-9所示：-38-

哈尔滨工业大学工学硕士学位论文
开始
从边界边链表中取
一条边
P
1
P
2
是
P
1
P
2
为内边？
从边界边链表中
删除
P
1
P
2
否
是
P
1
P
2
为死边？
否
从
P
1
、
P
2
的邻接点链表
中取一未处理点
P
c
标记
P
c
为已处理点
否
P
c
是
P
1
P
2
的
最佳候选点？
是
P
c
是外点？
是
否
P
c
与
P
1
、
P< br>2
是
生成2条新边
生成1条新边
直接相邻？
否
生成2 条新边，边界环
分裂
生成一个三角形
∆
P
1
P
c< br>P
2
，局部lawson优化
P
1
、
P
2< br>、
P
c
更新
的点链表及相关链表
P
1
的所有 邻接
是
边是否均为内边？
否
同理处理
P
2
、
P
c
从点链表中删除
内点
P
1
结束
图4-9最佳 候选点搜索流程图
Figure4-9Diagramofthebestcandidatepoin tsearching
-39-

哈尔滨工业大学工学硕士学位论文
4. 4.5实验结果及性能分析
在前面简化后的得到的点云模型的基础上，采用可控参数网格前沿生成
法对物体进行了三角网格化。图4-10和4-11给出了网格化后的运行结果。
(a)未简化时的手 骨网格(b)局部放大模型
(c)简化后的手骨网格正视图(d)局部放大模型
(e)简化后的 手骨网格侧视图(f)局部放大模型
图4-10手骨的网格模型
Figure4-10Mesh modelofhand
-40-

哈尔滨工业大学工学硕士学位论文
( a)未简化时的龙网格(b)局部放大模型
(c)简化后的龙网格正视图(d)局部放大模型
( e)简化后的龙网格侧视图
图4-11龙的网格模型
(f)局部放大模型
Figure 4-11Meshmodelofdragon
不同实验的对比结果如表4-1，4-2所示：
-41-