（计算机软件与理论专业论文）基于流的粒子系统的设计与实现.pdf

基于流的粒子系统的设计与实现 计算机软件与理论专业 研究生：罗军指导教师：王玲教授 摘要：粒子系统是三维图形引擎的重要组成部分。是模拟动态、模糊、 不规则物体的有效算法。在虚拟现实、数字娱乐、三维仿真、影视特效等领 域有着广泛应用。 随着图形处理器( g r a p h i c sp r o c e s s i n gu n i t ) 的快速发展，可编程能力不 断增强，g p u 已逐渐发展成为一个通用的计算平台。近几年，基于g p u 的 通用计算已成为计算机领域新的研究热点。 粒子系统通常是在c p u 上进行粒子的物理运算，然后将运算结果传输给 g p u 绘制。当粒子数目巨大时( 如1 0 0 ，0 0 0 个) ，运算时间和c p u 。g p u 的数据传输时间对实时渲染来说都难以接受。同时，在c p u 上还要进行碰 撞检测、骨骼动画、场景简化等计算，因此c p u 成为了系统瓶颈。如何将 c p u 的运算转移到g p u 上并减少c p u g p u 的数据传输，是提高绘制效率 的关键。 在分析粒子系统的并行算法和g p u 编程技术基础上，把粒子系统和基于 g p u 的通用计算结合起来，在g p u 上实现了粒子系统。它把基于g p u 的硬 件编程和基于d i r e c t x 的图形编程封装起来，为程序丌发人员了提供一个简 易清晰的程序框架，极大地提高了应用程序开发效率。为方便g p u 粒子系 统在不同开发环境中使用，我们利用c o m 技术把这些核心程序包装成一个 插件粒子系统引擎。 在引擎基础上，结合w i n d o w s 界面技术，我们开发了个可视化的粒子 系统编辑环境粒子系统编辑器。利用该编辑器，只需做简单调试就可以 制作出各种各样的粒子效果。把这些效果保存下来可在其它三维程序中用粒 子系统引擎加载。粒子系统与其它对象融合在一起，可构成更复杂的三维场 景。 在此基础上，我们提出了以粒子系统引擎为核心，以粒子系统编辑器为 工具，其它三维程序为具体应用环境的完整解决方案。其中粒子系统引擎用 并行算法在g p u 上实现，实时性好；粒子编辑器界面友好，使用方便；引 擎与其它三维程序兼容性好；实验证明整个方案切实可行。 关键字：流；粒子系统；图形处理器；引擎；编辑器 i i d e s i g n i n ga n di m p l e m e n t i n go fp a r t i c l es y s t e mb a s e do ns t r e a m m a j o r ：c o m p u t e rs o f t w a r ea n dt h e o r y g r a d u a t es t u d e n t ：l u oj u n s u p e r v i s o r ：w a n gl i n g a b s t r a c t ：p a r t i c l es y s t e mi sa ni m p o r t a n tc o m p o n e n to f3 dg r a p h i c s e n g i n e ri sa ne f f e c t i v ea l g o r i t h mf o rm o d e l i n gm o v a b l eo rf u z z yo b j e c t i th a s b e e nw i d e l yu s e di nf i e l d ss u c ha sv r ，d i g i t a lm o v e m e n t ，3 de m u l a t o ra n df i l m e f r e c t a st h er a p i dd e v e l o p m e n to ft h eg r a p h i c sp r o c e s s o ru n i t ( g p u ) a n dt h e c e a s e l e s s i n c r e a s i n gp r o g r a m m a b l ea b i l i t y , g p u h a sb e c o m eb o t h h i g h p e r f o r m a n c ec o m p u t a t i o n a lp l a t f o r ma n dn e wr e s e a r c hh o t s p o t f o rc u r r e n t p a r t i c l es y s t e m ，p a r t i c l e sp h y s i c a lc o m p u t a t i o nw o r k s a r e u s u a l l yb a s e do nc p ua n dt h er e s u l t sa r er e n d e r e do ng p u i ng e n e r a l w h e nt h e p a r t i c l en u m b e ri st o ol a r g e ，s u c ha s1 0 0 ，0 0 0 ，t h et i m es p e n to nc a l c u l a t i n ga n d t r a n s f e r r i n gb e t w e e nc p u a n dg p ui sa n a c c e p t a b l ef o rr e a l - t i m er e n d e r a tt h e s a m et i m e ，m a n yc a l c u l a t i o n s ，s u c ha sc o l l i s i o nd e t e c t i o n ，l o de t c ，h a v et ob e d o n eo nc p u s o ，c p ub e c o m e st h eb o t t l e n e c k h o wt ot r a n s f o r ms o m e c a l c u l a t i o n sw o r k sf o r mc p ut og p ua n dd e c r e a s et h ed a t at r a n s f e rb e t w e e n c p ua n dg p ua r et h ek e yo fe n h a n c et h er e n d e re f f i c i e n t b a s e do nt h e s t u d y i n gt h ep a r t i c l es y s t e m sp a r a l l e la l g o r i t h ma n dt h e p r o g r a m m i n gt e c h n o l o g yb a s e do ng p u ，ap a r t i c l es y s t e mh a sb e e ni m p l e m e n t e d w i t hu n i o no fg e n e r a lc o m p u t a t i o no ng p u b o t ht h ep r o g r a mt e c h n o l o g yo nt h e h a r d w a r ea n dt h eg r a p h i cp r o g r a mt e c h n o l o g yb a s e do nd i r e c t xh a v eb e e n e n c a p s u l a t e di nt h ep a r t i c l es y s t e ma n dt a ne a s yp r o g r a mf r a m e w o r kh a sb e e n p r o v i d e d f o rt h i sr e a s o n ，c o mt e c h n o l o g yh a sb e e nu s e df o rg p up a r t i c l e s y s t e m t h ee f f i c i e n c yo fs o f t w a r ed e v e l o p m e n th a sb e e ni n c r e a s e dg r e a t l y i ti s t h ec o r ec o d eo f p a r t i c l es y s t e mb a s e do ns t r e a m p a r t i c l es y s t e me d i t o ri sav i s u a le n v i r o n m e n tt oc r e a t ep a r t i c l es y s t e n ae f f e c t i l l w ec a l ld r a wa l lk i n d so fp a r t i c l es y s t e me f f e c ti ni t w i t hg r a p h i c su s e ri n t e r f a c e ， t h ep a r t i c l es y s t e me d i t o ri si m p l e m e n t e do nt h eb a s eo f t h ee n g i r l e s o ，aw h o l er e s o l u t i o nh a sb e e np r o v i d e da sf o l l o w s ：t h ep a r t i c l es y s t e m e n g i n e i st h ec o r ep a r t t h ep a r t i c l es y s t e me d i t o ri st h et o o la n do t h e r3 d p r o g r a m sa r et h ea p p l i c a t i o ne n v i r o n m e n t t h ee n g i n eh a sb e e ni m p l e m e n t e do n g p uw i t hp a r a l l e la l g o r i t h mw i t hg o o dr e a l t i m ep e r f o r m a n c e t h ee d i t o ri sa g o o dm e n di n t e r f a c ew i t hc o n v e n i e n to p e r a t i o nm o d e t ot h ee n g i n e ，t h e r ea r e g o o dc o m p a t i b l ef e a t u r e s k e y w o r d ：s t r e a m ；p a r t i c l es y s t e m ；g p u ；e n g i n e ；e d i t o r 基于流的粒子系统的设计与实玑 四川师范大学学位论文独创性及使用授权声明 本人声明：所呈交学位论文，是本人在导师指导下，独立进行 研究工作所取得的成果。除文中已经注明引用的内容外，本论文不含任何其 他个人或集体已经发表或撰写过的作品或成果。对本文的研究做出重要贡献 的个人和集体，均已在文中以明确方式标明。 本人承诺：己提交的学位论文电子版与论文纸本的内容一致。如因不符 而引起的学术声誉上的损失由本人自负。 本人同意所撰写学位论文的使用授权遵照学校的管理规定： 学校作为申请学位的条件之一，学位论文著作权拥有者须授权所在大学 拥有学位论文的部分使用权，即：1 ) 已获学位的研究生必须按学校规定提 交印刷版和电子版学位论文，可以将学位论文的全部或部分内容编入有关数 据库进行检索；2 ) 为教学和科研目的，学校可以将公开的学位论文或解密 后的学位论文作为资料在图书馆、资料室等场所或在校园网上供校内师生阅 读、浏览。 论文作者懿号霉 帅一7 年午月厶。同 四川师范大学硕士学位论文 第一章引言 1 1 课题背景知识介绍 在自然界中有一些现象，比如雨、雪、霜、烟、火等，没有固定的形状、 也没有平滑的表面。它们的形状不停的变化，表面没有规律，很难用多边形网 格来描述它。对这些不规则的、模糊的、运动的物体，粒子系统i l 】是一个有效 的造型方法。 粒子系统是计算机图形学的重要组成部分，是不规则物体造型的有效算法。 它由成千上万的微粒组成，在系统运行过程中，每个粒子执行相似的运算，粒 子之间关联度小。上述特点决定了粒子系统特别适合用并行算法实现。 随着图形处理器( g r a p h i c s p r o c e s s i n g u n i t ) 的快速发展，g p u 具有了强大 的并行计算能力且提供了编程接口【2 】，它使得在g p u 上实现并行算法成为可 能。 把粒子系统用并行算法在g p u 上实现，既可以平衡c p u 和g p u 的负载， 又可以避免c p u - g p u 之间大量的数据传输，由此可以提高粒子系统的绘制效 率，这正是本文要研究的内容之一。 1 1 1 粒子系统介绍 粒子系统起源于1 9 8 3 年。在短短的2 4 年时间里，它的发展非常迅速。从 最初的简单模拟到引入物理模型，加入碰撞检测1 3 】；从c p u 上的串行计算到超 级计算机的并行计算【4 1 。最近几年，人们又开始研究在个人计算机上的g p u 上 实现并行计算【5 1 。粒子系统规模也由最初的几千个发展到现在的百万个【6 】。其 应用领域不断拓展，如虚拟现实、游戏开发，三维仿真、影视特效、科学计算 可视化等领域都用到了粒子系统技术。 1 1 1 1 粒子系统原理 粒子系统用大量细小微粒来表现一个复杂的不规则物体或者景象。每个粒 子都有一定生命周期，系统会不断的产生新粒子，这些粒子不停地运动和变化， 直到生命周期结束时被系统删除。 四川师范大学硕士学位论文 粒子系统的绘制包括以下几个步骤： 1 ) 粒子的产生：产生新粒子并加入系统中； 2 ) 粒子的初始化：设置每个粒子的属性，如初始位髯、方向、颜色、透明 度、生命周期等； 3 ) 粒子的运动：根据粒子属性的动态变化对粒子进行移动和变换； 4 ) 粒子的消亡：从系统中删除那些生命周期已经结束的粒子； 5 ) 粒子的绘制：绘制并显示由有生命的粒子组成的图形。 上述几个步骤不停地循环以形成物体的动态变化过程。 1 1 1 2 粒子系统的特点 同其它描述不规则物体的图形方法相比，粒子系统具有以下几个显著的特 点： 1 ) 对物体的描述不是通过具有边界的面片( 如多边形) 集合来描述，而是 通过一组定义在空间中的原始粒子来描述。一个复杂物体或现象需要成千上万， 甚至几十万个粒子来描述。 2 1 粒子系统不是一个静态实体。每个粒子都在不停地运动和改变，因此整 个粒子系统是动态的，需要不停地计算和重新绘制。 3 ) 粒子系统的每个粒子都是一个独立个体，并按自身的规律进行运动和改 变，粒子之间的运动关联度较小。 经典的粒子系统在c p u 上计算，再把数据传输到g p u 上绘制。粒子系统 的动态性和大规模特点决定了其计算和数据传输量均大，并且数据传输频率高。 它们会影响绘制的实时性，表明不是特别适合在c p u 上以串行算法实现。 粒子规模大、关联度小的特点可以对所有粒子执行同一操作，进行批量处 理，这正是流计算模式的长处。 1 1 2 基于流的计算模式 1 1 2 1 基于流的计算模式简介 基于流的计算模式5 1 以一个数据序列作为输入数据，采用同一段内核程序 并行处理所有输入数据，最后将计算结果置于输出流输出。处理器对批量输入 2 四川师范大学硕士学位论文 数据按同一指令并行处理后。再批量输出。 g p u 是一个流处理器，它具有单指令多数据流的特性( s i n g l ei n s t r u c t i o n m u l t i p l ed a t as t r e a m ) t u ，在g p u 上用并行算法实现的计算是一种基于流的计算。 它充分利用g p u 并行计算的优势，有效使用高带宽，隐藏了内存重用的潜在 危险。 豳i - i 基于流的计算模式示意图 基于流的粒子系统就是在g p u 上用并行算法实现的粒子系统。它能够平衡 c p u - g p u 之间的计算负载，避免c p u g p u 之间的大规模数据传输，从而提高 整个系统的绘制效率。 1 i 2 2 图形处理器的发展 从2 0 世纪8 0 年代初期开始，以g e ( g e o m e t r y 锄s i n e ) 为标志的图形处理器 开始出现【8 l o 它用1 2 个g e 单元完整地实现三维图形输出流水线的功能。从1 9 9 8 年以来，g p u 功能迅速更新，平均每一年多便有新一代的g p u 诞生。 g p u 的两大品牌是n v d a l g j 和a t 1 0 1 ，g p u 的发展史，也是这两个显卡芯 片发展史。 第一代g p u 出现在1 9 9 8 年后期，主要代表为n v i d i at n t 2 ，a t ir a g e 9 。 它们主要处理光栅化部分。有些芯片支持多纹理，可以在光栅化过程中完成多 幅纹理的融合操作。 从1 9 9 9 年后期开始，第二代g p u 以n v i d i ag c f o r c e 2 5 6 ，g e f o r c e2 和a t i r a d e o n7 5 0 0 为代表 i u 。它们可以处理顶点的矩阵变换和光照计算。 第三代g p u 以n v i d i ag e f o r c e 3 ，g e f o r c e 4 ，a t ir a d e o n8 5 0 0 为代表，是 g p u 发展过程中的一次历史性突破。它第一次提供了编程接口，可以对顶点和 四川师范大学硕士学位论文 像素编程。顶点编程和像素编程分别支持v s l 0 和p s l 0 t 团。g p u 开始被用作 通用计算。 第四代g p u 以n v i d i ag e f o r e ef x 系列和a ：nr a d o o n9 7 0 0 9 8 0 0 为代表。 像素和顶点可编程性更通用化，并支持顶点编程v s 2 0 和像素编程p s 2 0 。此 时，基于g p u 的通用计算研究开始活跃。2 0 0 3 年，世界上唯一的图形学硬件 年会( s i g g r a p h e u r o g r a p h i c sg r a p h i c sh a r d w a r e2 0 0 3 ) 迅速将其重点转向 了计算机图形处理器的非图形应用。甚至有专家认为，g p u 将进入计算的主流 1 1 3 。 第五代g p u 以n v i d i ag e f o r c e6 8 0 0 为代表。其功能相对以前更为丰富、 灵活。顶点程序可以访问纹理，支持动态分支操作；像素程序开始支持分支操 作包括循环、i f e l s e 、重复等，支持子函数调用，“位浮点纹理滤波和融合， 多个绘制目标等；全面支持顶点编程v s 3 0 和像素编程p s 3 0 。特别是顶点纹 理技术( v e r t e xt e x t u r e s ) 砼i ，它使顶点处理器( v e r t e xp r o c e s s o r ) 能方便的访问纹理 数据。该技术使g p u 中的两个可编程管线能更好的协作，大大的提升了可编程 能力。 最新的g p u 性能进一步得到提升。如n v i d i ag e f o r e e 7 8 0 0 和a = r i r a d e o n x l 8 0 0 。其像素渲染管线最高达2 4 条，显存带宽最高达到4 8 g ，其性能 远远高于最新的p 4 3 0 双核处理器。 1 1 2 3 基于图形处理器的通用计算 1 ) g p u 的可编程硬件架构 g p u 的编程架构如图1 2 所示【1 2 】： 图1 2 g p u 的可编程架构 4 网川师范大学碗十学位论文 两个椭圆形表示的处理器就是可供编程的顶点处理器( v c r t a xp r o c e s $ o t ) 和 像素处理器( f r a g r a n tp r o c e s s o r ) 。在顶点处理器( v m c xp r o c e s r ) 上编写函数处 理顶点数据，在像素处理器( f r a g m e n tp r o c e s s o r ) 上编写函数处理纹理数据。这 两个处理器协同工作以在g p u 上实现通用计算。本文的并行算法主要在 f r a g m e n tp r o c e s s o r 上实现。 21 基于图形处理器的编程语言 图形处理器只能执行汇编级代码，因此对图形处理器进行编程不是一件容 易的事。图形界努力追求的目标是使用象c 件那样的高级语言对g p u 进行编 程。现在这个目标已经很接近了。比如fm i c r o s o f t 的h l s l ( 琢班l e v e ls h a d i n g l a n g u a g e ) 1 4 】类似于a 斗。其程序用h l s l c o m p i l e r 编译后，就可以直接链接。 大大降低了用户对g p u 的编程难度。除了h l s l 之外，还有o p e n g ls h a d i n g l a n g u a g e t m 6 】和n v i d a 公司提供的类似于c 语言的专门用于g p u 编程的图形处 理语言c g l l 7 1 。 3 ) 基于g p u 的通用计算应用 随着图形处理器可编程能力的提高，越来越多的人开始把g p u 用作通用计 算。g o v i n d a r a j u 等人利用g p u 来进行快速碰撞检测1 1 8 】。s u d 等人采用g p u 来 加速三维距离场的计算【。t o m o v 等人则用g p u 来进行蒙特卡洛仿真【2 0 】。 t h o m p s o n 等人使用顶点处理器编程实现了一个代数运算的框架系统【2 “，包括 矢量运算和矩阵乘法等。k r u g e r 等人利用像素程序做基本代数运算1 2 2 ，h a l l 等 人对于矩阵乘法运算利用像素程序做了若干优化，以充分利用g p u 的高速缓 存1 2 。美国北卡罗莱那大学用g p u 对数据库记录进行查询，取得了较好的效 果1 2 卅。m o r e l a n d 等人利用常规算法在g p u 上实现了快速傅立叶变换( f f t ) p j ，在g e f o r c e 5 8 0 0 u l t r a 上实现的快速傅立叶变换对5 1 2 5 1 2 的图像可以在 1 秒之内实施正向或反向的傅立叶变换。香港中文大学王剑清等人在g p u 上 实现了完整的小波变换 2 6 2 7 】，包括小波多尺度分解变换和重建逆变换，当图像 较大时，基于g p u 的计算在效率上比在c p u 上的计算要高很多。 5 四川师范大学硕士学位论文 1 2 粒子系统国内外研究现状 1 2 1 国外研究现状 1 9 8 3 年，w i l l i a mt r e e v e s 最早提出了粒子系统。它能充分体现模糊物体 的动态性和随机性，能很好地模拟动态的三维复杂景物【lj 。 a n d r 斟vw i t l d n 提出了基于物理模型的粒子系统，在经典粒子系统基础上加 上重力等物理因素，对自然现象的模拟更逼真p j 。 2 0 0 4 年以前的这些算法均在c p u 上计算，再把数据传送到g p u 上完成绘 制，受到c p u 和g p u 之间传输带宽的影响，要在普通的p c 机上实现粒子系 统的实时绘制，最多只能处理1 0 ，0 0 0 个粒子1 6 】，大大限制了粒子系统的应用 范围。 k a r ls i m s 为了提高粒子系统的处理规模和速度，提出了一种并行算法，在 一个能执行并行计算的超级计算机上实现了该算法【4 】。 2 0 0 4 年，l u t zl a t t a 提出了一种基于流的算法在可编程的g p u 上实现了 粒子系统，该方法可同时渲染1 , 0 0 0 ，0 0 0 个粒子，达到较好效果【6 1 。这在粒子系 统发展上是一个里程碑。它首次在g p u 上实现了粒子系统，避免了c p u 和g p u 之间的大量数据传输，提高了粒子系统绘制的实时性。第二年。l u t zl a t t a 等在 前面研究的基础上，用体绘制算法【2 s 】实现了粒子系统和场景中实体的碰撞检 测。该系统碰撞检测比较简单，不能进行复杂多边形与粒子系统的碰撞。同时， 在碰撞检测之前需要把三维模型用体绘制方法二维化，增加了碰撞检测需要的 时间。 k i p f e r p e t e r 等人用o p c n g l 实现了一个完全基于g p u 的通用粒子系统引擎 【2 9 1 ，它弓i 入了物理模型，实现了粒子之间的碰撞检测，并应用于火山模拟。但 它没有做粒子系统与场景中其它对象之间的碰撞检测，在构建大场景时与其它 对象的融合不是很理想。 1 2 2 国内研究现状 国内在粒子系统的研究上起步较晚，2 0 0 2 年贵州工业大学的姚颜林等基于 o p e n g l 的开发接口开发了面向对象的粒子系统1 3 0 l 。中科院南京地理与湖泊研 究所开发了一套粒子系统应用程序接口并应用予苏州工业园虚拟展示系统3 ”。 6 四川师范大学硕士学位论文 2 0 0 6 年，粒子系统的研究非常活跃。西安科技大学的宇亚卫用粒子系统模 拟三维火焰，在粒子系统中引入了运动场，讨论了重力和风力对火焰的影响i j “。 刘镪等用粒子系统模拟头发，生成了较为逼真的效果【3 3 】。北京航天航空大学的 许楠等1 3 4 1 实现了一种基于g p u 的粒子系统。在国内的粒子系统研究上是一次 飞跃，与传统的基于c p u 的算法相比，在绘制大规模粒子系统时，绘制速率明 显提高。他实现的是一个基本的粒子系统，没有进行碰撞检测，也没有考虑物 理模型，因此其应用有一定的局限性。 1 3 课题研究的意义 1 3 1 粒子系统应用价值 雨、雪、烟、火焰等不规则的、模糊的、运动的物体或景象很难用一般的 方法来建模。由于它们不停的运动和改变形状，表面不规则并且边界模糊，很 难通过定义其表面网格来描述它。粒子系统为这类物体或景象的建模提供了有 效的解决办法，它能很好的模拟物体的动态特性。 经过二十多年的发展，粒子系统已经成为计算机图形学的重要组成部分， 是模拟不规则动态物体或景象的有效算法，粒子系统广泛应用于虚拟现实【3 5 1 、 三维仿真【3 6 1 、游戏开发、电影特效【1 ) 、可视化阳等领域。用于模拟火3 8 1 、烟、 焰【3 9 】的动态效果，光、影、闪电特效，雨雪降落过程1 4 0 , 4 1 1 ，液体或气体的流动 过程【4 2 】等。 粒子系统是构建三维场景不可缺少的建模工具，在每一个具体的三维软件 项目中，都不能没有粒子系统。 1 3 2g p u 粒子系统研究意义 把在三维程序中，碰撞检测、场景管理、地形化简等大部分计算通常在c p u 上进行，而g p u 仅仅用作绘图。随着g p u 性能不断增强，c p u g p u 之间负 载不平衡表现突出如果能把c p u 的部分计算交给g p u 完成，将能有效的平 衡负载，从而提高整个系统的处理效率。 定义1 - 1 ：c p u 粒子系统，指粒子的属性存储在系统内存中，在c p u 上更 新粒子属性的粒子系统。 7 四川师范大学硕士学位论文 定义1 2 ：g p u 粒子系统，指粒子的属性存储在显存中，在g p u 上更新粒 子属性的粒子系统。 图l - 3 在c p u 和g p u 实现的粒子系统的处理流程比较 如图1 3 所示，c p u 粒子系统计算完成后需要把数据传输到显存，再由 g p u 完成绘制。由于粒子数量成千上万，传输的数据量很大，而c p u g p u 之 间数据传输带宽受限。庞大的数据传输会影响实时绘制。 而g p u 上实现的粒子系统，其数据存储在显存中，避免了从系统内存到显 存的数据传输。可节省数据传输的时间。并且g p u 具有强大的并行计算能力， 在g p u 上进行的计算效率也较高。因此g p u 粒子系统具有更好的实时性。 1 3 3 粒子系统解决方案研究意义 目前国内外研究主要集中在粒子系统的算法和具体应用上，即核心层和应 用层，缺乏中间的工具层，因此大家的研究彼此独立，不能通用。 国外大公司的商业软件中提供了粒子系统的可视化编辑模块和浏览模块， 即提供了工具层和应用层，但其实现算法保密，想在上面做些扩展工作很难。 8 四川师范大学硕士学位论文 在上面调试的粒子系统很难与自己开发的三维程序兼容。 在分析调研基础上，本文提出了如图l - 4 所示的三层解决方案。它以粒子 系统引擎为核心，以粒子系统编程器为工具，以其它三维软件为具体应用环境。 l三维软件( 如场景编辑器、演示程序、三维浏览器等) 1 挺供数据 。 粒子系统编辑器( 可视化的编辑环境)提供支持 1 捷供支持 l 粒子系统引擎( 核心算法的软件实现) 图1 - 4 粒子系统的三层解决方案示意图 应用层 工具层 核心层 这样，用粒子系统引擎和编辑器就能开展应用研究，直接在编辑器上调试 可视化效果，而不必从研究算法开始。这样做可以提高工作效率，减少重复劳 动。 核心层的算法和接口公开，如果可视化工具满足不了需要，可以扩展这个 通用算法和引擎。与从头开始算法的研究相比，它能大大降低研究和实现算法 的难度。 1 4 本文的研究工作与内容安排 1 a 1 本文的研究工作 如前节所述，本文提出了三层的粒子系统解决方案( 如图1 - 4 ) 。在方案中， 粒子系统引擎最重要。在设计引擎时，我们吸取了最新粒子系统研究成果，给 出了适合在g p u 上实现的完整粒子系统算法。提出了在g p u 上实现基于粒子 运动轨迹的碰撞检测算法，给出了适合在g p u 上运行的并行排序算法。 基于粒子系统算法，整合d i r e c t 3 d 、c o m 、x m l 等编程技术，实现了基 于流的粒子系统引擎。封装了d f f e c t 3 d 的底层调用，简化了编程接口；用c o m 技术把核心代码包装成一个跨平台软件组件；设计了开放数据接口，用x m l 文件格式来保存粒子系统数据，在引擎中实现了对x m l 文件的保存、读取支 9 四川师范大学硕士学位论文 持。 在粒子系统引擎基础上，结合w i n d o w s 界面编程技术，实现了粒予系统编 辑器。探索了在m f c 框架下使用d i r e c t 3 d 进行高效图形编程的方法。通过消 息映射实现了与粒子系统的交互；在b c gc o n 廿0 1 b a r f 4 3 1 支持下实现了浮动属性 面板。制作了友好的图形界面，实现了“所见即所得”的效果。 在应用层用虚拟校园项目来验证了本方案的可行性。用粒子编辑器制作了 喷泉效果。在粒子系统引擎支持下，喷泉与水池、教学楼、花草、树木等一起 组成了校园的一角。另外用粒子系统编辑器制作了一些有代表性的可视化粒子 效果，适用于不同应用环境，验证本方案的通用性。 1 4 2 本文的内容安排 第一章阐述了粒子系统和图形处理器的背景知识，介绍了国内外在粒子系 统领域的研究现状，说明了本课题研究的意义和具体内容。 第二章完整地描述了基于流的粒子系统算法，重点介绍了本文提出的基于 轨迹检测的碰撞检测算法。还简单介绍了用于粒子可见性测试和a l p h a 融合的 奇偶归并排序算法。 第三章介绍了面向对象的粒子系统引擎设计思路；详细介绍了用d i r e , c o d 实现粒子系统的计算和绘制技术，专门介绍了用h l s l 语言来更新粒子系统属 性的编程方法和绘制粒子系统的点绘制技术( p o i n ts p r i t e ) ，简单介绍了组件开发 中用到的c o m 技术，还定义保存粒子系统数据的x m l 文件结构。 第四章是粒子编辑器开发经验总结，先介绍了粒子编辑器的设计架构，再 介绍了主绘图窗口和浮动属性面板的制作过程，还介绍了人机交互技术的实现 技巧。它们是制作友好图形界面的关键。 第五章展示了用粒子编辑器完成的一些粒子效果及其制作要点和应用环 境。验证了算法的通用性和解决方案的可行性。 第六章是本文的结论部分。 i o 四川师范大学硕士学位论文 第二章基于流的粒子系统的算法设计 本文设计的粒子系统是在g p u 上实现，与在c p u 上实现的粒子系统相比， 它避免了从c p u 到g p u 的庞大的数据传输，g p u 上的并行计算提高了计算的 效率，可以把粒子的处理规模提高到1 , 0 0 0 ，0 0 0 t 6 1 。但c p u 上的算法不能简单移 植到g p u 上。因为g p u 的存储结构、编程接口、数据处理方式都和c p u 完全 不同研。在o p u 上数据必须以纹理( t e x t u r e ) 的形式存储，数据并行计算，粒子 系统在g p u 上的数据处理流程如图2 - 1 所示。 产生 新粒子 绘制 粒子 设置粒l 运动l 碰撞 子属性r + l 检测 粒子的可见性测 试、a l p h a 融合等 圈2 - l 粒子系统的处理流程 更新粒 子属性 删除生命周期 结束的粒子 对整个数据处理流程，本文给出了从新粒子的产生到粒子的绘制的完整算 法描述。重点介绍了碰撞检测算法和用于粒子的可见性测试的并行排序算法。 本文提出了基于粒子运动轨迹的碰撞检测算法。用于检测粒子系统与场景 中其它对象之间是否发生碰撞，并根据检测结果进行相应处理。它使场景看起 来更加真实。轨迹检测算法能对粒子系统与多边形物体进行精确的碰撞检测， 有较高的执行效率。 在粒子可见性测试及a l p h a 融合中需要用到排序算法，虽然排序是经典算 法，但适合并行计算且效率较高的算法不多。本文介绍了适合在g p u 上运行的 并行排序算法。 粒子系统的基本算法，如粒子的存储、产生、删除、属性更新等，在许多 文献中已有详细描述，本文只作简单介绍。 四川师范大学欲士学位论义 2 1 基于流的粒子系统属性存储 利用g p u 进行通用计算的运算器是像素处理器( f r a g m e n tp r o c e s s o r ) 。它存 取显存时的基本单位是纹理( t e x t u r e ) 。所以粒子属性必须存储在t e x l u r e 上。 f r a g m e n t p r o c e s s o r 用于输入的t e x t u r e 是只读的，用于输出的t e x t u r e 是只写的。 为便于计算，输入和输出各需要一个t e x t u r e 。即双缓存。粒子需要存储的属性 有位置、速度、颜色、尺寸、碰撞属性、生命周期、生存时间。 l 图2 2 粒子属性以纹理的形式存储 t e x t u r e 中每个元素( t e x e l ) f l jr g b a 四个分量组成，每个分量都可以是浮点 数。为了节省存储空间( 如图2 2 所示) 对粒子属性进行组合后存储：位置属 性是三维坐标，占三个存储分量。尺寸属性是一个浮点数，占一个存储分量。 因此把位置和尺寸它们组合在一起存储。速度是三维向量，碰撞属性是浮点数， 两者组合在一起刚好一个t e x e l 的存储空间。颜色本来就是r g b a 四分量，独 成一组。生命周期是粒子将在系统中存活的总时间，生存时间是指粒子自产生 以后在系统中存在的时间，一般把它们组合在一起存储。 2 2 基于粒子运动轨迹的碰撞检测算法 碰撞检测是图形学中研究的一个熟点领域，k o l b ，a 用体绘制算法实现了粒 子系统与实体的碰撞检测捌。其缺点是需要把三维实体转换为二维，增加了计 算量。范昭炜在g p u 上实现了两个三角形表示的物体间的碰撞检测，它的碰撞 检测效率较高，但不适合粒子系统与物体的碰撞检测：k i p f e rp e t e r 在g p u 雾 一一一吲一博一 室 四川师范大学硕士学位论文 上实现了粒子系统的内部碰撞检测【2 9 】，但没有考虑粒子系统和场景中其它物体 的碰撞检测。g o t t s e h a l k 等提出了o b b 包围盒算法【4 5 l ，它可以大大减少不必要 的碰撞检测。 本文在研究各种碰撞检测算法的基础上，结合粒子系统的特点，提出了让 粒子的运动轨迹与表示物体的三角形面片进行相交测试的轨迹检测算法。该算 法一次计算可以完成所有粒子与一个三角形的碰撞检测，要完成粒子系统和场 景中一个物体的碰撞检测，需要一个循环来完成。轨迹碰撞检测算法先把三角 形数据以顶点的形式输入，借助绘图过程把顶点信息保存到一个t e x t u r e 形式 的显存上，然后在像素处理器( f r a g m e n tp r o c e s s o r ) 上进行相交检测计算，再 把结果输出到另一个t e x t u r e 形式的显存中，最后根据检测结果更新粒子的速 度和方向。 2 2 1 数据的输入 2 2 1 1 粒子的运动轨迹的表示 粒子的运动轨迹即粒子由当前位置移动到下一个位置的运动过程形成的轨 迹。由于两个位置之间特别短，可以近似地认为它们就是条线段，该线段的 一个端点就是粒子的当前位置p o s i t i o n ，其长度为l e n g t h = v e l o c i t y x t i m e 即速度和时间的乘积。因此粒子的运动轨迹由p o s i t i o n , v e l o c i t y , 2 1 m e 三个分量 来描述，p o s i t i o n 和v e l o c i t y 已经以t e x t u r e 的形式存储，可以直接作为f r a g m e n t p r o c e s s o r 的输入数据。而t i m e 是整个粒子系统共用的一个变量，可以通过系 统时钟来获取。 2 2 2 2 物体的三角形表示 计算机图形学中，规则物体通常由三角形组成的网格来描述。一个三角形 有三个顶点和一个法线向量。先创建与存储p o s i t i o n 的t e x t u r e 长宽相等的矩形， 把三角形顶点和法线向量四个参数作为纹理坐标赋给矩形的每一个顶点。 2 2 2 3 运动轨迹和三角形数据的输入 运动轨迹保存在t e x t u r e 中，三角形数据以纹理坐标形式保存在矩形的顶点 四川师范大学硕士学位论文 中，通过绘制矩形过程把两者联系在一起。绘制矩形的光栅化过程会把纹理坐 标映射到视窗口的每个像素上，通过纹理映射就可以访问运动轨迹数据。因此， 其输入是借助绘制过程实现。需要补充说明的是这里的绘制不需要绘制到屏幕 上，而是绘制到显存中，在显存中创建一个t e x t u r e 对象，通过r e n d e rt ot e x t u r e 技术把矩形绘制到显存中，以区别真正的绘图过程。 2 2 2 射线与三角形的求交算法 m 6 1 1 e r 等人提出了一个非常有效的射线与三角形求交算法嗍，本文把它改 造后用于g p u 上的并行计算。求交算法如下： 一条射线尺彬，由原点0 和方向d 来表示。即 r ( t ) = 0 + f d ( 2 1 ) 三角形由三个顶点所和比来描述。三角形中任意点t ( 1 l ，v ) 应该满足下面 的公式： t ( u ，v ) = ( 1 - - u - v ) v o + u v i + v v 2 ( 二2 ) 其中， _ 0 ，v 批0 ，材+ v 审l 如果射线和三角形相交，那么必定有一个点，它既在射线上，又在三角形 中，因此有： o + t d = ( 1 一却- v ) v o + u v i + v y 2 ( 2 - 3 ) 上式变换成向量运算，即： h 【- d ，矿i y o ，y 2 一v 0 1 “i = o - v o ( 2 - 4 ) 【v j i ：南 e 2 = v 2 v 0 ，t = o v 0 ，则有： i r ，e z ，e 2 l l - d ，r ，e z l l - d ，风丁l 由公式i 爿，ec | = - ( a x c ) * b = - ( c x b ) * a ，式( 2 5 ) 可写为： ，1( t x i ) 2 1 l i = 赤暇筋j ，_ p s ， 四川师范大学硕士学位论文 为了提高运算效率，可先计算出p = d x e 2 和q = 口e i ) ，以减少不 必要的重复计算。 2 2 3 求交结果的输出 创建一个向量t e x t u r e 用作求交结果的输出，其初始值为零向量，表示粒子 与三角形不发生碰撞。当粒子与三角形相交时，把三角形的法向量h 输出。用 作粒子速度更新的输入参数。 2 3 基于流的粒子系统属性的更新 2 3 1 粒子速度属性的更新 粒子速度会受到多个参数影响。首先是它受到力的作用，会产生加速度。 如果受多个力的作用，那就需要通过物理方程来合成。粒子当前速度的计算公 式如下： v = v o + 口a t ( 2 7 ) 其中，矿表示当前速度，是上次更新时的速度，a t 是两次更新的时间差。 粒子和场景中其它物体碰撞后可能会发生方向和速率改变。比如水珠碰到 刚体后会溅起，雪碰到物体后就停在物体表面。这些碰撞属性由用户设定，在 粒子的整个生命周期中不会改变。粒子系统根据不同属性值用不同的算法来合 成碰撞后的速度。 2 3 2 粒子位置更新 粒子在运动过程中计算粒子位置的公式如下： p = p o + 础( 2 8 ) 其中