（信息与通信工程专业论文）大数据量网格模型的建模与简化技术研究.pdf

国防科学技术人学研究生院学位论文 摘要 在计算机图形学中，模型通常山网格进行描述，复杂网格往往包括成千上万 个多边形，其大数据基是快速绘制的瓶颈如何在保证较高逼真度的前提下实现 快速绘制是目前亟待解决的难题之一。 论文对大数据量网格模型的建模与简化过程巾的若干关键技术进行了分析研 究。 针对网格模型的不同应用场合给出基于视觉特征的模型简化算法。该方法 围绕视觉特征的主要因索对模型进行简化较好地实现了大简化比和较高逼真度 的统一。 对于简化后的网格数据点，提出一利快速的三角形建模和法矢量重建的算法。 算法快速有效，并具有较强的通用性。 针对等高线数据模型的广泛应用，论文还给出了一种有效地利用等高线数据 模型进行建模的方法。较好地解决了基于等高线进行地景建模的难点。 为加快复杂空间场景的绘制速度。论文采用包围盒和包围球的策略对构成场 景的简化模型进行调度和预裁剪。 关键词：模型简化，三角形网格，法矢量，层次绸节模型 、j u 、j 国防科学技术人学研究生院学位论文 a b s t r a c t i nt h ef i e l do f c o m p u t e r g r a p h i c s ，o b j e c t sa r eo f t e nr e p r e s e n t e db yt r i a n g l em e s h ， a n dm e s h o f o b j e c tu s u a l l yc o n t a i n st h o u s a n d so f p o l y g o n s t h el a r g e - s c a l ed a t ao f t h e s em o d e l so v e r w h e l m st h e r e n d e r i n gp e r f o r m a n c e o f c u r r e n t g r a p h i c ss y s t e m s i ti s a n i m p o r t a n tf o c u sq u e s t i o nh o w t or e n d e ro b j e c tm o d e l r a p i d l ya n dk e e p b e a e r d i s p l a y q u a l i t y w e a n a l y z ea n dr e s e a r c hs o m ec r u c i a lt e c h n o l o g yi np r o c e s so fm o d e l i n ga n d s i m p l i w i n gf o rl a r g e - s c a l ed a t am e s h m o d e li nt h i sd i s s e r t a t i o n f i r s t ，an e wa l g o r i t h mf o rm e s hs i m p l i f i c a t i o ni sp r e s e n t e di nt h i st h e s i s ，w h i c hi s b a s e do nv i s u a le f f e c ti nd i f f e r e n t a p p l i c a t i o nb a c k g r o u n d o fm e s hm o d e l t h i s a l g o r i t h mc a n r e s e r v eb e t t e ri m a g eq u a l i t ya n dl a r g e rr a t i oo f m o d e l s i m p l i f i c a t i o n s e c o n d ，w ep r e s e n t a r a p i da l g o r i t h m f o r t r i a n g l em o d e l i n g a n dn o r m a l r e c o n s t r u c t i o nf o rm e s hd a t a p o i n t st h a th a v e b e e ns i m p l i f i e d t h i r d ，b e c a u s eo fw i d e s p r e a da p p l i c a t i o no fc o n t o u rm o d e l ，w eg i v ea ne f f e c t m o d e l i n gt e c h n i q u eu s i n g c o n t o u rm o d e l a tl a s t ，i no r d e rt oi m p r o v er e n d e r i n gs p e e d ，w ep r e s e n ta na p p r o a c ht oa r r a n g e o b j e c t si n t ol o d ，a n da na p p r o a c ht os e l e c to b j e c t si nc o m p l e xs c e n ea c c o r d i n gt o v i e w p o i n t k e y w o r d s ：m o d e l s i m p l i f i c a t i o n ，t r i a n g l em e s h ，n o r m a l ，l o d 瓤i v 贰 曼堕型堂丝查厶堂堕壅尘些堂丝鎏塞 第一章绪论 1 1 引言 三维数据模型在计算机图形学和科学可视化中有着重要的应用，也是近年来 的研究热点之。许多应用领域如计算机辅助设计、虚拟现实、医学应用、军事 领域、三维g i s 等，通过对三维数据模型的交互操作，模拟现实中很难实现或不 可能实现的种种环境，可以获得对真实物体更全面的了解，甚至可以获得真实世 界不可能获得的信息。 对于可视化系统，复杂的三维数据模型能够较好的表征原始物体模型，但需 要很高的硬件支持才能达到一定的绘制速度，有些模型数据甚至在极高的硬件支 持下也无法达到可接受的绘制速度。简单的数据模型虽然能够获得较高的绘制速 度，但在模拟原始物体模型上却缺乏足够的逼真度。逼真度、绘制速度是可视化 系统需要解决的关键问题。逼真度与绘制速度通常互为制约条件，即高的逼真度 通常导致低的绘制速度，反之，高的绘制速度则以低的逼真度为代价。因此，如 何实现二者的统一是一个极为重要问题。 在计算机图形学中，三维模型数据通常由多边形网格模型来描述物体模型， 这是出于多边形网格数据数学上比较简单，并且现在大多数图形系统都针对多边 形绘制进行了硬件加速。其他数据模型如曲面或者空间数据点集都可以按要求的 任意精度转换搬多边形网格数据。多边形网格数据以物体空间几何信息为基础， 可以任意选取观察角度、方位，对模型进行任意观察、编辑、修改、裁剪，具有 良好的交互性【l l l 2 1 【3 】1 4 】【5 l 【6 】【7 j 。网格多边形使用模型的内在联系表征物体模型，能够 保留物体模型的几何拓扑关系( 包括几何数据、几何拓扑与特征数据) 。 由于构成物体三维模型的多边形网格模型通常由上万个甚至更多的多边形面 片组成。一方面，将多边形映射为图像需要大量的计算，绘制时间和存储量与多 边形的数量成正比，过于庞大的物体网格模型通常是不实用的。并且在虚拟环境 中，通常并不需要对物体的各局部细节刻划得很详细。因此，为满足计算机分析、 显示与存储的要求，通常要对这类复杂的模型进行简化；另一方面简化模型具 有较低的逼真度，在离视点较远的场合能够较好表征物体原始模型。但在视点较 近的应用场合又不能很好的表征原始物体模型，因此需要根据视点与物体的距离 关系建立多级简化模型，在可视化系统应用中，采用多分辨率的模型调度策略。 本论文重点研究基于大数据量模型的建模与简化技术中的若干关键问题，探 索网格模型简化及重建技术与简化模型的调度策略，以期在一定程度上实现高逼 真度、高绘制速度及良好交互性的有效融合。 1 2 本课题研究的相关技术 1 2 1 网格模型简化技术 对大数据量模型的快速绘制是当今计算机图形学的难点与热点问题( i e e e c o m p m e rg r a p h i c sa n da p p l i c a t i o nm a r c h a p r i l2 0 0 1 的研究专题) ，长期以来，对 这一问题的研究有关学者进行了大量的探索，并取得了一定的成果。主要体现在 第l 页 层次细节模型l o d ( l e v e l so f d e t a i l ) 与模型简化上，而模型简化是l o d 的基础。 其主要成果如下： 基于顶点删除的网格删减方法降i s c h r o e d e r 提出了基于顶点删除的网格删减方法，其基本思路是指定一个最小 的距离阈值，如果模型中某顶点到由该顶点定义的平均平面的距离小于该闽值， 则删除该顶点，并采用递归循环分割法对删除顶点后遗留的空洞进行三角剖分， 通过调整距离阈值大小可生成层次化模型。s c h r o e d e r 将该技术应用于从医学c t 数据中提取的等值面模型及地形模型的简化，大量消减了原模型中的三角形数， 同时较好地保留了原模型的几何特征。s c h r o e d e r 算法具有简单，执行效率高等特 点，但是，其删除顶点的判据过于简单容易导致错误的几何拓扑关系【9 1 。 基于拓扑修正的顶点删除方法i i s c h r o e d e r 在基于顶点删除的网格删减方法的基础上对其中容易导致拓扑错 误的顶点删除判据进行了进一步的修正，并重点讨论了删除顶点后遗留的空洞剖 分，依据边长最短准则进行边折叠，如果该顶点所在边不能被折叠，则将该顶点 重新形成两个顶点，然后对新形成的顶点再次进行判决，直到给定的拓扑误差最 小。该方法较为有效地解决了几何拓扑错误问题，但算法的时间复杂度大大增加 了。 基于重新划分的多边形网格模型简化方法i l l i 该方法首先指定一个新模型所包含的顶点数，然后将这些点布置在曲面上， 原则是面积大的多边形内多布一些点，曲率变化大的多边形内多布一些点，薪点 集合中可以包含原模型中的点；生成由新旧顶点共存的网格，即将新点插入到原 模型中，修改原模型网格；最后删除模型中不在新点集中的顶点，得到由新布点 集合中的顶点组成的简化模型通过调整新模型中的顶点数，可以生成层次化模 型。这种方法仅适用于光滑曲面，且简化模型中引入了新点，增加了处理的时间 复杂度。 。 基于能量函数的网格简化算法i i 2 l h o p p eh 的能量函数法，其中能量函数山三部分组成：距离能量、表示能量 及弹簧能量。其中距离能量反映原始顶点集与简化模型的距离偏差。该能量越小， 表明简化模型对原始模型的逼近精度越高表示能量定义为表示因子c r e p 与模型 顶点数m 的乘积，c r e p 值越大，表明模型表示的简洁性越重要c r e p 值越小， 表明对原模型的逼近精度要求越高，因此通过指定不同的c r e p 值，可以控制模型 的复杂度，构造层次化模型。这种方法的特点是用能量函数的变化指导网格简化， 通过在能量函数中加入一项表示能量将网格简化视作一个网格优化过程，通过能 量函数中的距离能量变化反映出简化后的模型对原始模型的逼近程度。h o p p eh 给出了对三维扫描仪测量的数据模型进行简化的实例，效果十分理想，但算法的 执行效率很低。 基于顶点聚类的网格简化算法 算法的总体思路是用一个包围盒把原网格模型包围起来，通过等分包围盒的 各棱边将包围盒等分成若干个小的长方体，这样原模型的所有顶点就分别落在这 第2 页 国防科学技术人学研究生院学位论文 些长方体内；扫描这些长方体，如果某个长方体内有顶点，则把该长方体内的所 有顶点删除并生成一个新顶点，这个新顶点是被删除的原顶点的加权平均。这种 方法存在三个局限性：其一，由于原网格模型上的点在空间的分布是未知的，这 种方法对包围盒进行等分，可能导致等分后某些区域的长方体内包含很多的顶点， 而某些区域的长方体内没有或只有很少的顶点，这一方面造成空间和时间的浪费， 另一方面造成模型的某些部分过分简化；其二，生成某个长方体内的新顶点时， 这种方法只是取简单的加权平均丽并没有给出一种较好的误差控制方法；其三， 当原网格模型比较特殊时，落在某些长方体内的顶点可能属于原模型的差别较大 的部分，如果这些顶点聚类成一个顶点就会造成很大的变形 其他方法还有：r o f a r d 的边退化法、h a m a n n 的三角形删除法【1 5 】【1 6 l 、基于 八叉树表示的模型简化方法1 1 7 岬l 、基于简化包围盒( s i m p l i f i c a t i o n e n v e l o p e ) 1 9 1 1 2 0 1 1 2 1 1 的模型简化方法、基于感知系统的模型简化方法、基于超曲面 ( s u p e r f a c e ) 的模型简化方法、基于体索表示的模型简化方法、r e n z e n 和h l a d u v k a 2 2 l 的非结构化网格简化方法等。近年来，将模型简化与压缩结合也是一个研究热点， 如累进几何压缩1 2 副以及正规化网格1 2 4 i 等。 以上方法极大促进了l o d 与模型简化的发展上述模型简化方法通常是以 几何误差最小化为准则，此种准则可以较好地保证模型的几何坐标及拓扑关系的 正确性，具有一定的通用性，但是，对模型的视觉效果有较大的影响，并且不同 的模型有其不同的具体特征和应用，通用简化算法不能达到最好的效果，而且， 上述方法处理过程一般采用迭代算法，对于大数据量的三维数据模型。其处理速 度也会大受影响。因此，利用视觉j 瞳优化作为模型简化准则【9 l ，针对数据模型特 征进行简化是一种有效途径。 1 2 2 模型的重建技术 对于多边形网格数据。必须对简化后三维数据( 包括三维数据点、边和多边 形等等) 进行重新组织，也就是重新构造简化后的三角网，才能进一步进行处理。 这方面与本课题相关的研究成果主要体现在d e l a u n a y 三角网生成算法上。 三角网生成算法的研究已经比较成熟，t s a i 根据实现过程把生成d e l a u n a y 三角网的各种算法分为三类：分治算法；逐点插入法；三角网生长法【2 5 1 。s h a m o s 和h o e y 提出了分治算法思想1 2 们，并给出了一个生成v - 图的分治算法。l e w i s 和 r o b i n s o n 将分治算法思想应用于生成d e l a u n a y 三角网【2 ”。他们给出了一个“问题 简化”算法，递归地分割点集直至子集中只包含三个点而形成三角形，然后自下 而上地逐级合并生成最终的三角网以后l e e 和s c h a c h t e r 又改进和完善了l e w i s 和r o b i n s o n 的算法1 2 8 1 上述这些方法较好的解决了各自领域内的问题，具有较好的通用性。大数据 量三维网格模型，特别是规则网格模型，如地景模型，其模型数据包括简化后的 网格数据具有一些特殊性质，上述方法在处理这些问题时，其结果并不是最优的。 针对网格模型的这种规律性，我们将对传统算法进行一些改变，以加速处理过程， 提高处理效果。 第3 页 璺堕登鲎丝莶盔兰婴壅生些堂垡丝銮 1 3 本文的工作 1 3 1 课题内容 本课题针对大数据量模型的建模与简化技术中的若干关键问题，探索网格模 型简化及重建技术与简化模型的调度策略，并设计实现了模型简化与重建的软件 试验系统，并将模型调度应用于其中。课题主要内容如下： ( 1 ) 几何模型的简化算法研究 模型简化是复杂几何模型建模与绘制技术中研究的的主要问题之一在计算 机图形学领域。经常采用多边形网格来描述物体的几何模型。本文对网格模型进 行研究，围绕影响视觉效果的因素，提出了一种基于视觉特征的模型简化算法， 较好的实现了大简化比与较高逼真度的统一。 ( 2 ) 三角网生成算法及模型重建技术研究 简化后兰维数据( 包括三维数据点、边和多边形等等) ，必须进行重新组织， 才能进行有效利用。本文提出了一种适合简化后网格数据点及空间散乱点集的三 角形网的构建算法，并给出一种快速的求网格点法矢量均值的算法。同时，由于 等高线数据模型的广泛应用，本文还给出了一种有效的利用等高线数据模型进行 建模的方法。 ( 3 ) 如何提高绘制效率 对简化算法生成的不同层次细节模型，必须进行合理的调度，才能有效利用 简化模型，实现较高的绘制速度和较高的逼真度。本文利用模型平均三角形投影 面积作为进行模型调度和确定简化模型级数的原则，对不同层次细节的模型进行 有效的调度。一个场景通常是由许多独立的空问几何物体构成，而实际绘制场景 往往只是空间场景的一个区域本文将提供一种预裁剪算法对上述问题进行处理。 1 3 2 论文组织 ， 本文共分五章，各章的内容和组织如下： 第一章绪论。对课题研究相关的技术进行综述，给出了课题研究的目的、意 义以及本文的主要工作： 第二章网格模型的简化。本章根据视觉特征相关。针对不同应用场合，提出 了基于多边形法矢量、基于视点以及二者相结合的简化算法。 第三章模型建模与重建技术。本章给出一种三角网的构建算法，同时对模型 表面属性( 法矢量、纹理) 进行重建同时给出一种利用等高线数据进行地景模 型建模的方法。 第四章一种快速绘制策略。本章提出一利有效的模型调度策略和场景预裁剪 策略。 第五章结束语。对全文的工作及创新点进行总结。 第4 更 国防科学技术人学研究生院学位论文 第二章网格模型的简化 2 1 引言 模型简化是复杂几何模型建模与绘制技术中研究的的主要问题之一。在计算 机图形学领域，经常采用多边形网格来描述物体的几何模型。对几何物体的复杂 模型，其网格通常由成千上万个多边形面片组成由于将多边形映射为图像需要 大量的计算，绘制时间和存储量与多边形的数量成正比，过于庞大的物体网格模 型通常不能满足实时绘制的需要。因此，需要对模型进行简化。模型简化在虚拟 现实、交互式可视化、计算机仿真等领域具有广阔的应用前景。 国内外对模型简化的研究已有一系列成果。如基于拓扑修正的顶点删除方法、 基于重新划分的多边形网格模型简化、基于能量函数的网格简化算法、基于顶点 聚类的网格简化算法以及三角形删除法、基于八叉树表示的模型简化方法等等， 这些简化算法通常以几何误差的最小化为准则，可以有效地保持模型的拓扑结构， 但不能保证模型的视觉效果，事实上，模型简化是以牺牲逼真度为代价的，从绘 制角度而言，如何保证较少地损害逼真度以及较大幅度地降低复杂度是模型简化 的主要目的。 基于以上原因，本章提出了基于视觉特征的模型简化方法。对于空间场景中 网格模型，由于应用场合不同，影响视觉特征的主要因素也不同，对此，我们进 行如下处理：对于场景中的单个物体模型，如树木，飞机等，我们采用基于多边 形顶点法矢量的简化准则，对于大豹场景模型，如飞行仿真中的地景模型，我们 采用视点相关准则对模型进行简化。对于介于大的场景模型与单个物体间的模型， 如飞行仿真中的基地，机场模型等我们采用结合基于多边形顶点法矢撬和基于 视点相结合的简化方法。实验结果表明一t - 述方法能够在保持较高逼真度的前提 下实现模型的大幅度简化。 2 2 简化准则 网格模型是对曲面的逼近，理想情况下( 不考虑绘制时间，只考虑高度真实感 要求) ，可以使用曲面( 如b e z i e r 或b 样条曲面) 进行逼真绘制。而曲面的视觉特征 主要是其起伏变化及其视觉反映。从观察的角度看，这种变化具有很大的数据冗 余度，如大片平坦变化的区域( 如地景模型的草原、平原、瓮地、河床或变化平 缓的山地及其它模型的变化平缓区域等) ，网格模型的部分数据在一定绘制精度下 是不必要的。曲面的一维数学模型如图2 1 所示： 图2 1曲面的一维数学模型 第5 页 国防科学技术火学研究生院学位论文 则点a 的梯度为( 以g r a d ( a ) 表示点a 的梯度) ： g r a d ( 加f 抓】宅 将其扩展到欧氏空间，则： g r a d ( 口) = 【旦掣o x ；+ 鱼；盟j + 至掣o z 乏】l ，、一 卯1一 其中，a 表示点a 在世界坐标系中的坐标。 同理可以求得其它各点的梯度。 显然g r a d ( a ) = g r a d ( b ) = g r a d ( c ) = g r a d ( d ) ，即口、b 、f 、d 的起伏变化相同， 由此，b 、c 是冗余点，可以由矢量耐代替日6 、6 c 、耐，同时，考虑到g r a d ( e ) 、 g r a d ( ) 、g r a d ( g ) 以及g r a d ( i ) 、g r a d o ) 、g r a d ( k ) 、g r a d ( 1 ) 的变化很小，即起伏变化 很小，可以判定，工_ ，、k 是冗余点，即经过简化后，只剩下a 、d 、e 、g 、h 、i 、 ，点。 由于梯度表示方向导数取最大值的方向，即曲面起伏变化的最大方向，因此 以梯度来判决冗余点可以保证对曲丽的起伏变化影响最小。 为了降低绘制复杂度，通常使用网格面对曲面进行逼近，因此，可以使用网 格面中的细节法矢量( 如网格模型中的四边形、三角形或网格交叉点等的法矢量) 对曲面梯度进行近似，同时，模型的逼真显示通常需要计算法矢量，如光滑绘制、 消除马赫带效应等，因此使用法矢量进行判决可以减少不必要的计算量，大大降 低计算复杂度。 由以上分析可得到如下判决准则：计算模型的法矢覆然后由法矢量根据 绘制精度对冗余点进行判决。 对于复杂的几何模型如地景模型，一般采用等间距网格进行采样描述，网 格面进一步细分为多边形面( 一般为三角形而) ，几何模型的绘制过程，也就是多 边形面向投影面映射形成为图像的过程。映射过程一般以视点作为参考，距视点 较近的多边形面向投影面进行映射时。其投影面的尺寸较大，几何模型的细节保 留的也较丰富；距视点较远的多边形面向投影面进行映射时，其投影面的尺寸较 小，显然模型的几何细节也不能完全保留。 如下图，是一视点模型 c 图2 2 视点空间模型 图中，c 为观察点( 视点) ，s 为投影平面，w 为一空间等边三角形网格，显 蘸6 最 国防科学技术火学研究生院学位论文 然构成w 的网格线在投影平面投影的大小不同 投影过程的一维数学模型如图2 - 3 所示： f ；厂 图2 3 几何投影的一维数学模型 d 图中，为投影面，d 为视点，o ，o ”b 为空间中两相同尺寸的线段，则 0 4 ，0 ”b 在投影面上的投影0 朋，0 1 b 分别为： 令d = o a = o ”b 7 o = 0 0 l 。z i = 0 0 1 ，z 2 = 0 0 ”，姚： o | n ；z o 拿 z ， 。，6 ：乙善 z j 即相同线段在投影面上的投影与其距视点的距离成反比。 对于几何物体的网格模型。特别是复杂网格模型，由于其各部分距视点的距 离变化比较大，如果对每一部分都采用同一网格进行采样，显然不利于网格模型 的绘制。可依模型同视点的关系，将网格模型进行分割，对分割的每一部分采用 不同采样间隔。 由以上分析，得到如下判决准则：将模型进行分割成比较规则的小区域，依 据各区域同视点的距离关系采用不同的采样间隔。 综合上述两规则，将视点相关与基于多边形顶点法矢量的模型简化结合起来， 可得以下简化准则：计算模型的法矢量，以基本绘制精度为参考，依据视点距离 关系确定不同网格点的绘制精度，由法矢量准则对冗余点进行判决。 下面分别进行详细论述。 篇悬幕 璺堕型堂丝垄丕堂坚塞生竖鲎垡笙塞 2 3 基于多边形顶点法矢量的网格模型简化 2 3 1 绘制精度 定义绘制精度为占，当小于占时，网格点将被删除。现在讨论小于s 的条件， 设存在两个面“1 2 ，它们的法矢量分别为i 、石其央角为口，如下图： 图2 4 占的定义 以上，l 、h 也可以是网格中相邻的网格面，为了清楚地表示法矢量的关系， 将它们通过平移合并到一起( 不会影响法矢量的方6 1 ) 。考虑以下条件： l 、若口= o ，则石= 石，网格线、，：的相对起伏变化为0 ，o ，：可合并为一 条网格线； 2 、若口s 一万2 或口 2 ，则网格线“，的相关性为0 ， 、，：不可合并； 3 、若一万2 口 2 ，则网格线、，：具有一定的相关性，且口越趋于0 ， 其相关性越强( 当8 = 0 时该条件转变为条件1 ) ，可以根据所要求的精度决定o ，： 是否合并； 因此，口可以成为网格简化的条件，即口可以表示绘制精度，由此，令6 = 8 。 为了满足归化的条件，则： 8 = e | 芤 即取占为归一化的口值。 2 3 2 算法描述 网格模型在实际绘制时通常需要进一步细分，由于三角形可以决定一个平面， 因此通常将网格面细分为三角形面。若网格数为 1 x 疗，则三角形面的个数为2 ( m ，1 ) 。设存在如图2 5 的网格面， 图2 5 模型网格面及其三角形细分 菇l 页 国防科学技术人学研究生院学位论文 进行三角形细分后，对网格面中的任意一个交点p ，其周围将存在疗个f 此处 为6 个，仃= 6 ) 三角形，设第i 个三角形的单位法矢量为岛( f = 1 , 2 m ) 。现定义交 点p 的法矢量为其周围所有( 此处为6 个) 三角形法矢量的平均，并以；表示交点p 的法矢量，则： ；= 去喜i胪i 缶8 现对其进行归一化( 即取模为1 ) ，令归一化后的单位法矢量以s 表示，则： 窆i 翮。 窆i ，i ( 2 1 ) 上式即为平均后的单位法矢量，现将其定义为网格交点p 的单位法矢量。 为了使网格面进一步逼近曲面，现将交点p 的单位法矢量；进一步修正为：包围p 的所有交点的单位法矢量之均值。如图2 6 所示： p ip 2p 3 1r r p ，p ， p 7 成 p 5 图2 6 网格交点及其法矢量平均 包围p 的所有网格交点分别为pn ，p 2 p s ，这8 个交点的单位法矢量已由式 ( 2 1 ) 得到，分别为5 ，( - ，= 1 , 2 8 ) 。现对这8 个单位法矢量取平均，从而得到交点 p 修正后的新的法矢量，令该法矢量以q 表示，则： ；：虹 q _ i 备。 上式是根据p 周围的8 个相邻点得到的公式，对不同的网格划分( 如网格的不 等间距划分) ，p 周围的相邻点数可能有所不同。不失一般性，令p 周围存在埘个 相邻点，则上式变为： ；= 去喜i栌i 白 篱9 匿 对上式进行归一化，则上式进一步表示为： 一 口= 羔磊 至此，已得到交点p 所对应的单位法矢量g 对任意一个网格交点仇，则有 单位法矢量元与之对应。 现讨论删除交点p 的条件已知占是给定的简化精度，p 。，p 2 p 。是包围 交点p 的所有网格点( 其中，卅是包围交点p 的所有网格点数，图2 6 中，m = 8 1 ， q ，q 2 q 。是a ，p 2 p 。的单位法矢量。在p i ，p 2 栅所包围的区域中， 交点p 是控制点，这种控制分别针对8 个方向，即币，p 2 p 币，显然， 若p 被删除，对8 个方向均将产生影响，若此种影响是可以接受的( 即在精度要求 的范围之内) ，则p 可以被删除。因此，判断p 是否被删除时，8 个方向的影晌均 应该被考虑。从视觉效果的角度而占，这种影响将以p 的法矢量与包围该点的所 有交点p i ，p 2 p 8 ) 的法矢量的兴角来衡挝。若交点p 的单位法矢量；与 q i ，q ：q ，的夹角均小于占，表明p 与p l ，p 2 p 。的相关性均在占的控制范 围之内，故可删除网格交点p 。 也即，若以下逻辑表达式成立： a r c c o s o q , ) 司a n d a r c c o s ( 睁* q 2 ) c 】a n d 【牙牙， c 】- = t r u e 从而简化判别过程中的计算量，降低网格简化的运算复杂度。 2 3 3 算法总结 现将基于多边形顶点法矢量的模型简化算法总结如下： 步骤l ：给定精度占： 步骤2 ：对网格面进行三角形细分； 步骤3 ：计算网格交点的平均法矢量； 步骤4 ：扫描网格点，由绘制精度进行判别，决定是否删除该网格点； 步骤5 ：所有网格点处理完毕，算法结束，否则跳转步骤3 。 憨孵 国防科学技术人学研究生院学位论文 2 4 基于视点的网格模型简化 构建几何物体的网格模型时依据网格划分可以分为等问距与不等间距模型， 也就是均匀网格模型和不均匀网格模型，模型绘制时再将网格划分为若干边界相 连的四边形或三角形，一般多采用三角形网格面。由于均匀网格存储和处理上比 较简单，所以建模时，通常采用均匀网格模型，如地景模型，采用d e m 数据， 将地表等间距划分为m n 的均匀网格，绘制时通常将该网格细分为2 ( m 1 ) x ( n 1 ) 的三角形面片。地景模型根据地域的大小，采样间隔大小，其数据量 将急剧膨胀，数据处理时间和绘制时自j 将大大延长，为了简化处理过程，通常采 用等间距抽点的方法降低数据地。采刚抽点的方法处理网格数据，大大降低处理 的几何数据量，简化了处理过程，可大大提高了地景模型的绘制速度，但由于模 型细节信息丢失过多，实际应用中会出现较大失真。 由视觉观察特性可知，当视角已定，视点( 观察点) 距离观察目标越远，则 目标被观察的范围越大；反之视点距离观察目标越近，则目标被观察的范围越 小。同理，对于大几何尺寸的几何物体，如地景模型，距离观察点近的部分由于 观察范围比较小，其分辨率较高，其细节特征也比较明显：而距离观察点远的部 分观察范围比较大，分辨率较低，其细节特征并不突出。如何降低处理的数据量， 同时又能保证绘制结果失真较小，是本节需要解决的问题。利用视点相关，建立 视点与网格精度的对应关系对距离视点较近的几何部分采用较密网格，对距视 点较远的几何部分采用稀疏网格是一种切实可行的方案。 2 4 1 绘制精度 几何物体的绘制过程，也就是物体的空问几何信息向投影平面进行投影，投 影平面向绘制平面映射的过程。通常，采用计算机屏幕作为绘制平面，将空间几 何物体到投影平面的投影映射到计算机屏幕。计算机屏幕山点阵构成，每个点阵 都有一定的几何尺寸，所以计算机屏幕在空间上并不连续。在投影平面向计算机 屏幕映射的过程中，会存在一个织索的量化误差。如下图所示： ：厂 图2 7 几何投影及绘制的一维数学模型 图中，o ，a , o ，b 为空间一线段在距投影平面不同距离处形成的投影，投影0 ，a , o ，b 两线段向绘制平面进行映射，绘制平面通常采用计算机屏幕，o l d 在屏幕上的映 射尺寸大于一个象素，小于两个象索。0 ，b 在屏幕上的映射尺寸小于一个象素。 绘制过程中，由于量化误差的存在，实际上在计算机屏幕上只有o i t 2 形成一个象 素进行表征，0 ，b 在计算机屏幕上没有表征，未形成象素。 空间几何物体在投影平面的投影与物体距投影面的距离成反比，不考虑量化 第l l 页 国防科学技术大学研究生院学位论文 误差，物体在投影平面的大小与绘制平面的绘制尺寸成正比，则空间几何物体在 绘制平面的绘制尺寸与物体距投影平面的距离成反比对于网格模型，如地景模 型，在一定的距离下，其几何网格在计算机屏幕上不能形成象素，没有表征，这 些网格数据在处理时实际上为冗余数据。同时，为简化数据处理过程，绘制结果 也允许一定的误差，即对可视网格也要进行简化。为此，我们定义绘制允许误差 的屏幕象素点数n 为绘制误差，称之为n 个点的误差。 为处理方便，将计算机屏幕的象素反映射到投影平面，将绘制精度定义为： 其中s 为投影平面到绘制平面的比例因子。 兰鏖兰兰兰亲气 ；厂 图2 8 网格投影一维数学模型 如图令z o = o o t ，z t = 0 0 ，乃= 0 0 ” 则空间一维网格的投影1 为： f - ，一l ：玩丑一厅，血：。( 生一生) z 2z | z 2z i 令视点到观察点( 也就是观察方向) 的单位方向矢量为n 。，则线段端点到视 点的距离在投影轴上的投影z 为： z ? = o a 。z ，= o b 门。 线段端点到投影轴线的距离d 为： d ，爿o a 亓。ld j = io b 亓f ji 则一维网格在投影面上的投影变换为： l = z o ( 幽一掣) o a n oo b n o 通过上式可得空间线段在投影平面的投影。 对于空间网格，如图： 夔臻蕊 旦堕型堂堡查丕笔婴塞生基堂焦迨苎 p 1 p ，- | d ， r p - 口1 p7 i 口6p 5 图2 9 空闻网格模型 对于网格交点p 已知f 是给定的简化精度p s ，p ：，p 。，p 。是与交点p 相邻的四个网格点。显然若这1 ! 条网格线p 。p ， 投影小于允许的误差精度，则可将p 点剔除。 也即，若以下逻辑表达式成立： ：。l ( l ! 刿一l ! 刿) i 占a n d ：。i o p s o p 嘞 i 掣一掣) i 占a n d ：。i ”万n o o p “ 则剔除p 点。 为简化运算，令占，：坚刿一三 。 o p g o p j p ，p 。p ，p 6 p 在投影平面的 ( 刿一掣) f a n d n oo p ( j 掣一掣) i s ：t r u 。 0 兄_ i i 。o p 吃 占，；坚刿+ 三将上式变化为 o p 玩 z o h 繁 ， 裂啡， 裂q ， a n dk 氅刿 占，】；t r u e 一 o p 8 一 处理过程中，由于网格点的剔除。后续网格点的相邻网格交点也在变化，如 图2 9 的p 。点，其相邻网格交点就是p ，p ，p ，p ，处理时，就需计算网格 线p 9 p a ，p j p 8 。p p a ，p ，p 8 在投影平面的投影 基于视点的简化方法是在网格模型绘制过程中，依据视点建立误差准则，实 时生成一定复杂度的网格模型，这是一种动态的模型简化策略。模型绘制显示过 程不仅包括模型绘制时间还包括模型简化时间。模型复杂度降低，可以减少绘 制过程的处理时间，但模型简化过程也会降低模型绘制帧率，因此如何优化模型 简化处理过程也是很必要的。由于模型绘制过程中，视点的变化是连续的，绘制 过程的前一帧与后一帧中模型的改变并不大，因此，我们将模型剖分成一些网格 区域的组合，并与第四章中的复杂场景的调度策略相结合，以网格区域中心距视 点的变化率决定这一区域是否参与简化过程，实际参与简化处理的区域只是整个 网格模型的- - , j , 部分，从而简化模型简化的复杂度，提高模型绘制帧率。 簿l 藤 国防科学技术大学研究生院学位论文 2 4 3 算法总结 现将基于视点的的网格模型简化算法总结如下： 步骤l ：给定精度占； 步骤2 ：建立网格点相邻关系； 步骤3 ：从网格模型目标点开始扫描网格点，山绘制精度进行判别，决定是 否删除该网格点。若该网格点被删除。改变与该网格点相关的网格 点的相邻关系，若不被删除，继续处理； 步骤4 ：所有网格点处理完毕。算法结束否则跳转步骤3 。 2 5 基于视点和多边形顶点法矢量的混合简化 基于多边形顶点法矢量的简化方法事先对网格模型进行预处理，对于不同法 矢量误差，生成不同复杂度的网格模型，在网格模型绘制和应用时，依据一定的 准则进行模型调度，这是一种静态的模型简化和调度策略：基于视点的简化方法 是在网格模型绘制过程中，依据视点建立误差准则，实时生成一定复杂度的网格 模型，以满足绘制要求的帧速率，这是一种动态的模型简化和调度策略。 上述两种方法各有一定的优势和适应性，基于多边形顶点法矢量的简化方法 把网格模型简化过程中大量的处理和运算放在预处理过程进行，降低了绘制过程 中处理的复杂度，节约了绘制过程中系统资源的开销，但由于采用静态的简化与 调度策略，绘制过程中，不同复杂度的模型过渡过程比较生硬，系统资源也未得 到充分利用；基于视点的简化策略，充分利用了系统资源，网格模型的简化处理 过程在模型绘制过程中实时进行处理，模型的过渡也比较平滑，但由于采用动态 简化与调度策略，模型绘制处理过程比较复杂。 由于基于多边形顶点法矢量的简化方法和基于视点的简化策略相互并不排 斥，实际应用过程中，可以将上述两种方法结合起来，取长补短。可对网格模型 先进行基于多边形顶点法矢悬的简化处理。绘制过程中，再结合视点进行处理。 为统一和简化处理过程，需将各简化过程的算法进行优化和变化。 2 5 1 混合简化算法描述 基于多边形顶点法矢量的简化方法其误差判别采用顶点法矢量夹角，基于视 点的简化方法其判别准则采用网格在绘制平面的投影。为统一和简化处理过程， 我们把基于多边形顶点法矢量的简化算法的绘制精度转化为基于距离的误差判 别。 如下图： 图2 1 0 基于多边形顶点法矢量简化方法的绘图精度定义 疗，、吃为网格点p t ，0 2 的法矢量，对其作归一化处理，_ i i ，、元，为单位矢量 笫1 4 页 国防科学技术火学研究生院学位论文 其模为1 。则以下等式成立： i n l - n ，叫畸 口的取值范围为【o ，】，则a 2 的取值范围为【0 ，“2 。s i n 函数在【o ，2 区间内 为单调递增函数因此，我们可定义矢量差为绘制误差判别准则，将绘制精度由 矢量央角转化为距离( 矢赶差的模) 。 则2 3 节的判别式变化为： 【| _ i i 一厅，i c 】a n d “疗一_ i i ? i c 】a n d 【i 疗一亓。i c 】- - 一t r u e 对于基于视点的网格模型简化算法，其误差判据采用的是相邻网格点在投影 绘制平面的投影线的大小。在综合简化处理过程中，对网格模型先进行了基于多 边形顶点法矢量的简化处理，这一处理势必会改变网格点相邻关系。我们定义如 下函数： f * t 1 、 l 网格点保留，未被简化$ 0 【j网格点不存在，已被简化 其中i ，表示网格模型中网格点的纵向和横向位置。 进行基于多边形顶点法矢量的简化处理过程时，依上述函数建立原始网格点 的保留与删除的关系。基于视点的网格简化处理过程中，依据原始网格点保留与 删除的关系建立网格点相邻关系。 相邻关系的建立采用网格点周围”个方向的最短网格线进行分析。处理过程 流程如下： 图2 1 1 网格点相邻关系建立的流程图 流程图中，函数五、石为方向调整函数。其定义如下 当n = 0 ( 左方向) 五= l ，五= o ； 第1 5 页 璺陵型鲎壁鉴叁堂鲤塞生墼堂垡鎏塞 警n = l ( 上方囱) 五一o ，五= - l ； 当n = 2 ( 右方向) 五= 一l ，菇= o ： 当n = 3 ( 下方向) 五一o ，石一l 。 闷格模黧网格点的栩邻关系建或完成后，基于视点，从网格模型的目标点开 始，慰每令孵格点采耀2 4 辅误差刿澍准辅对模蘩进行进一步的简亿。 2 5 2 算法总结 现将基予多边形顶点法矢m 和骐予说点的嘲格模型混合简化算法总结如f ： 步骤l ：绘定糙浚占l ； 步骤2 ：对网格强进行三角形细分； 步骤3 ：计算网格交点的，i z 均法矢甜； 疹骤4 ：扫攒网格点，由绘锕精度遗行剡剐，决定是磴删除该网格点； 步骤5 ：建变多级躅辏楚化模鹫与视点距璃豹关系； 步骤6 ：对予当前简化网格模型，建立网格点棚邻关系： 步骤7 ：给定精度占2 ： 步骤8 ：麸溺格模型目标点开始扫摘网格点，由绘制精度进行潮剐，决定是 否测除该飚格点。羞该瓣格纛被删除，改变与该网格点榻关的瘸格赢韵柜邻关系， 整不被删除，继续扫描处理； 步骤9 ：结束。 2 6 实验缩果及其分析 我们采用湖南襁源地i 噩的d e m 趣墩模挺数据进行实验，以检验前面的简化 算法。模型为9 8 5 x 7 4 8 豹爨格数据，豢始溺格点数目为7 3 6 7 8 0 ，誊接形成静三 角形颟数为1 , 4 7 0 ，0 9 6 个。如此波大蚋三角形矮冀数，蓉不遴霉麓他处理，姆占鹰 大量的系统资源，绘制时f f i j 也是不可忍受的。以下给出简化试验结果。 2 6 1 篾纯结果 对于阍格点的简化，为了直观的表示试验结果c p 删除的网接点髑保罄的网格 点，我们将d e m 网格点转化为9 8 5 x7 4 8 的平谢图像，图像中簿一象素表示一个 网格点，不同性放的网格点，用不同的颜色进行表铽。如下图： 翻2 1 2 ( a ) 颓始地形模型阳2 1 2 ( b ) 网格点简化结染( 简化拢3 6 0 8 9 ) 藩l 孬蕞 国防科学技术大学 l j 究生貌学位论文 翻2 1 2 ( c ) 网格赢简纯结采 0 ( a b b c ) z = 0 r a b b c ) z 0 若三角形a b c 的方向为0 ，说明点a ，b ，c 在同一直线上。 定义2 凸壳：对于点集v ，若存在凸多边形打，其顶点均为点集v 中的点，并且 点集v 中所有其他点均在该凸多边形的内部，则称该凸多边形为点集v 的凸壳。 如下图： p 图3 1 点集多边形凸壳示意图 第3 2 熏 ，d ，jltj，flt【 = ) c口4 ( rrd 团防科学技术人学研究生院学位论文 图中所示。多边形h ( p ，p ? p ，p j j p j n ) 为点集v ( p t ，p 2 ，p 3 ，p ，p j ，p 6 ， p 7 ，n ，p d 凸壳多边形。 定义3 相邻点、前趋点和后继点：设为点集v 中的某点，n ，巾 ， o ：点0 位于有i 向线段a b 的左侧 o r t ( o ，a ，b ) i o q l ， q 点在三角形a b c 外接圆内。放三角形a b c 不是d e l a u n a y 三角形，需重