Geometric Algebra: Rotor Averages

Many times it is necessary to calculate the weighted average of 2 rotors (I am restricting this discussion to 3D Euclidean rotations). That’s easy in Geometric Algebra, given two rotors R_1 and R_2 we can solve for \Delta R(t) knowing that for t=0 the equation R_1 \Delta R(0) = R_1 holds (identity at zero) and for t=1 we have R_1 \Delta R(1) = R_2 (the final rotor) so:

\Delta R(1) = \tilde R_1 R_2

\Delta R(1) = \exp(\log(\tilde R_1 R_2))

thus we have:

\Delta R(t) = \exp( t \log(\tilde R_1 R_2) )

Which satisfy our requirements and is smooth. Finally we get the expression: R(t) = R_1 \exp( t \log(\tilde R_1 R_2) ) for getting rotors from R_1 to R_2.

Notice you don’t need to know the angle as in the SLERP formula, however it can be shown that R(t) is the same as the SLERP interpolation (you get the same result). So we can actually interpolate rotors using SLERP if convenient.

But what about interpolating 3, 4 or N rotors? it turns out the interpolation of more than 2 rotors is not that easy, we can extend our previous approach, but that’s only one approach out many and there are trade-offs we need to be aware of. So let’s begin with the extension of the previous approach.

The Rotor Manifold

3D rotors live in a manifold i.e., a curved space, which is basically a four dimensional sphere called S^3. Also the 3D rotors form a group called SO(3) of orthogonal isometries (i.e., transformations that preserve length and angles on the sphere S^3 and also preserve orientation). The SO(3) group is also a Lie group i.e., the rotor exponential is a map from tangent space to the manifold i.e., exponential map can project a tangent vector into the manifold, or in other words it can project an euclidean bivector to a rotor (so euclidean bivectors are tangent vectors and 3D rotors are points of the manifold). However the rotor exponential only works in such way at the north pole of S^3 i.e., at the identity. That means if we have a rotor which moves from the identity rotor I to some “point” rotor R_1 in S^3, the exponential works just fine. But if you have a rotor which moves from an arbitrary point rotor R_1 to other arbitrary point rotor R_2 then the exponential map cannot be used. Fortunately the Lie group SO(3) is “translation invariant” which means that we can translate an arbitrary point rotor R_1 to the north pole of S^3, use the exponential map there and then translate back to point rotor R_1. And the beauty of Lie groups is that all those translations can be done using rotors.

Log-Euclidean Average

If we have N rotors \{ R_i \} we can attempt to average the rotors in the “tangent space” at the north pole of S^3.

But what does it mean? computation wise that amounts to do: R = \exp( \sum_i \lambda_i \log(R_i) ) where \sum_i \lambda_i = 1. We can see this is basically the average of bivectors (tangent vectors) in the tangent space at the north pole of S^3. Then we are using the exponential map to project the averaged result to the manifold so we get an averaged rotor. Notice that we are assuming that all rotors have their tangent space at the north pole of S^3 i.e., that they are all “connected to the identity” by a geodesic curve (a curve departing from the identity rotor to the given rotor).

That’s a reasonable assumption for many applications. For 2 rotors it will give an interpolation close to SLERP although without constant velocity. It is also cheap to compute (closed form) and one can do high order rotor interpolation using polynomial basis functions, B-Spline or any other.

Weiszfeld Algorithm

The geodesic distance covered by the geodesic curve R(t) = R_1 \exp( t \log(\tilde R_1 R_2) ) in S^3 can be measured as d(R_1, R_2) = \| \log(\tilde R_1 R_2) \| which is basically \|\theta\|. Note that I am using the logarithm defined at the north pole of S^3 i.e., at the identity. The quality of an average can be measured in terms of minimizing the distance d i.e., the rotor average is the one at the “center” or at “equal distance” to all N input rotors, so a sensible measure can be E(R) =  \sum_i d(R, R_i) where $R$ is the average rotor and E(R) is our measure of the quality (the less E(R) is the better is the quality of the average).

