烟雾等不规则模糊物体的模拟一直是计算机图形学中最 具挑战性的

烟雾等不规则模糊物体的模拟一直是计算机图形学中最 具挑战性的课题之一，它们由于外形极不规则，变化规律极其 复杂，使得经典的几何学对它的描述无能为力。但随着近年 来模糊物体特效在视影、游戏和计算机动画中的应用需求，模 糊物体的模拟得到了较快的发展，涌现出了很多成果。 很多不规则模糊物体的模拟都用到了基于微粒群的方 法（一种模拟一类模糊物体运动的技术），它是Reeves[1]于1983 年提出的。物体被定义为成千上万不规则且随机分布的微粒 集合，各个微粒都有自己的属性：如颜色、位置、大小、生存期、 速度等，它们每时每刻都在不断地运动和改变形态；每个微粒 都有一定的生命周期，都将经历出生、活动、死亡的过程。微 粒群充分体现了不规则模糊物体的运动性和随机性，从视觉 的真实性，它是符合物体的形体特征。 基于流体方程的模糊物体模拟也是一个主要方向，它是 通过方程的求解来展示物体运动的真实性。Stam[2]结合半拉 格朗日解法对NS方程进行隐式求解，有力推动了真实感流体 模拟的发展。Fedkiw[3]和Selle[4]是用流体力学模拟烟雾微粒运 动的杰出代表，他们模拟出的烟雾流体真实感非常强。 传统的微粒群优化技术因为不能精确模拟出运动轨迹， 所以不能应用于具有精度要求的场合[9]。而基于流体方程的

方法则需要求解大量的复杂方程，虽然网格插值等方法能够 提高速度，但实时性在当前硬件条件下仍然是其瓶颈，所以将 微粒群方法结合其他物理学模型来进行烟雾微粒运动模拟具 有重要的意义。 Stam[5]等人给烟雾微粒定义了浓度函数，在微粒绘制时根 据其浓度的大小来调节微粒颜色的深浅，湛永松[10]在前者的基 础上加入了风力对浓度的影响，但这类算法都不能从物理真 实上模拟微粒的运动。Zhou[6]等人用聚类树的方法模拟了烟 雾与场景障碍物的碰撞，这种方法的碰撞检测精度不高，而且 无法模拟粒子与粒子之间的碰撞。Barnes[7]提出了一种计算粒 子间作用力的方法，它用树结构来存储每个粒子，计算每个子 区域内部的所有粒子的质心和总质量，对每个粒子通过周游 树的各子区域的质心来计算它所受到的力。这样虽然减少了 复杂度，但碰撞检测精度不高，会产生提前碰撞，而且建立一 棵树也会消耗大量计算资源。 Teschner M[8]用一种基于空间哈希表的方法来进行变形 物体内部的碰撞检测，该方法极大地减少了碰撞检测的时间， 而且简单有效，碰撞精确度可以根据需要自己调整。因此本 文引入这种方法来进行烟雾粒子与粒子之间的碰撞检测，增 强了实时性。在系统中还增加了浓度扩散力的作用，用来精 基于微粒群优化的烟雾扩散的实时研究 刘 斓1，徐健锋2， 刘 群3 LIU Lan1, XU Jianfeng2,LIU Qun3 1.南昌大学 计算机科学与应用技术系，南昌 330031 2.南昌大学 软件学院，南昌 330047 3.重庆邮电大学 计算机科学与技术学院，重庆 400065 1.Department of Computer Science &Application Technology, Nanchang University, Nanchang 330031, China 2.College of Software, Nanchang University, Nanchang 330047, China 3.College of Computer Science and Technology, Chongqing University of Posts and Telecommunications, Chongqing 400065, China

LIU Lan, XU Jianfeng,LIU Qun. Studying of real-time smog diffusing based on particle swarm optimization. ComputerEngineering andApplications, 2012, 48（2）：179-181. Abstract：Based on particle system, the method of combining smog particle density diffusion and inter particles collision each other is studied in this paper, which simulates the diffusing and real-time performance of smog. Diffuse force field is established by the diffu- sion equation, which can ensure the accuracy of the trajectories of diffusion. In order to reduce the time on collision between particles each other, a collision technology based on spatial hashtable is introduced in the article. Experimental results via simulation experiment show that the proposed method in the paper not only can improve the simulation speed of real-time requirements, but also demonstrate the authenticity of the smog diffusion. Key words：particle system; diffusion equation; spatial

