注目★★★★★Hacker News
3Dメッシュの体積計算をO(n)で高速化、発散定理を活用
30秒で把握
- 1発散定理で閉じた3Dメッシュの体積計算をO(n)化
- 2三角形ごとに加算7回・乗算3回で数値積分を排除
- 335ドルのRaspberry Piで60fps・約3000万三角形を測定
要約
閉じた三角形分割3Dメッシュの体積を、発散定理を使って三角形ごとの和に変換する高速アルゴリズムを導出した。数値積分や微分を使わず、三角形数 n に対して O(n) で計算できる。各三角形の処理は加算7回と乗算3回で、ループ外の乗算も1回だけとなる。GPUを使わない35ドルのRaspberry Piでも、60fps処理なら毎フレーム約3000万三角形を測定できる概算になる。後の調査で、同じアルゴリズムを扱う既存論文が見つかり、新規性は確認できなかった。
あなたへの影響
3D形状を扱う日本のエンジニアは、閉じた三角形メッシュの体積計算で数値積分を避ける実装候補として式を検証できる。
推奨：既存研究と重なるため、採用時はアルゴリズムの出典確認と符号・メッシュの閉包条件のテストを行うべきだ。