假设边界球的中心也是边界框的中心是否有效?

计算科学 计算几何 几何学
2021-12-26 05:58:06

计算点集的轴对齐边界框是微不足道的。当中心已知时,计算点集的边界球也很简单据我所知,计算边界球的中心并不是那么简单。所以我的计划是通过边界框的中心来近似边界球的中心。

是否存在这种方法会导致愚蠢结果的情况?

3个回答

《实时碰撞检测》一书表明,AABB 质心是边界球体的近似值。事实上,AABB 质心通常比点的质心要准确得多。

快速浏览本书(第 4 章)中提到的技术:

  • AABB的质心:又快又脏,不可怕
  • 最大方差方向的数据中心(协方差矩阵的特征值/特征向量)-> 这种方法似乎可以泛化以找到数据的良好边界椭圆体,对于高纵横比点集可能更好
  • 随机 O(N) 算法(Welzl 算法)维护一组必须位于最小球体边界上的点。CGAL 中提供了一个实现。

这本书是为视频游戏程序员写的,所以强调要“足够好”,而不是一定要正确。在这种情况下,这些包围体的典型用例是用于碰撞检测。由于目标是最小化进行碰撞检测的总时间,因此具有计算成本可能很高的精确边界体积会适得其反,因此强调近似方法。

这是本书的官方链接,但互联网上也有其他“不太官方”的链接......

http://www.sciencedirect.com/science/book/9781558607323

我几乎可以肯定,文献综述会找到一个准确的算法。但我也建议从凸包的质心开始——这很容易计算。

副手,我认为你的点分布越倾斜,这个近似值就越差。例如,说在 2D 中你有一个点[x,y]=(0,0), 和沿垂直线的点(1,1)(1,1),边界框将是(0,1)×(1,1)质心在(0.5,0),但边界圆的质心将在(1,0).