Mãe, nem precisa de matrizes

• Um experimento de aplicar PGA Euclidiana até o fim em um renderizador forward compatível com glTF, no lugar das matrizes 4x4 usadas quase por inércia em gráficos 3D
• Rotação e translação são representadas por um motor PGA de 8 floats, e a composição geral de motores usa 48 multiplicações e 40 somas, menos que as 64 multiplicações e 48 somas da multiplicação de matrizes 4x4
• A transformação de pontos fica mais cara que com matriz se expandida de forma simples, mas com o produto sanduíche usando a condição de normalização ela cai para 21 multiplicações e 18 somas, e a transformação de direção e de direções de base fica ainda mais barata
• No normal mapping em tangent space, normal e tangent são substituídos por um tangentRotor, reduzindo os dados de vértice de 12 floats para 9 floats, enquanto o custo de transformação para world-space fica em um nível parecido com o de matrizes: 47 multiplicações e 38 somas
• Para funcionar com conteúdo glTF real, é preciso converter matrizes em motores no carregamento e rastrear a escala uniforme em um float separado; escala não uniforme exige tratamento limitado ou um caminho alternativo com matriz 4x4

---

Um renderizador forward sem matrizes feito com PGA

• O projeto é Look, Ma, No Matrices e tem como objetivo implementar um renderizador forward sem matrizes
• Desde a SIGGRAPH de 2019, Álgebra Geométrica, especialmente a PGA Euclidiana, vem recebendo atenção nas comunidades de gráficos e machine learning, mas nos gráficos 3D tradicionais muitas vezes isso ficou só em chamar dual quaternion de motor PGA
• Esta implementação integra a álgebra PGA em um engine 3D compatível com glTF, reorganizando várias partes do pipeline gráfico em torno de PGA em vez de apenas trocar nomes algébricos
• A implementação de referência é o visualizador glTF da Khronos e está mais para um experimento de substituir matrizes sem concessões do que para uma implementação de desempenho máximo
  • No fim, uma solução híbrida provavelmente é a melhor escolha

Por que desconfiar de matrizes 4x4

• Matrizes 4x4 tiveram papel central por muito tempo nas APIs gráficas e no pipeline de função fixa da GPU, e ainda são a ferramenta básica do renderizador forward comum
• As GPUs modernas se parecem mais com processadores escalares programáveis do que com pipelines de função fixa, então uma representação centrada em matrizes não é necessariamente obrigatória
• Em engines 3D reais, muitas matrizes contêm apenas rotação e translação, ou seja, são matrizes ortogonais
• O manifold de motores PGA representa todo o movimento euclidiano com menor custo computacional e de memória, e também engloba quaternion e dual quaternion sem conversão

Representação de dados em PGA e operações básicas

• A álgebra PGA é gerada a partir de quatro vetores-base e0~e3
  • e1, e2, e3 correspondem respectivamente aos planos x=0, y=0, z=0
  • O vetor degenerado especial e0 representa o plano no infinito
• Nos shaders, são usados tipos embutidos do GLSL para aproveitar soma, subtração e multiplicação escalar sem sobrecarga de operadores
  • motor mat2x4
  • line mat2x3
  • point vec3
  • direction vec3
• A composição geral de motores PGA é feita com o produto geométrico
  • Multiplicação de matriz 4x4: 64 multiplicações, 48 somas
  • Composição geral de motor gp_mm: 48 multiplicações, 40 somas
• Em combinações especiais de transformações, dá para usar operações ainda mais baratas
  • gp_rr: 16 multiplicações, 12 somas
  • gp_tt: 0 multiplicações, 3 somas
  • gp_rt / gp_tr: 12 multiplicações, 8 somas
  • gp_rm / gp_mr: 32 multiplicações, 24 somas
  • gp_tm / gp_mt: 12 multiplicações, 12 somas

Otimização da transformação de ponto e direção