We can improve the Log-Euclidean average by doing a gradient descent on E(R). Fortunately there is a simple way to do that. The “Weiszfeld Algorithm” is a known optimization algorithm for finding the geometric mean on a Riemannian manifold. Note that here E(R) is a scalarfield. The gradient vector field of E(R) is \nabla E(R) = -\sum_i \lambda_i \frac{\log(\tilde R R_i)}{\|\log(\tilde R R_i)\|}, which is a great result (we derive it in next section). The gradient points in the negative direction of the geodesic path minimizing E(R). The goal is to find a mean rotor R such that \nabla E(R) = 0. That minimization makes sense since the gradient belongs to the tangent space at the identity where all combinations are linear i.e., the \log of each point R_i is translated to the identity i.e., \tilde R R_i. The gradient descent iteration is as follows:

  1. Set R = 1
  2. \nabla E(R) = -\sum_i \lambda_i \frac{\log(\tilde R R_i)}{\|\log(\tilde R R_i)\|}
  3. R^* = R \exp(-\nabla E(R))
  4. Set R = R^* and repeat steps 2-4 until \|R - R^*\| < \epsilon

As you can see in step 3, we project the gradient to the manifold and translate the point from the identity (north pole) to where it belongs moving along the geodesic curve. The rotor R^* is the average rotor minimizing the geodesic distance. Instead of a gradient descent one can do a Newton type optimization, minimizing the squared distance d(R_1, R_2)^2. That improved version is the “Karcher Algorithm“.

Derivation of the L1 Gradient for Weiszfeld Algorithm

Having geodesic curve from R_1 to R_2 parameterized by the scalar t given by \gamma(t) = R_1 \exp( t \log(\tilde R_1 R_2)) and a function f(\gamma(t)) = \| \log(\tilde R_1 \gamma(t)) \| measuring the geodesic distance from R_1 to \gamma(t), where \gamma(0) = R_1 and \dot \gamma(0) = R_1 \log(\tilde R_1 R_2) the covariant derivative \nabla f is given by:

<\nabla f, w> = \frac{d}{dt} f(\gamma(t)) |_{t=0}

\frac{d}{dt} f(\gamma(t)) = \frac{d}{dt} \| \log(\tilde R_1 \gamma(t)) \|

\frac{d}{dt} \| \log(\tilde R_1 \gamma(t)) \| =2 \| \log(\tilde R_1 \gamma(t)) \|^{-1} <\frac{d}{dt} \log(\tilde R_1 \gamma(t)), \log(\tilde R_1 \gamma(t))>

\frac{d}{dt} \log(\tilde R_1 \gamma(t)) =  \frac{d}{dt} \log(\tilde R_1 R_1 \exp( t \log(\tilde R_1 R_2))) by definition of \gamma(t)

\frac{d}{dt} \log(\tilde R_1 \gamma(t)) =  \frac{d}{dt} t \log(\tilde R_1 R_2) by \tilde R R = 1 and \log(\exp(X)) = X

\frac{d}{dt} \log(\tilde R_1 \gamma(t)) =  \log(\tilde R_1 R_2)

Replacing in the original equation:

\frac{d}{dt} \| \log(\tilde R_1 \gamma(t)) \| = 2 \| \log(\tilde R_1 \gamma(t)) \|^{-1} < \log(\tilde R_1 R_2), \log(\tilde R_1 \gamma(t))>

Since we can identify any tangent vector along the geodesic with w = \log(\tilde R_1 \gamma(t)) then the following inner product represent the differential df(R):

\frac{d}{dt} f(\gamma(t))|_{t=0}= 2 \|w\|^{-1} < \log(\tilde R_1 R_2), w>

By identification with <\nabla f, w> = \frac{d}{dt} f(\gamma(t)) |_{t=0} we have \nabla f =  \log(\tilde R_1 R_2)

