Créer un éditeur de diagrammes interactif avec l’algèbre linéaire

 (medium.com/@ivan.ishubin)
2 points par GN⁺ 2024-12-19 | 1 commentaires | Partager sur WhatsApp
  • À mesure que Schemio a ajouté des fonctions pour hiérarchiser les formes et les attacher les unes aux autres, la conversion entre coordonnées locales et coordonnées monde est devenue un enjeu central de l’éditeur
  • L’approche initiale, qui appliquait directement des formules en remontant la chaîne des parents, est devenue difficile à maintenir avec l’arrivée du scaling et des points de pivot
  • En unifiant déplacement, rotation et scaling sous forme de matrices de transformation 3×3, on peut composer plusieurs transformations en une seule et calculer de manière cohérente les transformations cumulées d’une structure hiérarchique
  • Pour ramener des coordonnées monde dans le repère d’un objet, on utilise la matrice inverse A⁻¹ de la matrice de transformation complète afin de déterminer précisément la position d’un clic ou le point d’attache d’un connecteur
  • Lorsqu’un objet est monté sur un autre parent ou démonté, il faut recalculer ses nouvelles valeurs locales de façon à préserver sa position et sa rotation à l’écran, afin d’éviter les mouvements brusques

Les problèmes apparus lorsque Schemio est devenu un éditeur hiérarchique

  • Schemio a commencé comme un éditeur de diagrammes interactif prenant en charge la création, le déplacement, le redimensionnement et la rotation de formes
  • Chaque forme possède une structure area composée de x, y, w, h, r
    • x, y : position en coordonnées monde
    • w, h : largeur et hauteur
    • r : angle de rotation
  • Pour attacher des formes entre elles et créer des interactions complexes, un tableau childItems a été ajouté à chaque objet, introduisant une structure hiérarchique d’items
  • Comme la fonction de groupe d’un éditeur graphique vectoriel classique, déplacer un objet peut déplacer avec lui les objets qui lui sont liés, mais Schemio vise des animations et des comportements personnalisés à mi-chemin entre un éditeur de diagrammes et un moteur de jeu

Le rendu SVG ne suffit pas à résoudre les calculs de coordonnées

  • En SVG, lorsque des éléments sont imbriqués, le navigateur peut gérer les transformations parent-enfant au moment du rendu
  • Schemio doit toutefois calculer lui-même, au-delà du rendu, les connexions de connecteurs, le montage et le démontage d’objets, ainsi que les interactions personnalisées
  • Ces fonctionnalités nécessitent des transformations entre les coordonnées locales d’un objet et les coordonnées monde de toute la scène
  • Au départ, les transformations étaient appliquées avec des formules simples en parcourant la chaîne des parents, puis optimisées en mettant en cache les transformations des parents
  • Avec l’ajout du scaling et des points de pivot, les combinaisons de formules supposant seulement translation et rotation ont atteint leurs limites

La complexité accrue par le scaling et les points de pivot

  • Le scaling est une fonctionnalité qui ajuste dynamiquement la taille des objets et joue un rôle important dans Schemio pour charger dynamiquement des diagrammes externes
  • Le point de pivot définit le centre de rotation d’un objet
  • Quatre propriétés ont été ajoutées à l’area d’un objet
    • px, py : point de pivot relatif à la largeur et à la hauteur
    • sx, sy : facteurs de scaling dans les directions des axes x et y
  • Lorsque le point de pivot est exprimé comme une valeur relative, il s’ajuste aussi lorsque l’utilisateur modifie la taille de la forme
  • Combiner manuellement translation, rotation, scaling et correction du pivot devient de plus en plus difficile à gérer à mesure que les exigences augmentent