• Em PGA, ao transformar um ponto p com um motor M, usa-se o produto sanduíche M p M̃
• A expansão simples custa 33 multiplicações e 29 somas, acima das 16 multiplicações e 12 somas de um produto matriz-vetor
• Reorganizando a expressão com base no fato de que um motor normalizado satisfaz M M̃ = 1, a transformação de ponto cai para 21 multiplicações e 18 somas
• Direções, ou seja, pontos no infinito, são ainda mais baratas porque o coeficiente implícito e123 é 0
  • Transformação de direção geral: 18 multiplicações, 12 somas
  • Transformação de direção de base, por exemplo no eixo x, pode cair para 6 multiplicações e 4 somas
• Essa otimização para direções de base sustenta mais adiante a ideia de que matriz nem sempre é a forma mais rápida de tratar tangent frames

Normalização, raiz quadrada e mapas exponencial/logarítmico

• A pseudonorma quadrada de um motor PGA, M M̃, é um Número de Study da forma a + b e0123
• Normalizar aqui não é só normalizar um vetor, mas um procedimento que garante que o motor resultante represente uma transformação ortonormal
  • Custo da implementação geral de normalização de motor: 21 multiplicações, 5 somas
  • Em translação pura ou rotação pura, dá para usar versões mais eficientes
• A transformação rígida entre dois pontos, duas retas ou dois planos a, b pode ser expressa como M = sqrt(b / a)
  • O produto geométrico ba entre dois elementos do mesmo tipo produz um motor equivalente ao dobro da transformação de a para b
  • sqrt M pode ser calculado na forma normalize(1 + M)
• O logaritmo de um motor PGA é uma reta escalada, e essa reta escalada pode gerar um motor de rotação por exponenciação
• O mapa exponencial de uma matriz 4x4 geral é numericamente caro, mas no manifold de motores PGA existe uma forma fechada eficiente

Inverso e fatoração de motor

• A Álgebra Geométrica permite calcular com eficiência o inverso de objetos normalizados
  • inverso de plano: ele mesmo
  • inverso de reta: troca de sinal
  • inverso de ponto: troca de sinal
  • inverso de motor: reversão
• Quando um bivetor geral não satisfaz a condição de Plücker e não representa uma única reta, o inverso é calculado com o inverso de Número de Study
• A implementação de renderização usa duas fatorações
  • Fatoração euclidiana: decompõe o motor em uma rotação em torno da origem seguida de uma translação
  • Fatoração invariante: decompõe o motor em translação e rotação comutativas, conhecida em 3D como teorema de Mozzi-Chasles
• Ao compor o tangent frame com o motor object-to-world, a fatoração euclidiana é útil porque o frame é invariante a translação

Matrizes glTF e tratamento de escala

• Para interoperar com conteúdo glTF existente, é preciso converter matrizes em motores PGA no momento do carregamento
• Uma matriz ortogonal 4x4 é convertida em motor usando seu isomorfismo com quaternion
  • Todas as matrizes e transformações importadas são convertidas em load time
• Motores PGA tratam transformações de corpo rígido, então não incluem escala
• Escala uniforme é invariante a rotação e translação, então é rastreada com um float por nó
  • A escala total de cada elemento é calculada multiplicando sua própria escala pela escala do pai
  • A escala total é aplicada aos vértices no load time ou na primeira etapa do vertex shader
  • Na translação, a escala do pai é aplicada no load time e nas atualizações de animação
• Em cerca de 400 arquivos glTF aleatórios, casos com animação de escala ficaram abaixo de 0,5%, enquanto escala uniforme fixa era bem comum
• Escala não uniforme é mais complicada porque não é invariante à rotação
  • Para tratar escala não uniforme geral, um caminho alternativo com matriz 4x4 acaba sendo inevitável
  • Nos exemplos glTF analisados, a escala não uniforme só apareceu em nós folha; nesse caso, ela é aplicada separadamente antes das demais transformações sem afetar as chaves de animação

Substituindo Model-View-Projection

• Um renderizador forward transforma a geometria da malha do object space para screen space e decide quais pixels cada triângulo cobre
• No pipeline comum, as matrizes model e view são substituídas por motores PGA
  • posição de vértice: sw_mp
  • direções de normal e tangent: sw_md
• A matriz de projeção normalmente tem só 5 entradas não nulas, então em vez de forçar uma versão em PGA, a implementação usa diretamente a expressão de projeção
• No lado da CPU, a atualização da hierarquia do scene graph passa de composição por matriz para composição por motor, reduzindo o volume de cálculo
• No lado da GPU, a transformação de vértices parece pior para motores numa comparação simples, mas isso muda ao alterar a representação do tangent frame

