Mamá, no hacen falta matrices

• Es un experimento que aplica Euclidean PGA de punta a punta en un forward renderer compatible con glTF, en lugar de las matrices 4x4 usadas casi por inercia en gráficos 3D
• Las rotaciones y traslaciones se representan con un PGA motor de 8 floats, y la composición de motores generales se procesa con 48 multiplicaciones y 40 sumas, menos que las 64 multiplicaciones y 48 sumas de una multiplicación de matrices 4x4
• La transformación de puntos, si se expande de forma directa, es más costosa que con matrices, pero usando el sandwich product y la condición de normalización se reduce a 21 multiplicaciones y 18 sumas; transformar direcciones y direcciones de base es aún más barato
• En tangent space normal mapping, se reemplazan la normal y la tangente por un tangentRotor, reduciendo los datos de vértice de 12 floats a 9 floats, mientras que el costo de transformación a world-space queda en un nivel similar al enfoque con matrices: 47 multiplicaciones y 38 sumas
• Para encajar con contenido glTF real, hay que convertir matrices a motores al cargar y llevar el uniform scale como un float separado; el non-uniform scale requiere manejo limitado o una ruta alternativa con matrices 4x4

---

Un forward renderer sin matrices hecho con PGA

• El proyecto es Look, Ma, No Matrices, y apunta a implementar un forward renderer sin matrices
• Desde SIGGRAPH 2019, Geometric Algebra, en particular Euclidean PGA, ganó interés en las comunidades de gráficos y machine learning, pero en gráficos 3D tradicionales muchos casos se quedaron en rebautizar los dual quaternions como PGA motors
• Esta implementación integra PGA algebra en un motor 3D compatible con glTF, no solo cambiando nombres algebraicos, sino reorganizando varias partes del pipeline gráfico al estilo PGA
• La implementación de referencia es el Khronos glTF viewer, y se parece más a un experimento para reemplazar matrices sin concesiones que a una implementación de máximo rendimiento
  • Al final, es probable que una hybrid solution sea una mejor opción

Por qué sospechar de las matrices 4x4

• Las matrices 4x4 han tenido un rol central durante mucho tiempo en las API gráficas y en los pipelines de función fija de GPU, y siguen siendo la herramienta base del forward rendering común
• Las GPU modernas se parecen más a procesadores escalares programables que a pipelines de función fija, por lo que una representación centrada en matrices no es necesariamente imprescindible
• En motores 3D reales, muchas matrices son matrices ortogonales que solo contienen rotación y traslación
• La variedad de PGA motors representa todo el movimiento euclidiano con menor costo de cómputo y memoria, y puede incluir quaternions y dual quaternions sin conversión

Representación de datos en PGA y operaciones básicas

• PGA algebra se genera a partir de cuatro vectores base e0~e3
  • e1, e2, e3 corresponden respectivamente a los planos x=0, y=0, z=0
  • El vector degenerado especial e0 representa el plano en el infinito
• En los shaders se usan tipos integrados de GLSL para aprovechar suma, resta y multiplicación escalar sin sobrecarga de operadores
  • motor mat2x4
  • line mat2x3
  • point vec3
  • direction vec3
• La composición general de PGA motors se realiza con el geometric product
  • Multiplicación de matrices 4x4: 64 multiplicaciones, 48 sumas
  • Composición general de motores gp_mm: 48 multiplicaciones, 40 sumas
• En combinaciones especiales de transformaciones se pueden usar operaciones más baratas
  • gp_rr: 16 multiplicaciones, 12 sumas
  • gp_tt: 0 multiplicaciones, 3 sumas
  • gp_rt / gp_tr: 12 multiplicaciones, 8 sumas
  • gp_rm / gp_mr: 32 multiplicaciones, 24 sumas
  • gp_tm / gp_mt: 12 multiplicaciones, 12 sumas

Optimización de transformación de puntos y direcciones

• En PGA, al transformar un punto p con un motor M, se usa el sandwich product M p M̃
• La expansión directa requiere 33 multiplicaciones y 29 sumas, más que las 16 multiplicaciones y 12 sumas de una multiplicación matriz-vector
• Aprovechando que un motor normalizado satisface M M̃ = 1, se puede reescribir la expresión y reducir la transformación de puntos a 21 multiplicaciones y 18 sumas
• Las direcciones, es decir, puntos en el infinito, son más baratas porque el coeficiente implícito e123 es 0
  • Transformación general de direcciones: 18 multiplicaciones, 12 sumas
  • La transformación de una basis direction puede bajar, por ejemplo para el eje x, hasta 6 multiplicaciones y 4 sumas
