algorithm - 缩放任意方向和尺寸的 3D 框，以实现强制无交叉

Question

我有一组具有任意尺寸、平移和旋转的 3D 框。我需要通过在它们的 3 维分量上按单个常数缩放它们来强制盒子不相交。

目前，我正在通过检查交叉点来迭代地执行此操作，然后迭代地减小缩放比例，直到没有交叉点为止。然而，这需要很长时间才能运行，我需要做很多次。

有没有人知道一种方法可以在一次点击中找到我需要的缩放比例。近似的解决方案是最受欢迎的。

非常感谢大家。

抢。

Answer 1

您将需要执行某种搜索，除非您有关于可以利用的框的其他信息。但是，在一般情况下，您可以对搜索进行二值化，这将比使用线性搜索更快地迭代地使您更接近可接受的答案。

为此，请定义一个您满意的容差 ε 并使用类似以下的内容：

lower_bound <- 0
upper_bound <- 1

while (scaling with upper_bound results in no collisions)
    lower_bound <- upper_bound
    upper_bound <- 2 * upper_bound

while (|upper_bound - lower_bound| > ε)
    mid_point <- (upper_bound + lower_bound) / 2
    if (scaling with mid_point results in collisions)
        upper_bound <- mid_point
    else
        lower_bound <- mid_point

return lower_bound