発散定理でメッシュ体積を超高速計算——三角形1個あたり演算はわずか11回
Hilariously Fast Volume Computation with the Divergence Theorem
閉じた三角形メッシュの体積を、数値積分やレンダリングを使わずに計算する高速アルゴリズムを紹介。発散定理を用いて体積積分を表面積分に変換し、各三角形の頂点座標と外積だけで体積を求める。計算量は三角形数に対してO(n)で、三角形あたりの浮動小数点演算はわずか11回。60fpsのアプリケーションでRaspberry PiのCPUだけでも毎フレーム約3000万三角形を処理できるという。著者はベクトル解析の試験勉強を兼ねて考案したが、後に同様のアルゴリズムが既存研究にあることを認めている。
このアルゴリズムは三角形の数に対してO(n)であり、三角形あたりの計算も同様に効率的です。内側の計算は外積の自然な展開により、7回の加算と3回の乗算を含みます。
HNでの議論
61- physicsguy
これは、背景によって「おお、すごい！」と思うか、「え、このトリックはよく知られていると思ってた！」と思うかのどちらかになる類の話ですね。
こちらは1980年に書かれたFortranによる同様の実装で、重心などの他のプロパティも計算します：
Algorithm 550: Solid Polyhedron Measures
A. M. Messner and G. Q. Taylor
ACM Trans. Math. Softw., 6(1), Mar 1980, pp.121--130
キーワード: polyhedron, graphics, numerical integration
言語: Fortran 66/77; Shar Index: Z; Gams: P
ファイルサイズ: 19.1 KB;
しかし、Messnerはこれを最初に次の論文で発表しました：
A. M. Messner, "A surface Integral method for computer
calculation of mass properties", Paper No. 852, 29TH ANNUAL
CONF. OF THE SOCIETY OF AERONAUTICAL WEIGHT ENGINEERS,
Washington, D.C., May 1970.
だったと思います。
- eterevsky
これは、メッシュのすべての三角形を取り、その三角形と平面の1つへの投影との間のプリズム状のポリトープの体積を計算し、投影の向きに応じてプラスまたはマイナスの符号を付けるのと同じではないですか？この種の公式は基本的な幾何学に基づいて機能します。
- srean
一方、格子点上に頂点を持つ多角形の面積を計算したい場合は、内部点の数Iと境界点の数Bを数えることができます。すると面積Aは
A = I + B/2 - 1
となります。
これはピックの定理です
https://en.wikipedia.org/wiki/Pick's_theorem
私のお気に入りの結果の一つです。残念ながら、高次元にはうまく一般化できません。
記事のように多面体の体積を求めたい場合は、靴ひも公式の3次元版（本質的に同等）を使うことができます。
Va、Vb、Vcを表面の三角形分割の三角形∆の頂点とします。頂点は原点に関して一貫した順序/向きで名前を付ける必要があります。
すると体積Vは、そのようなすべての三角形に対する符号付き体積の合計です：
V_∆ = 1/6 Va ^ Vb ^ Vc。
これが符号付き面積と体積、行列式、外積代数の美しさです。
なぜそうなるかを理解するには、この美しい短いビデオがあります
- elikoga
私の直感では、ナイーブな公式は、原点に対する三角形のピラミッド体積を向きに応じて符号を付けて合計するものだと思います。彼らが導出したのはそれのように見えます。これは、各辺について三角形の面積を合計して2D多角形の面積を計算する方法の一般化であり、私は数学キャンプでGISデータ上の地図ポリゴン面積を計算するときにこれを教わりました。AI時代以前は数学の知識を得るのが難しかったのを覚えていますが、こんなに難しかったとは思いませんでした。
著者が「メッシュをレンダリングしてからレンダリングをサンプリングするのと同等」と言っている意味はまったくわかりません。
- ahaferburg
ここでの強調点は、メッシュが単純で閉じていることです。出力に依存する前に、これらの前提条件を検証するようにしてください。
剛体の慣性行列を計算するためのモーメントにも同様の公式が存在します。