Um caso de criação de um editor interativo de diagramas com álgebra linear

• À medida que o Schemio ganhou mais recursos para hierarquizar formas e conectá-las entre si, a conversão entre coordenadas locais e coordenadas globais se tornou o problema central do editor
• A abordagem inicial, que aplicava fórmulas manualmente ao longo da cadeia de pais, ficou difícil de manter quando entraram escalonamento e ponto de pivô
• Ao unificar translação, rotação e escalonamento em matrizes de transformação 3×3, é possível compor várias transformações em uma só e calcular de forma consistente as transformações acumuladas da hierarquia
• Ao converter coordenadas globais de volta para coordenadas relativas ao objeto, usa-se a matriz inversa A⁻¹ da transformação total para encontrar com precisão a posição de clique ou o ponto de conexão de um conector
• Ao montar ou desmontar um objeto em outro pai, é preciso recalcular os novos valores locais para preservar posição e rotação na tela e evitar saltos visuais

---

Problemas que surgiram quando o Schemio evoluiu para um editor hierárquico

• Schemio começou como um editor interativo de diagramas com suporte à criação, movimentação, redimensionamento e rotação de formas
• Cada forma tem uma estrutura area composta por x, y, w, h, r
  • x, y: posição no sistema de coordenadas globais
  • w, h: largura e altura
  • r: ângulo de rotação
• Para conectar formas entre si e criar interações complexas, foi adicionado um array childItems a cada objeto, introduzindo uma hierarquia de itens
• Como no recurso de agrupamento de editores vetoriais em geral, mover um objeto pode mover junto os objetos conectados, mas o Schemio busca animações e comportamentos personalizados que misturam editor de diagramas com motor de jogo

Cálculo de coordenadas que não se resolve só com renderização SVG

• Em SVG, ao aninhar elementos, o navegador pode tratar as transformações de pai e filho na etapa de renderização
• No Schemio, além da renderização, também é preciso calcular diretamente conexão de conectores, montagem e desmontagem de objetos e interações personalizadas
• Esses recursos exigem conversões entre as coordenadas locais do objeto e as coordenadas globais de toda a cena
• No início, a transformação era aplicada com fórmulas simples percorrendo a cadeia de pais, e depois isso foi otimizado com cache das transformações dos pais
• Quando escalonamento e ponto de pivô foram adicionados, a combinação de fórmulas que assumia apenas translação e rotação chegou ao limite

Como escalonamento e ponto de pivô aumentaram a complexidade

• Escalonamento é o recurso de ajustar dinamicamente o tamanho do objeto, e no Schemio ele tem papel importante no carregamento dinâmico de diagramas externos
• O ponto de pivô define o centro de rotação do objeto
• Quatro propriedades foram adicionadas à area do objeto
  • px, py: ponto de pivô relativo à largura e à altura
  • sx, sy: fatores de escala nos eixos x e y
• Ao manter o ponto de pivô como valor relativo, o pivô também se ajusta quando o usuário altera o tamanho da forma
• Combinar manualmente translação, rotação, escalonamento e correção de pivô fica cada vez mais difícil de manter conforme os requisitos crescem

Unificando transformações 2D com matrizes

• Em gráficos 2D e 3D, translação, rotação e escalonamento podem ser representados por matrizes
• Um ponto 2D é tratado como uma matriz 3×1, e a transformação como uma matriz 3×3
• Ao multiplicar a matriz de transformação 3×3 pela matriz de ponto 3×1, obtém-se o ponto transformado 3×1
• As matrizes de transformação básicas se dividem assim
  • matriz identidade: não aplica nenhuma transformação
  • matriz de translação: move a posição
  • matriz de rotação: gira conforme o ângulo
  • matriz de escalonamento: ajusta o tamanho
• Ao combinar várias transformações, multiplica-se as matrizes para reuni-las em uma única transformação

Como acumular transformações em uma estrutura hierárquica

• A transformação final de um objeto inclui não só sua própria transformação, mas também as transformações dos objetos pais
• Ao percorrer a hierarquia e multiplicar as matrizes de transformação de cada objeto, é possível construir a matriz de transformação total do objeto atual
• Se a matriz de transformação do objeto atual for Ai e a do pai for A(i-1), a transformação hierárquica se acumula pelo produto entre a transformação do pai e a do objeto atual
• Na fórmula completa, a ordem importa: primeiro desloca-se o objeto em relação ao ponto de pivô, depois aplicam-se rotação e escalonamento, e por fim faz-se o retorno
• Sem considerar o pivô, o objeto parece girar em torno do canto superior esquerdo, e não do pivô escolhido
• A correção de pivô precisa ser aplicada depois da matriz de escalonamento para que o escalonamento também pareça acontecer em torno do ponto de pivô