• Esta optimización de basis direction se vuelve luego una base para cuestionar la idea de que las matrices siempre son lo más rápido al procesar tangent frames

Normalización, raíces cuadradas y mapas exponencial/logarítmico

• La pseudonorma cuadrada de un PGA motor tiene la forma M M̃ = a + b e0123, un Study Number
• La normalización no es una simple normalización vectorial, sino un procedimiento que garantiza que el motor resultante sea una transformación ortonormal
  • Costo de una implementación de normalización de motor general: 21 multiplicaciones, 5 sumas
  • En translation o rotation puras se pueden usar versiones más eficientes
• Una rigid transformation entre dos puntos, dos líneas o dos planos a, b se expresa como M = sqrt(b / a)
  • El geometric product ba entre dos elementos del mismo tipo crea un motor que corresponde al doble de la transformación que va de a a b
  • sqrt M puede calcularse como normalize(1 + M)
• El logarithm de un PGA motor es una scaled line, y una scaled line puede producir un rotation motor mediante exponentiation
• Aunque el exponential map de una matriz 4x4 general es numéricamente costoso, en la variedad de PGA motors es posible una closed form eficiente

Inversas y factorización de motores

• Geometric Algebra puede calcular de forma eficiente las inversas de objetos normalizados
  • Inversa de un plano: él mismo
  • Inversa de una línea: cambio de signo
  • Inversa de un punto: cambio de signo
  • Inversa de un motor: reversion
• Cuando un bivector general no satisface la Plücker condition y no representa una sola line, la inversa se calcula usando la inversa de Study Number
• En la implementación de renderizado se usan dos factorizaciones
  • Euclidean factorization: descompone un motor en una rotation alrededor del origen seguida de una translation
  • Invariant factorization: descompone un motor en translation y rotation que conmutan entre sí; en 3D es la forma conocida como Mozzi-Chasles theorem
• Al componer el tangent frame con el motor object-to-world, la Euclidean factorization es útil por la propiedad del frame de ser invariante a translation

Manejo de matrices glTF y scale

• Para interoperar con contenido glTF existente, hay que convertir las matrices a PGA motors en el momento de carga
• Una 4x4 orthogonal matrix se convierte a motor usando su isomorfismo con quaternions
  • Todas las matrices y transformaciones importadas se convierten en load time
• Los PGA motors manejan rigid body transformations, por lo que no incluyen scaling
• El uniform scaling es invariante a rotation y translation, así que se lleva como un único float por nodo
  • El total scale de cada elemento se calcula como el producto de su propio scale y el scale del padre
  • Al vertex se le aplica el total scale en load time o en el primer paso del vertex shader
  • A la translation se le aplica el parent scale en load time y al actualizar animaciones
• En una muestra de unos 400 archivos glTF aleatorios, menos del 0.5% tenía scale animation, mientras que el fixed uniform scale era bastante frecuente
• El non-uniform scaling es más complicado porque no es invariante a rotation
  • Para manejar non-uniform scale general, una ruta alternativa con 4x4 matrix es inevitable
  • En los glTF de muestra se encontraron casos donde el non-uniform scale solo se aplicaba a leaf nodes; en ese caso se aplica el scale por separado antes del resto de las transformaciones, sin afectar las animation keys

Reemplazo de Model-View-Projection

• Un forward renderer transforma la mesh geometry de object space a screen space y determina qué píxeles cubre cada triangle
• Entre las matrices model, view y projection del pipeline común, model y view se reemplazan por PGA motors
  • La posición del vertex usa sw_mp
  • Las direcciones de normal y tangente usan sw_md
• La projection matrix normalmente solo tiene 5 entradas no nulas, así que no se fuerza su conversión a PGA y se usa directamente una projection expression
• La actualización de la scene graph hierarchy del lado CPU reduce el cómputo al usar composición de motores en vez de composición de matrices
• Del lado GPU, si solo se compara la transformación de vertices, el motor parece quedar en desventaja, pero el resultado cambia al modificar la representación del tangent frame

