（计算机应用技术专业论文）三维几何模型简化技术研究.pdf

摘要 随着计算机图形学的发展，越来越多的科学应用都需要对三维几何模型进行 分析和显示。一般说来，三维几何模型的数据量都十分庞大，给其存储、传输以 及渲染等诸多方面带来了较大的困难。然而在许多场合下，对三维几何模型的处 理只是为了满足视觉上的需求，因而可以考虑在保证其外形相似的前提下，用比 较简单的几何模型来代替复杂的原始模型，以减少数据量，加快处理速度，节约 存储空间，可见三维几何模型简化算法的研究课题具有一定的应用价值。 本文对当前国内外有关几何模型的简化算法进行了分析和研究后，将三角形 收缩简化操作与包络控制简化误差的方法相结合，利用一维线性搜索中的二分法 改进了c o h e n 提出的简化包络构造算法；随后又综合简化包络的误差控制方法和 二次误差矩阵的局部性误差控制思想，提出了一种分解式包络片的概念。分解式 包络片是按需构造的，打破了完整简化包络的概念，只是构造了重要部位的包络。 与c o h e n 的算法相比，采用分解式包络片来控制模型简化误差后，可以节省很多 不必要的三角形相交判断，大大加快了包络构造和模型简化的速度。 另外，本文还设计了演示系统以实现分解式包络片控制三角形收缩操作的这 种模型简化算法。实验结果表明，采用本文提出的这种算法来简化三角形网格模 型，简化后的模型能很好地保留原始模型表面的尖锐特征，与原始几何模型有着 很高的相似度，具有较高的简化效率和时间效率。 关键词三角形网格模型，三角形收缩，简化包络，分解式包络片，简化 a b s t r a c t n o w a d a y s ，a l o n gw i t ht h ed e v e l o p m e n ti n c o m p u t e rg r a p h i c s ，m o r ea n dm o r e a p l ： l i c a t i o n so t h e r s c i e n c ef i e l d sr e q u i r ea n a l y s i sa n dd i s p l a yo f 3 d g e o m e t r i c m o d e l s c o m m o n l y , b e c a u s eo f t h el a r g e - s c a l ed a t aq u a n t i t yo fa3 dg e o m e t r i cm o d e l ，i ti s v e r yd i f f i c u l tt os t o r ei t ，t ot r a n s f e ri t a n dt or e n d e ri t b u ti nm a n yc a s e s ，t h ep u r p o s e o fm a n i p u l a t i n go na3 dg e o m e t r i cm o d e li sj u s tt od i s p l a yi t ，s o as i m p l e rm o d e l w h o s es h a p ei ss i m i l a rt ot h a to fi t so r i g i n a lm o d e l i su s u a l l ye n o u g h a n da l s o ，u s i n g as i m p l e rm o d e li sb e n e f i c i a lt oq u i c k e ns c e n e sr e n d e r i n ga n dt o s a v em o r es p a c eo f s t o r a g e s o ，i ti sn e c e s s a r ya n ds i g n i f i c a n tt or e s e a r c ho n t h ea l g o r i t h mo f s i m p l i f y i n g ac o m p l e x3 d g e o m e t r i c m o d e l 一 a f t e ra n a l y z e da n ds t u d i e do ns o m ea l g o r i t h m sa b o u th o w t os i m p l i f yac o m p l e x 3 dg e o m e t r i cm o d e lf r o mh o m ea n da b r o a d ，t h i sp a p e rp r o p o s e s t h ec o n c e p to f d i v i s i o n a l e n v e l o p ep i t c ha n da m e l i o r a t e s t h em e t h o do fe n v e l o p e sc o n f o r m a t i o n p r o p o s e db yc o h e nu s i n gt h ed i c h o t o m y i nl i n e a rs e a r c h w h e nat r i a n g l ei ss e l e c t e d a n dc o n t r a c t e dt e n t a t i v e l y ，t w oc o r r e s p o n d i n gd i v i s i o n a le n v e l o p ep i t c h e ss h o u l db e c o n s t r u c t e da tf i r s t t h ed i v i s i o n a le n v e l o p ep i t c hi sab i to ft h ew h o l es i m p l i f i c a t i o n e n v e l o p e + s o ，w i t ht h eh e l p o ft h ed i v i s i o n a l e n v e l o p ep i t c h ，l o t s o fu n n e c e s s a r y d e t e c t i o no ft r i a n g l e si n t e r s e c t i o nw o n tb ec a r f i e do u t 。a n di ts p e e dt h ep r o c e s so f m o d e l s i m p l i f i c a t i o n ， a tl a s t ，t h i sp a p e rh a sd e v e l o p e dad e m os y s t e mt ov e r i f yt h i sa l g o r i t h m t h e r e s u l t sf r o me x p e r i m e n ts h o wt h a tt h es i m p l i f i e d m o d e lb yt h ea l g o r i t h mo fd i v i s i o n a l e n v e l o p ep i t c h e sc a np r e s e r v et h es h a r pf e a t u r e sa n db eo f ah i g h e rr e s e m b l a n c ew i t h i t so r i g i n a lg e o m e t r i cm o d e l k e yw o r d s ：t r i a n g u l a rm e s hm o d e l ，t r i a n g l ec o n t r a c t i o n ，s i m p l i f i c a t i o ne n v e l o p e ， d i v i s i o n a le n v e l o p ep i t c h ，s i m p l i f i c a t i o n 第一章绪论 1 1 模型简化技术概述 1 1 1 模型简化技术的出现 由于图形具有一定的直观性，能够帮助人们更好地理解复杂而单调的数据， 因此，随着计算机图形设备的不断发展，许多科技领域的应用都倾向于采用图形 的形式来表示数据，以直接对几何模型进行处理或显示。例如： 在产品制造业中，已经采用计算机辅助设计与制造( c a d c a m ) 技术实现 了飞机、汽车、船舶、机械设备等产品的“无纸设计”。同时，这种由计算机创建 的数字化精确模型还推动了数控加工、数控测量等技术的发展和应用； 在广告与影视制作方面，计算机制作的各种特效，诸如火焰、光效果、海浪 模拟、基于模型的角色渐变等，都能使得观众欣赏到更多精彩画面，而全三维的 真实感卡通电影则已经成为好莱坞的新一代票房大户| 2 j ； 在土建工程中，可以先通过航空摄影、g p s 卫星测量、野外测量或地质勘查 等手段获取相关地区的地理环境信息，建立起地形地貌的三维模型，然后再对其 进行分析、计算和设计，模拟出所要建设的构筑物的景观： 在进行虚拟实验或构造虚拟环境时，基于三维几何模型的虚拟现实技术可以 更好地实现人一机交互操作：而“数字地球”的构建则是科技、经济、政治、社会 和历史发展的必然趋势【l l ； 在科学计算可视化方面，就是要将海量数据用图形的方式描述，使其更为直 观易懂，以便于更好地发掘数据中蕴含的自然、物理现象和规律，如气象卫星云 图数据、脑部c t 扫描数据等都可以构建出相应的三维几何模型i l j 。 目前，多边形表面模型( p o l y g o n a ls u r f a c em o d e l ) 是最常用的一种三维几何 模型表示方法。现代的一些高科技设备和技术，如激光扫描仪、计算机可视系统、 医学图像设备、c a d 系统、卫星测量技术等，都能提供或创建大量的多边形表面 模型。但是，这样直接获得的原始模型数据量相当大，其多边形的数目可达几百 万甚至几千万，即使是高性能的图形工作站也难以及时处理。 更为普遍的，i n t e r n e t 互联网已经成为人们获取信息的重要来源之一。当前的 互联网上，以文字、声音、图像、视频等形式的多媒体信息为主，然而，随着互 联网在全世界范围内的不断发展和普及，越来越多的网络服务要求在互联网上传 送三维几何模型。如果网上商店将商品的三维几何模型放置到网页上，顾客在浏 览网页时，通过对模型进行旋转等操作，就能全方位地观看商品了，但现有的网 络设备还无法满足复杂多边形表面模型海量数据的传输。因此，人们考虑将复杂 的三维几何模型类似于声音、图像、视频等多媒体信息一样进行编码压缩，以节 省模型的存储空间，加快模型的处理速度。 一个三维多边形表面模型由其表面上的顶点组成的，通过其拓扑结构和几何 位置两方面的信息来描述，其中拓扑结构是指各项点之间的相互连接关系，而几 何位置是指各顶点在三维空间中的坐标信息【3 】【4 1 ，这两种信息组合在一起就能在 三维空间中定义一个表面模型了。另外，模型还可能具有一定的属性，如颜色、 纹理坐标、法向量等。 编码压缩实际上就是尽量减少模型在拓扑结构和几何位置信息描述方式上 的冗余度，例如对于三角形表面模型，采用带状三角形的描述方法可以减少对三 角形顶点的索引次数【3 】，还可以通过预测的方法来估计相邻顶点的位置坐标，以 降低模型顶点几何坐标的信息量 3 1 f “。这种编码压缩的方法不改变模型的外形、 结构、拓扑关系，甚至构成模型的图元类型和数目也不会发生变化。 然而在很多情况下并不要求十分精细的模型，例如在一个复杂的虚拟场景 下，离视点越近的物体，视觉重要度越高，模型要求越精细，而离视点越远的物 体，粗糙些的模型就已经能满足人们视觉上的需要了；再如网上商店的顾客在 浏览网页时，只要看到商品的基本形状即可，如果想看得更清楚，则可以要求传 输更精细些的模型。 因此，可以建立多个与原始模型外形相似的近似简化模型，表示原始模型不 同程度的细节，这一系列的近似模型被称之为原始模型的多分辨率模型 ( m u l t i - r e s o l u t i o nm o d e l ) ，也称作多细节层次模型( l e v e lo f d e t a i l s ，简称l o d ) 。 早在19 7 6 年，c l a r k 就提出过“多分辨率”概念，目前这一概念在二维的光栅图 像中已得到充分应用；自二十世纪九十年代中期起，研究人员开始了三维模型多 分辨率方面的探索。这些近似模型的表面没有原始模型分割得精细，其多边形的 数目有所减少，模型顶点集合中顶点的数目、位置坐标等信息都有所不同，而顶 点的变化又相应地引起了模型拓扑结构上的变化，这种多分辨率的方法是三维多 边形表面模型在几何上的简化。 2 1 1 2 模型简化技术的研究内容 三维几何模型的压缩技术和简化技术从各自的立足点出发，是两种本质上完 全不同的方法，但目的都是降低模型的数据量。其中，压缩技术是从多边形表面 模型表示方法的角度出发，采用编码、预测等手段去掉模型数据中的冗余信息； 简化技术则从几何学的角度出发，在保证模型外形基本不变的前提下，降低模型 表面的分割精度，尽量减少其分割的多边形数目。本文主要研究后者。 三维多边形表面模型简化技术的研究内容主要集中在以下几个方面： 模型的简化方法。研究通过什么样的方法或者操作才能减少模型表面的多 边形数目。 模型简化时误差的控制方法。研究采用什么样的手段才能保证简化后的模 型与原始模型在外形上相似。 多分辨率系列模型的构造方法。研究怎样构造出一系列的近似模型，其细 节程度逐渐降低，其中原始模型的细节程度最高，最精细，而最后一个近 似模型的细节程度最低，是最粗糙的简化模型。 模型的简化方法和误差控制方法是模型简化技术中的基本内容，结合这两个 方面的算法就能生成原始模型的一个近似模型，这称之为单分辨率简化模型，它 的构造方法是多分辨率简化模型构造方法的基础。 1 2 模型简化技术的研究意义及应用领域 由1 1 1 小节可知，随着信息化社会的到来，无论是在科学研究上，还是在 工程应用中，三维几何模型已经成为一种重要的数据表示形式。通常，直接由高 科技设备创建的多边形表面模型都很复杂，表面分割精细，数据量十分庞大，其 存储、传输以及渲染等方面存在较大困难。然而在很多情况下，较简单的近似模 型就已经足以满足要求了。模型简化技术就是为了解决这个问题而发展起来的， 它将复杂的原始多边形表面模型进行简化，生成一个外形与原始模型相似，而表 面分割较粗糙、多边形较少的近似模型。 模型简化技术有着十分广阔的应用领域和前景，例如： 当绘制一个复杂场景时，离视点越远的物体，其视觉重要性越小，可以采用 粗糙一些的近似模型来代替精细的原始模型，以加快复杂场景画面的绘制速度： 在制作计算机动画时，多边形表面模型的多边形数目越多，动画的渲染速度 就越慢，但是当物体在快速运动时，其表面不要求真实感很强的渲染效果，此时 就可以采用简化模型进行渲染； 同样。在虚拟现实系统中，虚拟环境随着视点的转移而发生变化，场景中的 一些物体将由远及近，而另一些物体将由近及远，采用多分辨率的模型来表示这 些物体则可以加快变化场景的绘制： 而在分布式虚拟系统、分布式协同应用中，各计算机之间也许需要通过互联 的网络来传输模型，如果将复杂的原始模型进行简化，就可以减小模型的数据量。 从而降低网络传输的负荷； 随着i n t e r n e t 的不断发展，网上传输三维模型的要求越来越迫切，多分辨率 概念充实了多媒体信息，也使得网络传输三维几何模型成为可能，反过来，模型 简化技术又加快了模型的传输速度，刺激了电子商务、网络游戏等业务的扩展。 可见，模型的简化技术有着十分重要的研究意义。 1 3 国内外模型简化技术研究现况 自二十世纪九十年代中期起，国内外的学者们开始研究三维几何模型的压缩 和简化技术，到目前为止已有了一定的成果。 1 3 1 几种主要的模型简化算法 目前已提出的模型简化算法大致可以分成以下四大类【5 】【6 】【7 】： 基于表面重新划分的简化算法。t u r k 在文献【8 】中提出，按照曲率在模型 表面上取组数量事先给定的新顶点，将这些新项点与旧顶点连接成一个 中间网格，然后去掉旧顶点，将造成的空洞重新三角形化，这样便生成了 一个新的网格模型。可见，开始选取的新点数目越少，最后生成的网格模 型就越简单。 基于顶点聚类( v e r t e x c l u s t e r i n g ) 的简化算法。该算法由j r o s s i g n a c 和 p b o r r e l p l 首先提出，先求出整个原始三维几何模型的长方体包围盒 ( b o u n d i n gb o x ) ，然后将其平均划分成许多小格子( g r i d ) 。由于每个小 格子内部的点与其它一些格子中的点有连接关系，因而格子与格子之间也 具有一定的连接关系。按照邻近点聚合的策略，将位于同一个格子中的所 4 有顶点都移动到格子内部的同一位置上，合并成一个点，最后将每个格子 内部的这个唯一点按照格子间的连接关系巨相连接起来，这样就构成了一 个新的网格模型，其顶点数远少于原始模型的顶点数。顶点聚类算法简单 易行，而且对原始模型没有任何限制。其包围盒划分的细小程度就决定了 模型的简化程度，但这种方法使得简化后的模型细节丢失严重，失真率较 大，且难以控制。 基于几何图元操作的简化算法。目前，这种简化算法是模型简化技术中的 主流算法。几何图元操作包括对点、线、面( 多边形) 所进行的删除、收 缩、合并等。对不同的图元可以采用不同的操作，所要考虑的问题也各不 同。这些基于几何图元操作的简化算法将在1 3 2 节中举例说明。 基于小波理论的简化算法。小波变换是一种比傅立叶变换更加灵活有效的 信号分析与处理工具，自1 9 8 4 年小波概念出现之后，小波变换作为数学 理论和方法在壬 学技术界引起了越来越多的关注，已经成功运用于信号分 种方法能直接得到一系列的多分辨率模型。 1 、穹女 、。研r m e c k 等人将 述模型1 ”，这 这一：青将从三纰。x q 稹尘简化技术的三个研究内容依次介绍国内外已有的 一些简化算法，由于目前三角形表面模型的应用十分广泛，因而大部分算法都是 针对三角形表面模型的。 l 、 模型的简化方法 目前，基于几何图元操作的简化方法是三维几何模型简化技术中的主流算 法，这一部分主要介绍了使用较多的几种几何图元操作。 点删除( v e r t e xd e c i m a t i o n ) 操作 1 4 - 1 6 点删除是一种反复操作的表面简化方法。在每次循环中，选择并删除网格模 型中的一个点，同时也删除掉那些以它为顶点的边和三角形面片。但是，去掉这 些几何元素后，模型的网格中会形成一个空洞( h o l e ) ，其边界通常为个多边形， 而不是三角形。为了保证模型外形上的完整性和表面分割的统一性，般要求把 删除操作造成的非三角形空洞进行重新三角化，如图1 1 所示。 点删除操作简单易懂，模型的简化质量好；但是由于要进行重新三角化，处 5 理速度较低。 ( a ) 原始网格( b ) 删除掉一个顶点( c ) 重新三角形化空洞 图1 1 点删除操作 三角形删除( t r i a n g l ed e c i m a t i o n ) 操作【l 7 1 三角形删除操作是对点删除操作的扩展，每次循环操作中选取的删除对象不 是一个单独的顶点，而是一个三角形面片。当一个三角形面片被删除时，所有与 之相邻的三角形也随着删除，最后同样也要重新三角形化删除造成的空洞。三角 形删除操作与点删除操作相比较，一次性处理了多个点，加快了简化速度。 边收缩( e d g ec o n t r a c t i o n c o l l a p s e ) 操作m 2 9 1 边收缩和下面介绍的三角形收缩实际上可统一为“点合并操作”，如图1 2 所示。每次进行边收缩操作时，这条边的两个端点移动到同一位置，也可以把其 中一个端点移动到另一个端点的位置上，这样这条边的两个端点合并成了一个点， 而所有那些入射到这两个端点的线段或从这两个端点出射的线段都连接到合并后 的点上。可见，随着一条边的收缩，其左右两个以之为边界的三角形也消失了， 而其它的相邻三角形则发生了形变。 ( a ) 原始网格( b ) 中i 目1 的边收缩成点 图1 2 边收缩操作 边收缩算法也要对模型反复进行操作，但是收缩操作不会像删除操作那样产 生空洞，也就不需要进行重新三角化，并且边收缩操作的对象是一条边，一次性 处理两个顶点，简化速度较快，模型的简化的质量也较好。在基于几何图元操作 的模型简化方法中，边收缩操作是使用最为广泛的方法，许多具体的算法都采用 了边收缩来简化模型，例如h o p p e 提出的累进网格算法i 垤。9 1 ，m i c h a e lg a r l a n d 的误差矩阵算法 2 0 - 2 3 。 三角形收缩( t r i a n g l ec o n t r a c t i o n c o l l a p s e ) 操作】 三角形收缩操作是边收缩操作的扩展，每次循环操作中选取的收缩对象不是 一条边，而是一个三角形面片。将三角形的三个顶点移动到同一位置，这个三角 6 形就收缩成为一个点，而原来入射到这一三角形三个顶点的线段或由这三个顶点 出射的线段都连接到合并后的点上，其周围的三角形面片也随之变化。 2 、模型简化时误差的控制方法 二次误差矩阵【1 7 】【2 0 2 5 】1 2 8 】f 3 0 1 当前在模型简化算法研究范畴中，使用最频繁的误差控制方法是二次误差矩 阵( q u a d r i ce r r o rm a t r i c e s ) 方法，其概念由卡内基梅隆大学的m i c h a e lg a r l a n d 和p a u ls h e c k b e r t 两人于1 9 9 7 年首次提出的1 2 0 。 文献f 2 0 采用边收缩作为基本的模型简化操作，算法首先为原始模型表面网 格中的每一个点都设置一个对称的4 4 误差矩阵，记为： q l l q 1 2 q 1 3 q 1 4 1 n iq 2 l q 2 2 q 2 3 q 2 4 i y lq 1 3q 2 3 q 3 3q 3 4 i q 1 4 q 2 4 q 3 4 q 4 4 j 同时，也为每一个点v 都定义一个移动误差的度量： v 1 q v = q l i x 2 + 2 q l2 x y + 2 q l3 x z + 2 q l4 x + q 2 2 y 2 + 2 q 2 3 y z + 2 q 2 4 y + q 3 3 2 2 + 2 q 3 4 z + q 4 4 若点v 移动到v ，则v 与移动前点v 的相邻面都有了一定的距离，假设p 是 与v 相邻的一个平面a x + b y + c z + d = 0 ( a 2 + b 2 + c 2 = 1 ) ，记p = 【a ，b ，c ，d 】7 ，则v 到 p 的距离为p 7 v 。采用这些距离的平方和( p 7 v ) 2 作为误差标准，当v 不移动时， v = v ，有v t q v = e ( p 7 v ) 2 = ( v 7 p ) ( p 7 v ) = v ( p p 7 ) v q = ep p l ，其中p p l = a b 卯耐 6 26 c 耐l 幻c 2 耐i 6 dc d d 2l 可见，每个点的初始误差矩阵q 是由其相邻三角形所在的平面决定的。通过 每一个点的q ，就能为每一条边计算其收缩误差。假设要收缩的边( v 1 ，v 2 ) 一v ， 则简单地定义v 的误差矩阵为q = q 1 + q 2 ，其收缩操作产生的误差( 收缩代价) 为s ( v ) = v 1 1q f v ，其中使得误差最小的v 就是这条边收缩成新点的最佳位置。 根据最小二乘法，对误差求偏导，令其等于0 ，得： j q 1 1q 1 2q 1 3 q 1 4 lr o 牌q 1 3 q 2 2 档2 q 2 3q 3 3q 啦3 4 4h 0 引ff ff l 0001 li 1 i 如果该方程有解，即第一个矩阵可逆，则v ，的位置为： 忙q 1 1 鞭q 1 23 搿q 1 4 q 旧- q 2 1 q 2 2001 忙 嚣郇；引吲 o ll l j 若无解，则从v l 、v 2 ，或者v l 、v 2 连线的中点之间选择一个使得收缩误差 简化包络( s i m p l i f i c a t i o ne n v e l o p e s ) 的概念是由j o n a t h a nc o h e n 等人提出的， 累进网格( p r o g r e s s i v e m e s h e s ，p m ) 【1 8 邶1 h u g u e sh o p p e 提出了累进网格的概念以构造多分辨率模型1 引。将一个任意的 原始模型网格m 描述并存储为一个很粗糙的基本网格m o ，以及一系列的细节信 息，而这一系列的细节实际上都是关于顶点分裂操作的信息。顶点分裂操作是顶 点合并操作的逆操作，每一次顶点分裂操作都会往模型网格中增加一个顶点。因 此，通过多次顶点分裂操作可以由m o 逐步恢复原来的拓扑信息，直至完全恢复 出原始模型网格。累进网格的表示形式实际上定义了一个连续的逐渐精细的模型 网格序列( m o ，m 1 ，m “，m ) ，其中任意两个网格之间的互相变换都能快速 实现，连贯性很强。 h o p p e 提出的累进网格是基于边收缩操作的，当然也可以采用其它的简化操 作来实现。显而易见，累进网格的表示形式支持三维多边形表面模型在网络上的 累进传输，它为模型提供了一种有效、无损、连续的多分辨率表示方式。 小波表面( w a v e l e ts u r f a c e s ) 一1 3 1 若要将小波理论应用于三角形网格模型的简化，则这一网格模型要求满足细 分连续性( s u b d i v i s i o nc o n n e c t i v i t y ) 。因此，首先要将原始模型进行网格重组 ( r e m e s h ) ，用小波表示的方法来描述模型网格，e c k 等人在文献 1 1 】中提出了一 种方法，能构造出任意一个无边界模型的小波表示。再将满足细分连续性的模型 网格进行小波分解，将模型的表面分解成一个反映基本拓扑结构的基本网格，以 及一系列代表细节的小波函数项( 含有各级小波系数) ，其数学表述如下式： j 一1 s ( x ) = m u ( x ) v ”+ w j ( x ) w j j = 0 其中，s ( x ) 表示原始三维网格，0 0 ( x ) v o 表示基本网格，( x ) 是小波函数， 一是小波系数。 给定误差范围后，比较各级小波系数的大小，舍弃掉部分小波系数较小的小 波函数项( 也就是去掉了原始模型的一部分细节) ，从而降低了模型的细节程度， 由此达到降低原始模型数据量的目的。 如果给定的误差范围不同，舍弃掉的小波函数项个数也将不同，这样就可以 获得一系列的多分辨率模型了，因此采用小波表示的三维几何模型是真正的多分 辨率模型。 9 1 4 本文所做工作 本文对当前国内外有关几何模型的简化算法进行了分析和研究后，将三角形 收缩简化操作与包络控制简化误差的方法相结合，改进了c o h e n 提出的简化包络 的构造算法；随后又综合简化包络的误差控制方法和二次误差矩阵的局部性误差 控制思想，提出了一种分解式包络片的概念。并在此基础上设计了一个演示系统， 实现了对三维几何模型的简化。 1 4 1 本文的主要研究内容和特点 本文将三角形收缩操作和包络控制误差的方法相结合，主要进行了以下两个 方面的研究： 包络构造方法的改进。c o h e n 等人在文献【3 1 】中提出了简化包络的概念及 其构造方法，但构造一个完整模型的简化包络的难度较大，效率较低，可 以对此进行改进，加快构造速度； 分解式包络片( d i v i s i o n a le n v e l o p ep i t c h ) 的提出。本文结合了c o h e n 简 化包络的概念和二次误差矩阵方法中有针对性的局部控制误差的思想，提 出了分解式包络片的概念，实现了原始复杂网格模型的简化。 与c o h e n 等人的简化算法【3 1 1 相比，本文最终实现的算法有以下突出特点： c o h e n 等人采用的模型简化操作是点删除，而本算法直接用三角形作为操 作对象来简化模型，将一个三角形的三个顶点合并成一个顶点，减少了三 角形的数目，这种图元操作不会形成空洞，不必重新三角形化，并且一次 性处理三个顶点，可减少多个三角形，简化效率较高； 在构造包络的方法上，c o h e n 等人使用的数值计算法采用小步长多次偏移 的方法来逼近最佳偏移值，而本算法则采用了一维搜索中的二分法来逼近 最佳偏移值，加快了逼近速度，提高了包络的构造效率和精度。 分解式包络片是按需构造的，打破了完整简化包络的概念，只是构造了重 要部位的包络。与c o h e n 的算法相比，采用分解式包络片来控制模型简化 误差后，可以节省很多不必要的三角形相交判断，大大加快了包络构造和 模型简化的速度。 1 0 1 4 2 演示系统的实现 本文为新算法设计了一个演示系统，采用了v i s u a lc + + 6 0 编程语言，在 w i n d o w sn t 环境下实现的。演示系统可以打开两种类型的三维图形文件，一种 是s m f ，一种是d x f 。其中s m f 是卡内基梅隆大学几个教授以w a v e f r o n t 的o b j 文件格式为基础定义的，用来描述一个单独的物体：d x f 即图形交换文件，已经 成为图形文件的一种标准，本演示系统要求模型的数据都定义成3 d f a c e 模块。 这些三维的原始模型输入演示系统后，先进行一定的初始化，建立其必要的数据 结构，而后进行简化，输出一个与原始模型形似的简化模型。 整个演示系统利用m f c 生成用户界面，采用o p e n g l 库函数绘制三维图形， 界面友好，操作简便。 实验结果表明，通过本算法得到的简化模型能够很好的保持原始模型的外形 和尖锐特征，具有较高的简化效率，达到了本课题研究的目的。 1 4 3 本文的结构安排 本文共分五章。第一章是绪论，介绍了模型简化技术的研究意义和研究现状； 第二章是本文算法的基本理论，描述了三角形收缩操作的过程，提出了分解式包 络片的概念，并详细介绍了它的构造方法；第三章是本算法演示系统的构建与具 体实现方法；第四章对多个算法进行了性能评价，利用演示系统给出了一些实验 结果；最后的第五章是结论，对本文算法进行了总结，并提出了需要改进的地方 以及继续研究的方面。 第二章包络控制三角形收缩简化误差的三维 几何模型简化方法的基本原理 2 1 有关模型的一些基本定义和属性 2 1 1 三角形表面网格模型 在计算机图形学中，尽管自由曲线、自由曲面作为一种重要的物体描述形式， 已经被广泛应用于c a d 制图系统和计算机动画系统中，但多边形表面模型 ( p o l y g o n a ls u r f a c em o d e l ) 却因其具有简单、灵活等特性，仍然是最常用的一种 三维物体模型表示方法1 3 1 。多边形表面模型只描述了整个物体的表面，通过表面 围成的区域来定义模型的外形和位置，并且模型的表面是由许多小多边形平面片 拼接而成的一个整体。 由于任意一个多边形都能划分成若干个三角形，因此三角形表面模型是多边 形表面模型中最基本的表示形式，非三角形的表面模型都可以细化成三角形表面 模型。就目前对三维几何模型简化技术的研究现状来看，研究对象都选用了三角 形表面模型，本文也是针对这种模型进行的研究和设计。通常，三角形表面模型 又被称作三角形网格模型( t r i a n g l em e s h m o d e l ) 。 当一个三维形体的表面经三角剖分后，可以得到一组三角形，这一组三角形 就表示了一个三角形网格模型( 简记为t m ) 。假设一个三角形网格模型由m 个三 角形构成，共有n 个三维顶点，则t m 包括了一个顶点集合v ( v l ，v 2 ， v n ) 和一个三角形集合t ( t 1 t 2 ，t m ) 。其中，顶点集合v 记录了模型 上每一个顶点在三维空间中的坐标位置，采用三元有序组( x ，y ，z ) 来表示，并 将之顺序编号；三角形集合t 则记录了构成模型表面的每一个三角形是由哪三个 顶点组成的，采用三元有序组( v i ，v j ，v k ) 来表示，v i ，v j ，v k 分别为构成 这个三角形的三个顶点的编号。 本文研究的对象是三角形网格模型，对其进行分析和简化，要求输入的三角 形网格模型在简化后依旧是三角形的网格模型，因此本文用t m o 来表示原始模 型，用t m a 来表示简化后的近似模型。但是，由于本文算法所具有的特点，t m o 和t m a 不能是任意的，而是某个正则形体的三角形网格模型。 1 2 图形学中定义：若形体上任意一点的足够小的邻域在拓扑上是一个等价的封 闭圆，即围绕该点的形体邻域在二维空间中可构成一个单连通域，满足这样条件 的形体就是正则形体 2 1 。对于正则的三维形体，面是形体表面的一部分，每一条 边都有且仅有两个邻面，每一个点至少和三个面( 或三条边) 邻接。 正则形体表面经三角剖分后得到一个三角形网格，它由多个三角形面片线性 连接而成【18 ，没有边界，没有裂缝，也不存在t 型接头，每一条边都有且仅有左 右两个相邻三角形面片，所有相邻的三角形只在公共边和公共顶点处相交“，保 持c o 连续，且每个三角形面片都只有一面是可见的。 当一条边只有一个相邻面时，也就是说这条边仅仅属于一个三角形，那么这 条边就是模型的一条边界线段，在模型的表面上就形成了道“裂缝”。如图2 ，1 所示，图中共有六个三角形，分别是a a b c 、a a b e 、a b d c 、a a e f 、c d f 和a a c f ，其中线段b e 仅仅是a a b e 的一条边，线段b d 仅仅是a b d c 的一条 边，e f 仅仅是a e f 的一条边，d f 仅仅是a c d f 的一条边，而其它的七条边都 分别有左右两个相邻的三角形面片。这样，线段b e 、b d 、e f 和d f 就是模型的 边界线，形成了一道“裂缝”b d f e 。 如果一条边同时是三个及三个以上三角形的公共边时，就形成了一个t 型接 头( t - j u n c t i o n ) 。如图2 2 所示，线段b c 是a a b c 、a b d c 和a b e c 的公共边， 那么这三个三角形就构成了一个t 型接头，其中a b e c 的两面都是可见面，这与 多边形表面模型的概念相冲突。 a f d c c a f 图2 i “裂缝”示意图图2 2t 型接头示意图 本文假定t m o 和t m a 是正则形体的三角形网格模型，整个模型的表面没有 “裂缝”和t 型接头。图2 3 为一个标准形体的三角形网格模型；图2 4 为一个 非规则形体的三角形网格模型。 图2 3 球的三角形网格图2 4 牛模型的三角形网格 2 1 2 空间三角形的法矢量 由2 1 1 可知，三角形网格t m 中所有的三角形面片拼接起来可以形成一个 封闭的完整的c o 连续面，将整个三维空间分成了内外两个空间，其内部空间就是 t m 描述的物体所占用的空间，物体模型的表面就是这两个空间的分界面。为了 区分分界面所划分的内部空间和外部空间，必须指明一个空间三角形面片的两个 面，朝向物体内部的面称作“里面( i n s i d e ) ”，是不可见面：朝向物体外部的面称 作“外面( o u t s i d e ) ”，是可见面。 空间平面两个面的方向可以用其法矢量来描述，任意一个空间平面把整个空 间分为两个半空间，其法向量与这个平面垂直，由一个半空间指向另一个半空间， 如果逆着法向量的方向去观看这个平面，则能够看到的这一面就是这个平面的正 面，另一面则为反面。假设一个空间平面的方程为a x + b y + c z + d = 0 ，则其法矢量 为( a ，b ，c ) 1 3 3 】。 在三维空间中，三点可以确定一个平面，也就是说，t m 中的每一个三角形 面片均位于相应的一个平面上。假设t j 为t m 中的一个三角形面片，其三个顶点 的坐标依次为( x l ，y l ，z 1 ) ，( x 2 ，y 2 ，z 2 ) 和( x 3 ，y 3 ，z 3 ) ，则t j 的法矢量的三 个参数可以按下面的三个公式计算f 3 3 】： a = y l ( z 2 一z 3 、+ y 2 x ( z 3 一z 1 ) + y 3 x ( z l z 2 ) b 2 z i x ( x 2 一x 3 ) + z 2 ( x 3 一x 1 ) + z 3 x ( x 1 一x 2 ) c = x i ( y 2 一y 3 ) + x 2 ( y 3 一y 1 ) + x 3 ( y l y 2 ) 在笛卡尔右手坐标系统中，从某个方向去观察一个三角形，如果它的三个顶 点是依逆时针方向排列的( 如图2 5 所示，假设这个三角形三个顶点的排列顺序 是a b c ) ，那么按照右手法则，大拇指所指的方向就是这个三角形所在平面的法 矢量方向，由反面指向正面。 在一个三角形网格模型t m 中，为了保证三角形面片t j ( i = 1 ，2 ，m ) 1 4 的“外面，可见，就要求“外面”是正面，即要求t j 的法矢量是从“里面”指向 “外面”的，当视点是从“外面”看向“里面时，t j 的三个顶点必须按照逆时 针方向指定。一般地，现有的高科技仪器设备和技术提供或创建的三角形网格模 型都是符合这一要求的。 反 图2 5 三角形面片的方向示意图 2 1 3 三维几何模型上顶点的法矢量 三角形网格t m 是一个正则的三角形表面模型其中包括的图元类型只有三 种：三角形面片、线段以及三维点。t m 中不存在“裂缝”或t 型接头，也没有 孤立点、悬挂的线段或面，是一个封闭的无边界的模型，其中的每一条线段都是 两个三角形的公共边，每一个三维点也由多个三角形面片所共有。 因此，t m 中每一个三维点v i ( i - 1 ，2 ，f i ) 的周围都必有一个由三角形 组成的环，如图2 6 所示，环中的三角形都以v i 为一个顶点，这些三角形的集合 称作与顶点v i 相关的三角形集合t v i 。 同样的，t m 中每一个三角形面片t j ( j = l ，2 ，1 1 1 ) 的周围也有一个三角 形环，该三角形环中的每一个三角形都通过一条边或一个顶点与t j 连接，如图 2 7 所示这些三角形的集合称作与三角形t j 相关的三角形集合t t j 。容易得知， 如果t j = ( v 1 ，v 2 ，v 3 ) ，则t t j 就是t v l 、t v 2 和t v 3 的并集。 图2 6 与顶点v i 相关的三角形集合 图2 7 与三角形t i 相关的三角形集台 在立体空间中，任意一个三维点的法矢量方向是不确定的，而一个三维点甚 至可以拥有多个法矢量。根据文献【3 1 】【3 4 】所描述的简化包络概念和作用，内外包 络可看成原始模型表面的两个等距面，通过偏移原始模型表面上的每一个顶点来 构造包络，其偏移的方向就是每个点的法矢量方向。因此，为了构造原始表面模 型的内外两层包络，与文献【3 l 】一样，本文也假定原始网格模型中的每一个顶点 v i ( i = 1 ，2 ，n ) 均有且仅有个法矢量刀，且与v i 周围的那些相邻三角 形面片的法矢量之间的夹角小于9 0 度。 网格模型中顶点v i ( i = l ，2 ，n ) 的法矢量胛，。与v i 周围的那些相邻三 角形面片( 即t v i 中的三角形) 有着紧密联系，三角形面积越大对v i 就越重要， 因此本文将t v i 中所有三角形面片的法矢量进行加权平均，以每一个三角形的面 积作为权值，这样求得的矢量值就认为是v i 的法矢量刀，。1 3 5 1 假设t v i 中共有j 个三角形，其法矢量依次为n l ，n 2 ，n i ，面积依次为s l ，s 2 ，s j ，则： ，z 。= s ， 胛，s ，。 2 2 三角形收缩操作 本文研究工作的主要目标是将三角形表面模型进行简化，减少原始模型表面 分割的三角形数目。在1 3 2 节中介绍了很多模型简化的方法，本文采用其中提 及的三角形收缩操作来达到模型简化的目的。 三角形收缩操作将一个三角形收缩成一个点，这种操作会导致模型表面的网 格发生变化，但是只会影响到那些与这个收缩掉的三角形直接相邻的三角形。图 2 8 举例说明了个三角形进行收缩操作的前后情况，假设要收缩的三角形是t j ， 其t t i 中共有八个三角形，标记为t 1 到t 8 ，如图2 8 ( a ) 所示。将三角形面片 t ，的三个顶点移动到同一个位置，合并成一个新点v i ，同时那些与t i 三个顶点 相连的线段也都相应地连到v j 上，从而导致了与t i 相邻的那些三角形面片( 即 t t i 中的三角形) 发生变化，如图2 8 ( b ) 所示。 在三角形“收缩成点v j 之后，图2 8 ( a ) 中外围轮廓线之内的九个三角形 都有所变化，根据其变化的不同，可以分成三种类型。其中，t i 收缩成点；与t i 通过一条边相连的三角形将退化成线段，因为当t i 收缩成v _ j 后，公共边也将不 复存在，退化成点v j ，那些以此为边的三角形也就随之退化成线段了，如图2 8 1 6 ( a ) 中的t 1 、t 2 和t 3 依次退化成图2 8 ( b ) 中的三条边e l 、e 2 和e 3 ；而最后 一部分三角形则只是发生变形，这种三角形与t i 仅仅通过一个顶点相连，当t i 收缩成v j 后，这些三角形的一个顶点偏移到v j 的位置上，而另两个顶点留在以 前的位置上，依旧构成一个三角形，只是形状发生了变化，如图2 8 ( a ) 中的t 4 、 t 5 、t