将体素/数据封装在框中的算法

Question

我有一个有 8 个可变角的立方体。我还有一个体素数据集，它的所有维度都具有相同的集合大小。

有谁知道一种算法，可以在立方体仍封装所有体素的情况下找到立方体的最小可能区域(以及所有 8 个角位置)？

最好是不太重的算法。

Answer 1

如果你的意思是一个长方体——一个有 6 个矩形面的 3D 形状——并且如果这些面必须与你的体素数据的轴对齐，那么这只是 (3D) 边界盒子。您需要做的就是计算数据集中每个体素的 x、y 和 z 坐标的最小值和最大值。将这 3 个维度的 {minimum, maximum} 的所有 8 种组合都给你 8 个角的坐标，尽管你通常只记录两个点 (min_x, min_y, min_z) 和 (max_x, max_y, max_z) , 完整地描述了形状。

如果形状必须是立方体(即所有维度都相等)，那么您必须将 2 个较小维度的大小增加到最大维度的大小。

如果您正在寻找可用于有效相交测试(使用点、线、平面或其他边界体积)的形状来限制体积，那么另一个不错的选择是球体。两个球体之间的交集测试特别简单:你需要做的就是检查它们的中心之间的距离是否超过它们的半径之和。