発散定理を用いた驚異的に高速な体積計算

（ジョークはありません。）以下では、単純で閉じた三角形メッシュの体積を高速に計算するアルゴリズムを提示します。この仮定は発散定理の結果です。さらなる拡張により、他のメッシュにも一般化できる可能性がありますが、現在は範囲外です。 体積の定義から始めます。体積は、領域上の定数1の三重積分として定義されます：V=∭R1dV Fをℝ3上の関数とし、その発散が1に等しいとします。本稿では、以下を選択します：𝐅(x,y,z)=<x,0,0> div𝐅=∂F/∂x+∂F/∂y+∂F/∂z=1+0+0=1であることが容易に検証できます。 したがって、V=∭R1dV=∭Rdiv𝐅(x,y,z)dV 発散定理により、これは表面積分に等しくなります：V=∬S𝐅(x,y,z)dS この表面積分は、3Dメッシュの表面S上で定義され、その区分的な三角形部分の合計に等しくなります。Tiをメッシュ内のi番目の三角形の表面とします。すると、V=∑i=0∬Ti𝐅(x,y,z)dS Tinをi番目の三角形のn番目の頂点とします。Δ1をTi1とTi0のベクトル差とし、Δ2も同様にTi2−Ti0とします。各個別の三角形Tiは、次のようにパラメータ化できます：𝐫(u,v)=Ti0+uΔ1+vΔ2 単純な微分により、次が得られます：𝐫u=Δ1 𝐫v=Δ2 したがって、𝐫u×𝐫v=Δ1×Δ2 これにより、表面積分は、必要に応じて𝐅の定義を代入しながら、このパラメータ化に関して書き換えることができます：V=∑i=0∬Ti𝐅(x,y,z)(𝐫u×𝐫v)dA V=∑i=0∬Ti𝐅(x,y,z)(̇Δi1×Δi2)dA V=∑i=0∬Ti<x,0,0>(̇Δi1×Δi2)dA この外積は三角形全体で一定であり、頂点データから簡単に計算できます。外積のX成分のみを計算する必要があります。他の成分は、𝐅のゼロ成分との内積によりゼロになります。 したがって、Vは次のように書き換えられます：V=∑i=0(Δi1×Δi2)x∬TixdA ここで、表面積分∬TixdAに焦点を当てます。パラメータ化を展開すると、次が得られます： ∬TixdA=∫01∫0uxdvdu=∫01∫0u(Ti0x+uΔi1x+vΔi2x)dvdu この積分は、頂点データを定数として扱い、直接評価できます： ∫01∫01−u(Ti0x+uΔi1x+vΔi2x)dvdu =Ti0x∫01∫01−udvdu+Δi1x∫01∫01−uudvdu+Δi2x)∫01∫01−uvdvdu =Ti0x(1/2)+Δi1x(1/6)+Δi2x(1/6) =Ti0x(1/2)+(Ti1x−Ti0x)(1/6)+(Ti2x−Ti0x)(1/6) =Ti0x(1/6)+(Ti1x)(1/6)+(Ti2x)(1/6) =1/6(Ti0x+Ti1x+Ti2x) 元の合計に代入し、内部ループの除算を避けるために定数因子1/6を外に出すと、体積の以下のコンパクトな公式が得られます： V=1/6∑i=0(Δi1×Δi2)x(Ti0x+Ti1x+Ti2x) パフォーマンス分析 最終的なアルゴリズムには、数値積分も微分も含まれていません。体積の一般的な単純なアルゴリズム（メッシュをレンダリングしてからサンプリングする、高コストな操作と同等）とは対照的に、このアルゴリズムには三角形を巡る単一のループしかありません。したがって、この体積計算アルゴリズムは、三角形の数に対してO(n)です。 さらに、三角形ごとの計算も同様に効率的です。外積の自然な展開を考慮すると、内部部分には7回の加算と3回の乗算が含まれます。ループの外側には単一の乗算しかありません。したがって、n個の三角形を持つメッシュの場合、アルゴリズムは8n-1回の加算と3n+1回の乗算、つまり11n回の浮動小数点演算を必要とします。これは非常に高速です。 概算として、高性能な60フレーム/秒のアプリケーションで毎フレーム体積を計算する必要があり、GPUの助けなしに、35ドルのRaspberry PiのCPU能力のみを使用する場合、毎フレーム約3000万トライアングルを測定できます。 動機 ベクトル解析の試験が近く、勉強が必要です。それに、3Dグラフィックスを愛さない人がいるでしょうか？！ アルゴリズムが新しいものであれば（嬉しいことに）驚くでしょう。 投稿後のさらなる調査により、Cha ZhengとTsuhan Chenによる論文「Efficient Feature Extraction for 2D/3D Objects in Mesh Representation」が明らかになりました。この論文は、導出は異なりますが、同じアルゴリズムを説明しているようです。楽しかったです！ ホームに戻る