Contoh Membuat Editor Diagram Interaktif dengan Aljabar Linear

• Seiring bertambahnya fitur Schemio untuk membuat hierarki bentuk dan menempelkan bentuk satu sama lain, konversi antara koordinat lokal dan koordinat dunia menjadi masalah inti editor
• Pendekatan awal yang menerapkan rumus secara langsung dengan menelusuri rantai induk menjadi sulit dipelihara setelah scaling dan pivot point ditambahkan
• Jika translasi, rotasi, dan scaling disatukan sebagai matriks transformasi 3×3, beberapa transformasi bisa dikomposisikan menjadi satu, dan akumulasi transformasi dalam struktur hierarkis juga dapat dihitung secara konsisten
• Saat mengembalikan koordinat dunia ke koordinat relatif objek, gunakan matriks invers A⁻¹ dari keseluruhan matriks transformasi untuk mendapatkan posisi klik atau titik koneksi connector secara akurat
• Saat objek di-mount ke induk lain atau di-unmount, nilai lokal baru harus dihitung ulang agar posisi dan rotasi di layar tetap terjaga, sehingga gerakan yang meloncat dapat dihindari

---

Masalah yang Muncul Saat Schemio Berkembang Menjadi Editor Hierarkis

• Schemio dimulai sebagai editor diagram interaktif yang mendukung pembuatan, pemindahan, pengubahan ukuran, dan rotasi bentuk
• Setiap bentuk memiliki struktur area yang terdiri dari x, y, w, h, r
  • x, y: posisi berdasarkan koordinat dunia
  • w, h: lebar dan tinggi
  • r: sudut rotasi
• Untuk menempelkan bentuk satu sama lain dan membuat interaksi yang kompleks, array childItems ditambahkan ke setiap objek dan struktur hierarki item diperkenalkan
• Seperti fitur group pada editor grafis vektor umum, ketika satu objek digerakkan, objek yang terhubung juga dapat ikut bergerak, tetapi Schemio menargetkan animasi dan perilaku kustom yang merupakan perpaduan antara editor diagram dan game engine

Perhitungan Koordinat Tidak Selesai Hanya dengan Rendering SVG

• Dalam SVG, jika elemen dibuat bersarang, browser dapat menangani transformasi induk-anak pada tahap rendering
• Selain rendering, Schemio juga harus menghitung sendiri koneksi connector, mount/unmount objek, dan interaksi kustom pengguna
• Fitur-fitur seperti ini memerlukan transformasi bolak-balik antara koordinat lokal objek dan koordinat dunia keseluruhan scene
• Pada awalnya, transformasi diterapkan dengan rumus sederhana sambil menelusuri rantai induk, lalu dioptimalkan dengan melakukan caching transformasi induk
• Setelah scaling dan pivot point ditambahkan, kombinasi rumus yang hanya mengasumsikan translasi dan rotasi mencapai batasnya

Kompleksitas yang Meningkat karena Scaling dan Pivot Point

• Scaling adalah fitur untuk menyesuaikan ukuran objek secara dinamis, dan di Schemio berperan penting dalam memuat diagram eksternal secara dinamis
• Pivot point mendefinisikan pusat rotasi objek
• Empat properti ditambahkan ke area objek
  • px, py: pivot point relatif terhadap lebar dan tinggi
  • sx, sy: faktor scaling pada arah sumbu x dan y
• Dengan menjadikan pivot point sebagai nilai relatif, pivot juga ikut disesuaikan ketika pengguna mengubah ukuran bentuk
• Pendekatan yang menggabungkan translasi, rotasi, scaling, dan koreksi pivot secara langsung menjadi makin sulit dikelola seiring bertambahnya kebutuhan

Menyatukan Transformasi 2D dengan Matriks

