掃除と剪定
物理シミュレーションにおいて、スイープ＆プルーンは、衝突検出中に衝突（交差）のチェックが必要なソリッドのペアの数を制限するために使用される、広域位相アルゴリズムです。これは、各ソリッドの境界体積の始点（下限）と終点（上限）を任意の軸に沿ってソートすることで実現されます。ソリッドが移動すると、始点と終点が重なり合うことがあります。2つのソリッドの境界体積がすべての軸で重なり合う場合、より正確で時間のかかるアルゴリズムで検査するようにフラグが立てられます。
スイープ＆プルーン法は、固体が2つのシミュレーションステップ間で大きく移動しない可能性が高いため、時間的な一貫性を利用します。そのため、各ステップにおいて、境界体積の開始点と終了点のソート済みリストを比較的少ない計算量で更新できます。挿入ソートなど、ほぼソート済みのリストを高速にソートできるソートアルゴリズムは、この目的に特に適しています。
使用する境界ボリュームの種類によっては、ソリッドの向きが変更されるたびに境界ボリュームの寸法を更新する必要があります。これを回避するには、時間的コヒーレンスを利用することで、より少ない演算で境界ボリュームの形状の変化を計算することができます。別の方法としては、境界球やその他の向きに依存しない境界ボリュームを使用する方法があります。
スイープアンドプルーンはソートアンドスイープとも呼ばれ、[ 1 ] 1992年のDavid Baraff博士論文でもこのように呼ばれています。[ 2 ]その後の研究、例えば1995年のJonathan D. Cohenらによる I-COLLIDEに関する論文[ 3 ]などでは、このアルゴリズムはスイープアンドプルーンと呼ばれています。
参照
参考文献
- ^ Ericson, Christer (2005),リアルタイム衝突検出, Morgan Kaufmann series in interactive 3D technology, Amsterdam: Elsevier, pp. 329– 338, ISBN 978-1-55860-732-3
- ^ Baraff, D. (1992)、「非貫通剛体の動的シミュレーション」（博士論文）、コーネル大学コンピュータサイエンス学部、pp. 52– 56
- ^ Cohen, Jonathan D.; Lin, Ming C .; Manocha; Ponamgi, Madhav K. (1995年4月9日～12日)、I–COLLIDE: 大規模環境向けのインタラクティブで正確な衝突検出システム(PDF)、1995年インタラクティブ3Dグラフィックスシンポジウム (カリフォルニア州モントレー) の議事録、pp. 189～ 196
外部リンク
 | この計算物理学関連の記事はスタブです。不足している情報を追加してWikipediaに貢献してください。 |