So the gradient of d(R,R_i) is \nabla_R d(R) = \log(\tilde R R_i) d(R,R_i)^{-1} and we can apply that to E(R) by linearity to get the gradient of it.

Time Derivative of \gamma(t) |_{t=0}

\dot \gamma(t) = \lim_{\Delta t \rightarrow 0} { \frac{\gamma(t+\Delta t) - \gamma(t)}{\Delta t} }

\dot \gamma(t) = \lim_{\Delta t \rightarrow 0} { \frac{R_1 \exp((t+ \Delta t) \log(\tilde R_1 R_2)) - R_1 \exp( t \log(\tilde R_1 R_2)) }{\Delta t} } by definition of \gamma(t)

\dot \gamma(t) = \lim_{\Delta t \rightarrow 0} { \frac{R_1 \exp(t \log(\tilde R_1 R_2)) \exp(\Delta t \log(\tilde R_1 R_2)) - R_1 \exp( t \log(\tilde R_1 R_2)) }{\Delta t} } By commutativity of exponentials of the same bivector.

\dot \gamma(0) = \lim_{\Delta t \rightarrow 0} { \frac{R_1 \exp(\Delta t \log(\tilde R_1 R_2)) - R_1 }{\Delta t} } After evaluating at t=0

\dot \gamma(0) = \lim_{\Delta t \rightarrow 0} { \frac{R_1 (1 + \Delta t \log(\tilde R_1 R_2)) - R_1 }{\Delta t} } By linearization of \exp(X) = 1 + X

\dot \gamma(0) = \lim_{\Delta t \rightarrow 0} { \frac{ R_1 \Delta t \log(\tilde R_1 R_2)}{\Delta t} }

\dot \gamma(0) =  R_1 \log(\tilde R_1 R_2)

Chord Metric Minimizer Average

Other way to define the average is in terms of the Euclidean distance i.e., the average that minimize the so called “chordal distance” or distance of rotors embedded in \mathcal R^4 space  (4-dimensional vector space), defined as:

d_{chord}(R_1, R_2) = \| R_1 - R_2 \|

Unfortunately for rotors the distance d_{chord}is not well defined since a rotor R and -R represent the same rotation and it doesn’t matter which one to choose, so the distance d_{chord}(R, -R) should be zero but it isn’t. So the mean rotor minimizing chordal distance on average R = \frac{\sum_i R_i}{n} is meaningful only if you choose all the R_i to have the same “orientation”.

On the other hand, the chord metric for matrices \| A_1 - A_2 \|_F under Frobenius norm is well defined and it can be shown, using Rodrigues formula, that chordal length is related to the sine of the angle as d_{chord}(A_1, A_2) = 2\sqrt{2} \sin(\theta/2)

For rotors you can also minimize the angle \sin(\theta/2) using the following distance function:

d(R_1, R_2) = \| < R_1 \tilde R_2 >_2\|

where the norm is the Euclidean norm in the embedding space of 3D bivectors \mathcal R^3. So this distance is measurimg the same quantity than the chord distance of matrices under Frobenius norm (up to a scalar). We will attempt to minimize the squared distance d(R_1,R_2)^2 since we can a closed form expression. Basically we have to solve the following optimization problem: 

arg \min_R \sum_i { \| <R_i \tilde R>_2 \|^2}

This functional is minimizing the squared angle  \sin^2 \theta/2

Terminology: lets denote the rotor R as the sum of the bivector L and the scalar w so R = L + w. Similarly the rotor R_i = L_i + w_i.

Then < R_i \tilde R >_2 = < (L_i + w_i) (\tilde L + w) >_2 so:

< R_i \tilde R >_2 = -L_i \times L + L_i w - w_i L

Where \times denote the commutator product of bivectors. This can be trivially expressed to matrix form by embedding bivectors in \mathcal R^3 and changing commutator product by cross product of vectors.

