（计算机科学与技术专业论文）流网格的并行与实时绘制技术.pdf

国防科技大学研究生院学位论文 摘要 随着三维激光测距和建模技术的不断发展，三维几何模型的精度越来越高， 数据量也越来越大，这给三维几何模型的绘制、编辑和传输等操作带来了巨大的 压力。这是因为传统的数字几何处理算法一般都要求将整个原始模型调入内存后 再计算，而计算机的内存容量是有限的，接近( 或超过) 内容容量的模型就无法 进行处理。为此，基于外存( o u t o f c o r e ) 处理技术成为大规模复杂三维几何模型 研究的热点。 o u t o f c o r e 通常先在外存上对模型数据进行重组，再通过不同的方式将需要 的局部数据调入内存中计算。为了解决常规o u t o f c o r e 算法中重组预处理时间长 和数据结构复杂的问题，网格流处理技术应运而生，该技术设计了复杂三维模型 的一种新的组织格式，以便实现对大规模复杂网格的绘制。 借鉴流网格的思想，采用并行处理技术，本文探讨了如何利用网格的流化格 式实现简单、高效的o u t o f - c o r e 实时绘制。主要工作包括以下几个方面： 1 设计了一种基于流网格的大规模网格模型并行绘制算法，该算法为绘制的每个 模型建立了一个单独的线程，通过一个互斥变量使模型对内存轮流使用，使得 多个模型能够并行的绘制。实验结果表明，这种方法对于解决现实问题确实有 效，能提高效率。 2 对大数据量模型的流网格格式建立了有效的模型细节等级数据结构，借助这种 数据结构实现了基于视点的动态l o d 控制的网格绘制算法，该算法绘制出的 模型能根据视点离模型的距离选择模型的细节等级，从而用尽可能少的数据为 用户提供逼真的可视化效果。 3 采用计算简便的基于平行平面族的网格切割方法，将大规模网格模型分割成数 据量较小的模型。并在网格分割的基础上实现了对大规模模型的网格绘制。针 对分块后的网格，使用前面的并行绘制算法，并且充分利用分块网格边界上的 对应关系，在一次循环中完成整个网格模型的绘制。在此基础上，将细节等级、 基于视点的控制方法也用到了分块后的大规模模型上。 主题词：流网格，o u t - 0 f - c o r e ，并行，细节层次，网格分割 第l 页 国防科技大学研究生院学位论文 a b s t r a c t w i t hm ed e v e l o p m e n to ft l l e3 ds c 锄i n ga n dm o d e l i n gt e c l m i q u e s ，t h e e d i m e n s i o m lm o d e l sa r em o r ep r e c i s i o na j l dl a r g e rs c a l e t h ef a c tb r i n g sg r e a tp r e s s u r e 白o g e o m e t r yp i 。o c e s s i n g ，e g ，r e n d e r i n g ，t r a n s m i t t i n g ，a n de d i t i n go p e r a t i o n s ， s i n c e t r a d i t i o n a ld i g i t a lg e o m e t 巧p r o c e s s i n gm e t h o d sm u s t1 0 a dt h ew h o l eo r i g i n a lm o d e li n t o m a i nm e m o 巧t op r o c e s s h o w e v e r ，t h ec a p a c i t yo fm a i nm e m o 巧i sl i m i t e d ，s o t r a d i t i o n a lm e t h o d sa r eu n a b l et oh a l l d l el a r g e - s c a l em o d e l st h a tn e a ro ro v e rm e m o 巧 c 印a c i 够t h e r e f o r e ，r e s e a r c h e r sh a v et os e e kg e o m e n yp r o c e s s i n gm e t h o d sb a s e do n e x t e m a lm e m o 叮，k n o w n 邪o u t - o f c o r ea l g o r i t h m s n o w ，t h eo u t o f - c o r ea l g o r i t h m s b e c o m et h eh o to fl a r g e s c a l em o d e l sp r o c e s s i n g o u t - o f c o r ea l g o r i t h m su s u a l l yr e o r g a i l i z et 坨d a t as e to fa3 dm o d e lo ne x t e m a l m e m o 巧i ns o m ew a y s ，a i l da c c e s sa n dl o a dt h el o c a ld a t as e t si n t om a i nm e m o 巧d u r i n g c o m p u t i n g h o 、v e v e r ，m o s to u t - o f - c o r ep r o c e s s i n ga l g o r i t h m sh a v el i m i t s ，e g ，t h e p r e - p r o c e s so fr e o r g a n i z i n g t h ed a t as e ti s c o m m o n l yt i i n e - c o n s u m i n ga n dt h e 1 1 1 1 d e r l y i n gd a t as t m c t u r ec o u l db ev e f ) ，c o m p l e xa n di n c o n v e n i e n tt oi m p l e m e n t m u l t i r e s o l u t i o nm o d e l i n g s 0 1 v et h e s ep r o b l e m s ，s t r e 锄i n gm e s h ，an e wf o r n l a to fl a r g e m o d e l s ，i sp r o p o s e dt or e n d e rl a r g ec o m p l i c a t e dm e s hm o d e l sc o n v e n i e n t l y i nm i sp 巾e r ，、eu s e ds t r e a m i n gm e s h e sa n dp a r a l l e l p r o c e s s i n gm e t h o d st o i m p l e m e n tr e a l t i m er e n d e r i n go fl a r g es c a l em e s h ( 1 ) f i r s t l y ，ap a r a l l e lr e n d e r i n gm e t h o do fs n e 锄i n gm e s h e s 、 ，a sd e s i g n e d at h r e a d w a sc r e a t e df o re a c hm e s h ，a i l dm o r et h a no n em o d e lw a sr e n d e r e di nb ym u t e x s e m a p h o r e r e s u l ts h o 、v e d t h a t t h i sm e t l l o dc o u l de n h a n c et 1 1 em u l t i m e s h r e n d e r i n g ( 2 ) s e c o n d l y ，a ne f - f e c t i v em u l t i r e s o l u t i o nf o r1 a r g e s c a l em e s hm o d e l s 、v a sb u i l ta n d l e v e l o f - d e t a i l ( l o d ) 、v a si m p l e m e n t e d d y n 锄i cc o n t r 0 1o fl o d so fm o d e l s 、v e r e i m p l e m e m e da c c o r d i n gt ot 1 1 ed i s 切n c eo fv i e w e r s g a z ep o i n tt oe a c hm e s h s o ， s m a l l e rd a t a ，w k c hc a nm e e tu s e r s v i s u a ld e m a j l d ( 3 ) t 1 1 i r d l y ，l a 唱e s c a l em e s hw a ss e g m e n t e di n t os u b - p a r t sb ys o m ep a u r a l l e lp l a n e s f o ra l ls u b m e s h e s ， t h ef o m l e rp a r a l l e lr e n d e r i n gm e t h o dw a se m p l o y e dt o a c c e l e r a t e dt h ev i s u a l i z a t i o n ；m o r ei m p o n a n t ，t 1 1 el a 唱e - s c a l em e s hc o u l db et o t a l l y r e n d e r e di no n ei t e r a t i o n ，s i n c ean o n - t r i v i a lr e - c o n s t r u c t i o nm e t l l o dw a sd e v e l o p e d b yu s i n go fc o 订i e s p o n d i n gb o u n d a r i e s 锄o n gp a r t s b e s i d e st h e s e ，l e v e l - o f - d e t a i lo f e a c hp a r tw a sb u i l t k e yw o r d s ：s t r e a m i n gm e s h ，o u t o f c o r e ，p a r a e i ，l e v e io fd e t a i l ，m e s h s e g m e n t a t i o n 第1 l 页 国防科技大学研究生院学位论文 表目录 表2 1并行绘制模型b 咖y 、h o r s e 和d m g o n 的结果2 8 表2 2并行绘制模型b u 蚰y 和d r a g o n 的结果2 9 表3 1多个模型各细节等级绘制的时间3 4 表4 1 模型绘制对比表4 3 第l i i 页 国防科技大学研究生院学位论文 图目录 图1 1网格模型2 图1 2 d i g i t a lm i c h e l a n g e l o 项引2 j 描述图。3 图1 3 流网格中点和三角形和点的跨度( s p a j l ) 4 图1 4 流网格格式的直观酬引5 图1 5网格分割实例【5 j 7 图1 6 处理数据流【12 1 7 图1 7 流网格的八叉树结构i ”j 8 图1 8 流网格与传统网格的区别9 图1 9 渐进式( 上) 和非渐进式算法( 下) 对比9 图1 1 0 典型的几何元素删除操作1 3 图2 1流形介绍18 图2 2 球的三角形网格模型1 9 图2 3 f 而n tf a c e 和f r o n tv e n e x 等的定义2 0 图2 4 点的激活和结束2 1 图2 5 普通处理网格和流水方式处理网格比较。2 4 图2 6 通过不同选择方法选择网格模型2 6 图2 7 不同方式选择模型绘制顺序。2 7 图3 1b 吣y 模型的简化效果图逆序3 3 图3 2 模型b u i l i l y 、h o r s e 和d r a g o n 模型不同细节等级的绘制结果3 3 图4 1根据分割结果对网格分割算法的分类【4 引3 6 图4 2 切割包围盒得到的分块空间分布3 9 图4 3 利用模型d r a g o n ，b u 肌y ，h o r s e ，d i n o s a u r ，b u d d l l a ，h a i l d 分块绘制产生的结 果：4 2 第1 v 页 独创性声明 本人声明所呈交的学位论文是我本人在导师指导下进行的研究工作及取得的研 究成果。尽我所知，除了文中特别加以标注和致谢的地方外，论文中不包含其他人已 经发表和撰写过的研究成果，也不包含为获得国防科学技术大学或其它教育机构的学 位或证书而使用过的材料。与我一同工作的同志对本研究所做的任何贡献均已在论文 中作了明确的说明并表示谢意。 学位论文题目：速圆整鲍羞鱼皇塞盟绘剑垫苤 学位论文作者签名： 嗍 产胂舢 学位论文版权使用授权书 本入完全了解国防科学技术大学有关保留、使用学位论文的规定。本人授权国 防科学技术大学可以保留并向国家有关部门或机构送交论文的复印件和电子文档，允 许论文被查阅和借阅；可以将学位论文的全部或部分内容编入有关数据库进行检索， 可以采用影印、缩印或扫描等复制手段保存、汇编学位论文。 ( 保密学位论文在解密后适用本授权书。) 学位论文作者签名：幽垒 吼 作者指导教师签名：墨型 日期： 凋年冶邮b 1 年吣膨b 国防科技大学研究生院学位论文 第一章绪论 继上世纪7 0 年代兴起的数字音频、8 0 年代以来的数字图像、9 0 年代以来的 数字视频之后，三维几何模型作为一种新的媒体形式，已开始逐渐进入人们的生 产和生活中。在虚拟现实、动画游戏等各个方面，三维几何模型因其更加丰富、 全面和生动的细节信息，正在逐渐取代传统的基于二维图像的表现方式。与此同 时，随着计算机硬件成本的不断降低和网络的不断普及，越来越多的用户要求能 够在p c 机上对这些三维模型进行浏览、编辑甚至传输。于是数据量的快速增长与 计算机有限的计算能力和带宽限制就形成了尖锐的矛盾，接近甚至超过计算机内 存容量的模型是无法用常规方法进行处理的。本文主要探讨的是如何利用外存 ( o u t o f - c o r e ) 来进行计算和处理网格模型，使得用户能够快速的对模型进行浏览、 编辑：以及如何利用外存( o u t o f c o r e ) 来对这些数据量超出内存容量的大规模模 型进行简单、高效的绘制，并建立细节等级模型。 1 1 1 网格模型 1 1 课题背景 随着数字几何模型的应用，迫切需要一种适用于数字几何模型的获取、存储、 编码、传输、显示等的媒介。于是在1 9 9 7 年，匈牙利科学院n ，考虑欠周到而没做。以后每想到此事， 都后悔万分 x 国防科技大学研究生院学位论文 越大，精细程度越来越高，表现能力也随之越来越好； 图1 1 网格模型 ( 3 ) 多边形网格模型只保留了物体最为重要的可视信息：表面信息。一方面这使得 它保存的信息量大大减少( 比起体数据而言) ，结构也比较简单，但是另一方 面也使得在处理变形等问题的时候遇到新的挑战； ( 4 ) 多边形网格模型与硬件绘制的需要非常接近。实际上，现在微机中所用的显示 卡，基本上都采用基于多边形网格的绘制方式，并对这种绘制方式进行了极大 的优化。当绘制其他形式的几何模型时( 如绘制样条曲面、c s g 模型、点云) ， 也一般在绘制的时候转换成网格进行绘制。 三维建模技术的发展已经使三维网格模型深入到各行各业，在许多领域都有着 广泛的应用。尤其是在虚拟现实、影视游戏动画、科学计算可视化、地理信息系 统等方面，都起到了越来越重要的作用。 1 1 2 所面临的问题 随着三维激光测距和建模技术的不断发展，获得真实物体的三维模型变得越 来越容易。为了充分表现真实物体的几何特征，三维建模过程中往往在物体表面 采取大量均匀的采样点，由此得到的三维网格模型也是均匀、稠密的。正因如此， 模型中的网格数目变得非常巨大，往往超出了计算机硬件的承受能力。例如，美 国s t a n f o r d 大学著名的“数字米开朗基罗工程( t h ed i g i t a lm i c h e l a j l g e l op r o j e c t ) ” 【2 】中d a v i d ( 图1 2 ) 雕像的一个三维模型，由大约8 0 0 万个三角形组成其原始数据则 超过了2 0 亿个三角形，存储量3 2 g b y t e ；与此同时，随着计算机硬件成本的不断 降低，越来越多的用户要求能够在p c 机上对这些三维模型进行浏览、传输以及交 互式编辑。于是数据量的快速增长与计算机有限的计算能力就形成了尖锐的矛盾。 第2 页 喜重i 岸明利投入复赤型缸篓阮举庸 拮等篓霎藿萋强荔薹羹萋羹薹薹辇冈囊薹霎耋解； 萎，霉霎萋薹菱蠢羹j 篷! 型；常羹。薹鏊羹i 萋i 薹粪冀鋈薹薹塞囊霎萎蘩荔 霎；馨囊薹霎霪冀霉羹鬟霎霎霪薹耋j 霎囊4 薹馨81 萋妻翥篓妻雾i 。5 羹薹；i 主菱翼当 薹嚣塞鏊彗! ；5 萋篓j ；摹鲣耄震震耋道j ；。囊薹8l 雪薹蚕耋垂奏量；= “翼羹囊笺蠢3l 霎篓囊雾 耄妻堇毒；ii 。奏蓁霎奏萋3i 羔冀薹塞蓊蓁藿蠢耄；i 。薹荆鋈攀l 霉囊薷翼星霉辇：蓁；囊姜霎靠 羹薹耋= 冀萎。墓簿；g 霉甜藿墓薹篓。穹希薹霎塞薹孙薹囊薹j 冀冀鋈鬟薹厕蓁薹蓥 囊薹耄羹i 羹璧塞羹羹薹霪薹雾。萋。羹蒌薹羹萎粪萎羹霪辇g j 鏊囊蚕薹；蠹薹霪鎏 雪霎鬟嚣篓霪琴囊鬻幅篓茎蓁蓁荔； 霎j 羹鼋拿点羹謇鬻粤：萋耋薹霪羹羹雾萋窭| 雾囊i 囊葡，基冀蓁囊壁雾萋萎 蠢，篓5 霉捌ii 奏霪雾笺凄囊蕈| l ；囊矍蕈；哩羹蓁雾妻霪霪i 霎篓羹! j 爹爹堇萋! ；。霎 雾薹霪。毒l 萋蓁薹 主蚕薹辜 ! 二。羹萋。i 零蠢菱茎薹雾鎏? j 。霉毳；萋i 藿4i 耄薹羹薹 妻毳羹雾羹! 。；囊登37 乒羹茎萝毳营翼i ! ；鋈善；主蠹囊雾 鏊摹摹委；羹雾i 霉萋受雾 至囊霎蠹蚕i ! = = 前饼“i 薹圆喜事! 囊善囊霎ii 。苗戡。i 翼域苴蓁垂霉尹l ；。霾萋。l 霎蓁蓁妻；ii ； 。委霾暖萎81 囊冀薹耋霎奏璧蚕蓍! ；3 羹萋蠹8i 雾羹霎震薹霆霎羹童l ；4 囊鐾璧i ! 喜事茎主ti i 耋l 。2 藿塞薹i 蓁耄囊笔妻；冀二耋| | 蘸翌2 ；鏊攀耋篙型萋萋蠢5 。蓁零冀囊羹跳 奏| i 。羹薹；羹羹蓁篓羹量掌兰j 磊堡雾= 薹委霎= 霉寻；竖霎霎蔷唑豳；薹蠢萋。 l 雾蕈霎箩i ? 目i ”霎羹萎妻8 鍪霪i 垂雾薹薹萋零：蒌篓薹薹薹薹薹荔一篓j 羹霎 蠢薹蓁羹鬟羹i 。孳羹委霎奏2 = 乖妻篓垂薹蓁雾秦薹重誊笺i 誓妻囊念冀= 蓁篱蓉孵 国防科技大学研究生院学位论文 点和三角形序列。当某个点第一次被引入的时候就激活此点，即调入内存，当访 问到点的最后一次相关的信息时，就排除出内存。称展开的活动点的集合为e ， 在i 时刻把网格分为处理的和未处理两种。前部面( f r o n tf a c e ) 的宽度或者简单来 说就是宽度，是聊甜i j e | ) 中的最大值，简单地说，就是同时处于活动状态的点的 最大数量。宽度( w i d t h ) 提供了一个内存的最低要求。因为任何流处理都必须使 得前部面在内存里。跨度( s p a n ) 是指的同一个三角形中，点索引的之差的最大值， 直观的意义就是表示某个点持续活动的时间。很明显宽度是要小于跨度的。同时 要注意到最多需要l o g ，( 删，z ) 位去索引这些点( 图1 3 ) 。 z ：) o 一 r o 其中黑色的表示三角形的跨度，浅灰色的表示点的跨度 图1 3 流网格中点和三角形和点的跨度( s p a n ) 通过采用不同的方法流化现在的点和三角形序列，来描述带索引的网格布局 特性：点的三角形跨度，是包括第一个和最后一个在内的，和三角形相关的点相 关三角形的数量。相反地，三角形的点跨度，这个三角形中的点最大的索引值和 最小索引值之差再加一。布局的点跨度是所有三角形最大的点跨度。同样地，一 个布局的点的宽度，是所有三角形中最大的那个。在网格中，访问点和三角形是 顺序的。点跳跃指的是，当具有比他大的索引值的点在他之前出现就称为跳跃。 布局的跳跃是指，同时发生的最大的跳跃点的数目。 而且，流网格格式关于点在三角形之前还是在三角形之后没有加任何限制。 流网格可以是先序的，即每一个和三角形相关的点都在三角形之前调入：同样地， 流网格也可以是后序的，即每个和三角形相关的点都在三角形调入内存之后才调 入。点的引入与其在流网格中出现并没有必然的关系，因为前面调入内存的三角 形可能在他之前就已经和其他三角形相关，而且已经调入了内存了。本文中只考 虑先序和后序。点最迟在和其第一次相关的三角形调入之后被引入，一个点被排 除出内存最早是在和最后相关的三角形排除出内存的时候。在先序中，可以通过 第4 页 国防科技大学研究生院学位论文 些基于外存( o u t o f c o r e ) 网格处理算法。这些算法通常先在外存上对模型数据进 行某种重组，再通过不同的方式将需要的局部数据调入内存进行计算。根据不同 的数据重组和访问策略，大致可分为分治、三角形池和联机处理、流网格等几类 方法。 1 3 1 大规模网格模型的处理方法 随着三维模型数据量的增长，接近甚至超过计算机内存容量的模型是无法用 这些常规方法进行处理的。因此，利用外存来进行计算和处理的o u t o f c o r e 方法 应运而生。 这里的c o r e 是指内核存储器( 内存) ，i n c o r e 指在内存中的，或直接通过内 存的，o u t o f - c o r e 指外存( 磁盘) 的，或者通过外存的。在计算机调用应用程序处 理数据时，应用程序和中间处理数据都是暂存于内存或是动态在内存中开辟的。 对于规模比较小的数据量，在处理时可以直接在内存中分配空间，但是对于大规 模数据的处理，比如g b 级的三维体数据的分割、配准和可视化，无法直接在内存 分配这么大的空间以处理，因此必须利用到外存磁盘来暂存这些数据，而在需要 对原始数据中某一部分小数据块进行处理时，动态地将相应的外存数据导入到内 存中。 因为相对于内存而言，外存可以是非常大的( 取决于磁盘容量或最大文件限 制) ，可以处理几g b 甚至几十g b 的数据量，但是同时，毫无疑问地，处理速度 也就相应地慢了很多，因为很多时间都花费在了内外存之间的数据导入出上面。 可以说o u t o f c o r e 实质上就是以时间换取空间。但我们又希望这个时间代价 尽可能小。因此如何设计内外存数据结构、数据访问机制，以及如何将其与具体 算法结合，以在尽可能短的时间内处理尽可能大的数据成为o u t o f c o r e 研究内容 的核心问题。 1 3 1 1 常规处理方法 ( 1 ) 分治方法【4 儿5 】：把大规模网格分割到足够小使得他们适合调入内存然后单独 处理小片。这些策略被用于分类、简化、压缩。切片需要首先解除相关性，而这 个步骤对于标准的索引输入形式来说是非常复杂的。 将大数据量的三维网格分割成若干小的分块( 图1 5 ) ，每一个分块的大小都小 于内存的容量，然后分别对每个分块进行处理。这是最为简单有效的处理方法， 但是由于处理后网格还需要进行拼接，因此网格分块边界上必须进行特殊的处理， 以保持连续性。当模型的数据量非常大时，这一过程可能需要重复多次，因此时 间开销可能很大。 第6 页 国防科技大学研究生院学位论文 图1 5 网格分割实例【5 1 ， ( 2 ) 三角形池方法【6 1 【7 】：将三角网格看成是一些互不相关的独立三角形的集合， 算法【引，其中三角网格首先被转换成流的形式，然后用顶点聚类网的方法加以简化。 移赢| 。然。，揍黎辜 攀雾霉骞：参爹爱i 一：?j j j 。? 忿。1 j 。、奶一 。1 亨j 一一j 。 j ，科，? ，墨l 一。一j 、：一一7 o ”。1 “。j t ， ， o h ”i 、， 、 、7 该方法还利用了二次误差度量方法【l o 】来控制每个顶点的误差。i s e n b u r g 等在此 第7 页 j 一 熬缀 麓熬鬟 国防科技大学研究生院学位论文 三角形使用了，这样他的索引值可以被解除以给别的点使用。从而保证了在内存 中的点和三角形的数量很少，使得模型可以利用现有内存来对他进行绘制。图1 8 显示了流网格格式同传统网格之间的区别。 a ) 襻s t a n d a r d v 0 3 1 1 0 2 v o 4 0 4o 5 v1 40 81 2 v o 9 0 5o 7 v1 oo 11 1 f241 f254 f3l4 f453 其中横轴表示三角形索引，纵轴表示点的索引，点从被引进到排除出内存这时间称其为活动的， 在图中以水平线的长短表示，传统的三角形网格格式( 间隔存储点和三角形的流网格格式。其 中负索引值的点表示的是已经排除内存的点) 图1 8 流网格与传统网格的区别 术语“渐进的”和“流”在计算机图形学中是同义的。这里所提到的流网格和 那种慢慢把细节加入到在内存粗糙的模型中的，直到耗完所有可用内存的一种渐 进式的几何传输多分辨率模型的方法完全不同。在流网格中，三角形和顶点都是 保存在个有限的，固定大小的内存块中，部分无缝的网格中被加入或者移除出 内存，是一个全分辨率滑动的窗口。图1 9 说明了渐进式和单分辨率的区别。 如果模型本身不具备很好的空间一致性，例如，每个三角形相关点的索引都 不相同，这样网格的就需要重新排列三角形和点的序列了。否则，内存可能不足 以存储由这种格式形成的流网格。 孥秽留霄 霄霄 图1 9 渐进式( 上) 和非渐进式算法( 下) 对比 使用这种网格格式，对传统网格经典的简化和压缩算法稍做改进后就可以用 于流网格的压缩。流网格能极大地提高简化和压缩的性能。因为网格( 重组后) 第9 页 m l 4 8 5 l、l玑玑仉，仉纠纠o r 3 4 4 9 4 ，一一川一一一一 霄蜉 国防科技大学研究生院学位论文 顶点周围的邻域都可以拓扑等价于一个圆盘。事实上，通过一些预处理方法，是 可以将非流形的网格转化成流形的。例如文献【l7 j 的算法将网格沿非流形边界剪裁 开来，边界上的顶点被复制，于是顶点周围的局部区域就成为一个流形。对于形 状复杂的三维网格模型，构造它的初始逼近网格并不容易，因此细化提升的方法 应用得比较少。常见的一些网格简化方法多属于抽取简化方法，大致可归类如下： 顶点聚类方法【9 】：将网格分割成小块，每一块中的顶点聚合为一个新顶点。该 方法简单高效，易于实现，但简化质量通常较差。 区域合并方法【l8 】：先将网格表面分成若干区域，然后将区域的边界简化成多 边形，最后对多边形进行三角剖分，得到简化网格。简化质量较高，但实现比较 复杂。 小波分解方法【19 】【2 0 】：利用小波分解理论将表面模型分解成一个基本形状加上 一系列顺序的表面细节。得到的逼近模型质量较差，且无法完全重建。 顶点抽取方法【2 l 】：迭代简化算法，每次删除一组顶点后，将留下的空洞进行 三角剖分。易于实现，简化模型的质量也比较高，是目前常用的方法之一。 迭代收缩方法瞄】【2 3 】：目前最为常用的一种方法，每次迭代中将网格中的一对 顶点合并成为一个新的顶点。易于实现，简化模型的质量很高。有可能改变模型 的拓扑结构。 上述几类算法在一般数据量的三维模型上能够取得较好的简化效果，尤其是 顶点聚类、顶点抽取和迭代收缩方法，应用十分广泛。但是，由于三维网格中的 顶点、三角形之间在几何、拓扑上都是相互关联的，因此常规的算法一般都要求 将整个原始模型同时调入内存进行简化计算。然而计算机内存的容量是有限的， 因此对于数据量非常庞大的三维模型，这些方法是 x 国防科技大学研究生院学位论文 在用三角形网格描述物体表面时，根据曲率可以很好地区分表面的一些特征 如地形数据中的峰、谷、脊在进行简化时，可在高曲率处保留尽量多的点，而在 低曲率处删除尽量多的点，通过计算顶点和三角形的曲率，把新顶点分布在曲率较 大的三角形上。 ( 3 ) 全局误差度量 全局误差是指所有点上近似误差的总和，控制全局误差通常可以得到较好的 近似效果，但也会增加计算量和算法的复杂性。在网格精化过程中，所增加的顶 点必须有尽量小的全局误差，例如可以把全局误差精确地定义为两个多边形网格 表示的曲面之间的距离。 ( 4 ) 俨特征角度量 多边形网格中顶点的重要性也可以用特征角来衡量，特征角可以定义为顶点 处任意两个相邻三角形的法向量之间的夹角中的最大者。 1 3 2 3l o d 自动生成算法分类 多边形网格简化算法进行分类的标准有多种。 ( 1 ) 拓扑结构保持型拓扑结构非保持型算法 在拓扑结构保持型简化算法中，必须保持模型的拓扑结构。大多数算法对输入 的数据模型有要求，如果模型包含退化情形( 如多边形重叠或边由两个以上的面片 共享) ，则不能进行处理。绝大多数简化算法【1 7 】【1 8 】【2 4 】【2 5 】【2 6 1 都属于这种类型。拓扑结 构非保持型简化算法并不保持模型的局部或全局拓扑结构。由于这类算法【2 4 】【2 5 】【2 6 】 的约束条件较少，因而模型的简化程度较高。在要保持较高帧速率且图形的视觉 效果可以一定程度下降时，可以使用这类算法，但是有时生成的简化模型效果可 能会很差。 ( 2 ) 自适应细分型采样型几何元素删除型 ( a ) 自适应细分型 这种方法要求首先建立原始模型的最简化形式，然后根据一定的规则通过 细分把细节信息增加到简化模型中，从而得到较细的l o d 表示【1 7 】。这种方法 不太常用，原因是在一般情况下构造最初网格的最简模型相当困难，它主要 适用于均匀的网格( 如高度场) 。 ( b ) 采样 这种方法类似于图象处理中的滤波方法，有时不能保持拓扑结构不变。它 对原始模型的几何表示进行采样，一种方法是从它的表面选择一组点【2 l 】，另 外一种方法是把一个三维网格覆盖到模型上并对每个3 d 网格单元进行采样 【2 引。在第一种方法的选择一组点时，又可分为随机选点或根据一定的规则选 第1 2 页 国防科技大学研究生院学位论文 择特征点，显然选择特征点的方法的近似程序高，但计算量大。 ( c ) 几何元素删除型 几何元素删除型算法通过重复地把几何元素( 点、边、面) 从三角形中“移 去来得到简化模型( 见图1 1 0 ) 。这里的“移去分3 种情形：一种是直 接删除，另一种是指通过合并2 个或多个面来删除边或面，第3 种是指对边 或三角形进行折叠。移去或删除操作一直进行，直到模型不能被简化或达到 用户指定的近似误差为止。绝大多数算法要求在进行几何元素删除时，不要 破坏模型的拓扑结构，大多数的模型简化算法都属于这一类型【2 6 】【2 1 7 1 。 钮一_ ( a ) 项点删除( b ) 三角形删除 眵一移q q ( c ) 边折叠成一个点( d ) 三角形折叠成一个点 图1 1 0 典型的几何元素删除操作 ( 3 ) 局部算法全局算法 全局算法是指对整个物体模型或场景模型的简化过程进行优化，而不仅仅根 据局部的特征来确定删除不重要的图形元素。有些全局算法中也使用到一些局部 算法的特征。全局算法的例子有t 咄【2 1 1 提出的在表面上重新分布顶点；h o p p e 【2 0 】 使用的全局能量最小化方法；c o h e n 【2 8 】提出的包络网格以及e c k 【2 9 】的小波表示方 法。局部算法是指应用一组局部规则，仅考虑物体的某个局部区域的特征对物体 进行简化，这些算法的例子有s c h r e o r d e r 【2 2 1 的顶点删除，r o s s i g n a c 的顶点折叠， h o p p e 【2 0 1 的边折叠和h 锄咖【2 3 】的三角形删除。 ( 4 ) 其它分类方法 除了上面三种主要的分类方法外，我们认为还可以有其它一些分类方法，如 视点相关性、误差可控性、实时性、连续过渡性等特征。 当模型越精细，要处理的顶点数目就多，绘制速度自然就慢。虽然可以通过 细节等级技术减小不必要细节绘制的问题，但并不能根本解决绘制真实感与绘制 速度的矛盾。这种绘制速度直接受限于所绘制模型复杂程度的问题，只有通过引 第1 3 页 国防科技大学研究生院学位论文 入新的网格观念来减小这种影响，即实现采用基于流网格的绘制方法。 1 3 3 三维网格的压缩 网格简化方法通过减少三角网格中的顶点和三角形数目，降低了模型的存储、 传输数据量，并且可以通过重建网格细节等级的方法，在绘制过程中恢复出必要 的细节。三维网格压缩方法【3 0 】采取的则是另一种途径，即通过编码解码过程减少 网格模型的几何、拓扑信息的存储量，而不直接对网格模型的细节信息进行消减。 最常用的网格压缩方法是将三角形网格模型拆分为连续的三角形条带 ( t r i a n g l es t r i p s ) ，于是三角形顶点的重复记录就大大减少，节省了存储空间【3 1 】。 这种方法有很多的应用和发展，如1 3 引。此外，通过平行四边形预测方法还可以减 少顶点坐标( 即网格的几何信息) 的存储量【3 3 。 另一类网格压缩方法通过坐标量化等手段对网格的几何信息进行编码，这是 一种有损的压缩方法。而近年来出现的一些方法中，通过重新建网将原始网格转 化成半规整的网格，然后利用一些常规的信号处理工具，如小波分析，对网格的 几何信息进行压缩【3 4 1 。这样网格在几何和拓扑两方面的压缩都是有损的。 近年兴起的“点绘制( p o i n t - b a s e d ) 的方法也可以看作是一种网格压缩的手 段。它完全抛弃了网格模型中的拓扑连接关系，仅保存几何信息部分，因而使数 据量大大减少，但是模型绘制的效果也相应的有所损失1 35 1 。 网格压缩方法在减少数据量的同时并不对模型的细节信息进行简化，因此在 数据传输中十分有用：但是它也因此无法提供不同l o d 的细节等级模型。目前有 很多方法将网格编码算法应用于大数据量模型简化的o u t o f - c o r e 方法【1 1 】中，取得 了很好的效果。 1 3 4 三维网格的绘制 大型模型的快速绘制在各种三维交互设计、科学计算可视化和虚拟仿真中都 有着非常重要的应用。近年来，随着三维扫描与建模技术的飞速发展，三维模型 的数据量急剧增加，包含上亿三角形面片的网格模型在实际应用中越来越常见。 例如波音7 7 7 的三维模型包含了3 5 0 m 的三角形面片。过去这些模型的交互显示只 能在高端的图形工作站上进行【3 6 儿3 7 j ，随着低端p c 机图形性能的大幅提升，普通 的p c 机逐渐成为一种可替代的选择，而且也出现了一些基于p c 机的大型模型绘 制方法【3 8 】【3 9 】【4 0 】。但是p c 机处理能力和内存容量是有限的，如何有效地分摊计算， 寻求c p u ，g p u 和i o 三者之间的效率平衡，己成为大规模场景绘制系统所面临 的难题。 由于大型模型无法一次性载入内存，就需要在使用模型时动态调入。而磁盘 第1 4 页 国防科技大学研究生院学位论文 i o 需要一定的时间，因此数据调度存在一定的延迟。如果能够使网格调入内存的 时间的延迟低于人眼能分辨的时间，则实现了实时绘制。考虑到人眼在某一时刻 某一观察位置上，所能看到的空间范围和内容都是有限的，因此在可视化处理时 对于可见范围以外的信息并不需要调入内存加以绘制，而是可以根据当前视点的 变化，将所需要的数据动态地调入内存，然后按照适当的细节等级进行绘制。这 样做不仅符合人眼观察的客观规律，同时可以避免不必要的大量处理，节省机器 的计算时间，从而大大提高绘制的效率。基于这样的考虑，国内外研究人员在大 规模模型绘制这一问题上从不同角度提出了多种优化方法，包括模型的分割、细 节等级( l o d ) 模型、可见性剔除、缓存预取、动态调度等多个方面。在这些系统中， 多数的方法【3 6 】都将模型分割组织成一定的层次结构，并为层次结构中的每个节点 生成静态的l o d 或者h l o d l 4 ，然后用这些l o d 或者h l o d 来近似地表示模型。 虽然这些方法可以对大规模场景进行有效地绘制，但是这种离散的方法在不同 l o d 切换时会产生“p o p p i n g ”( 跳跃) 现象【4 2 1 ，从而影响绘制的效果。 如何合理地组织数据，实现数据从硬盘到内存的快速交换和读取，是近年来 0 u t o f c o r e 数据设计研究的主要内容。v i t t e r 给出了基于外存算法的数据层次设计 方案【矧，在现有的计算机体系结构( c p u 快速缓存、系统内存、硬盘等) 中，各种 存储器的有效使用，对提高性能会起到很大的作用。在图形学中，大规模数字几 何处理【4 3 】【删和科学可视化中也提出了该问题的求精方法。由于大型模型的数据 不能全部储存于系统内存中，要实现数据的实时可视化，数据的组织和存储是一 件很重要的事。基于外存( o u t o f c o r e ) 的处理算法的关键是重新组织数据，使得数 据在外存模式下的访问频率尽可能低，该领域的处理方法在并行及分布式计算中 也很重要。 1 4 本文工作和创新点 1 4 1 本文工作 通过分析，可以看出现有的常规三维网格处理算法大多要求将整个网格模型 调入内存进行计算，因而在计算机内存容量和计算能力都十分有限的情况下，很 难对数据量庞大的三维模型进行交互式处理。 在基于外存的o u t o f - c o r e 的简化方法中，联机处理方法和三角形池处理方法 能够取得较好的结果，前者可以将常规方法拓展到大数据量的模型处理上，而后 者通过数据流的形式访问数据，内存使用量很低。但是这两种方法仍然存在一个 很重要的问题，就是对大规模数据需要一个较为复杂的预处理过程。如联机处理 方法需要将数据重组成特定格式的外存文件，而三角形池方法通常要去除网格中 第1 5 页 国防科技大学研究生院学位论文 三角形和顶点的相邻关系，将它们编码成数据流形式。这些预处理过程本身就是 一个代价很大的过程，也不易于实现。同时，这些算法产生的数据结构并不利于 实现网格的细节等级建模。 而基于流网格格式的处理方法实现相对比较简单，代价相对较小。可以将常 规网格的处理方法稍做修改即可用于流网格处理。多个网格模型可以同时使用不 同的方法调入内存，并行使用改进后的方法进行简化，为每一个分块网格建立细 节等级的数据结构。 显而易见，绘制单个流网格的时候对现有内存的占有很少，每个三角形和点 都仅被调入内存一次，在流网格绘制过程中大部分内存处于空闲状态，而且在大 部分时间内用户需要同时处理两个或者多个模型同时出现在场景中，对模型的精 度要求也不一样。 鉴于以上各种用户的要求，本文首先探讨了如何设计一种简单且高效的并行 绘制模型的方法，并且在此基础上建立有效的模型的细节等级数据结构，从而实 现对网格表面l o d 的交互控制。而后，针对数据量超大的三维网格模型，本文又 将这一系列算法推广成为单个模型分块绘制方法，使其能够对大型三维网格模型 进行快速的绘制，并且同样建立了模型细节等级数据结构，设计了基于视点的l o d 控制算法。 1 4 2 创新点 对于数据量接近或超过内存容量的大型三维模型，通过流化网格模型，本文 提出了一种并行绘制流网格的算法，这种算法的创新点在于，可以进行多个模型 并行的绘制。解决了原算法不能同时高效调入多个模型的问题，提高了系统效率。 本文还提出将l o d 技术应用于流网格模型实时渲染，该算法有利于改善实时渲染 的帧速度和精度的动态调整。利用流网格的流动性很好的缓解了实时渲染中的瓶 颈问题。同时根据需要自适应地对场景进行不同程度的压缩简化，解决了原来算 法与用户的交互性不强的问题，提高了系统效率。对于用不同方式产生流网格格 式的模型进行流绘制得到的结果是不一样。对于同一个模型的各个部分来说选择 的绘制方式也是不同，本文的方法扩展到了对于单个模型的各个部分进行并行的 绘制。并成功实现了对分块的流网格的细节等级建模和基于动态l o d 控制，这是 许多现有方法没有做到的。 综上，本文的主要贡献主要在于以下几点： 1 本文提出了一种并行的流绘制算法，使得多个模型能够并行的进行绘制。 实验结果表明，这种方法对于解决现实问题比较有效，能提高效率。