Wie lineare Algebra zum Bau eines interaktiven Diagramm-Editors genutzt wurde

 (medium.com/@ivan.ishubin)
2 Punkte von GN⁺ 2024-12-19 | 1 Kommentare | Auf WhatsApp teilen
  • Mit zunehmenden Funktionen zum Hierarchisieren und Verbinden von Formen wurde bei Schemio die Umrechnung zwischen lokalen Koordinaten und Weltkoordinaten zum Kernproblem des Editors
  • Der anfängliche Ansatz, Formeln entlang der Elternkette direkt anzuwenden, wurde mit Skalierung und Pivot-Punkt schwer wartbar
  • Wenn Verschiebung, Rotation und Skalierung in 3×3-Transformationsmatrizen vereinheitlicht werden, lassen sich mehrere Transformationen zu einer kombinieren und akkumulierte Transformationen in Hierarchien konsistent berechnen
  • Um Weltkoordinaten wieder in objektbezogene Koordinaten zurückzuführen, wird die Inverse A⁻¹ der gesamten Transformationsmatrix verwendet, um Klickpositionen oder Anschlussstellen von Konnektoren präzise zu bestimmen
  • Beim Mounten oder Unmounten eines Objekts an einen anderen Parent müssen neue lokale Werte neu berechnet werden, damit Position und Rotation auf dem Bildschirm erhalten bleiben und sprunghafte Bewegungen vermieden werden

Probleme, die entstanden, als Schemio zu einem hierarchischen Editor erweitert wurde

  • Schemio begann als interaktiver Diagramm-Editor, der das Erstellen, Verschieben, Skalieren und Rotieren von Formen unterstützt
  • Jede Form besitzt eine area-Struktur, die aus x, y, w, h, r besteht
    • x, y: Position in Weltkoordinaten
    • w, h: Breite und Höhe
    • r: Rotationswinkel
  • Um Formen aneinander zu befestigen und komplexe Interaktionen zu erzeugen, wurde jedem Objekt ein childItems-Array hinzugefügt und eine Item-Hierarchie eingeführt
  • Ähnlich wie die Gruppenfunktion gewöhnlicher Vektorgrafik-Editoren kann beim Bewegen eines Objekts auch das verbundene Objekt mitbewegt werden, aber Schemio zielt auf Animationen und benutzerdefinierte Abläufe ab, die eine Mischung aus Diagramm-Editor und Game Engine darstellen

Koordinatenberechnung, die sich nicht allein durch SVG-Rendering lösen lässt

  • In SVG kann der Browser beim Verschachteln von Elementen Parent- und Child-Transformationen bereits im Rendering-Schritt verarbeiten
  • Schemio muss jedoch zusätzlich zum Rendering auch Konnektor-Verbindungen, Mounten und Unmounten von Objekten sowie benutzerdefinierte Interaktionen direkt berechnen
  • Für diese Funktionen sind Transformationen zwischen den lokalen Koordinaten eines Objekts und den Weltkoordinaten der gesamten Szene nötig
  • Anfangs wurden die Transformationen durch das Durchlaufen der Parent-Kette und einfache Formeln angewendet, später wurden Parent-Transformationen zur Optimierung zwischengespeichert
  • Mit der Einführung von Skalierung und Pivot-Punkten stieß die auf Verschiebung und Rotation ausgelegte Formel-Kombination an ihre Grenzen

Die wachsende Komplexität durch Skalierung und Pivot-Punkte

  • Skalierung ist die Funktion, die Größe eines Objekts dynamisch anzupassen, und spielt in Schemio eine wichtige Rolle beim dynamischen Laden externer Diagramme
  • Der Pivot-Punkt definiert das Rotationszentrum eines Objekts
  • Zur area eines Objekts kamen vier weitere Eigenschaften hinzu
    • px, py: Pivot-Punkt relativ zu Breite und Höhe
    • sx, sy: Skalierungsfaktoren entlang der x- und y-Achse
  • Wenn der Pivot-Punkt relativ angegeben wird, passt er sich mit an, wenn der Benutzer die Größe der Form ändert
  • Das direkte Kombinieren von Verschiebung, Rotation, Skalierung und Pivot-Korrektur wird mit wachsenden Anforderungen immer schwerer beherrschbar