Optimización de tangent space normal mapping

• El vertex shader de una mesh normal-mapped en tangent space común debe transformar position, normal y tangent
• Como normal, tangent y bitangent forman un orthonormal frame, en PGA se pueden representar como un tangentRotor que lleva del canonical basis frame al tangent frame deseado
• Este enfoque reduce el vertex descriptor
  • Convencional: position 3 + normal 3 + tangent 4 + uv 2 = 12 floats
  • Enfoque PGA: position 3 + tangentRotor 4 + uv 2 = 9 floats
  • La cantidad de floats por vértice baja 25%
• El tangentRotor tiene double cover, y el sign del scalar coefficient se alinea con el classical handedness flag para distinguir k-reflections pares/impares
  • Depende de signed zero, y en el vertex shader se extrae el handedness con sign(1/tangentRotor.x)
• Transformar position, normal y tangent con una 4x4 matrix requiere en total 48 multiplicaciones y 36 sumas
• El enfoque PGA transforma todo el tangent frame de una vez y luego extrae normal y tangent
  • Composición de tangent frame: 16 multiplicaciones, 12 sumas
  • Extracción de normal/tangent: 9 multiplicaciones, 8 sumas
  • Transformación de position: 21 multiplicaciones, 18 sumas
  • 1 multiplicación para extraer handedness
  • Total: 47 multiplicaciones, 38 sumas
• El costo de transformación de vértices es casi igual al enfoque con matrices, y el almacenamiento de transform se reduce de 32 floats a 8 floats

Fragment shader y restricciones de baked textures

• Para cargar contenido existente, en la etapa de fragment shader vuelve a ser necesaria una TBN matrix
• La baking tool, durante el proceso de hornear una high-detail mesh sobre una low-detail mesh, interpola la vertex normal y la tangent sobre la cara del triangle y construye una TBN matrix ortogonal en cada fragment para crear la tangent space normal texture
• La interpolación de basis vectors genera el error típico del enfoque con matrices, y ese error ya está baked en la texture
• Por eso esta implementación extrae explícitamente normal y tangent vector desde el tangentRotor
• Si también se pudiera controlar la baking tool, se podría pasar el tangentRotor tal cual al fragment shader, normalizarlo y usarlo para transformar la sampled normal
  • No haría falta construir una TBN matrix
  • La extracción de normal/tangent en el vertex shader sería innecesaria
  • Se podría reducir un varying parameter
  • También se eliminaría la expensive orthogonalization del fragment shader

Motor skinning y animation blending

• Como los PGA motors son isomorfos a dual quaternions, se aplican naturalmente a skinning
• Después de convertir la inverse bind matrix a motor, se mezclan los bone motors siguiendo el mismo patrón que dual quaternion skinning
• Las transformations que se mezclan alinean su signo para seguir el shortest arc, y la transformation resultante se vuelve a normalizar
• El animation blending también se hace del mismo modo: se mezclan directamente los PGA motors en CPU y luego se normalizan

Resultados del experimento de reemplazo de matrices

• Es posible implementar un forward renderer compatible con glTF reemplazando matrices solo con PGA
• La expectativa de que el costo de transformación sería mayor no es tan simple si se aplican la representación de tangent frame y la optimización de sandwich product
• En el caso común de tangent space normal mapping, el enfoque con PGA motors mantiene el costo del vertex shader casi igual al enfoque con matrices, mientras reduce significativamente la huella de memoria de los vertices
• La mejora de memoria, que permite guardar alrededor de 33% más vertices en el mismo storage, es especialmente importante
• Esta técnica puede aplicarse a motores 3D existentes como un drop-in replacement que casi no aumenta el costo del vertex shader y no modifica el resto del pipeline

[GN⁺]

Opiniones en Hacker News

