algorithm - 缩放任意方向和尺寸的 3D 框以强制不相交

Question

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

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

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

非常感谢大家。

罗布。

Answer 1

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

为此，请定义您满意的公差 ε 并使用如下内容:

<i>lower_bound</i> <- 0
<i>upper_bound</i> <- 1

<b>while</b> (scaling with <i>upper_bound</i> results in no collisions)
    <i>lower_bound</i> <- <i>upper_bound</i>
    <i>upper_bound</i> <- 2 * <i>upper_bound</i>

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

<b>return</b> <i>lower_bound</i>