Minkowski Portal Refinement

Minkowski Portal Refinement（通称：MPR）とは、2006年にGary Snethenによって作成された 主に物理演算の当たり判定で使われている凸形状間の衝突検出アルゴリズムである。

このアルゴリズムを実装した最初のライブラリの名称である「XenoCollide」と呼ばれることもある。

XenoCollideはEidos Interactiveがスクウェア・エニックスに買収される直前の最後の作品である「トゥームレイダー： アンダーワールド」で使われているそうだ。日本語版はスパイクから発売された。

• https://www.amazon.co.jp/dp/B001K7HX6G/

オリジナルのMPRのソースコードとアルゴリズムの詳細説明は書籍「Game Programming Gems 7」に掲載されている。

• https://www.amazon.co.jp/dp/4862460763

オープンソースの実装としてはlibccdがある。

• https://github.com/danfis/libccd

MPRとGJKはよく似ている。 どちらもサポートマップを利用し衝突検出を行う。 ただしGJKでは扱える「分離した形状のサポートマップ」が扱えない。 その代わりMPRの方が計算量は少ないとしている。

外部リンク

• http://xenocollide.snethen.com/