• Dalam grafis 2D dan 3D, translasi, rotasi, dan scaling semuanya dapat direpresentasikan sebagai matriks
• Titik 2D ditangani sebagai matriks 3×1, sedangkan transformasi sebagai matriks 3×3
• Mengalikan matriks transformasi 3×3 dengan matriks titik 3×1 menghasilkan titik 3×1 yang sudah ditransformasi
• Matriks transformasi dasar terbagi seperti berikut
  • Matriks identitas: tidak melakukan transformasi apa pun
  • Matriks translasi: memindahkan posisi
  • Matriks rotasi: memutar sesuai sudut
  • Matriks scaling: menyesuaikan ukuran
• Saat menggabungkan beberapa transformasi, matriks-matriks transformasi dikalikan untuk menyatukannya menjadi satu transformasi

Cara Mengakumulasi Transformasi dalam Struktur Hierarkis

• Transformasi akhir suatu objek mencakup bukan hanya transformasinya sendiri, tetapi juga transformasi objek-objek induknya
• Dengan menelusuri hierarki dan mengalikan matriks transformasi setiap objek, keseluruhan matriks transformasi objek saat ini dapat dibuat
• Jika matriks transformasi objek saat ini disebut Ai dan matriks transformasi objek induk disebut A(i-1), transformasi hierarkis diakumulasikan sebagai hasil kali transformasi induk dan transformasi objek saat ini
• Dalam rumus keseluruhan, urutan memindahkan objek berdasarkan pivot point, menerapkan rotasi dan scaling, lalu mengembalikannya lagi adalah hal yang penting
• Jika pivot tidak diperhitungkan, objek akan terlihat berputar mengelilingi sudut kiri atas, bukan pivot yang dipilih
• Koreksi pivot harus diterapkan setelah matriks scaling agar scaling juga terlihat terjadi berdasarkan pivot point

Perhitungan Bolak-balik antara Koordinat Dunia dan Koordinat Lokal

• Saat berpindah dari koordinat lokal ke koordinat dunia, keseluruhan matriks transformasi dikalikan dengan titik
• Sebaliknya, untuk mengubah koordinat dunia menjadi koordinat lokal objek, gunakan matriks invers dari keseluruhan matriks transformasi
• Jika keseluruhan transformasi digabungkan sebagai matriks A, titik dunia direpresentasikan sebagai hasil kali A dan titik lokal
• Tidak ada pembagian matriks, tetapi jika A⁻¹ dikalikan dari kiri, A⁻¹A menjadi matriks identitas sehingga titik lokal dapat diperoleh
• Transformasi ini diperlukan saat mencari koordinat relatif terhadap sudut kiri atas objek untuk titik yang diklik pengguna di atas objek yang sudah ditransformasi, atau saat menempelkan connector ke posisi yang akurat

Mempertahankan Posisi Saat Mount dan Unmount

• Salah satu masalah sulit dalam fitur hierarki adalah mount dan unmount objek
• Ada dua cara untuk menempelkan objek ke objek lain
  • Menyeret objek di scene lalu menjatuhkannya di atas objek lain
  • Menata ulang hierarki di panel Item Selector
• Jika hanya hierarkinya yang diubah, posisi objek akan ditafsirkan sebagai koordinat relatif terhadap induk baru, sehingga muncul masalah objek meloncat naik-turun di layar
• Untuk menghindarinya, posisi dan rotasi baru objek yang diseret harus dihitung ulang

• Langkah 1: Simpan posisi dunia lama

  • Pertama, simpan posisi dunia sudut kiri atas objek sebelum dipindahkan
  • Dalam kode contoh, koordinat dunia sudut kiri atas objek diperoleh dengan worldPointOnItem(0, 0, item)
  • worldPointOnItem diimplementasikan menggunakan rumus transformasi matriks yang telah diturunkan sebelumnya

• Langkah 2: Koreksi rotasi

  • Rotasi objek didefinisikan relatif terhadap induk, sehingga jika induknya berubah, rotasi objek yang diseret juga harus dikoreksi
  • Fungsi worldAngleOfItem mengubah sudut kiri atas dan sudut kanan atas objek ke koordinat dunia, lalu menghitung sudut yang dibentuk sumbu x lokal objek terhadap sumbu x dunia
  • Rotasi objek disesuaikan dengan membandingkan sudut rotasi dunia induk sebelumnya dan sudut rotasi dunia induk baru
  • item.area.r += previousParentWorldAngle - newParentWorldAngle
  • Dengan perhitungan ini, rotasi objek di layar tetap terjaga meskipun induknya berubah

