基于摄像机位置的大规模粒子云绘制加速算法

葛奇鹏

(武汉717 研究所，湖北武汉430000)

0 引言

无论在娱乐、教学、军事还是辅助设计领域，只要涉及天空仿真，便不可避免的要遇到云团绘制问题，粒子系统很好的解决了这类不规则模糊物体的仿真问题，但是由于粒子系统本身具有大量冗余三角网格，即使在这个显卡处理能力日新月异的年代，粒子系统的效率依然是个巨大的难题［1］。

前人在粒子系统的加速及优化上做过很多工作，被广泛使用的技术有BSP 树技术、shader 技术等，但是这些技术都无法解决数据冗余问题，计算机依然在绘制大量对视觉效果无增益的粒子，实时绘制大规模云团依然是一大难题［2］。

众所周知，人在观察时，对远处物体的精细度要求低于近处物体。如果能够基于摄像机对远处物体进行细节降阶处理，不仅于显示效果损伤较小，还能够大大降低需要绘制的粒子数量，从而达到提高绘制速度的目的。本文将就这个问题进行一些探讨，并提出了一个可行的解决方案，达到了提高绘制速度的目的。

1 粒子云计算与绘制

为了解决火焰、水波、云彩等不规则模糊物体的模拟问题，Reeves 于1983年提出了粒子系统。粒子系统是由大量粒子结合在一起来表现模糊物体的系统，其基本原理为:将模糊物体看作由大量不规则的、运动的、随机分布的粒子组成的粒子集。不同的粒子虽然属性、形状、物理化学性质、运动轨迹不同，但是他们都具有通用的属性，在计算机里可以很方便的将其定义为粒子类，包含自身的外形、空间位置、纹理等等信息，他们不断运动，不断改变形态，合力表现景物的外部特征［3］。

三维云团的模拟一般基于粒子系统。基本思想是认为一个粒子为一个球形物体，粒子密度服从高斯分布。一个粒子的属性包括:中心位置、半径、密度、颜色等［4］，通过分型算法可随机生成各式各样的云粒子点集，一般存储在一个.mesh 文件中供调用。

本文例子中的云粒子类如下所示:

class SkyCloudParticle

{

…/ /省略了方法

protected:

float _rRadius;

float _rTransparency;

Vec3f _vecPosition;

Vec4f _vecBaseColor;

std::vector＜Vec4f ＞ _vecLitColors;

Vec3f _vecEye;

};

由于粒子系统极为庞大，成千上万的粒子往往不可避免，虽然计算的时候会将粒子模型化、具体化，但是真正绘制的时候，往往用贴附粒子纹理的公告板代替。所谓公告板，就是一个始终朝向摄像机的有纹理的正方形面，相比于至少6个面的球体［5］，公告板对视觉效果的影响很低，但是性能极大地改善。本文采用最简易的公告板进行粒子的绘制，效果如图1所示。

图1 使用公告板粒子渲染的大规模云团

本文例子由OpenGL 实现，另绘制了山峦、天空盒、海水等其他物体以增强可视效果。

2 基于摄像机的分层加速

粒子系统的特点是粒子繁多，但是每个粒子的结构都相对简单，可削减性强，对于较远的云团，减少一定数量的粒子是可以接受的。如果2 个粒子之间距离为L 时人眼可以感觉出差异，当距离缩减为L/2 以下时，便可用一个粒子表示这2 个粒子，我们认为云团整体变成1/2 大小时，云团的粒子数降低一半是不影响视觉效果的。

由此可推出公式:

M 为减少粒子的倍率;D 为粒子距离摄像头的距离;∂，β 皆为与视景体相关的参数;F为相关函数。

基于摄像机的场景分层如图2所示。在图2 的视景体下，可以将裁减后的场景分为3个部分，红色部分云团使用全体粒子进行绘制，蓝色部分使用1/2 粒子进行绘制，灰色部分使用1/4 粒子进行绘制。

图2 基于摄像机的场景分层

这种不规则分层方式消除了相当数量粒子，而由于人眼的观察特性，这些粒子的缺失是不影响视觉效果的，在加速的同时无画面质量的降低。

3 基于BSP 树的算法实现及优化

一种经典的云团绘制算法是利用BSP 树以AABB 包围盒为基础将云团进行排序［6］。BSP 树可以有效的加速遍历，当某一个分枝被检测到不与视景体相交，则其下的所有子树都无需继续遍历，用这种方法判断哪些云团需要绘制，哪些不需要，这样可以节约大量计算时间，不仅如此，在本文的算法中，涉及到了云团与3 部分视景体的碰撞检测，同样要使用到BSP 树进行加速。