• Una de mis creadoras favoritas de YouTube sobre matemáticas/gráficos, Freya Holmér, hizo hace poco un muy buen video introductorio sobre álgebra geométrica: https://www.youtube.com/watch?v=htYh-Tq7ZBI&ab_channel=Freya...
  Si te interesan los gráficos 3D, en especial las splines/curvas de Bézier, vale la pena ver todos sus videos.
  Personalmente, el álgebra lineal siempre me resultó difícil, pero este enfoque de álgebra de Clifford se siente mucho más intuitivo.

  • Fue una presentación realmente buena y me hizo acordar a https://enkimute.github.io/ganja.js/
    Esta biblioteca, creada por enkimute, el autor del artículo original, es bastante sorprendente: un script de un solo archivo y sin build, pero aun así ofrece soporte para álgebras de N dimensiones y renderizado.
  • Pensé que este artículo iba a tratar sobre ella. También disfruté sus videos sobre splines y Bézier, y la presentación va directo a lo esencial sin sentirse apresurada en absoluto.
  • En los comentarios de YouTube también hay explicaciones complementarias y preguntas sorprendentemente buenas.
    Por ejemplo, hay explicaciones bastante buenas de partes que Freya pasa un poco rápido u omite, como la no conmutatividad del producto.

• El álgebra geométrica fue un completo misterio para mí durante un tiempo, hasta que finalmente la entendí así: es simplemente multiplicación de polinomios, solo que hay cantidades donde el orden de multiplicación importa y la tabla de multiplicar es rara. Por ejemplo, i*i = 1, i*j = -j*i
  La mayoría de los materiales introductorios hacen que el producto geométrico de dos vectores (x1*i + y1*j) * (x2*i + y2*j) parezca algo profundo y misterioso, pero en realidad es igual a la expansión FOIL que aprendimos en álgebra de primer año:
  (x1*i + y1*i)(x2*i+y2*j) = x1*x2*i*i + x1*y2*i*j + y1*x2*j*i + y1*y2*j*j = (x1*x2 + y1*y2) + (x1*y2 - y2*x1)*i*j
  El valor dentro del primer paréntesis es el producto punto conocido, y el valor dentro del segundo paréntesis corresponde al producto cruz conocido, pero expresado con una base de una nueva dimensión llamada i*j. Y, a diferencia del producto cruz, se generaliza a cualquier dimensión; en álgebra geométrica se le llama producto exterior.
  Entender esto facilita cosas como derivar fórmulas de rotación, porque puedes aplicar directamente las técnicas aprendidas en álgebra para resolver problemas geométricos.

  • En https://youtu.be/htYh-Tq7ZBI?si=lOmsCL2DoqUCQgh1&t=1540, mencionado en otro comentario, Freya hace una excelente explicación reduciendo los axiomas a uno solo.
    Si defines el valor de un vector multiplicado por sí mismo como el cuadrado de la longitud de ese vector, todo lo demás se deriva de una simple multiplicación de polinomios. Es bastante hermoso.
  • Esta explicación muestra un contraste interesante. Hace unos días alguien preguntaba por qué las clases de matemáticas no enseñan el método y la razón detrás de las operaciones, sino que solo dan fórmulas para calcular; aquí, en cambio, el foco está en qué hace la operación más que en por qué es válida.
    “¿Cómo funciona?” y “¿por qué funciona?” son dos preguntas que un profesor de matemáticas debe equilibrar, y no siempre es fácil responder bien ambas en un mismo curso.
  • El segundo término no es el producto cruz, sino el producto del álgebra exterior, o un bivector. El producto cruz solo funciona en 3 dimensiones, mientras que el producto del álgebra exterior puede usarse también en dimensiones arbitrarias más altas.
    El producto cruz de dos vectores 3D es otro vector perpendicular al plano que forman esos dos vectores. En cambio, el producto del álgebra exterior es un 2-vector, es decir, un bivector, que recorre el paralelogramo entre los dos vectores y está sobre el plano en el que yacen. En 3D, el vector del producto cruz es perpendicular a este plano del bivector.
  • Una de las cosas que más tiempo toma aprender en matemáticas es que la mayoría de las cosas se definen de la forma más simple posible.
    En particular, definir un producto bilineal m:V x V -> V sobre un espacio vectorial V es exactamente lo mismo que definir m solo para pares de vectores base. Si a esto se le llama “propiedad universal del producto tensorial”, probablemente uno simplemente diga: “ah, ya veo”.

