大规模粒子数据的计算属性上的交互选择 (Interactive Selection on Calculated Attributes of Large-Scale Particle Data)

在大规模的粒子数据中,有些属性需要在模拟过程中才能获得,比如温度、表面张力等。我们需要这些属性用来选择感兴趣区域的粒子,比如热点区域或者局部极值区域等,并在之后的模拟中观察粒子的变化情况。为了使用这些属性,我们可以首先运行一遍模拟过程,并把计算得到的属性保存下来,接着在系统中加载这些提前计算好的属性。然而,保存这些属性需要大量的磁盘空间,而且如果需要其他的属性,还需要再进行模拟以保存属性。另一种使用计算属性进行选择的方法是在模拟过程中实时计算并根据属性选择粒子,然而如果计算所有粒子的属性,模拟时需要分配更多的内存空间并使用更长的时间。本文结合3D视图刷选,提出了一种数据驱动的基于延迟计算的选择扩展方法[1]。

图 1 工作流程

该工作的流程如图1所示:在用户刷选起始的粒子后,该方法计算起始粒子与邻居粒子的属性,并在邻居中扩展符合属性条件的粒子;接着以此轮中被选中的粒子出发,计算自身与邻居粒子的属性,并重复扩展过程;粒子选择的扩展过程完成后,便可观察这些粒子在之后模拟中的变化。

在介绍选择扩展的详细步骤之前,首先介绍该方法使用的数据结构。首先,依据空间位置,该方法对粒子进行计数排序(counting sort),将粒子划分到不同的小格(cell)中。每个小格内的粒子根据其选择状态,包括被选择(selected)、最新被选择(latest selected)以及未被选择(unselected)状态,进行排序。小格的结构如图2所示,三种选择的状态具体功能在扩展过程中进行描述。

图 2 小格内的数据结构

每个小格具有静态的属性:小格索引值,属性索引以及同步标识。在扩展的延迟计算中,需要计算的小格具有动态分配的信息,包括小格内部未选择的粒子数量、最近被选择的粒子数量、计算属性的索引等,每个小格通过其静态的索引值获取动态信息。同时,需要计算的小格的计算属性也需要动态分配的空间,每个小格通过内部的计算属性索引获取到对应的属性值。小格的静态信息以及动态信息如图3所示。

图 3 小格的静态和动态信息

接下来介绍该方法的选择扩展过程,该过程可分为四步。 第一步,系统载入粒子数据后,用户在感兴趣的区域,手动刷选一定的粒子,并指定扩展中使用的属性以及比较条件,例如“被扩展的粒子温度要低于当前的粒子”。

第二步,准备必需的计算属性。在扩展过程中,需要计算属性的粒子包括两部分,第一部分为新选的粒子所在小格内的所有粒子,第二部分为新选粒子所在小格的邻居小格中与新选粒子相邻的粒子。详细的计算过程如图4所示。

图 4 动态计算所需的粒子属性

第三步,对每个包含新选择粒子的小格,进行扩展。首先在包含新选择粒子的小格中,检查小格内部未选择的粒子,如果满足扩展的条件,则对其进行标记,并将符合条件选择的状态为未选择的粒子的状态转换为新选择,将用来检查扩展条件的新选择粒子状态转换为被选择;接着,在邻居小格中,对于新选择粒子的邻居粒子,如果其满足扩展条件,则标记其为external,即在邻居小格扩展的粒子。扩展的具体过程见图5。

图 5 粒子选择的扩展过程

第四步,合并本次扩展中选择的粒子。首先将第三步中标记为external的邻居小格内的粒子标记为最新选择的粒子, 接着对于包含最新选择粒子的小格,将其作为扩展后的基本小格,并标记未完成属性计算的小格,以便在第二步中计算此邻居小格内部粒子的属性。具体过程见图6。

图 6 合并选择的粒子

整体的扩展流程可见图7。在进行最初的粒子选择后,必要属性计算(即,准备过程)、扩展选择、合并三个步骤为重复进行的过程,直到没有可扩展的粒子。

图 7 扩展流程图示

文中的实验在两个数据集上进行。第一个数据集为光滑粒子流体动力学(smoothed particle hydrodynamics, SPH)数据集,测试在不同的选择粒子数量情况下,比较提前计算属性的方法与本文方法的时间。在图8的结果中可以看出,在大部分情况下,即选择的粒子数不是非常接近全部的80M粒子的情况下,本文的方法比提前计算的方法较快。

图 8 在 SPH 数据集上的测试

第二个数据集为分子动力学(molecular dynamics)数据集,测试在不同的总粒子数方案中,选择不同的粒子数量后,平均到每个所选粒子花费的时间。图9的结果中,每个方案包括三条线,为进行100次测试后的中值以及1/4、3/4的时间结果。

图 9 在分子动力学数据集上的测试

[1] Benjamin Wollet, Stefan Reinhardt, Daniel Weiskopf, and Bernhard Eberhardt. Interactive Selection on Calculated Attributes of Large-Scale Particle Data. In Eurographics Symposium on Parallel Graphics and Visualization 2021.

发表评论?

0 条评论。

发表评论


注意 - 你可以用以下 HTML tags and attributes:
<a href="" title=""> <abbr title=""> <acronym title=""> <b> <blockquote cite=""> <cite> <code> <del datetime=""> <em> <i> <q cite=""> <s> <strike> <strong>