（计算机应用技术专业论文）基于感知特征的网格处理算法的研究.pdf

摘要+ 随着数字媒体的快速发展，计算机图形学以及计算机动画领域中对于数字模 型的需求日益增加，因此如何快速而高效地获取数字模型成为计算机图形学领域 中的一个重要的研究课题。数字模型的表示力法是对数字媒体进行进。步处理的 基础。传统的参数曲面或者隐式曲面的表示方法在拓扑方而受到较大的限制。基 于三角形网格的表示方法则因为其结构简单，拓扑限制少，并n 适合于当前讣算 机显示系统的管道线设置而受到日益重视。因此，基丁网格表示的处理算法得到 快速的发展。 感知特征是人类认识世界的丰要依据，在三维模型中，结构特征构成人类认 识和识别模型的主要的几何特征。由于数字娱乐以及工业的需要，在数字模型的 处理算法中，如何使处理后的模型能够有效的遵循人在视觉上的认知特点显得特 别重要。本文针对当前基十网格表示的数字模型在获取和处理算法中存在的问 题，从模型的感知特征出发，提出了新的算法。首先，设计了一种可以重建显著 特征的网格填充算法：其次，使用感知特征作为尺度，分别设计丫针对自然物体 模型和牙齿模型的交互式的网格分割算法；最后，设计了种可以重建尖锐特征 的逆向i j o o p 细分算法，同时提出了渐进细分曲面的概念。本文的工作主要包括 如下的网个方面： 1 ) 网格修复算法是从重建后的网格获取健壮的数字模型的一个重要步骤。本 文提出了一种基于特征线的网格修复算法，克服了当前空洞填充算法中不 能够有效恢复显著特征的缺点。本文将特征线，这一网格的结构特征信息， 引入到待填充的网格模型中，使用三角化算法来封闭空洞，采用区域生长 算法来确定缺失区域中所丢失的显著特征的拓扑，缺失区域的顶点以及特 征点的几何位置则使用一种最小平方算法来确定。 2 ) 网格分割技术使得由基本的数字模型可以创建山更为复杂、丰富的模型。 本文提出一种新的交互式的针对自然物体的网格截取方法，它可以高效地 本文工作得到国家自然科学基会项目“基于r b f 插值与多分辩卑表示的扣描数据重建”6 0 3 7 3 0 7 0 、“基 于运动捕获数据的人体运动合成”6 9 6 2 5 3 0 4 及博士点基金“基于图像的绘制”2 0 0 6 的资助。 从三角网格中分割出有意义的部分。本文算法提供给用户一套新的基于屏 幕空问的界面，使得用户可以很方便地指定要截取的物体。为了能够分割 出大数据量的网格，我们使用基于二次型的网格算法来简化网格。在使用 带硬约束的最小割算法来分割简化网格后，传统的最小割算法被用来对原 先的网格进行边界光顺。 3 ) 作为三角网格模型在计算机辅助牙齿正畸中的一个应用，本文提出了一种 基于网格点主曲率的牙齿模型分割算法，克服了当前算法错误切割过度拥 挤的牙齿的缺点。本文利用网格顶点的主曲率作为牙齿分割的尺度，然后 使用三维网格上的数学形态学操作来选择特征线作为候选的分割边界，最 后使用基于局部区域的优化方法来封闭这些特征线以完成牙齿模型的精确 分割。 4 ) 细分造型技术可以克服传统造型技术在拓扑上的限制，因此广泛用于数字 模型的获取和显示。本文提出了一种高效并且鲁棒的逆向l o o p 细分算法， 该算法可以重建细分曲面上的尖锐特征。它适合于以细分作为渐进光顺的 模型以及以细分作为造型工具的应用程序。我们的主要目的是设计一种可 以从细分后的精细模型重建出细分前的粗糙模型的算法。该算法只需要极 少的内存并且不会带来几何和拓扑上的误差。同时，该算法易于实现，并 且具有线性的时间复杂度。基于这一逆向的细分算法，本文提出了渐进细 分曲面的框架，它可以被用来生成基于细分曲面的渐进光顺模型。 关键词：数字几何，网格修复，网格分割，细分，感知特征。 a b s t r a c t i nt h ef i e l do fc o m p u t e rg r a p h i c sa n dc o m p u t e ra n i m a t i o n ，t h e r ea r ei n c r e a s i n g d e m a n d sf o rd i g i t a lm o d e l sa st h er a p i dd e v e l o p i n go fd i g i t a lm e d i a ，a n di ti so n eo f i m p o r t a n tr e s e a r c hd i r e c t i o n st oe f f i c i e n t l yo b t a i na l lk i n d so fd i g i t a lm o d e l s t h e r e p r e s e n t a t i o no fd i g i t a lm o d e l si st h ek e yt of a r t h e rp r o c e s s i n gd i g i t a lm e d i a b e c a u s e o f t h ei n t r i n s i c a l i m i t a t i o no f t h et r a d i t i o n a lp a r a m e t r i ca n di m p l i c i tr e p r e s e n t a t i o ni n t o p o l o g y , t h em e s hr e p r e s e n t a t i o nb a s e do np o l y g o nh a sg a i n e dm u c ha t t e n t i o ns i n c e i ti sr e l a t i v e l y s i m p l ea n dh a sl i t t l et o p o l o g i c a ll i m i t a t i o n ，a n di sm o r ea d a p t i v et o p i p e l i n eo fc o m p u t e rd i s p l a ys y s t e m s o ，t h ep r o c e s s i n ga l g o r i t h mb a s e do nm e s hh a s h a dr a p i dd e v e l o p m e n t p e r c e p t i o nb a s e df e a t u r e sa l et h em a i nf a c t o r st h a th u m a nb e i n gu n d e r s t a n d st h e w o r l d i nt h e3 dd o m a i n ，t h ed i s c o n t i n u o u ss t r u c t u r ec o n s i s t so f t h em a i nf e a t u r e st h a t h u m a n sr e c o g n i z ea n du n d e r s t a n dt h ed i g i t a lm o d e l s b e c a u s eo ft h ed e m a n d sf r o m d i g i t a le n t e r t a i n m e n ta n di n d u s t r y , h o wt om a k et h ep r o c e s s e dm o d e l se f f i c i e n t l y r e s p e c tt h ep e r c e p t i o nf e a t u r e si nm e s hp r o c e s s i n ga l g o r i t h mi sv e r yi m p o r t a n t i nt h i s p a p e r , b a s e do f ft h ep e r c e p t i o nf e a t u r e sw ep r o p o s ef o u rn o v e lm e s hp r o c e s s i n g a l g o r i t h m st oe r a s et h ec o r r e s p o n d i n gl i m i t a t i o n si np r e v i o u sa l g o r i t h m s f i r s t l y , w e d e s i g nan o v e lm e s hr e p a i r i n ga l g o r i t h mt h a tc a nr e s t o r et h es a l i e n ts t r u c t u r ef e a t u r e s s e c o n d l y , u s i n gt h ep e r c e p t i o nf e a t u r e s a st h em e t r i c ，w ep r o p o s et w oi n t e r a c t i v e m e s hs e g m e n t a t i o na l g o r i t h m sb a s e do nn a t u r eo b j e c tm o d e l sa n dd e n t a lm o d e l s ， r e s p e c t i v e l y f i n a l l y , w ei n t r o d u c ear e v e r s el o o ps u b d i v i s i o ns c h e m et h a tc a nd e a l w i t hs h a r pf e a t u r e s ，a n dt h ef r a m e w o r ko fp r o g r e s s i v es u b d i v i s i o ns u r f a c ei sa l s o p r o p o s e d 。f h ef o l l o w i n ga r et h em a i nw o r k sw eh a v ed o n e ： 1 ) m e s hr e p a i r i n gi so n eo ft h en e c e s s a r ys t e p st oo b t a i nr o b u s tm o d e l sf r o mt h e i n i t i a lr e c o n s t r u c t e dm e s h w ep r o p o s ea ne f f i c i e n th o l e - f i l l i n g a l g o r i t h mt h a t a d d r e s s e st h ep r o b l e mo fr e c o n s t r u c t i n gt h es a l i e n tf e a t u r e si nm e s h t h ec r e s t l i n e s ，t h es t r u c t u r ef e a t u r e so fm e s hb a s e do np e r c e p t i o n ，a r ei n t r o d u c e dt om e s h r e p a i r i n g t h ec o n n e c t i v i t yo f t h eh o l ei n c l u d i n gt h el o s tc r e s tl i n e si sd e c i d e db y t r i a n g u l a t i o na n dr e g i o ng r o w i n g t h eg e o m e t r i c a lp o s i t i o no ft h ev e r t i c e sa n d c r e s tp o i n t si nt h eh o l ea r er e s o l v e db yu s i n ga l e a s t s q u a r ea l g o r i t h m 2 1m e s hs e g m e n t a t i o nm a k e st h eb a s i cd i g i t a lm o d e l sm o r ef r u i t f u l i nt h i sp a p e r , a n i n t e r a c t i v es y s t e mi si n t r o d u c e dt oe f f i c i e n t l ye x t r a c tm e a n i n g f u lo b j e c t sf r o ma t r i a n g u l a rm e s h ，w h i c hr e p r e s e n t san a t u r a lo b j e c t w ep r o v i d eas c r e e n - s p a c e u s e ri n t e r f a c et h a ta l l o w st h eu s e rt oi n d i c a t et h em e a n i n g f u lo b j e c te a s i l y i no u r s y s t e m ，q u a d r i c - b a s e ds u r f a c es i m p l i f i c a t i o ni sa d o p t e dt ol e tt h eu s e rc u to u t o b j e c t sf r o mal a r g em e s h a r e ra p p r o x i m a t e l yp a r t i t i o n i n gt h es i m p l i f i e dm e s h b yu s i n gt h ei m a g eb a s e dm i n c u tw i t hh a r dc o n s t r i a n t s ，t h et r a d i t i o n a lg r a p hc u t s a r eu s e dt or e f i n et h ef i n a lc u t si nt h eo r i g i n a lm e s h 3 ) a sa l la p p l i c a t i o no fm e s hp r o c e s s i n ga l g o r i t h mi nc o m p u t e r - a i d e do r t h o d o n t i c ， w ep r o p o s ea ni n t e r a c t i v es e g m e n t a t i o na l g o r i t h mo nd e n t a lm o d e l s ，w h i c hc a n a d d r e s st h ew r o n gc u ti nt h ec a s eo fs e r v e rm a l o c c l u s i o ni np r e v i o u sa r t o f - s t a t e a l g o r i t h m t h e c u r v a t u r eo fm e s hv e r t i c e si ss e l e c t e da st h em e t r i co f s e g m e n t a t i o n ，a n dt h et e c h n o l o g yo f3 dm o r p h o l o g i c a lo p e r a t i o n sa r eu t i l i z e dt o s e l e c tt h ec a n d i d a t ef e a t u r ec o n t o u r s i no r d e rt oc l o s et h o s ef e a t u r ec o n t o u r s ，w e u s et h el o c a lo p t i m i z a t i o na l g o r i t h mt oc o m p l e t et h ea c c u r a t es e g m e n t a t i o n 4 ) t h et e c h n o l o g yo fs u b d i v i s i o nh a sb e e nu s e dw i d e l yi nd i g i t a lm e d i ab e c a u s ei t h a sn ol i m i t a t i o no nt h et o p o l o g yo ft h em o d e l s i nt h i sp a p e rw ep r e s e n ta n e f f i c i e n ta n dr o b u s tr e v e r s el o o ps u b d i v i s i o nm e t h o d ，w h i c hi sw e l l - s u i t e dt o s u b d i v i s i o n - b a s e dp r o g r e s s i v er e f i n e m e n tt e c h n i q u ea n de n g i n e e r i n ga p p l i c a t i o n s t h a tu s e ss u b d i v i s i o na sam o d e l i n gt 0 0 1 i tg a i na l s or e c o n s t r u c tt h es u b d i v i s i o n s u r t h c ew i t hm o s to fs h a r pf e a t u r e sr o b u s t l y o u rm a i ng o a li st od e s i g nar e v e r s e s u b d i v i s i o nm e t h o dt h a tc a nr e c o n s t r u c tt h ec o a r s e rm e s hf r o mt h ef i n e r s u b d i v i s i o ns u r f a c e t h ep r o p o s e dm e t h o do n l yn e e d sal i t t l ec o n s t a n tm e m o r y s t o r a g ea n db r i n g st i ce r r o r t h em e t h o di se a s yt oi m p l e m e n ta n di sl i n e a ri n c o m p u t a t i o n a lt i m ew i t hr e s p e c tt ot h en u m b e ro ft r i a n g l e s b a s e do nt h er e v e r s e l o o ps u b d i v i s i o n ，t h ep r o g r e s s i v es u b d i v i s i o ns u r f a c ei si n t r o d u c e d ，w h i c hc a nb e u s e di ns u b d i v i s i o n - b a s e dp r o g r e s s i v er e f i n e m e n t k e yw o r d s ：d i g i t a lg e o m e t r y , m e s hr e p a i r i n g ，m e s hs e g m e n t a t i o n ，s u b d i v i s i o n ， p e r c e p t i o nf e a t u r e s i v 上海交通大学 学位论文原创性声明 木人郑重声明：所呈交的学位论文，是本人在导师的指导下，独立进行研究 工作所取得的成果。除文中已经注明引用的内容外，本论文不包含任何其他 个人或集体己经发表或撰写过的作品成果。对本文的研究做出重要贡献的个 人和集体，均已在文中以明确方式标明。本人完全意识到本声叫的法律结粜 南本人承担。 学位论文作者签名： 日期：知名年f ，月，日 上海交通大学 学位论文版权使用授权书 本学位论文作者完全了解学校有关保留、使用学位论文的规定，同意学校保 留并向国家有关部门或机构送交沦文的复印件和电子版，允许论文被查阅和 借阅。本人授权上海交通大学可以将本学位论文的全部或部分内容编入有关 数据库进行检索，可以采用影印、缩印或扫描等复制手段保存和汇编本学位 论文。 保密口，在一年解密后适用本授权书。 本学位论文属于 ， ， 不保删 ( 请在以上方框内打“”) 黝乏 日期：加缉r 口月r 徊 日期：嘶，月厂9 曰 ，定童声謦博士学位论文 第一章绪论 计算机图形学是利用计算机研究图形的表示、生成、处理和显示的学科。经 过3 0 多年的发展，计算机图形学已成为计算机科学中最为活跃的分支之一，并 得到广泛的应用【孙家广9 5 ，【倪吴9 9 “田捷9 4 。计算机图形学的研究内容非 常广泛，如图形硬件、图形标准、图形交互技术、光栅图形生成算法、曲线曲面 造型、实体造型、真实感图形计算与显示，科学计算可视化、计算机动画、自然 景物仿真以及虚拟现实等 j a s j 9 0 ， j a s j 9 6 。其中，图形的表示是研究计算机 图形学的基础，它成为后续处理、显示的重要前提。根据表示图形体方法的不一 样，可以将表示归纳为如下几种方式： 参数曲面( p a r a m e t r i cs u r f a c e ) 表示。它表示象飞机、汽车、轮船等具 有复杂外形的产品表面，是工程设计与制造的首要环节参数曲线曲面 表示一直是描述几何形状的主要工具，由c o o n s ，b 6 z i e r 等人在6 0 年 代奠定其理论基础 b f k 8 4 。从最早的参数三次曲线、样条函数以及后 面的b 6 z i e r 曲面，再到8 0 年代后期的n u r b s 曲面，表示形式经历了 从简单到复杂的演变过程。 隐式曲面( i m p l i c i ts u r f a c e ) 表示在计算机辅助几何设计( c a g d ) 中， 另外一种表示形状的方法是隐式曲面。与参数曲面相比，隐式曲面具有 更多的自由度。在构造复杂曲面的时候，能够得到更高光滑度，提供更 多的形状控制手段。隐式曲面表达形式紧凑，而且具有几何运算封闭的 特点 s e d 9 0 a ，【s e d 9 0 b 】。 网格( m e s h ) 表示。随着数字媒体以及三维采样技术的快速发展，在近 1 0 年，以网格表示的图形在快速的增长。这种以点、线、面的表示方法 结构简单，适合于基于图形硬件的绘制。因此，在计算机图形界，很多 的研究是基于网格表示的模型来展开。在网格表示中，以多边形作为原 子结构，其中，三角形和四边形则是主要的表示方法。本文的研究正是 基于三角形网格来处理。 点云( p o i n t ) 表示。在进入二十一世纪以来，图形体的表示向着更简单 化的方向发展 m j d s d 0 1 】。点云模型仅仅使用采样点的位置来表示图 l 第一章绪 论 形，因此非常简单。基于点云数据的研究主要集中在重建、修复、编辑、 动画和显示方面。 在以上的四种图形表示上，纂于三角形的网格是一种重要的表示方法。一 方面是因为三角网格模型的表示比较简单。另一方面，由于计算机显示硬件的限 制，使得其他种类的图形表示模型在最终显示的时候都要三角化，以适应计算机 图形显示卡的管道线设置。三角网格模型在c a d c a m 、科学计算可视化、计 算机视觉、3 d 游戏、计算机动画、逆向工程等领域应用非常广泛。广义上讲， 三角网格模型的数据处理包括网格的生成、简化、形状分割以及规整、细分和拟 合等。 在人类进入2 l 世纪以来，数字娱乐业正在快速的发展，因此对三维数字模 型的需求日益增加。如何高速有效的获取数字模型正在成为计算机图形学中的一 个重要研究课题数字模型的获取有两种基本的形式，一类是无中生有，通过一 些造型工具来创建；另一类则是通过数据获取仪器，如c t 、激光扫描仪等，从 现实的物体中获取原始模型，然后对模型进行进一步的处理。在造型方法上，传 统计算机图形学中基于参数曲面和隐式曲面的造型受到拓扑的限制，而基于网格 的细分( s u b d i v i s i o n ) 方法可以克服这个困难，因而得到极大的发展。另一方面， 在直接获取数字模型方面，由于捕获技术本身的一些缺陷，需要对获取的初始模 型做进一步的处理，在此，网格修复( r e p a i r ) 起着重要的作用。在获取到初始 的网格后，为了能够对网格进行搜索或者编辑等其他的操作，以得到更丰富的模 型，需要对网格进行分割( s e g m e n t a t i o n ) 。在这些算法中，为了使得模型能够高 效，逼真地反映现实中的物体，需要基于与人的认知特点密切相关的感知特征进 行处理。本文从基于数字模型的感知特征出发，在网格修复、网格分割以及网格 细分方面进行了理论研究和算法设计。在本章，我们将简要介绍这方面的相关知 识，以及h 前的研究状况和发展趋势。 1 1 三角网格模型 三角网格模型的直观理解是三维欧氏空间r 3 中一系列三角片的集合三角 网格模型可以用顶点( v e r t e x ) 、边 e d g e ) 和面( f a c e ) 表示，也可以只用顶点和面来 表示。这时，三角网格模型可以定义为一个由顶点表和面表组成的二元组： 2 ，麦童声謦博士学位论文 m = ( v ，d 。其中，顶点表y = ( v ，v ：，咋) 是一有序的顶点序列，每个顶点都可 由唯一的整数进行标识，面表，= ， ，厂j 是有序的三角面片序列，其中 的每个三角形面也都具有唯一的整数标识。顶点b = ( ，只，：，) 7 是欧氏空间r 3 中 的列向量。三角面片z = u ，k ，) 由构成，的三个顶点( v ，h ，v ，) 的整数标识的有 序排列表示。 具有二维流行( 2 - m a n i f o l d ) 特征的模型是很多网格处理算法的必要条件， 二维流行的三角网格需要满足如下的特性： ( 1 ) 两条边仅在公共端点相交，两个三角面片仅在公共边或公共顶点相交。 ( 2 ) 不存在悬挂边、悬挂面。 ( 3 ) 一条边只和两个三角形相邻接。 ( 4 ) 概括来说，就是模型上的每个点拓扑同构于一个圆或者半圆( 带边界) 。 1 1 1 三角片上的点 在定义完三角网格模型之后，模型上的点可以由其所属的三角片的三个顶点 的线性组合来表示( 如图l i l 所示) 。 v = a l v i + a ，i + t v i 其中，丑，乃，五分别为三角形 1 ，唯，q w t ，v i v v 的面积与三角片_ v j v k 的面积之 比。 r 图l l 三角片上的点 f i g 1 - 1p o i mo nat r i a n g u l a rf a c e 1 1 2 邻域 对于一个顶点，其邻域三角片集合为所有包含该顶点的三角片集合；其邻接 第一章绪论 三角片与邻域三角片的概念一致；其邻接边为包含该顶点的边；其邻接顶点为与 该顶点之间有边相连的顶点。 对于一条边，其邻域三角片集合为该条边的两个顶点的邻域三角片集合组成 的并集；其邻接三角片只是指包含该边的三角面片( 两个或一个) 。 对于一个三角片，其邻域三角片集为该三角片的三个顶点的邻域三角片组成 的并集；其邻接三角片是指与之有公共边的三角面片。 1 2 三角网格上的感知特征 感知( p e r c e p t i o n ) 是人脑对直接作用于感觉器官的事物的整体反应，是人对 感觉信息的组织和解释的过程。感知通常是在感觉信息的基础上，由于知识经验 的作用，经过人脑的加工，对客观对象做出直接解释的过程。如果没有感觉做基 础，没有以往知识经验做基础，人的感知就很难形成。 人的感知活动是一个较为复杂的过程。影响感知的客观因素主要包括感知对 象的的大小、强度、重复性、对比性。在信息处理领域中，基于计算机的客观认 知上，强度和对比起着很重要的作用。被感知的物体强度越高，就越容易被感知。 例如，鲜艳的颜色、突出的标记在另一方面，如果图像和背景的差别越大，人 们就越容易从背景中把对象区分出来。 图l - 2 边缘检测 f i g i - 2e d g ed e t e c t i o n 总的来说，对于一般的感知对象，结构信息给人的感知最为强烈。这里结构 信息指的是物体的边界或者物体中不连续的部分。在机械制图领域，就有用线框 4 ，麦童声謦博士学位论文 图来表示物体的模型。在二维图像上，人们通过边缘检测后的图像就可以认知原 先的图像。例如，图i 2 ( b ) 是对图像l - 2 ( a ) 实施c a n d y 边缘检测后的结果，这些 线条组合构成了原l e n a 图像的主要结构特征。 在三维领域，基于非真实感的绘制采用边缘轮廓和线条来绘制三维模型 l a d 0 0 】。他们首先检测出三维物体的边缘轮廓，然后使用不同风格的线条来将该 模型在特定视点下的图像绘制成线条风格画。在这里，轮廓是最重要的感知信息， 成功的轮廓检测可以勾勒出物体的大致模型。例如，图l - 3 ( b ) 是三维模型( a ) 在特 定视点下的基于边缘轮廓的非真实感绘制，该图像基本可以反映原有的三维模型 的轮廓特征 a )b 图1 - 3 三维模型的线条画 f i g 1 - 3l i n ea r ti l l u s t r a t i o no f 3 dm o d e l s 三维模型的边缘可以表示物体的轮廓信息，而由模型的脊线( r i d g e s ) 和谷 线( v a l l e y ) 组成的特征线( c r e s tl i n e s ) 则可以表示出物体主要的几何特征， 它们构成了三维模型的结构信息，是人类感知物体的主要特征。在机械模型中， 最为常见的是具有连续的尖锐特征( s h a r pf e a t u r e s ) ，它们是模型中最为突出 的结构特征，人的视觉对这类特征的感知也最为强烈。图l - 4 ( b ) 是从m a x p l a n k b u s t 模型( a ) 上抽取的特征线，不考虑模型的纹理和色彩信息，通过这些几何特征 线，人们就可以对该模型有个主要的认识。 心理物理学认为；人类对形状进行识别时，部分地基于分割，复杂物体往往 被看作简单的基本元素或组件的组合。基于这个原理，h o f f m a n 等于1 9 8 4 年提 出人类对物体的认知过程中，倾向于把最小的负曲率线定义为组成要素的边界 线，并据此将物体分割为几个组成要素，即视觉理论的“最小值规则理论” s 第一章绪论 【d w $ 4 】，由此得到的分割结果称为“有意义的”分割，也就是说，分割得到的 子叫格必须具有和其所在应用相关的相对尺寸和组织结构【孙李0 5 】。在这个规则 下，网格中三角形之问的双面角( d i h e d r a la n g l e ) 或者顶点的主曲率( p r i n c i p l e c u r v a t u r e ) 都可以成为分割的尺度。作为分割的另外一个理论是基于心理感知科 学中的格式塔理论( g e s t a l t l a w s ) 。其中韵近似规则( l a w o f p r o x i m i t y ) 认为 越是距离相近的物体越有可能成为一个部分m v 0 3 1 。例如，在图1 5 中的左半部 分，因为圆和圆之间的距离在垂直方向小于水平方向，人们将之看成是两条垂直 的直线。在另一方面，由于左边两列和右边两列相互之间的距离小于中间两列相 互之间的距离，凼此人们总是将整个图看成是由左边两列和右边两列组成的两个 部分。在三维模型上。测地距离( g e o d i s cd i s t a n c e ) 成为近似规则的龉常用的衡 量尺度。对于一个理想的分割算法，其最后的分割边界的主要部分应该是模型的 特征线。 0 )b ) 图i - 4 m a x - p i n n c kb u m 模型及其特征线【o b s 0 4 ， f i g 1 - 4m a x - p l a n c kb 懈a n di t sc r e s tl i n e s 0 b s 0 4 p r 0 m t v 图1 5 格式塔中的近似规则 f i g1 - 3 p r o x a n i o f g e s t a l t l a w s 在网格处理算法中，无论是数字娱乐的需要还是工业上的精度需求，正确的 处理好这些基于结构信息的感知特征显得非常重要。基于这一认识，我们在网格 6 ，麦童声謦博士学位论文 修复算法中。提出了一种可以恢复网格显著特征的空洞填充算法；为了使得三维 网格的分割结果尊重人的感知特点，我们组合最小值规则和近似规则作为分割尺 度，提出了一种针对自然物体的交互式的网格分割算法；作为三角网格模型在计 算机辅助牙齿正畸中的一个应用，在基于严重拥挤的牙齿模型分割中，我们提出 了一种基于网格点曲率的牙齿模型的分割算法：最后，在基于细分曲面的多分辨 率框架下，我们设计了一种可以恢复网格上的尖锐特征的逆向l o o p 细分算法。 1 3 论文综述 1 3 1 网格修复 由于数据获取技术的限制，例如，由于遮挡或者物体本身的高光，一些重建 物体形状所必须的数据会缺失。因此，在经过基于表面的数据重建后，重建出的 多面体表现出有缝隙、空洞、自交等非封闭的特性。修复算法的目的是消除这些 特征，并且使得修整后的网格是一个封闭的二维流行。因此，对于网格修复来说， 存在两个目标：首先，将网格从非流行转化为二维流行；其次，将这些空洞填充 ( f i l l i n gh o l e ) ，构成一个封闭的模型。如何有效的填充这些空洞，使得其最大 程度的恢复网格的原始特征是网格修复的最重要的任务。理想的空洞填充算法需 满足如下两个条件： 边界匹配。被填充的空洞和其边界的周围区域在形状上匹配，中间有个 自然的过渡。同时，它包括网格在三角形数量以及形状上的近似。 内容匹配。内容匹配涉及到细节复制以及特征匹配。细节复制是指将边 界周边区域的规则的细小特征复制到空洞中；特征匹配是指空洞周边的 特征在被填充的区域中应该重现并且连续。在这里，特征是指那些在感 知上比较突出的结构信息( 特征线) 。 在计算机图形学领域，存在着很多网格修复算法。它们可以被分成如下的两 种类型，一种可以被看成是一个独立的应用，一般在重建算法处理完成之后使用； 另外一种是将修复集成到曲面重建算法之中，当重建完成以后，所得到的曲面即 是封闭的二维流行。本文的算法基于前一种类型，它作为一个独立的算法来使用。 下面根据修复算法所采用的空问结构的不同，对主要的网格修复算法作一介绍。 7 第一章绪论 ( 1 ) 基于体的网格惨复 基于体的修复，其思想是用三维的体网格来嵌入输入的网格，修复的模型需 要从体中进行重建。一般的，对于基于体的空洞填充算法，它同时包含了将非流 行转换为二维流行。基于体的修复，主要的问题在于两个方面，一方面，在于如 何将一个多边形网格转换为体素：另一方面，如何在体索上进行网格修复。 将一个多边形网格转换为体的表示方法，通常称为扫描转换 ( s c a n - c o n v e r s t i o n ) 或者体素化( v o x e l i z a t i o n ) 。为了能够重建一个封闭的曲面， 关键的问题是如何确定体中的每个体素的符号，这个符号表示了该体素是否在这 个模型的内部。 第一种扫描转换算法仅仅检查每个体素是否和模型曲面相交，但是并不生成 正负符号 h y f k 9 s ，【d k 0 0 。这种体表示方法的模型曲面是个薄板，因此它没 有内部和外部之分。 第二种扫描转换算法直接从输入的模型中生成带有符号的体素。利用法向对 每个体素计算它到输入曲面的最短带符号距离f f p r j 0 0 ，因此对于那些无向的多 边形曲面，该算法不能够产生符号一致的表示。 n o o r u d d i n 和t u r k 提出了两种算法来直接从输入曲面来生成每个体素的符 号：奇偶计算( p a r i t yc o u n t ) 和射线穿刺( r a ys t a b b i n g ) n t 0 3 和f r i s k c n 等 的算法一样，该算法采用了一个非均匀的网格来表示体。从每个体素发射一个射 线，通过奇偶数以及曲面和射线的相交点位置选取符号因为该算法是个全局的 过程，在射线相交的过程中，曲面上一个很小的误差将会使得体网格上的点产生 较大的位置偏移 最后一种扫描转换算法将如何确定内外两个部分作为一种后处理的过程它 首先构建一个八叉树，然后使用一个鲁棒的种子算法来确定每个八叉树网格点的 符号。相似的，o o m c s 等首先用一个均匀的网格来体素化每个三角形，然后使用 边界填充策略 f v f h 9 0 来填充每个内部体素 o s d 9 7 。这些算法只对封闭的曲面 起作用，对于包含有空洞的曲面则失去作用。 为了能够处理有空洞的模型，以下四种算法被提出来用以处理复杂的曲面： 空间雕刻算法( s p a c ec a r v i n g ) ，体散播算法( v o l u m e t r i cd i f f u s i o n ) ，离散凸包 ( d i s c r e t ec o n v e xh u l l ) 算法以及基于样本的算法【j u 0 4 空间雕刻算法是基于距 8 j 麦兰z 謦博士学位论文 离扫描的曲面重建算法的一部分，它依赖于从扫描仪发射的光线信息来确定空洞 的区域。体散播算法依赖于已知的每个体素中的带符号的距离。它使用一个全局 的迭代算法来达到收敛，获取一个光滑的并且看起来比较自然的曲面。j u 使用 八叉树作为数据结构 j u 0 4 ，利用一个自底至e 的策略来检测出洞的边界，然后 使用离散凸包理论从顶到下的填补这些区域，最后利用等值面抽取算法来重建三 角形i l c s 7 或者四边形网格 j l f w 0 2 。该算法运行速度块，鲁棒性高，适合于处 理海量数据。但是，该算法按照丽积最小的原则来填充空洞，因此，在某些区域 看起来不自然( 曲率的不连续性) 。 d a v i s 等使用基于体的散播技术将一个截断的距离方程扩展到空间中，找到 该方程的零集合 d m g l 0 2 。该距离方程需要利用在每个网格顶点的已知带符号 的距离参数，并且使用个全局的循环来收敛求解，以找到一个光滑的并且看起 来不错的曲面。v e r d c r a 等则扩展了他们在图像i n p a i n t i n g 中的技术，利用数值化 求解偏微分方程来填充三维网格w c a s 0 3 。 m u r a l i 和f u n k h o u s e r 提出一种基于曲面建模领域的b s p 算法【m f 9 7 1 在他 们的算法中，输入的模型由一个b s p 树来保存，b s p 树上的叶子被划分为实体 或者非实体。该算法总是能够确保输出模型的封闭性，但是该算法需要极为耗时 的操作来构建b s p 树。同时，它也需要解一个阶数和网格的多边形个数相等的 线性方程租，这无疑极为耗时。 ( 2 ) 基于网格的修复 基于网格的修复直接在三角形网格上进行操作，以修复网格的几何和拓扑错 误。一般的，它分为两个独立的步骤，首先是修复网格中导致非流行的点线面， 然后进行空洞填充 为了将非流行转化为二维流行，g u e z i e e 等在2 0 0 1 提出了一种高效的算法 【a g f b 0 1 。该算法可以被划分为两个步骤，切割( c u t t i n g ) 和缝 b ( s t i t c h i n g ) 。首 先，检测出那些导致非流行的奇异点和边( 例如，一条边邻接3 个或者3 个以上 的三角形) 切割操作通过全局的和局部的两种方法沿着这些奇异点和边将网格 切开。全局切割操作对网格上的所有顶点和面进行操作，而局部的切割操作只切 割那些奇异边当网格中有大量的奇异拓扑的时候，全局算法比较适合；而局部 操作则对于整个网格拓扑正确，只有局部范围内奇异的网格有比较明显的效果。 9 第一章绪 论 在进行切割后，通过缝补操作将网格修复起来，使得其是一个有效的二维流行 该算法具有线性的时间复杂度，并且不依靠浮点运算，因此特别适合于海量数据 的处理。 为了修复非流行的三角形网格，w a g n e r 等提出了一种基于模拟退火的算法来 进行流行修复以及空洞填充 m u g i m 】。他们首先检测并且删除非流行的三角形 ( 相交三角形以及引起拓扑错误的三角形) 。对于简单的空洞，通过插入三角形 来填充；对于复杂的空洞，通过基于优化的模拟退火算法来填充。在三角化后， 通过曲率优化来光顺填充区域，以达到边界匹配。最为重要的一点是，他们的基 于模拟退火的算法可以确保修复后的模型的二维流行性 为了填充网格上的空洞，b a r e q u e t 和s h a r i r 使用一种动态规划的算法来找到 一种针对三维多边形的面积最小的三角化算法f g m 9 5 在三维空间中找到一个 三角化后，网格求精( r e f i n e m e n t ) 以及光顺( f a i r i n g ) 技术被用来填充分段多 项式曲面 r h 9 6 。b a r e q u e t 和k u m a r 实现了一个交互式的系统 b k 9 7 ，他们使 用缝合对应边的方法来封闭小的裂隙：而对于大的空洞，他们则采用