Gottschalk 的 Oriented Bounding Box 算法中导致问题的数值精度

Question

我正在尝试使用 Gottschalk's algorithm (code available here) 为 3D 三角形网格创建定向边界框 (OBB)。由于我正在处理网格，因此我使用协方差矩阵和特征值分解方法来创建定向边界框。我已经意识到特征值分解的数值精度会导致错误的 OBB 计算。

让我们用一个例子来阐明这一点。假设我有一个单位立方体网格，由 [0, 1] 范围内的 8 个顶点组成（如下所示）。显然这个立方体的 OBB 就是它自己。

如果我运行 Gottschalk 的算法，我最终会得到如下所示的边界框：

（旋转以获得更好的视图）

显然结果是错误的。我已经追踪到特征值分解的问题。由于我正在处理单位立方体，因此轴必须是单位 x、y 和 z 方向。但是，特征值分解会产生其他方向的轴。错误的结果源于协方差矩阵。我为这个立方体计算的协方差矩阵如下：

Covariance matrix:
|     0.138889  -2.77556E-17         0 |
| -2.77556E-17      0.138889         0 |
|            0             0  0.138889 |

得到的特征向量如下：

Eigenvectors:
| -0.7071         0   -0.7071 |
| -0.7071         0    0.7071 |
|       0    1.0000         0 |

将此矩阵的每一列作为OBB的轴会产生上图所示的错误结果。如果我用零替换协方差矩阵中的超小值，我将得到正确的特征向量和（通过扩展）轴：

Correct eignenvectors:
| 1     0     0 |
| 0     1     0 |
| 0     0     1 |

对于具有更多顶点的对象，这往往不是一个问题。但是，我确实有恰好有 8 个顶点的对象，我需要能够正确计算它们的 OBB。

我应该如何解释这些准确性问题？如何让我的 OBB 算法更健壮？

如果有帮助，我正在用 C# 实现该算法。正在使用 CGAL 计算凸包，使用 Math.NET.

进行特征值分解

Answer 1

经过大量挖掘，我看到了 this related question。基本上，您似乎不能指望 Gottschalk 的算法适用于所有情况。因此，最好使用近似方法。

计算近似定向边界框的一个很好的库是 ApproxMVBB。在与库的作者反复沟通后，我终于能够在 Windows 下编译和工作。以下是我在问题中使用的单位立方体算法输出的屏幕截图：

特别感谢图书馆的作者对图书馆的编译提供的帮助:)

Numerical accuracy causing issues in Gottschalk's Oriented Bounding Box algorithm