\begin{bmatrix} 0 & 0 \\ L_i & -([L_i]_{\times} + w_i I_3)\end{bmatrix} \begin{bmatrix} w \\ L \end{bmatrix} = \begin{bmatrix} 0 \\ L_i w -L_i \times L - w_i L \end{bmatrix}

Where [L_i]_{\times} is the cross product matrix and I_3 is the 3 \times 3 identity matrix.

Let’s denote M_i the matrix \begin{bmatrix} 0 & 0 \\ L_i & -([L_i]_{\times} + w_i I_3)\end{bmatrix} made exclusively with terms of rotor R_i, then we can express the quadratic form as:

\| <R_i \tilde R>_2 \|^2 = R^T (M_i^T M_i) R

The matrix M_i^T M_i has the following form:

M_i^T M_i = \begin{bmatrix} L_i^T L_i & -w_i L_i^T \\ -w_i L_i & -[L_i]_{\times}^2 + w_i^2 I_3\end{bmatrix}

The whole optimization problem can be expressed as:

arg \min_R R^T \sum_i { M_i^T M_i } R subject to R^T R = 1

The quadratic form is minimized when R is equal to the eigenvector of \sum_i { M_i^T M_i } associated with the min eigenvalue.

Dual Problem

This problem we solved above can be restated as 

arg \max_R \sum_i \| <R_i \tilde R>_0\|^2

which is maximizing \cos^2 \theta/2. This dual problem convenient since this the quadratic form associated is much simpler than the primal problem:

Recall that <R_i \tilde R>_0 = -L_i \cdot L + w_i w and this is equivalent to:

\begin{bmatrix} w_i & L_i^T \end{bmatrix} \begin{bmatrix} w \\ L \end{bmatrix} = L_i^T L + w_i w

Notice the negative sign of -L_i \cdot L is absorbed by the Euclidean inner product L_i^T L so there is no mistake in the sign. So the quadratic form is:

\| <R_i \tilde R>_0 \|^2 = R^T (M_i^T M_i) R

where M_i^T M_i =  R_i R_i^T and so the quadratic form is:

\sum_i \| <R_i \tilde R>_0\|^2 = R^T (\sum_i R_i R_i^T) R

The quadratic form is maximized when R is equal to the eigenvector of M = \sum_i R_i R_i^T associated with the max eigenvalue.

The above quadratic form was derived by Markley et al http://www.acsu.buffalo.edu/~johnc/ave_quat07.pdf in 2007 for finding quaternion’s average and it is quite popular in the graphics industry since it is simple to implement and fast to compute i.e., closed form. However Markley et al paper lacks clarity, they used a much more complex mathematical approach to derive the quadratic form, based on matrices related to the Wahba’s Problem, probably because the first author was familiar to those methods. Anyway, they also gave an obscure interpretation to the solution. They assert that this solution is a “maximum likelihood estimate” of an attitude matrix which is totally unrelated to the problem i.e., the Fisher information matrix of matrix errors in SO(3). I found that interpretation totally clueless and irrelevant. The real interpretation is that it minimizes the squared angle \sin^2 \theta/2 of rotors (or quaternions) embedded in the \mathcal R^4 vector space, since it is equivalent to primal problem. You can also say it minimizes the chordal distance of the equivalent matrices under Frobenius norm.

Geometric Algebra: Eigenvectors from Eigenvalues

Recently I have found a new expression for for calculating eigenvectors from eigenvalues of a real symmetric matrix in Geometric Algebra, just using the outer product!. Basically the only thing we need to do is taking the meet of n – 1 columns of a singular matrix like explained in my paper:

viXra: http://vixra.org/abs/1911.0127

That works very well for small matrices, in practice. It seems more convenient to use than determinants and minors.

Continue reading

Eigenvectors from Eigenvalues

There was a newly published result relating the coordinates of the eigenvectors of a (hermitian or symmetric) linear operator to the eigenvalues of the operator and its minors that has been getting some press lately:

Quanta Magazine: https://www.quantamagazine.org/neutrinos-lead-to-unexpected-discovery-in-basic-math-20191113/