Unifier les transformations 2D avec des matrices

  • En graphisme 2D et 3D, translation, rotation et scaling peuvent tous être représentés par des matrices
  • Un point 2D est traité comme une matrice 3×1, et une transformation comme une matrice 3×3
  • En multipliant une matrice de transformation 3×3 par une matrice de point 3×1, on obtient le point transformé sous forme de matrice 3×1
  • Les matrices de transformation de base se répartissent ainsi
    • Matrice identité : n’applique aucune transformation
    • Matrice de translation : déplace la position
    • Matrice de rotation : effectue une rotation selon un angle
    • Matrice de scaling : ajuste la taille
  • Pour combiner plusieurs transformations, on multiplie les matrices de transformation afin de les fusionner en une seule transformation

Cumuler les transformations dans une structure hiérarchique

  • La transformation finale d’un objet inclut non seulement sa propre transformation, mais aussi celles de ses objets parents
  • En parcourant la hiérarchie et en multipliant la matrice de transformation de chaque objet, on peut construire la matrice de transformation complète de l’objet courant
  • Si l’on note Ai la matrice de transformation de l’objet courant et A(i-1) celle de son parent, la transformation hiérarchique s’accumule par le produit de la transformation du parent et de celle de l’objet courant
  • Dans la formule complète, l’ordre consistant à déplacer l’objet par rapport au point de pivot, à appliquer la rotation et le scaling, puis à le ramener, est important
  • Si l’on ne tient pas compte du pivot, l’objet semble tourner autour du coin supérieur gauche plutôt qu’autour du pivot choisi
  • La correction du pivot doit être appliquée après la matrice de scaling pour que le scaling semble lui aussi se produire autour du point de pivot

Calculs entre coordonnées monde et coordonnées locales

  • Pour passer des coordonnées locales aux coordonnées monde, on multiplie le point par la matrice de transformation complète
  • À l’inverse, pour convertir des coordonnées monde dans les coordonnées locales d’un objet, on utilise la matrice inverse de la matrice de transformation complète
  • Si l’on regroupe toute la transformation dans une matrice A, le point monde s’exprime comme le produit de A et du point local
  • Il n’existe pas de division matricielle, mais en multipliant par A⁻¹ à gauche, A⁻¹A devient la matrice identité, ce qui permet d’obtenir le point local
  • Cette transformation est nécessaire pour déterminer, par rapport au coin supérieur gauche de l’objet, le point sur lequel l’utilisateur a cliqué dans un objet transformé, ou pour attacher un connecteur à l’emplacement exact

Préserver la position lors du montage et du démontage

  • L’un des problèmes difficiles de la fonctionnalité hiérarchique a été le montage et le démontage des objets
  • Il existe deux façons d’attacher un objet à un autre
    • Faire glisser un objet dans la scène et le déposer sur un autre objet
    • Réorganiser la hiérarchie dans le panneau Item Selector
  • Si l’on ne fait que modifier la hiérarchie, la position de l’objet est interprétée dans le repère du nouveau parent, ce qui le fait sauter à l’écran
  • Pour éviter cela, il faut recalculer la nouvelle position et la nouvelle rotation de l’objet déplacé

  • Étape 1 : enregistrer l’ancienne position monde

    • On enregistre d’abord la position monde du coin supérieur gauche de l’objet avant le déplacement
    • Dans l’exemple de code, worldPointOnItem(0, 0, item) permet d’obtenir les coordonnées monde du coin supérieur gauche de l’objet
    • worldPointOnItem est implémentée avec la formule de transformation matricielle dérivée plus haut

  • Étape 2 : corriger la rotation

    • La rotation d’un objet étant définie par rapport à son parent, elle doit aussi être corrigée lorsque le parent change
    • La fonction worldAngleOfItem convertit le coin supérieur gauche et le coin supérieur droit de l’objet en coordonnées monde, puis calcule l’angle que forme l’axe x local de l’objet avec l’axe x du monde
    • On ajuste la rotation de l’objet en comparant l’angle de rotation monde de l’ancien parent avec celui du nouveau parent
    • item.area.r += previousParentWorldAngle - newParentWorldAngle
    • Ce calcul préserve la rotation apparente de l’objet à l’écran même lorsque son parent change

  • Étape 3 : préserver la position

    • Après le déplacement de l’objet sous le nouveau parent, il faut calculer ses nouvelles coordonnées locales pour qu’il reste au même endroit à l’écran
    • La fonction findTranslationMatchingWorldPoint calcule la translation nécessaire pour qu’un point local donné corresponde au point monde souhaité
    • Si un résultat est calculé, area.x et area.y de l’objet sont mis à jour avec les nouvelles valeurs
    • Ainsi, même si l’on change la hiérarchie en faisant glisser un objet sur un autre, sa position à l’écran est préservée