hashtable; collision detection; real time

摘 要：在粒子系统的基础上研究了烟雾微粒浓度扩散和微粒内部之间碰撞检测相结合的方法。通过扩散方程建立了烟雾扩散 力场，以确保扩散运动轨迹的精确性；为了降低微粒之间的碰撞检测时间，引入了基于空间哈希表的碰撞检测技术。经仿真实验 结果证明了该算法不仅能够提高模拟速度以达到实时控制要求，而且能够展示烟雾扩散的真实性。 关键词：粒子系统；扩散方程；空间哈希表；碰撞检测；实时模拟 DOI：10.3778/j.issn.1002-8331.2012.02.051 文章编号：1002-8331（2012）02-0179-03 文献标识码： A 中图分类号：TP391.9 基金项目：国家自然科学基金（No.61070139）；重庆市自然科学基金（No.CSTC2007BB2386）；重庆市教委应用基础研究项目（No.KJ070504）。 作者简介：刘斓（1973—），女，讲师，主要研究方向：人工智能，Rough集，数据库；徐健锋（1973—），男，副教授，硕士生导师；刘群（1969—），女， 博士，教授，硕士生导师。E-mail：jianfeng.nc@gmail.com 收稿日期：2011-06-15；修回日期：2011-12-23

Computer Engineering and Applications计算机工程与应用 179

Computer Engineering and Applications计算机工程与应用2012 ，48（2）

确模拟烟雾的扩散，这种粒子系统与物理动力学相结合的模 型达到了物理真实性与模拟实时性之间的一个权衡，取得了 比较好的模拟效果。 1 浓度扩散 当烟雾在无穷的空间扩散时，假设不受大地和风等其他 力的影响作用，扩散服从热传导定律。烟雾微粒浓度随着烟 雾的扩散时刻发生着变化，浓度的变化规律可表示为： ì í ? ? ? ? ? ?C ?t =k ? è ? ? ? ? ÷ ÷ ?2C ?x2 + ?2C ?y2 + ?2C ?z2 (-￥t0) C(xyzt0)=C0(xyz) （1） 在上式中，C 表示浓度场的标量浓度， k 表示扩散系数， t0 表 示粒子生成的时间，因为式（1）只用来模拟粒子生成后浓度的 变化，所以有 C0(xyz)=0 （2） 经过Jos Stam[5]等人的求解，根据式（2）求出式（1）的基本 解是： C(xyzt)= 1 [2k π(t-t0)]3 e -

(x-x0)2 +(y-y0)2 +(z-z0)2 4k2(t-t0) （3） 其中(x0y0z0)表示烟雾源点的位置，令： ì í ? ? ? l=t-t0 r= (x-x0)2 +(y-y0)2 +(z-z0)2 则l 表示粒子的当前存活时间（当前生命值）， r 表示粒子到源 点的距离，于是式（3）可以化为： C(rl)= 1 (2k πl)3 e - r2 4k2l （4） 由式（4）可知，浓度C 的等值面是一个半径相等的球面， 并随着半径的增加而递减，烟雾从浓度高的地方向浓度低的 地方扩散，如图1所示。

设空中一个烟雾粒子的当前位置距源点为 r1 ，当前生命 值为 l1 ，前一帧的位置距源点为 r2 ，生命值为 l2 ，则两帧间产 生的浓度差为： DC=C(r2l2)-C(r1l1) （5） 根据理想气体状态方程 PV=nRT 可知，压强与浓度成正 比，浓度差会产生压强进而产生压力。为了方便计算，设粒子 由浓度产生的扩散压力为： f扩散 =DC′s （6） 其中s为比例常数，由经验值给出。烟雾是以球体半径的方式向 各个方向扩散，因此 f扩散 的方向是由源点指向当前粒子位置。 虽然浓度扩散力相对其他力来说比较小，但对烟雾运动 的轨迹的影响还是很重要，加上浓度扩散力之后烟雾的扩散 将更加真实。 2 内部碰撞检测 在烟雾微粒运动的过程中，粒子与粒子之间发生的碰撞 是不能忽略的，而且粒子与粒子之间碰撞所产生的力是造成 烟雾扩散的一个重要因素。但如果每两个粒子之间都要进行 一次碰撞检测，显然需要消费大量的时间，当粒子数量很多的 时候不可能达到实时性要求。因此碰撞检测和碰撞反应的处 理在计算机图形学中是一个十分困难的问题，