arXiv: https://arxiv.org/abs/1908.03795

Terry Tao gives a nice “geometric” proof on his blog that might be interesting to readers here (see “2 a geometric proof”): https://terrytao.wordpress.com/2019/08/13/eigenvectors-from-eigenvalues/

I have worked out the Tao’s geometric proof in Geometric Algebra and have re-write it so anybody can follow what is going on in detail.

Continue reading

Tutorial de Álgebra Geométrica Conforme

“…for geometry, you know, is the gate of science, and the gate is so low and small that one can only enter it as a little child.” — William Kingdon Clifford (1845–1879)

El Álgebra Geométrica es un subconjunto de lo que hoy se conoce como Álgebras de Clifford. Se puede afirmar que es la parte del Álgebra de Clifford que tiene sentido geométrico. Citando a David Hestenes:

“When a geometric interpretation is attached to a Clifford Algebra, I prefer to call it a Geometric Algebra, which is the name originally suggested by Clifford himself.”

El Álgebra Geométrica Conforme es la fusión del Álgebra Geométrica de Clifford con la Geometría Hiperbólica. Un importante resultado de la geometría hiperbólica es que se pueden encontrar superficies cuya métrica hiperbólica es isomorfa a la del espacio Euclidiano. Básicamente, el espacio vectorial 3D (i.e., Euclidiano) es embebido en un espacio proyectivo 5D en el cual se cumple que los vértices en el espacio Euclidiano 3D se corresponden con vértices en la superficie de un hiperparaboloide en el espacio hiperbólico 5D. Como veremos más adelante esta representación algebraica tiene muchas ventajas para el Modelado Geométrico, ya que las transformaciones no lineales en el espacio 3D (e.g., transformaciones conformes) son lineales en el espacio 5D.

El Álgebra Geométrica Conforme de Hestenes tiene la ventaja de que las primitivas geométricas como son: puntos, líneas, planos, círculos y esferas, pueden ser representadas directamente como “objetos” algebraicos que pueden ser comparados, intersecados y transformados (i.e., trasladados, rotados y escalados) sin necesidad de especificar sus coordenadas, obteniendo una correspondencia inmediata entre objetos algebraicos y objetos geométricos con un gran nivel de abstracción. Además posee un álgebra de transformaciones conformes propiamente dicha sobre la cual se puede aplicar Cálculo Geométrico. Citando a Alan McDonald:

“How Geometric Algebra Works: Algebraic operations on blades correspond to geometric operations on the subspaces they represent”

En la última década el Álgebra Geométrica y el Cálculo Geométrico han recibido más atención de la comunidad académica, perfilándose como alternativas de (entre otras) al álgebra vectorial, tensorial, compleja y cuaterniónica por un lado y al cálculo vectorial, análisis complejo, geometría diferencial y otras teorías avanzadas por el otro. La razón es que se trata de una teoría matemática que unifica varias teorías matemáticas de forma consistente y es por lo tanto un lenguaje unificado para la física y la ingeniería. Y eso la hace inmensamente poderosa. Un lenguaje que hace accesibles las investigaciones de máximo nivel en ciencias para los no especialistas en matemáticas, ya que codifica los fundamentos matemáticos subyacentes de diversas teorías matemáticas y facilita relacionarlos y transportarlos hacia nuevas áreas de estudio. En última instancia, el Álgebra y Cálculo Geométricos son la puerta de entrada hacia las matemáticas avanzadas y aceleran el aprendizaje de teorías matemáticas para la física y la ingeniería.

Diversos artículos demuestran el poder de síntesis del Álgebra y Cálculo Geométricos y sus aplicaciones en Visión Computacional y Robótica. En esos campos, el álgebra de motores y de transformaciones conformes (y su correspondiente algebra de Lie) son usados rutinariamente para reformular diversos problemas geométricos de forma algebraica y resolverlos de forma eficiente. Como veremos más adelante, AGC (Álgebra Geométrica Conforme) es la teoría matemática idónea para el modelado geométrico. También veremos que, usando el AGC evitamos completamente los inconvenientes que tienen las coordenadas homogéneas y sus transformaciones rígidas y además tenemos nuevas herramientas más generales y poderosas a nuestra disposición.

