找到两个重叠长方体的共享体积

Question

找到两个重叠立方体对象占用的共享空间的最有效方法是什么？

我不一定在寻找源代码,只是关于如何解决的一般想法.

为简化起见,算法不必考虑旋转的立方体.

Answer 1

两个非旋转立方体的重叠仍然是一个"盒子".如果框A的两个角点是(x,y,z)和(x',y',z')(x'> x,y'> y,z'> z),则框B的两个角点是(a,b,c)和(a',b',c')(a'> a,b'> b,c'> c)然后重叠的体积是

max(min(a',x')-max(a,x),0)
* max(min(b',y')-max(b,y),0)
* max(min(c',z')-max(c,z),0)

如何阅读公式:

重叠在X轴上以两个坐标x和a的最大值开始,并且以'和x'的最小值结束.如果'<x(即a <a'<x <x')则没有重叠,发生的是max(a,x)= x> min(a',x')= a',所以区别变为负数且体积为零(因此外部最大(...,0))项.这同样适用于其他两个轴.

Answer 2

计算每个立方体每个维度的最小值/最大值，然后相互测试它们，例如在立方体标记为 1 和 2 的 x 方向上

XminInt;
if ( Xmin1 > Xmax2 )
{
    // no intersection
}
else if ( Xmin1 >= Xmin2 )
{
    // possible cube intersection
    XminInt = Xmin1;
}
else if ( Xmin2 <= Xmax1 )
{
    // possible cube intersection
    XminInt = Xmin2;
}

对 max 执行类似的操作，并对 y 和 z 重复。如果您遇到其中任何一个没有交叉路口的情况，那么您可以提前退出。如果您没有在六个可能的早期退出子句中的任何一个中提前退出，那么您将拥有交集立方体的所有六个定义值，即每个维度的最小值/最大值。

六个早期回报几乎是分离轴方法最简单的例子。由于您的形状是立方体并且轴对齐，因此笛卡尔轴是可能的分离轴。然后，测试就是比较上述最小/最大值的简单问题。

请注意，我已经用 C++ 实现了上述方法并确认它有效。