如何缩短碰撞 检测时间以及碰撞后的粒子如何运动仍是当今图形学研究的 热点之一。本文引入空间哈希表来进行碰撞检测，并根据冲 量定理精确求出粒子碰撞后的运动状态。 2.1 空间哈希表 空间哈希表和普通的哈希表一样，是建立一种数据实体 与数据存放地址之间的映射关系。空间哈希表将整个三维空 间划分成许多小的三维网格，其存放的内容便是系统中的烟 雾粒子，而烟雾粒子所存放的地址便是粒子所在的三维网格 被散列化后的索引号。图2以二维空间为例，将空间划分成0、 1、 2、 3四个小网格，空间中的粒子ABCDEFGH与其所占的网 格索引号通过哈希表进行映射。 2.2 粒子空间散列 在三维空间中，将一个三维点(xyz) 映射到一维的哈希 表中的键值 h可以通过哈希函数实现： h=hash(xyz)。本文 根据烟雾的形状来制定一个特殊的哈希函数，以提高散列的 均匀度。由于烟雾从下往上扩散，因此在Y 轴上的跨度很大， 而在 X 和 Z 轴上的偏移较小，可以基于Y 轴分层，然后每一 层按象限分成四小块： h(xyz)=D(y)′4+D(xz) 其中， D(y)= ì í ? ? ? ? ? 0, y￡L ? ? y L , L

图2 空间哈希表示意图 180

2012，48（2）

2.3 粒子间的碰撞 粒子通过哈希函数散列化之后，每帧的碰撞检测只要与 其所处网格内的粒子（即哈希表键值相同的粒子）进行检测即 可，这样避免了每一个粒子进行碰撞检测时的复杂性。当粒 子 p 既属于 Ci 又属于 Cj 时，对 p 的碰撞检测要分成两个部 分，即对Ci 和Cj 中的所有粒子（不包括 p）进行碰撞检测。于 是对所有粒子碰撞检测可以通过以下伪代码来实现： for（int i=0 to n－1）//从C0 到Cn-1开始遍历 { for（int j=0 to size of (Ci)－1）//遍历每一个网格 for（int k=0 to size of (Ci) －1）//网格中的粒子每两个之 间都要检测 { if（pij != pik）//是否为同一粒子 Collision detection (pij,pik)；//碰撞检测 } }

如图4所示，粒子 S1和粒子 S2 相碰，碰撞前 S1和 S2 的 速度分别为 v1- 、 v2- ，碰撞后的速度分别为 v1+ 和 v2+ ， n 为碰 撞作用线的单位向量。现以一维空间的碰撞为例，运用动量 守恒定理求出碰撞后的速度。

根据已知条件，可以列出三个方程： J=m1(v1+ -v1-) （7） -J=m2(v2+ -v2-) （8） e=-(v1+ -v2+)/(v1- -v2-) （9） 其中式（7）和（8）是冲量定律，式（9）是恢复系数方程，方程中 m1 和 m2 分别表示 S1和 S2 的质量， J表示粒子碰撞产生的冲 量，此时 S1和 S2 受到的冲量是相反的， e表示碰撞的恢复系 数，这是一个常量，与物体材质和结构相关。将方程（7）和（8） 进行变形： v1+ =J/m1+v1- （10） v2+ =-J/m2 +v2- （11） 将 v1+ 和 v2+ 代入式（9）的方程中，得到： J=- (v1- -v2-)(e+1) 1/m1+1/m2 （12）

