摘要: 目前的距离场构建时间消耗过于漫长。而目前各种场景要求有稳定高速的距离场构建算法。因此我们提出了一种快速的方法BADF（基于包围盒层次结构的自适应距离场），用于加速GPU上刚性和可变形模型的ADF（自适应距离场）的构建。我们的方法基于BVH，我们使用 该BVH生成基于八叉树的ADF。 我们利用连续帧之间的连贯性，并对八叉树的网格点进行排序，以加快计算速度。 我们的方法适用于刚性和变形模型。 我们的基于GPU的算法比基于CPU的算法快20-50倍。 我们的BADF算法可以在NVIDIA GTX GeForce 1060上以交互速率构造具有60K三角形的可变形模型的距离场，此外，我们观察到的速度是以前基于GPU的ADF的3倍。
1、研究背景（context）：距离场可以应用到许多的场景中，例如运动规划，物理仿真，几何变换等。但是当前距离场加速算法却不是非常普遍，现有的算法针对大规模物体构建距离场非常耗时，对于可变形物体来说，距离场算法就在时间计算上过度消耗。
2、目的（Objective）：在针对可变形物体和刚体的碰撞中，我们发现对刚体距离场计算耗时过长，因此我们就对算法进行改进，现有的刚体距离场已经可以进行中规模的实时计算。
3、方法（Method）：我们的方法基于BVH，我们使用该BVH生成基于八叉树的ADF。 我们利用连续帧之间的连贯性，并对八叉树的网格点进行排序，以加快计算速度。 我们的方法适用于刚性和变形模型。我们先对每个三角形面片生成Morton Code，然后基于Morton Code对三角形进行排序。同时我们基于Morton Code在GPU上对三角形进行并行的空间划分，构建出三角形所在的空间八叉树。
4、结果（Result & Findings）：BADF算法针对上下帧连续的物体进行了GPU上构造的优化，构造时间快速降低。我们的基于GPU的算法比基于CPU的算法快20-50倍。 我们的BADF算法可以在NVIDIA GTX GeForce 1060上以交互速率构造具有60K三角形的可变形模型的距离场，此外，我们观察到的速度是以前基于GPU的ADF的3倍。目前的构造距离场的速度可以针对中等规模的物体实时构造。
5、结论（Conclusions）：实验结果表明，过去的并行构造八叉树的算法在构造树形结构的时候并行度不高，而且构造了过多的数据结构。因此我们在增加算法并行度的情况下，复用了数据结构，因此就对算法速度有较大的提升。