Otimização de normal mapping em tangent space

• Em uma malha comum com tangent space normal mapping, o vertex shader precisa transformar position, normal e tangent
• Como normal, tangent e bitangent formam um frame ortonormal, em PGA isso pode ser representado por um tangentRotor que leva o frame de base canônico ao tangent frame desejado
• Essa abordagem reduz o descritor de vértice
  • Antes: position 3 + normal 3 + tangent 4 + uv 2 = 12 floats
  • Com PGA: position 3 + tangentRotor 4 + uv 2 = 9 floats
  • Redução de 25% no número de floats por vértice
• O tangentRotor tem double cover, e o sinal do coeficiente escalar é alinhado ao flag clássico de handedness para distinguir k-reflection par/ímpar
  • Isso depende de zero com sinal, e o vertex shader extrai a handedness com sign(1/tangentRotor.x)
• Transformar position, normal e tangent com matriz 4x4 exige ao todo 48 multiplicações e 36 somas
• Na abordagem PGA, o tangent frame inteiro é transformado de uma vez e depois se extraem normal e tangent
  • composição do tangent frame: 16 multiplicações, 12 somas
  • extração de normal/tangent: 9 multiplicações, 8 somas
  • transformação de position: 21 multiplicações, 18 somas
  • 1 multiplicação para extrair handedness
  • total: 47 multiplicações, 38 somas
• O custo de transformação de vértices fica quase igual ao do método com matriz, enquanto o armazenamento da transformação cai de 32 floats para 8 floats

Restrições do fragment shader e de texturas baked

• Para carregar conteúdo existente, ainda é necessária uma matriz TBN na etapa de fragment shader
• Ferramentas de baking criam texturas de normal em tangent space interpolando normal e tangent de vértice sobre a face do triângulo e montando uma matriz TBN ortogonal em cada fragment
• A interpolação de vetores-base introduz o erro típico da abordagem com matrizes, e esse erro já fica embutido na textura
• Por isso, esta implementação extrai explicitamente os vetores normal e tangent a partir do tangentRotor
• Se também fosse possível controlar a ferramenta de baking, daria para passar o tangentRotor diretamente ao fragment shader, normalizá-lo e usá-lo na transformação da normal amostrada
  • não seria necessário montar a matriz TBN
  • a extração de normal/tangent no vertex shader deixaria de ser necessária
  • um varying a menos seria usado
  • a ortogonalização cara no fragment shader também seria eliminada

Skinning com motor e blending de animação

• Como o motor PGA é isomorfo a dual quaternion, ele se aplica naturalmente a skinning
• Depois de converter a inverse bind matrix em motor, os bone motors são misturados no mesmo padrão do dual quaternion skinning
• Os sinais das transformações misturadas são alinhados para seguir o arco mais curto, e a transformação resultante é normalizada novamente
• O blending de animação segue a mesma lógica na CPU, misturando diretamente motores PGA e normalizando o resultado

Resultado do experimento de substituir matrizes

• É possível implementar um renderizador forward compatível com glTF substituindo matrizes apenas com PGA
• A expectativa de que o custo de transformação seria maior não é tão simples quando se aplicam a representação por tangent frame e as otimizações do produto sanduíche
• No caso comum de tangent space normal mapping, a abordagem com motor PGA mantém o custo do vertex shader quase igual ao de matrizes enquanto reduz bastante o uso de memória por vértice
• O ganho de memória é especialmente grande: cabe cerca de 33% mais vértices no mesmo espaço de armazenamento
• A técnica pode ser aplicada em engines 3D existentes como um substituto drop-in, quase sem aumentar o custo do vertex shader e sem modificar o restante do pipeline

[GN⁺]

Opiniões no Hacker News

