- Schemioでは図形の階層化や相互に取り付ける機能が増えるにつれ、ローカル座標とワールド座標の変換がエディタの中核課題になった
- 親チェーンをたどって数式を直接適用していた初期方式は、スケーリングとピボットポイントが加わると保守が難しくなった
- 移動・回転・スケーリングを3×3変換行列で統一すると、複数の変換を1つに合成でき、階層構造での累積変換も一貫して計算できる
- ワールド座標をオブジェクト基準の座標に戻すときは、全体変換行列の逆行列 A⁻¹を使ってクリック位置やコネクタ接続点を正確に求める
- オブジェクトを別の親にマウントまたはアンマウントするときは、画面上の位置と回転を保つよう新しいローカル値を再計算しないと、飛ぶような動きを避けられない
Schemioが階層型エディタへ拡張されて生じた問題
- Schemioは、図形の作成、移動、サイズ変更、回転をサポートするインタラクティブなダイアグラムエディタとして始まった
- 各図形は
x, y, w, h, r からなる area構造 を持つ
x, y: ワールド座標基準の位置w, h: 幅と高さr: 回転角度
- 図形同士を取り付けて複雑な相互作用を作るため、各オブジェクトに
childItems 配列を追加し、アイテム階層構造を導入した
- 一般的なベクターグラフィックエディタのグループ機能のように、あるオブジェクトを動かすと接続されたオブジェクトも一緒に動かせるが、Schemioはダイアグラムエディタとゲームエンジンを組み合わせたようなアニメーションとユーザー定義動作を目指している
SVGレンダリングだけでは解決できない座標計算
- SVGでは要素をネストすると、ブラウザが親子の変換をレンダリング段階で処理できる
- Schemioではレンダリング以外にも、コネクタ接続、オブジェクトのマウント・アンマウント、ユーザー定義インタラクションを自前で計算しなければならない
- こうした機能には、オブジェクトのローカル座標とシーン全体のワールド座標を行き来する変換が必要になる
- 初期には親チェーンを巡回しながら単純な数式で変換を適用し、その後は親変換をキャッシュして最適化した
- スケーリングとピボットポイントが追加されると、移動と回転だけを前提にした数式の組み合わせは限界に突き当たった
スケーリングとピボットポイントが増大させた複雑さ
- スケーリングはオブジェクトのサイズを動的に調整する機能で、Schemioでは外部ダイアグラムを動的に読み込むうえで重要な役割を果たす
- ピボットポイントはオブジェクトの回転中心を定義する
- オブジェクトの
area には4つのプロパティが追加された
px, py: 幅と高さに対する相対的なピボットポイントsx, sy: x軸方向とy軸方向のスケーリング係数
- ピボットポイントを相対値にすると、ユーザーが図形サイズを変更したときにピボットも一緒に調整される
- 移動、回転、スケーリング、ピボット補正を手作業で組み合わせる方式は、要件が増えるほど管理が難しくなる
2D変換を行列で統一する
- 2Dおよび3Dグラフィックスでは、移動、回転、スケーリングはすべて行列で表現できる
- 2Dの点は3×1行列として、変換は3×3行列として扱う
- 3×3変換行列と3×1の点行列を掛け合わせると、変換後の3×1の点が得られる
- 基本変換行列は次のように分かれる
- 単位行列: 何の変換もしない
- 平行移動行列: 位置を移動する
- 回転行列: 角度に応じて回転する
- スケーリング行列: サイズを調整する
- 複数の変換を組み合わせるときは、変換行列同士を掛けて1つの変換にまとめる
階層構造で変換を累積する方法
- オブジェクトの最終変換には、自身の変換だけでなく親オブジェクト群の変換も含まれる
- 階層をたどりながら各オブジェクトの変換行列を掛けると、現在のオブジェクトの全体変換行列を作れる
- 現在のオブジェクトの変換行列を
Ai、親オブジェクトの変換行列を A(i-1) とすると、階層変換は親変換と現在オブジェクト変換の積として累積される
- 全体の式では、オブジェクトをピボットポイント基準へ移動し、回転とスケーリングを適用してから再び戻す順序が重要になる
- ピボットを考慮しないと、オブジェクトは選択したピボットではなく左上隅を中心に回転しているように見える
- ピボット補正はスケーリング行列の後に適用される必要があり、そうすることでスケーリングもピボットポイント基準で起きているように見える
ワールド座標とローカル座標を行き来する計算
- ローカル座標からワールド座標へ行くときは、全体変換行列を点に掛ける
- 逆にワールド座標をオブジェクトのローカル座標へ変換するには、全体変換行列の逆行列を使う
- 全体変換を行列
A にまとめると、ワールド点は A とローカル点の積で表される
- 行列の割り算はないが、左から
A⁻¹ を掛ければ A⁻¹A が単位行列になり、ローカル点を得られる
- この変換は、ユーザーが変換済みオブジェクト上をクリックした位置を、そのオブジェクトの左上基準座標として求めたり、コネクタを正確な位置に取り付けたりするのに必要となる
マウントとアンマウントで位置を保つ
- 階層機能における難題の1つが、オブジェクトのマウントとアンマウントだった
- オブジェクトを別のオブジェクトへ取り付ける方法は2つある
- シーン上でオブジェクトをドラッグして別のオブジェクトの上にドロップする
- Item Selector パネルで階層を再配置する
- 階層だけを変えると、オブジェクトの位置が新しい親基準の座標として解釈され、画面上で上下に跳ねる問題が生じる
- これを避けるには、ドラッグされたオブジェクトの新しい位置と回転を再計算しなければならない
-
1段階目: 既存のワールド位置を保存
- まず移動前のオブジェクト左上隅のワールド位置を保存する
- サンプルコードでは
worldPointOnItem(0, 0, item) によってオブジェクト左上のワールド座標を求めている
worldPointOnItem は前述の行列変換式を使って実装される
-
2段階目: 回転補正
- オブジェクトの回転は親基準で定義されるため、親が変わるとドラッグされたオブジェクトの回転も補正する必要がある
worldAngleOfItem 関数は、オブジェクトの左上隅と右上隅をワールド座標へ変換したあと、オブジェクトのローカルx軸がワールドx軸となす角度を計算する- 以前の親のワールド回転角度と新しい親のワールド回転角度を比較して、オブジェクトの回転を調整する
item.area.r += previousParentWorldAngle - newParentWorldAngle- この計算により、親が変わってもオブジェクトの画面上の回転は維持される
-
3段階目: 位置の保持
- オブジェクトが新しい親の下へ移動した後も画面上の同じ位置に残るよう、新しいローカル座標を計算する必要がある
findTranslationMatchingWorldPoint 関数は、特定のローカル点が望むワールド点に一致するために必要な移動値を計算する- 計算結果があれば、オブジェクトの
area.x, area.y を新しい値に更新する
- この方法により、オブジェクトを別のオブジェクトへドラッグして階層を変更しても、画面上の位置が維持される
逆行列で新しい移動値を求める
- 新しい移動値を求める問題は、ワールド点
Pw とローカル点 PL が与えられたとき、オブジェクトの移動行列 At を求める問題になる
- すでに分かっている親変換、ピボット、回転、スケーリング行列は、1つの行列
A にまとめられる
- 親変換行列の逆行列を使って式を整理できるが、3×1行列は正方行列ではないため、同じ方法で逆行列を適用することはできない
- その代わりに行列式を展開して、必要な
x, y の移動成分を分離する
- この計算を適用すると、ドラッグされたオブジェクトが新しい親へ移動するときも位置と回転が自然に保たれ、不自然なジャンプや歪みを避けられる
コードとデモ
- Schemioの実装はGitHubリポジトリ ishubin/schemio で確認できる
- 実際に使うには、schem.io でインタラクティブなダイアグラムやアプリのプロトタイプを作成できる
- Schemioには行列変換以外にも、ベジェ曲線、微分計算、性能最適化のためのquadtreesのような数学的トピックがさらにある
1件のコメント
Hacker News のコメント
Schemio は初めて聞いたけど、いい感じ: https://schem.io/
見た目も使い心地もとても滑らかで、大きく宣伝してはいないが オープンソース: https://github.com/ishubin/schemio
フロントエンドのコードは完全に公開されていて、自分でサーバーをホスティングすることもできる。ただしその場合、ストレージにはファイルシステムだけを使うため、データベースやユーザー管理はない
Obsidian で欲しかった機能はこういうものだったが、Schemio ほど滑らかではなかった
変換行列は 1980 年代に Adobe PostScript が普及させ、SVG は PostScript のイメージングモデルから多くを借りている
PostScript における 2D 行列の使い方は以下の資料を見るとよい
https://personal.math.ubc.ca/~cass/graphics/text/old.pdf/las...
https://scientificgems.wordpress.com/2014/11/28/mathematics-...
同次座標も調べてみるとよさそう: https://en.wikipedia.org/wiki/Homogeneous_coordinates
時間があるときに必ず読んでみるつもりで、ざっと見たところ、自分が使っていた 変換行列に関する節もあるようだ
エディタを作る過程がうまく要約されていて、線形代数の要約としても良い
でも、すべてのエディタが線形代数を使うものではないのか？
ただ、こうしたものを初めて開発する人にとって、すべての問題が当然のように見えるわけではないので、数学の観点から経験した難所を共有したかった。すでに線形代数は使っていたが、行列が計算をどれほど単純にしてくれたかが核心だった
また SVG レンダリングに依存していれば、関連する数学を深く考えずにコードだけで済ませることもできる。たとえばオブジェクト階層構造を導入していなければ、数学をほとんど気にしなくてもよかったはずだ。SVG がすべての変換を処理してくれるし、行列が存在することや、それを SVG オブジェクトに 1:1 で使えることすら知らなくてよい。階層のないオブジェクトのドラッグもずっと簡単で、SVG の
transform属性内のtranslate(x,y)だけを変更すればよかったはずだQGraphicsView フレームワークは見てみる価値がある: https://doc.qt.io/qt-6/graphicsview.html
自分が使ったグラフィックフレームワークの中でも最も強力な部類に入る。オブジェクト階層を含むシーン-オブジェクト変換だけでなく、複雑でインタラクティブなシーンをレンダリングする強力なツールを数多く提供している
残念ながら、Web では QGVF ほどよく動作する代替を見つけられていない
Schemio は良さそう
Claude で多くの フローチャートを作っているが、Claude は Mermaidjs で出力し、ブラウザでレンダリングする。フローからシーケンスへズームイン／アウトする機能がさらに良さそうなので、Schemio でも似たことを試してみたい
2D の平行移動に 3x3 同次行列を使うと、2D の平行移動が実際には
z = 1平面に沿う 3D のせん断である点が面白いhttps://youtu.be/AheaTd_l5Is?t=263
関連して、https://webglfundamentals.org/webgl/lessons/webgl-scene-grap... と https://webglfundamentals.org 全体は読みやすく、変換階層構造の入門としてもしっかりしている
記事もソフトウェアも非常に興味深い
個人的にダイアグラム用の堅牢なオープンソースソフトウェアを探していたのに、不思議なことに Schemio はこれまで目に入っていなかった
変換とアニメーションには、線形代数より 幾何代数を使うほうが直感的なのではという気もする
[1] Projective Geometric Algebra:
https://projectivegeometricalgebra.org/
子を多く持つオブジェクトを動かすと、フレームごとにすべての子の
A(i-1)項を更新し、孫まで再帰的にたどる必要があるはずだが、コストが大きくならないのか気になるそれとも、適度な大きさの図形ではそれほど悪くないのだろうか？
それでも今のところ、目に見える性能低下はない。現状では必要になった場合に備えて計算だけしている程度で、実際の SVG 要素には影響しないため、SVG 要素を更新する必要はない。この変換行列を再計算する理由は、接続されているコネクタを再調整したり、位置ベースのロジックを処理したりする際に、特定オブジェクトの ローカル-ワールド座標を知る必要が出る場合があるからだ