Масштабирование Произвольно ориентированных и размерных 3D-боксов для силы пересечения

Question

У меня есть набор 3D-боксов с произвольными размерами, переводами и поворотами. Мне нужно заставить блоки не пересекаться, масштабируя их по одной константе по их 3 компонентам измерения.

В данный момент я делаю это итеративно, проверяя пересечение, а затем итеративно уменьшая масштаб до тех пор, пока пересечения не будет. Однако это занимает слишком много времени, и мне нужно делать это много раз.

Кто-нибудь знает способ найти нужное мне масштабирование за один удар? Приблизительные решения приветствуются.

Большое спасибо всем.

Rob.

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>| &gt <i>&epsilon;</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>