NAWASHIRO

哲学対話イベントで使える Udon ギミックを作った話 #2 - 力学モデル

前回は、哲学対話イベントにツェッテルカステンを活用するアイデアについてお話ししました。

今回は、その第 2 章として、私たちが開発したメモツールの背後にある技術、特に力学モデルを用いたグラフ描画アルゴリズムについてご紹介します。

多くは説明のため疑似コードで書かれており、コピペしても動きません。注意してください。

グラフ描画アルゴリズム - 力学モデルとは何か

力学モデルは、ネットワークグラフを視覚的に美しく、かつ直感的に理解しやすい形に配置するためのアルゴリズムです。その中でも、Fruchterman-Reingold アルゴリズムは広く知られています。このアルゴリズムは、グラフの頂点（ノード）と辺（エッジ）の関係を物理的な力に置き換えてシミュレーションします。

私たちが「いい感じ」にノードを配置するとは、具体的に以下の条件を満たすことを指します。

  • 頂点の接続関係が距離に反映されていること：関連性の高いノード同士が近くに配置されます。
  • 頂点が重ならないこと：ノード同士が重ならず、全体の構造が見やすくなります。

これを実現するために、

  • 辺でつながっているノード同士が引き合う力を「ばねの計算（フックの法則）」で、
  • ノード同士が反発し合う力を「電気力の計算（クーロンの法則）」で、

それぞれモデル化します。これにより、システム全体のエネルギーが最小になる位置を求めることができます。

力学モデルの引力 - フックの法則

まず、辺でつながっているノード同士が引き合う力についてです。これは、ばねが理想的な長さに近づこうとする性質を表すフックの法則を利用します。計算式は以下の通りです。

  • k：頂点間の理想的な距離。
  • delta：自ノードの座標 - 相手ノードの座標（ベクトル）。
  • distance：delta の大きさ（自ノードと相手ノードの間の距離）。
attractiveForce = (distance ^ 2 / k) * (delta / distance)

この式では、ノード間の距離が遠いほど引力が強くなり、近づくように働きます。

力学モデルの反発力 - クーロンの法則

次に、全てのノード同士が反発し合う力です。これは、同極の電荷が反発する性質を表すクーロンの法則を使用します。計算式は以下の通りです。

  • k：頂点間の理想的な距離。
  • delta：自ノードの座標 - 相手ノードの座標（ベクトル）。
  • distance：delta の大きさ。
repulsiveForce = (k ^ 2 / distance) * (delta / distance)

この式では、ノード間の距離が近いほど反発力が強くなり、離れるように作用します。

力学モデルを収束させる - 温度

力学モデルは理論上、システムのエネルギーが最小になるまで計算を続けますが、必ずしも平衡に達するとは限りません。そこで、計算を適切なタイミングで停止するために温度という概念を導入します。

温度はシミュレーションの進行につれて徐々に下げていき、ノードの移動量を抑制します。これにより、計算が収束しやすくなります。温度の更新式は以下の通りです。

  • iteration：現在の反復回数（ゼロ除算を防ぐために 1 を加算）。
temperature -= temperature / (iteration + 1)

また、引力や反発力を適用する際には温度を考慮してノードの移動量を計算します。

  • force：引力または反発力のベクトル。
  • forceDistance：force の大きさ。
displacement = (force / forceDistance) * temperature
newPoint = point + displacement

これにより、シミュレーションが進むにつれてノードの移動が徐々に小さくなり、最終的に安定した配置が得られます。

力学モデルの全体の処理の流れ

力学モデルを用いたグラフ描画の全体的な処理フローは以下のようになります。

while (温度が一定以上) {

    // 全てのノードの組み合わせに対して
    for (各ノードのペア) {
        // 反発力の計算
        repulsiveForceを計算し、各ノードに適用
    }

    // エッジで繋がったノード同士に対して
    for (各エッジ) {
        // 引力の計算
        attractiveForceを計算し、接続されたノードに適用
    }

    // ノードの位置更新
    for (各ノード) {
        displacementを計算し、ノードの位置を更新
    }

    // 温度の減少
    温度を更新
}

このループを温度が低くなるまで繰り返すことで、ノードの配置が徐々に最適化されていきます。

次回予告

次回は、この力学モデルを具体的に UdonSharp でどのように実装したのか、その技術的な詳細についてご紹介したいと思います。

Back Link

Back to Home