Scaling Arbitrary oriented and dimensioned 3D boxes for force no intersection

I have a set of 3D boxes with arbitrary dimensions, translations and rotations. I need to force the boxes not to intersect by scaling them by a single constant over their 3 dimension components.

At the moment I am doing this iteratively by checking for intersection and then reducing the scaling itera开发者_如何学Gotively until there is no intersection. However this is taking too long to run, and I need to do it a lot of times.

Does anybody know of a way to find the scaling I need in a single hit. Approximate solutions are most welcome.

Many thanks to all.

Rob.

You will need to perform some sort of search unless you have additional information about the boxes that you're able to exploit. In the general case, though, you could binarize the search, which will iteratively get you closer to an acceptable answer more quickly than using a linear search.

To do this, define a tolerance ε that you're satisfied with and use something like the following:

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