BepuPhysics2中ConvexHull构建的内存爆炸问题分析与解决方案

问题背景

在使用BepuPhysics2物理引擎时，开发人员遇到了一个严重的性能问题：当使用特定输入点集创建ConvexHull(凸包)时，程序会在ConvexHullHelper.cs中的某个循环处卡死，内存消耗以每秒超过1GB的速度增长，最终导致系统冻结。

问题现象

该问题出现在BepuPhysics2 2.5.0-beta.19版本中，当使用一组特定的3D点集创建ConvexHull时触发。问题表现为：

1. 程序执行阻塞在ConvexHullHelper.cs的特定函数/循环中
2. 内存使用量急剧增长，每秒消耗超过1GB
3. 最终导致操作系统冻结

技术分析

经过深入分析，该问题与凸包的面合并(face merging)算法有关。具体原因如下：

1. 面合并机制：BepuPhysics2中的凸包生成器使用面合并算法来检测共享边且法线足够相似的面，并将它们合并。

2. 数值问题：在特定输入情况下，面访问顺序和数值精度问题导致两个法线极其相似的面之间产生振荡。这些面共享顶点但不共享检测到的边，尽管它们生成了能够相互发现的搜索方向。

3. 循环问题：由于每个新面不会排除任何顶点(所有顶点都在2D面凸包的外部)，算法会不断重新发现相同的面并删除之前存在的面。

4. 内存爆炸：由于删除操作被延迟执行(假设不会有数百万步操作)，导致内存使用量持续增长而无法释放。

解决方案探讨

针对这个问题，开发者提出了几种潜在的解决方案：

1. 共享顶点面检查：检查所有共享顶点的面，而不仅仅是共享边的面。

2. 法线暴力测试：不考虑连通性，对所有面法线进行暴力测试。

3. 平面偏移测试：对所有新面中的点与现有平面进行偏移测试，但这与初始面构建过程类似。

4. 非数值干预：引入某种形式的非数值干预来保证不会发生内存爆炸。

最终倾向的解决方案方向是：

• 在共面性测试阈值中加入边缘距离项，降低合并频率
• 引入暴力法线合并
• 仅在检测到循环时执行特定操作

具体实现方案

一个可行的非数值干预方案是：

1. 对于每个新候选面，查找具有两个或更多共享边的现有面(这些面至少部分冗余)
2. 如果新面是现有面的子集，则丢弃它不做任何操作(通过不重新生成相同的搜索方向来避免循环)
3. 如果新面有其他顶点，则合并这些面并简化(面中任何新内部顶点将从未来考虑中移除)

这种方案应该能够保证离散单调性，避免无限循环和内存爆炸问题。

问题解决状态

该问题已在开发分支中得到基本修复，但仍需进行最终测试和完善。开发者表示虽然解决时间较长，但已经找到了根本原因并实施了有效的解决方案。

总结

这个案例展示了在物理引擎开发中处理数值精度问题和算法边界条件的重要性。ConvexHull生成作为碰撞检测的基础组件，其稳定性和性能对整个物理引擎至关重要。通过深入分析面合并算法的数值行为并引入适当的干预机制，BepuPhysics2团队成功解决了这个棘手的内存爆炸问题。