¿La forma más sencilla de determinar si dos cajas 3D se cruzan?

Question

Dado

Si se dan dos conjuntos de dos puntos en el espacio 3D (donde se definen como las esquinas de la caja):

Caja1:

P1 = (961.46, 215.15, 1465.44) P2 = (970.02, 214.93, 1481.77)

Matriz de traslación para el recuadro 1:

---

Caja2:

P1 = (1093.52, -499.50, 896.11) P2 = (1093.12, -505.49, 878.68)

Matriz de traslación para el recuadro 2:

---

Lo que busco

¿Cuál es la forma más sencilla de determinar si las dos cajas se cruzan en el espacio o no? Me doy cuenta de que esto puede no ser una pregunta simple, pero la esperanza de alguna orientación al menos.

Por supuesto, las cajas pueden inclinarse en cualquier grado y no siempre tienen el eje alineado. Añadí mi matriz de traslación con la que empecé a establecer las cajas, ya que ésta contiene los dos vectores a los que están orientados los puntos, por si esto es útil.

Answer 1

Suponiendo que las cajas están alineadas con el eje (porque de lo contrario están mal especificadas), digamos que las esquinas de la primera son $$P_1 = (x_1, y_1, z_1)\\ Q_1 = (X_1, Y_1, Z_1)$$ con $x_1 < X_1, y_1 < Y_1, z_1 < Z_1$ y para el segundo $$P_2 = (x_2, y_2, z_2)\\ Q_2 = (X_2, Y_2, Z_2)$$

Entonces la forma de comprobar si hay un solapamiento es esta: Comparar los intervalos $[x_1,X_1]$ y $[x_2, X_2]$ y si no se superponen, no hay intersección. Haz lo mismo para el $y$ intervalos, y el $z$ intervalos.

Si los tres pares de intervalos se solapan, entonces SÍ hay una intersección.

¿Qué quiero decir con "solapamiento"? Quiero decir que hay un número $a$ con $x_1 \le a \le X_1$ y $x_2 \le a \le X_2$ por ejemplo.

Esto se puede comprobar fácilmente verificando sólo los puntos finales: los intervalos se superponen si alguna de estas cuatro condiciones es verdadera: $$x_1 \le x_2 \le X_1 \\ x_1 \le X_2 \le X_1 \\ x_2 \le x_1 \le X_2 \\ x_2 \le X_2 \le X_2$$

Si no se cumple ninguna de esas cuatro, los intervalos no se solapan.

Para su caso particular, $$P_1 = (961.46, 215.15, 1465.44) \\ Q_1 = (970.02, 214.93, 1481.77)$$ y $$P_2 = (1093.52, -499.50, 896.11)\\ Q_2 = (1093.12, -505.49, 878.68)$$ vemos que los intervalos x no se superponen, y por lo tanto las cajas no se superponen. Ni siquiera tenemos que mirar el $y$ s y $z$ s (aunque es particularmente simple, porque el $y$ tampoco se superponen, y el $z$ ¡s tampoco se superponen! Estas cajas son lo más disjuntas posible.

Answer 2

Para las cajas arbitrarias, querrás hacer primero los casos fáciles.

Para cada caja, calcula la ubicación de su centroide (puedes hacerlo promediando las coordenadas de las ocho esquinas), digamos $\vec{c}$ y $\vec{C}$ . Calcule también la distancia del centroide a las esquinas más cercanas y más lejanas, digamos $r_{min}$ y $r_{max}$ para la caja con centroide en $\vec{c}$ y $R_{min}$ y $R_{max}$ para la caja con centroide en $\vec{C}$ .

Si $\left(\vec{c} - \vec{C}\right)\cdot\left(\vec{c} - \vec{C}\right) \lt (r_{min} + R_{min})^2$ Las cajas deben intersecarse, porque sus esferas inscritas se intersecan.

Si $\left(\vec{c} - \vec{C}\right)\cdot\left(\vec{c} - \vec{C}\right) \gt (r_{max} + R_{max})^2$ Las cajas no se pueden cruzar, porque sus esferas circunscritas no se cruzan.

De lo contrario, hay que comprobar si una caja contiene a la otra, o si las dos cajas se cruzan.

Hay muchas maneras de implementar una prueba de colisión caja-caja, pero lamentablemente no tengo idea de cuál es "más simple" . Probablemente depende de muchos factores, como si las cajas tienden a girar o a permanecer en la misma orientación, si sus tamaños relativos cambian, etc. Hasta ahora no he necesitado una prueba de intersección entre cajas no alineadas con el eje, porque las esferas son mucho más fáciles y rápidas.

El hecho de que el OP busque la prueba de intersección caja-caja más sencilla me indica un problema X-Y. Las cajas no alineadas con el eje son una mala aproximación para los objetos, porque son muy caras computacionalmente en comparación con las esferas (o grupos de esferas). Los otros casos de uso que se me ocurren son algo así como los motores de física simples (cajas que colisionan), donde realmente se quiere encontrar el punto de colisión, la línea o el plano, y no sólo probar si hay una colisión o no.