algorithm - 从许多 3D 平面中找到 AABB - 形成一个凸包

Question

我有一些 3D 平面信息。当所有平面连接在一起时，它将形成一个 3D 凸包。

这是一个输入示例。
每个 3D 平面由平面上的一个点及其法线表示。
所有法线都指向内部：-

- (-1,0,0)              with normal = (1,0,0)
- ( 1,0,0)              with normal = (-1,0,0)
- (0,-1,0)              with normal = (0,1,0)
- (0,1,0)               with normal = (0,-1,0)
- (0,0,-1)              with normal = (0,0,1)
- (0,0,1)               with normal = (0,0,-1)
- (0.142,-7.18,10.12)   with normal = (0.001,0.31,-0.95) 
- note: some planars can be redundant (contribute nothing) e.g. the last one

问题：如何从中计算AABB？
上述示例的解决方案是((-1,-1,-1),(1,1,1)).

（起初，我想要质心，但我意识到这是一个 Hard 问题。AABB
对我来说应该足够好了。）

我糟糕的解决方案是使用构造实体几何找到所有船体顶点， 然后对它们执行 MIN 和 MAX，但性能太差了。

在实际情况下，我想在两个凸包重叠时找到 3D 包的中心点。
此信息可用于物理引擎中更准确的碰撞响应。

Answer 1

这是线性规划的经典问题。给定一组线性不等式（在您的情况下由平面表示，例如 ax+by+cz+d>=0）和一个线性函数（例如 f(x,y,z) =x)，找到一个在满足所有不等式的同时最小化函数的点。AABB 是 6 个此类问题的解，对于函数 x、-x、y、-y、z 和 -z。

有几种方法可以解决这个问题，最著名的是单纯形算法，以及许多现成的库（包括一些利用 GPU 的库）。