測地線距離（Geodesic Distance）とは何か — Stanford Bunnyで理解するメッシュ最短経路アルゴリズム

3D形状処理の分野で頻繁に登場する 測地線距離（Geodesic Distance） について、直線距離（ユークリッド距離）との違い、メッシュ・B-Repそれぞれでの計算アルゴリズム、実製品での応用例を解説します。

記事の最後には、Stanford Bunny のメッシュ上でクリックした点からの測地線距離を実際に計算し、等間隔のアイソライン（等距離線）として可視化するインタラクティブな3Dデモ（Three.js）を用意しました。

1. 測地線距離とユークリッド距離の違い

ユークリッド距離（Euclidean Distance） は、3D空間中の2点を結ぶ直線の長さです。物体の内部や外部の空間をどれだけ突き抜けても構わない、いわば「鳥が飛ぶ最短距離」です。

一方、測地線距離（Geodesic Distance） は、曲面や物体の表面から離れずに移動する経路のうち、最も短いものの長さです。平面上ではユークリッド距離と一致しますが、曲がった表面や凹凸のある形状では、表面に沿って迂回する必要があるため、常に 測地線距離 ≥ ユークリッド距離 という関係になります。

Stanford Bunnyで直感的に説明すると：

• 両耳の先端どうしのユークリッド距離は、2つの耳先を結ぶ空中の直線の長さです（耳の間の空間を突き抜けます）。
• 一方、両耳の先端どうしの測地線距離は、片方の耳から表面を這い降りて頭を通り、もう片方の耳まで登る経路の長さになります。耳が長く伸びているほど、また間の谷が深いほど、この2つの値の差は大きくなります。

この性質から、測地線距離は「表面という制約の中でどれだけ移動する必要があるか」を正しく表す指標であり、CG・CAD・ロボティクスなど、対象がある曲面上に拘束されている問題で本質的に重要になります。

2. 計算アルゴリズム

2.1 メッシュベースの計算

三角形メッシュ上で測地線距離を求める代表的な手法には、精度と計算コストのトレードオフに応じていくつかの選択肢があります。

• グラフ近似（Dijkstra法） メッシュの辺をそのままエッジとする重み付きグラフとみなし、辺の長さをコストとしてダイクストラ法で最短路を求める最も単純な方法です。実装が容易な反面、経路が「辺の上」に限定されるため、実際の測地線（三角形の面を斜めに横切る経路）よりも距離を過大評価する傾向があります。メッシュが十分に密であれば誤差は小さくなります。本記事末尾のデモもこの手法を採用しています。

• MMP法（Mitchell–Mount–Papadimitriou, 1987） 各三角形上を波面の「窓（window）」として伝搬させることで、辺上に限定されない数学的に厳密な測地線距離を計算するアルゴリズム。Surazhsky らによる高速化・実用化（2005年, SIGGRAPH）で広く使われるようになりました。

• Fast Marching Method on Triangulated Domains（Kimmel & Sethian, 1998） レベルセット法で使われる Fast Marching Method を三角形メッシュに拡張した手法。波面（距離が等しい前線）を近い点から順に確定させながら伝搬させることで、距離場全体を1回の走査で計算できます。

• Heat Method（Crane, Weischedel, Wardetzky, 2013） 熱拡散方程式をごく短時間だけ解き、得られた温度勾配を正規化して積分することで測地線距離を近似的に求める手法。疎行列の連立一次方程式を2回解くだけで計算でき、事前にコレスキー分解しておけば繰り返し計算が非常に高速なため、実用アプリケーションで広く採用されています。

2.2 B-Rep（NURBS曲面）でのケース

CADで扱うB-Rep・NURBS曲面のような解析的パラメトリック曲面の上では、測地線は曲面の**第一基本形式（計量テンソル）**から導かれる2階非線形常微分方程式（測地線方程式）を数値的に解くことで求められます。

具体的には、曲面のパラメータ空間 (u, v) 上で測地線方程式をシューティング法や有限差分法で数値積分し、開始点・方向（または開始点・終了点）を与えて曲面上の最短経路を追跡します。複数のトリムパッチにまたがる形状では、各パッチ境界をまたぐ際の接続処理に加え、パッチ単位の局所解とパッチ間のグラフ探索（どのパッチをどの順で通過するか）を組み合わせたハイブリッドなアプローチが必要になります。メッシュベースの手法に比べて実装は複雑ですが、曲面の解析的な滑らかさをそのまま活かせるため高精度な結果が得られます。

3. 実製品での応用例