Trouver la nouvelle translation avec la matrice inverse

  • Trouver la nouvelle translation revient à chercher la matrice de translation At de l’objet à partir d’un point monde Pw et d’un point local PL
  • Les transformations déjà connues — parent, pivot, rotation et scaling — peuvent être regroupées dans une seule matrice A
  • On réorganise l’équation à l’aide de la matrice inverse de la transformation du parent, mais une matrice 3×1 n’étant pas carrée, on ne peut pas lui appliquer une inverse de la même manière
  • À la place, on développe le déterminant pour isoler les composantes de translation x et y nécessaires
  • En appliquant ce calcul, lorsqu’un objet déplacé passe sous un nouveau parent, sa position et sa rotation sont conservées naturellement, ce qui évite les sauts ou déformations étranges

Code et démo

  • L’implémentation de Schemio est disponible dans le dépôt GitHub ishubin/schemio
  • Pour l’utiliser directement, il est possible de créer des diagrammes interactifs ou des prototypes d’apps sur schem.io
  • Outre les transformations matricielles, Schemio couvre aussi d’autres sujets mathématiques comme les courbes de Bézier, le calcul différentiel et les quadtrees pour l’optimisation des performances

À lire aussi

1 commentaires

 
GN⁺ 2024-12-19
Commentaires sur Hacker News

  • Je ne connaissais pas Schemio, mais c’est sympa : https://schem.io/
    L’apparence et la prise en main sont très fluides, et même si ce n’est pas mis très en avant, c’est open source : https://github.com/ishubin/schemio

    • Schemio est publié en open source, à l’exception de la partie backend de https://schem.io
      Le code frontend est entièrement ouvert, et on peut aussi héberger soi-même le serveur. Dans ce cas, toutefois, seul le système de fichiers sert de stockage, donc il n’y a ni base de données ni gestion des utilisateurs.
    • J’aime bien la façon dont on peut zoomer vers un diagramme plus détaillé, puis dézoomer facilement
      C’est le genre de fonctionnalité que j’aurais voulu dans Obsidian, mais ce n’était pas aussi fluide que Schemio.

  • Les matrices de transformation ont été popularisées par Adobe PostScript dans les années 1980, et SVG a beaucoup emprunté au modèle d’imagerie de PostScript
    Pour l’utilisation des matrices 2D dans PostScript, voir les ressources ci-dessous
    https://personal.math.ubc.ca/~cass/graphics/text/old.pdf/las...
    https://scientificgems.wordpress.com/2014/11/28/mathematics-...

    • Dire qu’Adobe les a popularisées me semble discutable : les matrices de transformation, c’est simplement quelque chose qu’on apprend en algèbre, non ?

  • Ça vaudrait aussi le coup de regarder les coordonnées homogènes : https://en.wikipedia.org/wiki/Homogeneous_coordinates

    • Merci pour la recommandation, de la part de l’auteur
      Je compte bien lire ça quand j’aurai le temps ; en le parcourant rapidement, il semble aussi y avoir une section sur les matrices de transformation que j’utilisais.

  • Le processus de création de l’éditeur est bien résumé, et c’est aussi un bon résumé d’algèbre linéaire
    Mais tous les éditeurs n’utilisent-ils pas l’algèbre linéaire ?

    • Techniquement, on peut considérer que tous les éditeurs graphiques s’appuient sur l’algèbre linéaire à de nombreuses fins
      Cela dit, quand on développe ce genre de chose pour la première fois, tous les problèmes ne paraissent pas forcément évidents ; je voulais donc partager les difficultés rencontrées sous l’angle mathématique. J’utilisais déjà l’algèbre linéaire, mais l’essentiel était de voir à quel point les matrices simplifiaient les calculs.
      De plus, si l’on s’appuie sur le rendu SVG, on peut s’en sortir uniquement avec du code sans réfléchir en profondeur aux mathématiques sous-jacentes. Par exemple, si je n’avais pas introduit de hiérarchie d’objets, je n’aurais presque pas eu à me soucier des maths. SVG aurait géré toutes les transformations, et je n’aurais même pas eu besoin de savoir que les matrices existent, ni qu’elles peuvent s’appliquer en 1:1 aux objets SVG. Le glisser-déposer d’objets sans hiérarchie aurait aussi été beaucoup plus simple : il aurait suffi de modifier translate(x,y) dans l’attribut SVG transform.

  • Le framework QGraphicsView vaut le coup d’œil : https://doc.qt.io/qt-6/graphicsview.html
    C’est l’un des frameworks graphiques les plus puissants que j’aie utilisés. En plus des transformations scène-objet, y compris avec une hiérarchie d’objets, il fournit de nombreux outils puissants pour rendre des scènes complexes et interactives.
    Malheureusement, je n’ai pas trouvé sur le Web d’alternative qui fonctionne aussi bien que QGVF.

  • Schemio a l’air bien
    Je crée beaucoup de diagrammes de flux avec Claude ; Claude les génère en Mermaidjs et je les rends dans le navigateur. La fonctionnalité de zoom/dézoom d’un flux vers une séquence a l’air encore meilleure, donc j’aimerais essayer quelque chose de similaire avec Schemio.

  • Ce qui est sympa avec l’utilisation de matrices homogènes 3x3 pour les translations 2D, c’est qu’une translation 2D est en fait un cisaillement 3D le long du plan z = 1
    https://youtu.be/AheaTd_l5Is?t=263

  • À ce sujet, https://webglfundamentals.org/webgl/lessons/webgl-scene-grap... ainsi que tout https://webglfundamentals.org sont de bonnes lectures, et constituent aussi une solide introduction aux hiérarchies de transformations.

  • L’article comme le logiciel sont très intéressants
    Personnellement, je cherchais un logiciel open source robuste pour les diagrammes, et curieusement Schemio n’était jamais apparu sur mon radar.
    J’ai aussi le sentiment que, pour les transformations et les animations, l’algèbre géométrique serait plus intuitive que l’algèbre linéaire.
    [1] Projective Geometric Algebra:
    https://projectivegeometricalgebra.org/

  • Si l’on déplace un objet qui a beaucoup d’enfants, il faudra sans doute mettre à jour le terme A(i-1) de tous les enfants à chaque frame, puis descendre récursivement jusqu’aux petits-enfants ; je me demande si le coût ne devient pas élevé
    Ou bien est-ce que, pour des formes de taille raisonnable, ce n’est pas si problématique ?

    • Quel que soit l’ancêtre qui bouge, les matrices de transformation de tous les enfants situés en dessous doivent être mises à jour à chaque fois
      Jusqu’ici, il n’y a toutefois pas de baisse de performance notable. Pour l’instant, ces calculs sont simplement faits au cas où ils seraient nécessaires, et ils n’affectent pas les éléments SVG réels, donc il n’est pas nécessaire de mettre à jour les éléments SVG. La raison pour laquelle on recalcule ces matrices de transformation est qu’on peut avoir besoin de connaître les coordonnées local-monde d’un objet donné, par exemple pour réajuster les connecteurs attachés ou gérer de la logique basée sur la position.