（计算机应用技术专业论文）由散乱点生成三角网格曲面的算法研究与实现.pdf

摘要 摘要 随着计算机辅助设计岛图形学的发展，几何造型技术农许多领域褥到丁广泛的研究 和应用，其中基予散乱点数据的曲灏重建技术是其中一个很藿要的内容。该技术可以应 用于医学成像数撂躲可视化、有限惩分析等诸多方掰。 本文藏要在基于散乱点的三维曲面重建算法、曲面有限元网格自动生成工具系统的 设诗帮实琥等方霞遴行了戮突程掭讨。 对予根据散乱点重建网格曲面的问题，本文采用分全局麓建和局部修正两步走的方 法。全羼黧建采焉筵子c c i c o n e 方法的算法，并秀了稔溺迭器藤对藏方法透露了改逶。通 谶全局重建后得到的网格基本反映了待重建曲面的拓扑信息。但由于采样的原因，此网 椿的某些蟪方存在奇异点，不满足二维流形的要求，需要进行自动的修正。本文采瘸切 平面作为曲面的局部近似，将局郝的采样点投影到切平强上，弗对投影点集作二维 d e i a u n a y 三角音0 分，最后穰据投影点上的邻接关系确定三缎点之间的连接关系。具体的 局部算法毽括局部过滤、熨部重建_ 秘环髟送域填蛰，宅 | 、】分燃锺在苓露熬馕毽下怼潮格 进行修正。通过局部算法的修正，辣法的鲁棒性增强了。为了能够有效的处理海量数据， 我嚣】角努瓣霉会劳瓣愚想慰述舅法进霉了浚逶，减，l 、了冀法豹辩阏复杂度蠲空闺笈杂 度。 根据散乱点爨和点集掰在的益瑟重建嚼格鳆面也是实酸中常见的问题。本文以上谱 的算法为綦础，充分利用曲蕊这个煎耍的已知条件，提出了对这个闽题的一个解决方法。 最后本文将上述两类随题的处瓒算法缀合至我们的系统中，实现了可以处理多种输 入数据的热嚣有殴惩自动生成系统。 关键谪：魏西重建，二维流形，d e l a l 琏垮三角吝分，c 算法 j 索工业大学工学硕士学证论文 a 蕊l r a c 重 1 1 1 n l i s 吐1 e s i s ，m es l l r f 犯e ”e c o n s 呻c t i o nf o ru n o 培a l l i z e dp o 礁s ，a n dt kd e 娅a 畦 妇p l e m e n t a t i o no f t h 。s y s t e m f o r c o n s 蜘l c 蜒t h e 盘娃t ee l e m e 嫩l 批s k d 糠n g f e c o 掰鼬e 圭主。蛀至ti sd i 摄e 堪t og 畦氇e p m 秘ft o p o l o g 主c 越c o n n e c t i o n s 矗m o n gp o 汝耄s 遮氇e 玉攮s c 专j u s ta c c o 磁赫g t ot 圭l e 氇他e d i 稍傩s i o n a lc o c 枉瞳n a t e so f t 酶p o i n t s h t h i s 也e s i s ，w e s 缸ys o m em a 王n s t r e 糊s u r f 矗c er e c o l l s 缸1 】c t i o n 撕g o r i t l l m sf 醅u n o 唱枷z e dd a t as e ta n da d o p t m e a l g o d t h r n sb a s e do n d e l a u n a y h a n g l l l a t 溉f i r s tw eg e ta m e s h 舶m m e d a 协s e t b y t h e 曲p m v e dc o c o n e 赳g 耐t h i l l h l 曲em e s h t h el o c a lg e o m “c 锄d t o p o l o 西c a lp r o p c r c yc a nb e c l e a r l yd e 刚b e d 诫t h 越a d j 躲m tp o i n t sf o rag 沁e np o 随n e n t h ed e l a u n a yt r i 鼬则a 畦o n t e c 1 1 1 i q u em 柳o s i o n s i sl l s e dt od e l 啦张dm o d i 玲t h ei l l e 酬证a 芏l 醛e s 强搬ef e s u l 蛀n g m e s h f 妇l l y w e 诹l l g e t a2 一文趣e n s i 供堪凇畦勤撼m 鼬 堍酾基腿啪溉w e l l 妇删e s w 魏a r b i 秘a 翠姆弦l o g ya 越c 鲢t o 融矧嚣氇e 淄婶l i n gn o i s e 甜s o “l e 如g f e e 赫a d d i t i o n ， 溺瑚出矗e sc 矗l lb e 曲0 c c 诧da u 幻m 娟c a l l yd u 抽gr e c o n s 撖1 蕊o n 1 no r d e rt od i s p o s em e l a 娼ed a t a ，、wu s e 伽ed i v i d 船a r l dc o r l q u e rm e m o d t oi m p r o v et 1 1 e a l g o r i m m m e m i o n e da _ b o v e 1 1 1p r a c t i c en 艟s l 成a c o 廿i a i l g u l a t i o nw 酏西v e n p o i n t s s e to nt h es 删雠ei sa 加n i l i a ri s s u e ht h i sm e s i s 、v eb r i n gf on = 忸r dam e 吐1 0 df o rm ei s s u ek i s e do n 也ea l g o 蛀m mmm et l e s i s a tl a s tw ed e s i g n 鞋s y s t e mf o rc o n s 奴l e 蛀n g 也ef i n i t ee l e m e 难m e 照b a s e do n 爆e a l 鲥也m s 爨e 螺涮曲o 、蟹，w 嫩e h e a n d 廷p o s e 糙撼y 垃砖so f 主主l p 挂t 玉t a k e y w o r d s ：s u 娃孔er e c o 璐t 垃帆2 咖s i o i l a l m a m f o l d ，d e l 辄m a y 州a 1 1 9 u l a t i o n ，c o c o n e 舢g o f i t h n l l 第1 章绪论 第1 章绪论 1 1 课题背景 本课题是北京市教委项目曲面有限元网格自动生成系统中的一部分。有限 元网格自动生成问题在有限元分析、计算机辅助设计、科学计算可视化及计算机图 形学等众多领域中具有重要研究意义，并随着信息及网络技术的不断发展，也在日 益广泛的工程技术领域中发挥作用。 有限元网格在应用领域上的延伸为网格自动生成问题提供了新的、更大的研究 空间，同时也对网格生成工具在独立、通用等方面提出新的要求。根据应用实践， 该系统应提供多种条件下的网格曲面生成功能。其中根据未知曲面上网格顶点集合 来重建网格曲面便是本课题的主要研究内容，这也是一个根据散乱点集合进行网格 曲面重建的过程。 1 2 问题的提出 图l l 曲面重示意图 图1 1 是表示网格曲面重建的示意图，图1 1 ( a ) 表示的是初始曲面，图1 1 ( b ) 表 示的是从图1 1 ( a ) 中所示的曲面上采样得到的散乱点，图1 1 ( c ) 表示从采样点重建出 的曲面。从图1 1 ( b ) 到( c ) 所示的过程，就是本文所讨论的问题。 随着计算机图形显示对于真实性、实时性和交互性要求的日益增强，几何设计 对象体现出向着多样性、特殊性和拓扑结构复杂性靠拢的明显趋势，与此同时图形 工业和制造工业向着一体化、集成化和网络化快速迈进，激光测距扫描等三维数据 采样技术和硬件设备日臻完善，曲面造型近几年得到了长足的发展。 北京工业大学工学硕士学位论文 从目前的研究趋势来看，曲面造型技术己从传统的研究曲面表示、曲面求交和 曲面拼接，扩充到曲面变形、曲面重建、曲面简化等。 从曲面上的部分采样信息来恢复原始曲面的几何模型，称为曲面重建( 如图 1 1 所示) 。当然，仅利用曲面上有限个采样点的三维坐标信息的曲面重建并不能完 全恢复原来的未知曲面，但生成的曲面与原曲面有同样的拓扑结构，并且生成的曲 面在每一处都和原曲面尽量接近。通过这种方式，就可以把现实世界中已有的物体， 转变成计算机中的模型，从而进一步对这些对象进行编辑等操作。 1 3 应用领域 曲面重建在科学研究和工程上都有很多的应用领域，其中包括三维扫描、边缘 数据的曲面重建等。下面几个章节将对此作介绍。 1 3 1 三维扫描 曲面重建的最重要的应用之一就是三维扫描，目的在于恢复模型的形状和其他 可视特征。在工业上，可以用机械探头测得物体表面的点的坐标位置，如汽车车身 或飞机机翼等，但这需要人工的干预。三维激光扫描仪可以用激光束照射到物体表 面，利用三角化、干涉或时间差来计算物体表面点的距离信息，这样得到的数据点 比较密集、精确，是一种得到数据点的好方法。三维扫描应用的领域十分广泛，可 包括如下方面： 文物的数字化：数字化博物馆使人们通过计算机等设备在一个虚拟的环境中花 费较低的费用完成对博物馆的参观，而且还能在一定程度上起到文物保护的作用。 为了尽可能真实的再现这些文物，我们需要用三维扫描技术将文物的三维信息( 几何 信息、纹理信息) 精确的采集下来，再利用三维重建技术根据这些信息将文物的三维 模型在计算机内建立起来。利用这些模型我们便可以从任何角度真实的将文物绘制 在计算机中。 利用通过三维扫描技术得到的模型还可以实现用计算机控制的对文物进行的清 洁和维护。同手工操作方式相比较，用这种方式对文物本身的破坏程度要小的多。 米开朗基罗工程就是利用这种技术来对塑像进行的清理工程。 第1 章绪论 逆向工业：计算机辅助设计经常是由实际的模型开始的。工业上有许多传统的 部件不是由c a d 软件设计出来的，甚至没有图纸，为了在计算机中对这些部件进行 合并或修改，需要利用三维模型重建技术。 1 3 2 边缘数据的曲面重建 曲面重建的另一个应用就是边缘数据的处理。在医学研究中，通常可以用c t 技术得到某器官的层状数据，每一层的数据表示器官某一层的轮廓。把这些层状数 据组合在一起就可以看成是表示一个完整器官的散乱点数据集合。在加工制造业中， 也可以通过c a t ( x 射线轴向分层造影扫描机) 扫描机械零件的相交部分而得到这样 的层状数据集合。 类似的情况是，利用超声传感器探测心脏的形状，就是通过将一个探头伸入食 道中，从而得到心脏的边缘数据。与薄片切片机不同，这样的超声得到的边缘数据 不是平行的，而且探头可以生成不同角度不同位置的边缘数据，这样生成的数据要 看它的密度情况来具体处理。 对于这些边缘数据，采用散乱点重建曲面的方式生成曲面表示，可以更有效的 用计算机对这些实体进行研究、分析等。 1 4 相关算法综述 曲面重建算法都是要利用采样点的某些相关信息，例如：曲面的拓扑结构、数 据的结构、曲面的法向的信息等。本文仅讨论散乱点重建曲面的算法，这里的散乱 点是指仅有采样点的三维坐标，而无其他任何附加信息的点。为了描述算法方便， 对各类算法进行分类。 根据结果曲面是否过给定的散乱点集，将算法分为拟合曲面算法和插值曲面算 法。 1 4 1 拟合曲面算法 这类算法不要求结果曲面经过散乱点集，往往利用图形学中常用的造型曲面( 如 等势面、n u r b s 曲面、二次曲面等) 来拟合散乱点集。 北京工业大学工学硕士学位论文 1 4 1 i 零集法 这种方法( 1 】通过定义每个取样点的近似切平面，然后以此为基础定义空间点到 曲面的有向距离函数。再以此有向距离函数作为某场的场函数，这样待重建的曲面 分布在该场的零等势面上，只要抽取出零等势面就得到了待重建的曲面。常用的抽 取等势面的方法有m a r c h i n gc u b e 。算法具体如下： 首先，估计每个采样点附近的近似切平面。算法利用每个点的r 一邻域内的点集 ( r 是采样密度) 来估计每个点附近的切平面。采用的方法是用最小二乘法求出点 集的拟合平面作为切平面的估计。为了定义有向距离函数，必须对切平面执行法向 量一致化操作，使所有的法向量都指向睦面的“外”或“内”。算法先确定一个点 处的法向量的方向，然后根据邻近的点处的法向量的夹角是锐角的假设按照深度遍 历的顺序将此方向传播下去。 确定了切平面后，就可以定义有向距离函数了 2 ( 如图卜2 所示) 。首先， 找到切平面l ( x 。) ，它的中心o 是最靠近p 的，然后用如下定义的，( p ) 作为有向距 离函数。 ，( p ) = ( 始f ，( p ) = ( p d ，) 而 如果待重建的曲面已知无边界，这一简单规则很适用。然而，当曲面有边界时， 用此方法容易产生错误，规则必须扩展以适应有界曲面。规定d ( z ，x ) ( z 和x 之间 的距离) 的取值范围，当超过某一阈值时，就把，( p ) 作为未确定值，用作识别边界 4 。这种识别边界的思想也可以在其他算法中得以利用。 确定了有向距离函数后，以此函数构造一个标量场，从这个场中抽取出零等势 面便得到了待重建的曲面。抽取等势面选取m a r c h i n gc u b e 算法 3 5 ，这是一个将 空间分成立方体再进行抽取的方法。将抽取出的网格进行优化后，便得到了最后的 结果 3 。 零集法非常巧妙的将曲面重建问题转化成了一个抽取等势面的问题，为这个问 题的解决提供了一个非常好的思考方法。在此基础上，后人在细节问题上精心考虑， 使这个方法日臻完善。 4 第l 章绪论 l e i f p k o b b e l t 5 ，6 】等人提出的方法用提高的距离场和扩展的t c h i n gc u b e 代 替零集法中采用的有向距离估计法和m a t c h i n gc u b e ，使算法能够更好的重建棱角、 折痕等细节。 1 4 1 2 用标准曲面拟合数据点的算法 f o l e y 7 综述了从散乱点重构隐函数曲面和参数曲面的有关算法。而p r a t t 8 则直接采用简单形状( 如圆、球、直线、立方体) 来拟合数据点，但这种方法难以重 建复杂拓扑的曲面形状。 1 4 2 生成插值曲面的算法 插值曲面要求用散乱点集来构成曲面，就是把散乱点连成二维流形三角网格。 这也可以看成是一个把散乱点集从“无序”到“有序”的排序过程。通常的“一维” 条件的排序算法中，每个点只有“前趋”、“后继”两个邻接点，而且排序的依据 只有点之间的距离。但是在网格曲面中，每个点有多个邻接点，而且确定邻接关系 不能仅考虑距离因素，还要综合考虑空间位置等其他因素。这样，我们需要一个有 效的分析工具d e l a u n a y 三角剖分 9 ，1 0 ，1 l ，1 2 ，1 3 。 根据使用d e l a u n a y 三角剖分处理点集的范围的不同，把这部分算法分成两类： 全局算法和局部算法。 1 4 _ 2 1 全局算法 全局算法首先对散乱点集做全局的三维d e l a u n a y 三角剖分，对散乱点集进行的 初次的排序。理论上认为，在面f 上进行足够密度的采样，对采样点集进行d e l a u n a y 三角划分后，这时待重建的曲面应该蕴含在三角剖分的结果中。三角剖分中属于待 重建曲面的连接是正确的连接，其余的连接是错误的连接。算法的关键是如何过滤 错误连接，将曲面抽取出来。目前比较有代表性的算法有以下几种。 ( 1 ) 。s h a p e 法 e d e l s b n l n n e r 【1 4 1 提出了口- s h a p e 的概念，口一s l l a p e 方法删除了散乱点集的 d e l a u n a v 三角剖分中其外接球或外接圆半径大于口的四面体、三角形和边，然后利 用“最大点乘法”或“最小二面角法”通过抽取外部面来得到重建睦面。 b a j a j 【1 5 ，1 6 利用口s h 印e 将散乱点所在的空间区域分割成四面体，并用此生成 了c 1 连续的散乱数据点的插值曲面。 北京工业大学工学硕士学位论文 口一s h 印e 方法的关键是找到合适的口值。对于均匀一致的数据点集口s t l a p e 方 法很有效，但由于数据点集的不均匀性或表面的某种不连续性，有时很难自动选择 合适的口值，以保留需要的三角化元素，删除不需要的所有元素。 ( 2 ) c r u s t 法 c m s t 方法使用中介面来删除d d a u l l e y 三角剖分中错误的连接 17 】。其中中介面 的计算是用点集的v o r o n o i 顶点来模拟的。算法的主要过程是先对散乱点集进行 d e l 舢1 c y 三角剖分，并计算散乱点集的v o r o n o i 顶点，形成v 点集，与原取样点合 并。再对合并后的点集进行d e l a l l n e y 三角划分，取原取样点生成的三角形，作为所 得到的三角网格，再用v o r o n o i 点进行过滤，除去不符合标准的网格，最后得到要 求的网格。 此算法给出了理论上的证明 1 8 。如果有“好的取样”，就能够保证所生成的网 格正确的反映了原曲面的拓扑，当取样点密度增加时，就能够保证生成原曲面。“好 的取样”，从直观上来讲，就是在曲率大的地方取样密集，曲率小的地方取样稀疏。 ( 3 ) c o c o n e 算法 c o c o n e 算法是利用d e l a u n e y 三角剖分后的三角形对应的v o r o n o i 边来进行三 角形过滤的 1 9 。过滤算法是基于下面的一个必要条件： 一个d d 锄m a y 三角形应该被保留下来的必要条件是此三角形所对应的v o r o n o i 边同曲面s 有交点。 然而，由于曲面s 是未知的，所以v o 舢i 边与曲面s 求交的过程无法用程序 实现，这样只能用近似的形式来代替。算法中采用了一种叫c o c o n e 结构作为局部的 近似。并且当采样满足算法假设的条件时，使用这种近似形式不会将正确的三角形 过滤掉。 c o c o n e 算法还从理论给检测边界点提出了新的方法 2 0 ，2 1 。c o c o n e 算法只需执 行一次d d a ：i 1 a y 三角剖分，而且还适合于用d i v i d ea n dc o n q 懈方法加以改进以处 理海量数据 2 2 】。 此算法也从理论上给出了详细的证明 1 9 ，算法对采样密度有同c r u s t 算法相 同的要求 1 7 。但是对采样的要求非常严格，在处理实际数据时难以得到正确的结 果 1 9 。 第1 章绪论 14 2 2 局部算法 这类算法往往基于这样一个采样假设：给定一个点，其邻近点集可以反映出该 点附近的局部拓扑和几何信息。局部算法通常先用简单的判断条件( 例如k 一近邻 2 3 ) 来初步确定每个点附近的邻接点集合，然后估计每个点处的切平面，采用深 度数据的思想将其邻接点集合投影到切平面上，再用二维d e l a u n e y 三角剖分来进一 步确定此点与周围的点的邻接关系。 m g o p i y 提出了一个基于局部二维d e l a 眦y 三角剖分的算法【2 4 】o 算法首先利用 k 一近邻的技术得到每个点的邻域并根据邻域估计每个点附近的切平面。再把邻域内 的点投影到切平面上并对投影点作二维d e l 咖a y 三角剖分。根据三角剖分后的结果 得到每个采样点可能的邻接点信息。然后根据这些点之间的邻接信息构造一个初始 网格，这个网格很可能不是二维流形。然后需要再对这个网格进行修改。这种方法 很容易设计成并行程序。 王青提出了一个进行曲面重建的快速增量算法 2 5 。此算法也是用局部的二维 d e l a u n a y 三角剖分来确定点的邻接三角形。与上面的算法不同的是此算法在为点确 定邻域时要受到当前生成的网格的约束。此算法先选择一个采样点，并用上面的方 法得到此点的局部的网格，以此网格为初始网格，并不断将边界点的局部网格合并 入当前网格，其中邻近点的选择和局部网格的并入过程都要受到当前网格的约束， 即要保证并入此局部网格后得到的新网格仍满足二维流形的要求。直到当前网格中 的边界点都被访问过。这样重建完后的网格满足二维流形的要求。 1 4 3 算法比较 将以上算法相比较，拟合曲面算法的结果曲面不经过采样点，在有的部位会产 生形变，不满足要求；插值曲面算法中的全局算法对采样质量的要求比较高，在实 际应用中难以单独使用；局部算法不能全面的考虑问题，生成的网格不能全局最优， 但是这类算法的鲁棒性比较高。 1 5 本文主要研究内容 本文中讨论的散乱采样点满足如下的要求： 1 ) 采样点只有三维坐标信息，而没有法向量等其他几何信息； 北京工业大学工学硕士学位论文 2 ) 采样点是无序的，彼此没有任何相关信息： 3 ) 采样点的密度是未知的，不知道是均匀采样还是非均匀采样； 4 ) 曲面的拓扑结构是未知的，有可能存在很复杂的拓扑； 5 ) 数据量可能会比较大，需要考虑算法的运行时间： 6 ) 采样的过程中会有误差； 从这样的散乱点生成原曲面是一项难度很大的工作。针对这样的散乱点集，本 文的主要研究内容有： 1 ) 设计一个重建算法，根据散乱点生成一个插值的二维流形网格曲面。要求算 法要有较高的鲁棒性。 2 ) 已知散乱点集和点集所在的曲面来重建网格也是实际应用中常遇到的问题。 本文对上面的重建算法加以改进，提出了对这个问题的一种解决方案。 1 6 本章小结 本章从实际应用中引出了本文所要研究的课题，并从其在其他领域的应用论述 此研究课题的实际意义。然后引用国内外文献说明此领域目前的研究进展及成果。 并从其存在的不足和待深入研究的问题中引出本文的主要研究内容。 第2 章系统的建立及体系结构 第2 章系统的建立及体系结构 本项目旨在开发针对曲面的有限元网格自动生成系统。根据应用实践，该系统 要实现如下三类条件下的曲面网格生成功能： 1 ) 已知曲面上网格顶点集合时的网格自动生成。 用户仅以曲面上的一个点集定义曲面，系统须从顶点集合提取皓面定义信息以 确定顶点间的拓扑关系。从理论上讲这是一个根据散乱点重建曲面的问题。 2 ) 针对大数据量的数据的网格自动生成算法。 3 ) 已知曲面及网格顶点集合时的网格自动生成。 以用户指定的待剖分曲面及曲面上的网格顶点集合作为输入条件，系统根据曲 面中蕴含的性质生成以指定点集为顶点的曲面的有限元网格。该条件下的网格生成 算法与曲面类型无关。 这三种输入条件总起来说都是从散乱点构造网格曲面。相比较而言，后面两个 问题是从第一个问题派生出来的，也就是说第一个问题更加基本一些，因而它的解 决方法会对后面两个问题的解决提供新的思路，所以本文主要讨论仅根据散乱点重 建曲面的算法。 2 1 关于采样条件的假设 没有任何一种重建算法能够处理任何条件的数据。重建算法都是基于一定的采 样条件之上的，有的甚至把采样条件作为构造方法中的输入参数。例如零集法要求 采样为均匀采样 4 ，并把采样密度和采样误差限作为求得每个点的邻域的参数。而 c r u s t 算法要求局部的采样密度同局部的特征大小成正比，直观上来看就是曲率大的 地方采样应该密集，曲率小的地方采样应该稀疏。这是一种比较合理的采样密度的 要求方法 1 7 。 本文算法吸取上述算法中对采样的合理要求并与实际应用相结合，对采样提出 下面的假设要求： 1 ) 存在一个流形表面插值或拟合这些采样点。 2 ) 采样密度基本满足c r l l s t 算法的要求。 北京工业大学工学硕士学位论文 3 ) 允许存在一定程度的采样误差。 基于这个假设条件之上，我们分析了多种曲面重建方法，吸取它们处理某些问 题的长处，提出了本文的重建方法。 2 2 系统采用的算法概述 本系统主要处理三种类型的数据。这一节将对这三类数据的处理方法进行概述。 由于第一类问题的处理方法更基本一些，所以主要说明第一类问题的处理方法。 2 2 1 针对散乱点重建网格曲面算法 上一章列举了一些算法，这些不同的算法用不同的观点来看待睦面重建问题， 因而形成了不同的处理方法。在本文中，将曲面重建的过程看成是一个把散乱点从 “无序”状态变成“有序”状态的排序过程。 通常的排序过程都经历一个由“粗”到“细”的过程，我们的算法也是如此： 1 )先对散乱点做三维的d e l a u n a y 三角剖分。 d e l a u n a y 三角剖分是对散乱点集的凸壳进行的三角剖分。在第三章将对此作详 细介绍。通过剖分，某些点之间具有了连接关系，也就是有了初步的“顺序” 关系。但这里面存在大量的错误的连接，需要通过后面的操作将其过滤掉。 2 )用全局方法进行过滤操作 在第一步的基础上，我们采用全局算法来对d e l a u n a y 三角剖分后得到的 三角形进行过滤。这些过滤的依据是算法本身对采样条件提出的合理假设，主 要是采样密度的假设。根据假设条件推演出过滤条件，利用这些条件进行过滤。 在此基础之上为了检测边界而添加了新的过滤条件。这些内容将在第四章中进 行介绍。 全局方法要求任何位置的采样都要满足算法的假设。但在实际采样结果 中，由于采样误差等隋况的存在，这一点往往很难保证。这样在这些地方仅用 全局过滤方法难以得到正确的网格，需要用局部处理方法对网格进行进一步的 处理。 3 )用局部方法对网格进行处理。 1 0 第2 章系统的建立及体系结构 根据局部算法鲁棒性比较高的特点，采用这类算法的思想对网格进行进一步修 改。本文中对网格的修改是针对采样点展开的。这里把其局部的网格不满足二维流 形要求的点叫做奇异点。然后针对产生奇异点的因素不同，分别采用局部过滤、局 部重建的方法对网格进行修改。修改的过程中都要对出现的环形区域进行填补，最 终得到一个二维流形的网格。这部分内容将在第五章中详细说明。 2 2 2 针对海量数据的处理算法 当问题的规模非常庞大时，仅用上面的算法受时间和空间条件的约束难以在实 际中得到应用，为此采用先分组再合并的思想对上面的算法进行改进。但是算法的 核心仍然来自于上面的算法。这部分内容在第六章中说明。 2 2 3 针对散乱点和其所在的曲面构造网格 用上面的算法对散乱点进行三维重建时由于曲面是未知的，因而只能用c o c o n e 结构作为曲面的局部近似来进行处理。而在这个问题里曲面的表达形式是己知的， 因而将这个重要的条件在算法中加以利用便得到了本文对这个问题的一种解决方 法。 首先作点集的三维d e l a u n a y 三角剖分，然后以曲面为基础用多种方法对三角剖 分中的三角形进行过滤。具体的过滤方法将在第七章中详细说明。 2 3 体系结构 本系统的体系结构如图2 1 所示。此系统结构图简要说明了各个模块之间的关 系，和数据的处理过程。 2 4 本章小结 本章首先从系统需求的角度提出了本文系统所要处理的几类数据，并简要说明 了几类问题之间的关系。 然后正式提出了本文系统对所处理的数据的采样条件所做的假设。在此基础上 分详略概述了系统对各种问题处理方法的技术路线，以及系统的各个模块在后续各 章的分布。最后用图示方式说明了整个系统的体系结构。 北京工业大学工学硕士学位论文 图2 1 系统体系结构图 第3 章三角剖分算法基础 第3 章三角剖分算法基础 三角割分楚本文雾法中确定点与点之闰静透接关系酌一个菲常有用的工其，是 本文算法静理论基础。它蹩计算凡衍中一个j 常重要的概念。三角剖分研究可追溯 到三十年代，并在七十年代后期得到了较大的发展和应用。其中以d e l a u n a y 三角制 分最具代表性，它建优化的三角剖分，简记为d t ( d e i a u i l a yt r i a n g l i l a t i o n ) 。虽然 d t 处理的对象是散乱点的凸包，但是在实际应用中它已拓展到很多其他情况，如三 维曲面的三角剖分问题，也是采用许多d d a u n a y 三角妾4 分的原理。本章主要分绍二 维、三维d e l 叫n a y 三角剖分和二维有界域的d e l a u 舱y 三角划分。首先余绍皿个基 本擐念。 3 1 三角剖分的基本概念 不失一般性，这里先绘如n 维空趣三焦裂分熬严格定义。 定义3 - l 三角窘分阚格：绘定n 维空闻中静m 个不阉结点缀成酌煮集p ，其三 角割分r ”怒具有下猁性质的n 个n 维单纯形”的集合，即： 少= f ? ，贮，。r ； 满足： 1 7 1 ”的顶点集为p ； 2 。p 憨凸镪掣：u 剪； 3 若i ：j ，则胛的内部n 的内部；巾； 4 r 的小l 维嚣载在垮的边爨上，或纛戈嚣令单纯形共事。 其中，n 维单纯形是指n 维空间中的n + 1 个点，k ，酩，满足： 构成的黯包。 在本文中，我们照黪是二维平嚣熬三建刹分( 其结巢是三焦形酶集合) 和三维 玑珑圪l 衍矿l 矿矿矿l 。1 3 - # 0 北京工业大学工学硕士学位论文 空间上的三角剖分( 其结果是四面体的集合) 。以下给出二维平面三角剖分的定义。 定义3 - 2 平面三角剖分网格：称三角形集合r = n ，r ：，丁。) 为平面上m 个非共线有限点集p 的三角剖分，当且仅当r 满足以下三个条件： 1 ) r 的顶点集为p 2 ) p 的凸包= u 几 3 ) r 中任两个三角形的交集或者为空集，或者是p 中的点，或者是以r 中两点为 端点的直线段。 从定义3 1 和定义3 2 中不难看出，对于一个给定的点集p ，满足定义的三角 剖分不是唯一的，需要对r 附加确定的优化条件才能得到唯一结果。理想情况下的 三角网格的各个单元应是等边三角形，但这一目标通常是难以企及的，因此通常只 能使三角形的内角尽可能的大。这样网格的各个三角形单元的最小内角便成为衡量 网格质量的一个重要标准：最小内角越大，网格质量就越好。而d e l a u n a y 三角剖分 恰好是满足最小内角最大的最优三角剖分。 3 2 优化的三角剖分技术 1 9 3 4 年，b d e l 眦l a y 证明 2 6 】：必定存在且仅存在一种剖分算法，使得所有三 角形的最小内角最大。这种剖分被命名为d d 锄m a y 三角剖分。5 0 年代，g f v o r o n o i 【2 7 】 及g l d i r i c h l e t 【2 8 】分别提出v 咖i 图及d i r i c m e t 网格。1 9 7 0 年，m n 髓【2 9 在此基 础上建立了较完善的v 咖i 基础理论体系，证明其直线对偶图即是d e l a l m a y 三角 剖分，具体说来，其定义形式是这样的： 定义3 3 平面d e l a u n a y 三角剖分网格：给定二维平面上的结点集合 矿= 慨，k ，踢0 3 ) ，假设这些结点不全共线。若d ( 形，呦表示m 与乃的距离， 嘲= & i d o ，功 ( ( a ，8 ) t ) o r ( q ( b ，c ) t ) 0 r ( a ( a ，c ) t ) 其中t 便是衡量两个点是否排斥的阀值。 4 4 完整的全局处理算法 完整的全局处理方法如图4 6 所示。对散乱点执行完此全局操作之后，