Gottschalk面向边界盒算法中的数值精度问题

Question

我试图使用戈特沙克氏算法(代码可在这里找到)为三维三角网格创建一个定向包围盒(OBB)。由于我处理的是网格，所以我使用协方差矩阵和特征值分解方法来创建定向包围盒。我已经认识到特征值分解的数值精度会导致错误的OBB计算。

让我们用一个例子来说明这一点。假设我有一个单位立方体网格，由区域0，1中的8个顶点组成。很明显，这个立方体的OBB本身就是。

​

​

如果运行Gottschalk的算法，我将得到一个包围框，如下所示：

​

​

(旋转以获得更好的视图)

​

​

显然，结果是错误的。我已经找到了这个问题的特征值分解。因为I处理的是一个单元立方体，所以轴必须是单元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

在深入挖掘之后，我看到了这个相关的问题。基本上，似乎你不能期望Gottschalk的算法适用于所有情况。因此，最好采用近似方法。

ApproxMVBB是计算近似定向包围盒的一个很好的库。在与库的作者反复交流之后，我终于能够让它在Windows下编译和工作。下面是我在问题中使用的单位立方体算法输出的截图：

​

​

特别感谢图书馆的作者，感谢他帮助编纂图书馆:)