把式（12）代入式（10）和（11）便可求出两个粒子碰撞后的 速度大小。 当在三维空间时，速度将变成矢量，只有法线方向的速度 变化才会产生冲量，只有在法线方向上的冲量分量才能对速 度产生影响，这样式（12）变为： J= -(v1- -v2-)(e+1)·n 1/m1+1/m2 （13） 式（10）和（11）变为： ì í ? v1+ =J·n/m1+v1- v2+ =-J·n/m2 +v2- 再代入式（13），最后所求结果为： v1+ =v1- - (v1- -v2-)(e+1) 1+m1/m2 v2+ =v2- + (v1- -v2-)(e+1) 1+m2/m1 碰撞后的两个粒子将分别以 v1+ 和 v2+ 的速度进行运动， 并继续在这一帧内与空间中的其他粒子进行碰撞检测。

3 仿真 在仿真阶段，将微粒群优化技术结合纹理映射和Bill- board方法，对烟雾粒子进行渲染。这样一个纹理片可以代替 许多的小粒子，从而节省计算资源，提高渲染速度。本文利用 40×40的纹理作粒子贴图，采用大粒子模拟。 本文算法在个人计算机上实现，软硬件环境配置为CPU： INTEL E2180；显卡：Gforce 7300GT 128 MB；内存： 1 GB RAM； 研发平台：VS2005 C++。图5是烟雾在随机风力的作用下自由 扩散的现象；图6是烟雾与空中的球体碰撞时产生发散现象。

本文算法和Reeves在文[1]中的粒子系统方法进行了比 较，由于文[1]中的粒子系统方法是单纯进行粒子内部碰撞检 测的，所以时间明显消耗更多。在试验中，哈希表一共采用了 32个网格，划分的三维网格高度为 L=100 ，总共有 n =8层，粒 子球体碰撞的恢复系数 e=0.5，浓度扩散力比例常数 s=0.1， 粒子的生命周期介于[68]秒之间。比较结果如表1所示。 通过表1可以看出，本文所采用的算法明显比传统的粒子 系统算法要快，当系统中的粒子较多时，传统粒子的碰撞检测 算法很难满足实时性所要求的帧率大于20的特点，而本文算 法依然可以达到较好的性能。 碰撞后的速度 碰撞后的速度 碰撞前的速度 碰撞前的速度 S2 S1

图4 两个粒子的碰撞

图5 烟雾微粒在风中自由扩散 图6 烟雾微粒在空中碰撞时发散 粒子发射 速率/（个· s－1） 10 20 30 40 50 本文算法 帧率/（f· s－1） 72 60 51 43 38

传统粒子系统 算法帧率/（f· s－1） 46 32 22 17 14 表1 不同算法的帧率比较 0 1 2 3 4 5 6 7 8 0 1

2 3 4 5 6 7 8

S 图3 一个粒子对应几个空间网格 SSS S

（下转234页）

刘 斓，徐健锋， 刘 群：基于微粒群优化的烟雾扩散的实时研究 181 Computer Engineering and Applications计算机工程与应用2012 ，48（2） [2] Shladover S E，Desoer C A，Hedrick J K，et al.Automated vehicle control developments in the PATH program[C]//IEEE Transac- tions on Vehicular Technology，1991，40（1）：114-130. [3] Zhang J R，Xu S J，Rachid A.Sliding mode controller for auto- matic steering of vehicle[C]//Proceedings of the 27th Annual Conference of the IEEE Industrial Electronics Society.Piscat- away，NJ，USA：IEEE，2001：2149-2153. [4] Smith D E，Starkey J M，Benton R E.Nonlinear-gain-optimized controller development and evaluation for automated emergency vehicle steering[C]//Proceedings of the American Control Con- ference.Piscataway，NJ，USA：IEEE，1995：3586-3591. [5] Chan C Y，Tan H S.Lane tracking control in vehicle-following collision situation[C]//Proceedings of the American Control Con- ference.Piscataway，NJ，USA：IEEE，1999：3697-3701. [6] O’Brien R T，Iglesias P A，Urban T J.Vehicle lateral control for automated highway systems[J].IEEE Transactions on Control Systems Technology，1996， 4 （3）：266-273. [7] Feng K T，Tan H S，Tomizuka M.Automatic steering control of vehicle lateral motion with the effect of roll dynamics[C]//Pro- ceedings of the American Control Conference.Piscataway，NJ， USA：IEEE，1998：2248-2252. [8] Wang J Y，Tomizuka M，Robust H.Lateral control of heavy-duty vehicles in automated highway system[C]//Proceedings of the American Control Conference.Piscataway，NJ，USA：IEEE，1999： 3671-3675. [9] Hessburg T，Tomizuka M.Fuzzy logic control for lateral vehicle guidance[C]//Proceedings of the IEEE Conference on Control Applications.Piscataway，NJ，USA：IEEE，1993：581-586.

