赵相坤 李凤霞 战守义

(北京理工大学北京市智能信息技术实验室，北京100081)

基于物理的模拟已广泛用于计算机图形学中，越来越多的自然现象如雨、泥浆、烟圈、海浪等都可以被逼真地模拟显示出来.这些模拟问题都可以归结为复杂的流体模拟.一个典型的流体模拟可以用Navie-Strokes方程表示:

式中，u为流体速度，ρ为密度，p为压强，ν为动力粘滞系数，F为作用于流体的所有外力之和.

目前主要有两种跟踪流体移动的方法:(1)欧拉方法，该方法一般基于网格，在固定的网格点监测流体的参数(密度、速度、压强等)随时间的变化;(2)拉格朗日方法，该方法用一系列的粒子表示流体，流体在指定位置的参数通过对一定范围内粒子属性值的加权求和得到.

平滑粒子动力学(SPH)［1］是一种拉格朗日形式的流体模拟方法.在SPH方法中，流体用一系列的携带有各种流体属性的粒子表示，任意位置的流体属性通过对附近的粒子属性值进行加权求和得到.当使用的粒子数达到几十万甚至上百万时，查找指定位置的粒子的所有邻居就成为流体模拟的瓶颈.

为了查找粒子在指定位置处的邻居，一般采用空间划分的方法，将空间划分成均匀的网格，如图1所示.不同的粒子根据其位置属性分别属于不同的网格单元，位于同一网格内的粒子互为邻居，当然任一粒子的邻居还包括与粒子所在网格相邻的其余26个网格内的粒子.

图1 三维空间的网格剖分Fig.1 Grid partition in 3D space

为了实现粒子邻居的快……