Neptalium

Hay pocas cosas tan útiles en programación como la interpolación, de hecho son tantos los casos en los que resulta útil (o incluso esencial) que ni me voy a molestar en mencionarlos.
Directamente dejo aqui un par de ejemplos, el primero es una función de interpolación lineal:

Esta es una función de interpolación cuadrática (“Easy In”):

Y por último una interpolación cuadrática (“Easy In-Out”):

En los tres casos se fija el rango a interpolar con los parámetros inicio y fin, y con el parámetro tiempo se indica el punto de interpolación (por supuesto se asume que tiempo tendrá un valor comprendido entre 0.0 y 1.0).

En programación 3D en tiempo real es imprescindible optimizar todo lo posible, y la inversión de matrices homogéneas es uno de los casos complejos (aparentemente) en donde se puede conseguir una excelente optimización siguiendo las reglas del álgebra matricial y conociendo cómo ha sido generada la matriz a invertir (conociendo su estructura).

Nota: En este post usaré el formato fila (pre-multiplicación) para representar las matrices y la formulación.

Vamos a ver primero la inversión aislada de los tres casos básicos, matriz de rotación, escala y traslación:

Si la matriz de rotación R es ortogonal (si sus tres ejes son perpendiculares entre si), entonces su inversa es simplemente su traspuesta:





La inversa de una matriz de escala S es muy sencilla:





Y la inversa de una matriz de traslación T también es muy simple:





Ahora veamos un caso más práctico, cómo invertir una matriz de transformación RT (es decir, una matriz que primero realiza una rotación y luego una traslación). Es imprescindible saber siempre el orden de las transformaciones contenidas en una matriz para poder optimizar el cálculo de su inversa ya que vamos a optimizar los cálculos por partes y siguiendo una regla muy simple; la inversa del producto de dos matrices es igual al producto invertido de las inversas de dichas matrices:

Con esta regla tan simple podemos invertir una matriz RT multiplicando la inversa de la traslación por la inversa de la rotación: y como ya sabemos que la inversa de una matriz ortogonal es su traspuesta la fórmula final será:

Con lápiz y papel calculamos la estructura final de la matriz inversa de una transformación RT:



Para invertir una matriz TR es incluso más simple:



Ahora veremos cómo invertir matrices que incluyen transformaciones de escala isométrica (que significa que se ha aplicado la misma escala a los tres ejes), empecemos por la clásica transformación SRT (donde primero se escala, luego se rota y finalmente se traslada). Como siempre su inversa será:

Volvemos a coger el lápiz y calculamos:



La misma inversa SRT pero de una matriz con escalado anisométrico (escalado no idéntico en los tres ejes) sería:



Para terminar veremos la inversa de una matriz que represente una transformación RTS. La inversa con escalado isométrico es:



Y la inversa de una matriz RTS con escala anisométrica es:



Si teneis dificultades para ver alguna de las matrices pulsad con el botón derecho del ratón sobre ella y elegid Abrir/Ver imagen.

Desde los inicios de OpenGL existe una confusión bastante importante sobre cómo administra internamente las matrices. Unos piensan que las almacena en formato fila y otros piensan que lo hace en formato columna. Pues lo cierto es que ni una cosa ni la otra!
OpenGL almacena las matrices en un array unidimensional de 16 elementos y es el programador quien decide cómo prefiere interpretarlas.

Quedará más claro con un ejemplo:

Con el código anterior leemos la matriz actual MODELVIEW y la almacenamos en el array m.

¿Y cómo están estructurados los elementos de la matriz? Pues muy sencillo, secuencialmente:



Ahora el programador puede decidir interpretarlo como una matriz de tipo columna:



O como una matriz de tipo fila:



Matemáticamente es indiferente cómo prefieras interpretarlas, pero recuerda que si utilizas el formato columna debes realizar post-multiplicaciones, y si usas el formato fila pre-multiplicaciones.

Supongamos que tienes una matriz que representa una rotación y la matriz que realiza una traslación, y quieres combinarlas en una matriz , de forma que la matriz de trasformación resultante realice primero la rotación y luego la traslación. Si usas el formato fila tendrás que hacer una pre-multiplicación: (Esto se lee: la matriz R pre-multiplica a la matriz T).
Pero si usas el formato columna el orden se invierte ya que es una post-multiplicación: (Y esto se lee: la matriz R post-multiplica a la matriz T).

Otro ejemplo; quieres transformar el vector por la matriz para obtener el vector transformado .
Si la matriz es de tipo fila pre-multiplicas:
En cambio, si es de tipo columna post-multiplicas:

En algebra matricial siempre se multiplican filas por columnas, por lo tanto si la matriz es de tipo fila y deben ser interpretados como un vectores fila, y si es de tipo columna entonces y deberán ser interpretados como vectores columna.

Un último ejemplo; transforma el vector por las matrices (en éste orden).
La pre-multiplicación sigue el orden natural de las transformaciones por lo que resulta más intuitiva:
La post-multiplicación sería el proceso inverso:

Para terminar un truco para no liarte; cuando utilices matrices y vectores columna (post-multiplicación) debes interpretar las transformaciones como series de funciones:

En programación 3D hay pocas funciones tan necesarias como la raíz cuadrada. ¿Quién no recuerda el famoso teorema de Pitágoras? El cuadrado de la hipotenusa es igual a la suma de los cuadrados de los catetos por lo tanto la hipotenusa será

Esto lo podemos emplear con cualquier número de dimensiones, en 3D tendremos tres coordenas que definen un punto o vector en un espacio tridimensional, aplicando el mismo teorema podemos saber el módulo (longitud) del vector y a partir del módulo podemos, por ejemplo, normalizarlo (hacer que el vector sea de módulo 1).

Un ejemplo práctico:

La función anterior para normalizar vectores es perfectamente correcta pero se puede optimizar bastante. En primer lugar calcular raíces cuadradas tiene un coste computacional bastante importante y en aplicaciones 3D como juegos se usa constantemente por lo que es interesante optimizarla todo lo posible. Además de la raíz cuadrada también podemos sustituir las tres divisiones por tres multiplicaciones, ¿cómo lo hacemos? usando la inversa de la raíz cuadrada que nos permitirá multiplicar en lugar de dividir ya que la división está implícita en el cálculo.

¿Y cómo optimizamos la raíz cuadrada? Existen muchas formas de hacerlo pero vamos a ver la más rápida y sencilla, la raíz cuadrada inversa rápida (Fast InvSqrt):

Esta función se aprovecha de la forma interna de trabajo de la unidad de punto flotante (normativa IEEE 754)  para calcular una buena aproximación del resultado exacto. No es más que una simple aproximación por el método Newton.
Este código se hizo muy popular por haber sido utilizado en el Quake 3 y aunque su origen no está nada claro parece que surgió de SGI (Silicon Graphics) hace bastantes años.

La nueva función de normalización vectorial quedaría de la siguiente manera:

El incremento de velocidad conseguido es muy importante pero también hay que tener en cuenta que el resultado es una aproximación y que este código sólo puede usarse en procesadores cuyas unidades de punto flotante sigan la normativa IEEE 754.