A pesar del enorme potencial que poseen el Álgebra y Cálculo Geométricos hoy en día son teorías relativamente desconocidas, inclusive para matemáticos y físicos. Por supuesto también es desconocido por la mayor parte de la comunidad de Ciencias de la Computación y es por eso que su aplicación en modelado geométrico resulta un poco esotérica. Parte de la razón es porque aún no se enseña en el pregrado de la mayoría de universidades. La enseñanza de estas teorías recién está empezando a expandirse ya que se cree que es posible enseñarla desde el colegio. Citando a los Lasenby:

“While providing an immensely powerful mathematical framework in which the most advanced concepts of quantum mechanics, relativity, electromagnetism, etc. can be expressed, it is claimed that GA [Geometric Algebra] is also simple enough to be taught to school children!”

Álgebra Geométrica de Clifford

No es mi intención hacer una introducción minuciosa ni rigurosa del Álgebra Geométrica, sino mas bien hacer una introducción intuitiva y comprensible de los conceptos básicos para lectores que no conocen nada del Álgebra Geométrica pero que han culminado sus cursos de álgebra lineal y análisis matemático a nivel universitario. Una introducción amplia y muy accesible para graduados en Ciencias de la Computación se puede encontrar en el excelente libro: “Geometric Algebra for Computer Science” de Dorst, Mann y Fontijne.

Nota: ante cualquier duda o vacío encontrado durante la lectura de este post, sugiero complementar con wikipedia.

Continue reading

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.

Aplicaciones de Aprendizaje por Refuerzo en Video Juegos

Reinforcement Learning es una metodología que forma parte del campo de Machine Learning y de las Ciencias Cognitivas. Los algoritmos de Reinforcement Learning permiten a uno o varios agentes tomar decisiones optimas de acuerdo a su conocimiento del ambiente. En Reinforcement Learning, el agente aprende gracias a técnicas de ganancia y castigo. El agente aprende a realizar tareas a través de la repetición de acciones correctas e incorrectas. Es así que cada acción que realiza el agente tiene asociada una ganancia.

La precisión del aprendizaje está en función del tiempo que tiene para aprender. En general, un aprendizaje rápido le dará una mala representación de la tarea que realizará, mientras que un aprendizaje a largo plazo le dará una mejor representación y por lo tanto un mejor resultado en la tarea que realizará. Todas las metodologías de RL requieren un balance entre la búsqueda de nuevas estrategias y el uso del conocimiento ya adquirido.

Cuando un agente usa el conjunto de acciones que ya realizó y su ganancia como premisas para escoger una nueva acción a realizar, entonces estamos hablando de “Explotación”. Cuando un agente está buscando nuevos caminos, estamos hablando de “Exploración”. Un buen aprendizaje requiere la combinación de estrategias de Explotación tanto como de Exploración.

Reinforcement Learning es usado frecuentemente para el aprendizaje de políticas de control y para tomar decisiones en casos específicos donde se aplican esas políticas. En realidad virtual se esta utilizando Reinforcement Learning como modelo para generar automáticamente controladores para tareas típicas en 2D y 3D. Se investiga la animación del comportamiento de agentes autónomos que se desenvuelven como humanos virtuales y son capaces de tomar decisiones. La industria de los video juegos es un campo de prueba de muchos algoritmos de control, (por ejemplo control de la navegación de vehículos) y de aprendizaje de estrategias. El objetivo de este post es hacer una revisión del estado del arte de los algoritmos de control y aprendizaje de estrategias desarrollados bajo el paradigma de Reinforcement Learning usados en Video Juegos.

El post completo es de 36 páginas, por lo que preferí editarlo en PDF, descárgalo aquí.

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