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

Question

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

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

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

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

Rob.

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 

returnlower_bound