（计算机应用技术专业论文）基于离散点的图形重建技术.pdf

摘要 摘要 近年来的大量研究工作表明，图形重建技术与许多领域联系愈来愈密切，诸如在计 算机图形学、科学计算可视化、机器人视觉、医学等领域中都存在着广泛的应用前景。 理论上研究图形重建的目的是多方面的，主要是根据给定的离散点来重构物体原貌，揭 示它的本质，刻画它的基本特征；实践上是通过图形重建来解决日常生活中的问题使之 为人类服务。如何使用现有离散点进行图形重建已经成为了当今一个重要的研究课题。 三角网划分技术由此提出，并成为近年来图形重建领域的热点研究问题。 本文将给定的空间离散点分为两种类型：一种离散点是可以直接投影n - 维平面上 而没有重叠现象的数据；另一种是空间中任意给定的无组织散点数据。对于以上两种类 型的数据，本文分别进行了研究，主要涉及到以下内容： ( 1 ) 基于给定的一批特殊散点数据，提出了逐层提取轮廓线来构造初始三角网，然后 应用重心插值来重建图形的新算法。实现这一算法的关键是将给定的特殊散点投影n - - 维平面上，在给定参数的条件下逐层提取内部离散点的轮廓线；接着在所提取的轮廓线 间进行等比例三角划分；然后，将划分好的三角网的拓扑结构映射到三维空间中；最后， 为了更清楚的描绘图形的细节特征对构造的初始三角网进行了重心插值。 ( 2 ) 基于给定的一批无组织离散点，提出了在初始三角网格中插入新的控制点进而对 三角网进行细分来重建物体的新算法。文中首先运用局部投影法进行初始三角网的划 分，并且给出了切平面的概念；然后，在初始三角网格中借助b e z i e r 出面来生成新的插 入点，进而对网格进行细分；接着，对于细分后的三角网进行一次升阶来调整网格密度 ( 也就是进行第二次细分) ；最后，在最终形成的三角网上进行光照、材质和雾的设定来 重建物体。 本文通过给定的两类离散点分别利用上述算法进行了实验，实验证明通过这两种方 法重建的模型可以更好的保留物体的细节，结果是可行有效的。 关键字：空间离散点，初始三角网，重心坐标，b e z i e r 曲面，控制点，顶点向量，重构 a b s 仕a c t a b s t r a c t i nt h er e c e n ty e a r s ，al a r g en u m b e ro fs t u d i e si n d i c a t et h a tt h er e l a t i o n s h i pb e t w e e n g r a p h i c sr e c o n s t r u c t i o nt e c h n i c ( g r t ) a n dm a n yd o m a i n sa r em o r ea n dm o r ec l o s e d g r t h a saw i d ea p p l i c a t i o n si nm a n yf i e l d s ，s u c ha sl i m i t e dn u m b e ra n a l y s i s 、c o m p u t e rg r a p h i c s 、 s c i e n c ec o m p u t ev i s u a l i z a t i o n 、r o b o tv i s i o n 、m e d i c i n ea n ds oo n i nt h e o r y , t h em a i np u r p o s e s f o ri n v e s t i g a t i n gg r ti sr e c o n s t r u c t i o nm o d e l sp a n o r a m ab a s e do nt h es c a t t e r e d p o i n t s ， u n c o v e r i n gi t sn a t u r e s ，d e p i c t i n gi t sb a s i cc h a r a c t e r s ；i np r a c t i c e ，t h em o s t l ya i mi ss o l v et h e p r o b l e m so fd a i l yl i f e ，c o n t r o l l i n ga n du t i l i z i n gi tt os e r v ep e o p l e h o wt ou s et h es c a t t e r e d p o i n t st or e c o n s t r u c t i o nt h em o d e l si sb e c o m ea ni m p o r t a n tr e s e a r c ht a s k t h u s ，t h ep r o b l e m o f t r i a n g u l a t i o ni sp r o p o s e da n db e c o m et h em o s ti m p o r t a n tp r o b l e mi ng r t t h i sp a p e rc l a s s i f yt h e3 ds c a t t e r e dp o i n t si nt w ot y p e s ：o n ei st h ee s p e c i a l l yp o i n t s w h i c hc a np r o j e c ti n2 ds p a c ed i r e c t l y ；t h eo t h e ri st h ei n o r g a n i z e dp o i n t si n3 ds p a c e i nt h i s p a p e rm a i n l ys t u d i e st h et w op r o b l e m s ，t h em a i nc o n t e n t sa sf o l l o w s ： ( 1 ) b a s e do nt h ee s p e c i a l l ys c a t t e r e dp o i n t s ，aq u i c km e t h o df o rt h et r i a n g u l a t i o nb e t w e e n t w oc o n t o u rl i n e s ，t h e ni n s e r t i n gp o i n t su s i n gt h ec e n t e ro fg r a v i t yc o o r d i n a t em e a n si s p r o p o s e d t h ep r o b l e mo f t h en e wa l g o r i t h mi sp r o j e c t e dt h ep o i n t si n t o2 ds p a c e ，a n d p i c k e d u pt h ei n t e r i o rc o n t o u rl i n e ；t h e np l o t e do u tt h et r i a n g l eb e t w e e nt h ec o n t o u rl i n e ； w h e r e a f t e r ，p r o j e c t i n gt h et r i a n g l e s t o p o l o g yf r a m ei n t o3 ds p a c e ；f i n a l l y , i no r d e rt o d e s c r i p t i o nt h ed e t a i l so f t h em o d e l ，p u t t i n gu pt h ei n s e r t i n gm e t h o do ft h ec e n t e ro fg r a v i t y c o o r d i n a t e ( 2 ) b a s e do nt h e3 di n o r g a n i z e ds c a t t e r e dp o i n t s ，am e t h o df o ri n t e r p o l a t i n gn e wp o i n t s i n t ot h ei n i t i a lt r i a n g l e si s p r o p o s e d t h ed e t a i lp r o c e d u r e s a r et h a t ：f i r s t , u s i n gl o c a l p r o j e c t i o nm e t h o de s t a b l i s hi n i t i a lt r i a n g u l a t i o n s ，a n dg i v i n gt h ec o n c e p to ft a n g e n tp l a n e ；t h e n ， r n a k eu s eo ft h eb e z i e rs u r f a c et og e n e r a t en e wc o n t r o lp o i n t s ，i no r d e rt os u b d i v i s i o nt h e i n i t i a lt r i a n g l e s ；a n dt h e ni n s e r t i n gt h es e c o n dc o n t r o lp o i n t st oa d j u s tt h e 鲥dd e n s i t y ；f i n a l l y , s e t t i n gt h el i g h t ，m a t e r i a la n df o go n t ot h ef i n a lm o d e l t h r o u g ht h ee x p e r i m e n t st op r o v et h a tt h et w om e t h o d sw e r ef e a s i b l ea n de f f e c t i v e k e y w o r d s ：3 ds c a t t e r e dp o i n t s ，i n i t i a lt r i a n g l e s ，t h ec e n t e ro fg r a v i t yc o o r d i n a t e ，b e z i e rs u r f a c e ， c o n t r o lp o i n t s ，v e r t e xn o r m a l s ，r e c o n s t r u c t i o n h 独创性声明 本人声明所呈交的学位论文是本人在导师指导下进行的研究工作及取 得的研究成果尽我所知，除了文中特别加以标注和致谢的地方外，论文 中不包含其他人已经发丧或撰写过的研究成果，也不包含本人为获得江南 大学或其它教育机构的学位或证书而使用过的材料与我一同工作的同志 对本研究所做的任何贡献均已在论文中作了明确的说明并表示谢意。 签名： 关于论文使用授权的说明 本学位论文作者完全了解江南大学有关保留、使用学位论文的规定： 江南大学有权保留并向国家有关部门或机构送交论文的复印件和磁盘，允 许论文被查阅和借闺，可以将学位论文的全部或部分内容编入有关数据库 进行检索，可以采用影印、缩印或扫描等复制手段保存，汇编学位论文， 并且本人电子文档的内容和纸质论文的内容相一致 保密的学位论文在解密后也遵守此规定 签 名：垄塑兰导师签名：益递羔 日 期：b o o7 鲁f 够， 第一章绪论 1 1 图形重建概述 第一章绪论 随着计算机技术的飞速发展，计算机的应用领域正以空前的规模扩展着。特别是最 近十几年来，计算机日益普及的进入了千家万户并与人们的日常生活越来越贴近。其中 计算机图形学已成为计算机科学中，最为活跃的分支之一，并得到广泛的应用。计算机 的普及大力推动了计算机图形学的发展，使得人们足不出户就可以体验到充满现代气息 的全新工作方式以及娱乐方式，尤其在工业生产、军事演练、影视制作、媒体广告还有 游戏娱乐等各个领域。因此，用计算机来模拟真实的物质世界，也逐渐成为计算机图形 学工作者们所面临的最为艰巨和最具有挑战意义的工作之一。 1 9 8 6 年，美国科学基金会( n s f ) 专门召开了一次研讨会，会上提出了“科学计算 可视化( v i s u a l i z a t i o ni ns c i e n t i f i cc o m p u t i n g 简称v i s c ) j 9 0 第二年，美国计算机成像 专业委员会向n s f 提交了“科学计算可视化的研究报告”后，v i s c 就迅速发展起来了。 随着科学技术的迅猛发展，现实世界也变得五彩缤纷，怎样将现实世界中形态各异的物 体真实的展现在计算机上，这就给计算机的模拟工作带来了极大的困难。如何使现实生 活中的物体更加精准和真实地在计算机屏幕上展现出来，已经成为计算机工作者们不可 推卸的责任，同时这个方向也吸引了众多的研究者们为之而努力。因此，开展用计算机 进行图形重建的研究，有着十分重要的理论和实践意义。 1 2 图形重建方法 1 2 1 离散点数据模型的获取 计算机图形学始于计算机出现后不久，1 9 6 3 年，伊凡苏泽兰在麻省理工学院发表 了名为画板的博士论文，它标志着计算机图形学的正式诞生，至今已有三十多年的 历史，但是由于当时的硬件十分昂贵，而且缺乏易用和廉价的基于图形的应用程序，因 此只能用计算机来表示一些简单的图形。随着计算机图形学以及计算机技术的不断发 展，开发出了很多经济实用的专门的硬件系统，比如三维扫描仪硬件设备，使得获取物 体表面的几何数据信息和表面纹理颜色信息更加容易，再加上计算机运算能力和存储能 力的大幅度提高以及各种图形加速卡的出现，使得在个人计算机上处理离散点数据进而 重建物体成为当今的热点研究问题之一。 目前，模型离散点数据的获取主要使用三维设备数据获取的方法( 3 ds c a n n i n g ) 。其 实质就是通过三维扫描仪将物体表面的数据信息扫描出来，在此过程中可以人为进行规 划，使得在曲率大的地方获得较多的数据点，而在平坦区域得到较少数据点，然后通过 后续的数据处理，并对整体或者部分数据进行修补，从而得到模型的离散点数据信息。 这种获取方式相对比较简单和方便，目前大部分3 d 离散点数据模型都以这种方式获取。 江南大学硕士学位论文 当今三维扫描仪设备可以分为远景全周激光扫描仪、中近景激光扫描仪、高精度激 光扫描仪和手持式激光扫描仪等。 1 2 2 离散点数据模型的表示方法 离散点数据模型造型，是建立恰当的模型来表示自然界中形态多样的三维物体的技 术，根据重构对象将重构技术分为3 类：基于面的重构、基于体数据的重构和基于实体 的重构。在计算机图形学中，离散点数据模型通常包含两部分内容：一部分是从模型上 提取的数据点信息，另一部分是模型的外观属性，如表面纹理和材质等。 对采集到的离散点数据进行多边形网格的构建是目前表现离散点数据模型的主要 方法，当然也就成为图形重建的主要方法，这是由于多边形网格模型具有以下优点： ( 1 ) 多边形网格模型可以任意精度的逼近任何复杂曲面。随着计算机处理能力的增 强以及采用更新更好的技术，可以处理的数据点规模越来越大，因此使用多边形网格构 建出来的模型的精细程度就越来越高，表现能力也随之越来越好。 ( 2 ) 多边形网格模型只保留了物体最为重要的可视信息：表面信息。这使得它保存 的信息量大大减少，结构也比较简单。 ( 3 ) 多边形形状简单，便于处理与计算，只需存储多边形顶点的位置坐标及属性 就可表示物体的表面信息。 基于以上优点本文将采用多边形网格来描述采样得到的离散点数据模型，由于任何 多边形都可以方便的被剖分为三角形，并且目前研究和应用的最广泛的多边形网格即为 三角网格，因此本文主要针对三角网格模型进行研究。三角网格模型是一种重要的三维 物体表示方法，它用一系列空间三角形逼近表示三维物体。三角网格模型具有表示简单 一致的优点，在计算机图形学等领域有着广泛的应用。 1 2 3 三角网格的处理方法 通过光学三维测量系统得到的数据一般具有以下几个特点： ( 1 ) 每一个原始数据点都有它自己的坐标； ( 2 ) 这些点是没有规律的； ( 3 ) 这些原始数据点中包含有少部分的无用点，即噪声点； ( 4 ) 通过这些点构造拓扑结构可以表现出原始物体的形状； ( 5 ) 通过这些原始数据点形成的表面可能会存在一些孔洞。 离散点数据模型是指对真实物体表面进行采样而得到的几何数据，以上都是离散点 数据模型的一些特点，我们在处理这些数据时必须考虑到这些方面。另外要想把得到的 这些原始数据点转化成我们所需的三角网的格式，所形成的三角网格必须要满足以下一 些要求： ( 1 ) 这些三角网格要以三个表来表示：第一个表内要包含有所有采样点的坐标，第二 个表要包含所有的边信息，第三个表则要包含所有三角形的拓扑结构信息，其中每一个 三角形要求有三个顶点。 2 第一章绪论 ( 2 ) 生成的三角形不能重叠。 ( 3 ) 相邻三角形的法向应该是同侧。 离散点数据模型处理即用计算机对这种三维数据进行三角网的划分，以达到不同应 用所要求的数据转换、模型表示或场景绘制等目的。在此，应用三角网划分技术对离散 点数据模型进行重建，离散点数据模型可以有以下特点： ( 1 ) 离散点数据本身以及各种属性都是非规则采样的。 ( 2 ) 它所表示的物体表面通常是任意弯曲、复杂( 流行非流行，定向非定向) 和缺 乏连续参数化的，很难找到一种内在的函数形式对其进行描述。 ( 3 ) 对于一些结构复杂的物体，其数据表面的形状变化多样，拓扑结构错综复杂。 ( 4 ) 随着三维激光扫描技术的进步，采集的离散点数据量也将大幅度的增长。 迄今为止国内外已经有大量的关于三角网划分算法的研究，主要的算法有典型的 d e l a u n a y 三角网划分法、区域生长法、分治算法、细分法、三角网的简化算法以及二次 曲面拟合方法等，这些方法都是进行三角网划分时所用到的基本方法，在下一小节中分 别概述了这些方法在研究中的应用。 1 3 对于三角划分算法的研究 近几年来，国内外已经有很多有关三角划分算法的研究，这些算法各有各的优点， 当然也有其自身的不足之处。在现实生活中，为了将给定的离散点进行有效的三角划分， 进而更加清晰地展现物体的全貌，各地的研究工作者们分别从不同的角度利用不同的方 法对离散点集进行了三角划分。现就将三角划分算法的研究简要介绍如下。 1 9 0 8 年，g v o r o n o i 首先在数学上限定了每个离散点数据的有效作用范围，即其有 效反映区域信息的范围，并定义了二维平面上的v o r o n o i 图。俄国数学家d e l a u n a y 在 1 9 3 4 年由v o r o n o i 图演化出了更易于分析应用的d e l a u n a y 三角网，证明了：对于任意给 定的平面点集，有且仅有一种三角剖分方法能够满足“最大一最小角 优化准则，即所 有三角形的最小内角之和最大。s i b s o n 证明了平面任意给定点集的d e l a u a y - - 角划分具 有整体最优化的性质，这就是说，对于任意给定的平面点集，d e l a u n a y - - 角划分能够得 到整体最优的三角形网格，能尽可能地避免病态三角形的出现。由于这两个性质，决定 了d e l a u n a y 三角网具有极大的应用价值。同时，它也是二维平面三角网中唯一的、最好 的。1 9 6 9 年m i l e s 1 】证明了d e l a u n a y 三角网是“好的”三角网；1 9 7 8 年s i b s o n z 认定 d e l a u n a y 三角网是有限点集中唯一存在的一个局部等角的三角网；1 9 8 6 年l i n g a s 3 j 进一 步证明了在一般情况下，d e l a u n a y - - - 角网是最优的；1 9 9 3 年t s a i m j 认为在不多于3 个相邻 点共圆的欧几里德平面中，d e l a u n a y - - - - 角网是唯一的。在大量的研究中从算法的实用性 出发，力图使算法的时间复杂度最小，1 9 7 8 年g a r e y e 5 】提出简单多边形三角剖分的线性时 间算法。1 9 9 7 年李景焕【6 】提出用“有向线段推进法”生成初始网格，生成的三角形都在计 算区域内，避免了删除计算区域外的多余三角形，这对凹域或多连通区域来说，大大减 轻了工作量。 区域生长算法开始于种子三角形，以局部增量扩张的方式生成新的三角形，直至覆 3 江南大学硕士学位论文 盖整个表面。这种方法的关键在于如何为当前扩展边选取第三点形成新三角形。b p a 算 法【7 】对第三点的选取依赖于用户定义的外接球半径；l i n t 8 】的方法需要依靠样点的最长和 最短关联边的比率( 采样均匀度) 来确定第三点的搜索范围；h u a n 9 1 9 1 拘算法把与当前扩展 边端点相关联的k 个邻接点投影到局部平面上，然后根据最小长度准则为当前扩展边选 取第三点。h o p p e 等【l o 】使用邻域点进行表面重构。 三角网划分的另一种算法为分治算法，这种算法的思想由s h a m o s 和h o e y 首先提出， 该算法被形象的称为分割归并算法。该思想是指递归地分割点集，直至子集中包含点数 足够少，以利于对每个分割出来的点集进行d e l a u n a y z 角化，然后自下而上逐级合并相 邻子集的凸壳，进而生成最终的整个点集三角网模型。分割归并算法按分割方法的不同， 可以分为条带分割方法、网格分割方法和四叉树分割方法。b p l i i i , 1 2 】( b a r e q u e t s p i e c e w i s e 一1 i n e a ri n t e r p o l a t i o n ) 算法是由b a r e q u e t 提出的一种基于二维平行轮廓线重建三 维表面的方法，是一种很常用的局部优化方法。m a t c h i n gc u b e s 算法【l3 1 ，即将点划分在 不同的立方体内，在每个立方体内利用各点之间的几何物理关系生成三角形，从而得到 整个三维划分。基于四叉树结构的d e l a u n a y - - - 角化基本思想【1 4 】是首先利用四叉树结构来 对离散点进行分割，然后对四叉树叶节点进行d e l a u n a y - - - 角化，再两两合并四叉树节点 三角网的凸壳，以快速生成网格模型。g o p im 的算法【1 5 】基于求二维点集凸包的g r a h a m 扫 描法对原始两维区域进行分割，然后对子区域进行三角剖分，从而实现对整个区域的三 角剖分。 在进行重构的过程中为了突出细节往往需要对三角曲面网格模型进行拟均匀细化 过程。细分法作为曲线曲面的离散化造型方法，可分为插值细分法和逼近细分法。插值 细分法的研究已经获得了许多引人注目的成果；d y n 等u 6 j 提出了四点及六点b i n a r y 插值 细分法；文献【1 7 】阐述了对于无孔域的情况，采用两步方案：先任意连接一三角形网格，然 后用最小内角最大准则迭代地修改三角形连接关系，直至达到除边界外其他节点都符 合最小内角最大准则。对于逼近细分法l d ef l o r i a n i t ”】提出了一种所谓的线性约束 d e l a u n a y - - - 角划分算法，其优点是不需要预先指定特征线，在已有的三角形网格中插 入特征线来形成约束的优化网格。此外，v o l a k i s 与t a y l o r 对于网格细化也做了很多研 究【1 9 郐i 。f a r i n 【2 1 1 利用二元b e r n s t e i n 多项式构造出著名的三角形b d z i e r 网上的 b e r n s t e i n - b 4 z i e r 曲面，这是一种以三角形b 6 z i e r 网为控制点阵的磨光曲面。 在构造三角网的时候并不是所划分的三角网越多越好，而是根据对原模型逼近精度 的要求，相应的减少模型中三角形面片数目，为此提出了模型简化算法。国外对模型简 化算法的研究已有一系列成果。d e h a m e r 【2 2 】使用自适应剖分方法对多边形物体进行简化； s c h r o e d e r 【2 3 】提出了基于顶点删除的网格删减方法；t u r k v 4 】给出了基于重新划分的多边 形网格模型简化方法；r o s s i g n a c t 2 5 】提出了一种基于顶点聚类的网格简化方法；h o p p e l 2 6 1 则提出了一种整体网格优化算法，算法建立了比较复杂的全局能量优化方法；h a m a n n 鲫 基于三角形的曲率计算来移去三角形，从而达到模型简化的目的。c o h e n 【2 s 通过构造包 络网格来控制网格简化的全局误差。 另外一种图形重建方法是二次曲面拟合方法。这种算法的关键是高效稳定的二次曲 4 第一章绪论 面拟合算法，对于这种算法也有很多研究结果：w e r g h i 2 9 1 介绍了使用线性最小二乘技术 的拟合方法；m a r s h a l l l 3 0 1 介绍了使用非线性最：j 、- - 乘技术的拟合方法；在各种非线性最 d - 乘拟合方法中，l u k a c s 3 l 】提出了以逼近真实距离的“可信 距离平方和为目标函数 进行迭代求解的二次曲面拟合方法。 以上是近几十年来人们提出的一些图形重建算法，其中的一些算法也在趋于成熟， 当然应用领域也在不断地延伸。但由于种种原因，目前普遍认为比较满意的算法还比较 有限，通用性都或多或少的受到了一定的限制，很难说哪一种方法更加适合人们的需要。 因而对于计算机工作人员，特别是计算机图形学的研究者和制作者来说，不断探索和改 进目前的图形重建算法，发展出新的更加便于人们使用的有效算法来势在必行。因此， 把现有的各种算法的优点有机的结合起来，更好的满足时代发展的需要，仍然是摆在我 们面前的重要课题，也是需要人们长期进行探索的重要方向。 1 4 图形重建的意义 在反求工程中，依据测量数据生成物体的几何模型是最关键也是最困难的工作，研 究三维重建对反求工程有着及其深远的意义。目前，三维重建已经渗透到了日常生活中 的各个领域，简要介绍如下： ( 1 ) 动画制作领域。随着计算机图形学和计算机硬件的不断发展，现代的动画形象对 外部造型要求越来越高，特别是对媒体角色的逼真度提出了苛刻的要求。在一部动画片 中，动画及环境角色可能成千上万，图形重建提供了直接从现实模型到数字模型的方法， 这样一个直观高效、稳定可靠的造型工具将推动动画制作技术迈向新的台阶。 ( 2 ) 医学领域。当前有大量的仪器设备可以获取人体表面及内部数据，利用图形重建 的结果，可以将从仪器获取的数据恢复三维形状，再现感兴趣的人体部分的形貌，为拟 定最佳手术方案提供可靠的依据，以提高手术质量，减少医疗事故，因此，图形重建技 术对外科手术的精确定位起到了关键的作用；同时，图形重建技术也对整形外科产生了 巨大的影响。1 9 9 7 年，美国应用快速制造出的人工下颌替代了病变骨。 ( 3 ) 断层数据重构领域。当今基于断层数据的三维重建已经成为国内外的研究热点， 并成为工业上反求工程的一个新的方向。为了对重建后的产品进行修改和再设计，需要 对断层进行面向制造而不仅是面向可视化的三维重建，因此首先对断层进行三角网的划 分是必要的。 ( 4 ) g i s 领域。大规模g i s 的数据通常是卫星深度图像，数据量巨大，利用图形重建 的结果能够大量简化模型，缩小数据量，复原三维地貌。在城市地理信息系统中，要得 到比较真实的建筑物模型，一种快捷的方法是用高速三维测量仪获取数据，进行三维合 成。 ( 5 ) 文物的保护和修复。对于文物处于保护的需要，一般不能用接触的方式获取它们 的三维数据，只能用非接触式的三维扫描仪定期获取数据，进行比较，判断毁损程度， 以决定是否需要进行修复。对于已毁损的文物，可通过图形重建技术得到它的三维模型， 首先在电脑里进行复原，最后确定复原方案。 5 江南大学硕士学位论文 1 5 本文主要工作 图形重建技术的研究离不开计算机图形学和图像处理的理论支持。在图形学领域 里，图形学的建模思想、三维观察、光照以及消隐等技术直接影响着三维图形的显示和 处理；在图像处理领域里，图像处理的平滑、恢复、重建、体显示等技术也影响着三维 图形恢复的效果。所以说图形重建是计算机图形学和图像处理相结合的交叉学科。前人 在这个领域所作的研究和实验，得出的理论和经验，都为本文研究提供了很大的帮助。 本文在研究图形重建技术时，分别从离散点数据模型的获取和处理、三角网的构建 和模型恢复三个方面进行研究。概括起来，主要有以下几个方面的工作： 学习分析了当前主要的离散点数据模型的获取和处理方法。掌握了离散点数据模型 的读取方式，以及概括了图形重建的意义。 分析和研究了当前的三角网划分算法，发现很多算法只简单对已知的采样点进行初 始的三角网划分，对于原始模型的细节等并没有很好的反映出来，而且对于一些简单的 三维数据点并没有提出相对容易的算法。其次本文简单介绍了o p e n g l 的一些知识，并对 一些常用函数进行了讲解。 本文经过对采集的离散数据点进行分析，将数据点分为两大类：一类是较为简单的 三维数据点模型，这类数据点可以直接投影n - - 维平面上而没有重叠现象，然后利用二 维三角网划分算法对其进行重建，重建过程中用到了分治算法和细分算法思想。另一类 是经常见到的无组织数据点模型，对于这类数据点的重建，本文用到了局部投影的方法， 利用这种方法得到的初始三角网在进行光照材质的设定时模型表面并不是光滑的，因此 本文又对建立的初始三角网进行了b e z i e r 曲面插值以及升阶处理，目的是细分网格以得 到平滑的效果，最后本文还利用了o p e n g l 函数在细分后的三角网上进行光照、材质和雾 的设定，使得重建后的几何模型具有很好的可视化效果。 1 6 论文组织 本文第一章综述了图形重建的内容、方法、研究概况和应用前景，并且详细地论述 了国内外学者在图形重建上的研究成果。 第二章首先详细介绍了几种常见的在进行图形重建时所使用的三角网划分算法，主 要包括区域生长算法、分治算法、插值细分法、网格模型简化算法；其次简单介绍了 o p e n g l 相关知识，对一些函数的用法进行了讲解；最后，引出了本文研究的主要内容。 第三章基于一种特殊的三维点集，以分治算法为启发，提出了一种新的曲面重建算 法，并进行了实验验证。 第四章对任意的无组织三维点集，应用局部投影法进行初始网的建立，并对初始三 角网进行了b e z i e r 曲面片的逼近，而且利用o p e n g l 函数进行光照、材质和雾的设定，使 重建后的模型更加真实化，同样进行了实验验证。 第五章是对本文工作的总结与展望，同时介绍了今后需要进一步完善的工作。 6 第二章三角划分算法及0 p e n g l 简介 第二章三角划分算法及o p e n g l 简介 2 1 几种常用的三角划分算法介绍 计算机图形学中，特别是用三角划分技术进行三维实体几何造型时，空间中任意离 散点的三角划分的优劣，将在一定程度上影响着三维重构的质量。由于三角形是平面域 的单纯形，与其它类型的多边形相比，它具有很多特性和优点，例如可以更好的贴近拟 合复杂边界等。有限元网格自动生成，计算机图形处理及模式识别等许多领域都存在三 角剖分问题；三维实体几何造型系统中的曲面描述及隐藏面消除等技术也需要用到三角 剖分算法。可以说三角剖分算法是计算机图形学的一个重要理论基础。随着物体复杂度 的提高，为了满足实时绘制的需求，有时需要对初始三角网格进行细分，有时需要对初 始三角网进行简化，即在保持原模型外观不变或在允许范围内变化的前提下增加或减少 模型的三角形面片数量，因此研究三角划分算法是十分必要的，有效的算法可以减少运 行时间而且更能很好的反应模型的细节。三角剖分在医学、地质勘探、气象学、分子模 型构造、计算流体力学和有限元分析等领域具有广泛的应用价值。 如何把一个散点集剖分成不均匀的三角形网格，这就是散点集的三角剖分问题，散 点集的三角剖分，对图形学来说是极为重要的一项预处理技术。三角剖分的定义为：假 设v 是二维实数域上的有限点集，边e 是由点集中的点作为端点构成的封闭线段，e 为e 的 集合，那么该点集v 的一个三角剖分t = ( v ，e ) 是一个平面图g ，该平面图满足以下条件： ( 1 ) 除了端点，平面图中的边不包含点集中的任何点。 ( 2 ) 没有相交边。 ( 3 ) 平面图中所有的面都是三角面，且所有三角面的合集是散点集v 的凸包。 俄国数学家d e l a u n a y 在1 9 3 4 年提出了d e l a u n a y - - - 角剖分算法，此算法所具备的优异 特性如下： ( 1 ) 最接近性：以最近临的三点形成三角形，且各线段( 三角形的边) 皆不相交。 ( 2 ) 唯一性：不论从区域何处开始构建，最终都将得到一致的结果。 ( 3 ) 最优性：任意两个相邻三角形形成的凸四边形的对角线如果可以互换的话，那 么两个三角形六个内角中最小的角度不会变大。 ( 4 ) 最规则：如果将三角网中的每个三角形的最小角进行升序排列，则d e l a u n a y 三角网的排列得到的数值最大。 ( 5 ) 区域性：新增、删除、移除某一个顶点只会影响临近的三角形。 ( 6 ) 具有凸多边形的外壳：三角网最外层的边界形成一个凸多边形的外壳。 由于d e l a u n a y 三角剖分的六个特性，因此在实际中运用的最多的就是d e l a u n a y 三 角割分，它是一种特殊的三角剖分。以d e l a u n a y 三角剖分为基础，许多工作者们 又提出了很多三角剖分算法，如第一章中1 3 节中所述的有区域生长算法、分治算法、 细分法、网格模型简化算法、二次曲面拟合方法等。在实际的构网重建过程中这些算法 7 江南大学颈学位论文 可咀结合起来使用，以求得到更好的剖分效果。本章主要详细举例介绍前四种三角剖分 算法思想，然后通过对已有算法的研究找出其中的不足之处，提出改进的算法思想，以 得到创新，图2 一l 为对离散点进行三角划分后的结果。 图2 1 三角划分实例 f i 9 2 - l t h e e x a m p l e o f t h e t r i a n g u l a t i o n 2 1 1 区域生长算法 在进行图形重建过程中，利用区域生长算法进行初始网的构建是非常简单的，而且 容易理解和操作，另外在一般情况下构造的初始三角嘲并不是最优的，所以我们要对其 进行优化处理，由于采集的数据点有时是不均匀的，导致初始三角网的密度也是不一样 的，当我们对其进行优化时难免会破坏模型原来的特性，所以基于网格模型的分割技术 也随之产生了，区域生长算法也在分割领域中有很重要的应用。 区域生长法的关键首先是选取种子种子选定后根据一定的生长原则将满足条件的 其他的元素归入种子一类，然后将这一类元素作为新的种子继续向外进行生长各种区 域生长方法最丰要的区别是生长的原则的不同，生长原则影响着三角叫划分结果的好 坏。种子的选取有三种方法：即以顶点作为种子、以边作为种子和以三角形作为种子。 在进行三角网划分时最常用的种子是三角形，当进行区域分割时，最常用的种子可以是 顶点，也可以是边或三角形， 2 1 11 利用区域生长渣构造初始三角网 当以三角形做为种子进行区域生长时，需要从候选点集中选择一个最优点，常用的 选择准则有昂小面积准则、最小长度准则和加权最小长度准则。生长过程需要经历以下 步骤： ( 1 ) 首先选择初始种子，即确定初始三角形。一般情况下，在给定离散点模型的适当 位置处利用定的原则构造初始三角形。 ( 2 ) 初始种子选取完毕后，以种子作为中心依照一定的生长原则向外生长三角形，逐 渐将其它离散点集归并到三角网中。 ( 3 ) 在生长过程中，要随时对已经生长好的部分进行三角l 司拓扑结构的检套，确定自 第二章三角划分算法及o p e n g l 简介 由边之间关系；同时，也要判断生长过程是否终止，确定终止条件。 文献 3 2 1 提出了基于点云数据的区域生长算法，文中使用三角形做为种子进行生长， 并且将种子三角形建立在点云数据的中心位置处，然后以初始种子做为生长点继续生 长。文章在整个三角网生成过程中都采用了动态圆的思想，在构造初始种子三角形时首 先找到位于点云数据中心处的一点v ，然后以v 为圆心以r 为半径做球，计算出球中 所包含的数据的重心位置并赋给初始三角形的一个顶点v l ，然后寻找v l 最近的点，继 续利用动态圆的方法寻找初始三角网的另一个顶点v 2 ，最后寻找距离边v l v 2 最近的点， 再以这个点为球心寻找第三个点v 3 ，这样初始种子就形成了。然后从v l v 2 v 3 的各边 出发分别进行三角网的生长，在生长过程中要判断没有被生长的每个三角形的自由边之 间的夹角如图2 2 ，若夹角小于9 0 。，则将这两个边的另外两个顶点连接起来。同时在 生长过程中要判断三角形的每条边中有没有边界边的存在，如果有，则此边界边不必向 外生长。 图2 2 检查三角网的拓扑结构 f i g2 - 2c h e c k i n gt o p o l o g yp r o c e d u r e 文献 3 3 1 主要用局部最优的贪婪策略来近似求解全局最小权重三角形问题，首先在 给定的离散点集的中心附近找到起始点p ( 砩，y p ) ，然后寻找与p 最接近的点q ( x q , y q ) ，以p q 为初始边寻找第三点r ( x r ，y r ) ，要保证r 与边p q 的距离l 最小，r 点确定以后也就是说种子 三角形a p q r 已经确定，接下来分别以a p q r 的三边为生长边向外生长，假设p q 为首选 的生长边，在选择另一项点时要使得公式( 2 1 ) 中的w 沩最小，式( 2 1 ) 中w 为加权长度值， k 为边长比例系数，l 为边长，a 为面积。 彬= k p ，口i p p p q l 2 + k l 耳一只1 2 + k 鳓l 匕一只1 2 轮警+ 警 ， 舻驴2 学 2 1 1 2 利用区域生长法分割初始三角网 选择顶点做为种子进行区域分割时，假设正在生长的种子顶点为v l ( 如图2 - 3 ( a ) 所示) ，以将与顶点v l 相关的三角形集合作为生长单元，f l l l d l 、d 2 、d 3 、d 4 和d 5 。此时， 区域生长的方法是找到与顶点v l 相邻的三角形d i 的另外两个顶点，记为v l i ，然后对顶点 v l i 按照生长准则进行衡量( 此准则可以根据不同的情况设定) ，若顶点v l i 满足区域生长 9 江南大学硕士学位论文 的条件( 即满足生长准则) ，则将以v l i 为顶点的生长单元扩展为区域的一部分，图2 3 ( a ) 中是将顶点v l l 进行了扩展，图中画圈的三角形为被扩展的三角形。 ( a ) 用顶点做为种子进行区域生长图示( b ) 用三角形做为种子进行区域生长图示 f i g2 - 3u s ev e r t e xa n dt r i a n g l e sa ss e e d st oc a l t yo u t a r e ag r o w t h 当选择三角形作为种子进行扩充时，假设t l 是区域中正在生长的三角形种子如图 2 - 3 ( b ) ，我们把与它相关的所有三角形作为生长单元，此时，区域生长的方法是分别以 种子三角形t l 的三条边v l v 2 、v 2 v 3 、v l v 3 为出发点，寻找第三点p i ，使得p i 可以与其中 的一条边构成三角形并且满足生长准则。如图2 - 3 ( b ) 中，首先考虑t l 的一条边v l v 3 ，p l 为边v l v 3 附近的点，将以点p l 、v l 、v 3 构成的三角形按照生长准则进行衡量，若p l 满足 区域生长的条件，则将t l l 扩展为该区域的一部分。 在已经建立好的三角形网格模型中，由于大片的平滑区域中三角形的面积一般都较 大，而在边缘处细节丰富的部位通常三角形的密度较大，但是面积都较小，所以文献 3 4 用面积作为区域生长的主要依据，文中用顶点做为种子进行区域生长时所采用的生长准 则为：选择与顶点的相关三角形的面积的均值做为属性对生长的顶点进行衡量，所用公 式为( 2 2 ) ；用三角形做为种子进行区域生长时所采用的生长准则为：将种子t 与欲扩 展的t 1 1 面积的差值作为衡量三角形的生长的准则，若t 与t l l 的面积属性满足生长 条件，便可将t l l 的生长单元扩展到区域中，所用公式为( 2 3 ) 。 一斗 弦 b 一墨l 0 时，g 为凹点，反之则为凸点。 r 26 、 巡，。送，移 l 圪 口 6 z = 第二章三角划分算法及o p e n g l 简介 文献【3 9 】等提出的基于平衡二叉树的三角网生成算法中，提出了怎样将不同块中的 三角网进行合并的新方法，文中对于子网的合并方法是找到左右以及上下子网之间的公 切线，图2 8 显示了左右子网公切线的寻找方法，图中上公切线为有向线段b f ，下公 切线为有向线段厄，接着是寻找某种三角网生成算法进行子网之间三角剖分，从图中可 知参与连接构网的左侧节点在有向线段b e 的左侧( 包括b 、e ) ，参与连接构网的右侧节 点在有向线段f j 的右侧( 包括f 、j ) ，那么左右子网的连接就局限在了指定的区域内， 最后在指定的区域内进行子网与子网的连接过程，这样提高了效率。 文献 4 0 】对于散乱数据点提出了基于四叉树结构的格子分块算法，该算法将离散点 逐级分块，以保证每个格子中的离散点数目相差不是很大，然后分别处理每个小块中的 离散点并对其进行三角网格构造，最后再把已经划分好的局部三角网连成一个整体，进 而生成整个点集的最终三角网模型，如图2 9 所示。 r 了t 工 tti翻ii i p 一+ 叫 i 。 lrj - 一 ( a ) 对点云以方格子( b ) 对每个方格子点云(