• Es interesante que haya varios enfoques para interpolar rotaciones: álgebra geométrica, cuaterniones e incluso interpolación de matrices completas: https://www.gamedev.net/tutorials/programming/math-and-physi...
  Pero una vez que optimizas el código a mano, el código final termina siendo casi igual en la mayoría de los enfoques. La diferencia está en cómo entiendes las reglas y las posibilidades.
  Hasta donde sé, el álgebra geométrica parece el enfoque más coherente y potente. Es poco familiar y bastante difícil de aceptar al principio, pero a quienes superan esa barrera les gusta.
  En cambio, todo el mundo usa cuaterniones pero se queja de que no los entiende, y dicen que para visualizarlos hace falta un libro entero, como 『Visualizing Quaternions』 de Andrew J. Hanson y Steve Cunningham.

  • No soy matemático y tampoco uso mucha geometría en mi trabajo, pero estaba aprendiendo álgebra geométrica por diversión, y antes también había intentado aprender cuaterniones.
    El álgebra geométrica es divertida, los cuaterniones no. Siento que entendí el álgebra geométrica; con los cuaterniones, aunque seguía clases y problemas, lo único que tenía claro era que no los entendía. Ahora que sé un poco de álgebra geométrica, por fin siento que también entiendo algo de cuaterniones.
  • 『Naive Lie Theory』 es un libro excelente, y enseña cuaterniones en el primer capítulo.
    https://www.goodreads.com/en/book/show/4419538

• Si te interesa este tema, hay unas buenas diapositivas que repasan los conceptos de Grassman/Clifford/álgebra geométrica: http://www.terathon.com/gdc12_lengyel.pdf
  También hay otro buen sitio: https://mattferraro.dev/posts/geometric-algebra

• Tampoco hay que dejar fuera la excelente “A swift introduction to projective geometric algebra” de Sudgy: https://www.youtube.com/watch?v=0i3ocLhbxJ4
  Y el sitio de referencia principal es https://bivector.net
  También se puede participar en el Discord de bivector, con más de 1000 profesores, investigadores y aficionados: https://discord.gg/vGY6pPk

  • Eric Lengyel, el autor de esa presentación, también escribió 『Foundations of Game Engine Development, Volume 1: Mathematics』, y el capítulo 4 trata el mismo tema

• Sinceramente, de la álgebra geométrica nunca me gustó mucho la forma en que, si no tienes cuidado con qué multiplicas por qué, aparecen todo tipo de elementos mixtos
  También se siente difícil de manejar que, para lo que era un espacio n-dimensional, puedas terminar necesitando hasta 2^n términos
  Parecería que debería permitir manejar mejor la geometría, es decir, el producto interno, pero no he visto una explicación convincente de por qué no basta con usar simplemente el producto exterior y el operador estrella de Hodge o el isomorfismo musical
  Incluso esa especie de “magia” de convertir el bivector u^v en una rotación e^(u^v)t en ese plano, en esencia, consiste en convertir la 2-forma u^v en un automorfismo lineal mediante el isomorfismo musical, y así entender e^(u^v)t como una exponencial de matriz
  Otro ejemplo que se menciona a menudo es que se pueden convertir las ecuaciones de Maxwell en una sola ecuación, pero con formas diferenciales ya se pueden resumir en dos ecuaciones que se cumplen por motivos distintos, así que no entendía la utilidad de fusionarlas en una

  • Eso de que “para lo que era un espacio n-dimensional se necesitan hasta 2^n términos” a veces es una ilusión de ahorro
    Por ejemplo, los vectores normales se transforman de forma distinta a los vectores de posición. Puedes representarlos con la misma estructura de datos, pero tienes que llevar registro de qué tipo de vector contiene, y meter casos especiales en distintas partes del código para tratarlos de manera diferente
    La álgebra geométrica aborda esto de frente: usa la base (i,j,k) para los vectores y una base separada (j*k, k*i, i*j) para el otro tipo
    Es un buen ejemplo de cómo, en términos de almacenamiento, un espacio de mayor dimensión puede ser más económico que uno de menor dimensión, en el sentido de que una sola ecuación es mejor que dos o cuatro
    El campo eléctrico difiere del campo magnético de una forma bastante parecida a como un vector difiere de un bivector. Puedes tratar el campo eléctrico y el magnético como casos especiales con ecuaciones separadas, o puedes manejarlos de manera uniforme con un solo enfoque
  • Los elementos mixtos son precisamente la parte importante
    Un cuaternión con w=1, x,y,z=0 es la identidad, y cuaterniones como w=0, x=1 o w=0, x=y=0.7 corresponden solo a rotaciones de 180 grados
    Si quieres una rotación arbitraria, necesitas una combinación de ambos. Es mezclar “un poco de rotación de 180 grados alrededor de esta línea” con “un poco de rotación de 0 grados/identidad”. Eso es exactamente lo que significa tener juntos un escalar y un bivector
    Si intentas evitar la mezcla “con cuidado” usando el producto exterior y el producto interno, lo estás usando mal. El protagonista es el producto geométrico, y produce mezclas excelentes
  • Estoy de acuerdo en que la confusión ya existe. El enfoque tradicional simplemente la barre debajo de la alfombra
    Por ejemplo, si trabajas con normales, tienes que seguir al menos dos espacios n-dimensionales que se transforman de formas bastante distintas
    Representar puntos, planos, líneas, normales, traslaciones y rotaciones con un único tipo multivector y reglas coherentes resulta bastante liberador una vez que lo entiendes. Aunque yo todavía lo estoy aprendiendo

