由散乱点生成三角网格曲面的算法研究与实现

《由散乱点生成三角网格曲面的算法研究与实现》由会员上传分享，免费在线阅读，更多相关内容在学术论文-天天文库。

北京工业大学硕士学位论文由散乱点生成三角网格曲面的算法研究与实现姓名：张杰申请学位级别：硕士专业：计算机应用技术指导教师：尹宝才2003.6.1 j￡索工业大学工学硕士学证论文A蕊lrac重111nlis吐1esis，mesllrf犯e”econs呻ctionforuno培allizedpo礁s，andtkde《娅a畦妇plementationofth。systemforcons蜘lc蜒the盘娃teeleme嫩l批skD糠ngfeco掰鼬e圭主。蛀至tisdi摄e堪￡tog畦氇epm秘ftopolog主c越connectionS矗mongpo汝耄s遮氇e玉攮sc专justacco磁赫gtot圭le氇他e—di稍傩sionalcoc枉瞳natesoft酶points．hthis也esis，weS缸《ysomema王nstre糊surf矗cerecolls缸1】ction撕gOritllmsf醅uno唱枷zeddatasetandadoptmealgodthrnsbaSedonDelaunayHanglllat溉Firstwegetamesh舶mmeda协setbythe曲pmvedCocone赳g耐thIll．hl曲emeshthelocalgeom“c锄dtopolo西calpropcrcycanbeclearlyde刚bed诫th越adj躲mtpointsforag沁enpo随．nentheDelaunayTri鼬则a畦ontec}111iquem柳o‰sionsisllsedtodel啦张dmodi玲theille酬证a芏l醛es强搬efesul蛀ngmesh．F妇llywe诹llgeta2一文趣ensi供堪凇畦勤撼m鼬．{＆堍酾基腿啪溉well妇删e{sw魏arbi秘a翠姆弦logya越c鲢to融矧嚣氇e淄婶lingnoise甜so“le如gfee．赫addition，溺瑚出矗esc矗llbe曲0cc诧dau幻m娟callydu抽grecons撖1蕊on．1nordertodiSpoSemela娼edata，、wuse伽edivid船arldcorlquermemodtoimprovet11ealgorimmmemioneda_bove．111practicen艟sl成’aco廿iaIlgulationw酏西venpointsSetonthes删雠eisa加niliarissue．hthismesis、vebringfon=忸rdame吐10dformeisSuekIsedon也ealgo蛀mmmmet}lesis．Atlastwedesign鞋systemforcons奴le蛀ng也efiniteeleme难me照basedon爆eal鲥也ms爨e螺涮曲o、蟹，w嫩eheand廷poSe糙撼y垃砖sof主主lp挂t玉ta．Keywords：su娃孔ereco璐t∽垃帆2咖sioIlalmamfold，Del辄may州a119ulation，Cocone舢gofit}Hnll 第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章绪论逆向工业：计算机辅助设计经常是由实际的模型开始的。工业上有许多传统的部件不是由cAD软件设计出来的，甚至没有图纸，为了在计算机中对这些部件进行合并或修改，需要利用三维模型重建技术。1．3．2边缘数据的曲面重建曲面重建的另一个应用就是边缘数据的处理。在医学研究中，通常可以用CT技术得到某器官的层状数据，每一层的数据表示器官某一层的轮廓。把这些层状数据组合在一起就可以看成是表示一个完整器官的散乱点数据集合。在加工制造业中，也可以通过cAT(x射线轴向分层造影扫描机)扫描机械零件的相交部分而得到这样的层状数据集合。类似的情况是，利用超声传感器探测心脏的形状，就是通过将一个探头伸入食道中，从而得到心脏的边缘数据。与薄片切片机不同，这样的超声得到的边缘数据不是平行的，而且探头可以生成不同角度不同位置的边缘数据，这样生成的数据要看它的密度情况来具体处理。对于这些边缘数据，采用散乱点重建曲面的方式生成曲面表示，可以更有效的用计算机对这些实体进行研究、分析等。1．4相关算法综述曲面重建算法都是要利用采样点的某些相关信息，例如：曲面的拓扑结构、数据的结构、曲面的法向的信息等。本文仅讨论散乱点重建曲面的算法，这里的散乱点是指仅有采样点的三维坐标，而无其他任何附加信息的点。为了描述算法方便，对各类算法进行分类。根据结果曲面是否过给定的散乱点集，将算法分为拟合曲面算法和插值曲面算法。1．4．1拟合曲面算法这类算法不要求结果曲面经过散乱点集，往往利用图形学中常用的造型曲面(如等势面、NURBS曲面、二次曲面等)来拟合散乱点集。 北京工业大学工学硕士学位论文1．4．1．I零集法这种方法(1】通过定义每个取样点的近似切平面，然后以此为基础定义空间点到曲面的有向距离函数。再以此有向距离函数作为某场的场函数，这样待重建的曲面分布在该场的零等势面上，只要抽取出零等势面就得到了待重建的曲面。常用的抽取等势面的方法有Marchingcube。算法具体如下：首先，估计每个采样点附近的近似切平面。算法利用每个点的r一邻域内的点集(r是采样密度)来估计每个点附近的切平面。采用的方法是用最小二乘法求出点集的拟合平面作为切平面的估计。为了定义有向距离函数，必须对切平面执行法向量一致化操作，使所有的法向量都指向睦面的“外”或“内”。算法先确定一个点处的法向量的方向，然后根据邻近的点处的法向量的夹角是锐角的假设按照深度遍历的顺序将此方向传播下去。确定了切平面后，就可以定义有向距离函数了[2](如图卜2所示)。首先，找到切平面L(x。)，它的中心o．是最靠近p的，然后用如下定义的，(p)作为有向距离函数。，(p)=(始f，(p)=(p—D，)·而．如果待重建的曲面已知无边界，这一简单规则很适用。然而，当曲面有边界时，用此方法容易产生错误，规则必须扩展以适应有界曲面。规定d(z，x)(z和x之间的距离)的取值范围，当超过某一阈值时，就把，(p)作为未确定值，用作识别边界[4]。这种识别边界的思想也可以在其他算法中得以利用。确定了有向距离函数后，以此函数构造一个标量场，从这个场中抽取出零等势面便得到了待重建的曲面。抽取等势面选取MarchingCube算法[35]，这是一个将空间分成立方体再进行抽取的方法。将抽取出的网格进行优化后，便得到了最后的结果[3]。零集法非常巧妙的将曲面重建问题转化成了一个抽取等势面的问题，为这个问题的解决提供了一个非常好的思考方法。在此基础上，后人在细节问题上精心考虑，使这个方法日臻完善。4 第l章绪论LeifP．Kobbelt[5，6】等人提出的方法用提高的距离场和扩展的№tchingcube代替零集法中采用的有向距离估计法和MatchingCube，使算法能够更好的重建棱角、折痕等细节。1．4．1．2用标准曲面拟合数据点的算法Foley[7]综述了从散乱点重构隐函数曲面和参数曲面的有关算法。而Pratt[8]则直接采用简单形状(如圆、球、直线、立方体)来拟合数据点，但这种方法难以重建复杂拓扑的曲面形状。1．42生成插值曲面的算法插值曲面要求用散乱点集来构成曲面，就是把散乱点连成二维流形三角网格。这也可以看成是一个把散乱点集从“无序”到“有序”的排序过程。通常的“一维”条件的排序算法中，每个点只有“前趋”、“后继”两个邻接点，而且排序的依据只有点之间的距离。但是在网格曲面中，每个点有多个邻接点，而且确定邻接关系不能仅考虑距离因素，还要综合考虑空间位置等其他因素。这样，我们需要一个有效的分析工具～Delaunay三角剖分[9，10，1l，12，13]。根据使用Delaunay三角剖分处理点集的范围的不同，把这部分算法分成两类：全局算法和局部算法。1．4_2．1全局算法全局算法首先对散乱点集做全局的三维Delaunay三角剖分，对散乱点集进行的初次的排序。理论上认为，在面F上进行足够密度的采样，对采样点集进行Delaunay三角划分后，这时待重建的曲面应该蕴含在三角剖分的结果中。三角剖分中属于待重建曲面的连接是正确的连接，其余的连接是错误的连接。算法的关键是如何过滤错误连接，将曲面抽取出来。目前比较有代表性的算法有以下几种。(1)∞。shape法Edelsbnlnner【141提出了口-Shape的概念，口一sllape方法删除了散乱点集的Delaunav三角剖分中其外接球或外接圆半径大于口的四面体、三角形和边，然后利用“最大点乘法”或“最小二面角法”通过抽取外部面来得到重建睦面。Bajaj【15，16]利用口．sh印e将散乱点所在的空间区域分割成四面体，并用此生成了C1连续的散乱数据点的插值曲面。 北京工业大学工学硕士学位论文口一sh印e方法的关键是找到合适的口值。对于均匀一致的数据点集口．stlape方法很有效，但由于数据点集的不均匀性或表面的某种不连续性，有时很难自动选择合适的口值，以保留需要的三角化元素，删除不需要的所有元素。(2)crust法Cmst方法使用中介面来删除Ddaulley三角剖分中错误的连接[17】。其中中介面的计算是用点集的Voronoi顶点来模拟的。算法的主要过程是先对散乱点集进行Del舢1cy三角剖分，并计算散乱点集的Voronoi顶点，形成v点集，与原取样点合并。再对合并后的点集进行DelaLlney三角划分，取原取样点生成的三角形，作为所得到的三角网格，再用Voronoi点进行过滤，除去不符合标准的网格，最后得到要求的网格。此算法给出了理论上的证明[18]。如果有“好的取样”，就能够保证所生成的网格正确的反映了原曲面的拓扑，当取样点密度增加时，就能够保证生成原曲面。“好的取样”，从直观上来讲，就是在曲率大的地方取样密集，曲率小的地方取样稀疏。(3)cocone算法cocone算法是利用Delauney三角剖分后的三角形对应的Voronoi边来进行三角形过滤的[19]。过滤算法是基于下面的一个必要条件：一个Dd锄may三角形应该被保留下来的必要条件是此三角形所对应的voronoi边同曲面S有交点。然而，由于曲面S是未知的，所以Vo舢i边与曲面S求交的过程无法用程序实现，这样只能用近似的形式来代替。算法中采用了一种叫Cocone结构作为局部的近似。并且当采样满足算法假设的条件时，使用这种近似形式不会将正确的三角形过滤掉。Cocone算法还从理论给检测边界点提出了新的方法[20，21]。Cocone算法只需执行一次Dda：IⅡ1ay三角剖分，而且还适合于用Divideandconq懈方法加以改进以处理海量数据[22】。此算法也从理论上给出了详细的证明[19]，算法对采样密度有同Crust算法相同的要求[17]。但是对采样的要求非常严格，在处理实际数据时难以得到正确的结果[19]。 第1章绪论1422局部算法这类算法往往基于这样一个采样假设：给定一个点，其邻近点集可以反映出该点附近的局部拓扑和几何信息。局部算法通常先用简单的判断条件(例如K一近邻[23])来初步确定每个点附近的邻接点集合，然后估计每个点处的切平面，采用深度数据的思想将其邻接点集合投影到切平面上，再用二维Delauney三角剖分来进一步确定此点与周围的点的邻接关系。M．Gopiy提出了一个基于局部二维Dela眦y三角剖分的算法【24】o算法首先利用K一近邻的技术得到每个点的邻域并根据邻域估计每个点附近的切平面。再把邻域内的点投影到切平面上并对投影点作二维Del咖ay三角剖分。根据三角剖分后的结果得到每个采样点可能的邻接点信息。然后根据这些点之间的邻接信息构造一个初始网格，这个网格很可能不是二维流形。然后需要再对这个网格进行修改。这种方法很容易设计成并行程序。王青提出了一个进行曲面重建的快速增量算法[25]。此算法也是用局部的二维Delaunay三角剖分来确定点的邻接三角形。与上面的算法不同的是此算法在为点确定邻域时要受到当前生成的网格的约束。此算法先选择一个采样点，并用上面的方法得到此点的局部的网格，以此网格为初始网格，并不断将边界点的局部网格合并入当前网格，其中邻近点的选择和局部网格的并入过程都要受到当前网格的约束，即要保证并入此局部网格后得到的新网格仍满足二维流形的要求。直到当前网格中的边界点都被访问过。这样重建完后的网格满足二维流形的要求。1．43算法比较将以上算法相比较，拟合曲面算法的结果曲面不经过采样点，在有的部位会产生形变，不满足要求；插值曲面算法中的全局算法对采样质量的要求比较高，在实际应用中难以单独使用；局部算法不能全面的考虑问题，生成的网格不能全局最优，但是这类算法的鲁棒性比较高。1．5本文主要研究内容本文中讨论的散乱采样点满足如下的要求：1)采样点只有三维坐标信息，而没有法向量等其他几何信息； 北京工业大学工学硕士学位论文2)采样点是无序的，彼此没有任何相关信息：3)采样点的密度是未知的，不知道是均匀采样还是非均匀采样；4)曲面的拓扑结构是未知的，有可能存在很复杂的拓扑；5)数据量可能会比较大，需要考虑算法的运行时间：6)采样的过程中会有误差；从这样的散乱点生成原曲面是一项难度很大的工作。针对这样的散乱点集，本文的主要研究内容有：1)设计一个重建算法，根据散乱点生成一个插值的二维流形网格曲面。要求算法要有较高的鲁棒性。2)已知散乱点集和点集所在的曲面来重建网格也是实际应用中常遇到的问题。本文对上面的重建算法加以改进，提出了对这个问题的一种解决方案。1．6本章小结本章从实际应用中引出了本文所要研究的课题，并从其在其他领域的应用论述此研究课题的实际意义。然后引用国内外文献说明此领域目前的研究进展及成果。并从其存在的不足和待深入研究的问题中引出本文的主要研究内容。 第2章系统的建立及体系结构本项目旨在开发针对曲面的有限元网格自动生成系统。根据应用实践，该系统要实现如下三类条件下的曲面网格生成功能：1)已知曲面上网格顶点集合时的网格自动生成。用户仅以曲面上的一个点集定义曲面，系统须从顶点集合提取皓面定义信息以确定顶点间的拓扑关系。从理论上讲这是一个根据散乱点重建曲面的问题。2)针对大数据量的数据的网格自动生成算法。3)已知曲面及网格顶点集合时的网格自动生成。以用户指定的待剖分曲面及曲面上的网格顶点集合作为输入条件，系统根据曲面中蕴含的性质生成以指定点集为顶点的曲面的有限元网格。该条件下的网格生成算法与曲面类型无关。这三种输入条件总起来说都是从散乱点构造网格曲面。相比较而言，后面两个问题是从第一个问题派生出来的，也就是说第一个问题更加基本一些，因而它的解决方法会对后面两个问题的解决提供新的思路，所以本文主要讨论仅根据散乱点重建曲面的算法。2．1关于采样条件的假设没有任何一种重建算法能够处理任何条件的数据。重建算法都是基于一定的采样条件之上的，有的甚至把采样条件作为构造方法中的输入参数。例如零集法要求采样为均匀采样[4]，并把采样密度和采样误差限作为求得每个点的邻域的参数。而Crust算法要求局部的采样密度同局部的特征大小成正比，直观上来看就是曲率大的地方采样应该密集，曲率小的地方采样应该稀疏。这是一种比较合理的采样密度的要求方法[17]。本文算法吸取上述算法中对采样的合理要求并与实际应用相结合，对采样提出下面的假设要求：1)存在一个流形表面插值或拟合这些采样点。2)采样密度基本满足Crllst算法的要求。 北京工业大学工学硕士学位论文3)允许存在一定程度的采样误差。基于这个假设条件之上，我们分析了多种曲面重建方法，吸取它们处理某些问题的长处，提出了本文的重建方法。2．2系统采用的算法概述本系统主要处理三种类型的数据。这一节将对这三类数据的处理方法进行概述。由于第一类问题的处理方法更基本一些，所以主要说明第一类问题的处理方法。2．2．1针对散乱点重建网格曲面算法上一章列举了一些算法，这些不同的算法用不同的观点来看待睦面重建问题，因而形成了不同的处理方法。在本文中，将曲面重建的过程看成是一个把散乱点从“无序”状态变成“有序”状态的排序过程。通常的排序过程都经历一个由“粗”到“细”的过程，我们的算法也是如此：1)先对散乱点做三维的Delaunay三角剖分。Delaunay三角剖分是对散乱点集的凸壳进行的三角剖分。在第三章将对此作详细介绍。通过剖分，某些点之间具有了连接关系，也就是有了初步的“顺序”关系。但这里面存在大量的错误的连接，需要通过后面的操作将其过滤掉。2)用全局方法进行过滤操作在第一步的基础上，我们采用全局算法来对Delaunay三角剖分后得到的三角形进行过滤。这些过滤的依据是算法本身对采样条件提出的合理假设，主要是采样密度的假设。根据假设条件推演出过滤条件，利用这些条件进行过滤。在此基础之上为了检测边界而添加了新的过滤条件。这些内容将在第四章中进行介绍。全局方法要求任何位置的采样都要满足算法的假设。但在实际采样结果中，由于采样误差等隋况的存在，这一点往往很难保证。这样在这些地方仅用全局过滤方法难以得到正确的网格，需要用局部处理方法对网格进行进一步的处理。3)用局部方法对网格进行处理。10 第2章系统的建立及体系结构根据局部算法鲁棒性比较高的特点，采用这类算法的思想对网格进行进一步修改。本文中对网格的修改是针对采样点展开的。这里把其局部的网格不满足二维流形要求的点叫做奇异点。然后针对产生奇异点的因素不同，分别采用局部过滤、局部重建的方法对网格进行修改。修改的过程中都要对出现的环形区域进行填补，最终得到一个二维流形的网格。这部分内容将在第五章中详细说明。2．22针对海量数据的处理算法当问题的规模非常庞大时，仅用上面的算法受时间和空间条件的约束难以在实际中得到应用，为此采用先分组再合并的思想对上面的算法进行改进。但是算法的核心仍然来自于上面的算法。这部分内容在第六章中说明。2．2．3针对散乱点和其所在的曲面构造网格用上面的算法对散乱点进行三维重建时由于曲面是未知的，因而只能用cocone结构作为曲面的局部近似来进行处理。而在这个问题里曲面的表达形式是己知的，因而将这个重要的条件在算法中加以利用便得到了本文对这个问题的一种解决方法。首先作点集的三维Delaunay三角剖分，然后以曲面为基础用多种方法对三角剖分中的三角形进行过滤。具体的过滤方法将在第七章中详细说明。2．3体系结构本系统的体系结构如图2．1所示。此系统结构图简要说明了各个模块之间的关系，和数据的处理过程。2．4本章小结本章首先从系统需求的角度提出了本文系统所要处理的几类数据，并简要说明了几类问题之间的关系。然后正式提出了本文系统对所处理的数据的采样条件所做的假设。在此基础上分详略概述了系统对各种问题处理方法的技术路线，以及系统的各个模块在后续各章的分布。最后用图示方式说明了整个系统的体系结构。 北京工业大学工学硕士学位论文图2．1系统体系结构图 第3章三角剖分算法基础三角割分楚本文雾法中确定点与点之闰静透接关系酌一个菲常有用的工其，是本文算法静理论基础。它蹩计算凡衍中一个j}常重要的概念。三角剖分研究可追溯到三十年代，并在七十年代后期得到了较大的发展和应用。其中以Delaunay三角制分最具代表性，它建优化的三角剖分，简记为DT(DeIauIlayTriangLIlation)。虽然DT处理的对象是散乱点的凸包，但是在实际应用中它已拓展到很多其他情况，如三维曲面的三角剖分问题，也是采用许多Ddaunay三角妾4分的原理。本章主要分绍二维、三维Del叫nay三角剖分和二维有界域的Delau舱y三角划分。首先余绍皿个基本擐念。3．1三角剖分的基本概念不失一般性，这里先绘如n维空趣三焦裂分熬严格定义。定义3-l三角窘《分阚格：绘定n维空闻中静M个不阉结点缀成酌煮集P，其三角割分r”怒具有下猁性质的N个n维单纯形”的集合，即：少={F?，贮，。r；}满足：1．71”的顶点集为P；2。P憨凸镪掣：u剪；3．若i：≠j，则胛的内部n"的内部；巾；4．r的小l维嚣载在垮的边爨上，或纛戈嚣令单纯形共事。其中，n维单纯形是指n维空间中的n+1个点％，K，¨．，酩，满足：构成的黯包。在本文中，我们照黪是二维平嚣熬三建刹分(其结巢是三焦形酶集合)和三维玑珑⋯圪l∥衍⋯矿l矿矿··矿l。13-#0 北京工业大学工学硕士学位论文空间上的三角剖分(其结果是四面体的集合)。以下给出二维平面三角剖分的定义。定义3-2平面三角剖分网格：称三角形集合r={n，r：，⋯，丁。)为平面上M个非共线有限点集P的三角剖分，当且仅当r满足以下三个条件：1)r的顶点集为P2)P的凸包Ⅲ=u几3)r中任两个三角形的交集或者为空集，或者是P中的点，或者是以r中两点为端点的直线段。从定义3—1和定义3—2中不难看出，对于一个给定的点集P，满足定义的三角剖分不是唯一的，需要对r附加确定的优化条件才能得到唯一结果。理想情况下的三角网格的各个单元应是等边三角形，但这一目标通常是难以企及的，因此通常只能使三角形的内角尽可能的大。这样网格的各个三角形单元的最小内角便成为衡量网格质量的一个重要标准：最小内角越大，网格质量就越好。而Delaunay三角剖分恰好是满足最小内角最大的最优三角剖分。3．2优化的三角剖分技术1934年，B．Del眦lay证明[26】：必定存在且仅存在一种剖分算法，使得所有三角形的最小内角最大。这种剖分被命名为Dd锄may三角剖分。50年代，G．F．Voronoi【27】及G．L．Dirichlet【28】分别提出V咖i图及DiricMet网格。1970年，Mn髓【29]在此基础上建立了较完善的V咖i基础理论体系，证明其直线对偶图即是Delalmay三角剖分，具体说来，其定义形式是这样的：定义3—3平面Delaunay三角剖分网格：给定二维平面上的结点集合矿=慨，K⋯．，踢0>3)，假设这些结点不全共线。若d(形，呦表示M与乃的距离，嘲=&Ido，功(V(A)nS)n(V(B)ns)n(V(C)nS)≠O<=>(V(A)nV(B)nV(C))nS≠0<=>△ABC对应的Voronoi边与曲面S相交由于曲面S的具体表示形式未知，所以这个定义无法直接使用，必须找到一种可以代替曲面s的几何结构，设这个结构为M。为了在过滤三角形的过程中不将约束的Delaunay三角形过滤掉，M需要满足下面的条件：若△ABc对应的Voronoi边与曲面S相交则它必与M相交切平面是常用的作为曲面的局部近似的形式，但很明显它不满足上面的条件，这里用一种称为Cocone的结构。Cocone的定义如下[19]：图4-2co∞ne示意图 第4章全局处理算法的设计设P是V处的正极点，则PV可作为法向量的估计。以此法向量为中轴，以角e为顶角做两个对顶的圆锥(cone)，取其补集便得到点V处的Cocone结构(如图4—2所示)。切平面可以看成是。为90度的Cocone，因此e的取值非常关键。当采样的密度满足Voronoi方法的条件时，e取67．5度。由图中很容易发现Cocone结构满足上面的要求。△ABc附近的曲面的局部近似可以用三个顶点处的Cocone结构的交集来表示。4．3Cocone算法与改进上一节说明了Cocone算法的基本原理，本节首先简要介绍Cocotle算法的几个基本问题的处理，然后主要说明本文针对边界问题对C0cone算法的一种改进。4．3．1正极点【18】的计算图4_3极点示意图上图中，标注成蓝色圆圈的Voronoi顶点就是这个采样点的正极点。求得采样点集的Delaunay三角剖分、Voronoi图和凸壳之后，就可定义采样点的正极点：1)若采样点不在凸壳上，则从此点对应的Voronoi点集中选择一个距离此采样点最远的vomnoi点作为此采样点的正极点。2)若采样点位于凸壳上，那么求出和这个采样点相关的所有凸包面上的三角形的平均法向量。从此采样点出发，沿此方向在“无穷远”处求得一点作为此采样点的正极点。根据此定义可以求出每个采样点对应的正极点。 北京工业大学工学硕士学位论文4．3，2Cocone结构与线段的相交判断由上面的步骤求出了采样点的正极点，再确定顶角e(e=67．5)[19]，每个采样点处的Cocone结构就可以确定了。下面说明如何使用Cocone结构过滤过程的关键步骤是一个点的Cocone结构与线段的相交判断。Cocone结构不是基本的几何元素(如平面)，不能转化成线段与它们的求交。只能根据Cocone的定义来判断。图4_4cocone与线段相交判断示意图如图4—4灰色部分是一个顶角为e的cocone结构，vp是点P处的正极点，则Cocone的上下界与向量PVp的夹角分别为。和Ⅱ一o。红色的是待判断的线段AB。设向量PA、PB与向量PVp的夹角分别为么l和么2，其对应的角度分别为Ⅱ、B。若区间[n，B]n[e，Ⅱ一e]≠O，则此Cocone与线段AB相交，否则认为不相交。4．3．3三角形的Cocone过滤三角形的过滤要用到上面的求交判断，具体说明如下：设△ABC是采样点的Del孤may三角剖分中的一个三角形，MN是其对应的vomnoi边，C0cone__A、Cocorle—B、Cocon9_C是三个点处对应的Cocone结构。若CoconeA、CoconeB、CoconeC与MN都相交，则保留此三角形，否则过滤掉此三角形[19】。20 第4章全局处理算法的设计4．3．4用距离条件进行三角形过滤在边界处，用极点估计的法向量与真实的法向量有较大的差别，这样一些连接边界上的点的三角形会被保留下来。实验表明，用cocone算法不能很好的将边界检测出来，因此需要加入新的过滤条件。在零集法[4】和局部重建方法[25]中都有用距离作为条件来检测边界的思想。考虑把这种思想加入到cocone算法的过滤算法中。当采样均匀的情况下，可以用一个全局唯一的值作为分类的标准，但当采样不均匀的情况下，这个全局唯一的值就很难得到了。从实验结果中可以发现：连接边界上的点的边要“远远大于”每个点与其附近的点的距离。为了在程序中使用这个条件，必须将某些将其中模糊的说法具体化。为此说明几个重要定义：1)点的密度系数值点的密度系数值：对任一点V，V的K近邻中到V的最长距离称为v的结点密度系数值K_D(V)，用数学语言描述如下：K_D(V)=Max({dld=Distallc《P，V)，P∈Kjqeig蛐or(V)})点的密度系数值用K-近邻描述了点局部的疏密程度，也估计了v的邻接点到v的距离的可能的上限。2)点之间的排斥系数两点问排斥系数：结点间的排斥系数a由下式定义：噼驴m世‰，器，其中1B剧为月、B两点间的距离，K—D㈣，K—D(P2)分别为B、尸2的密度系数值。可见，B、P2之间的距离越远，a值越大，A、R两点越排斥；Pl、B之间的距离越近，a值越小，P1、P2两点越不排斥。这里“排斥”意味着两点在结果网格中不能成为邻接点。3)距离过滤条件： 北京工业大学工学硕士学位论文对于△ABC，如果任意两个顶点之间的排斥系数大于一个阀值，则此三角形应该被过滤掉。用数学语言描述于下：△ABC应该被过滤掉《_>(Ⅱ(A，8)>T)oR(Q(B，C)>T)0R(a(A，C)>T)其中T便是衡量两个点是否排斥的阀值。4．4完整的全局处理算法完整的全局处理方法如图4．6所示。对散乱点执行完此全局操作之后，得到了一个初步的网格胍砌。此网格能够粗略的反映待建曲面的拓扑信息。从坛曲中我们可以初步得到每个点的邻接点集合、邻接三角形集合。而用K．近邻方法只能得到近似的邻接点的信息。cocone算法综合利用了点之问的距离、空间位置分布等许多信息，所得到的结果比用K-近邻法更可靠。图4巧用c∞one算法得到的—个局部网格结果 第4章全局处理算法的设计图4《全局处理算法如图4—7所示，用Cocone算法得到的根据点的邻接关系得到的一个网格的局部。从图中可以看出，多数点的邻接点已经确定。而若用K-近邻法(K-_20)，则每个点将有20个邻接点。因此用cocone算法得到的结果比K_近邻法要可靠的多。下面对全局算法的时间复杂度进行分析。全局算法主要用到一次全局的三维Delaunay三角削分。本文中计算Delaunay三角剖分采用的是Clarkson的Hun程序[31]。Clarkson的Delaunay三角剖分算 北京工业大学工学硕士学位论文法对数据的处理，它采用整形数计算，因此结果非常稳定，而且效率比较高，此算法的时间复杂是Df"2)[32]。后续的过滤算法针对每个三角形，由计算几何的知识可知，Delaunay三角剖分中三角形的数量同点数的关系是线性的[33]。而每个三角形的判断算法的时间是个常数，所以整个过滤算法的时间复杂度是D(n)。那么全局处理算法的时间复杂度是D(月2)。下面给出一些对散乱点数据执行了全局处理后的结果图4_7cocone算法的一个结果4．5本章小结本章说明了本文算法中的全局处理算法的内容。首先对多种相关算法进行了比较。然后说明了cocone算法的基本原理。接着分正极点的计算、cocone结构与线段的相交判断和三角形的coconc过滤等三个部分简要说明了cocone算法的实现方法。最后针对Cocone算法在边界处理方面上的不足，提出了本文中的一种解决方法：用距离条件进行三角形过滤。 第5章对网格的局部处理方法5．1局部处理方法的目标经过Coconc算法，已经能够得到散乱点生成的曲面的粗略的网格。这个初步的网格已经基本上能够反映原曲面的形状特征和每个点附近粗略的几何和拓扑信息。从图3—5和图3—6中可以看到。但是又把它叫做粗网格，是因为这时生成的网格曲面并不满足二维流形网格的要求，有可能有三个三角形共享一条边，也有可能在曲面上存在着漏洞，甚至还可能有更复杂的结构。下面给出这样的实验结果(如图5—1所示)。图5—1瞬格中存在的复杂结构的局部示意图为了解决这个问题，Cocone算法在自己的采样假设的基础上提出了一个理论上的解决方法，但在处理实际问题时效果并不理想[19]。为此本文提出了一个基于局部算法的网格处理方法。处理方法的提出应该基于问题的根源，通过对全局算法的结果的分析，我们认为出现这些问题的原因主要有两个：1)cocone结构作为s曲ce的近似，用它进行过滤，仍会保留下一些冗余的三角形。这通常发生在这样一些点处，其对应的Voronoi点集中存在距离待重建曲面非常近的Vomnoi点。如图5—2所示，四面体一丑CD是点4的一个邻接四面体。y是4的正极点，O是四面体爿占CD的外接球的球心。D膨、0Ⅳ、DP、DQ分别是4爿BC、4A肋·、 北京工业大学工学硕士学位论文4DBC和44CD对应的Voronoi边。设0点在四面体丘BCD的内部，则很明显点D距离带重建的曲面很近。O0图5_2C∞佃e过滤算法不彻底的原因的示意图如图5．20Ⅳ，0P、0Q都与A处的Cocone结构相交，所以4ABD、4D8C和44CD都会被保留下来。很明显根据二维流形的定义44肋和4爿CD是不能共存的，因此这个过滤是不彻底的。但是这种情况下期望得到的三角形往往蕴含在过滤完的结果中，只要对这个结果进行进一步的过滤。2)某些采样的局部存在采样质量差的情况如采样密度过于稀疏或采样存在较大的误差，这些采样的结果不再满足Cooom算法的理论要求，因此在这些地方得到的结果不再可靠，因此仅用过滤的方法无法得到理想的结果(图5-3)。图513网格中存在的复杂的结构 第5章对网格的局部处理方法为了对这些情况进行修正，我们采用类似局部重建算法[24，25】中用到的处理思想来对这些不同的情况用不同的方法进行修改。5-2局部方法的基本原理图5-4鞠国瞪嘴处理示意图在处理深度数据(如地理数据)时，往往将三维数据投影到一个平面上，然后对投影点做二维Delalmay三角剖分，再将此结果映射回三维空间就得到了待重建的网格。这种方法对在拓扑上同构与平面的数据比较有效。而本文处理的数据是任意拓扑结构的，所以不能直接使用此方法。尽管数据所代表的曲面的拓扑结构是任意的，但是它们都是采自于一个二维流形[34]的表面。二维流形有这样一个性质：任取二维流形上的一点，总存在此点的一个邻域，此邻域拓扑同构于一个圆盘，这就启发我们利用这个圆盘作为这个邻域的近似来辅助对其邻域进行进一步分析。常用的曲面在某点处的邻域的近似形式是曲面在此点处的切平面。C0cone算法中用约束的voronoi元来确定每个点的邻接点[19]：若两个点对应的约束的vomlloi元的交集不为空，则将这两个点互为邻接点。但是由于曲面的形式未知，所以约束的vo埘10i元无法求解，所以这个原则不能直接利用，需要用一种近似的形式来模拟。 北京工业大学工学硕士学位论文cocone算法用Cocone结构定义了一种约束的Voronoi元的近似。而本文是从局部对网格图5-5本文模拟局部约束的voronoi图的原理图元的方法。本文利用点V处的切平面作为曲面的在V处的局部近似，并将V和其邻域内的点映射到此切平面上，求解映射点集的vomnoi图，并用切平面上的vomnoi图作为曲面上的V点处局部的约束的Voronoi图的近似形式，用于确定v的邻接点。这是主要思想，在不同的情况下其使用的方法稍有不同。主要的局部处理方法由局部过滤、局部重建和环形区域填补等几部分组成，其之间的关系如图5．6所示。图5．6局部处理算法示意图本文中的局部处理算法都要解决切平面的估计和映射方式等基本问题，下一节就对这些基本问题进行论述。 第5章对网格的局部处理方法5．3局部处理方法的基本问题的计算这一节介绍几个局部处理方法共用的几个基本问题，包括奇异点的选取、法向量的估计和投影方式。5J3．1奇异点的选取为了对网格进行修正，必须找到修正的位置。在本文算法中，是针对网格上的点来进行修改的。我们期望得到一个二维流形的网格，因此需要对那些其局部网格不满足二维流形要求的网格顶点进行修改，并把这样的点称做奇异点。为表述奇异点的特点方便，先说明几个描述网格中点、线、面关系的概念。在一个三角形网格中，对于顶点y和三角形L若y为，的一个顶点，则三角形r称为r的邻接三角形。若顶点A和顶点V有相同的邻接三角形，则顶点爿称为矿的邻接点。而爿关于y的重数是指r的邻接三角形中含有爿的个数。需要进行局部过滤的奇异点的特点：1)存在重数大于2的邻接点。2)存在这样的邻接边，其对应的二面角为尖锐角。3)邻接的三角形中按照相连的关系分组后，组的数目大于1。以上三种情况如图5—7所示：霪哂锤图5-7奇j}点5．3．2法向量的估计方法在局部算法中，通常要将点附近的局部信息投影到切平面上，因此每个点处的法向量的估计非常重要。在一般的局部算法中，由于得到的点的局部信息少，所以多数采用最小二乘法对邻近的点进行拟合。然而经过本文中的全局算法处理过后，得到了每个点处的几何的和拓扑的信息比较多。主要有每个点可能的邻接点和可能的邻接三角形。给定一个点V，可供使用的估计法向量的方法主要有：1)用最小二乘法计算拟合V及其邻接点集的平面的法向量。．29． 北京工业大学工学硕士学位论文2)V到其对应的极点P的向量[18]。3)V所邻接的三角形片的法向量的均值。在子剖分等算法中，通常用方法3)来估计法向量。但是由于在奇异点处并不是所有的邻接三角形都是正确的，需要参考方法1)或方法2)来选择。本文算法中先用方法1)得到一个向量m并用此向量做判断三角形是否合适的标准。设V的第』个邻接三角形的法向量为删。若lⅣ·州I(O．7，则认为这个三角形是合适的三角形。计算这些合适的三角形的法向量的平均值作为曲面在点v处的法向量的估计。S．3．3投影方式以估计出来的向量为法向量，再以给定的点V为平面上一点做一个切平面，以此切平面作为曲面的局部近似，因此需要将曲面上的点映射到此切平面上。多数局部算法的主要思想是源自于地形数据的处理方法，因此它们常用的映射方式是垂直投影。V图釉映射方式而本文的算法的思想是要用平面点集的Vomnoi元来模拟曲面上的约束的voronoi元，那么在投影过程中应该尽可能的保持关键的几何信息。曲面上的约束的voronoi元的计算是根据点在曲面上的距离进行，两点在空间中的直线距离可以作为两点的曲面距离的近似。而且从具体的计算公式上可以看出极坐标投影的结果受法向量估计误差的影响小。综合以上原因，本文采用极坐标投影方法。本节介绍了局部算法中的几个关键问题的处理方法。下一节将具体说明局部处理算法，对这些问题就不再赘述。 第5章对网格的局部处理方法5．4局部处理算法5．4．1局部过滤现在可以考虑进行过滤算法的设计了，这主要针对由于Coconc的过滤算法的不彻底性提出的一种进一步的过滤算法。既然是过滤算法，它仍然是按照某种原则从当前网格中滤掉某些三角形。关键是确定一种过滤的原则。(1)局部过滤原则：此过滤原则是针对网格中的奇异点进行的，设v是当前网格中的一个奇异点。根据前面的算法，估计V点处的切平面，再将网格中V的所有邻接点和点v按照上面说的投影方式映射到此切平面上，对此投影点的集合做二维的Delaunay三角剖分。设三角剖分中的边的集合为E，三角形的集合为T。用下面的规则对V点附近的网格进行过滤：删除这样的三角形VPQ：其投影点连成的三角形△V’P’Q’不属于T。(这里，V’、P’、Q’分别是V、P、Q的投影点)(2)局部过滤算法：根据上述过滤原则，写出对网格进行进一步过滤的局部过滤算法(如图5．10)。下面从局部给出经过局部过滤算法后的一些局部的实验结果。一闲又茬√／弋心莎≮3、／＼械八优／＼／＼∥＼5．9局都过滤算法的一个结果实验表明：局部过滤算法通常在采样条件比较好的地方能达到预想的效果。在这些地方，cocone算法得到的三角形集合能够蕴含待重建的网格。但是在采样质量 北京工业大学工学硕士学位论文不高的地方，cocone算法得到的结果不再可靠，这时仅用过滤的思路已经不足以得到理想的结果。对这些局部，我们采取一个叫做局部重建的算法图5-10局部过滤算法5．4．2局部重建如上所述，在采样质量不高的地方，用全局处理算法得到的结果不再可靠，这时仅用过滤的思路已经不足以得到理想的结果。过滤完后，在这些地方仍会保留一 第5章对网格的局部处理方法些奇异点。这样，只能根据“不破不立”的思想，先将一个奇异点附近的有可疑边的点删除掉，一直删除到重建的结果可靠的点处，再根据这些结果可靠的点回来重新推断这个局部的网格曲面。(1)预处理算法预处理算法是为了进行局部重建算法之前对网格进行的预先的处理，主要是删除一个奇异点附近的可疑连接，为后面的处理做好准备：其输出是后续重建算法的输入。为了说明这个过程，先定义完全点和孤立点的概念。完全点：给定一个点P，如果P所有的邻接边邻接的三角形的数目都是2，则P是一个完全点。本文认为完全点就是重建结果比较可靠的地方。孤立点：没有邻接点的点称为孤立点。图5_10完全点和孤立点的关系示意圈将当前网格看作一个“图”，一个由非完全点的连通域应该包围在一个由完全点构成的环中(如图5．10所示)。我们的删除算法的目的就是要找到这个由完全点构成的环，并通过删除操作将包围在此环内的非完全点变成孤立点。此过程是一个从一个奇异点开始的一个对“图”的广度遍历算法。完全点是遍历“停止”的条件。5—11特殊情况下的完全点和孤立点的关系示意图口图 北京工业大学工学硕士学位论文在有些比较复杂的情况下，一个非完全点的连通域可能被包含在多个由完全点构成的环中(如图5．11所示)。为了得到每个环对应的可能的孤立点，本文将遍历过程访问过的点存放在一个树中，为以后的查找做准备。算法描述见图5—13，其结果是输出一个树缸∞，从舰P中，可以得到经过此操作之后得到的边界点集合和孤立点集合。其中树的中间节点是孤立点，根节点是边界中的点。若有多个边界环，从每个边界环包含的点对应的根节点开始向上遍历直到找到这些根的第一个公共父节点，在此过程中访问到的中间节点对应的顶点是这个边界环包含的可能的孤立点集合。图5-12一个预处理算法的结果 第5章对网格的局部处理方法一个奇异点砌0初始化一个树船P和一个栈‘I将砌入栈，将砌设为树根节点一<毫>’从栈中弹出栈顶点玎并找出y对应的树节点加d士将y中没有访问过的邻接点加入到加d的子节点0将V的邻接点中没有访问过的非完全点入栈0删除树的中间节点对应的网格点邻接的三角形上．返回树抛P图5-13预处理算法流程图(2)曲面局部愈合算法通过预处理算法输出的边界点环和孤立点集合是曲面局部愈合算法的输入条件，其中边界点环是曲面增长的地方。用类似网格前沿算法【36】的思想，通过不断选择合适的孤立点并将其加入到网格中，并对当前的边界进行修改，直到边界不再变化。为边界上的点选择邻接点的方法 北京工业大学工学硕士学位论文正如上文所述，网格的生长是从边界开始的，用程序来体现就是根据边界上的点，来选择合适的孤立点，生成合适的三角形，使此点变成完全点。设点v是一个边界点，选择算法的基本思想也是将可供选择的点投影到v处的切平面上，再用二维Dela吼ay三角剖分进行判断与选择。但与过滤算法不同的是，这里的操作受到V处已有的邻接三角形的约束，并且我们要求处理完后V处就应该是正确的网格。这样我们有下面的要求：a)保持v原先的邻接三角形集合不变；b)新生成的三角形受到原先的邻接三角形集合的约束。基于这两个原则，我们分下面的三步来确定点V的新的邻接三角形。为描述问题方便，先对v附近的网格信息作如下的说明：由于v是边界点上的点，则V应该有且仅有两个关于V的重数为l的邻接点，设这两个邻接点为A、B。以V的邻接三角形的平均法向量作为V点处的法向量，从而得到V点处的切平面。设V、A、B在此切平面上的投影点分别为矿’、4’、B’。设当前边界点和孤立点的集合为C。sTEPl)用距离作为约束条件进行初次选取。这个步骤是根据v的邻接点距点V不能太远的原则进行选取，我们必须找到一个比较的标准，这里我们采用VA、Ⅶ中较长的一个做为标准ls：1s=Max(Distallce(v，A)，DistanceⅣ，B))；用ls为标准得到一个C的子集Cl：C1={引Distajnce(V，P)0，则心d=M：否则^k=—鹕。 第5章对网格的局部处理方法5．5完整的局部处理算法如图所示，将上面阐述的算法连起来，便得到了本文的局部处理算法。下面对局部处理算法的时间复杂度进行分析。局部过滤算法是针对每个采样点的。经过全局处理算法后，每个采样点邻接的三角形、边、点的数量有限，可以认为它们分别小于常数m、ME和MP。那么奇异点的判断的时间复杂度是0(^扭)，每个点处的过滤算法主要是二维Delaunay三角剖分，其时间复杂度是D((^卵)2)，这些都可以看成是常数。因此整个局部过滤算法的时间复杂度是D(”)。全局算法后得到的网格舱曲上对地幽执行环形区域处理J对朋缸^执行局部过滤上对朋如^执行环形区域处理t对拖妇执行局部重建上对埘蹦执行环形区域处理Jr对埘醯^执行法向量一致化工输出拖如图5—20局部处理算法局部重建算法包括删除可疑连接和局部重建两部分。删除可疑连接是访问所有的采样点，并判断它是否是奇异点，因此其时间复杂度是D(厅)。而局部重建是针对 北京工业大学工学硕士学位论文剩下的奇异点的，对每个点邻近的～些点做二维Delaunay三角剖分。经过一些限制后，每个点邻近的点的数量有限(设其小于Mv)，因此这个三角剖分的时间复杂度至多是D((^∥)2)，因此局部重建的时间复杂度是D(功。则整个局部重建算法的时间复杂度是D∞)。需要执行填补操作的环形区域的点的数量是有限的，本文定为30。每次填补是进行～次二维有界域的Delaunay三角剖分，其时间复杂度是D(M2)(M是多边形的点的数目)。这里填补一个环形区域的时间可以认为是常数时间。则所有环形区域的填补的时间复杂度是0(功。则整个局部处理算法的时间复杂度是0(，1)。下面给出经过局部处理算法后的最终结果。此结果中包含了不同的采样点数目，采样密度和拓扑结构的数据。例子点数面数例子点数面数3593571866cat352700mobius18603600rrlmhcad1735834712m2497l495947051406表5一l实验数据的信息 第5章对网格的局部处理方法5-2l实验结果5．6本章小结本章介绍局部处理的方法。首先说明由全局处理得到的结果网格中存在的问题，并分析了出现这些问题的可能的原因。由此提出了局部处理方法所要处理的问题和期望达到的目标。第二节从地形数据出发说明了本文采用的局部处理算法的基本原理。第三节说明了局部处理算法中所共用的几个基本问题的解决方法，主要包括奇异点的判断、法向量的估计和映射方式。为后面的局部算法的描述打下的基础。第四节具体描述局部处理算法的几个步骤。主要有局部过滤、局部重建和环形区域填补，它们分别用在不同的情况下对网格进行修改。最终将得到一个满足二维流形要求的网格。 北京工业大学工学硕士学位论文第6章海量数据的处理算法随着三维扫描技术的发展，采样的精度越来越高，采样密度也越来越密，例如一个人脸的面部数据就可由3万多个点构成，这种大数据量的数据被称为海量数据。海量数据的出现使人们可以非常精确的重建复杂物体的表面，但是也从时间复杂度和空间复杂度方面对重建算法提出了新的要求。一个时间复杂度和空间复杂度非常高的算法的实用价值并不高。从第四章和第五章的分析中可知当处理的数据量比较大时，本文所描述的算法的时间复杂度为0即2)。根据实验的结果，本文算法需要为解决海量数据的处理而进行改进。从第四章的分析可知本文算法的时间复杂度高的原因是算法需要执行一次全局的三维Delaunay三角剖分。因此为了减少时间复杂度，可以采用先分片再合并的思想来进行加速处理。分片再合并的主要想法是首先将大规模问题分割成同类型的小规模问题，并且大规模问题的结果可以由这些小规模问题的结果通过合并方法得到。这里主要的要求是小规模问题的处理方法是相互独立的，合并算法的时间复杂度应该比较低。根据本文算法的特点可以发现，本文的算法可以用分片再合并算法进行改进。1)本文的全局操作采用的是基于cocone方法的算法，cocone方法是适合于才用这种分片再合并的思想的[22]。2)本文的合并算法只要是先将各个分片对应的网格合并在一起，这样得到的网格必然包含奇异点。只需采用第五章说明的局部网格处理方法来对此网格进行修改最后得到一个正确的二维流形的网格。由第五章的分析可知局部处理方法的时间复杂度是D(n)，因此可以作为合并算法进行使用。本文中之所以在全局处理时采用cocone这个效率相对较低的算法，主要是考虑牺牲一定的时间来获得网格整体的优化。但是采用分片的思想后并不会破坏结果的优化，主要原因是每个点的连接情况仅跟其邻近的点相关，而与距其距离较远的点 第6章海量数据的处理算法无关。而每个分片的数据量仍能数以千计，因此根据分片的信息基本能够得到优化的网格。6．1本文算法本文改进算法首先采用八叉树的方法对数据进行分片。若当前数据的数量大于4000，则将数据分成8个分片；若存在采样点的数量大于4000，则将此分片再进行八叉树分解，直到每个分片的采样点的数目都小于4000。为了合并算法的需要，相邻的分片数据之间应该有一定数量的共同顶点，如图6一l所示的灰色采样点。图6一lbunny数据的分片示意图对每个分片分别执行本文第四章的全局算法进行处理，并将这些结果网格直接合并在—起，得到初始合并的网格。(如图6—2所示)图6—2初始的合并网格图6—3初始网格中共同点处的局部网格 北京工业大学工学硕士学位论文对直接合并后的网格进行观察后发现，在分片之间的共同点处存在着大量的奇异点(如图6—3所示)，因此只要对这些奇异点用第五章的局部网格处理方法后，将奇异点变成非奇异点，便实现了分片网格的合并(如图6_4所示)。图6_4对共同点进行局部处理后的结果图6—5用改进后的算法得蓟的网格曲面6．2算法分析由于用八叉树得到的每个分片的数据量小于4000，则分片的数量是问题规模n(采样点的数量)的线性函数，而对每个分片的处理时间可以看成常数时间，则这 第6章海量数据的处理算法部分算法的时间复杂度为0(”)。合并算法主要采用第五章的局部处理算法，其时间复杂度为O(n)。则整个算法的时间复杂度为0(H)。同理可知算法的空间复杂度也是Df")。通过将bunny数据使用第四章算法的结果和用本章的改进算法得到的结果进行对比可以看出：1)使用第四章算法时，操作系统发出了虚拟内存不够的警告；而使用本章的改进算法时没有发出这样的警告。这说明使用的内存空间大大减少了。2)在相同的软硬件环境下，使用第四章的算法时的执行时间为1229秒，而用本章的改进算法使用了394秒。执行时间也减少了。6．3本章小结从实际应用的需要出发，本节对海量数据的处理提出了本文的一种改进算法。本文采用八叉树的方法对数据进行了分片操作，其中相邻分片之间的共同点为后面的合并算法打下了基础。最后采用第五章的局部处理算法进行了合并操作。实验证明，采用改进后的加速算法使内存空间得到了有效的利用，时间复杂度也减少了。 北京工业大学工学硕士学位论文第7章已知散乱点点集和曲面的网格自动生成上面介绍的算法要求其输入的数据只有曲面上的网格顶点集合，然而在实际应用中，由用户指定待剖分的曲面和曲面上的网格顶点集合也是常见的系统输入条件。系统将根据曲面性质生成以指定点集为顶点的曲面有限元网格。从系统的通用性方面考虑，要求此类网格生成算法与曲面类型无关。7．1相关算法此类算法所要解决的问题是给定一个曲面和曲面上的采样点集，完成对这个曲面的三角剖分。文献[37]中的算法要求给出待重建网格的边界，这样这个问题可以看成是平面有界域的三角剖分在曲面上的推广。其总的思想就是从边界开始，利用网格前沿算法[36]不断选择最优点，生成三角形并修改前沿边界，直到前沿边界为空。采用前沿边界算法的关键是如何为边界上的线段选择最优点从而构成三角形。平面有界域的三角剖分主要有两个用于选择最优点的准则，一个是两个点关于线段的可见性判断准则，另一个是外接圆准则。算法首先将平面外接圆的准则推广，定义了一种外接球的准则[37]。并且定义了两个三维点关于一条直线的侧的概念，并以此为基础定义了三维空间中两个点关于线段的可见性的判断准则。本文将曲面作为重要的已知条件加入到前文所述的散乱点重建网格曲面的算法得到了一个已知散乱点点集和曲面的网格重建算法。加入了曲面信息后，某些问题的处理得到了简化，而且准确程度也提高了。7．2本文算法原理本文算法不需要给出待重建曲面的边界，可以看成是平面的Delaunay三角剖分在曲面上的推广。平面Delaunay三角剖分有一种计算方法是根据点集的Voronoi图来计算：若三个点其对应的Voronoi元的交集不为空，则由这三个点构成的三角形是一个Delaunay三角形。为了在曲面S上使用这个原则，我们需要计算点集在曲面s上的Voronoi图。这使我们想起了Cocone算法中提到的约束的Voronoi图的概念，以及由此得到的约50 第7章已知散乱点点集和曲面的网格自动生成束的V0ronoi元的概念[19]。利用这几个概念将二维平面上的Delaunay三角剖分和voronoi图的关系推广到曲面上来便得到了下砸的结论：若三个点其对应的约束的voronoi元的交集不为空，则由这三个点构成的三角形可以作为待重建网格曲面中的三角形[19]。将约束的Voronoi元的概念应用到这里，并进行推理便得到了下面的结论：对散乱点集做三维Delaunay三角剖分，若三角剖分中的一个三角形所对应的Voronoi边同曲面有交点，则此三角形可以作为待重建网格曲面中的三角形[19]。由于在Cocone算法中，曲面的具体形式未知，所以只能用Cocone结构来作为曲面的局部的近似。然而在这里曲面的具体形式是已知的，这使我们可以非常方便的使用这个结论。由上面的论述可以知道：此算法也是先对散乱点集作三维Delaunay三角剖分，然后尽可能利用已知曲面s这一重要条件，来对三角形剖分中的三角形进行过滤。7．2．1Voronoi边过滤这个过滤过程是根据上文的结论来进行处理的。计算每个三角形的对应的voronoi边，判断它是否与曲面s相交，若相交就保留，否则就将此三角形过滤掉。三角形的voronoi边是一个线段，这样在这个过程中涉及到线段与曲面的相交判断，许多文献中对这类求交问题的算法进行了介绍。同用Cocone结构作判断的结果相比，用曲面作相交判断确实准确了很多。图7—1cocone检测与曲面检测结果比较 北京工业大学工学硕士学位论文7．2．2距离条件过滤用Vornonoi边条件进行过滤时实际上有一个隐含的条件：被保留下来的三角形应该与曲面相交在由散乱点集所确定的曲面上，然而给定的曲面的信息中没有显式的给出曲面范围的信息。这样有些Delaunay三角形与曲面的交点远远超出这个范围。这样的三角形本应过滤掉，但若仅用Voronoi边的条件无法过滤掉。需要考虑其他的过滤条件。由于这种三角形与曲面的交点距给定的点集较远，也就与此三角形的三个顶点较远，也就是说此三角形的外心距离三个顶点的长度较远，那么这个三角形中必定至少有一个线段的长度“非常长”。在这里，可以利用第四章介绍的距离过滤条件来对这种三角形进行过滤。7．23接近程度过滤网格曲面中的三角形应该逼近曲面，这样在已知曲面的情况下，用三角形与曲面的接近程度也是～个非常有效的过滤条件。先给出本文中关于三角形与曲面的接近参数的定义。三角形与曲面的接近参数：三角形的外心到三角形对应的Voronoi边与曲面的交点的距离。若有多个交点则选择其中最短的距离。给定一个阈值，若三角形与曲面的接近参数大于此阈值，则此三角形也应该被过滤掉。实验表明：此条件在检测边界时非常有效。7—2采用接近程度过滤方法前后的结果比较 第7章已知散乱点点集和曲面的网格自动生成7．2．4利用外接球进行过滤对某些有奇异顶点的三角形用外接球再进行过滤，这个想法主要来自于文献[37]的选择最优点的外接球准则。本文用如下的方法定义一个三角形对应的检测外接球。三角形的检测外接球：设△ABc的外接圆圆心为O，d是衡量三角形与曲面接近程度的阂值。则从O开始沿三角形的法向量得到两个距O的距离为d的点K、砍。经过接近程度的过滤后可知，线段D“、DK中必有～个与曲面相交，将其中与曲面相交的线段记为0矿。四面体ABCV对应的外接球便是三角形的检测外接球。外接球过滤条件：设△ABc的检测外接球为球O，若球O中包含点集中除A、B、c以外的点，则此三角形也应该过滤掉。这样根据散乱点集合和曲面重建出的网格已经基本建立起来，考虑到采样误差的存在，为了增强系统的鲁棒性，再用第五章介绍过的方法对网格进行奇异点的检测和修改。下面给出一些实验结果。图7—3曲面Z=X2+】，2结果 北京工业大学工学硕士学位论文图7q鞍马面2Z=Ⅳ2一】，2的结果图7_5曲面y=sin(爿)×cos(Z)的结果 筹8颦系缝实现、总缝秘展翅第8章系统实现、总结和展望本文的工作慧要开发～个人梳界谳友好的、搡作方便的曲谣有限元两格自动生成工聂蕊统。此系绕怒一个交互式三维显示、编辑系统，能掇供多种输入数据的类型，生戏虫输入嬲数摄艨没示的麴颟的肖限元网格。8+l系统实现本系统主要由嚣大功S§摸块组成，数攒读入与绩暴墩成模块、初始网格生成模块、嫠帮黼洛囊动惨燕模块、湿示模块。1)数爨读入与绪暴文移生靛模块本系统主要攥傻了溪搴孛黉鬃戆输入数撵；～耱只输入教熬点鬃数摄+雯～种黉饕输入散筏患集数据帮盏疆数据。对于第一稀输入数据，提供辩下的文佟袼式：文{孛怒一个文本文件，文件的每行表示一个点的坐标信患，每一行黻逗母缩柬。簿个点豹三缎坐栋售慰依次按照x、Y、Z嫩标顺序以浮点数形式写入文件，坐标数攒之润激空掺籀骧开。例如：一1．?42一14．293一O．788。一4。3l器一13，S65一l。OS?，一3。i6莲一7．3l唾—鑫。57龟～1．i琵一10．?44—0。各43，一3．80l—iO．唾3l—O．822。一2．36l—lO．726～2．078，黠予第二糖簸入数据，本文星兹耋爨融陕了二次曲面和数乱点数据的输入格式：营兔依次按照x2、y2、z2、拶、弦，溜、芏、y、：、常数琰鲍膜序依次输入番项的系数。然后再按照第一种数据的输入方式输入散乱点集。-辩· 北京工业大学工学硕士学位论文由于本文的曲面和散乱点集的处理算法与具体的曲面类型无关，因此只要为此模块添加新的类型的曲面读入方法和曲面与直线的求交算法，就可以对系统进行扩展。结果网格数据以wrl格式的文件输出，这样的文件能被标准的3D模型处理软件所读取。2)初始网格生成模块此模块以从数据读入模块得到的数据作为输入，用全局的方法生成初始网格作为输出。‘当输入的数据只有散乱点集时，当数据量不是非常大时采用第四章介绍的算法进行处理，而若输入的数据是海量数据时，采用第六章介绍的加速改进算法；当输入的数据包括曲面数据和散乱点集时，采用第七章介绍的算法进行处理。这个模块的算法基础是散乱点的采样密度满足理论上的要求，而在实际应用中经常存在不满足理论要求的情况，因此用此模块得到的网格难以保证是正确的网格，因此只能作为中间的处理结果，需要进行后续的修正处理。3)局部网格自动修正模块此模块以初始网格生成模块生成的中间结果网格作为输入，输出正确的网格，并可以调用结果文件生成模块将得到的网格以wRL格式的文件输出。用切平面作为曲面的局部近似，以此为修改和矫正网格的根据。通过局部过滤、局部重建和环形区域填补等算法对网格进行修改，并最终得到一个满足二维流形要求的网格。这部分算法在第五章中介绍。4)显示模块此模块主要实现了三维网格的显示，以及交互所需要的键盘命令。为了能很好的观察网格点之间的连接情况，我们设计了一个三维空间中的漫游环境，用户可以通过键盘操作来改变视点的位置和视线方向，以及控制网格绕X、Y、z三个坐标轴的旋转。网格的显示主要提供了线框显示模式。本模块的实现主要涉及0penGL的编程。交互操作所需的键盘命令如下表所示按键功能按键功能方向键(左)左摆头方向键(下)视点后移 第8章系统实现、总结和展望方向键(右)右摆头PageUp上抬头方向键(上)视点前移PageDOWn下低头J视点左移L视点右移I视点上移M视点下移Q绕x轴正向旋转网格A绕X轴反向旋转网格W绕Y轴正向旋转网格S绕Y轴反向旋转网格E绕z轴正向旋转网格D绕Z轴反向旋转网格系统的运行界面如图所示表8—1按键与功能对应表图8_1系统界面示意图8．2系统总结本系统目前主要提供了针对两种类型的输入数据的有限v元网格生成功能。 北京工业大学工学硕士学位论文1)在实现根据散乱点集生成有限元网格的功能时，我们采用了基于cocone算法的曲面重建方法，并用局部重建算法的思想对此算法进行了改进。采用这种方法使系统在实现这个功能时具有如下特点：a)基于Cocone算法的曲面重建方法在计算的过程中并不需要采样点的密度信息，同时，也并不要求采样是均匀的。这使系统放宽了对散乱点数据的总体分布的要求，扩大了系统可处理的数据的范围。b)生成了初始网格后，针对初始网格所存在的问题及产生这些问题的原因，我们设计了局部过滤、局部重建和环形区域填充法等局部处理方法。局部过滤和局部重建是针对网格上的奇异点而进行的局部处理方法。它的主要思想是利用切平面作为曲面的局部近似，并用它作为判断点的邻接点集的依据。本文算法正是运用这种思想到来处理某些局部采样质量比较差例如有采样误差的情况，这正是Cocone算法本身不善于处理的情况。这个处理过程从细节处考虑问题，增强了系统对有采样误差的数据的处理能力，提高了系统的鲁棒性。综上所述，系统综合利用了cocone算法处理问题全局的优势和局部算法的鲁棒性，在一定程度上放松了这些算法对采样数据的限制，拓宽了系统能够处理的问题的范围。与Cocone算法相比较，本文算法的优点有以下两点：a)采样有一定程度的误差或采样密度不严格满足cocone算法的要求时，本文的算法仍能得到正确的二维流形的网格。b)本算法在重建过程中能够自动的识别数据中蕴含着的明显的边界2)系统还实现了根据散乱点集生成有限元网格的功能。很显然这个问题同上一个问题有紧密的联系，这一点在我们处理这个问题时得到了体现。我们在处理这个问题时以上一个问题的处理方法为基础，紧紧抓住曲面这个已知条件简化了其中某些问题的处理，并添加了一些新的处理步骤，提出了我们对这个问题的一个处理方法。因此在处理这个问题时，上一个问题的许多代码得到了重用，使整个系统变得非常紧凑。 第8章系统实现、总结和展望8．3下一步的工作展望从本系统的功能扩展和本文算法的不足之处，我们提出了下一步可能的工作内容：1)根据实际应用角度需要，我们认为系统还应提供如下功能：a1已知曲面时的网格自动生成功能。b1提供将网格表示成光滑曲面的功能。c1增加网格交互编辑功能，包括网格精度控制、对单个顶点的修改、两组网格的合并。2)针对本文算法的不足，我们认为本文的算法还应进行如下的进一步改进：在对网格进行修改时主要考虑网格的正确性，对网格的光滑程度考虑不够，尤其是在采样误差较大的地方。可以考虑在这些地方采用拟合曲面的生成算法思想根据给定的点来进行重新布点，以求生成一个尽可能光滑的曲面。 北京工业大学工学硕士学位论文结论本文虢嚣标是研究由数蘸患羹建瞬洛穑瑟的算法。针对这个西标本文主要在采样点存在误茇条件下的网格萄面生成、海爨数据的黼格曲丽生成和根据已知曲面及曲面上的散乱点生成阏格曲面的算法等三个方面进行了研究，并根据这三个算法实现了～个可以处理这三种输入数据的有限元网格自动生成系统。在根据散乱点重建曲面的方面，国外有一姥经典的算法，这些算法从理论上绘出了证明。但是由于实际问题时常难以满足理论上的要求，因此这些算法难以葭凌髑予处理实骣目题，鬟要麴以改进。本文在总结co∞能算法的基≤皇上，利用深度数据豹处理恩怨慰c粼算法提穗了鑫邑静一秸揭部处理豹改进方法。实验证明，遴遂本文的改进方法，算法的髻棒住增强了。系统能箍理的数据的范围扩大了。对于海量数据的巯理，我们采用了先分片褥合并的思想来对上面的算法进行了加速改进。算法中的合并算法也是基于本文的瞒格局部处理算法。使用此方法改进后算法的时间复杂度和空间复杂度降低了，系统的性能褥到改善。根据曲躐和曲面上的点来对曲面进行三角剖分也是实际中常见的问题。本文将其看成是已知曲馥的散乱点重建网揍越题阏题，并根据邑知曲藏这个条l牛对上西的算法进行泼避，掇出了本文慰这个阂题弱一秘黪决方法。矮嚣本文根攥上述技零程葵法实魂了～个曲瑟有限元掰格强动生成系统。魏系统能够处连多稀输入条件下酶数据，有一定的应焉价德。60 参考文献【l】H．H叩pe，T．DeRose，T．Duchamp，M．Halstead，H．Ji巩J．McDonald，J．Schweitzer，andW．S毗le．Piece、visesmootllsurfkerecon咖tion．CD—妒“柳G心砷妇俗，GG删朋J94尸，D凹8删，pages295-302，July1994．【21H'Hoppe，T．DeRosc，T．Duch锄p，J．McDollald，andw．Smetzle．Surfkerecom廿uc-tion疗omun0唱aIlizcdpo幽．cD唧加rGr劝蛔舯饼MP日J92PrDceedf增曲，26(2)：71_78，July1992．[3]H．Hoppe，T．DeRose，T．Duchnp，J．McDonald，andW．StuetzIe．Meshoptjmization．ComputerG唧厅把，俸，(删P日，93m卯e旃㈣，pageslE卜-26，August1993．[4】H．H叩pe．Sur矗lceReconsmjc吐onfbmUnorgmlizedPoints．Ph．D．Thesis，ComputerScience趾dEng妇e血岛删vcrs时ofwaSbington，1994．[5】LeifP．KobbeltFe砒meSensmvcsurf犯eE】(乜action舶mVol唧eData．§!垡j堡缱丛2鲤!：57_66[6]LeifP．KobbeltAnh此rac廿veApproachtoPointCloud啊趾蓦；ulation．￡Q噬鱼塑叠埏望里Q幽!里(3)：(2000)[7]FolcyTA，HagenH，NielsonGM．Visuali五ngandInodeIingu枷cturedda诅．neVisllalComputcrh他n洲。砌JournalofC0nlputerGrapbics1993，9(8)：439—449．[8]PrattV．DirectLeaSt—squaresfimngofalgebraics删沁es．111StoneMCed．ProceedillgofSIG—GRAPH’87，D觚vcrs：Assison-WssleyPublishingCompany，1987，145一152．61 I￡京王鼗大学互学磺士学位论文【9】kwsonCLGene圳onofamanglllar鲥d1lvi也appIicaiiontocomourpIotting．Califb栅a111stitⅡteofTecIlnolOgyJetPropmsionLabo疆cory，Te眩h越calMemorand搬l29殳1972【l翅(沁檄Pj，Si砖on＆Co鹤赋if毽转强c毯e￡钯ssel莪溉onsin垃砖pl锄e．{聚Compulef孙啪越，1978，2lf2)：i68一173．【ll】BowyerA．eompu妇gDiri踟ettessell娟ons．111eComp蝴JoIJnlal，1981，24(2)：162一166．[12】DeyTK，Su西haraK，B匈萄cL．Delalmay订划矾。璐iIldlreedimensionswnf诚teprecision撕吐必e如．Computer～dedGeome城cDesi辨，1992，9(5)：457。470，[13】HofrKE，刚VerT，KeyserJ鲋戚Fas￡eomp删onof鲫eral酬VofonoiDia蓼a热sUSi珏鬈Grap越csb蚤荩煅．瓤：C∞kR秘。p鞫eee漱gofSlGG廷AP}{99．f)a琏ve搭：As蛙son—Wssley善’翻醵ishi醒Co臻【p鑫玛01992，2弘286．【14】H．Edeli酾塌nerandE．醚懈ke，3DA每融S峨)es，熊M髓ans．on￡融p糙cs，13(I)，pp．43～72(1994)．f15】c．L．B勾两ReconstmctingSu】{hcesandFuncdonsonSuIf犯es旬吣mUno娼aIliZedT协ee-D_iIIlensionalData．mpr∞eedingsoftheF0urdlSMMCo脏renceonGeome砸cDcsign，Nashnlle，1N，Noven慨r1995。f1翻c。B曼斑，F。Befn捌灏，andG．Xu．Autonl娟cR∞ons№蛙挑ofs删％鄂an硅se砖越F越泰蠹。趣3Dsca璐．s酪G_是《尹譬舛只删蚴，pagesl鹦bll8，jdyl995。【17】N矗捻Am黻妇a畦髓燃隧lB饿ksu娥∞糙∞B呶髂畦潍谚Vo默loi蠡l溆蠢壤．确a粥ar弧l矿ACMsⅣnpo《umonC嘣ipu溆(沁onle窿y，june1998．【l8】N妇Anler慨Ma蕊allBemandM嬲ohsKarnWssclis．ANewVoronoi-转asedS删FaceReco璐眦tionAlgo棚1n1．ToappearinSIG(黜PH’98Proceedings，pages4】5，421．