衝突判定
The hope here is that these bounding spheres are much smaller than B ( S ) {\displaystyle B(S)} and B ( T ) {\displaystyle B(T)} . And, if, for instance, B ( S ) {\displaystyle B(S)} and B ( L ( T ) ) {\displaystyle B(L(T))} do not intersect, then there is no sense in checking any triangle in S {\displaystyle S} against any triangle in L ( T ) {\displaystyle L(T)} .
As a precomputation, we can take each physical body (represented by a set of triangles) and recursively decompose it into a binary tree, where each node N {\displaystyle N} represents a set of triangles, and its two children represent L ( N ) {\displaystyle L(N)} and R ( N ) {\displaystyle R(N)} .
ヒットボックス方式の一種で、衝突判定を取りたい双方のオブジェクトを「円形」または「球形」とみなす。円形の境界ボックスの事を「ヒットボックス」と呼ぶ。ちなみに海外でも円形なのに「ヒットボックス」と呼ばれる。「境界円」「ヒットサークル」と呼ばれることもまれにある。
円を中心(x,y)、半径 r で表すと、二つの円 A, B が当たっていることは「Aの中心とBの中心の距離が、Aの半径とBの半径の和以下である」ことと同値であるから、円どうしの衝突判定は
( A x − B x ) 2 + ( A y − B y ) 2 ≤ ( A r + B r ) 2 {\displaystyle (A_{x}-B_{x})^{2}+(A_{y}-B_{y})^{2}\leq (A_{r}+B_{r})^{2}}
これを3次元に拡張すると、球と球の衝突判定を行うことができる。球形の境界ボックスのことを「境界球(Bounding Sphere)」と呼ぶが、やはりこれも「ヒットボックス」と呼ぶことが多い。
( A x − B x ) 2 + ( A y − B y ) 2 + ( A z − B z ) 2 ≤ ( A r + B r ) 2 {\displaystyle (A_{x}-B_{x})^{2}+(A_{y}-B_{y})^{2}+(A_{z}-B_{z})^{2}\leq (A_{r}+B_{r})^{2}}
球と直方体であたり判定を取る場合、双方を球か直方体で近似すると計算が簡単になるが、見た目と衝突判定が食い違うのでプレイヤーが不満を抱く。一方でポリゴン同士の衝突判定とみなして衝突判定を行うと計算量が膨大になる。これらを緩和するため、直方体を楕円形で近似して衝突判定を行う方法がある(コナミの3DO M2用ゲーム『とべ!ポリスターズ』開発チームのちちびんたつかさが開発した手法)。
ヒットボックスを「点」で近似する手法がある。衝突判定のプログラムが格段に簡単になる上、自機の当たり判定が極小(1ドット)になってプレーヤーも満足する。
複雑なポリゴンモデルの衝突判定を取る場合、複数のポリゴンを一つのポリゴンとみなして衝突判定を行ったり、一旦ボクセルに変換して衝突判定を行う手法がある。また、投影像の画素ごとの奥行き値を比較して衝突判定を行うという手法もある。これらは3DOを擁する松下電器産業の開発した技術。
「壁抜け」を防ぐために、単に「フレームレートを限界まで上げる」という手法がある。ハードウェアを自作するならともかく、既定のスペックがあるゲーム機などでは厳しい。
Once we're done pruning, we are left with a number of candidate pairs to check for exact collision detection.
A basic observation is that for any two convex objects which are disjoint, one can find a plane in space so that one object lies completely on one side of that plane, and the other object lies on the opposite side of that plane. This allows the development of very fast collision detection algorithms for convex objects.
Early work in this area involved "separating plane" methods. Two triangles collide essentially only when they can not be separated by a plane going through three vertices.
ゲームにおいては衝突判定の精密性よりもリアルタイム性が重視されるので、以下のような手法がよく用いられる。