Mise à l'échelle Boîtes 3D orientées et dimensionnées arbitrairement pour ne pas forcer l'intersection

Question

J'ai un ensemble de boîtes 3D avec des dimensions, des translations et des rotations arbitraires. J'ai besoin de forcer les boîtes à ne pas se croiser en les mettant à l'échelle par une seule constante sur leurs composantes en 3 dimensions.

Pour l'instant je le fais itérativement en vérifiant l'intersection et en réduisant itérativement la mise à l'échelle jusqu'à ce qu'il n'y ait plus d'intersection. Cependant, cela prend trop de temps à courir, et je dois le faire beaucoup de fois.

Est-ce que quelqu'un connaît un moyen de trouver la mise à l'échelle dont j'ai besoin en un seul coup. Les solutions approximatives sont les bienvenues.

Un grand merci à tous.

Rob.

Answer 1

Vous devrez effectuer une sorte de recherche à moins d'avoir des informations supplémentaires sur les boîtes que vous pouvez exploiter. Dans le cas général, vous pouvez toutefois binariser la recherche, qui vous rapproche itérativement d'une réponse acceptable plus rapidement que d'une recherche linéaire.

Pour ce faire, définissez une tolérance & epsilon; que vous êtes satisfait et utilisez quelque chose comme:

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