Brief Introduction to Conformal Geometric Algebra

In words of Pablo Colapinto: “modern day graphics systems are an amalgam of matrix, vector, and tensor algebras“. These algebras run fast in computers, but the intricacies of their algebraic representations make it difficult to realize their truly geometric interpretation. Within the last decade, Geometric Algebra has emerged as a powerful alternative to the classical matrix, vector and tensor algebras as a comprehensive conceptual language and computational system for computer science. In his Master’s thesis Colapinto states that “great research has been done demonstrating its powers of synthesis, especially with regards to forms and control systems generated by twist groups and motor algebras“. However, it is known that little research focuses on their application to computer graphics, geometric modeling and animation. The aim of this post is to encourage the reader for use geometric algebra in geometric  modeling applications and computer graphics.

Geometric Algebra can be defined as the subset of Clifford Algebra that has geometric interpretation. In Conformal Geometric Algebra (CGA), rigid body motions can be represented as compact (multi-)vectors called Motors. Unlike homogeneous matrices, motors are linear transformations. All multivectors can be transformed by motors in a covariant and linear way. CGA motors can be efficiently interpolated for generating continuously deformed motions, and that is one of the main features that we should exploit in computer graphics. On the other hand, the interpolation of matrices is difficult and expensive. The logarithm of a matrix can be defined but is not elementary and not in closed form. A straightforward way to compute it is to take the eigenvalue decomposition of the rigid body motion matrix in the homogeneous coordinate framework, and take the Nth root of the diagonal matrix. Such numerical techniques makes the matrix logarithm expensive to compute and hard to analyze.

Continue reading

Otro tutorial de Quaternions

Existen muchos tutoriales que explican qué son los quaternions, sin embargo parece que están orientados a un público que ya tiene desarrollada cierta “intuición matemática”, es decir, han tenido contacto moderado o alto con álgebra abstracta, topología, teoría de categorías, entre otros.

Están plagados de tecnicismos, tanto así que comienzan definiendo a los quaternions como el cubrimiento doble del grupo SO(3). Es decir. aún no son accesibles para la mayoría de estudiantes y/o profesionales de ciencias de la computación.

En este post voy a explicar qué son los quaternions a un nivel accesible para gente interesada en sus aplicaciones en computación gráfica.

Entonces, comencemos por el principio de todo: los números complejos.

Los números complejos representan rotaciones

El matemático Sir William Rowan Hamilton paso 20 años de su vida tratando de representar las rotaciones en 3 dimensiones de manera similar a como los números complejos pueden representar rotaciones en el plano, y lo consiguió en 1843. En la época de Hamilton no existía todavía el álgebra vectorial, es decir, no se contaba con la noción de espacio vectorial, productor interior, producto cruz, etc. Las teoría de matrices no estaba desarrollada al punto que no existía una notación estándar para describir un conjunto de m ecuaciones con n variables. Así que Hamilton tuvo que desarrollar todas estas ideas antes de poder descubrir los quaternions, sin dudas fue un ¡genio!.

Hamilton conocía que los números complejos de norma = 1 pueden ser interpretados como rotores. Por ejemplo, el número:

R = \cos \theta + i \sin \theta

Representa la rotación de \theta radianes al rededor del origen. Hay que prestar atención a que la norma de R es unitaria, es decir \|R\| = 1.

De modo que si tenemos el vector 2d v = x + i y, y queremos rotarlo \theta radianes en el origen para hallar el vector v', podemos hacerlo simplemente multiplicandolo por el rotor R:

v' = R v

Cómo funciona esto? veamos con atención:

Continue reading

Geometría Hiperbólica: Disco de Poincaré

En este post les muestro cómo generar teselaciones hiperbólicas regulares del disco de Poincaré. El código de ejemplo está escrito en C# y utilicé Windows Presentation Foundation (WPF) por su facilidad de generar gráficos vectoriales, hice uso del .Net Framewoek 4 por su soporte para números complejos. Por supuesto, no es difícil transportar todo esto a Java, C++ o cualquier otro lenguaje.

Teselacion {5,4}
Teselación Hiperbólica {5,4} generada en C# y WPF

Continue reading

Álgebra Geométrica en las Ciencias de la Computación

Las Ciencias de la Computación tienen sus raíces en las matemáticas. De este hecho dan cuenta el Análisis de Algoritmos, la Geometría Computacional, los Métodos Numéricos y muchas más ramas de las Ciencias de la Computación. No es de sorprendernos que en éstas ramas existan problemas computacionales que encuentran su mejor expresión en lenguaje matemático. Resulta imprescindible contar con las herramientas matemáticas adecuadas que nos permitan expresar de forma simple y concisa ésta clase de problemas para así poder encontrar soluciones computacionales óptimas.

