Масштабирование 3D-боксов с произвольной ориентацией и размерами для принудительного отсутствия пересечения

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

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

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

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

Роб.


algorithm math computational-geometry collision-detection
person B_o_b    schedule 19.08.2010    source источник

Ответы (1)


arrow_upward
0
arrow_downward

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

Для этого определите допуск, который вас устраивает, и используйте что-то вроде следующего:

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
person andand    schedule 19.08.2010