Capitulo 3: Geometría básica. Algebra

Introducción:

En éste capítulo, abordaremos los aspectos básicos de geometría necesarios para entender los capítulos posteriores. Nótese que no estoy dando todas las explicaciones necesarias, solo es un repaso por encima, ya que mi objetivo no es dar una clase de geometría y álgebra, sino exponer sus utilidades y uso en ciertos aspectos.

3.1: Rectas y planos:

Los elementos geométricos más básicos, además del punto y el vector, son la recta y el plano.

La recta es un elemento muy importante en los vidojuegos, ya sea para seleccionar un objeto en un entorno 3d mediante algún algoritmo de raycasting, o en el algoritmo de raytracing (Aunque ésto hoy en día solo se utilice en películas, ya queda poco para que veamos raytracing en nuestras consolas; o eso parece vistas las nuevas pruebas de NVIDIA). Pero no nos vallamos por las ramas. 

Una recta en 2d está definida por una ecuación general del tipo:

Ax + By + C = 0

Es decir, la reta está formada por todos los puntos que satisfacen dicha ecuación.

Pero además, una propiedad a tener en cuenta es que para aquellos puntos que no pertenezcan a la recta, el signo del resultado de la ecuación depende de en que lado de la recta se sitúen. Ésto nos permite clasificar los puntos del plano fácilmente (Muy util para algoritmos de recorte de polígonos, como veremos más adelante)

El plano, tiene una ecuación general muy similar:

Ax + By + Cz + D = 0

Y al igual que pasaba con la recta en 2d, el signo de los puntos no pertenecientes al plano dependerá de su posición respecto al plano.

3.2: Intersecciones

Utilizando éstas ecuaciones, el cálculo de intersecciones es muy simple. Por ejemplo, en el caso de una recta 2d, la intersección de dos rectas r, s definidas como:

r: Ax + By + C = 0

s: A'x + B'y + C' = 0

No es más que la solución al sistema formado por las dos ecuaciones.

Con dos planos, exactamente igual:

alfa: Ax + By + Cz + D = 0

beta: A'x + B'y + C'z + D = 0

Y la intersección de los dos planos alfa y beta será una recta en 3d. Por ese motivo, las rectas en 3d se definen de manera general como el corte de dos planos. Así, por ejemplo, si quieres calcular el punto de intersección entre una recta y un plano, no tienes más que calcular el sistema formado por los tres planos.

3.3: Posiciones relativas:

Además de la posición relativa entre una recta/plano y un punto,a veces es necesario conocer la posición relativa entre dos rectas, dos planos, o una recta y un plano. Por ejemplo, antes de calcular las intersecciones, ya que en determinados casos puede que no haya intersección. Las posiciones relativas entre éstos elementos se obtiene discutiendo el sistema de ecuaciones de la intersección. 

En el caso recta-recta: Si sale compatible determinado, las rectas se cortan, y la solución es el punto de intersección.

En el caso plano-plano: Si el sistema sale compatible indeterminado, el sistema tiene infinitas soluciones, y por tanto, esos dos planos definen una recta.

El caso plano-recta: Si el sistema es compatible determinado, como en el caso de recta-recta, la solución es el punto de intersección. Pero si es compatible indeterminado, significa que hay infinitas soluciones, es decir, que la recta está contenida en el plano.

Conclusión:

En éste capítulo hemos resumido los aspectos básicos necesarios para desarrollar algoritmos más avanzados que desarrollaremos en el siguiente capítulo, como son la implementación de segmentos, polígonos, o diferentes tipos de volúmenes envolventes.


Consideraciones sobre implementación:

Muchas veces, se define la recta mediante su ecuación paramétrica, ya que el cálculo de intersecciones es mas sencillo (es una ecuación de una única variable). Éste tema lo dejo a elección de cada uno. En mi caso, en los algoritmos geométricos que he implementado suelo utilizar muchas veces la posición relativa de los puntos, así que me conviene usar la ecuación general.

Como se ha visto, el cálculo de intersecciones se basa fundamentalmente en la resolución de sistemas de ecuaciones.

Existen diversos métodos para el cálculo y discusión de sistemas de ecuaciones. Pero si se examinan éstos a fondo. los más fáciles de implementar son aquellos que están basados en el teorema de Rouché-Frobenius, ya que éstos se reducen básicamente al cálculo de rango de matrices.
Normalmente, en los institutos se enseña a realizar éste cálculo buscando la dimensión del mayor menor no nulo, pero implementar éste tipo de algoritmo es complicado, ya que es el tipo de cálculo en el que una persona se basa en la intuición. (Y como cualquiera que se haya metido en programación de IA sabrá, generar una heurística que simule intuición es algo prácticamente imposible).

Así que mi recomendación es calcular el rango mediante el método de Gauss (muy fácil de implementar), y calcular la solución mediante la regla de Cramer (También fácil)