En éste post presento una nueva herramienta matemática, considerada por no pocos matemáticos y físicos como la más poderosa disponible a la fecha. Se trata de la denominada Álgebra Geométrica (en inglés, Geometric Algebra). El Álgebra Geométrica (AG) es una teoría matemática avanzada y a la vez una herramienta práctica para la representación y solución de problemas geométricos que impacta directamente en las Ciencias de la Computación, pero especialmente en las áreas de Geometría Computacional, Computación Gráfica y Visión Computacional.

Sus orígenes se remontan hasta hace más de 100 años. Fue concebida por el matemático inglés William K. Clifford (1845-1879) en la década de 1870 y desde entonces ha venido impactando en varias áreas de la Matemática, la Física y la Ingeniería. Recientemente ha sido introducida en las Ciencias de la Computación a través de conferencias como ACM SIGGRAPH, AGACSE (Applied Geometric Algebra for Computer Science and Engineering), GRAVISMA, entre otras.

Orígenes del Algebra Geométrica

Si bien el álgebra geométrica (conocida también como álgebra de Clifford) fue concebida por W. K. Clifford a fines del siglo XIX, no todo el crédito es suyo. El álgebra inventada por Clifford se basó fundamentalmente en las teorías del matemático alemán Hermann G. Grassmann (1809-1877) y en las del físico irlandés Sir William Rowan Hamilton (1805-1865). La muerte prematura de Clifford, a sus 33 años, cortó de golpe los avances en la teoría del álgebra geométrica ya que sus contemporáneos no la supieron interpretar y terminaron adoptando un álgebra mucho más simple, pero también mucho más limitada, como es el álgebra vectorial introducida por el físico norteamericano Josiah W. Gibbs (1839-1903) y el físico inglés Oliver Heaviside (1850-1925). Desde entonces, el álgebra vectorial y el cálculo vectorial fueron el estándar de facto tanto para física como para ingeniería, en cuanto a las aplicaciones geométricas del álgebra lineal concierne.

Recientemente, el físico norteamericano David Hestenes (1933-presente) buscando mejores representaciones matemáticas para la mecánica cuántica y la relatividad se dio cuenta de que el álgebra de Clifford casi no había sido explorada en sus aspectos geométricos (el sentido original que le trató de dar su creador W. K. Clifford) y comenzó el redescubrimiento de un “álgebra universal” que está conduciendo a la reformulación de la física cuántica: el álgebra geométrica.

¿Qué es y para qué sirve?

Clickea aquí para leer el artículo completo.

Vectores y Multivectores

Clickea aquí para leer el artículo completo.

Implementaciones y Eficiencia

Clickea aquí para leer el artículo completo.

Aproximación de curvas con BSpline

Comienzo este Blog con uno de los temas fundamentales de la Computación Gráfica, las curvas y superficies están en el corazón de la disciplina y entre las representaciones más poderosas para curvas y superficies tenemos a la BSpline.

Como programador de gráficos creo que no hay mejor forma de conocer este hermoso tema que poner las manos en la masa. En este post voy a mostrar cómo aproximar e interpolar datos n-dimensionales con BSpline usando el método de los mínimos cuadrados. Mostraré tanto las ecuaciones como el código fuente y trataré de hacer algunos paralelos entre ellos, las optimizaciones de código las dejaré como ejercicio para los lectores :).

BSpline Fitting
Aproximación de BSpline

¿Para qué aproximar datos con BSpline? en la práctica la aproximación BSpline se usa para:

  • Poder suavizar datos ruidosos (e.g. series de tiempo)
  • Generar curvas C^n continuas (cuyas n diferenciales existan) lo cual es importante para optimización, si se quiere encontrar los mínimos y máximos por ejemplo
  • Comprimir datos reduciéndolos a unos pocos puntos de control
  • Poder modificar los datos manteniendo continuidad C^n a través de puntos de control
  • Animar objetos a través de trayectorias suaves y continuas

Es necesario distinguir la aproximación de la interpolación. Una curva aproximada no necesariamente pasa por los todos los puntos (pero trata de acercarse), mientras que una curva interpolada si pasa por todos los puntos. La interpolación BSpline se utiliza para computar todos los “datos intermedios” conociendo sólo unas pocas muestras, por ejemplo permite computar colores intermedios en una fotografía, animaciones intermedias en una secuencia de key frames, deformaciones intermedias en una secuencia de deformaciones, transformaciones intermedias, etc.

Pero antes de entrar de lleno a la aproximación repasemos los conceptos básicos de BSplines y su formulación.

Continue reading