• Langkah 3: Pertahankan posisi

  • Setelah objek dipindahkan ke bawah induk baru, koordinat lokal baru harus dihitung agar objek tetap berada di posisi yang sama di layar
  • Fungsi findTranslationMatchingWorldPoint menghitung nilai translasi yang diperlukan agar titik lokal tertentu cocok dengan titik dunia yang diinginkan
  • Jika ada hasil perhitungan, area.x dan area.y objek diperbarui dengan nilai baru
  • Dengan cara ini, meskipun hierarki diubah dengan menyeret objek ke objek lain, posisi di layar tetap dipertahankan

Mencari Nilai Translasi Baru dengan Matriks Invers

• Masalah mencari nilai translasi baru adalah masalah mencari matriks translasi At objek ketika titik dunia Pw dan titik lokal PL diketahui
• Transformasi induk, pivot, rotasi, dan matriks scaling yang sudah diketahui dapat digabungkan menjadi satu matriks A
• Persamaan disusun ulang menggunakan matriks invers dari matriks transformasi induk, tetapi karena matriks 3×1 bukan matriks persegi, matriks invers tidak dapat diterapkan dengan cara yang sama
• Sebagai gantinya, determinan matriks diekspansi untuk memisahkan komponen translasi x, y yang diperlukan
• Dengan menerapkan perhitungan ini, posisi dan rotasi objek yang diseret saat berpindah ke induk baru dapat dipertahankan secara alami, serta lompatan atau distorsi aneh dapat dihindari

Kode dan Demo

• Implementasi Schemio dapat dilihat di repositori GitHub ishubin/schemio
• Untuk mencobanya langsung, Anda dapat membuat diagram interaktif atau prototipe aplikasi di schem.io
• Selain transformasi matriks, Schemio juga memiliki topik matematika lain seperti kurva Bézier, perhitungan diferensial, dan quadtrees untuk optimasi performa

[GN⁺]

Komentar Hacker News

• Baru pertama kali mendengar Schemio, dan ini keren: https://schem.io/
  Tampilan dan pengalaman pakainya sangat mulus, dan meski tidak terlalu ditonjolkan, ini open source: https://github.com/ishubin/schemio

  • Schemio dirilis sebagai open source kecuali bagian backend dari https://schem.io
    Kode frontend-nya sepenuhnya terbuka dan Anda juga bisa meng-host server sendiri. Namun dalam kasus itu, karena hanya memakai sistem file sebagai penyimpanan, tidak ada database atau manajemen pengguna
  • Saya suka cara bisa zoom in ke diagram yang lebih detail lalu mudah kembali zoom out
    Ini fitur yang saya inginkan di Obsidian, tetapi tidak semulus Schemio

• Matriks transformasi dipopulerkan oleh Adobe PostScript pada 1980-an, dan SVG banyak meminjam dari model pencitraan PostScript
  Untuk penggunaan matriks 2D di PostScript, lihat materi berikut
  https://personal.math.ubc.ca/~cass/graphics/text/old.pdf/las...
  https://scientificgems.wordpress.com/2014/11/28/mathematics-...

  • Rasanya kurang tepat mengatakan Adobe yang mempopulerkannya; bukankah matriks transformasi itu memang materi yang dipelajari dalam aljabar?

• Mungkin bagus juga membaca tentang koordinat homogen: https://en.wikipedia.org/wiki/Homogeneous_coordinates

  • Sebagai penulis, terima kasih atas rekomendasinya
    Saya pasti akan membacanya saat ada waktu, dan setelah sekilas melihat, tampaknya ada juga bagian yang berkaitan dengan matriks transformasi yang saya gunakan

