Un caso de creación de un editor de diagramas interactivo con álgebra lineal

• A medida que Schemio fue sumando funciones para jerarquizar figuras y unirlas entre sí, la conversión entre coordenadas locales y coordenadas globales se volvió un problema central del editor
• El enfoque inicial, que aplicaba fórmulas directamente siguiendo la cadena de padres, se volvió difícil de mantener cuando se incorporaron el escalado y los puntos de pivote
• Al unificar traslación, rotación y escalado en matrices de transformación 3×3, se pueden componer varias transformaciones en una sola y calcular de forma consistente las transformaciones acumuladas en una estructura jerárquica
• Para convertir coordenadas globales de vuelta a coordenadas relativas al objeto, se usa la matriz inversa A⁻¹ de la matriz de transformación completa, lo que permite obtener con precisión la posición del clic o el punto de conexión de un conector
• Al montar o desmontar un objeto bajo otro padre, hay que recalcular los nuevos valores locales para preservar su posición y rotación en pantalla y así evitar movimientos bruscos

---

Los problemas que surgieron cuando Schemio se expandió como editor jerárquico

• Schemio comenzó como un editor de diagramas interactivo que permitía crear, mover, redimensionar y rotar figuras
• Cada figura tiene una estructura area compuesta por x, y, w, h, r
  • x, y: posición en coordenadas globales
  • w, h: ancho y alto
  • r: ángulo de rotación
• Para unir figuras entre sí y crear interacciones complejas, se agregó a cada objeto un arreglo childItems y se introdujo una estructura jerárquica de ítems
• Al igual que la función de agrupación de los editores de gráficos vectoriales comunes, mover un objeto puede mover también los objetos conectados, pero Schemio apunta a animaciones y comportamientos personalizados que mezclan un editor de diagramas con un motor de juegos

El cálculo de coordenadas no se resuelve solo con el renderizado SVG

• En SVG, cuando se anidan elementos, el navegador puede procesar las transformaciones padre-hijo durante la etapa de renderizado
• Schemio, además del renderizado, también debe calcular directamente conexiones de conectores, montaje y desmontaje de objetos e interacciones personalizadas
• Estas funciones requieren transformaciones entre las coordenadas locales de un objeto y las coordenadas globales de toda la escena
• Al principio, se recorría la cadena de padres y se aplicaban transformaciones con fórmulas simples; luego se optimizó cacheando las transformaciones de los padres
• Con la incorporación del escalado y los puntos de pivote, la combinación de fórmulas basada solo en traslación y rotación llegó a su límite

La complejidad añadida por el escalado y los puntos de pivote

• El escalado es una función para ajustar dinámicamente el tamaño de los objetos y, en Schemio, cumple un rol importante para cargar diagramas externos de forma dinámica
• El punto de pivote define el centro de rotación de un objeto
• Se agregaron cuatro propiedades al area del objeto
  • px, py: punto de pivote relativo al ancho y al alto
  • sx, sy: factores de escalado en los ejes x e y
• Al definir el punto de pivote como un valor relativo, el pivote también se ajusta cuando el usuario cambia el tamaño de la figura
• Combinar directamente traslación, rotación, escalado y corrección del pivote se vuelve cada vez más difícil de gestionar a medida que aumentan los requisitos

Unificar las transformaciones 2D con matrices

• En gráficos 2D y 3D, la traslación, la rotación y el escalado pueden representarse como matrices
• Un punto 2D se maneja como una matriz 3×1, y una transformación como una matriz 3×3
• Al multiplicar una matriz de transformación 3×3 por una matriz de punto 3×1 se obtiene el punto transformado 3×1
• Las matrices básicas de transformación se dividen así
  • Matriz identidad: no realiza ninguna transformación
  • Matriz de traslación: desplaza la posición
  • Matriz de rotación: rota según un ángulo
  • Matriz de escalado: ajusta el tamaño
• Para combinar varias transformaciones, se multiplican las matrices de transformación y se fusionan en una sola transformación

Cómo acumular transformaciones en una estructura jerárquica

• La transformación final de un objeto incluye no solo su propia transformación, sino también las transformaciones de sus objetos padre
• Al recorrer la jerarquía y multiplicar la matriz de transformación de cada objeto, se puede construir la matriz de transformación completa del objeto actual
• Si se define la matriz de transformación del objeto actual como Ai y la matriz de transformación del objeto padre como A(i-1), la transformación jerárquica se acumula como el producto de la transformación del padre y la transformación del objeto actual
• En la fórmula completa, es importante el orden: mover el objeto según el punto de pivote, aplicar rotación y escalado, y luego devolverlo
• Si no se considera el pivote, el objeto parece rotar alrededor de la esquina superior izquierda en lugar del pivote seleccionado
• La corrección del pivote debe aplicarse después de la matriz de escalado para que el escalado también parezca ocurrir respecto del punto de pivote

