衝突判定
At each node in the tree, we can precompute the bounding sphere B ( N ) {\displaystyle B(N)} .
When the time comes for testing a pair of objects for collision, their bounding sphere tree can be used to eliminate many pairs of triangles.
Many variants of the algorithms are obtained by choosing something other than a sphere for B ( T ) {\displaystyle B(T)} . If one chooses axis-aligned bounding boxes, one gets AABBTrees. Oriented bounding box trees are called OBBTrees. Some trees are easier to update if the underlying object changes. Some trees can accommodate higher order primitives such as splines instead of simple triangles.
上記の衝突判定ではすべて、オブジェクト同士が衝突しているかどうかを「1フレームごと」にチェックする、つまり「離散的(Discrete)」な衝突検出法を用いた。1フレームごとにしか衝突判定を行わないことで、高速な衝突判定が行えるが、しかしこの方式を用いた場合、オブジェクトが速すぎてヒットボックスが1フレーム以下の時間で壁を通り過ぎてしまって衝突判定が行われない、トンネリング(いわゆる「壁抜け」)が起こりがちである。それを防ぐためには、1フレームごとに離散的に衝突判定を行うのではなく、連続的に衝突判定を行う「連続的衝突判定」(Continuous Collision Detection, CCD)と言う手法を取るのが一般的である。そのための最も一般的な手法がこれである。
オブジェクトを球体で近似する。この球が、現在の速度で直線的に動くと考え、「ある点」から「ある点」まで移動することで出来る軌跡を考える。この結果できた、カプセルのような形をしたボリューム(掃引体)のことを「球体スウィープボリューム(sphere-swept volume:SSV)」と言う。このボリュームが別のオブジェクトと接触していた場合、衝突が発生していると考えられる。
This is not much better than an n-body pruning algorithm, however.
If E = E 1 , E 2 , ... , E m {\displaystyle E={E_{1},E_{2},\dots ,E_{m}}} is a set of triangles, then we can split it into two halves L ( E ) := E 1 , E 2 , ... , E m / 2 {\displaystyle L(E):={E_{1},E_{2},\dots ,E_{m/2}}} and R ( E ) := E m / 2 + 1 , ... , E m − 1 , E m {\displaystyle R(E):={E_{m/2+1},\dots ,E_{m-1},E_{m}}} . We can do this to S {\displaystyle S} and T {\displaystyle T} , and we can calculate (ahead of time) the bounding spheres B ( L ( S ) ) , B ( R ( S ) ) {\displaystyle B(L(S)),B(R(S))} and B ( L ( T ) ) , B ( R ( T ) ) {\displaystyle B(L(T)),B(R(T))} .
Then, we sort the list by coordinates, and update the matrix M {\displaystyle M} as we go. It's not so hard to believe that this algorithm will work relatively quickly if indeed the configuration of bounding boxes does not change significantly from one time step to the next.
In the case of deformable bodies such as cloth simulation, it may not be possible to use a more specific pairwise pruning algorithm as discussed below, and an n-body pruning algorithm is the best that can be done.
If an upper bound can be placed on the velocity of the physical bodies in a scene, then pairs of objects can be pruned based on their initial distance and the size of the time step.