基于不可见剔除的大规模粒子绘制算法

 共1页  1 

粒子模拟出现在分子动力学、电磁辐射、激光聚变、裂变能源等多个应用领域中，是科学计算的一个重要形式。为了取得高科学置信度，人们不断增加粒子数目以实现更高的计算精度，由此，模拟输出的粒子数据也持续增长。大规模粒子数据对可视化与可视分析带来了极大的挑战。在目前的可视化系统中，常用球体表示粒子，并以离散化球面的方式送入OpenGL绘制。根据离散化精度的不同，一个球面可能对应生成10~1000个OpenGL绘制图元。对于数千万甚至数亿粒子，绘制中OpenGL处理图元量可达数亿至数百亿以上，这对目前的并行绘制系统来说是难以承受的。

极大量的粒子之间容易相互遮挡，呈现给用户的只是一小部分，将大部分的不可见的粒子送入OpenGL绘制，严重浪费了绘制资源。而且，粒子最终投影到绘制屏幕上，由于屏幕分辨率有限，用相同的离散化精度绘制粒子，对投影面积很小的粒子是冗余的，而对投影面积很大的粒子又是不够的。这两方面的问题给粒子绘制算法留下了很大的优化空间。由此，我们提出了基于不可见剔除的大规模粒子绘制算法，在保证绘制质量的前提下，大幅提升绘制效率，满足相关应用领域对粒子数据的交互可视分析需求。我们一方面充分利用粒子球之间的遮挡关系，剔除掉大量被遮挡的粒子，另一方面则自适应地选用合适分辨率来绘制粒子球，由此不断提升绘制速度。

1  基于不可见剔除的大规模粒子绘制算法

我们提出了基于不可见剔除的大规模粒子绘制算法，以实现对大规模粒子数据的高效绘制，如图1所示。我们首先基于可见性对粒子数据进行筛选，筛选从两个粒度进行：利用OpenGL的视景锥对数据场进行粗筛，将落在视景锥之外因而对用户不可见的数据块剔除；然后在绘制一个个粒子时，我们将判断粒子是否被其它粒子遮挡，剔除掉被遮挡的粒子。另一方面，在具体离散化一个粒子球面时，我们将根据粒子离视点的远近及其半径大小，自适应地选用合适的网格分辨率，而不是基于一个固定分辨率。在静态负载平衡中，我们优先把相邻的数据块分配到一个处理器核上，局部粒子集中到了一块，它们之间的遮挡关系很容易被凸显出来，使后续的遮挡绘制更能发挥效用。最后，我们融合各处理器核上的绘制结果，得到完整的绘制结果图像输出。

2  基于遮挡的粒子绘制

根据透视投影的连续性，投影到屏幕上相近位置的球，具有相似的投影形状，一种近圆形的二维凸区域。我们以球心的投影坐标作为这些投影形状的参考点。由于屏幕像素是有大小的，参考点位于同一个像素的具有相同深度和半径的两个球，其投影形状也不一定重合。为了覆盖一个球，我们考虑以其参考点为中心的3′3屏幕区域，投影到这9个像素的9个球，在绝大多数情况下可完全覆盖这个球，见图2。由此推知，用3′3模板上的9个球可遮挡投影到中心位置的一个离视点更远且半径更小的球。作为该遮挡剔除方法的理论基础，我们提出并证明了九圆覆盖定理：在半径相同的情况下，若有9个圆的圆心所在像素正好组成一个3′3像素区域，则任意一个圆心落在中心像素的圆被上述9个圆覆盖。

在具体的基于遮挡的绘制算法中，我们生成一个辅助网格对应屏幕像素，一个像素赋予几种属性：占位标记T、最小深度D和邻居个数N。占位标记T的含义是，有粒子（指球心）投影到这个像素时记为1，否则为0。最小深度D指的是投影到此像素的粒子深度的最小值。邻居个数N表示以它为中心的3′3邻域网格中有多少已被占位。占位标记T和邻居个数N均初始化为0。

然后，我们将按以下算法递归地处理下一个粒子（其深度为d）：

（1）若投影像素的占位标记T等于0，则绘制该粒子，并将T修改为1，D设为d，八个邻居的N_i各加1。

（2）当投影像素的占位标记T等于1时：若N=8、D￡d且D_i￡d，"i，则粒子被遮挡，无需绘制；否则，绘制该粒子，D更新为min{d, D}。

3  粒子球自适应离散化

在粒子绘制中，粒子球由于离视点远近不同、半径不同，从而在屏幕上投影区域或大或小，甚至退化为一个像素，而实际上粒子一般是以一个离散化球面的形式送入OpenGL绘制。如果以相同的分辨率离散球面，则离视点太近的球可能绘制得过于粗糙，而离视点很远的球又使用了过多几何图元从而浪费了绘制时间。由此，我们按如下方式自适应地选用不同分辨率来绘制空间中的一个粒子球：

（1）依据OpenGL的视景投影关系，计算该球在屏幕上的投影宽度；

（2）若只有一个像素宽度，则计算视线与球的前交点，送入OpenGL绘制；

（3）否则，依据宽度取一个合适的分辨率来定义一个离散化球面，送入OpenGL绘制。

4  应用效果

测试数据是分子动力学实际模拟结果数据，该模拟在32000个处理器核上实现了2.56亿粒子的模拟，揭示了含纳米尺度孔洞金属材料的冲击结构和动力学响应机理，实际选择输出了3800万粒子(见图3)。测试中分别使用了4个、8个、16个和24个处理器核，测试结果参见图4。从图4中可看出，我们提出的算法充分利用极大量粒子之间的遮挡关系，自适应地绘制粒子球，相对于传统粒子绘制方法实现了显著的绘制加速，加速比可达29~53倍，其中，24核上绘制时间从269 s降低到了9 s。

在24核上，我们统计了各核处理的粒子总数以及因遮挡而被剔除的粒子个数，并计算它们之间的比率，由此绘制了各核上粒子的剔除比率图，结果参见图5。从图5中可以看出，各核上粒子的剔除比率在78%~92%。我们进一步求出了算法的总体剔除比率，约为89%。显然，众多粒子因为遮挡而被剔除，不进入后续的处理流程，为系统节省了大量的绘制开销。