（计算机科学与技术专业论文）大型三维网格模型多分辨率构建与绘制.pdf

浙江大学博士学位论文摘要 摘要 随着三维扫描、计算机辅助设计和科学仿真等技术的发展和应用需求的拉动， 包含上千万甚至数十亿几何图元的三维网格模型变得十分普遍，如何实现这些模型 的交互式绘制成为迫切需要解决的难题。多分辨率技术作为一种非常有效的绘制加 速技术，一直得到广泛的应用。但是对于大型三维网格模型而言，这种技术的设计 和实现本身存在诸多难点。受限于内存容量，网格模型的几何数据及其辅助数据结 构不能完全装载进内存，无法直接应用传统的多分辨率构建与绘制算法；受限于总 线带宽和c p u 处理能力，大型三维网格模型的多分辨率构建普遍耗时很长。本文在 深入研究近年来大型三维网格模型简化和多分辨率技术的基础上，通过分析比较各 种方法的关键思想及其优缺点，提出并实现了能够有效减少大型三维网格模型多分 辨率构建时间的并行构建算法，以及兼顾构建速度和绘制质量的大型三维网格模型 多分辨率构建与绘制算法，研究并实现了适用于拓扑复杂、局部深度相差较大模型 的大型三维网格模型多分辨率构建与绘制算法，最后把上述成果扩展到网格( g r i d ) 环境上。本文的贡献和创新点主要体现在以下四个方面： 1 针对基于外存八叉树的大型三维网格模型多分辨率构建算法，提出了基于子 树的任务分割策略和基于基准测试的动态构建任务管理机制，实现大型三维网格模 型的多分辨率并行构建和负载平衡，有效地提高了大型三维网格模型的多分辨率构 建速度。 2 完成了基于自适应空间聚类的大型三维网格模型多分辨率构建与绘制算法， 既提高了简化质量，又保持了空间聚类算法的高效性。本文采用适应性八叉树对模 型的包围盒进行划分，自顶向下构建模型的多分辨率层次结构，较好地保持了原模 型的细节分布；并对多分辨率层次结构中每个节点所包含的三角形片段进行网格排 布优化，降低缓存的平均失配率；在实时绘制时，采用基于视点的细节层次选择策 略进行模型的细化，以及通过数据预取机制来隐藏磁盘i o 延时，进一步提高绘制性 能。 3 完成了基于表面分割的大型三维网格模型多分辨率构建与绘制算法，提供最 精细的顶点粒度细化选择，保证最佳的绘制质量。该算法采用双层次结构，由渐进 i i i 浙江大学博二l ：学位论文摘要 网格簇来表示模型的簇层次结构，用于视点相关的粗粒度细化，而由簇节点内渐进 网格构建顶点树层次结构，用于精细粒度的局部细化。本文采用g p u 实现渐进网格 顶点树的视点相关并行细化，极大地提高了模型的局部细化速度，减轻了c p u 的负 载，使其能够在g p u 进行局部细化时并行执行数据的预取，从而更为有效地隐藏数 据的i 0 延迟。 4 在前期的交互式可视化网格( g r i d ) 系统的实现基础上，通过扩展其运行时 环境层，为大型三维网格模型的多分辨率并行构建提供网格( g r i d ) 环境支持，实 现资源的动态配置与调度，增强并行构建过程的灵活性、容错性和可扩展性；并通 过扩展网格( g r i d ) 门户，为用户提供大规模数据集的可视化服务。 关键词：大型三维网格模型，多分辨率构建与绘制，视点相关绘制，网格简化，空 间聚类，表面分割，外存算法，渐进网格，网格( g r i d ) 浙江人学博士学位论文 a b s t r a c t a b s t r a c t w i t ht h ea d v a n c eo f3 ds c a n n i n g ，c o m p u t e r a i d e dd e s i g na n ds c i e n t i f i cs i m u l a t i o n t e c h n o l o g i e sa n dw i t ht h ep u s hb ya p p l i c a t i o nn e e d s ，m a s s i v em e s h e sc o n t a i n i n go v e r b i l l i o n so fg e o m e t r i cp r i m i t i v e sa r eb e c o m i n gp o p u l a r i ti sd i f f i c u l tt or e n d e rt h e s e m a s s i v em e s h e si n t e r a c t i v e l y t h eo u t - o f - c o r em u l t i r e s o l u t i o nt e c h n i q u e ，w h i c hi so n eo f t h em o s te f f i c i e n ta p p r o a c h e st oi m p r o v et h er e n d e r i n gp e r f o r m a n c e ，h a sb e c o m eah o t t o p i ci nt h ef i e l do fc o m p u t e rg r a p h i c s h o w e v e r , t h e r ea r em a n yd i f f i c u l t i e si nt h ed e s i g n a n di m p l e m e n t a t i o no ft h i st e c h n i q u ef o rm a s s i v em e s h e s f i r s t l y , a sg e o m e t r i cd a t aa n d a u x i l i a r yd a t as t r u c t u r e so fm a s s i v em e s h e sc a nn o tb ec o m p l e t e l yl o a d e di n t om e m o r y d u et ol i m i t e dm e m o r ys i z e ，t h et r a d i t i o n a lm u l t i r e s o l u t i o nm o d e l i n ga n dr e n d e r i n g a l g o r i t h mc a nn o tb ed i r e c t l ya p p l i e dt ot h em a s s i v em e s h e s s e c o n d l y , w i t hl i m i t e db u s b a n d w i d t ha n dc p up r o c e s s i n gp o w e r , t h ec o n s t r u c t i o np r o c e s so fm u l t i r e s o l u t i o n r e p r e s e n t a t i o nf o rm a s s i v em e s h e so f t e nt a k e sm u c ht i m e ，w h i c hi sn o tc o n d u c i v et o s y s t e md e b u g g i n ga n dr e a l - t i m ea p p l i c a t i o n s b a s e do ni n t e n s i v es t u d yo nm a s s i v em e s h s i m p l i f i c a t i o na n dm u l t i r e s o l u t i o nt e c h n i q u e si nr e c e n ty e a r sa sw e l la sa n a l y s i sa n d c o m p a r i s o no fk e yi d e a so fv a r i o u sm e t h o d s ，t h i sd i s s e r t a t i o nr e a l i z e st h ep a r a l l e l c o n s t r u c t i o no fm u l t i r e s o l u t i o n r e p r e s e n t a t i o n f o rm a s s i v em e s h e s t h e p a r a l l e l c o n s t r u c t i o nm e t h o di m p r o v e st h ec o n s t r u c t i o ns p e e de f f e c t i v e l y s u b s e q u e n t l ya n a l g o r i t h mf o rc o n s t r u c t i n ga n dr e n d e r i n go u t o f - c o r em u l t i r e s o l u t i o nr e p r e s e n t a t i o nf o r m a s s i v em e s h e si sp r o p o s e d t h i sa l g o r i t h mt a k e sa c c o u n to ft h es p e e da n dr e n d e r i n g q u a l i t y t h e na l la l g o r i t h mf o rc o n s t r u c t i n ga n dr e n d e r i n go u t o f - c o r em u l t i r e s o l u t i o n r e p r e s e n t a t i o n f o rm a s s i v em e s h e sw i t hc o m p l e xt o p o l o g ya n dl a r g el o c a l d e p t h d i f f e r e n c e si sp r o p o s e da n dr e a l i z e d l a s t l yt h ea b o v ep a r a l l e lc o n s t r u c t i o na l g o r i t h m sa r e e x t e n d e dt og r i de n v i f i o n m e n t t h ec o n t r i b u t i o n sa n dn o v e l t i e so ft h i sd i s s e r t a t i o na r ea s f o l l o w s ： 1 b a s e do nt h ee x t e r n a lm e m o r yo c t r e ec o n s t r u c t i o na l g o r i t h mo fm u l t i r e s o l u t i o n r e p r e s e n t a t i o nf o rm a s s i v em e s h e s ，t h i sd i s s e r t a t i o np r o p o s e sas u b t r e et a s kp a r t i t i o n m e c h a n i s ma n dab e n c h m a r km e a s u r i n gb a s e dd y n a m i cc o n s t r u c t i o nt a s km a n a g e m e n t m e c h a n i s m ，a n dr e a l i z e sap a r a l l e lc o n s t r u c t i o no fm u l t i r e s o l u t i o nr e p r e s e n t a t i o nf o r m a s s i v em e s h e sw i t ht h el o a d b a l a n c i n g t h i sp a r a l l e la l g o r i t h mi m p r o v e s t h e c o n s t r u c t i o ns p e e de f f e c t i v e l y v 浙江大学博士学位论文 a b s t r a c t 2 an o v e la p p r o a c hf o rc o n s t r u c t i n ga n dr e n d e r i n go u t o f - c o r em u l t i r e s o l u t i o n r e p r e s e n t a t i o nf o rm a s s i v em e s h e sb a s eo na d a p t i v es p a t i a lc l u s t e r i n g i sp r o p o s e d t h i s a p p r o a c hn o to n l yi m p r o v e st h er e n d e r i n gq u a l i t y , b u ta l s om a i n t a i n st h ee f f i c i e n c yo f s p a t i a lc l u s t e r i n ga l g o r i t h m i tk e e p st h ed e t a i l so ft h eo r i g i n a lm o d e lb yu s i n ga d a p t i v e o c t r e ep a r t i t i o n i n gt h em e s hb o u n d i n gb o x ，a n dr e d u c e st h ea v e r a g ec a c h em i s sr a t e t h r o u g hm e s hl a y o u to p t i m i z a t i o nf o rt r i a n g l e sc o n t a i n e di nt h eo c t r e en o d e a tr e n d e r i n g t i m e ，t h e m u l t i r e s o l u t i o n r e p r e s e n t a t i o n s t r u c t u r ei sr e f i n e da n dr e n d e r e dw i t h v i e w d e p e n d e n tl o d s e l e c t i o n a tl a s t ，t h em e t h o de m p l o y sd a t ap r e f e t c h i n gs t r a t e g yt o h i d ei ol a t e n c ya n dt h e ni m p r o v e st h er e n d e r i n gp e r f o r m a n c ef u r t h e r 3 an o v e la p p r o a c hf o rc o n s t r u c t i n ga n dr e n d e r i n go u t o f - c o r em u l t i r e s o l u t i o n r e p r e s e n t a t i o n f o rm a s s i v em e s h e sb a s eo ns u r f a c es e g m e n t a t i o ni s p r e s e n t e d t h i s a p p r o a c hp r o v i d e sv e r t e x g r a i n e dl o c a lr e f i n e m e n ta n dg e n e r a t e st h eo p t i m a lr e n d e r i n g q u a l i t y t h i sa l g o r i t h mr e p r e s e n t st h em o d e la sad o u b l eh i e r a r c h y ：ac l u s t e r e dh i e r a r c h y o fp r o g r e s s i v em e s h e sf o rc o a r s e g r a i n e ds e l e c t i v er e f i n e m e n ta n dav e r t e xh i e r a r c h yo f p r o g r e s s i v em e s h e sf o rf i n e - g r a i n e dl o c a lr e f i n e m e n t i no r d e rt oi m p r o v et h es p e e do f l o c a lr e f i n e m e n t ，ap a r a l l e lv i e w d e p e n d e n tr e f i n e m e n tm e c h a n i s mi sr e a l i z e db yu s i n g g p u ，w h i c ha l s or e d u c e sc p ul o a da n dm a k e si ta v a i l a b l ef o rd a t ap r e f e t c h i n g ，t h e n h i d e si ol a t e n c yf u a h e r 4 b a s e do nt h ep r e v i o u sw o r ko fi n t e r a c t i v eg r i dv i s u a l i z a t i o ns y s t e m ( g v i s ) ，t h i s d i s s e r t a t i o ne x t e n d si t sr u n t i m ee n v i r o n m e n tl a y e rt os u p p o r tt h ep a r a l l e lc o n s t r u c t i o no f m u l t i r e s o l u t i o nr e p r e s e n t a t i o nf o rm a s s i v em e s h e s ，c o n s e q u e n t l yr e a l i z e s d y n a m i c r e s o u r c ea l l o c a t i o na n ds c h e d u l i n ga sw e l la se n h a n c e sf l e x i b i l i t y , f a u l tt o l e r a n c ea n d s c a l a b i l i t yo fp a r a l l e lc o n s t r u c t i o np r o c e s s a d d i t i o n a l l y , t h i sd i s s e r t a t i o ne x t e n d si t sg r i d p o r t a lt op r o v i d ed i s p l a ys e r v i c eo f m a s s i v ed a t a s e tt oe n du s e r s k e y w o r d s ：m a s s i v e3 dm e s hm o d e l ，m u l t i r e s o l u t i o nr e p r e s e n t a t i o nc o n s t r u c t i n ga n d r e n d e r i n g ，v i e w d e p e n d e n tr e n d e r i n g ，m e s hs i m p l i f i c a t i o n ，s p a t i a lc l u s t e r i n g ，s u r f a c e s e g m e n t a t i o n ，o u t - o f - c o r ea l g o r i t h m s ，p r o g r a s s i v em e s h e s ，g r i d v i 浙江大学博! b 学位论文 图目录 图目录 图1 1 大型三维网格模型示例2 图1 2g p u 与c p u 的浮点计算能力增长表3 图2 1 顶点聚类算法10 图2 2 顶点移除和边折叠1 4 2 】ll 图2 3 从空间的1 2 个视点取得三维模型的外观图像l l 图2 4 网格模型的三个细：i f 了层次表示16 图2 5 网格模型的渐进多分辨率表示1 7 图2 6 顶点层次结构多分辨率表示示例刚6 2 1 18 图2 7 二叉树? 边折叠层次结构【叫l8 图2 8 基于四面体空间层次结构的多分辨率表示【6 6 l 1 9 图2 9 渐进网格簇层次结构多分辨率表示【6 丌2 0 图2 1 0 构建过程中内外存结构之间的对应关系【5 2 1 2 1 图2 11 基于几何图像的多粒度多分辨率表示 6 9 1 2 1 图2 12 细。仃层次选择策略结果示意图i 酬2 4 图2 1 3 顶点领域、影响区域和包围球示意图2 5 图2 1 4 视域体判断示意图2 5 图2 1 5 节点法向锥示意图2 6 图2 1 6 顶点层次结构背面判断示意图2 6 图2 1 7 聚类层次结构背面判断示意图2 7 图2 1 8 轮廓保留示意图一2 8 图2 19 细：竹层次混合示意图2 9 图2 2 0 使用几何变形调整边界分辨率1 7 8 2 , 9 图3 1m r m m 算法中的多分辨率表示二维示意图一3 4 图3 2 外存八叉树构建流程图3 5 图3 3 动态构建任务管理机制4 0 图3 4 任务管理性能比较4 3 图4 1 基于视点绘制5 1 图4 2t h a is t a t u e 模型在进行网格排布前和排布后的缓存失配比较图5 4 图4 3l u c y 模型分别用m r m m 算法和本文算法得到的局部结果比较图5 4 图5 1 可编程图形流水线5 8 图5 2 顶点层次结构中以顶点v 为根节点的子树结构【7 刁6 4 图5 3 模型绘制结果7 0 图5 4 原始模型内存绘制结果和本章算法绘制结果比较图7 1 图6 1 网格五层沙漏结构及与i n t e r n e t 协议体系结构的关系7 6 图6 2g v i s 体系结构7 8 图6 3 资源管理网格服务的功能模块结构图【9 4 j 8 1 图6 4 任务代理网格服务的功能结构图畔l 8 3 图6 5g v i s p o r t a l 网格门户8 4 图6 6m r p c 网格任务定制界面与任务查询窗口8 6 图6 7 系统客户端多应用多任务效果截图8 7 图6 8 分布式仿真与并行绘制结果8 8 浙江大学博士学位论文表目录 衣日汞 表2 1 大型三维网格模型多分辨率表示及其性能比较3 1 表3 1 外存八叉树：节点数据结构3 4 表3 - 2 内存八义树节点数据结构3 4 表3 3 八义树单机构建性能( 时间格式m ：s ) 3 7 表3 4 构建服务器生成的内存八义树节点数据结构3 9 表3 5 基于子树分割的并行构建结果( 时间格式m ：s ) 4 2 表3 6l u c v 模型的子树分割与分布一4 2 表4 1 内存八义树：青点数据结构4 7 表4 2 顶点记录数据结构4 7 表4 3 三角形记录数据结构4 7 表4 4 基于贪心优化策略的三角形绘制序列生成算法伪码5 0 表4 5 视点相关绘制时的内存八叉树肖点数据结构5 1 表4 6 八义树构建性能( 时间格式m ：s ) 5 3 表4 7 本文算法和m r m m 算法绘制性能比较5 5 表5 1 簇层次结构构建性能6 9 表5 2 绘制性能6 9 表6 1g v r e 信息索引中心数据模型定义8 0 表6 2 测试环境中网格节点的配置信息8 5 x i 浙江大学研究生学位论文独创性声明 本人声明所呈交的学位论文是本人在导师指导下进行的研究工作及取得的研究成果。 除了文中特别加以标注和致谢的地方外，论文中不包含其他人已经发表或撰写过的研究成 果，也不包含为获得逝鎏盘鲎或其他教育机构的学位或证书而使用过的材料。与我一 同工作的同志对本研究所做的任何贡献均已在论文中作了明确的说明并表示谢意。 学位论文作者签名：签字日期： 年 月 日 学位论文版权使用授权书 本学位论文作者完全了解逝姿盘堂有权保留并向国家有关部门或机构送交本论文 的复印件和磁盘，允许论文被查阅和借阅。本人授权迸婆盘堂可以将学位论文的全部 或部分内容编入有关数据库进行检索和传播，可以采用影印、缩印或扫描等复制手段保存、 汇编学位论文。 ( 保密的学位论文在解密后适用本授权书) 学位论文作者签名：导师签名： 签字日期：年月 日签字日期： 年月 日 浙江大学博上学位论文致谢 致谢 去年五一参加了大学同学毕业十周年聚会，大家见到我的第一句话几乎都是“你 怎么还在读书啊! ”呵呵，也是。同学们几乎个个都是拖家带口的了，有房、有车、 有存款，而我每天还在实验室混迹。虽然大学毕业后也工作过几年，正因为如此才 明白自己想要的是什么。校园生活简单、清贫但充实、快乐，因此在硕士毕业后我 选择了继续深造，攻读博士学位研究生。能够考入浙江大学我真得感到很幸运，坐 落于西湖畔的她很美丽，古朴庄严的教学楼，幽雅静谧的校园以及良好的学习科研 氛围，无一不令我深深心折。随着博士学位论文的完成，我在浙江大学c a d & c g 实验 室的近5 年求学生涯也即将结束，虽然其中经历了许多艰辛，也得到了很多人的帮 助。在此，我要对他们表达最深的感激和祝福。 感谢我的导师石教英教授。作为石老师的最后一名博士研究生，我经历了这个 大家庭从人丁兴旺到孤单一人，期间毕业离去的师兄弟姐妹留下了很多的感激之言。 是啊，石老师无论在科研上还是生活上都给予了我们一个良师、一个长辈无私而有 意义的指导和帮助，他渊博的学术知识、严谨的治学作风、敏锐的科学眼光、活跃 的学术思想以及积极热爱生活的态度为我们树立了科研、工作和生活等多方面的榜 样。然而，作为他的学生，我想我们大家最能感受到的应该是他的那份坦诚与关爱。 虽然很多师兄弟姐妹毕业离开了杭州，但每到教师节时许多留下来的师兄弟姐妹还 是会在百忙之中抽空聚到一起给石老9 币送上祝福，我想大家都是因为对石老师怀有 浓浓的感激之情以及被他的人格魅力所吸引才能做到的吧! 我很荣幸成为这个大家 庭中的一员，和众师兄弟姐妹一起在石老师的关爱中成长，祝福石老师身体健康、 生活幸福! 感谢姜晓红副教授，她在科研过程中给予了我很多帮助，在生活中平易近人让 我倍感亲切。感谢实验室的潘志庚老师和林海老师在我科研过程中给予的帮助。感 谢徐丹教授，既作为我硕士研究生时的导师，又是我的师姐，在她的指导和关心下， 我才能有机会进入实验室并且跟随石老师攻读博士学位。 感谢熊华师兄，是他把自己多年的研究积累传授于我并且给我提供了很好的研 究思路，他勤奋刻苦的求学态度和严谨的科研作风永远是我学习的榜样。感谢赵友 兵师兄、仇应俊师弟，通过对他们研究工作的学习让我对网格( g r i d ) 有了更深入 地了解，同时也极大地提高了我的编程能力。感谢刘真、庄玲、崔晨肠、秦爱红、 万贤美、白静几位博士及博士生在学习和生活中给予的诸多帮助，与你们谈心说事 让我研究生后期的“单身”生活仍就充满乐趣，不觉得孤单。感谢彭浩宇、王总辉、 李岩、周永霞、郁佳荣、杨珂、周然、毛祖秋、高可、殷萍、吴潜禄、戴芬、陈微 浙江大学博士学位论文致谢 微、王田、姜翰青等师兄弟姐妹，在实验室里，大家相互帮助，团结协作，我们在 一起学习的时光将构成我永久的美好回忆。 深深地感谢我的父母，求学数载，背后始终有你们的支持，使我心中安定、脚 下踏实，唯愿你们永远平安康顺，让我回报你们的恩情；感谢我的哥嫂们一直给予 我生活的支持和无私的关爱，祝愿你i f _ t - 作顺利，生活幸福美满；感谢我两个可爱 的侄子，每次假期见到你们都给我带来无穷的乐趣，从你们身上我看到了自己个性 上的不足，突然明白该如何做一个快乐、可爱的人，希望你们能健康成长，永远快 乐。有你们作为家人，我真得很幸福! 想要感谢的人太多，在此无法一一表述。最后让我再一次向所有关心、爱护我 的人们表示我最衷心的感谢。谢谢你们! h 张亚萍 浙江大学紫金港校区 20 1o 年1 月 浙江大学博士学位论文 第l 章绪论 第1 章绪论 1 1 大型三维网格模型的现状、应用和挑战 在过去的几十年间，模型获取、计算机辅助设计( c a d ) 和仿真技术等得到了 飞速发展，由此产生的城市扫描模型、自然风景模型、c a d 模型以及各种科学仿真 数据的规模都十分的庞大，达到g b ( 1 0 9 ) 甚至t b ( 1 0 1 2 ) 的数量级。例如由美国 斯坦福大学采用0 2 5 m m 激光扫描重建的d a v i d 雕像模型( 图1 1 a ) 大约包含1 g 个 多边形，是目前最大的扫描几何模型。而由萨尔不吕肯( s a a r l a n d ) 大学提供的风景 模型( 图1 1 b ) 则包含超过1 g 个多边形；波音公司的b o e i n g7 7 7 模型( 图1 1 e ) 包含3 5 0 m 个三角形，大约1 2 g b 数据量；c r s 4 和劳伦斯利弗莫尔国家实验_ 室( c r s 4 a n dl a w r e n c el i v e r m o r en a t i o n a ll a b s ) 的r i c h t m y e r m e s h k o v 等值面( 图1 1d ) 包含 4 7 2 m 个三角形【l 】。这些模型可以高度真实地保留原物体的全貌，在很多方面有很强 的应用需求，比如文物保护、数字化虚拟博物馆、影视娱乐、大型计算机辅助设计 ( c a d ) 、大规模信息处理等。 文化遗产的数字化是近年来比较热的一个研究邻域。为了“抢救”那些濒临损毁和 消失的珍贵文物，需要对其进行全方位3 6 0 度的数据采集，包括从里到外的每一个 细节，不仅希望能够对文物实施数字化保存，同时也希望能够就此探究文化遗产的 渊源、形成和发展过程。如斯坦福大学的“数字化米开朗基罗工程”，为了保存和恢 复这些古老的雕塑随着时间的流逝由于各种原因受到破坏的全貌，以及便于研究米 开朗基罗的雕塑手法，对雕塑作品进行三维扫描时已精细到保留雕塑表面的凿痕【2 1 。 三维模型在影视娱乐制作方面的应用可谓十分广泛。为了达到较高的视觉逼真 度，许多虚拟场景和人物的三维造型要求非常精细，特别是包含大量自然风景的虚 拟场景，每片树叶每棵小草都需要进行几何建模，整个场景的数据量变得十分的庞 大，甚至已经超过1 5 g 个多边形1 3 1 。如今的c a d 行业对工业模型的复杂度和精细 度要求也在不断攀升，包含上千万多边形的汽车模型到超过上亿多边形的航空模型 已十分普遍【4 j 这些应用领域的一个共同特点就是需要对模型进行交互式的绘制，然而如此巨 m 人学博学位论文 第l 乖缔论 大规模的图元绘制却给整个图形处理流水线带来了前所未有的挑战。传统绘制方法 需要把输入模型全部加载到内存、建立包含几何和拓扑信息的数据结构，而后依赖 于随机访问这些数据结构实现模型的交互武绘制。对于包含几千万甚至数十亿几何 囤元的大型三维网格模型，其内存需求通常已超出当前普通p c 的内存容量，无法 一次性装载进内存，例如s t m a t t h e w 模型包含约3 7 2 m 个三角形，厚始数据量为 9 ，6 1 i m b ，普通p c 显然难以完全将其加载到内存，导致传统绘制算法无法处理如此 庞大的模型，需要研究新的绘制算法。此外将如此庞大规模的图元全部提交给图形 流水线进行处理也会导致很高的绘制开销，例如t h a is t a t u e 模型包含1 0 m 个三角形， 原始数据量为3 7 7 m b ，直接将其敲入内存进行绘制每帧大概也需要消耗l3 s ，根本 无法满足交互式绘制的要求。 a ) d a v i d 雕像模型( i g 十边形) ( b ) 风景模型( i g 十；边形) 1 1 3 c ) b o e i n g7 7 7 ( 3 5 f ) m 个! 角形) 4 1 fd ) r i c h t m y c r - m e s h k o v 等值i ( 4 7 2 m5 - - 角彤) 田i 】大型二维网格模型示倒 浙江大学博士学位论文第1 章绪论 1 2 大型三维网格模型的绘制加速策略 尽管如今计算机的c p u 运算速度和图形硬件( g p u ) 的处理能力都得到了显著 的提高，如日本富士通公司研制的八核c p u v e n u s 的浮点计算能力能达到1 2 8 g f l o p s ，而a m dr a d e o nh d5 8 7 0 则更高达2 7 2 t f l o p s ，处理能力遵循着摩尔定 律飞速增长，如图1 2 所示【5 l 。然而大模型的绘制性能问题却始终存在，这是因为在 计算能力提高的同时更复杂、更庞大的数据集不断涌现；而更重要的是存储带宽和 数据访问速度的增长远远落后于处理能力的增长，不同层次的存储介质( c p u 缓存、 内存，硬盘) 间读取速度的差异进一步加大，如l 1 l 2 缓存的访问时间约为1 0 一s ， 内存为1 0 s ，而磁盘则是1 0 之s ，这使得数据的输入输出成为大规模数据处理时的最 主要瓶颈。因此，在绘制大型三维网格模型时必须有效地管理带宽需求，尽量控制 有用数据集的大小，降低绘制的数据量；充分利用缓存连贯性，减小数据的访问失 配率。这些方面的技术主要包括数据裁剪技术( d a t ar e d u c t i o n t e c h n i q u e s ) 、存储访问优 化技术和数据压缩技术【l 】。 8 0 0 图1 2g p u 与c p u 的浮点计算能力增长表 o o o o o 0 弼 轴 孙 的 ：兰 浙江大学博士学位论文 第l 章绪论 1 2 1 数据裁剪技术 当前的图形硬件在绘制包含上亿多边形的大模型时很难达到交互帧率，因此需 要尽可能地过滤对特定帧图像没有贡献的数据来达到降低绘制数据量的目的，能够 实现这一目标的技术称为数据裁剪技术，主要有可见性剔除( 只绘制可见的多边形) ， 多分辨率表示( 用较少的多边形来近似原始模型) ，基于采样表示和高阶图元表示( 使 用其他表示替代多边形表示进行绘制) 。 1 2 1 1 可见性剔除 模型中的图元一般不会同时全部可见，例如有些图元不在视域内，有些图元会 被其他图元遮挡。绘制这些不可见图元不但对最终生成的图像毫无贡献，还会增加 硬件绘制流水线的负担。可见性剔除技术通过离线处理或实时计算得到图元的可见 性状态( 又称为可见性计算技术) 6 1 ，剔除不可见图元( 不发送到绘制流水线) ，从 而减少每帧绘制的图元总量，提高绘制速度。可见性剔除技术包含视域剔除、背面 剔除和遮挡剔除三类。几乎所有的大规模数据集在进行交互式绘制时都考虑了视域 剔除和背面剔除这两项容易实现的计算；遮挡剔除的计算相对比较复杂，主要用来 加速处理那些自身深度相差较大、拓扑结果复杂的大规模数据集盯1 。 1 2 1 2 多分辨率表示 模型对绘制图像贡献的大小随其距离视点的远近而不同，例如距离视点远的模 型投影到图像平面的像素较少。在某些情况下，其投影面积甚至可能小于一个像素， 此时绘制相同数量的图元不但消耗了绘制资源，还会影响绘制质量( 出现走样现象) 。 多分辨率技术以模型简化为基础，通过预先构建出模型的细节层次表达，在绘制时 根据硬件平台性能和视点参数重构出最合适的逼近表示，能有效减少模型的几何复 杂度，提高绘制速度。多分辨率技术不仅可以应用于加快绘制速度，还可以应用于 多尺度信号分析、渐进传输、碰撞检测等多个方n t 7 1 。 1 2 1 3 基于采样表示和高级图元表示 上面两个小节分别介绍了只绘制对最后成像有用的部分以及根据对绘制图像贡 献的大小选择相应的模型分辨率进行绘制两项技术，采用基于采样表示或其他高级 图元表示代替三角形表示进行绘制也是目前一种非常有潜力的绘制加速技术。在过 4 浙江大学博上学位论文第1 章绪论 去，由于老的绘制流水线不支持高级图元，因此通常需要将其拆分为三角形或其他 中间形式。经过研究者的多年努力以及图形硬件的迅速发展，目前已经能够在g p u 上实现二次、三次和四次曲面的光线投射2 1 。直接绘制高级图元的优点是能够减 少对内存的需求，并且能够在较高的放大倍数下生成平滑视图。 基于采样表示方法与高级图元表示方法相反，主要是利用离散采样方法来表示 复杂模型，如点集或体素。这种表示方法的一个最大好处是简单，不用显式地管理 和维护网格连接信息。在g o b b e t t i 等人提出的f a rv o x e l s 方法1 1 3 】中，模型空间区域 被离散化为固定数目的立方体体素。通过预采样，每个立方体体素表示成类似于光 谱球的形式，包含了相应部分在各个视线方向的可见性信息，这样可以大大简化实 时绘制时候的遮挡计算。 1 2 2 存储访问优化技术 现代计算机系统普遍采用多级存储访问体系结构，例如高速缓存一内存一磁盘， 以减少数据访问时间、隐藏数据传输延时。这一设计理念同样体现在现代图形处理 器中，例如g p u 寄存器一g p u 缓存一c p u 显存。在多级存储体系结构中，不同存 储介质的存储容量相差很大，访问速度也相差若干数量级，数据访问效率往往是影 响应用程序性能的关键因素之一【7 1 。存储访问优化技术主要包括外存技术和缓存优 化技术两类。外存技术通过优化数据存储方式保证访问的顺序性，避免任意随机地 访问外存。缓存优化技术通过优化数据存储方式保证访问的继承性，降低平均缓存 失配率。 1 2 3 数据压缩技术 模型的多分辨率表示以及为了降低缓存失配率的缓存优化排布通常都会导致模 型的数据量增大，这对于大型的三维网格模型来说是十分不利的。网格模型压缩能 够有效减少存储空间大小和传输带宽需求，对于实时图形绘制具有重要意义。三角 形条带是目前常用的具有绘制加速能力的压缩数据表示，由一系列有序连接的三角 形组成。每个三角形和前序的一个三角形共用一条边，一个新点隐式定义了一个新 三角形，因此能够极大的减少模型的数据量。而且由于三角形条带具有较好的局部 浙江大学博：f ：学位论文第1 章绪论 性，绘制时能够有效的降低缓存失配率，提高模型的绘制速度。 1 3 本文的主要内容及组织安排 多分辨率表示作为一种非常有效的绘制加速技术，一直以来得到了广泛的应用， 这不仅是由于模型的多分辨率层次结构表示能够提供更为简单的模型表达来近似原 始模型，另一个重要的原因是这种层次结构能够很好地与可见性剔除、基于