概要
- 三角形メッシュ による閉じた3D形状の 体積計算の高速アルゴリズム を解説
- 発散定理 を利用し、表面積分に帰着
- 各三角形ごとに 一定回数の演算 のみで計算可能
- O(n) の計算量で、非常に高速
- 実用性や既存研究との関係も簡潔に紹介
三角形メッシュの体積計算アルゴリズム
- 入力は 単純閉曲面の三角形メッシュ
- 体積Vは、領域R上の三重積分V=∭R1dVとして定義
- 発散定理より、 体積=ベクトル場Fの発散の体積分=Fの表面積分
- ここでF(x, y, z) = <x, 0, 0>を選択
- このときdiv F = 1となる
- よって体積Vは、メッシュ表面S上の積分に変換
- V = ∬S F(x, y, z)・dS
- メッシュは三角形T_iの集合で構成
- 各三角形T_iの3頂点T_{i0}, T_{i1}, T_{i2}を用いる
- Δ1 = T_{i1} - T_{i0}, Δ2 = T_{i2} - T_{i0}
- 各三角形のパラメータ表示：r(u,v) = T_{i0} + uΔ1 + vΔ2 (0≤u, v, u+v≤1)
- 面積要素はΔ1×Δ2（外積）で計算可能
- 積分の簡略化により、各三角形について
- V_i = (1/6) * (Δ1×Δ2)x * (T{i0x} + T_{i1x} + T_{i2x})
- 総体積は全三角形で合計
- V = (1/6) ∑{i=0}^{n-1} (Δ1×Δ2)x * (T{i0x} + T{i1x} + T_{i2x})
アルゴリズムの性能と特徴
- 数値積分や微分不要、単純な加減乗算のみ
- ループは三角形数nに対してO(n)
- 各三角形あたり
- 加算7回、乗算3回
- 全体で加算8n-1回、乗算3n+1回（合計11n回の浮動小数点演算）
- CPU性能のみでも非常に高速
- 例：Raspberry Piで60fps動作時、約3000万三角形/フレーム処理可能
背景と関連研究
- 発散定理の復習 や 3Dグラフィックスへの応用 が動機
- 同様のアルゴリズムはCha Zheng, Tsuhan Chenの論文（Efficient Feature Extraction for 2D/3D Objects in Mesh Representation）にも記載あり
- 導出法は異なるが、 理論的裏付けと実用性 を再確認できる内容
まとめ
- 三角形メッシュの体積計算 を発散定理で効率化
- O(n)の高速アルゴリズム
- 実装容易かつ高精度
- 3Dグラフィックスや計算幾何分野での応用価値