（计算机应用技术专业论文）三维植物网格并行生成及渲染算法研究.pdf

大连理工大学硕士学位论文 摘要 植物是一种重要的自然环境元素，对植物进行虚拟仿真和真实感渲染一直是计算机 图形学的研究热点之一，本文在前人工作的基础上，在三维植物网格并行生成及渲染领 域进行了一定的研究工作。 在三维植物网格生成方法上，本文提出了一种基于g p u ( g r a p h i c sp r o c e s s i n gu n i t ， g p u ) 加速的l 系统植物网格并行生成方法。该方法利用g p u 的s i m d 计算能力，将同 一迭代层次所有树枝的前驱数据分配到不同计算单元同时进行网格生成计算，使元数据 树生成和图形解释两部分工作完全在可编程图形硬件中完成，避免了原有基于g p u 的 l 系统方法需要c p u 参与的问题，绕开了计算机主内存与显存之间的数据传输瓶颈， 提高了算法的运算速度；在树枝多边形网格的生成过程中，利用f r e n e t 标架产生以任意 参数曲线为轴的植物三维网格，解决了传统方法只能生成特定形状树枝的问题。 在植物的真实感渲染方面，本文提出了一种基于深度剥离的屏幕空间环境遮挡植物 渲染算法( d e p t h p e e l i n gb a s e da m b i e n to c c l u s i o n ，d p a o ) ，该算法通过深度剥离过程萃 取了多深度层次的z b u f f e r ，为遮挡计算提供了更精确的遮挡采样片段，针对原有屏幕 空间环境遮挡算法存在的自遮挡距离误差问题，利用深度剥离技术进行了修正，从而得 到了更具有物理真实性的植物渲染结果。 实验结果表明，本文方法能够在高帧速率情况下实现三维植物网格的并行生成和真 实感渲染。 关键词：l 系统；植物；生成；环境遮挡；g p u 三维植物网格并行生成及渲染算法研究 r e s e a r c ho fp a r a l l e l3 dp l a n tm e s hg e n e r a t i n ga n dr e n d e r i n g a b s t r a c t p l a n ti so n eo ft h em o s tc o n i t l o nn a t u r a ll a n d s c a p e ，p l a n ts i m u l a t i o na n dr e a l i s t i c r e n d e r i n gi sa l w a y sah o t s p o ti nc o m p u t e rg r a p h i c sd o m a i n i nt h i sp a p e r , s o m er e s e a r c hw o r k f o c u s e do nt h i st o p i cb a s e do np r e v i o u se f f o r ti sr a i s e d i n3 dp l a n tm e s hg e n e r a t i n ga s p e c t , an e wg p u l s y s t e mp l a n tm e s hg e n e r a t i n gm e t h o d i sp r e s e n t e di nt h i sp a p e r e x p l o i t i n gs i m dc o m p u t a t i o np o w e ro fc u r r e n tg p u ，t h em e t h o d c a na s s i g na l lt h eb r a n c ha p i c e sd a t ai nt h es a m eh i e r a r c h yi n t od i f f e r e n tc o m p u t i n gs t r e a m st o g e n e r a t em e s h e ss i m u l t a n e o u s l y , w ea l s oi m p l e m e n tb o t hm e t a - t r e eg e n e r a t i o na n dg r a p h i c a l r e p r e s e n t a t i o no ng p uw i t h o u tp a r t i c i p a t i o no fc p ut oa v o i dm e m o r yt r a n s f e rb o t t l e n e c k s ； f u r t h e rm o r e ，a sf o r m e rb r a n c he x t r u d i n gm e t h o dc a no n l yg e n e r a t ec e r t a i nk i n do fb r a n c h ，a b r a n c hm o d e l i n gm e t h o db a s e do nf r e n e tf r a m ei sa l s or a i s e dw h i c hc a nc o n s t r u c tb r a n c h m e s h e su s i n ge i t h e rk i n do f p a r a m e t r i cc u r v e s i nr e a l i s t i cp l a n tr e n d e r i n ga s p e c t , an e ws c r e e n - - s p a c ed e p t h - p e e l i n gb a s e da m b i e n t o c c l u s i o na l g o r i t h m ( d p a o ) i sp r e s e n t e di nt h i sp a p e r f o rs o l v i n gt h es e l f - o c c l u s i o nd i s t a n c e e r r o rc a u s e db yp r e v i o u ss s a oa l g o r i t h m s 1 1 1 ep r o c e d u r eo b t a i n sm o r et h a no n ez b u f f e ri n d i f f e r e n td e p t hl a y e rb yu s i n gd e p t h p e e l i n gt e c h n i q u e ，w h i c ho f f e r sm o r ec o m p u t a t i o n a l a c c u r a c ya n dp h y s i c a lr e a l i t yf o rc a l c u l a t i n gs c r e e n - s p a c ea m b i e n to c c l u s i o nr e s u l tf o rp l a n t r e n d e r i n g a st h ee x p e r i m e n tr e s u l ts h o w s ：t h i sa p p r o a c hc a ni m p l e m e n t3 dp l a n tm e s hg e n e r a t i n g a n dr e n d e r i n gi nh i g hp e r f o r m a n c e k e yw o r d s ：l - s y s t e m ；p l a n t ；g e n e r a t i n g ；a m b i e n to c c l u s i o n ；g p u i i 大连理工大学学位论文独创性声明 作者郑重声明：所呈交的学位论文，是本人在导师的指导下进行研究 工作所取得的成果。尽我所知，除文中已经注明引用内容和致谢的地方外， 本论文不包含其他个人或集体已经发表的研究成果，也不包含其他已申请 学位或其他用途使用过的成果。与我一同工作的同志对本研究所做的贡献 均已在论文中做了明确的说明并表示了谢意。 若有不实之处，本人愿意承担相关法律责任。 学位论文题目： 作者签名： 三钨诅蜘i 庇器哥气1 ) 训列蚴埠 么石勺移 刁i 了睇 大连理工大学硕士学位论文 大连理工大学学位论文版权使用授权书 本人完全了解学校有关学位论文知识产权的规定，在校攻读学位期间 论文工作的知识产权属于大连理工大学，允许论文被查阅和借阅。学校有 权保留论文并向国家有关部门或机构送交论文的复印件和电子版，可以将 本学位论文的全部或部分内容编入有关数据库进行检索，可以采用影印、 缩印、或扫描等复制手段保存和汇编本学位论文。 学位论文题目： 作者签名： 导师签名： 芝钔胁，斌稆蜀匀j “尺渔三蹲 舂磊印弛 大连理工大学硕士学位论文 引言 植物作为常见自然景观的一种，其形状具有丰富多彩的细节和明显的不规则性，因 此很难用传统的计算机图形学方法进行真实感网格模型产生和渲染。自二十世纪六十年 代末以来，先后有多位学者对真实感植物的计算机仿真和渲染进行了长足的研究，并提 出了一些卓有成效的方法，如基于分形的植物建模、a 系统、粒子系统、基于人机交互 的植物建模和l - 系统等。 其中l 系统是一个著名的植物建模系统，由l i n d e n m a y e r 于1 9 6 8 年提出，随后 p r z e m y s l a w 、d e u s s e n 、w e b e r 等学者对【广系统做了大量的研究，对l 系统功能进行了 一定的扩展，使传统的l 。系统能够模拟更多种类的植物，并在一定程度上丰富了l - 系 统的植物学细节。 随着近年来电影特效、实时游戏等领域对网格模型镶嵌度要求的不断提高，而l 一 系统植物网格生成的计算量随着树枝层次的提高呈指数级增长【l 】，传统的基于c p u 的 l 系统方法r 益无法满足实时仿真应用的需求。从l 广系统的本质来看，它属于一种并行 字符串替换机制，在实现上很适合应用通用图形处理器g p u 的s i m d 并行方式对其进 行并行加速以提高原有算法的效率。随着g p u 在图形学领域应用的逐步扩展，昌经有 一部分文献提出了利用g p u 的高性能图形计算能力来加速l - 系统植物的生成：m e c h 等人于2 0 0 3 年开始尝试使用g p u 来产生l 系统植物拓扑结构，但并未提出如何根据拓 扑结构生成实际应用所需要的三维网格【2 】。b a e l e 等人于2 0 0 5 年提出采用c p u 产生l - 系统植物拓扑结构，并将结果送往g p u 的顶点处理单元进行植物三维几何网格的生成。 鉴于g p u 对三维向量运算指令集的优化，该算法加速了网格的产生，不过整个算法过 程是串行的，并且从c p u 到g p u 之间的数据传输构成了算法效率的瓶颈【3 ，4 j 。此外，为 了达到照片级真实感的植物渲染效果( p h o t o r e a l i s t i cr e n d e r i n g ) 这一目的，仅仅提供高镶 嵌度的植物网格是不够的，还需要为已产生的植物网格提供真实感的阴影和光照，以进 一步增强由l 系统产生的植物的真实感。 针对上述问题，本文提出了一种基于g p u 加速的l 系统植物三维网格并行生成算 法：该算法从原有l 系统实现方法在效率和真实感上的不足出发，充分利用现有g p u 的s i m d 并行计算功能，将整个植物几何拓扑构造过程放入g p u 中进行并行计算，并 对其结果在屏幕空间内进行了环境遮挡阴影的计算，在一定程度上增强了植物网格的真 实感。 综上所述，本文主要解决了以下几个问题： 三维植物网格并行生成及渲染算法研究 ( 1 ) 改变了以往l i 系统实现的串行字符串迭代过程，使之在完全在g p u 上得以并 行化实现，并直接生成任意镶嵌度的三维网格。 ( 2 ) 提出了适于g p u 实现的基于f r e n e t 标架的树枝生成方法，以较小的时间开销 生成以任意参数曲线为轴线的树枝。 ( 3 ) 提出了一种基于深度剥离的屏幕空间环境遮挡算法，修正了原有屏幕空间环境 遮挡算法的自遮挡距离误差问题，提高了植物网格模型阴影渲染的真实感。 实验结果表明，本方法能够为高几何镶嵌度植物网格的生成和渲染提供完整的解决 方案，在取得真实感的渲染效果的同时，有效地提高了算法的计算速度。 大连理上大学顷十学位论文 1 植物网格生成算法综述 对树木、草体、森林等各种植物形态进行虚拟仿真一自是计算机图形学研究的热点 方向之一，植物作为常见自然景观的一种，其形状具有复杂多样的细肯和明显的不规则 性，因此很难用传统的汁算机图形学方法进行真实感网格模型产生和渲染。另外，植物 还拥有与其他自然景观元素不同的特点。第一，植物是种生物，植物的l l _ 片通过光合 作用从太刚光能量中获取养料，植物的根系通过这些养料使植株成k 成熟，新q ：的枝条 不断地生长出来。甘的枝条逐渐娈得粗壮，每一种植物都有自己特殊的生长方式，有自 己特有的丰富复杂的三维结构。第一二，植物的形状特点是规则与不规则的综合体，很容 易区分某一植物的类型，但是对于可一种类型的植物在自然界是找小出完全相同的两 棵而且植物的生长过程中，还要受到各种环境因素的制约，比如太阳光能的强度，地 球引力的作用，地表水分的不均匀分靠，风、阿、雪等自然现蒙的影响，以及一些人为 因素的作用，这提高了对植物形状模拟的难度h 】。 凹i1 d e u s s e n 文中的二维植物算机仿真被粜 f i g ii3 dp l a n ts i m u l a l i o n i n d e u s s e ns p a p e r 除其自然特性以外，作为典型的观赏性景观作物，辅物往往只有定的艺术性羊u 荚 感j 。古代吟咏植物的诗列浩如娴海：“碧玉妆成一树高，“条垂下绿丝绦”，“红豆 生南固，春束发几枝”，早在唐束两代，贺知章，土维等诗人创作了无数赞咏植物亦或 挺拔“* 韧，办或婀娜多姿的形状特征。因此，在艺术型植物三维网格生成的过程中，需 要结合定的荧学思想。而美学和艺术往往被认为超过了计算机技术能力的范围，凼此 使计算机对茭的模拟具有一定的难度口】。 维植物网格并行生成及渲染算法研究 1 1 植物网格生成研究背景 目前对植物刚格生成的模拟方法大致分为基于分形的植物建模方法、植物建模的 a 一系统、粒子系统、交互式植物建模和l - 系统口】。 111 基于分形的植物建模方法 分形几何可以说是柬自于一种思维上的理论存在。该方法最早于1 9 7 3 年山 m a n d e l b r o t 在法兰西学院授课时首次提出。分形( f r a c t a l ) 、分数维等诃，是m a n d e l b r o t 创造出来的，其原意具有不规则、支离破碎等意义。分形几何学是一fj 以非规则几何形 态为研究对象的几何学。由于不规则现象在自然界是普遍存在的，因此分形几何又称为 描述大自然的几何学。分形儿何建立以后，很快就引起了许多学科的关注，这是由于它 不仅在理论上，而且在实用上部具有重要的价值 1 。 幽12 o p p e n h e i m e r 史 i 的分形植物 f i gl 2 f r a c t a lp l a n t i n o p p e n h e i m e r s p a p e r 利用分形几何进行植物网格建模，最甲由o p p e n h e i m e r 于s i g g r a p h 8 6 提出”。 在其著作巾，植物的生长山一些基本参数控制，这些参数包括予树枝与母树枝的夹角， 子树枝相对母树枝长度的收缩比例，数值的半径收缩比例，了树枝相对母树枝的旋转角 以及母树枝上生长的子树枝的树木。然后根据这些参数递归地生成新的子树枝，同时在 植物的每一，lk 新的子树枝的节点处对数值生长参数进行随机扰动，使牛成的植物更加 大连理工大学硕士学位论文 真实，使它具有统计自相似的特点而不至于显得过分规则。b a r n a l e y 随后提出了基于分 形和仿射变换的i f s 系统【9 】。该系统通过对这些仿射变换的重复迭代生成复杂的分形图， 包括用i f s 生成植物的形状。 分形理论是一套在理论上非常完美的系统，需要在植物的生成中，采用大量的空间 点来表示植物的形状，因而给植物的生成处理带来一定的困难【5 】。 1 1 2 植物建模的a _ 系统 a o n o 提出的a 系统是较早的一种对植物三维结构的真实感建模方法【i o 】，该方法为 植物建模研究提供了许多值得借鉴的思想和方法。该文主要做了以下几部分工作： ( 1 ) 对植物的基本形状做了一个简单的分类：单轴型植物、二分型植物、三分型植 物和混合型植物。 ( 2 ) 从植物的生长特性出发，文中提出了一个植物树枝的生长算法，树枝生长由如 下参数控制：树枝相对母树枝的夹角，树枝长度的收缩比例因子，树枝的生长方向规定 为母树枝的最大梯度平面内，另外还给定树枝生长方向相对树枝的旋转角。 ( 3 ) 对树枝生长方向变化提出五类模式：树枝从底到高生长角度递减、开始变慢递 减然后快速递减、开始快速递减、开始快速递减然后慢慢递减、开始慢慢递减然后快速 递减然后又慢慢递减和开始慢慢递增然后慢慢递减。 ( 4 ) 提出了对植物进行三维变形的一致偏离方法和非一致偏离方法，通过设置吸引 因子和排斥因子控制对植物的三维变形。这是较早的一种模拟植物变形的处理方法，采 用一致偏离方法和非一致偏离方法可以在一定程度上模拟风力对植物形状的改变和重 力所导致的植物树枝形状的弯曲，但这只是对生成植物的简单变形处理。 1 1 3 粒子系统 1 9 8 3 年由r e e v e s 等首次系统地提出了一种用于不规则模糊物体建模的方法【1 1 1 。该 方法适合模拟整体的自然生态环境。粒子系统是一种随机建模算法，系统由大量的粒子 组成，粒子之间是相互独立的，粒子随时间而移动并变化形态，粒子的位置、属性和动 态主要根据约束的随机过程定义，每一个粒子都有自己的产生，发展，直至死亡的整个 过程，粒子系统适合模拟一些不规则的物体，比如云、雾、山等。在结构化粒子系统中， 粒子不再是独立的，它们之间有复杂的联系，比如在模拟树群，草地等自然环境中：树 枝、叶子、小草等是基本粒子，树枝和树枝之间、叶子和树枝之间有复杂的连接关系。 通过随机递归算法，由一些简单的输入数据生成复杂的自然生态环境。 三维植物网格并行生成及渲染算法研究 求解粒子系统粒子间约束关系的过程即经典的n b o d y 问题，随着粒子数量的逐渐 增加，具有较高的渐进时间复杂度o ( n 2 ) ，难以达到实时效果，而且粒子规律的提取液 比较费时，需要一定的经验和技巧。 1 1 4 交互式植物建模方法 l i n t e r m a n n 提出了对植物三维建模的真实感交互设计方法【1 2 】，该方法实际上是经典 的c s g 造型方法在植物模拟中的一种应用，他们采用一系列包含几何形状信息和植物 结构体系的组件组成，并用可视化的图表表示，植物的空间结构和形状信息由这些组件 通过层次关系进行组织和管理。该方法提供了三种类型的组件：几何体组件，组织组件 和几何变换组件。这是一个很出色的植物三维交互设计系统，缺点是该系统缺乏对植物 的三维可视化编辑，对植物的自由变形处理方法功能并不是很强大，没有提供所见即所 得的变形方法【6 1 。 1 1 。5l 一系统 l 系统是一个著名的植物建模系统，由 p r z e m y s l a w 等学者对l 系统做了大量的研究， 系统能够模拟很多种类的植物。 l i n d e n m a y e r 于1 9 6 8 年提出【1 3 】，随后 对l - 系统功能进行了一定的扩展，使l 文 1 4 中给出了一个用l 系统对草本植物的三维建模方法，可以用来模拟真实的植 物生长，同时该方法也可以用来模拟叶子和花的三维结构。在文 1 5 中提出了基于微分 的l 系统，他在l 系统中加入了微分方程，可用来模拟植物的动态生长过程。在文 1 6 】 中提出了对植物的综合裁剪方法，该方法在植物的生长过程中通过对植物生长空间的约 束获得对植物三维形状的人为控制，是一种模拟植物形状与环境交互的方法。在文 1 】 中提出了一个基于环境交互的丌放l 系统，在l 系统中模拟植物生长的同时加入对环 境因素的模拟，主要模拟了树枝空间竞争所导致的植物生长的变化。在文 1 7 】中提出了 一个基于l 。系统的模拟真实感复杂自然生态环境的建模方法，采用四个步骤来模拟自然 生态环境、环境地形的设计，基于地形的生态系统的模拟，植物的三维建模和真实感处 理，其中植物的模型由l 系统实现。 大连理工大学硕士学位论文 霉，攀攀 霉，爹、琴 图13p r z e m y s l a w 文中的l 一系统植物生成过程 f i g 13 l - s y s t e m p l a n tg e n e r a t i n g e m i n p r a ! r n y s l a w s p a p e r l 系统是一种文法系统，由大量产生式和一个表示植物种子的简单字符串组成，从 种子字符串开始，产生式通过并行回写方法生成表示植物三维模型的字符串，然后由字 符串获得植物的结构，产生式具有毗下形式： 甜：l c p r e d m ：c o n d - s u c c ：p r o b c 1 1 ) 其中i d 表示产生式的索引号，l c 、删和i c 分别是左相关字符串、前驱字符串和 右相关字符串，c o n d 是替换条件，s u c c 是后继字符串，p r o b 表示该产生式发生的概率。 如满足条件就把前驱字符串转化为后继字符串。最后生成的字符串就是有多个产生式共 同作用的结果。然后把字符串中的字符转化为对植物三维结构的表示。 生成的字符串中的字符表示了特点的含义，比如+ 、一、一、分别表示树枝在 三个方向的六种不同的旋转方法，中括号1 里面表示植物从中括号前面的树枝，f 始的一 路子树枝。对生成的字符串从左到右进行解释最后获得植物的三维结构。 l 系统中的产生式可以看作是植物的生长基因，种子字符串相当于植物的种子，因 此用l 景统模拟植物生长具有一定的方便之处，但l 系统的缺点是设计比较困难而 且植物的字符串表示方法比较抽象，难以对植物进行交互的可视化设计【5 】。 本文提出的植物网格模型并行生成算法也是一种基于l 系统的生成方法。 三维植物网格并行生成及渲染算法研究 1 2 研究目的 效率和真实感是当前实时真实感计算机图形学( p h o t o r e a l i s t i er e n d e r i n g ) 的主要议 题，随着电影工业、视频游戏、科学仿真和可视化领域对网格模型精度要求的不断提高， 对大规模、高精度植物网格模型的生成速度及渲染真实感也提出了新的挑战。 1 2 1效率 自l i n d e n m a y e r t ”】于1 9 6 8 年提出对植物进行模拟的l - 系统后，许多学者提出了针 对该算法的改进措施，使l 系统从植物学角度得到了不断的完善。p r z e m y s l a w 等学者 对l 系统进行了有意义的扩充，使之能够模拟很多种类的植物【1 4 】；p r u s i n k i e w i c s 等人提 出了微分l 广系统、开放l 系统等一系列方法以增强l 广系统的真实感【1 5 , 1 6 ：d e u s s e n 等人 提出了基于l 系统的自然环境建模方法，利用l 系统来生成大量树木模型【l 。刀。 由于近年来电影特效、实时游戏等领域对网格模型镶嵌度要求的不断提高，而l 系统植物网格生成的计算量随着树枝层次的提高呈指数级增长【2 】，传统的基于c p u 的 l 系统方法日益无法满足实时仿真应用的需求。 从l 系统的本质来看，它属于一种并行字符串替换机制，在实现上很适合应用通用 图形处理器g p u 的s i m d 并行方式对其进行并行加速以提高原有算法的效率。随着g p u 在图形学领域应用的逐步扩展，已经有一部分文献提出了利用g p u 的高性能图形计算 能力来加速l 系统植物的生成：m e c h 等人于2 0 0 3 年开始尝试使用g p u 来产生l - 系统 植物拓扑结构，但并未提出如何根据拓扑结构生成实际应用所需要的三维网格【2 】。b a e l e 等人于2 0 0 5 年提出采用c p u 产生l - 系统植物拓扑结构，并将结果送往g p u 的顶点处 理单元进行植物三维几何网格的生成。鉴于g p u 对三维向量运算指令集的优化，该算 法加速了网格的产生，不过整个算法过程是串行的，并且从c p u 到g p u 之间的数据传 输构成了算法效率的瓶颈【3 4 】。 随着g p u 硬件性能和功能的不断提高，我们需要针对新硬件的体系结构来设计整 个算法，以充分利用硬件的新特性带来的好处，从而使基于l 系统的植物网格产生效率 提高到适应当前硬件发展水平的新高度。 1 2 2 真实惑 为了达到照片级真实感的植物渲染效果( p h o t o r e a l i s t i cr e n d e r i n g ) 这一目的，仅仅提 供高镶嵌度的植物网格是不够的。我们还需要为已产生的植物网格提供真实感的阴影和 光照。 大连理工大学硕+ 学位论文 利用计算机产生真实感图形效果这一课题经过了三十余年的研究与发展，在有关真 实感图形的出版物中，人们不难看到这样的比较：在一张真实场景的照片旁边，放上了 一张针对同样拍摄角度、由计算机生成的图形，以区分两者间细微的差别。随着计算机 图形硬件和算法的不断发展、改进，到2 0 世纪9 0 年代中期，人们已经能够真实地模拟 各种自然界的客观现象和想象中的特殊艺术效果了。在侏罗纪公园珍珠港飞 屋环游记等好莱坞电影中，真实感图形与电影胶片摄制出的图像得到了完美的结合。 从这个意义上讲，真实感图形达到了它所追求的“像照片一样真实 的效果【l 引。 在真实感渲染领域中，全局光照模型是一种能够提供照片级渲染效果的照明技术， 它能表现物体之间的相互光照影响，达到一种逼真的真实感渲染效果。但是在当前的硬 件条件下，全局光照是一种昂贵的渲染技术，计算量巨大，在高几何精度植物网格模型 这种输入条件下，要达到满意的效果往往需要较长的渲染时间；而采用局部光照模型计 算得到的植物网格虽然计算速度较快，但由于仅仅考虑了光如何从物体的微表面反射的 物理原理，并没有考虑渲染场景中物体之间的相互影响，渲染效果并不是很理想。 为了解决上述矛盾，本文在植物网格的真实感阴影渲染方面进行了一定的研究工 作。 1 3 本文的主要内容 、 本文围绕上述两个研究目的展开了一定的研究工作，一方面从并行三维植物网格生 成的具体实现出发，探讨了当前研究成果的不足，然后介绍了基于g p u 的并行植物网 格生成方法；另一个方面从植物网格的真实感渲染算法考虑，开发了一种基于深度剥离 的屏幕空间环境遮挡算法，在一定程度上提高了植物仿真的真实感。 全文一共分为四章，第1 章介绍了当前植物网格生成方法的研究现状及发展趋势； 第2 章介绍了基于g p u 的高质量图形处理的基本理论；第3 章探讨了原有l 系统植物 网格生成方式的局限，并详细论述了本文提出的基于g p u 的并行植物网格生成方法。 第4 章介绍了基于深度剥离的屏幕空间环境遮挡算法在植物网格渲染上的应用。最后对 本文提出的植物仿真方法进行了总结。 一9 一 三维植物网格并行生成及渲染算法研究 2 基于g p u 的高质量图形处理 高质量图形和实时响应速度在以c p u 作为主要计算负载的计算机实时图形渲染系 统中是相互矛盾的两个面。需要达到高质量图形效果的电影级渲染程序，往往无法在计 算速度上达到实时性的要求；而满足良好实时性的图形程序，通常无法提供令人信服的 真实感渲染效果。g p u 在这种背景下应运而生。由于具有将大量图形计算从c p u 上迁 移，并在硬件上完成部分图形流水线工作：几何变换、裁剪、几何体生成、光栅化、像 素着色的能力。g p u 逐步作为计算机图形计算的另一重要处理核心，被各种各样的图形 处理程序所广泛采用【1 9 1 。 传统的基于c p u 的图形处理程序不适合用于许多高性能图形渲染应用程序的主要 原因是：它采用相对低效的串行编程模型，在这种应用程序中无法适应图形处理这种具 有高度并行性的计算任务【2 0 1 。因此，为了在现有硬件条件下，低成本高性能地实现本文 提出的并行植物网格生成及渲染算法，我们选择n v i d i a 公司的g e f o r o e 系列g p u 作为 算法计算的主要执行单元。 2 1 g p u 流式计算模型 当前的微处理器主要由数以百万计的晶体管相互连接的切换设备构建而成。随着处 理技术的进步，这些晶体管和它们之间的连接，可以集成在一个很小的范围内。1 9 6 5 年，g o r d o nm o o r e 注意到可以经济地制造在单个处理器核心上的晶体管数量每年都翻 倍。m o o r e 指出在将来这样的增长可能持续，而他的论断也被称作著名的m o o r e 定律， 在今天意味着每一年一个核心上大约可以多放置5 0 的组件。自m o o r e 提出他的语言的 4 0 年来，每个核心的晶体管数量从1 9 6 5 年的5 0 发展到2 0 0 9 年的上亿，而且预计增长 率可以持续至少1 0 年。 随着时钟速度和芯片大小的增加，一个以时钟周期测量的信号通过整个芯片的时问 也增加了。在今天最快的处理器上，从芯片的一端发送信号到另一端一般要求的时钟周 期数随着新一代处理器的出现而增加。我们可以用“在通信上的开销与计算的开销之比 的增加”来描绘这一趋势。结论是，未来的设计者将越来越通过廉价的晶体管产生的计 算代替昂贵的通信需要。另一个可能的冲击将是存储器带宽的每个字对应计算量的增 加。例如，比较n v i d i a 的三款旗舰g p u ：2 0 0 2 年的g e f o r c ef x5 8 0 0 、2 0 0 3 年的g e f o r c e f x5 9 5 0 和2 0 0 4 年的g e f o r c e6 8 0 0 ，测量其可编程浮点性能峰值和芯片到存储器的带宽 大连理工大学硕士学位论文 峰值。g e f o r c ef x5 8 0 0 可以为芯片外带宽的每个字进行接近6 次操作，而2 0 0 9 年 n v i d i a 最新的f e r m i 架构g p u 已经超越了1 t f l o p s ，可以实现双精度浮点运算峰值执 行率可达到单精度浮点的1 2 ，即至少6 2 4 g f l o p s 2 1 1 。可以预计这个趋势在未来芯片世 代中会持续存在。图2 1 显示了在一系列g p u 体系结构中，每秒进行的浮点操作的历史 数据【2 0 1 。 图2 1 快速发展的g p u 处理能力 f i g 2 1r a p i dg r o w i n gg p uc o m p u t a t i o n a lc a p a c i t y g p u 所采用的流式编程模型能够利用流式s i m d 处理器的高并行性和通信模式。 它允许高效计算和通信的方式构造程序f 2 3 1 。这个编程模型就是当前g p u 编程的基础。 在流式编程模型中，所有数据都表现为流( d a t as t r e a m ) 。我们把流定义为具有相同 数据类型的数据的有序集。数据类型可以是简单的整数或浮点数流或复杂的点、三角形 和变换矩阵流。流可以是任意长度，如果流中有上百或更多的元素，那么流上的操作效 率将很高。流上允许的操作包括复制它们，从它们导出子流，用一个单独的索引流索引 入它们，以及用核在它们的基础上执行计算。 核程序( k e m e lp r o g r a m ) 操作整个流，获取一个或多个流作为输入，并产生一个或多 个流作为输出。核程序的定义特征是它操作多个流上的所有元素而不是独立的元素。对 核程序的典型用途是对输入流的每个元素做纹理映射操作，即用一个函数进行求值。再 比如，变换核程序可以把一个点组成的流中的每个元素投影到另一个坐标系统中。其他 hao苗)1_-塞mj_*謦u口童 三维植物网格并行生成及渲染算法研究 常见的核程序包括扩展，即对每个输入元素产生一个以上输出元素；缩减，即把一个以 下元素合并为单个输出元素；过滤，即得到输出输入元素的一个子集。 核程序输出的是函数作用于其对应数据流后输出的结果，并且在核程序之内，对流 元素的计算从不依赖于在其他元素上的计算。这些制约有两个主要好处。首先，当写核 程序或编译时。核程序执行所需要的数据完全已知。因此，当它们的输入元素和中间计 算数据储存在局部或是仔细控制的全局引用时，核程序往往非常高效。其次，在一个核 程序之内对不同的流元素求值需要独立计算，这看起来像串行核计算的内容能够得以直 接映射到数据并行的硬件。 在流式编程模型中，通常通过把多个核程序串联在一起来构建应用程序。例如，在 流式编程模型实现图形流水线需要写一个顶点程序核、三角形汇编核、剪切核等，然后 把一个核程序的输出连接到下一个核程序的输入。图2 2 显示了整个图形流水线是怎样 映射到流式模型的。这个模型利用了图形流水线固有的核之间的数据局部性，明确了核 程序之间的通信方式。 片段流 图2 2 映射为流式计算模型的图形流水线 f i g 2 2g r a p h i c sr e n d e r i n gp i p e l i n em a p p e di n t os t r e a mc o m p u t i n gm o d e l 实际上，图形流水线在几方面都很好地匹配了流式模型。图形流水线传统上被构造 为多个计算阶段，由阶段之间的数据流连接。这个结构近似于流式编程模型的流和核程 序的抽象。图形流水线中阶段之间的数据流是高度局部化的，一个阶段产生的数据立刻 被下个阶段所消耗；在流式编程模型中，流在核程序之间的串行也显现出相似的行为。 而且在流水线的各个阶段所调用的计算在不同的图元之间一般是一致的，使这些阶段很 容易映射成核程序。 大连理1 = ：大学硕士学位论文 流式模型用多种方式实现了高效计算。最重要的是，流利用了应用程序的并行性。 由于核程序操作整个流，流元素可以用数据并行硬件并行的处理。包含很多元素的大数 据量流使数据级的并行有了很高的效率。在处理一个元素时，可以利用指令级的并行性。 而且因为应用程序由多个核程序构建而来，多个核可以用任务级并行性进行深度流水线 处理和并行处理。 把重要的应用程序划分为核程序可以把硬件实现成执行一个或多个核程序的特殊 硬件。专用硬件比可编程硬件效率高得多，可以适当用在这个编程模型里。最后，在核 程序执行时只有一个简单的控制流程，比如在各个输入元素上数据并行地用一个函数求 值，允许g p u 的硬件实现把大多数晶体管用作数据流计算硬件，而不是控制硬件，从 而实现计算性能的最优化。 2 2g p u 体系结构的发展 在2 0 0 9 年g p ut e c hc o n f e r e n c e 大会上，n v i d i a 公司发布了新一代的g p u 并行 计算架构f e r m i ，本节描述f e r m i 系列g p u 的体系结构，该系列g p u 每秒钟能够进行 上万亿次的单精度浮点运算，而当前的高端c p u 只能进行每秒近1 2 0 亿次的运算【2 。 f e r m i 对f j 一代g e f o r c e8 8 0 0 系列( 即g 8 0 ) g p u 在架构上进行了显著的改良。该公 司对g p u 进行高性能通用计算的第一次改进起源于2 0 0 6 年11 月推出的g 8 0 系列。g 8 0 系列g p u 不仅支持以往g p u 架构的专属着色器结构、独立的顶点和像素处理管线、手 动管理的向量寄存器，并且支持面向统一架构的通用计算模型c u d a ( c o m p u t eu n i f i e d d e v i c ea r c h i t e c t u r e ) ，g 8 0 系列还是第一个为基于g p u 的通用计算应用提供c 语言支持 的架构。 f e r m i 架构对g 8 0 系列的几点关键改进在于，它的每个流处理器具有3 2 个c u d a 计算核心，是g t 2 0 0 系列和g 8 0 系列的4 倍；一般情况下，f e r m i 架构的g p u 具有1 6 个流处理器，也就是说，每个母板上可以布局5 1 2 个c u d a 计算核心，这种扩展能够 显著地增强g p u 的吞吐量和计算性能【2 2 1 。 图2 3 为f e r m i 架构的基本结构，图的左侧在更低的层次表现了单个c u d a 计算核 心与其载体流处理器的关系，从中我们可以发现，尽管单个c u d a 核心看起来类似于 一个通用计算处理器核心：例如一个多核x 8 6 架构的c p u ，但实际上，由像素着色单元 演变而来的c u d a 计算核心在结构上具有更加简单的特点。 图中每个c u d a 核心都具有一个浮点处理单元( f p u ) 、一个整数处理单元、一些任 务指令调度单元和控制单元，并且设置了一个队列用来保存运算结果。与其他通常用做 通用计算目的的处理器结构不同，c u d a 计算核心不具有l 1 缓存和寄存器，也并未为 二维植物网格并行生成及渲染算法研究 浮点型和整型等常见数据类型提供多功能单元。实际二，他们甚至没有内存读取写入控 制机构。c u d a 核心被设计为仅能够在单个线程上运行非常简单的单一处理指令，并具 有在多条线程间迅速切换能力的形式。该架构并未为单线程性能细致优化，但却为处理 大量等同问题时的多线程计算进行了仔细的优化和布局。具有3 2 个c u d a 计算核心构 成流处理器的f e r m i 架构如图2 3 右侧所示，该图表解释了3 2 个c u d a 计算核心无需 独立的寄存器、缓存和输，v 输出单元的原冈所有这些资源被流处理器共享，这3 2 个核 心被设计为能够同时在3 2 个g p u 线程上运行w a r p 指令的形式。 e = 二二二二二二 霹豳匿二二二二二二 w ar p * 度8 w a r p * 度器 、塑旦塑j j # g # n 1 # l 。，。一 二二= 二二二二卫叠霞 二二二二二 幽23c i j d a 计葬 复心原理幽 f i g2 3p r i n c i p l eo f c u d a 大连理工大学硕士学位论文 阿2 3 上方为f d r m i 架构独有的l 1 指令缓存，除此之外，每个流处理器还具有“k b 可配置的共享缓存，用来为应用程序员自行分配l 1 缓存和通用共享内存空间到所需要 的分区中，其中每个分区可以为1 6 k b 或4 8 k b 。但在一个流处理器上，g 8 0 架构和g t 2 0 0 架构只有1 6 k b 的通用共享缓存可以分配瞄】，并且它们无法操作受硬件控制的l l 缓存 设备。 g p u 流处理器中另一个重要的共享资源是指令调度和分配逻辑组件。f e r m i 架构通 过将原有c u d a 计算核心中单个始终循环只能进行一次指令调度提高到两次，从而提 高了指令的调度效率，但这种改进方式与传统的二次调度式超标量微处理器技术并不完 全一致。在f e r m i 架构中，这种二次指令调度流水线是完全解耦的。另外，在单个线程 中，f e r m i 无法在单个时钟周期内完成两个指令的调度，而是在不同的w a r d 中进行这种 操作，每个流处理器可以同时管理4 8 个w a r p 。因为每个w a r p 具有3 2 个线程，所以这 种方式可以管理1 5 3 6 个线程，因此一个具有1 6 个流处理器的f e r m i 架构g p u 可以同 时管理2 4 5 7 6 个并行线程。 在一个时钟周期内，无法利用现有的c u d a 计算核心执行逐线程的计算。因为每 个计算核心单时钟周期只能执行条指令，所以只有5 1 2 条线程能够在同一时间执行。 但由于在当前执行的线程中切换效率很高，所以其余线程可阻在下一个时钟周期内得以 运行，这种大规模线程并行运算模型j f 是c u d a 的高计算吞吐量的关键。图2 4 为w a r p 调度器从不同的线程l j 分离并调度w a r p 的基本原理。 她嗍烟啤熙! 卿* g 喇嘲! 鳓睡簟 岬1fw 口0 i m 日u ：6 帅“ 二】至堕堕堕 幽24f e r m i 架构中的多线样调度模刑 f i g2 4 m u l t i - t h r e a ds c h e d u l i n g m o d e l i n r m ia r c h i t e c t u r e ，；，diji 三维 a 物网格并行生成及渲染算法院 在单个时钟周期可以执行1 6 个读耿或写入指令的内存读取写入单元是另一个可共 享的流处理器资源。如果使用了如图2 3 所示特有的统一缓存，这种机制将运行得更加 高效：一般来说，矩阵数学运算命令经常在连续相邻的线性地址空间加载许多标量数据， 或在同一个w a r p 中，将一个共用变量在所有线程中共享，在这种情况下，流处理器可 以在一个时钟周期读取两个操作数。 图2 5 是f e r m i 架构的晟顶层封装原理。所有的1 6 个具有3 2 个c u d a 计算核心流 处理器一同共享7 6 8 k b 的统一l 2 缓存。根据当前用做通用计算用途的c p u 标准这 些缓存相对较小，但此前的c u d a 架构原本不具有l 2 缓存，f e r m i 架构通过这种调整 使母板上的所有流处理器都能够共享l 2 缓存。 1 1 篓蒸；r 蟹翟 一兰：l 遂卜一 一 幽25f e r m i 架构顶层视幽 f i g2 5l o pv i e wo f f e r m ia r c h i t e c t u r e f e r m i 架构g p u 的内存层次结构与一般的c p u 具有品著不同。首先，g p u