基于扫掠球量的快速距离计算

Fast Distance Computation Based on Swept Sphere Volumes

引入扫掠球量作为包围量。扫掠球是一系列相对于核基本形状以某一等距向外扩展而形成的包围量。核基本形状包括点,线段和矩形。这些包围量可以提供对被包围物体的不同的紧密性。基于这些包围量,建立混合层次并且采用有效而准确的算法可以计算两物体之间的距离,并可通过在返回值中引入相对误差来进一步提高算法效率。

A family of bounding volumes called swept sphere volumes is introduced. It corresponds to a core primitive shape grown outward by some offset. The core primitives include point, line and rectangle. This family of bounding volumes provides varying tightness to the underlying geometry, furthermore, hybrid hierarchies are built and an efficient and accurate algorithm to perform distance computation using those volumes is provided. The efficiency of the algorithm can be further improved by accepting a relative error in the returned result.