从许多 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)).

(一开始我想要质心，后来发现that is a Hard problem。
AABB 对我来说应该足够好了。 )

我糟糕的解决方案 是使用Constructive solid geometry 找到所有的外壳顶点，然后对它们进行 MIN 和 MAX，但是性能太差了。

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

Answer 1

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

有多种解决此问题的方法，最著名的是单纯形算法和许多 ready-made 库（包括一些利用 GPU 的库）。

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

Find AABB from many 3D planes - that form a convex hull

language-agnostic

algorithm

convex-polygon