En éste capítulo abordaremos el tema de los volúmenes envolventes, un aspecto muy importante en el desarrollo de videojuegos.
4.1: Volúmenes envolventes
En un videojuego, ya sea 3d o 2d, uno de los problemas más importantes es saber cuando y como colisionan dos objetos, además de reaccionar apropiadamente a dicha colisión. Ésto es lo que se denomina "Gestión de colisiones" , un tema muy estudiado y desarrollado.
La gestión de colisiones normalmente se divide en tres fases: Detección de colisión, cálculo de las características de la colisión, y por último la respuesta a la colisión. Aunque ya desarrollaremos más detenidamente éste tema en capítulos posteriores, la primera fase integra una serie de elementos que nos son de gran utilidad: Los volúmenes envolventes.
Pero, ¿Que es un volumen envolvente?
Un volumen envolvente, también llamados recubrimientos simpliciales, es una representación más simple de un objeto, ya sea un polígono en 2d, o un poliedro en 3d. Su utilidad consiste en reducir la complejidad de la detección de colisión entre diferentes objetos.
Veamos un ejemplo. Imaginemos que tenemos dos pentágonos en el plano, y queremos saber si colisionan o no:
Alguno me dirá: "Pues colisionan, lo estoy viendo". Ya, pero recordad que el ordenador no ve.
El problema es bastante más complejo de lo que parece, pero existen muchas maneras de solucionarlo.
Un método sería intentar calcular los puntos de intersección entre los polígonos. Si existe alguno, significa que hay colisión. Pero el problema es que tendríamos que calcular la intersección (si las hay) de m*n rectas, siendo m y n el número de lados de cada polígono respectivamente. Descartado.
Otro método consistiría en averiguar si algún vértice de uno de los polígonos está contenido en el otro y viceversa. Como en el caso anterior, queda descartado, ya que igualmente tendríamos que hacer m+n tests, además que, como veremos más adelante; el test de inclusión de un punto en un polígono suele ser bastante costoso.
Así que ya se ve la complejidad del asunto. Pensemos en un caso más extremo, una escenario en el que sabemos perfectamente que cada polígono está en una punta del mapa. ¿Para que hacer todos éstos cálculos?
Y aquí es donde entran en juego los volúmenes envolventes. La idea es recubrir la figura por otra mucho más simple (Idealmente con un test de colisión más simple), y efectuar primero el test entre las nuevas figuras. En caso de que se detecte colisión entre los volúmenes envolventes, pasar a test más precisos (y costosos) que involucren a las figuras originales.
Éste tipo de metodología es la que se suele usar en la primera fase de la gestión de colisiones, dividiendo la fase de detección en dos subfases, denominadas "Fase Ancha" y "Fase Estrecha". En la fase ancha, descartas mediante un algoritmo sencillo todos los casos extremos, y solo los que no la pasen continuarán por la fase estrecha, que constará de un test mucho más preciso que la anterior.
4.2: Clasificación de volúmenes envolventes
En la actualidad, se han desarrollado diferentes tipos de volúmenes envolventes, cada uno con sus ventajas y desventajas. Los dos más importantes son:
- AABB (Axis Aligned Bounding Box): Como su nombre indica, consiste en una caja rectangular alineada con los ejes de coordenadas. Su principal ventaja es que el test de colisión entre ellos es muy sencillo. El problema es que no suele adaptarse muy bien a las figuras. Ideal para la fase ancha.
 |
| AABB |
- OBB (Oriented Bounding Box): Es un caso especial de AABB que está alineado con el sistema de coordenadas del objeto. Aunque mucho más fiel que el AABB, obtener los ejes de coordenadas óptimos no es facil. Además, el test de colisión es bastante más costoso que el de los AABB.
 |