2D-Transformationen einheitlich als Matrizen behandeln

  • In 2D- und 3D-Grafik lassen sich Verschiebung, Rotation und Skalierung alle als Matrizen darstellen
  • Ein 2D-Punkt wird als 3×1-Matrix behandelt, eine Transformation als 3×3-Matrix
  • Multipliziert man eine 3×3-Transformationsmatrix mit einer 3×1-Punktmatrix, erhält man den transformierten 3×1-Punkt
  • Die grundlegenden Transformationsmatrizen gliedern sich wie folgt
    • Einheitsmatrix: führt keine Transformation aus
    • Translationsmatrix: verschiebt die Position
    • Rotationsmatrix: rotiert entsprechend dem Winkel
    • Skalierungsmatrix: passt die Größe an
  • Wenn mehrere Transformationen kombiniert werden, werden ihre Matrizen multipliziert und zu einer einzigen Transformation zusammengefasst

So werden Transformationen in einer Hierarchie akkumuliert

  • Die endgültige Transformation eines Objekts umfasst nicht nur seine eigene Transformation, sondern auch die Transformationen aller Parent-Objekte
  • Wenn man entlang der Hierarchie geht und die Transformationsmatrizen der einzelnen Objekte multipliziert, erhält man die Gesamttransformationsmatrix des aktuellen Objekts
  • Wird die Transformationsmatrix des aktuellen Objekts als Ai und die des Parent-Objekts als A(i-1) bezeichnet, akkumuliert sich die Hierarchietransformation als Produkt aus Parent-Transformation und aktueller Objekttransformation
  • In der vollständigen Formel ist die Reihenfolge wichtig: Das Objekt wird relativ zum Pivot-Punkt verschoben, dann werden Rotation und Skalierung angewendet, danach wird es wieder zurückverschoben
  • Ohne Berücksichtigung des Pivot-Punkts scheint sich das Objekt nicht um den gewählten Pivot, sondern um die obere linke Ecke zu drehen
  • Die Pivot-Korrektur muss nach der Skalierungsmatrix angewendet werden, damit auch die Skalierung so wirkt, als erfolge sie relativ zum Pivot-Punkt

Berechnungen zwischen Weltkoordinaten und lokalen Koordinaten

  • Für die Umrechnung von lokalen in Weltkoordinaten wird die Gesamttransformationsmatrix mit dem Punkt multipliziert
  • Umgekehrt wird für die Umwandlung von Weltkoordinaten in die lokalen Koordinaten eines Objekts die Inverse der Gesamttransformationsmatrix verwendet
  • Fasst man die Gesamttransformation als Matrix A zusammen, lässt sich ein Weltpunkt als Produkt aus A und dem lokalen Punkt ausdrücken
  • Eine Matrixdivision gibt es nicht, aber wenn man links mit A⁻¹ multipliziert, wird A⁻¹A zur Einheitsmatrix und man erhält den lokalen Punkt
  • Diese Umrechnung wird benötigt, um etwa die Stelle zu finden, auf die der Benutzer auf einem transformierten Objekt geklickt hat, bezogen auf dessen obere linke Ecke, oder um Konnektoren exakt an der richtigen Position zu befestigen

Position beim Mounten und Unmounten beibehalten

  • Eines der schwierigeren Probleme bei der Hierarchiefunktion war das Mounten und Unmounten von Objekten
  • Es gibt zwei Wege, ein Objekt an ein anderes anzuhängen
    • Ein Objekt in der Szene auf ein anderes ziehen und dort ablegen
    • Die Hierarchie im Item-Selector-Panel neu anordnen
  • Wird nur die Hierarchie geändert, wird die Position des Objekts relativ zum neuen Parent interpretiert, was dazu führt, dass es auf dem Bildschirm nach oben oder unten springt
  • Um das zu vermeiden, müssen die neue Position und Rotation des gezogenen Objekts neu berechnet werden

  • Schritt 1: Bisherige Weltposition speichern

    • Zuerst wird die Weltposition der oberen linken Ecke des Objekts vor dem Verschieben gespeichert
    • Im Beispielcode wird mit worldPointOnItem(0, 0, item) die Weltkoordinate der oberen linken Ecke des Objekts bestimmt
    • worldPointOnItem ist mit der zuvor hergeleiteten Formel für Matrixtransformation implementiert

  • Schritt 2: Rotation korrigieren

    • Die Rotation eines Objekts ist relativ zum Parent definiert, daher muss sie bei einem Parent-Wechsel ebenfalls korrigiert werden
    • Die Funktion worldAngleOfItem wandelt die obere linke und die obere rechte Ecke des Objekts in Weltkoordinaten um und berechnet dann den Winkel zwischen der lokalen x-Achse des Objekts und der Welt-x-Achse
    • Durch Vergleich des Welt-Rotationswinkels des alten Parent mit dem des neuen Parent wird die Rotation des Objekts angepasst
    • item.area.r += previousParentWorldAngle - newParentWorldAngle
    • Dadurch bleibt die sichtbare Rotation des Objekts auch nach dem Parent-Wechsel erhalten

  • Schritt 3: Position beibehalten

    • Auch nachdem das Objekt unter den neuen Parent verschoben wurde, muss ein neuer lokaler Koordinatenwert berechnet werden, damit es auf dem Bildschirm an derselben Stelle bleibt
    • Die Funktion findTranslationMatchingWorldPoint berechnet den erforderlichen Verschiebungswert so, dass ein bestimmter lokaler Punkt auf einen gewünschten Weltpunkt abgebildet wird
    • Wenn ein berechnetes Ergebnis vorliegt, werden area.x und area.y des Objekts mit den neuen Werten aktualisiert
    • Auf diese Weise bleibt die Bildschirmposition erhalten, selbst wenn ein Objekt auf ein anderes gezogen und dadurch die Hierarchie geändert wird