[10] El Kamel A，Dieulot J Y，Borne P.Fuzzy controller for lateral guidance of busses[C]//Proceedings of the 2002 IEEE Interna- tional Symposium on Intelligent Control.Piscataway，NJ，USA： IEEE，2002：110-115. [11] 李庆中，顾伟康，叶秀清，等.移动机器人路径跟踪的智能预瞄控 制方法研究[J].机器人，2002，24（3）：252-255. [12] Kehtarnavaz N，Groswold N，Miller K，et al.A transportable neural- network approach to autonomous vehicle following[J].IEEE Trans- actions on VEHICULAR Technology，1998，47（2）：694-702. [13] Tsugawa S，Mori H，Kato S.A lateral control algorithm for vision- based vehicles with a moving target in the field of view[C]// IEEE Int Conf Intelligent Vehicles，1998. [14] 曹凯，于少伟，周芦芦.基于动态目标位置的智能车辆控制研究[J]. 信息与控制，2008，37（4）：476-480. [15] Pozna C，Troester F.On the design of an obstacle avoiding tra- jectory：method and simulation[J].Mathematics and Computers in Simulation，2009， 79：2211-2226. [16] 殷路，尹怡欣.基于动态人工势场法的路径规划仿真研究[J].系统 仿真学报，2009，21（11）：3325-3328. [17] 吴镜开，黄远灿，王世兴.基于势场法的移动机器人避障路径规划[J]. 微计算机信息，2007，23（2）：228-230. [18] 赵毅红，朱剑英.基于综合导向的车式移动机器人轨迹跟踪控制[J]. 华南理工大学学报：自然科学版，2006， 34（11）：60-63. [19] 李惠光，

卫涛.基于速度矢量的机器人动态避障规划[J].武汉理工 大学学报，2009，31（13）：133-136. [20] 胡跃明.非线性控制系统理论与应用[M].2版.北京：国防工业出版 社，2005：188-193. 通过设定粒子发射速率为30个/s，其他参数不变的情况 下，选择了不同网格对本文算法实时性进行了对比，实验数据 如表2所示，由比较可以看出，在网格少的时候，帧率增长比较 明显，但随着网格的增加，因为粒子所占空间的局限性，因此 结果趋于稳定。 4 结束语 本文基于粒子系统技术，结合动力学，引入基于空间哈希 表的碰撞检测方法进行了烟雾微粒扩散模拟的研究，在场景 中添加了浓度扩散力作用，执行结果有很强的实时性、物理真 实性和视觉真实性，这一研究结果将在环境监测、空气污染指 数测定方面具有较好的应用价值。 今后的研究工作将主要集中在以下几个方面：首先，研究 粒子碰撞后的聚合以及形变效果；其次，烟雾粒子的真实感光 照模型的研究，以实现更加具有视觉真实性和物理真实性的 模拟效果。第三，用环境检测、空气污染指数测定实例进一步 说明这项研究应用的有效性、可行性和实际应用价值。