Cálculos para ir e voltar entre coordenadas globais e locais

• Para ir de coordenadas locais para globais, multiplica-se o ponto pela matriz de transformação total
• No sentido contrário, para converter coordenadas globais em coordenadas locais do objeto, usa-se a matriz inversa da transformação total
• Se toda a transformação for agrupada na matriz A, o ponto global pode ser expresso como o produto entre A e o ponto local
• Não existe divisão de matrizes, mas ao multiplicar A⁻¹ pela esquerda, A⁻¹A vira a matriz identidade e o ponto local é obtido
• Essa conversão é necessária para descobrir, por exemplo, a coordenada relativa ao canto superior esquerdo do objeto onde o usuário clicou em um objeto transformado, ou para fixar um conector na posição exata

Preservando a posição ao montar e desmontar

• Um dos problemas mais difíceis dos recursos hierárquicos foi o mount e o unmount de objetos
• Há duas formas de anexar um objeto a outro
  • arrastar o objeto na cena e soltá-lo sobre outro objeto
  • reorganizar a hierarquia no painel Item Selector
• Se só a hierarquia mudar, a posição do objeto passa a ser interpretada no sistema de coordenadas do novo pai, causando saltos para cima ou para baixo na tela
• Para evitar isso, é preciso recalcular a nova posição e rotação do objeto arrastado

• Etapa 1: salvar a posição global atual

  • Primeiro, salva-se a posição global do canto superior esquerdo do objeto antes da mudança
  • No código de exemplo, worldPointOnItem(0, 0, item) é usado para obter a coordenada global do canto superior esquerdo do objeto
  • worldPointOnItem é implementada com a fórmula de transformação por matriz derivada anteriormente

• Etapa 2: corrigir a rotação

  • Como a rotação do objeto é definida em relação ao pai, quando o pai muda a rotação do objeto arrastado também precisa ser corrigida
  • A função worldAngleOfItem converte os cantos superior esquerdo e superior direito do objeto em coordenadas globais e calcula o ângulo entre o eixo x local do objeto e o eixo x global
  • Compara-se o ângulo de rotação global do pai anterior com o do novo pai para ajustar a rotação do objeto
  • item.area.r += previousParentWorldAngle - newParentWorldAngle
  • Com esse cálculo, a rotação visível do objeto é preservada mesmo com a troca de pai

• Etapa 3: preservar a posição

  • Mesmo depois de mover o objeto para baixo do novo pai, é preciso calcular novas coordenadas locais para que ele permaneça na mesma posição na tela
  • A função findTranslationMatchingWorldPoint calcula os valores de translação necessários para que um ponto local específico coincida com o ponto global desejado
  • Se houver resultado calculado, area.x e area.y do objeto são atualizados com os novos valores
  • Assim, mesmo ao arrastar um objeto para outro e mudar a hierarquia, sua posição visual na tela é mantida

Encontrando novos valores de translação com a matriz inversa

• Encontrar os novos valores de translação significa resolver o problema de achar a matriz de translação At do objeto quando são dados o ponto global Pw e o ponto local PL
• As matrizes já conhecidas de transformação do pai, pivô, rotação e escalonamento podem ser reunidas em uma única matriz A
• A fórmula pode ser reorganizada com a matriz inversa da transformação do pai, mas como a matriz 3×1 não é uma matriz quadrada, não dá para aplicar a inversa exatamente da mesma forma
• Em vez disso, expande-se o determinante da matriz para separar os componentes de translação x e y necessários
• Aplicando esse cálculo, o objeto arrastado mantém posição e rotação de forma natural ao ser movido para um novo pai, evitando saltos estranhos ou distorções

Código e demo

• A implementação do Schemio pode ser vista no repositório GitHub ishubin/schemio
• Para usar diretamente, é possível criar diagramas interativos ou protótipos de apps em schem.io
• Além de transformações por matriz, o Schemio também aborda outros temas matemáticos, como curvas de Bézier, cálculo diferencial e quadtrees para otimização de desempenho

[GN⁺]

Comentários do Hacker News

• Nunca tinha ouvido falar do Schemio, mas parece muito legal: https://schem.io/
  A aparência e a usabilidade são bem polidas e, embora isso não seja muito destacado, é open source: https://github.com/ishubin/schemio

  • O Schemio é open source, exceto pela parte de backend do https://schem.io
    O código do frontend é totalmente aberto e você também pode hospedar seu próprio servidor. Nesse caso, porém, ele usa apenas o sistema de arquivos como armazenamento, então não há banco de dados nem gerenciamento de usuários
  • Gosto da forma como dá para dar zoom em diagramas mais detalhados e depois voltar facilmente
    Era esse tipo de recurso que eu queria no Obsidian, mas não era tão fluido quanto no Schemio