Cálculos para pasar entre coordenadas globales y locales

• Para ir de coordenadas locales a coordenadas globales, se multiplica el punto por la matriz de transformación completa
• A la inversa, para convertir coordenadas globales a coordenadas locales del objeto, se usa la matriz inversa de la matriz de transformación completa
• Si se agrupa la transformación completa en una matriz A, el punto global se expresa como el producto de A por el punto local
• No existe la división de matrices, pero si se multiplica A⁻¹ por la izquierda, A⁻¹A se convierte en la matriz identidad y se puede obtener el punto local
• Esta transformación es necesaria para encontrar, respecto de la esquina superior izquierda del objeto, el punto donde el usuario hizo clic sobre un objeto transformado, o para pegar un conector en la posición exacta

Preservar la posición al montar y desmontar

• Uno de los problemas difíciles de la función jerárquica fue el montaje y desmontaje de objetos
• Hay dos formas de unir un objeto a otro
  • Arrastrar un objeto en la escena y soltarlo sobre otro objeto
  • Reorganizar la jerarquía en el panel Item Selector
• Si solo se cambia la jerarquía, la posición del objeto se interpreta como coordenadas relativas al nuevo padre, lo que provoca que salte hacia arriba o hacia abajo en la pantalla
• Para evitarlo, hay que recalcular la nueva posición y rotación del objeto arrastrado

• Paso 1: guardar la posición global existente

  • Primero se guarda la posición global de la esquina superior izquierda del objeto antes de moverlo
  • En el código de ejemplo, se obtiene la coordenada global de la esquina superior izquierda del objeto con worldPointOnItem(0, 0, item)
  • worldPointOnItem se implementa usando la fórmula de transformación matricial derivada antes

• Paso 2: corrección de la rotación

  • La rotación de un objeto se define respecto del padre, por lo que si el padre cambia también hay que corregir la rotación del objeto arrastrado
  • La función worldAngleOfItem transforma la esquina superior izquierda y la esquina superior derecha del objeto a coordenadas globales, y luego calcula el ángulo que forma el eje x local del objeto con el eje x global
  • Se compara el ángulo de rotación global del padre anterior con el del nuevo padre para ajustar la rotación del objeto
  • item.area.r += previousParentWorldAngle - newParentWorldAngle
  • Con este cálculo, la rotación en pantalla del objeto se mantiene aunque cambie el padre

• Paso 3: preservar la posición

  • Después de mover el objeto bajo el nuevo padre, hay que calcular las nuevas coordenadas locales para que permanezca en la misma posición en pantalla
  • La función findTranslationMatchingWorldPoint calcula el valor de traslación necesario para que un punto local específico coincida con el punto global deseado
  • Si hay un resultado calculado, se actualizan area.x y area.y del objeto con los nuevos valores
  • Con este enfoque, aunque se cambie la jerarquía arrastrando un objeto sobre otro, su posición en pantalla se mantiene

Obtener el nuevo valor de traslación con la matriz inversa

• Encontrar el nuevo valor de traslación equivale a encontrar la matriz de traslación At del objeto cuando se conocen un punto global Pw y un punto local PL
• Las transformaciones ya conocidas del padre, el pivote, la rotación y el escalado pueden agruparse en una matriz A
• La ecuación se reorganiza usando la matriz inversa de la matriz de transformación del padre, pero como una matriz 3×1 no es una matriz cuadrada, no se le puede aplicar una inversa de la misma manera
• En su lugar, se desarrolla el determinante para separar los componentes de traslación x, y necesarios
• Al aplicar este cálculo, cuando el objeto arrastrado se mueve a un nuevo padre, su posición y rotación se mantienen de forma natural, evitando saltos o distorsiones extrañas

Código y demo

• La implementación de Schemio se puede consultar en el repositorio de GitHub ishubin/schemio
• Para usarlo directamente, se pueden crear diagramas interactivos o prototipos de apps en schem.io
• Además de las transformaciones matriciales, Schemio incluye otros temas matemáticos como curvas de Bézier, cálculo diferencial y quadtrees para optimización de rendimiento

[GN⁺]

Comentarios de Hacker News

