Mac用プロットライブラリ-24「重なりチェック」

QTKit Captureのお勉強でしばらくお休みしていた3次元プロットでの隠面陰線消去について考えている。結構、いやすっかり忘れてるのでもう一度おさらいすると

1. 3次元オブジェクトに射影変換を行って2次元に変換する。そのとき奥行き方向の値も保持する
2. 奥行き方向の値に従って並べ替える
3. 遠いオブジェクトから描画して近くのオブジェクトはそれを上描きする

という一番簡単な方法で隠面消去をすることにした。

前回まで、奥行きに従って並べ替えるときの問題を考えていた。オブジェクトは半順序集合になって普通のソートアルゴリズムでは対応できないことがわかった。そこで半順序集合を非循環有向グラフとして表現してそれを再帰的に取り出すことで並べ替えをすることにした。

つぎに、今回からオブジェクトの前後関係をどうやって調べるか、という問題を考える。すなわち、頂点しか座標値を持っていないオブジェクトの前後関係をどうやって比較するかという問題になる。オブジェクトの間に重なりがなければ順序を考える必要はない。

ということで次に考えなければいけないのは3次元オブジェクトが射影変換によって平面に並んだ２次元オブジェクトとして重なっているかどうかをどうやって判定するか、ということ。

一般的な手法

AABB

ゲームではいわゆる「当たり判定」といって、キャラ同士が接触しているかどうかを判定することが必要な場合がある。古い2Dのゲームでは図-18のようなAABB（Axes Aligned Bounding Box）というオブジェクトに外接する座標軸に平行な長方形が交差するかどうか、で判定していた。

これは座標の値の最大値と最小値だけで判定ができるので簡単だけど、かなりおおざっぱなものになる。これは2次元ビットマップの32ドット×32ドット程度のキャラクターの接触判定など小さなオブジェクトどうしに対して使われることが多い。

それでも例えば図-19のような配置の場合はAABBによる当たり判定で十分である。

ところが図-20のような左右ふたつの場合は、両方ともAABBでの判定では重なっていることになってしまう。

交差判定法

ゲームなどで次によく使われる簡単な方法は「交差判定」などと呼ばれる方法である。これはある点がオブジェクトに内包されているか、外にあるかを判定する方法で、例えばある点というのがミサイルの先端で、オブジェクトが宇宙船、などの場合である。

判定したい点から一方の方向（もちろんどの方向を向いていてもよいので、どれかの軸に沿うのが簡単）に線を引く。その線がオブジェクトの境界と奇数回交差したら内部の点で、偶数回なら外部の点となる。この判定法はアイデアが簡単なので、よく使われるが

• 判定のための線がちょうど頂点を通ったときには誤判定を起こす
• 頂点のデータしかないオブジェクト（ポリゴン）では辺を計算してから判定する必要がある
• 開領域のオブジェクトが混じっている場合、適用できない

などの問題がある。また、これをオブジェクトどうしの重なりの判定に使おうとすると、例えば図-22のように、

オブジェクトの頂点はどれも相手のオブジェクトと重なっていないけど、オブジェクトそのものは重なっている、と言う場合には使えないと言うことになる。

辺どうしの交差の判定

この場合には辺どうしが重なっていないかを判定する必要がある。この場合は面倒で、辺をなす直線が交差するかどうかを判定しなければいけない。しかし、例えば図-23のような場合には、辺は交差していないのに重なっていると判断できなければいけない。

辺の交差は計算量が増えてしまうのであまりやりたくない。

ということで、非常に面倒なことになった。

整理

整理すると、二つのオブジェクトに対して

1. AABBによる判定をする
2. 重なりなしなら、オブジェクトの重なりは無いとする
3. 重なりありなら、頂点に対して交差判定法を使う
1. 重なりありなら、オブジェクトの重なりはあるとする
2. 重なりなしなら、辺に対して交差するか調べる
1. 交差していたら、オブジェクトの重なりはあるとする
2. 交差していなかったら、オブジェクトの重なりはなしとする

ということになる。

ややこしいので図-24にフローチャートにする。

もっと簡単な方法って無いのかなあ。みんなどうしてるんだろ？

その他の判定法

ついでにほかの判定法について見てみる。

点がオブジェクトに内包されているかどうかを判定する方法として、交差判定法以外に次のようなものがある。

オブジェクトのそれぞれの頂点をO_nとする。そして番号は連続して振られている（隣り合う点を）とする。内包しているかどうかをチェックしたい点をPとする。Pを頂角とするO_nPO_n+1の符号も含めた角度をa_nとする。この角度を全部足したA

を計算する。この値が2πなら内包されていて、0なら内包されていない。図-25を見てみれば直感的に理解できる。この方法はあまりエクスキューズがなくて実装も簡単。

しかし当然、直感的に理解できるようにこの方法はarccosを計算する必要があるので非常に計算量が多い。

例えば、オブジェクトが凸多角形だけを前提にできるなら、上の方法を簡単化して角度の和を計算するかわりに、判定する点からオブジェクトの頂点へのベクトルを、ふたつずつ順番にベクトル積をとっていく。すべてのベクトル積の符号が同じなら判定点はオブジェクトの内部である。

オブジェクトが凸多角形だけ、という制限はなかなか厳しいのでどうしようもなくなったら考えることにして、このやり方は保留とする。

ほかにも判定法はあるらしい。でも、今回のような場合をいっぱつで解決できる方法は見つからなかった。