• アパレル・衣服CAD: 3Dボディスキャンから2Dパターン（型紙）を展開する際、伸縮しない生地の性質を再現するために、表面上の距離（測地線距離）をできるだけ保存する展開（等長写像に近い展開）が使われます。
• 板金・複合材の展開設計: 曲面パネルを平面に展開する製造工程で、歪み・伸縮を最小化するために測地距離ベースの展開アルゴリズムが利用されます。
• CADの「表面に沿った寸法」測定: 自動車のボディパネルに沿って配線・ホースを這わせる際の必要長さなど、直線距離ではなく表面沿いの距離を測定する寸法機能に使われます。
• ロボットパス計画: 検査ロボットや塗装ロボットのアームが、対象物の表面をなぞりながら移動する経路の計画に測地線距離が使われます。
• キャラクターアニメーション・スキニング: バウンデッド・バイハーモニック・ウェイトなどのスキンウェイト計算やUVアンラッピングの歪み評価で、表面距離の概念が用いられます。
• 医療画像解析: 脳のMRIから再構成した大脳皮質表面上での距離計測や、腫瘍境界からの表面距離の算出などに応用されます。

4. インタラクティブ可視化：Stanford Bunny上の測地線距離

以下は、Stanford Bunnyのメッシュ（約1,800頂点・3,600三角形、Stanford 3D Scanning Repository 由来のパブリックドメインデータ）上で、2点間の測地線そのものを曲線として描画するデモです。初期状態では、片方の耳の先端Aと、そこから測地線距離が最も遠い点B（後ろ足のあたり）を結んでいます。

デモに描かれる3種類の線：

• メッシュをクリックすると、起点A / 終点B を置き直せます（どちらを置くかはボタンで切り替え）。
• 等距離線の基準を**「測地線距離」⇔「ユークリッド距離」**で切り替えると、リングの形が明確に変わります。測地線基準では輪が表面に沿って耳を回り込むのに対し、ユークリッド基準では空間を突き抜けて耳と背中が同じ輪に入ってしまいます。
• ドラッグでカメラを回転、ホイールでズームできます。

実装のポイント

測地線の計算には、メッシュの辺をエッジとする重み付きグラフに対する ダイクストラ法 を使っています（2.1節「グラフ近似」）。経路が辺の上に限定されるため実際の測地線よりわずかに長く見積もられますが（そのため右上の「比」は真の値よりやや大きめに出ます）、形状の傾向をつかむには十分です。求めた最短経路の頂点列を CatmullRomCurve3 で滑らかに補間し、TubeGeometry として描画しています。

等距離線の抽出は、距離場に対する marching triangles（Marching Cubesの2次元版にあたる手法）です。各三角形の3頂点が持つ距離値を見て、等距離レベル L が三角形を横切る場合、L を跨ぐ2本の辺上の交点を線形補間で求め、その2点を結んで1本の線分とします。これをすべての三角形・すべてのレベルについて行うと、表面上に閉じた輪が浮かび上がります。

線がメッシュ表面と Z-fighting を起こさないよう、頂点法線方向にわずかに浮かせたうえで、メッシュ側のマテリアルに polygonOffset を設定しています。また、直線距離（ピンクの破線）は体内に埋もれる部分こそが見どころなので、depthTest: false で常に手前に描画しています。

記事冒頭で例に挙げた「両耳の先端どうし」も、A・Bをそれぞれの耳先に置けば再現できます（測地線は耳を下って頭を渡り、もう片方の耳を登っていきます）。表面が大きく回り込む2点ほど、シアンの測地線とピンクの直線の差は劇的になります。

5. 元論文・参考文献

• Mitchell, J. S. B., Mount, D. M., & Papadimitriou, C. H. (1987). The Discrete Geodesic Problem. SIAM Journal on Computing, 16(4), 647–668.
• Kimmel, R., & Sethian, J. A. (1998). Computing geodesic paths on manifolds. Proceedings of the National Academy of Sciences, 95(15), 8431–8435.
• Surazhsky, V., Surazhsky, T., Kirsanov, D., Gortler, S. J., & Hoppe, H. (2005). Fast Exact and Approximate Geodesics on Meshes. ACM Transactions on Graphics (SIGGRAPH 2005), 24(3), 553–560.
• Crane, K., Weischedel, C., & Wardetzky, M. (2013). Geodesics in Heat: A New Approach to Computing Distance Based on Heat Flow. ACM Transactions on Graphics, 32(5), 152:1–152:11.
• Turk, G., & Levoy, M. (1994). Zippered Polygon Meshes from Range Images. Proceedings of SIGGRAPH 1994. — Stanford Bunnyの元データを含む、Stanford 3D Scanning Repository の由来論文。

Stanford Bunnyそのものの誕生の歴史については、Stanford Bunny（スタンフォード・バニー）の歴史と形状のヒミツ もあわせてご覧ください。CG・CAD/CAM分野の用語全般は 用語集 にまとめています。