発散定理を用いた高速体積計算アルゴリズム

発散定理を応用した3次元三角形メッシュの体積計算アルゴリズムが発表された。このアルゴリズムはO(n)の計算量で単一ループにより処理でき、n個の三角形に対して11nの浮動小数点演算で体積を求められる。

発散定理に基づくこのアルゴリズムは、単純な閉じた3次元三角形メッシュの体積を計算する。n個の三角形からなるメッシュに対して、アルゴリズムは8n−1回の加算と3n+1回の乗算、合わせて11nの浮動小数点演算を必要とする。計算過程に数値積分や微分は含まれず、三角形に対する単一ループのみで構成されている。

計算効率と性能

アルゴリズムはO(n)の計算量を持ち、三角形の数に対して線形の複雑さで動作する。高性能アプリケーションが60フレーム/秒で動作する場合、$35のRaspberry Piで毎フレーム約30万個の三角形の体積測定が可能と推定されている。

関連研究

Cha ZhengとTsuhan Chenによる「Efficient Feature Extraction for 2D/3D Objects in Mesh Representation」という論文が類似のアルゴリズムについて記述している。

この記事は元記事の事実のみに基づいて自動生成されました。

出典

Alyssa Rosenzweig ブログ、「Hilariously Fast Volume Computation with the Divergence Theorem」 https://alyssarosenzweig.ca/blog/hilariously-fast-volume-computation-with-the-divergence-theorem.html