• Uma das minhas criadoras favoritas de matemática/gráficos no YouTube, Freya Holmér, fez há pouco tempo um vídeo introdutório excelente sobre álgebra geométrica: https://www.youtube.com/watch?v=htYh-Tq7ZBI&ab_channel=Freya...
  Se você se interessa por gráficos 3D, especialmente splines/curvas de Bézier, vale a pena ver todos os vídeos dela
  Pessoalmente, álgebra linear sempre foi difícil para mim, mas essa abordagem de álgebra de Clifford parece muito mais intuitiva

  • Foi uma apresentação realmente boa e me lembrou de https://enkimute.github.io/ganja.js/
    Essa biblioteca foi criada por enkimute, o autor do post original, e é bastante impressionante: um script de arquivo único, sem build, que ainda assim oferece suporte a álgebras em N dimensões e renderização
  • Achei que o texto fosse falar dela. Também gostei de ver os vídeos sobre splines e Bézier, e a apresentação vai direto ao ponto sem nunca parecer apressada
  • Nos comentários do YouTube também há explicações complementares e perguntas surpreendentemente boas
    Por exemplo, há explicações bem decentes sobre pontos que a Freya passa um pouco rápido ou omite, como a não comutatividade do produto

• A álgebra geométrica foi um mistério completo para mim por um tempo, até que finalmente entendi assim: é apenas multiplicação de polinômios, só que há quantidades em que a ordem da multiplicação importa e a tabela de multiplicação é estranha. Por exemplo, i*i = 1, i*j = -j*i
  A maioria dos materiais introdutórios faz o produto geométrico de dois vetores (x1*i + y1*j) * (x2*i + y2*j) parecer algo profundo e misterioso, mas na verdade é igual à expansão FOIL que se aprende em álgebra do primeiro ano:
  (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
  O valor dentro do primeiro parêntese é o produto interno familiar, e o valor dentro do segundo parêntese corresponde ao produto vetorial familiar, mas expresso como uma base de uma nova dimensão chamada i*j. E, ao contrário do produto vetorial, ele se generaliza para dimensões arbitrárias; na álgebra geométrica, isso é chamado de produto exterior
  Entendendo isso, coisas como derivar fórmulas de rotação ficam mais fáceis, porque dá para aplicar diretamente as técnicas aprendidas em álgebra à resolução de problemas geométricos

  • Em https://youtu.be/htYh-Tq7ZBI?si=lOmsCL2DoqUCQgh1&t=1540, citado em outro comentário, a Freya fez uma ótima explicação reduzindo os axiomas a um só
    Se você define o produto de um vetor por ele mesmo como o quadrado do comprimento desse vetor, todo o resto decorre de simples multiplicação de polinômios. É bem bonito
  • Essa explicação mostra um contraste interessante. Alguns dias atrás, alguém perguntou por que as aulas de matemática fazem os alunos calcular usando fórmulas em vez de ensinar como e por que as operações funcionam; aqui, o foco está em o que a operação faz, mais do que em por que ela é válida
    “Como funciona?” e “Por que funciona?” são duas perguntas que professores de matemática precisam equilibrar, e é difícil responder sempre bem às duas em um único curso
  • O segundo termo não é produto vetorial, mas sim produto da álgebra exterior, ou um bivetor. O produto vetorial só funciona em 3 dimensões, enquanto o produto da álgebra exterior funciona também em dimensões arbitrariamente maiores
    O produto vetorial de dois vetores em 3D é outro vetor perpendicular ao plano formado pelos dois vetores. Já o produto da álgebra exterior é um 2-vetor que varre o paralelogramo entre os dois vetores, isto é, um bivetor, e fica no plano em que os dois vetores estão. Em 3D, o vetor do produto vetorial é perpendicular a esse plano do bivetor
  • Uma das coisas que mais demora para aprender em matemática é que a maioria das coisas é definida da maneira mais simples possível
    Em particular, definir um produto bilinear m:V x V -> V sobre um espaço vetorial V é exatamente o mesmo que definir m apenas para pares de vetores da base. Se você chamar isso de “propriedade universal do produto tensorial”, provavelmente a reação será só “ah, entendi”

• É interessante que existam várias abordagens para interpolação de rotações, incluindo álgebra geométrica, quatérnios e até interpolação de matrizes inteiras: https://www.gamedev.net/tutorials/programming/math-and-physi...
  Mas, depois de otimizar o código à mão, o código final fica quase igual na maioria das abordagens. A diferença está em como você entende as regras e as possibilidades
  Pelo pouco que sei, a álgebra geométrica parece a abordagem mais consistente e poderosa. Ela é estranha e bem difícil de aceitar no começo, mas quem passa por essa barreira gosta
  Em contrapartida, todo mundo usa quatérnios e reclama que não os entende, dizendo que é preciso um livro inteiro para visualizá-los. Livros como 『Visualizing Quaternions』, de Andrew J. Hanson e Steve Cunningham

  • Não sou matemático e também não uso muita geometria no trabalho, mas eu estava aprendendo álgebra geométrica por diversão e, antes, já tinha tentado aprender quatérnios
    Álgebra geométrica é divertida, quatérnios não são. Sinto que entendi álgebra geométrica, mas com quatérnios, mesmo acompanhando aulas e exercícios, só tinha certeza de que não tinha entendido. Agora que sei um pouco de álgebra geométrica, finalmente sinto que também entendo quatérnios em alguma medida
  • 『Naive Lie Theory』 é um ótimo livro, e ensina quatérnios no primeiro capítulo
    https://www.goodreads.com/en/book/show/4419538

• Se este assunto te interessa, há bons slides que passam pelos conceitos de Grassman/Clifford/álgebra geométrica: http://www.terathon.com/gdc12_lengyel.pdf
  Há também outro bom site: https://mattferraro.dev/posts/geometric-algebra

• Também não dá para deixar de fora a excelente “A swift introduction to projective geometric algebra”, do Sudgy: https://www.youtube.com/watch?v=0i3ocLhbxJ4
  E o principal site de referência é https://bivector.net
  Você também pode participar do Discord da bivector, que tem mais de 1000 professores, pesquisadores e entusiastas: https://discord.gg/vGY6pPk

  • Eric Lengyel, o autor dessa apresentação, também escreveu Foundations of Game Engine Development, Volume 1: Mathematics, e o capítulo 4 trata do mesmo tema

• Sinceramente, nunca gostei muito do modo como a álgebra geométrica, se você não tomar cuidado com o que está multiplicando por quê, acaba gerando todo tipo de elemento misto
  Também parece difícil de lidar com o fato de que algo que era um espaço n-dimensional pode passar a exigir até 2^n termos
  Parece que ela deveria lidar melhor com geometria, isto é, com o produto interno, mas nunca vi uma explicação convincente de por que não bastaria usar o produto exterior e o operador estrela de Hodge, ou um isomorfismo musical
  A “mágica” de transformar um bivetor u^v na rotação e^(u^v)t naquele plano é, essencialmente, usar um isomorfismo musical para transformar a 2-forma u^v em um endomorfismo linear e então entender e^(u^v)t como uma exponencial de matriz
  Outro exemplo recorrente é a possibilidade de escrever as equações de Maxwell como uma única equação, mas, usando formas diferenciais, já é possível resumi-las em duas equações que valem por motivos diferentes; então eu não entendi a utilidade de juntá-las em uma só

  • A ideia de que “algo que era um espaço n-dimensional passa a exigir até 2^n termos” às vezes é uma ilusão de economia
    Por exemplo, vetores normais se transformam de modo diferente de vetores de posição. Dá para representar os dois com a mesma estrutura de dados, mas você precisa acompanhar que tipo de vetor está dentro dela e espalhar casos especiais pelo código para tratá-los de formas diferentes
    A álgebra geométrica encara isso de frente: usa a base (i,j,k) para vetores e uma base separada (j*k, k*i, i*j) para outro tipo
    É um bom exemplo de como um espaço de dimensão mais alta pode ser, na prática, mais econômico em armazenamento do que um de dimensão mais baixa, no sentido de que uma equação é melhor do que duas ou quatro
    O campo elétrico difere do campo magnético de um modo bem parecido com a diferença entre vetores e bivetores. Você pode tratar campos elétricos e magnéticos como casos especiais em equações separadas, ou pode tratá-los de maneira uniforme com uma única abordagem
  • Os elementos mistos são justamente a parte importante
    Um quatérnio com w=1, x,y,z=0 é a identidade, e quatérnios como w=0, x=1 ou w=0, x=y=0.7 correspondem apenas a rotações de 180 graus
    Se você quer uma rotação arbitrária, precisa de uma combinação dos dois. É misturar “um pouco de rotação de 180 graus em torno desta reta” com “um pouco de rotação de 0 grau/identidade”. É exatamente isso que significa ter escalar e bivetor juntos
    Se você está tentando evitar misturas “com cuidado” usando produto exterior e produto interno, está usando a ferramenta de forma errada. O produto geométrico é o protagonista, e ele cria misturas excelentes
  • Concordo que a confusão já existe. A abordagem tradicional apenas varre essa confusão para baixo do tapete
    Por exemplo, se você está lidando com normais, precisa acompanhar pelo menos dois espaços n-dimensionais que se transformam de maneiras bem diferentes
    Representar pontos, planos, retas, normais, translações e rotações com um único tipo multivector e regras consistentes é bem libertador quando você entende. Eu mesmo ainda estou aprendendo

• A interpolação de animação mais abaixo é realmente incrível, mas acho que eu gostaria que os modelos no restante da página fossem um pouco menos agitados
  Matemática já é difícil o bastante sem pequenos elefantes líderes de torcida

  • Para mim é o contrário. Sem esse incentivo elefantino, eu não teria chegado até o fim da página

• Se o autor estiver lendo, seria bom definir a sigla PGA na primeira vez que ela aparecer

  • Para quem estiver curioso: PGA é projective geometric algebra, ou álgebra geométrica projetiva
    Você acrescenta um vetor de base nulo aos vetores de base do espaço em que está trabalhando. Isso permite representar algebricamente também objetos geométricos que não passam pela origem
  • Em especial, a parte em que “Fast PGA” foi escrito como FPGA foi bem confusa
  • Corrigido. mea maxima culpa

• Esse tipo de algoritmo é eficiente mesmo considerando GPUs?
  Tenho a impressão vaga de que GPUs são bem ajustadas para operações com matrizes, e fico me perguntando se, ao usar uma formulação em álgebra geométrica, você não perderia essa vantagem e, na prática, não ficaria à frente
  É um palpite de alguém que não entende muito, então gostaria que me corrigissem se eu estiver errado

  • É um equívoco muito comum achar que, como os padrões de GPU incluem multiplicação matriz-matriz e matriz-vetor, as empresas de GPU necessariamente aceleram essas operações
    Na prática, o núcleo inteiro de shaders já é SIMD, então isso não é algo que necessariamente dê para fazer. Algumas GPUs fazem, outras não
  • Ao programar, você precisa descobrir duas coisas: qual é a quantidade que quer calcular e qual é a forma mais eficiente de calculá-la
    PGA exige um esforço considerável para entender, mas é uma ótima forma de lidar com a primeira parte. De todo modo, normalmente é melhor tentar primeiro o método mais simples e fácil de implementar
    A implementação obtida ao resolver a primeira parte com PGA é suficiente para prototipar o restante do programa e fazer benchmarks para encontrar o gargalo real. Felizmente, na maioria dos casos, ela já é o método de cálculo mais rápido, ou rápida o bastante para não virar gargalo
    Mesmo que vire gargalo, ela dá uma compreensão profunda do problema que você está tentando resolver. Acho melhor ter essa compreensão antes de começar a cortar ciclos torcendo para ficar rápido o bastante
  • Este texto trata exatamente disso. Em resumo, em geral pode ficar em um nível parecido

• Isso parece uma briga por diferenças minúsculas no limite do progresso
  O fato de animação esquelética 3D ainda usar matrizes 4x4 na GPU significa que a matemática desenvolvida para esse fim em CPUs na época de Half-Life 1 ainda está na linha de frente. São 26 anos, de 1998 a 2024
  Daqui a 1000 anos, a animação 3D continuará igual

• Este texto está além da minha compreensão, mas o título me lembrou de um experimento em que fiz um renderizador 3D simples
  Depois de fracassar várias vezes tentando aprender álgebra linear, pensei no banho que rotação 3D é apenas três rotações 2D, e isso eu já sabia. Cerca de uma hora depois, eu tinha um renderizador 3D em wireframe com perspectiva
  Recomendo que todo mundo tente uma vez