• No conocía Schemio, está genial: https://schem.io/
  Se ve y se siente muy pulido, y aunque no lo destacan mucho, es open source: https://github.com/ishubin/schemio

  • Schemio está publicado como open source excepto por la parte de backend de https://schem.io
    El código del frontend está completamente abierto y también puedes alojar tu propio servidor. Pero en ese caso solo usa el sistema de archivos como almacenamiento, así que no hay base de datos ni gestión de usuarios
  • Me gusta la forma en que puedes hacer zoom hacia un diagrama más detallado y luego volver a alejarte fácilmente
    Esto era justo lo que quería en Obsidian, pero no era tan pulido como Schemio

• Las matrices de transformación fueron popularizadas por Adobe PostScript en los años 80, y SVG tomó prestadas muchas partes del modelo de imagen de PostScript
  Para el uso de matrices 2D en PostScript, se pueden ver estos recursos
  https://personal.math.ubc.ca/~cass/graphics/text/old.pdf/las...
  https://scientificgems.wordpress.com/2014/11/28/mathematics-...

  • No sé si diría que Adobe las popularizó; las matrices de transformación son simplemente algo que se aprende en álgebra, ¿no?

• También valdría la pena buscar sobre coordenadas homogéneas: https://en.wikipedia.org/wiki/Homogeneous_coordinates

  • Como autor del artículo, gracias por la recomendación
    Definitivamente lo voy a leer cuando tenga tiempo y, al echarle un vistazo rápido, parece que también hay una sección sobre las matrices de transformación que estaba usando

• Resume bien el proceso de crear un editor, y también sirve como buen resumen de álgebra lineal
  Pero ¿acaso no todos los editores usan álgebra lineal?

  • Técnicamente, se puede decir que todos los editores gráficos dependen del álgebra lineal para varios propósitos
    Pero alguien que desarrolla algo así por primera vez no ve todos los problemas como algo obvio, así que quería compartir las dificultades que encontré desde el punto de vista matemático. Ya estaba usando álgebra lineal, pero el punto clave fue cuánto simplificaban los cálculos las matrices
    Además, si dependes del renderizado SVG, puedes salir adelante solo con código sin pensar demasiado en la matemática relacionada. Por ejemplo, si no hubiera introducido una jerarquía de objetos, casi no habría tenido que preocuparme por la matemática. SVG se encarga de todas las transformaciones, y ni siquiera tienes que saber que existen las matrices o que se pueden usar 1:1 en objetos SVG. Arrastrar objetos sin jerarquía también habría sido mucho más fácil: habría bastado con cambiar translate(x,y) dentro del atributo transform de SVG

• Vale la pena revisar el framework QGraphicsView: https://doc.qt.io/qt-6/graphicsview.html
  Está entre los frameworks gráficos más potentes que he usado. Además de transformaciones escena-objeto con jerarquías de objetos, ofrece muchas herramientas potentes para renderizar escenas complejas e interactivas
  Lamentablemente, no he encontrado en la web una alternativa que funcione tan bien como QGVF

• Schemio se ve bien
  Estoy creando muchos diagramas de flujo con Claude, y Claude los genera en Mermaidjs y los renderizo en el navegador. Como la función de acercar/alejar desde el flujo hacia una secuencia se ve mejor, quiero intentar hacer algo parecido también con Schemio

• Al usar matrices homogéneas 3x3 para traslación 2D, es genial que la traslación 2D en realidad sea un cizallamiento 3D a lo largo del plano z = 1
  https://youtu.be/AheaTd_l5Is?t=263

• Relacionado con esto, https://webglfundamentals.org/webgl/lessons/webgl-scene-grap... y todo https://webglfundamentals.org son buenas lecturas, y también una base sólida como introducción a las jerarquías de transformación

• Tanto el artículo como el software son muy interesantes
  Personalmente estaba buscando software open source sólido para diagramas, y curiosamente Schemio nunca había aparecido en mi radar
  También tengo la sensación de que para transformaciones y animaciones sería más intuitivo usar álgebra geométrica en lugar de álgebra lineal
  [1] Projective Geometric Algebra:
  https://projectivegeometricalgebra.org/

• Me pregunto si al mover un objeto con muchos hijos no se vuelve costoso tener que actualizar el término A(i-1) de todos los hijos en cada frame, y bajar recursivamente hasta los nietos
  ¿O no es tan grave para figuras de tamaño razonable?

  • Ante cualquier movimiento de un ancestro, la matriz de transformación de todos los hijos debajo de él debe actualizarse cada vez
    Aun así, hasta ahora no hay una degradación de rendimiento perceptible. Por ahora solo hago esos cálculos por si se necesitan, y como no afectan a los elementos SVG reales, no hace falta actualizar los elementos SVG. La razón para recalcular esta matriz de transformación es que, al reajustar conectores adjuntos o manejar lógica basada en posición, puede ser necesario conocer las coordenadas local-mundo de un objeto específico