• La interpolación de animación de la parte de abajo es realmente genial, pero me gustaría que los modelos del resto de la página fueran un poco menos activos
  Las matemáticas ya son lo bastante difíciles sin pequeños elefantes porristas

  • Al contrario. Sin ese ánimo elefantino, no habría llegado hasta el final de la página

• Si el autor está viendo esto, me gustaría que definiera la sigla PGA la primera vez que la use

  • Para quien tenga curiosidad, PGA es projective geometric algebra, es decir, álgebra geométrica proyectiva
    Se agrega un vector base nulo a los vectores base del espacio en el que se está trabajando. Esto permite representar algebraicamente también objetos geométricos que no pasan por el origen
  • En particular, la parte donde llama FPGA a “Fast PGA” fue bastante confusa
  • Corregido. mea maxima culpa

• ¿Algoritmos como estos son eficientes incluso pensando en la GPU?
  Tengo la impresión vaga de que las GPU están bien adaptadas a las operaciones con matrices, y me pregunto si al usar una formulación de álgebra geométrica se pierde esa ventaja y, en la práctica, no se termina yendo por delante
  Es una conjetura desde el desconocimiento, así que agradecería que me corrigieran si me equivoco

  • Es un malentendido muy común pensar que, como en los estándares de GPU hay multiplicación matriz-matriz y matriz-vector, las empresas de GPU necesariamente las aceleran
    En realidad, todo el núcleo de shaders ya es SIMD, así que no siempre pueden hacerlo. Algunas GPU lo hacen y otras no
  • Al programar, hay que averiguar dos cosas: qué cantidad quieres calcular y cuál es la forma más eficiente de calcularla
    La PGA tiene una carga considerable para entenderla, pero es una muy buena forma de abordar lo primero. De todos modos, normalmente conviene probar primero el método más simple y fácil de implementar
    La implementación obtenida al resolver lo primero con PGA basta para prototipar el resto del programa y hacer benchmarks para encontrar el verdadero cuello de botella. Por suerte, en la mayoría de los casos esa es la forma de cálculo más rápida, o es lo suficientemente rápida como para no ser un cuello de botella
    Incluso si termina siéndolo, te da una comprensión profunda del problema que estás tratando de resolver. Creo que conviene tener esa comprensión antes de empezar a recortar ciclos esperando que quede lo bastante rápido
  • Este artículo trata exactamente de eso. En resumen, en general pueden quedar más o menos al mismo nivel

• Esto parece una disputa de diferencias minúsculas en la punta del progreso
  Que la animación esqueletal 3D siga usando matrices 4x4 en la GPU significa que las matemáticas desarrolladas para este uso en la CPU en tiempos de Half-Life 1 siguen siendo la vanguardia. Son 26 años, de 1998 a 2024
  Dentro de 1000 años, la animación 3D seguirá igual

• Este artículo está fuera de mi alcance de comprensión, pero el título me recordó un experimento que hice al crear un renderizador 3D sencillo
  Después de fracasar varias veces intentando aprender álgebra lineal, en la ducha se me ocurrió que una rotación 3D no era más que tres rotaciones 2D, y eso ya lo sabía. Más o menos una hora después, ya tenía un renderizador 3D de wireframe con perspectiva
  Recomiendo que todos lo intenten