Neue Verschiebungswerte mit der Inversen finden

  • Das Problem beim Finden neuer Verschiebungswerte besteht darin, bei gegebenem Weltpunkt Pw und lokalem Punkt PL die Translationsmatrix At des Objekts zu bestimmen
  • Bereits bekannte Matrizen für Parent-Transformation, Pivot, Rotation und Skalierung lassen sich in einer Matrix A zusammenfassen
  • Die Formel wird unter Verwendung der Inversen der Parent-Transformationsmatrix umgeformt, aber eine 3×1-Matrix ist keine quadratische Matrix, daher kann dieselbe Inversionsmethode nicht direkt angewendet werden
  • Stattdessen wird die Determinantenformel aufgelöst, um die benötigten Verschiebungskomponenten x und y zu isolieren
  • Mit dieser Berechnung bleiben Position und Rotation des gezogenen Objekts beim Verschieben zu einem neuen Parent natürlich erhalten, ohne seltsame Sprünge oder Verzerrungen

Code und Demo

  • Die Schemio-Implementierung ist im GitHub-Repository ishubin/schemio zu finden
  • Wer es direkt ausprobieren möchte, kann auf schem.io interaktive Diagramme oder App-Prototypen erstellen
  • In Schemio gibt es neben Matrixtransformationen noch weitere mathematische Themen wie Bézier-Kurven, Differentialrechnung und Quadtrees zur Performance-Optimierung

Verwandte Beiträge