• Matrizes de transformação foram popularizadas pelo Adobe PostScript nos anos 1980, e o SVG herdou bastante do modelo de imagem do PostScript
  O uso de matrizes 2D no PostScript pode ser visto nos materiais abaixo
  https://personal.math.ubc.ca/~cass/graphics/text/old.pdf/las...
  https://scientificgems.wordpress.com/2014/11/28/mathematics-...

  • Não sei se dá para dizer que a Adobe popularizou isso; matrizes de transformação não são simplesmente algo que se aprende em álgebra?

• Talvez valha a pena procurar também por coordenadas homogêneas: https://en.wikipedia.org/wiki/Homogeneous_coordinates

  • Como autor do texto, obrigado pela recomendação
    Vou ler com certeza quando tiver tempo e, dando uma olhada rápida, parece estar relacionado às matrizes de transformação que eu estava usando

• O texto resume bem o processo de criar o editor e também funciona como um bom resumo de álgebra linear
  Mas todo editor não usa álgebra linear?

  • Tecnicamente, dá para dizer que todo editor gráfico depende de álgebra linear para vários propósitos
    Mesmo assim, para quem está desenvolvendo algo assim pela primeira vez, nem todos os problemas parecem óbvios, então eu queria compartilhar as dificuldades que enfrentei do ponto de vista matemático. Eu já estava usando álgebra linear, mas o ponto principal foi o quanto as matrizes simplificaram os cálculos
    Além disso, se você depender da renderização em SVG, dá para passar por isso só com código sem pensar muito na matemática envolvida. Por exemplo, se eu não tivesse introduzido uma hierarquia de objetos, quase não precisaria me preocupar com a matemática. O SVG cuidaria de todas as transformações, e eu nem precisaria saber que matrizes existem ou que podem ser aplicadas 1:1 aos objetos SVG. Arrastar objetos sem hierarquia também seria muito mais simples: bastaria mudar o translate(x,y) dentro do atributo transform do SVG

• Vale a pena dar uma olhada no framework QGraphicsView: https://doc.qt.io/qt-6/graphicsview.html
  Está entre os frameworks gráficos mais poderosos que já usei. Além das transformações de cena-objeto com hierarquia de objetos, ele também oferece muitas ferramentas fortes para renderizar cenas complexas e interativas
  Infelizmente, ainda não encontrei na web uma alternativa que funcione tão bem quanto o QGVF

• O Schemio parece muito bom
  Tenho criado muitos fluxogramas com o Claude, que gera em Mermaidjs e renderiza no navegador. A função de ampliar e reduzir de fluxo para sequência parece melhor, então queria tentar fazer algo parecido também no Schemio

• É legal que, ao usar matrizes homogêneas 3x3 para translação em 2D, a translação 2D na verdade seja um cisalhamento 3D ao longo do plano z = 1
  https://youtu.be/AheaTd_l5Is?t=263

• Sobre isso, https://webglfundamentals.org/webgl/lessons/webgl-scene-grap... e o site https://webglfundamentals.org como um todo são ótimas leituras e também servem como uma introdução sólida à hierarquia de transformações

• Tanto o texto quanto o software são muito interessantes
  Eu estava procurando um software open source robusto para diagramas e, curiosamente, o Schemio nunca tinha aparecido no meu radar
  Também tenho a sensação de que, para transformações e animações, usar álgebra geométrica seria mais intuitivo do que álgebra linear
  [1] Projective Geometric Algebra:
  https://projectivegeometricalgebra.org/

• Ao mover um objeto com muitos filhos, não ficaria caro ter de atualizar o termo A(i-1) de todos os filhos a cada frame e continuar descendo pelos netos e assim por diante?
  Ou, em formas de tamanho razoável, isso não chega a ser um grande problema?

  • Independentemente do movimento de qualquer ancestral, a matriz de transformação de todos os filhos abaixo dele precisa mesmo ser atualizada toda vez
    Ainda assim, até agora não houve nenhuma queda de desempenho perceptível. No momento, isso é calculado apenas para o caso de ser necessário e não afeta os elementos SVG reais, então não é preciso atualizar os elementos SVG. O motivo para recalcular essa matriz de transformação é que, ao reajustar conectores anexados ou processar lógica baseada em posição, pode ser necessário saber as coordenadas local-mundo de um determinado objeto