• Proses pembuatan editornya diringkas dengan baik, dan ini juga bagus sebagai ringkasan aljabar linear
  Tapi bukankah semua editor menggunakan aljabar linear?

  • Secara teknis, semua editor grafis bisa dibilang bergantung pada aljabar linear untuk berbagai tujuan
    Namun bagi orang yang baru pertama kali mengembangkan hal semacam ini, semua persoalannya tidak selalu terlihat jelas, jadi saya ingin berbagi kesulitan yang saya alami dari sudut pandang matematika. Saya memang sudah memakai aljabar linear, tetapi poin utamanya adalah betapa matriks membuat perhitungan menjadi jauh lebih sederhana
    Selain itu, jika mengandalkan rendering SVG, Anda bisa saja melewati banyak hal hanya dengan kode tanpa memikirkan matematika terkait secara mendalam. Misalnya, kalau saya tidak memperkenalkan struktur hierarki objek, saya mungkin hampir tidak perlu memedulikan matematika. SVG akan menangani semua transformasi, dan Anda bahkan tidak perlu tahu bahwa matriks itu ada atau bahwa matriks bisa digunakan 1:1 pada objek SVG. Drag objek tanpa hierarki juga jauh lebih mudah; cukup mengubah translate(x,y) di dalam atribut transform SVG

• Layak melihat framework QGraphicsView: https://doc.qt.io/qt-6/graphicsview.html
  Ini termasuk salah satu framework grafis paling kuat yang pernah saya pakai. Selain transformasi scene-objek termasuk hierarki objek, framework ini menyediakan banyak alat yang kuat untuk merender scene yang kompleks dan interaktif
  Sayangnya, di web saya belum menemukan alternatif yang bekerja sebaik QGVF

• Schemio terlihat bagus
  Saya sedang membuat banyak flowchart dengan Claude; Claude mengeluarkannya sebagai Mermaidjs lalu dirender di browser. Karena fitur zoom in/out dari flow ke sequence tampak lebih baik, saya ingin mencoba melakukan sesuatu yang serupa dengan Schemio

• Jika memakai matriks homogen 3x3 untuk translasi 2D, menarik bahwa translasi 2D sebenarnya adalah shear 3D yang bergerak di sepanjang bidang z = 1
  https://youtu.be/AheaTd_l5Is?t=263

• Terkait hal ini, https://webglfundamentals.org/webgl/lessons/webgl-scene-grap... serta keseluruhan https://webglfundamentals.org enak dibaca dan juga merupakan pengantar yang solid untuk hierarki transformasi

• Baik artikel maupun perangkat lunaknya sangat menarik
  Secara pribadi saya sedang mencari software open source yang tangguh untuk diagram, tetapi anehnya Schemio belum pernah masuk radar saya
  Saya juga merasa bahwa untuk transformasi dan animasi, memakai aljabar geometri mungkin lebih intuitif daripada aljabar linear
  [1] Projective Geometric Algebra:
  https://projectivegeometricalgebra.org/

• Saya penasaran, kalau memindahkan objek yang punya banyak anak, bukankah setiap frame harus memperbarui suku A(i-1) untuk semua anaknya, lalu turun berulang sampai cucu-cucunya, sehingga biayanya bisa besar?
  Atau apakah pada bentuk berukuran wajar itu tidak terlalu buruk?

  • Untuk gerakan leluhur apa pun, matriks transformasi semua anak di bawahnya memang harus diperbarui setiap kali
    Meski begitu, sejauh ini belum ada penurunan performa yang mencolok. Saat ini perhitungan itu hanya disiapkan untuk berjaga-jaga bila diperlukan, dan tidak memengaruhi elemen SVG sebenarnya, jadi elemen SVG tidak perlu diperbarui. Alasan menghitung ulang matriks transformasi ini adalah karena saat menyesuaikan ulang konektor yang menempel atau menangani logika berbasis posisi, kita mungkin perlu mengetahui koordinat lokal-ke-dunia dari objek tertentu