| OBB |
4.3: Implementación de AABBs
La implementación mas sencilla de AABB consiste en guardar los datos sobre la posición y dimensiones del rectámgulo:
De ésta manera, el espacio del AABB queda definido por:
MinX = Coordenadas.X
MinY = Coordenadas.Y
MaxX = Coordenadas.X + Ancho
MaxY = Coordenadas.Y + Largo
Y las esquinas se definen como:
EsquinaSuperiorIzquierda = (MinX,MinY)*
EsquinaSuperiorDerecha = (MaxX,MinY)
EsquinaInferiorDerecha = (MaxX,MaxY)
EsquinaInferiorIzquierda = (MinX,MaxY)
*Como se observa, la esquina superior izquierda es el origen de coordenadas del AABB. En mis implementaciones suelo tomar éste criterio, ya que la mayoría de los sistemas de gráficos por ordenador tienen el origen de coordenadas en la esquina superior izquierda, además de aumentar la coordenada Y hacia abajo.
4.3.2: Cálculo de AABB dado un conjunto de puntos
Calcular el AABB de un conjunto de puntos es algo bastante sencillo: Basta con calcular los cuatro puntos extremos (Mas arriba, más abajo, más a la derecha, y más a la izquierda) del conjunto de puntos, y utilizar sus coordenadas como base para el AABB. Es decir si tenemos los cuatro puntos extremos, llamados Norte, Sur, Este, Oeste, los datos del AABB serán:
Coordenadas = (Oeste.X , Norte.Y)*
Dimensiones = ( |Este.X - Oeste.X| , |Sur.Y - Norte.Y| )
*Recordad que el origen está en la esquina superior izquierda
4.3.3: Test de pertenencia Punto-AABB
Con éstos datos, el test de pertenencia de un punto a un AABB es muy sencillo. Lo único que hay que hacer es examinar si el punto pertenece al espacio definido por los extremos del AABB, es decir, si el punto está entre MinX y MaxX, además de MinY y MaxY:
Pertenece(P) = P.X >= MinX y P.X <= MaxX y P.Y >= MinY y P.Y <= MaxY
4.3.4: Test de colisión entre AABBs
El test de colisión entre dos AABBs se puede abordar de dos maneras:
- La primera, basada en el teorema de los ejes separados, consiste en evaluar si los intervalos (MinX,MaxX) y (MinY,MaxY) de ambos AABB se superponen:
SuperposiciónX = No ( MaxX' < MinX o MinX' > MaxX)
SuperposiciónY = No ( MaxY' < MinY o MinY' > MaxY)
Aplicando las leyes de Morgan:
SuperposiciónX = MaxX' >= MinX y MinX' <= MaxX
SuperposiciónY = MaxY' >= MinY y MinY' <= MaxY
Y finalmente:
Colisión = SuperposiciónX y SuperposiciónY
- El segundo método consiste en transformar el test de colisión en uno de pertenencia Punto-AABB. ¿Como? Veamos:
Lo que tenemos que hacer es generar un nuevo AABB que contenga a los AABBs originales, de manera que si la esquina origen del segundo (Las coordenadas del AABB) pertenece al nuevo AABB, los originales colisionan. Las características de éste nuevo AABB son:
Coordenadas = (CoordenadasA.X - AnchoB , CoordenadasA.Y - LargoB)
Dimensiones = (AnchoA + AnchoB , LargoA + LargoB)
De manera que el test de colisión se transforma en:
Colisión = Pertenece (NuevoAABB , CoordenadasB)
4.3.5: Test colisión recta-AABB:
Éste test es muy util para realizar una fase ancha en un algoritmo de raycasting. El método que voy a explicar se me ocurrió en un momento de inspiración, y me parece mucho mas sencillo que calcular las intersecciones de los lados del AABB:
La idea es muy sencilla: Si todas las esquinas del AABB están al mismo lado de la recta, la recta no lo atraviesa, y si lo atraviesa en caso contrario. Y como vimos en el capítulo anterior, saber la posición relativa de un punto respecto de una recta es muy sencillo.
Como recomendación, no calculéis las cuatro posiciones relativas y luego las comparéis, ya que, aunque el cálculo sea sencillo, ahorramos algo si vamos comparando paso a paso:
Public Function Pertenece(ByRef Recta As Recta2D) As Boolean
Dim Posicion As Double = Recta.SignoPosicionRelativa(EsquinaSuperiorIzquierda)
Dim P As Double
P = Recta.SignoPosicionRelativa(EsquinaSuperiorDerecha)
If P = Posicion Then
P = Recta.SignoPosicionRelativa(EsquinaInferiorDerecha)
If P = Posicion Then
P = Recta.SignoPosicionRelativa(EsquinaInferiorIzquierda)
If P = Posicion Then
Return False
Else
Return True
End If
Else
Return True
End If
Else
Return True
End If
End Function
4.4: Implementación de OBBs
La implementación de OBBs es algo más complicada que la de los AABBs. Recordemos que un OBB no es más que un AABB definido en el sistema de coordenadas del objeto. Entonces lo primero que tendremos que hacer es encontrar dicho sistema de coordenadas. Es decir, tenemos que calcular la transformación que nos lleve desde el sistema universal de referencia (SUR) hasta el sistema del objeto.
Para ello, tenemos que encontrar los ejes de coordenadas óptimos para el objeto. La manera correcta de hacerlo es mediante el cálculo de la matriz de covarianza del conjunto de puntos del objeto, y de ésta sacar los ejes de coordenadas. El problema es que ésto implica calcular los autovectores de la matriz, un proceso que suele incluir el cálculo de raices de polinomios (Algo bastante complejo). Para solucionar ésto, existen diversos algoritmos que permiten calcular los autovectores sin utilizar la factorización de polinomios. Pero también son bastante complicados.
Voy a exponer un método bastante sencillo para encontrar unos ejes de coordenadas que, aunque no siempre son óptimos, suelen valer:
- Primero, necesitamos conocer el baricentro del objeto, algo trivial, es la media de todos sus puntos.
- Segundo, averiguamos cual es el punto más alejado del centro.
Y ya está, el eje que nos interesa es la recta que une el centro con el punto más lejano.
Ahora solo nos falta calcular la transformación desde el mundo al objeto.En 2d es facil: Ésta será una rotación que convierta una recta en dirección del ejeX en el eje que hemos calculado, seguido de una traslación desde el origen hasta el centro del objeto.
En 3d es algo más complicado, ya que implica la rotación mediante cuaterniones, que veremos en temas posteriores.
Una vez hecho ésto, solo falta calcular el AABB en el nuevo sistema de coordenadas, con los métodos que vimos en el apartado anterior.
Aquí podéis ver mi implementación en acción: OBBs VB.NET
4.4.2: Test de pertenencia Punto-OBB:
Como hemos definido el OBB como un AABB con su propio sistema de coordenadas, solo tenemos que transformar el punto para que esté definido en dicho sistema de coordenadas (Mediante la matriz de transformación que calculamos antes). Una vez hecho ésto, ejecutamos el test de pertenencia Punto-AABB.
4.4.3: Test de colisión entre OBBs
La mayoría de la gente implementa éste test mediante el teorema de los ejes separados, o SAT, por sus siglas en inglés Separating Axis Theorem. En este teorema se define el eje de separación entre dos objetos convexos como aquella recta tal que las proyecciones ortogonales de los objetos sobre ella no se solapan. Nuestras OBBs no colisionarán entre sí, si nuestro algoritmo consigue encontrar un eje de separación entre ellas. En el siguiente dibujo se puede ver la representación gráfica de lo que acabamos de comentar en un ejemplo en dos dimensiones:
El problema que tienen los algoritmos basados en éste teorema es que para asegurar la fiabilidad de los cálculos, hay que probar muchos rectas de proyección.
Otra forma de hacerlo es utilizando el test de colisión entre AABBs. Dados dos OBBs, se calcula el AABB de uno de ellos en el sistema de coordenadas del otro y viceversa. Si ambos test detectan colisión, significa que hay colisión:
4.4.4: Test de colisión recta-OBB
Al igual que el test de inclusión de un punto, basta transformar la recta al sistema de coordenadas del OBB, y utilizar el test del AABB. Para aplicar una transformación a una recta, solo hay que aplicar la transformación a dos puntos de la recta y volverla a generar con los nuevos puntos.
Conclusión
En éste capítulo hemos desarrollado la implementación de los volúmenes envolventes más utilizados en el desarrollo de videojuegos. En el próximo capítulo mostraremos un ejemplo práctico de todo lo que hemos aprendido hasta ahora: La implementación de un Arcanoid
Consideraciones sobre implementación:
Todos los algoritmos explicados en éste capítulo son válidos tanto para 2d como para 3d, con la diferencia de utilizar una dimensión más o menos. Como expliqué en el apartado 4.4, el cálculo de OBBs en 3d la veremos más adelante, cuando veamos rotaciones en 3d.
