computer-science - 什么是 3D 蒙特卡罗集成的巧妙边界框？

Question

对于一个项目，我需要计算 3D 中两个重叠椭球的重叠体积。该方法本身不是问题：我基本上是在边界框中选择随机点并检查它们是否同时在两个椭球体中。

在我对运行时优化程序的永无止境的追求中，更小的边界框显然是有利的。现在，“盒子”是一个以椭球质心之间的中点为中心的球体，其直径对应于最长的椭球轴。这完全是任意的，我相当肯定重叠体积将始终包含在这个球体中，但我真的很想找到一些方法来优化整个过程。

有没有一些通用的方法来优化包围体？

Answer 1

如果你想坚持蒙特卡洛，这里有另一个想法：

将椭圆体投影到 XZ 平面上以获得 2 个椭圆。计算它们的边界矩形的交集以用作计算的边界矩形。

然后沿着 Y 轴通过边界矩形内的 XZ 平面发射光线。对于每条射线，计算与椭球的交点并计算在两者内部的射线的长度。将此添加到变量“hits_length”中。

椭球相交的体积应近似为：

hits_length/ray_shot * bounding_rectangle_area

同样，您通过对 2D 空间进行采样来计算体积，这应该使其收敛更快。

Answer 2

这可能更像是一个数学问题而不是编程问题，但我认为 2 个椭圆体的交集是一个凸形，所以也许你可以尝试另一种方法而不是蒙特卡洛来处理这样一个表现相对良好的对象。

首先，您需要（以某种方式）在两个椭球内找到一个点。

现在创建一个以该点为中心的立方体，大到足以完全包含两个椭圆体。沿着所有 3 个轴将立方体细分为 8 个大小相等的子立方体（创建八叉树的第一步）。

在此之后，对子多维数据集应用递归。如果一些立体角在两个椭球内而一些不在，则再次细分立方体。此外，如果立方体面的某些区域在椭圆体内而其他区域不在，请再次细分。

重复到所需的递归深度。您可以通过对细分的立方体的体积求和来跟踪计算错误。

现在，这里具有挑战性的操作是解决“如果立方体面的某些区域在两个椭球内”。椭圆体与平面的交点就是椭圆。要检查 6 个立方体面中的每一个，您需要将它们与椭圆体相交，然后如果它们都与立方体面重叠，则将剩余的椭圆彼此相交。幸运的是，对于 2D 椭圆-椭圆重叠测试，您可以更轻松地找到参考...

Monte Carlo 将通过 O(2^n) 的努力为您提供 n 位的准确度，因此例如 24 位需要 1670 万个样本。如果您使用这种分而治之的方法专注于形状表面，您应该只需要 O(2^(n*2/3)) 个样本，即 24 位大约 65,000 个样本。

此外，您对初始边界框大小的担忧也变得无关紧要，因为在初始递归步骤中会迅速删除多余的边界框。

Answer 3

这不是一道数学题，而不是一道CS题吗？您似乎要求的是一个定义两个椭球可能重叠的公式。当然，您打算使用该公式使您的代码更高效，但据我所知，这与核心问题无关。如果您有公式并试图弄清楚如何将其编写为代码，那将是另一回事。也许您应该考虑将其发布到https://math.stackexchange.com/

在我看来，您可以将您的问题重新定义为“定义 3D 空间中 2 个椭圆体之间可能重叠的体积的公式是什么？”，这与计算无关。