3.1 使用BSP 树对粒子绘制进行加速

首先用AABB 包围盒将云团分割成以云团为最小单位的BSP 树，然后根据视景体进行判断，如图3所示。

图3 基于AABB 包围盒的云团BSP 组织

判断哪些云团需要被绘制的方法如下:

1)以一个AABB 包围盒包围视景体，遍历BSP 树进行碰撞检测，裁减掉不相交的BSP 分枝［7］。

2)用视景体遍历剩下的BSP 树作碰撞检测，裁减掉不相交BSP 分枝，最后得到需要绘制的云团列表［8］。

3.2 使用BSP 树进行分层判断加速

判断云团阶层的方式跟判断哪些云团需要被绘制的方法类似，设置3 个列表，分别存放一阶、二阶、三阶云团的代号。从一阶视景体开始，将其用AABB 包围盒包裹，与已确定要显示的云团BSP 树进行碰撞检测，得到结果之后，再用实际视景体进行碰撞检测，得到一阶云团，将这些云团放入一阶云团列表，并从云团显示总表中移出。用同样的方式将剩下的显示总表与二阶、三阶视景体继续进行碰撞检测。最后依次以绘制100% 数量粒子、50%数量粒子、25% 数量粒子的方式对一阶、二阶、三阶云团表进行计算以及渲染。

4 本算法的加速效能计算

以本文程序为例，视景体投影为一个顶角为45°的等腰三角形。当云团足够多时认为一阶、二阶、三阶中绘制的云团与视景体面积成正比，则最终绘制的粒子数与未使用算法之前的比为:

可见减少的粒子数跟三阶的分割比例有很大关系。当一阶越大，显示效果越好，但绘制所需时间越多;反之当三阶越大，绘制速度极大提高，但绘制越粗糙。只要确保L1小于视景体长度的1/3，这种算法就能将绘制速度提高2 倍以上。

在本例中，多次试验得到结果为:不使用加速算法的场景绘制漫游平均帧数为27 帧，而使用之后可以提高到49 帧。

5 结束语

云团的绘制是场景仿真中不可缺少的部分，从以往的经验可得，云团的绘制由于其固有属性，占据了天空绘制60%以上的资源［9］，提高云团绘制速度即可提高天空场景的仿真速度。

本文的分阶思想简单明了，实践证明提高了绘制速度，但是尚有可继续挖掘的地方。本文只进行了三阶分阶，如采用更加精细的分割，对视觉效果的影响可能会更低，剔除的无需绘制的粒子可能更多，但是计算量可能会增加，编程复杂度也可能会相应增加，需要大量的研究和试验，但却不失为一个可以研究和探寻的方向［10］。

［1］陈华杰，余小清，唐经洲，等.基于粒子系统与LOD 技术的实时雨雪效果模拟［J］.计算机仿真，2008(4):194－197

［2］丁纪云，陈利平，李思昆.基于OpenGL 的烟花动态模拟方法的研究与实现［J］.计算机工程，2002，28(4):240－241

［3］王功明，郭新宇，赵春江，等.粒子系统的优化技术研究［J］.计算机应用研究，2008，25(2):495－497

［4］龚琳，顾大权，范茵，等.三维云场景的模拟［J］.解放军理工大学学报(自然科学版)，2006，7(5):496－500

［5］郭佳佳.基于粒子系统的自然景物模拟研究［J］.电脑知识与技术，2009(4):1006－1008

［6］马登武，叶文.虚拟现实技术及其在飞行仿真中的应用［M］.北京:清华大学出版社，2005:76－176

［7］胡英芳，黄强强，江顺亮.基于OpenGL 的离散粒子系统显示方法及其改进［J］.计算机与现代化，2011(2):53－57

［8］汪继文，陆和军，张妍妍.基于粒子系统的水滴溅落模拟［J］.科学技术与工程，2010(6):1547－1550

［9］Andersen S，Andersen L.Analysis of spatial interpolation inthe material－point method［J］.Computers and Structures，2010 (6):506－518

［10］Fang Jiannong，Parriaux Aurele，Rentschler Martin，et al.Improved SPH methods for simulating free surface flows ofviscous fluids［J］.Applied Numerical Mathematics，2009(3):251－271