1 Kommentare

 
GN⁺ 2024-12-19
Hacker-News-Kommentare

  • Von Schemio hatte ich noch nie gehört, sieht cool aus: https://schem.io/
    Sieht sehr rund aus und fühlt sich auch so an, und obwohl es nicht groß damit wirbt, ist es Open Source: https://github.com/ishubin/schemio

    • Schemio ist Open Source, mit Ausnahme des Backend-Teils von https://schem.io
      Der Frontend-Code ist vollständig offen, und man kann auch selbst einen Server hosten. In diesem Fall wird allerdings nur das Dateisystem als Speicher genutzt, es gibt also keine Datenbank und keine Benutzerverwaltung
    • Mir gefällt, dass man in detailliertere Diagramme hineinzoomen und dann leicht wieder herauszoomen kann
      So etwas hatte ich mir in Obsidian gewünscht, aber dort war es nicht so elegant wie bei Schemio

  • Transformationsmatrizen wurden in den 1980er-Jahren durch Adobe PostScript popularisiert, und SVG hat vieles aus dem Imaging-Modell von PostScript übernommen
    Zur Verwendung von 2D-Matrizen in PostScript siehe die folgenden Materialien
    https://personal.math.ubc.ca/~cass/graphics/text/old.pdf/las...
    https://scientificgems.wordpress.com/2014/11/28/mathematics-...

    • Ob man sagen kann, Adobe habe sie popularisiert, weiß ich nicht; Transformationsmatrizen lernt man doch einfach in der Algebra, oder?

  • Es könnte sich auch lohnen, homogene Koordinaten nachzuschlagen: https://en.wikipedia.org/wiki/Homogeneous_coordinates

    • Danke für die Empfehlung, ich bin der Autor
      Ich werde es mir auf jeden Fall durchlesen, wenn ich Zeit habe; beim schnellen Überfliegen sah es so aus, als gäbe es dort auch einen Abschnitt zu den Transformationsmatrizen, die ich verwende

  • Der Artikel fasst den Prozess, einen Editor zu bauen, gut zusammen und ist auch eine gute Zusammenfassung von linearer Algebra
    Aber verwendet nicht jeder Editor lineare Algebra?

    • Technisch gesehen kann man sagen, dass jeder Grafikeditor für verschiedene Zwecke auf lineare Algebra angewiesen ist
      Nur ist für jemanden, der so etwas zum ersten Mal entwickelt, nicht jedes Problem offensichtlich. Deshalb wollte ich die Hürden teilen, die ich aus mathematischer Sicht erlebt habe. Ich verwendete bereits lineare Algebra, aber der Kernpunkt war, wie stark Matrizen die Berechnungen vereinfacht haben
      Außerdem kann man, wenn man sich auf SVG-Rendering verlässt, auch nur mit Code auskommen, ohne sich tiefer mit der zugrunde liegenden Mathematik zu befassen. Hätte ich zum Beispiel keine Objekthierarchie eingeführt, hätte ich mir um die Mathematik fast keine Gedanken machen müssen. SVG übernimmt alle Transformationen, und man muss nicht einmal wissen, dass es Matrizen gibt oder dass man sie 1:1 auf SVG-Objekte anwenden kann. Auch das Ziehen von Objekten ohne Hierarchie wäre viel einfacher gewesen; man hätte nur translate(x,y) im SVG-Attribut transform ändern müssen

  • Ein Blick auf das QGraphicsView-Framework lohnt sich: https://doc.qt.io/qt-6/graphicsview.html
    Es gehört zu den leistungsfähigsten Grafik-Frameworks, die ich ausprobiert habe. Es bietet nicht nur Szenen-Objekt-Transformationen samt Objekthierarchie, sondern auch viele starke Werkzeuge zum Rendern komplexer und interaktiver Szenen
    Leider habe ich im Web keine Alternative gefunden, die so gut funktioniert wie QGVF

  • Schemio sieht gut aus
    Ich erstelle viele Flussdiagramme mit Claude; Claude gibt sie als Mermaidjs aus und ich rendere sie im Browser. Die Funktion, vom Ablauf in Sequenzen hinein- und herauszuzoomen, sieht besser aus, daher würde ich gern etwas Ähnliches mit Schemio ausprobieren

  • Wenn man für 2D-Translation eine homogene 3x3-Matrix verwendet, ist es schön, dass eine 2D-Translation tatsächlich eine 3D-Scherung entlang der Ebene z = 1 ist
    https://youtu.be/AheaTd_l5Is?t=263

  • Dazu sind https://webglfundamentals.org/webgl/lessons/webgl-scene-grap... und https://webglfundamentals.org insgesamt gut zu lesen und auch eine solide Einführung in Transformationshierarchien

  • Sowohl der Artikel als auch die Software sind sehr interessant
    Ich habe persönlich nach robuster Open-Source-Software für Diagramme gesucht, aber seltsamerweise war Schemio nie auf meinem Radar
    Ich habe auch das Gefühl, dass geometrische Algebra für Transformationen und Animationen intuitiver sein könnte als lineare Algebra
    [1] Projective Geometric Algebra:
    https://projectivegeometricalgebra.org/

  • Wenn man ein Objekt mit vielen Kindern bewegt, müssten doch zwischen den Frames die A(i-1)-Terme aller Kinder aktualisiert werden und das Ganze rekursiv bis zu den Enkeln weiterlaufen. Ich frage mich, ob das nicht teuer wird
    Oder ist es bei Formen von angemessener Größe nicht besonders schlimm?

    • Bei jeder Bewegung eines Vorfahren müssen die Transformationsmatrizen aller darunterliegenden Kinder jedes Mal aktualisiert werden
      Bisher gibt es trotzdem keinen merklichen Performance-Einbruch. Derzeit werden die Berechnungen nur vorsorglich durchgeführt, falls sie gebraucht werden, und sie wirken sich nicht auf die tatsächlichen SVG-Elemente aus, sodass die SVG-Elemente nicht aktualisiert werden müssen. Der Grund, diese Transformationsmatrizen neu zu berechnen, ist, dass man für die Neuausrichtung verbundener Konnektoren oder für positionsbasierte Logik möglicherweise die Lokal-zu-Welt-Koordinaten eines bestimmten Objekts kennen muss