（计算机应用技术专业论文）散乱数据的曲面重建及绘制方法研究.pdf

摘要 近年来，随着快速、高精度的三维数字化扫描设备的不断涌现， 人们获取物体表面采样点数据变得相对简单、便宜而且准确。将这些 采样数据集转换成几何模型的过程称为曲面重建，该技术可广泛应用 于计算机辅助几何设计、计算机图形学、医学图像处理、计算机视觉 等领域。本文从三维数字化扫描设备获取的数据出发，针对基于人脸 真实照片的整形与美容虚拟手术系统e l i 存在的不足，对散乱数据的曲 面重建和绘制方法进行了研究，具体工作如下： 针对散乱数据的曲面重建，本文分析了国内外散乱数据的曲面重 建算法，比较了它们的优点和不足，汲取这些算法的优点，并结合人 脸的自身特点，提出了一种基于拟合误差驱动的自适应隐式曲面重建 算法。该算法根据拟合误差对散乱数据进行自适应拟合，通过减少对 八叉树高层节点的拟合次数，提高了算法效率；并修正单元分解方法 中的权函数，加入密度权函数，削弱散乱数据密度的不一致对重建曲 面影响。实验结果表明，该算法原理简单，重建速度快，重建效果良 好，满足三维人脸整形与美容虚拟手术系统对曲面重建的要求。 针对隐式曲面的绘制，我们发现采用传统三角化方法【2 】【3 】对开区 域上散乱数据重建的隐式曲面三角化所得的网格模型会沿着边界扩 张。为了解决这个问题，本文提出了一种边界保持的隐式曲面三角化 方法。首先计算散乱数据的立方体包围盒，并对包围盒所在空间进行 剖分，建立散乱数据的八叉树存储结构，得到立方体体素；然后以包 含散乱数据且与零值面相交的体素为种子，沿零值面进行扩张。在扩 张过程中，根据体素与散乱数据的几何特征关系对体素分类，对不同 类型的体素采用不同的三角化策略。实验结果表明，该算法能够产生 和散乱数据边界一致的三角网格。 关键词散乱数据，曲面重建，隐式曲面，三角化，边界保持 a b s t r a c t r e c e n t l y , w i t ht h ef a s ta n dh i g h p r e c i s i o nt h r e e d i m e n s i o n a ld i g i t a l s c a n n m gd e v i c e se m e r g i n gc o n t i n u o u s l y , a c q u l n n gs a m p l i n gp o m ts e t s f r o mo b je c ts u r f a c eb e c o m e sr e l a t i v e l ys i m p l e ，c h e a pa n da c c u r a t e t h e p r o c e s so fc o n v e r t i n gt h e s es a m p l i n gp o i n ts e t st og e o m e t r i cm o d e li s c a l l e ds u r f a c er e c o n s t r u c t i o n t h i s t e c h n o l o g y i s w i d e l y u s e di n c o m p u t e ra i d e dg e o m e t r i cd e s i g n ，c o m p u t e rg r a p h i c s ，m e d i c a li m a g e p r o c e s s i n g ，c o m p u t e rv i s i o na n do t h e rf i e l d s a c c o r d i n gt ot h es a m p l i n g p o i n ts e t sa c q u i r e db yt h r e e d i m e n s i o n a ld i g i t a ls c a n n i n gd e v i c e s ，t h i s t h e s i sf o c u s e so nt h el i m i t a t i o n so ft h ev i r t u a lo p e r a t i o ns y s t e mf o r b e a u t i f y i n gl a d v sf a c e 川a n dm a i n l ys t u d i e so ns u r f a c er e c o n s t r u c t i o n a n dr e n d e r i n g t h ec o n c r e t er e s e a r c hw o r kc o n s i s t sa sf o l l o w s ： a c c o r d i n gt ot h es c a t t e r e dd a t as u r f a c er e c o n s t r u c t i o n ，t h i st h e s i s r e f e r st ot h es c a t t e r e dd a t as u r f a c er e c o n s t r u c t i o na l g o r i t h m sa th o m ea n d a b r o a d ，c o m p a r e st h e i ra d v a n t a g e sa n dd i s a d v a n t a g e sa n dd r a w st h e s e a l g o r i t h m s a d v a n t a g e s ，a n dc o m b i n e sw i t ht h eh u m a nf a c ec h a r a c t e r i s t i c s ， a n dp r o p o s e sa na d a p t i v ei m p l i c i ts u r f a c er e c o n s t r u c t i o na l g o r i t h md r i v e n b yf i r i n ge r r o r t h i sm e t h o da d a p t i v e l yf i t ss c a t t e r e dd a t aa c c o r d i n gt o f i t t i n ge r r o r s ，i m p r o v e st h ea l g o r i t h me f f i c i e n c yb yr e d u c i n gf i r i n gt i m e s o fo c t r e e sh i g hn o d e s ，a n dm o d i f i e st h ew e i g h tf u n c t i o n so ft h ep a r t i t i o n o f u n i t ym e t h o da n dw e a k e n st h ee f f e c to fi n c o n s i s t e n c yd e n s i t yo ft h e s c a t t e r e dd a t ao ns u r f a c er e c o n s t r u c t i o na l g o r i t h mb ya d d i n gd e n s i t y w e i g h tf u n c t i o n t h ee x p e r i m e n t a lr e s u l t si n d i c a t et h a tt h ea l g o r i t h m s p r i n c i p l ei ss i m p l ea n dt h er e c o n s t r u c t i o ni sf a s tw i t hg o o de f f e c t w h i c h a l s om e e t st h e s u r f a c er e q u i r e m e n to ft h ev i r t u a lt h r e e d i m e n s i o n o p e r a t i o ns y s t e mf o rb e a u t i f y i n gl a d y sf a c e h o w e v e r , w h e nw eu s et h ec l a s s i cm a r c h i n gc u b e sa l g o r i t h mf o r i m p l i c i ts u r f a c et r i a n g u l a t i o n ，w ef i n dt h a ti st h et r i a n g u l a rm e s hm o d e l e x p a n d sa l o n gw i t ht h e i rb o u n d a r yf o rs c a t t e r e dd a t ar e c o n s t r u c t e df r o m o p e nd o m a i n i no r d e rt os o l v et h i sp r o b l e m ，t h i st h e s i sp r e s e n t sa n i m p l i c i ts u r f a c et r i a n g u l a t i o nm e t h o dw i t hb o u n d a r yp r e s e r v e d f i r s t l y , w ec o m p u t et h ec u b i cb o u n d i n gb o xo ft h es c a t t e r e dd a t aa n dd os p a c e s u b d i v i s i o nf o rt h e s e b o u n d i n gb o x e s ，a n de s t a b l l i s ho c t r e es t o r a g e s t r u c t u r ef o rt h e s es c a t t e dd a t aa n do b t a i nc u b i cv o x e l s s e c o n d l y , w e c h o o s eav o x e lw h i c hc o n t a i n ss c a t t e r e dd a t aa n di n t e r s e c tw i t ha e r o i i i s o s u r f a c ea ss e e da n de x p a n da l o n gw i t ht h ez e r oi s o s u r f a c e d u r i n gt h e e x p a n d i n gp r o c e s s ，w eu s ed i f f e r e n tt r i a n g u l a rm e t h o ds t r a t e g i e sf o rt h e s e v o v e l sa c c o r d i n gt ot h e i rt y p e sd e t e r m i n e db yt h er e l a t i o n s h i po fv o v e l a n dt h eg e o m e t r i cf e a t u r e si ns c a t t e r e dd a t as e t t h ee x p e r i m e n t a lr e s u l t s i n d i c a t et h a tt h ea l g o r i t h mc a np r o d u c eat r i a n g u l a rm e s hw h i c hk e e p st h e b o u n d a r yo ft h es c a t t e r e dd a t a k e yw o r d ss c a t t e r e dd a t a ，s u r f a c er e c o n s t r u c t i o n ，i m p l i c i ts u r f a c e ， t r i a n g u l a t i o n ，b o u n d a r yp r e s e r v e d 原创性声明 本人声明，所呈交的学位论文是本人在导师指导下进行的研究 工作及取得的研究成果。尽我所知，除了论文中特别加以标注和致谢 的地方外，论文中不包含其他人已经发表或撰写过的研究成果，也不 包含为获得中南大学或其他单位的学位或证书而使用过的材料。与我 共同工作的同志对本研究所作的贡献均已在论文中作了明确的说明。 作者签名： 搿峄 学位论文版权使用授权书 本人了解中南大学有关保留、使用学位论文的规定，即：学校 有权保留学位论文并根据国家或湖南省有关部门规定送交学位论文， 允许学位论文被查阅和借阅；学校可以公布学位论文的全部或部分内 容，可以采用复印、缩印或其它手段保存学位论文。同时授权中国科 学技术信息研究所将本学位论文收录到中国学位论文全文数据库， 并通过网络向社会公众提供信息服务。 作暑毓犁峰喜昴签名掣嗍盟皑月型日 硕十学位论文第一章绪论 1 1 课题来源 第一章绪论 近年来，实验室课题组与闩本k i s t e m 公司合作，联合丌发了一个基于人脸 真实照片的整形与美容虚拟手术系统，简称b y u p a q 系统。用户可以在手术前 输入人脸的真实照片，利用b y u p a q 系统设计的多种操作算子，交互式地在人脸 真实照片上实施虚拟手术，如眼睛放大、鼻子隆高、嘴唇修薄、除斑、去痣等操 作( 如图1 - 1 所示) ，经过一系列的交互式操作，人脸逐渐变得美丽、漂亮，最终 可获得虚拟整形和美容后的照片。该系统是从图像处理的角度出发，能够使整容 者在手术前看到手术后的整容效果，为医生和整容者的沟通提供了方便。然而， 该系统缺乏对各种操作算子的定量计算，如鼻子隆高的具体高度，隆高所需要材 料的多少等。因而，较难用于具体的医学使用环境，为医生的手术工作提供详尽 的数据指导。为此，本课题结合湖南省自然科学基金项目“基于点( 在本文中指 散乱点数据，也称为散乱数据) 重建人脸面部器官三维模型的关键技术研究”( 项 目编号：0 6 j j 2 0 0 6 5 ) ，开展了一系列的研究工作。 手术两手本中手术后 ( a ) 眼睛放大 麓黧翟 手术谪手术中手术后 ( b ) 鼻子隆高 ；确阌藏 硕士学位论文 第一章绪论 ( 2 ) 基于点模型的人脸面部器官三维模型的重建方法；( 3 ) 人脸面部器官重建模型 的绘制方法；( 4 ) 人脸面部器官三维模型的变形，如眼睛放大、鼻子隆高、嘴唇 修薄；( 5 ) 人脸面部器官的纹理映射等。本文是该项研究的先导性工作，旨在对 基于点模型的三维模型重建和绘制为主要研究内容，为后继三维模型变形和三维 人脸整形与美容虚拟手术系统的研究奠定理论基础。 1 2 研究背景 近几年来，计算机图形显示与图像处理技术发展很快，无论是图形硬件设备 还是软件技术都取得了明显的进步。在硬件方面，早期的图形数据采集设备只能 拾取二维的图形数据，如常用的鼠标、操纵杆、光笔等，只能在图形显示屏上拾 取二维的点坐标，而不能直接地对现实中的物体进行三维数据采集，这使得带有 复杂曲面的三维形体造型只能通过其它方式来实现，如基于参数的三维建模、基 于标准形体的三维建模以及基于图像的三维建模，这些方法虽然解决了不少问 题，包括复杂曲面的建模，但由于没有直接采集实际物体表面的三维数据，因此 所建立的几何模型精度不够，导致三维模型的真实感不强。 随着激光扫描仪、计算机辅助断层扫描仪、接触式扫描仪等三维数据采集技 术和硬件设备的日臻完善，使得获取实物表面的三维数据采样模型变得相对简 单、便宜且准确，也使得直接采集实际物体表面的三维数据，重建物体的三维数 字模型成为可能。但是，基于采样点集的三维建模技术，由于实物的几何和拓扑 信息未知，并且可能非常复杂，而且，采样点集中包含的采样点集可能非常庞大 ( 如斯坦福大学计算机图形学小组扫描的l u c y 模型含有5 8 ，2 4 1 ，9 3 2 个采样点) ， 采样点集的采样密度不均匀，还可能存在采样噪声等原因，现有算法在正确性、 有效性、健壮性等方面都面临严峻的考验，不能满足现有的应用需求。 另一方面，在计算机图形学中，曲面的表示方式主要包括两种形式：参数曲 面和隐式曲面。参数曲面绘制相对简单，在计算曲率、边界等操作上相当方便， 因而在传统计算机图形学中颇受青睐。然而，由于隐式曲面可以方便的判定空间 点和曲面的位置关系，光滑性较高，在表现人体肌肉、水滴、云、树干等物体的 造型和动画方面具有很大的优势，因此在在医学图像处理、分子建模、计算机辅 助设计和有限元分析等领域中被广泛应用。在隐式曲面绘制过程中，主要采用两 种方式：光线跟踪和隐式曲面多边形化。光线跟踪算法直接从隐式曲面的公式表 述得到绘制结果，因此可以得到高质量的图形效果，即使将图形放大若干倍，也 不会产生多边形化所产生的不连续感。光线跟踪的核心计算在于求光线和隐式曲 面的交点，由于隐式曲面通常都比较复杂，因此光线跟踪的缺点是速度通常较慢。 为此，隐式曲面多边形化是成为隐式曲面绘制的另一常用算法，这是因为大多数 2 硕士学位论文第一章绪论 的图形加速卡和商业动画软件包都支持高性能的、基于多边形的绘制，因此绘制 速度很快。但该技术在抽取等值面时会盲目计算大量无关节点的距离值，算法效 率低，不仅如此，这些算法大都是从隐式曲面出发，不考虑隐式曲面的来源和具 体应用，因而，传统隐式曲面三角化方法【2 】【3 】在具体应用过程中也不同程度的存 在各种问题，如本文提出的边界保持的隐式曲面三角化方法就是针对开区域上散 乱数据重建隐式曲面三角化所得的网格模型不能有效的表现散乱数据的边界这 个问题。 1 3 研究意义 基于散乱数据的益面重建和绘制问题，是计算机图形学领域所研究的热门问 题，国内外的许多研究小组对该课题进行了大量的研究。匈牙利人v a r a d y 组织 了研究小组，对点模型的数据分块、曲面拟合、曲面过渡、自由曲面和规则曲面 模型的建立等工作进行了研究；c a r d i f 大学的m a r t i n 和v a r a d y 等对规则曲面的 拟合、约束的识别和添加、b r 印结构的建立等方面进行了深入研究；o h i o 州立 大学的m e n q 等对三坐标测量技术、自由曲线曲面拟合、数据分块等进行了探讨； 国内以浙江大学为首的多个高校，包括上海交通大学、西北工业大学、北京航空 航天大学、华中科技大学、南京航空航天大学等高校均对散乱数据进行了较为深 入地研究，由此，本文的研究工作应该是具有广泛普遍性。从理论上说，这是一 个极具一般性的问题；而在实践中，其研究可用于许多领域，如逆向工程( r e v e r s e e n g i n e e r i n g ，l 也) 中的曲面重建，还有文物数字化、数字博物馆、虚拟现实和医 学图像以及机械制造等领域，下面就一些典型的应用领域予以说明。 1 3 1 逆向工程中的应用 随着三维数据测量技术的进步和发展，逆向工程迅速发展为- f - j 新兴的学科 和技术，并成为计算机辅助设计计算机辅助制造( c o m p u t e ra i d e d d e s i g n c o m p u t e ra i d e dm a n u f a c t u r i n g ，c a d c a m ) 技术领域的研究热点1 4 】【5 l 6 l 。它 的出现主要出于以下两种需要： ( 1 ) 某些产品采用手工设计即可满足实际需要，或在计算机出现以前相关的 工艺和技术就己成熟。但是，出于降低人力成本和缩短产品周期考虑，需要引入 c a d c a m 技术。但产品设计并不是全部用c a d 软件来完成，而是在现有的产 品模型基础上做一些局部改进。这就需要对产品模型数字化，再对产品的外型进 一步修改、分析和设计。 ( 2 ) 某些复杂产品，先用手工方式设计出一个模型后，根据实际使用时的舒 适度对模型进行修改。如此反复，直至得到满意的模型为止，然后将模型数字化， 3 硕士学位论文 第一章绪论 再用c a d 软件进行后续设计和分析，整个过程比完全采用c a d 软件设计更为 有效。 以上两种需求存在一个共同的特点，那就是模型数字化。当需要导入计算机 内部的实物是简单而且规则的表面，则在计算机内部重建这一形体不复杂；但是， 如果需要导入计算机内部的实物具有相对复杂的曲面外形，则在计算机内部重建 这一形体是一个比较复杂的问题。这时，解决问题的通常做法是从实物上采集到 一定数量的离散点，利用这些点来对原始曲面进行模拟重构以满足应用的需要。 如概念汽车黏土模型，机械工程师用黏土模型表达他们创造的概念设计后，通过 激光扫描仪采集三维散乱数据，然后进行拓扑重建、网格优化、几何重建，曲面 的修改、光顺和优化设计。与此同时，由于目前专业反求软件，功能相对有限， 且不宜处理大量点云数据，因此，散乱数据的曲面重建更具有实际应用价值，它 改变了c a d 系统从从图纸到实物的传统设计模式，为产品的快速开发及原型化 设计提供了一条新途径。 1 3 2 文物数字化中的应用 我国数千年的文明史为后人留下了丰富而珍贵的自然文化遗产，但是，随着 时间的流逝，也随着人类活动的日益影响，这些遗产不断遭到破坏。如何利用先 进的技术手段来保护这些宝贵遗产，成为迫在眉睫的问题。随着虚拟现实技术的 兴起，文物数字化技术初露端倪，为文物的保护提供了新的思路，主要体现在文 物的复原研究中破碎文物的数字化和数字化博物馆等工作中。 由于人为或者自然损坏，大部分出土的文物都存在不同程度的破损，尤其是 对于出土的瓷器和陶器。利用三维数据获取设备，采集破碎文物表面的数据信息， 提取每个碎片的边缘，通过这些边缘代表的空间曲线进行匹配，达到拼合破碎文 物的目的。通常，破损文物的修复还可以结合该文物的相关历史资料信息，以提 高文物修复的准确度。 数字化博物馆是人们利用计算机等设备，在一个虚拟的环境中，以互联网的 方式为用户提供文物的数字化展示。为了尽可能真实的再现这些文物，我们需要 用三维扫描技术将文物的三维信息( 几何信息纹理信息) 精确的采集下来，再利用 三维重建技术【7 】【8 】，重构出高分辨率的三维虚拟文物。利用这些模型，我们便可 以从任何角度真实的将文物绘制在计算机中。 利用三维扫描技术得到的模型，还可以通过计算机控制，对文物进行清洁和 维护。同手工操作方式相比较，用这种方式对文物本身的破坏程度要小的多。美 国斯坦福大学的米开朗基罗工程就是利用这种技术来对塑像进行清理的。 4 硕士学位论文 第一章绪论 1 3 3 医学图像中的应用 曲面重建的另一个应用就是医学图像。在医学研究中，经常会有一些器官的 生理切片，这是用医学薄片切片机得到的。把一系列这样的二维的薄片平行地组 合起来，形成一个栈，就可以得到一个完整器官的散乱数据集合【9 】【1 0 1 ，通过对重 建模型不同方向观察、剖切，使得医生可以对感兴趣的部位的大小、形状和空间 位置不仅有定性的认识，也可获得定量的认识。类似的情况是，利用超声传感器 探测心脏的形状，通过将一个探头伸入食道中，得到心脏的边缘数据。同薄片切 片机相比，利用超声得到的边缘数据不是平行的，因为探头可以获取不同角度、 不同位置的边缘数据，故所得的数据要根据它的密度情况来具体处理。对于这些 边缘数据，采用散乱数据重建曲面的方式生成曲面表示，可以更有效的进行观察、 分析等处理。 1 4 本文的主要工作 在实验室现有的基于入脸真实照片的整形与美容虚拟手术系统( b y u p a q 系 统) 的基础上，结合计算机图形学领域内的新热点基于散乱数据的曲面重建 技术，开展了一系列的工作。主要内容如下： ( 1 ) 散乱数据的曲面重建和绘制方法研究总结。在阅读了大量国内外相关文 献的基础上，对散乱数据的曲面重建和绘制方法研究进行了深入的剖析，把散乱 数据曲面重建的方法分为5 类( 详见2 1 节) ，并对与本文相关的曲面拟合方法 进行了详细的分析和比较，得出了它们的优缺点；此外，也对隐式曲面绘制的相 关方法进行了归类分析( 详见2 2 节) ，并对隐式曲面的多边形化方法进行了详 尽的介绍。 ( 2 ) 研究散乱数据的曲面重建算法。分析国内外基于散乱数据的曲面重建算 法，比较了他们的优点和不足，并结合人脸的自身特点，提出了一种基于拟合误 差驱动的自适应隐式曲面重建方法( 详见第三章) ，根据拟合误差对散乱数据进 行自适应拟合，并改变传统方法从八叉树中顶层节点开始拟合，减少了拟合次数， 加快了重建速度；并修正单元分解方法中的权函数，加入了密度权函数，削弱由 于散乱数据密度的不一致对重建曲面的负面影响。实验结果表明，该算法原理简 单，重建速度快，重建效果良好，能满足三维人脸整形与美容虚拟手术系统中对 重建曲面的要求。 ( 3 ) 研究隐式曲面的三角化算法。在散乱数据的曲面重建算法研究过程中， 我们发现传统的隐式曲面三角化算法存在一个问题对开区域上散乱数据重 建隐式曲面三角化所得的网格模型不能很好的表现散乱数据的边界，本文结合重 建曲面对边界的的要求，提出了一种边界保持的隐式曲面三角化方法( 详见第四 5 硕士学位论文 第一章绪论 章) ，根据散乱数据的空间分布，控制等值面的抽取范围，最终可以获得边界保 持的三角网格模型。 1 5 本文的组织结构 本文共分五章，各章的内容安排具体如下： 第一章：绪论。阐述了本文的课题来源、研究背景、曲面重建和绘制方法的 研究意义、课题的研究内容和论文的结构安排。 第二章：散乱数据的曲面重建和绘制方法综述。论述了散乱数据的曲面重建 和绘制技术的发展和国内外研究现状，分别对散乱数据的曲面重建和隐式曲面三 角化方法进行了分类，并对这些算法进行了细致的分析和比较，得出了各类算法 的优缺点。 第三章：基于拟合误差驱动的自适应隐式曲面重建。提出了一种新的隐式曲 面重建算法。根据拟合误差对八叉树中的节点进行自适应的拟合，通过对拟合过 程和权函数的修改，提高算法效率，最后给出了一些实验结果和分析。 第四章：一种边界保持的隐式曲面三角化。提出了一种边界保持的隐式曲面 三角化方法，详细介绍了现有隐式曲面三角化方法存在的问题，并对改进算法进 行了详细说明。最后给出了一些实验结果和分析。 第五章：总结与展望。对本文的研究成果进行总结，并探讨了进一步研究的 方向。 6 硕士学位论文第二章散乱数据的曲面重建和绘制方法综述 第二章散乱数据的曲面重建和绘制方法综述 2 1散乱数据曲面重建算法综述 散乱数据是点云数据的一种，而点云数据是指在同一空间参考系下表达目标 空间分布和目标表面特性的海量点集合，它是表达物体的一种最简单的方式【l l 】， 可以用于表示任意物体表面。但是，由于点云数据缺乏必要的拓扑信息，所以， 在实际应用中，通常需要将点云数据的拓扑结构重建出来，即把点元数据重构成 多边形网格或者拟合成曲面。 按照点的组织方式，可以把点云数据分为深度点元数据、轮廓线元数据和散 乱点元数据，散乱点元数据就是本文所指的散乱数据。由于各类型点云数据的组 织方式不同，故其曲面重建方式和难易程度也各不相同，下面对各类型点元数据 予以分别介绍。 ( 1 ) 深度点元数据单一方向的深度点元数据( 如图2 1 ) 只能表示拓扑简单的 曲面，其曲面重建问题通常比较简单。但若要表示任意拓扑曲面，则需要多个方 向的深度点元数据。现有的研究1 1 2 1 1 1 3 】1 1 4 】表明，将多个方向的深度点元数据重建 曲面拼合成一个多边形分段线性曲面是一个相当困难的问题。 图2 - 1 深度点元数据曲面重建 ( 2 ) 轮廓线元数据相对于散乱点元数据，轮廓线元数据只不过是点与点之间 沿截线方向的距离比其它方向要小很多( 见图2 2 ) 。轮廓线元数据的曲面重建问 题也得到了很多研究者的深入研究和探讨1 1 5 】。从数据理论的角度而言，轮廓线元 数据也可以表示任意拓扑曲面，但要寻找一种重建算法以实现复杂拓扑结构的曲 面重建通常比较困难。 7 硕士学位论文第二章散乱数据的曲面重建和绘制方法综述 图2 - 2 轮廓线元数据曲面重建 ( 3 ) 散乱点元数据采样点数据的分布可以是毫无规律的，因而散乱点云数据 更具有普遍性( 见图2 - 3 ) ，基于散乱数据的曲面重建算法【1 6 】【1 7 】【1 8 j 【l9 】【2 0 】【2 l j 也具有 更好的适应性，但这并不是说它可以取代其它曲面重建的方法。 j + 墓一， 警j - 0 = ? 移，+ ；_ ： 冉+ + + + ：一 + + ；：4 ，- ： + o 二二 + + 7 + * ，+ + + + 母+ 十 。 + + f 专+ + + + 。五 + 士 ，一+ 、主：蠢参+ 气一矗。 图2 - 3 散乱点元数据及其曲面曲面重建 通常，点云数据的组织方式是由获取数据的方法决定的。常用的表面数据采 集方法中，通常只有工业c t 方法获得的数据是按断层截面上的截线组织的，而 其他测量方法在大多数时候，尤其是物体的表面的拓扑结构和几何形状比较复杂 时，都是得到无结构的采样点集数据，因此，基于散乱数据的曲面重建问题无论 在理论还是实用上都具有更加重要的价值。按照重建方式【2 2 1 不同，可以把散乱数 据的曲面重建方法分为： ( 1 ) 曲面拟合利用计算机辅助几何设计( c o m p u t e ra i d e dg e o m e t r i cd e s i g n c a g d ) 和数字分析技术，用一组曲面片表示重建物体。 ( 2 ) 分段线性重建通过建立多面体化( 主要是三角化) 的表面，插值或近似 给定采样数据集。 ( 3 ) 基于物理的重建通过赋予曲面一定的物理属性，使曲面在内、外力作用 下变形，直至近似给定采样数据集。 硕士学位论文 第二章散乱数据的曲面重建和绘制方法综述 ( 4 ) 基于神经网络的重建利用神经网络强大的泛函逼近能力、容错性能和联 想力来拟合给定的采样数据集。 ( 5 ) 其它方法。 在这些方法中，曲面拟合法又可以分为隐式拟合和显示拟合。由于本文采用 的是曲面拟合这一类方法，因而，本文只对这类方法进行详细介绍，并通过对典 型算法的分析和比较，阐述各方法的特点、应用及不足。 2 1 1 隐式拟合 通过定义函数厂( p ) ：r 3 寸r ，保证散乱数据集合x = ，x n j 逼近函数的零 集。根据选用拟合函数的形式不同，可将隐式拟合分为分为参数形式的函数拟合 和隐函数拟合，前者用x ，y ，z 坐标上的多面体为函数，生成如x = ，：( t l ，w ) ， y = 正( “，w ) ，z = a ( “，w ) 形式的代数面；后者选用势函数或者场函数，如b l i n n 的高斯密度函数、n i s h i m u r a 的分段二次多项式和w y v i l l 的六次多项式分别可以得 到水滴状物体、元球和软物体模型。下面分别介绍隐式拟合中常用的几种曲面拟 合方法。 ( 1 ) 二次曲面拟合方法 三元二次方程所表示的曲面称为二次曲面，由于大多数需要重建的对象是由 规n - - 次曲面组成，因而二次曲面的拟合方法得到国内外研究者的广泛研究。 p r a t t 掣2 3 】利用平方h a u s d o r f f 距离之和的最小化，直接用球、立方体、圆柱等简 单二次曲面拟合散乱数据。由于简单二次曲面的解析表达十分简洁，因而难以重 建复杂拓扑的曲面形状。 超二次曲面通过在简单二次曲面方程中引入额外参数，大大提高了形状描述 能力。p e n t l a n 等【2 4 】利用隐函数易于进行曲面求交计算的特性，用变形超二次曲 面，以模式变形描述整体形状，以曲面沿表面法向的偏移表达局部细节，这种混 合了隐函数参数曲面方法以单一的隐式方程同时描述曲面的局部和全局特性， 为描述物体形状提供了一种通用的隐函数形式；z h o u 等【2 5 】将超二次曲面的特征 指数由常数扩展到函数形式，可以用于重建光滑变形的非对称体。 ( 2 ) b 样条曲面拟合方法 作为矩形域参数曲面的代表，b 样条具有表示和设计自由曲线曲面的强大功 能，在曲面重建中被广泛采用。h a l s t e a d 等【2 6 1 提出了利用b 样条曲面构造高精度 逼近需要重建的曲面法向的方法，该方法虽然不能重建有尖点和棱角的曲面，但 是它以b 样条为工具，为包括b e z i e r 在内的各类型参数曲面重建工作开辟了道 路。l e e 掣2 7 】给出了层次b 样条法，通过构造基于层次结构的控制点网格，对粗 糙网格进行逐步自适应细化，直至其达到逼近精度。该方法连续性良好，有利于 9 硕士学位论文 第二章散乱数据的曲丽重建和绘制方法综述 实现曲面的多分辨率表示和分析，只是它不易合理选择细化区域，而且采样点集 的组织形式受到一定的限制。p i g e l 和t i n e r 等【2 8 】提出了用b 样条曲面逼近离散 采样点的方法，他们假设通过数据预处理后，采样数据点可变成一组具有矩形分 布形式的点q 其中i = l ，2 ，l ，= l ，2 ，m ，从而可以构造一张c 川矿”连续 的曲面作为重建所需的曲面。 b 样条具有统一、通用、有效地标准算法，b 样条曲面也具有直观性、凸包 性、局部性、连续性与光滑性好、低次样条拟合稳定等优点，但它难以解决以下 问题：( 1 ) 多项式中的二次项难于精确表达；( 2 ) 需要定义矩形拓扑网格；( 3 ) 难 以用单一b 样条面片重建任意拓扑曲面；( 4 ) 对于拓扑结构复杂的曲面，难以自 动构造b 样条面片网和对面片上数据点进行参数化；( 5 ) 难以同时满足相邻b 样 条面片间的切面连续和保持面片网与数据点的拟合。 ( 3 ) n u r b s 曲面拟合方法 相对于b 样条益面，n u r b s 曲面的灵活性更大，效率和简洁度更高。它能精 确表示解析实体和自由曲面，是s t e p 标准中描述产品几何形状的唯一方法。但 因引入新的未知权重，重建算法复杂性变大，所能处理的曲面形状也受到一定限 制。w e i y i n 等【2 9 】的工作很具有代表性，他们首先根据边界构造一个初始曲面， 然后将型值点投影到这个初始曲面上，接着根据投影位置算出其参数分布，从而 解决散乱数据得参数分配问题，根据这一型值点参数分配拟合出一张新的 n u r b s 曲面，然后再对型值点参数进行优化，使所拟合曲面离给定型值点误差 最小。但是，这种方法不适合大规模散乱数据点集，而且当曲率变化较大时，重 建所得到的结果可能仍是散乱点。为解决这个问题，b r a d l e y 等【3 0 】提出一种先压 缩后拟合的两步方案，首先采用函数方法，如s h e p a r d 插值法构造插值于数据点 的曲面模型，然后在曲面上构造拓扑矩形网格，再采用n u r b s 方法拟合，生成 最终重建曲面，这种方法的局限性在于它只适于曲率变化较小的情况。除此之外， w e i r 等【3 1 】通过手工布点使b 样条曲线型值点随曲率增大而增加，但手工布点效 率低，不易实现布点的优化；来新民等【3 2 】使用基于曲率测度的方法将数据自适应 压缩后再进行曲面拟合。 n u r b s 曲面的主要优点可以归纳为：( 1 ) 为标准解析几何形状( 如二次曲面 和旋转曲面) 和自由曲面( 如有理和非有理b e z i e r 曲面) 提供了一种统一的数学 表达形式。不仅能对它们进行精确的表示，而且拥有一致的数据存储方式；( 2 ) 通过对权因子和控制顶点的修改，能够灵活地控制曲面，具有很强的交互设计能 力；( 3 ) 计算简单且具有一定的数值稳定性；( 4 ) 具有清晰的几何意义，为设计提 供了极大的便利；( 5 ) 经过多年的发展，已经形成了一整套几何设计功能集，如 节点的删除、插入、优化以及降阶、分段等，而且这些功能贯穿于设计、分析、 l o 硕士学位论文第二章散乱数据的曲面重建和绘制方法综述 处理、检验等各个阶段；( 6 ) 在缩放、旋转、移动等基本变换以及平行和透视投 影变换下，具有几何不变性。但是，n u r b s 曲面在实际应用中也存在着一些难 以解决的问题，主要问题包括：( 1 ) 对于某些曲面，与传统的表达形式相比，需 要额外的存储空间；( 2 ) 在重建过程中，权因子选择不当可能导致很坏的参数化， 使重建曲面发生歧变：( 3 ) 在某些应用上，n u r b s 曲面比不上传统形式和技术， 如曲面之间的求交；( 4 ) 很难处理曲面搭接和重叠等情况；( 5 ) 某些基本算法存在 数值稳定性问题，如重建曲面上点的参数值；( 6 ) 由于n u r b s 曲面的控制网格 必须是规则矩形网格，这使其在某些应用中存在着严重的局限性，特别在处理裁 剪曲面的表示和曲面地光顺拼接时工作量很大；( 7 ) n u i 氇s 曲面也很难表示局部 特征，如局部的棱边或者夹一个局部的平面片。 ( 4 ) 细分曲面拟合方法 细分曲面与传统的曲面表示方法不同，它通常没有显式表达式，而是一个网 格序列的极限曲面。从初始多面体网格开始，按照某种细分规则( 通常为加权平 均) ，递归地计算新网格上的每个顶点。随着细分的不断进行，控制网格被逐渐 磨光，最终多边形网格收敛到一张光滑曲面。 随着c a t m u l l c l a r k 细分曲面的出现，基于不同细分规则的细分曲面不断涌 现，如l o o p 模式、b u t t e r f l y 模式、d o o s a b i n 模式等。h o p p e 掣”】率先于1 9 9 4 年将细分曲面应用于曲面重建，该方法首先从散乱数据点集出发，构造密集的三 角网格，估计待重建表面的拓扑结构，然后通过求解庞大的非线性方程组来求出 细分曲面控制网格的顶点位置，因而其曲面重建时间相当长；而后，s e d e r b e r g 等【3 4 】和李桂清掣3 5 】提出了在光滑曲面上构造非光滑特征的算法；s u z u k i 等阳提 出了迭代求解细分曲面控制网格顶点位置的细分曲面重建方法，该方法虽然花费 的时间较少，但由于没有考虑待建曲面的特征信息，因而不能反映出待重构物体 的细节特征，只适用于拓扑结构与球相近的曲面重建；周海等【3 7 】提出了散乱数据 点的细分曲面重建算法，通过对有特征的细分控制网格极限位置分析，按照拟合 曲面与数据点的距离误差最小原则，对细分曲面控制网格循环进行调整、优化、 特征识别、自适应细分等过程，使得细分曲面不断地逼近原始数据。该算法不适 合稀疏数据的曲面重建，这是因为稀疏数据的采样点过少，因而不可避免地会出 现多个控制网格顶点的极限位置与同一个数据点匹配，导致重建网格自交。 总之，细分曲面可看成是参数曲面在任意拓扑网格下的扩展，它除具简单性、 表示的一致性之外，还能克服参数曲面难以实现任意拓扑网格中面片裁剪和面片 之间的光滑连接的问题，几乎可以描述任意复杂的光滑曲面，其层次性和递归性 使之与多分辨率分析紧密相连，保证了数值稳定性。细分曲面常用于特征动画设 计和复杂雕塑曲面，但由于细分曲面上的点并非显式给出，这也给曲面的几何计 硕士学位论文 第二章散乱数据的曲面重建和绘制方法综述 算等带来了一定的困难。 ( 5 ) 其他曲面拟合方法 散乱数据的曲面重建方式种类繁多，国内外很多的专家都对这方面进行了深 入的研究，但是，这些算法大多是基于b l i r m 局部隐式曲面【3 8 】混合思想。除上四 个方面的拟合算法之外，典型的算法大致如下。 c a r r 等【3 9 】较早地提出了用多项式径向基函数( r a d i a lb a s i sf u n c t i o n ，r b f ) 重 建曲面的方法，该方法以径向基函数为基函数，通过求解线性方程组得到插值函 数。由于约束点的个数就是线性方程组的阶数，故约束点的个数往往较多，因此 求解方程所需时间长、占用内存大，并且方程组可能无解；a l e x a 等【删采用基于 投影的形状逼近方法，在局部性和直接重采样方面有所突破，但是，投影需要求 解非线性移动最小二乘问题，而这会使大部分形状操作非常费时，因而重建速度 很慢；o h t a k e 等【4 1 】对大规模数据点采用多层次单元分解方法( m u l t i - 1 e v e lp a r t i t i o n o f u n i t y , m p u ) 进行了基于局部的曲面重建，对采样点根据其采样点数及法向误差 值对八叉树进行自适应的剖分，然后，对每个八叉树节点，根据采样点的法向判 断出是否有明显特征( 如棱边、尖角之类) 的存在，继而进行相应的曲面拟合处 理。该方法在重建速度和效果方面取得了较好的结果，但它不支持严格的数学推 理和证明；n e l s i o n 等f 4 3 】提出了一种基于径向h e r m i t e 基函数的加权对散乱数据 点的位置和法向进行插值，重建的曲面经过采样数据点，且保持曲面经过散乱点 处的法向。该方法是通过邻域内的个点的信息( 即法向及位置值) 直接求取函数 值，其重建速度快于前面的任何一种的曲面重建方法( 如r b f 、m p u ) ，但是该 重建方法不能处理带有噪声的散乱点数据。 除上述算法外，b a j a j t 4 4 用口一s h a p e 方法建立了初始的分片线性曲面，并用 口一s h a p e 定义的标量距离函数进行累进的、自适应的分段线性拟合，生成c 1 连 续的插值曲面，并进一步探讨了口值的自动寻优【4 5 1 。该类方法具有口一s h a p e 方 法的优点，如最接近的反映散乱数据对象；s a p i d i s 等【删人提出了基于区域增长 的多项式曲面重建方法，用数目尽量少的具有z = 厂“y ) 表示形式的函数曲面片 来逼近三维采样数据点。此外，z h a o 等【4 7 】提出了一类基于极小曲面模型( m i n i m a l s u r f a c el i k em o d e m s l m ) 和偏微分方程( p a r t i a ld i f f e r e n t i a le q u a t i o n ，p d e )