参考文献： [1] Reeves W T.Particle systems-a technique for modeling a class of fuzzy objects[J].Computer Graphics，1983，17（3）：359-376. [2] Stam J.Stable fluids[C]//Proceedings of SIGGRAPH，Los Angeles， California，USA，1999：121-128. [3] Fedkiw R，Stam J，Jensen H.Visual simulation of smoke[C]//Pro- ceedings of SIGGRAPH，Los Angeles，California，USA，2001： 15-22. [4] Selle A，Mohr A，Chenney S.Cartoon rendering of smoke anima- tions[C]//Proceedings of the 3rd International Symposium on Non-photorealistic Animation and Rendering，Annecy，France， 2004：57-60. [5] Stam J，Fiume E.Turbulent wind fields for gaseous phenomena[J]. Computer Graphics，1993，27（4）：369-373. [6] Zhuo Neng-Wen，Rao Yun-Bo.Real time dense smoke simulation based particle system[C]//IITAW’08，2008：809-813. [7] Barnes J，Hut P.A hierarchical O（NlogN）force calculation algo- rithm[J].Nature，1986，324：446-449. [8] Teschner M，Heidelberger B，Muller M，et al.Optimized spatial hashing for collision detection of deformable objects[C]//Pro- ceedings of Vision，Modeling，Visualization，2003： 47-54. [9] 张芹，谢隽毅，吴慧中，等.火焰、烟、云等不规则物体的建模方法研 究综述[J].中国图象图形学报，2000， 5 （3）：186-190. [10] 湛永松，石民勇，费广正.基于物理模型的实时卡通烟雾模拟算法[J]. 中国图象图形学报，2007，

卫涛.基于速度矢量的机器人动态避障规划[J].武汉理工 大学学报，2009，31（13）：133-136. [20] 胡跃明.非线性控制系统理论与应用[M].2版.北京：国防工业出版 社，2005：188-193. 通过设定粒子发射速率为30个/s，其他参数不变的情况 下，选择了不同网格对本文算法实时性进行了对比，实验数据 如表2所示，由比较可以看出，在网格少的时候，帧率增长比较 明显，但随着网格的增加，因为粒子所占空间的局限性，因此 结果趋于稳定。 4 结束语 本文基于粒子系统技术，结合动力学，引入基于空间哈希 表的碰撞检测方法进行了烟雾微粒扩散模拟的研究，在场景 中添加了浓度扩散力作用，执行结果有很强的实时性、物理真 实性和视觉真实性，这一研究结果将在环境监测、空气污染指 数测定方面具有较好的应用价值。 今后的研究工作将主要集中在以下几个方面：首先，研究 粒子碰撞后的聚合以及形变效果；其次，烟雾粒子的真实感光 照模型的研究，以实现更加具有视觉真实性和物理真实性的 模拟效果。第三，用环境检测、空气污染指数测定实例进一步 说明这项研究应用的有效性、可行性和实际应用价值。

参考文献： [1] Reeves W T.Particle systems-a technique for modeling a class of fuzzy objects[J].Computer Graphics，1983，17（3）：359-376. [2] Stam J.Stable fluids[C]//Proceedings of SIGGRAPH，Los Angeles， California，USA，1999：121-128. [3] Fedkiw R，Stam J，Jensen H.Visual simulation of smoke[C]//Pro- ceedings of SIGGRAPH，Los Angeles，California，USA，2001： 15-22. [4] Selle A，Mohr A，Chenney S.Cartoon rendering of smoke anima- tions[C]//Proceedings of the 3rd International Symposium on Non-photorealistic Animation and Rendering，Annecy，France， 2004：57-60. [5] Stam J，Fiume E.Turbulent wind fields for gaseous phenomena[J]. Computer Graphics，1993，27（4）：369-373. [6] Zhuo Neng-Wen，Rao Yun-Bo.Real time dense smoke simulation based particle system[C]//IITAW’08，2008：809-813. [7] Barnes J，Hut P.A hierarchical O（NlogN）force calculation algo- rithm[J].Nature，1986，324：446-449. [8] Teschner M，Heidelberger B，Muller M，et al.Optimized spatial hashing for collision detection of deformable objects[C]//Pro- ceedings of Vision，Modeling，Visualization，2003： 47-54. [9] 张芹，谢隽毅，吴慧中，等.火焰、烟、云等不规则物体的建模方法研 究综述[J].中国图象图形学报，2000， 5 （3）：186-190. [10] 湛永松，石民勇，费广正.基于物理模型的实时卡通烟雾模拟算法[J]. 中国图象图形学报，2007，

本文来源：https://www.bwwdw.com/article/wc4a.html