衝突判定
衝突判定(しょうとつはんてい、Collision Detection)とは、「2つ以上のオブジェクトの交差を検出する」という計算機科学上の問題であり、具体的には「ある物体が別の物体に当たったか(衝突したか)どうか」を判定するプログラム処理のことを指す。ロボット工学、計算物理学、コンピュータゲーム、コンピュータシミュレーション、計算幾何学など、さまざまなコンピューティング分野で応用されている。
衝突判定のアルゴリズムは、2Dオブジェクト同士の衝突判定と3Dオブジェクト同士の衝突判定に分けることができる。
ビリヤードの物理シミュレーションをする場合を考えて欲しい。剛体運動と弾性衝突と言う両軸に従って跳ね回るビリヤードの球の物理学は、おそらく読者諸君もよく理解しているだろう。シミュレーションを始める前に、まず、ビリヤード台とボールの非常に正確な物理的記述、そしてすべてのボールの初期位置という、初期状態が提示される。キューボールに「力が加えられる(おそらくはプレーヤーがキュースティックでボールを打ったことが想定される)」という事象が適用された場合、コンピューターのプログラムに従い、すべての球の軌道、正確な動き、および球の最終的な休止場所が算出される。このゲームをシミュレートするプログラムは、いくつかのプログラムのまとまりによって構成されているが、そのうちの1つはビリヤードの球どうしの正確な衝撃を計算する役目を果たす。もちろん、しくじることもある。計算に小さなエラーがあると、ビリヤードボールの最終的な位置が大幅に変化することになる。
ゲームで衝突判定を行う場合もだいたい同じであるが、いくつかの重要な違いがある。一般的なコンピュータシミュレーションでは、現実世界の物理を可能な限り正確にシミュレートする必要があるが、コンピュータゲームにおいては、ハードの性能が許す範囲内で、リアルタイム性を損なわず、なおかつバグが起きないようにシミュレートする必要がある。シミュレーションで得られた結果が、ゲームのプレーヤーが十分満足する範囲内である限り、妥協は許される。
Physical simulators differ in the way they react on a collision. Some use the softness of the material to calculate a force, which will resolve the collision in the following time steps like it is in reality. Due to the low softness of some materials this is very CPU intensive. Some simulators estimate the time of collision by linear interpolation, roll back the simulation, and calculate the collision by the more abstract methods of conservation laws.
Some iterate the linear interpolation (Newton's method) to calculate the time of collision with a much higher precision than the rest of the simulation. Collision detection utilizes time coherence to allow even finer time steps without much increasing CPU demand, such as in air traffic control.
After an inelastic collision, special states of sliding and resting can occur and, for example, the Open Dynamics Engine uses constraints to simulate them. Constraints avoid inertia and thus instability. Implementation of rest by means of a scene graph avoids drift.
In other words, physical simulators usually function one of two ways, where the collision is detected a posteriori (after the collision occurs) or a priori (before the collision occurs). In addition to the a posteriori and a priori distinction, almost all modern collision detection algorithms are broken into a hierarchy of algorithms. Often the terms "discrete" and "continuous" are used rather than a posteriori and a priori.
In the a posteriori case, we advance the physical simulation by a small time step, then check if any objects are intersecting, or are somehow so close to each other that we deem them to be intersecting. At each simulation step, a list of all intersecting bodies is created, and the positions and trajectories of these objects are somehow "fixed" to account for the collision. We say that this method is a posteriori because we typically miss the actual instant of collision, and only catch the collision after it has actually happened.
In the a priori methods, we write a collision detection algorithm which will be able to predict very precisely the trajectories of the physical bodies. The instants of collision are calculated with high precision, and the physical bodies never actually interpenetrate. We call this a priori because we calculate the instants of collision before we update the configuration of the physical bodies.
The main benefits of the a posteriori methods are as follows. In this case, the collision detection algorithm need not be aware of the myriad of physical variables; a simple list of physical bodies is fed to the algorithm, and the program returns a list of intersecting bodies. The collision detection algorithm doesn't need to understand friction, elastic collisions, or worse, nonelastic collisions and deformable bodies. In addition, the a posteriori algorithms are in effect one dimension simpler than the a priori algorithms. Indeed, an a priori algorithm must deal with the time variable, which is absent from the a posteriori problem.
On the other hand, a posteriori algorithms cause problems in the "fixing" step, where intersections (which aren't physically correct) need to be corrected. Moreover, if the discrete step is too large, the collision could go undetected, resulting in an object which passes through another if it is sufficiently fast or small.
The benefits of the a priori algorithms are increased fidelity and stability.  It is difficult (but not completely impossible) to separate the physical simulation from the collision detection algorithm. However, in all but the simplest cases, the problem of determining ahead of time when two bodies will collide (given some initial data) has no closed form solution—a numerical root finder is usually involved.
Some objects are in resting contact, that is, in collision, but neither bouncing off, nor interpenetrating, such as a vase resting on a table. In all cases, resting contact requires special treatment: If two objects collide (a posteriori) or slide (a priori) and  their relative motion is below a threshold, friction becomes stiction and both objects are arranged in the same branch of the scene graph.
The obvious approaches to collision detection for multiple objects are very slow.
Checking every object against every other object will, of course, work, but is too inefficient to be used when the number of objects is at all large.  Checking objects with complex geometry against each other in the obvious way, by checking each face against each other face, is itself quite slow.  Thus, considerable research has been applied to speed up the problem.
In many applications, the configuration of physical bodies from one time step to the next changes very little.  Many of the objects may not move at all.
Algorithms have been designed so that the calculations done in a preceding time step can be reused in the current time step, resulting in faster completion of the calculation.
At the coarse level of collision detection, the objective is to find pairs of objects which might potentially intersect.  Those pairs will require further analysis.  An early high performance algorithm for this was developed by Ming C. Lin at the University of California, Berkeley , who suggested using axis-aligned bounding boxes for all n bodies in the scene.
Each box is represented by the product of three intervals (i.e., a box would be I_1 \times I_2 \times I_3=[a_1,b_1] \times [a_2,b_2] \times [a_3,b_3]). A common algorithm for collision detection of bounding boxes is sweep and prune. We observe that two such boxes, I_1 \times I_2 \times I_3 and J_1 \times J_2 \times J_3 intersect if, and only if, I_1 intersects J_1, I_2 intersects J_2 and I_3 intersects J_3. We suppose that, from one time step to the next, I_k and J_k intersect, then it is very likely that at the next time step, they will still intersect. Likewise, if they did not intersect in the previous time step, then they are very likely to continue not to.
So we reduce the problem to that of tracking, from frame to frame, which intervals do intersect. We have three lists of intervals (one for each axis) and all lists are the same length (since each list has length n, the number of bounding boxes.) In each list, each interval is allowed to intersect all other intervals in the list. So for each list, we will have an n \times n matrix M=(m_{ij}) of zeroes and ones: m_{ij} is 1 if intervals i and j intersect, and 0 if they do not intersect.
By our assumption, the matrix M associated to a list of intervals will remain essentially unchanged from one time step to the next. To exploit this, the list of intervals is actually maintained as a list of labeled endpoints. Each element of the list has the coordinate of an endpoint of an interval, as well as a unique integer identifying that interval. Then, we sort the list by coordinates, and update the matrix 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.
Once we've selected a pair of physical bodies for further investigation, we need to check for collisions more carefully. However, in many applications, individual objects (if they are not too deformable) are described by a set of smaller primitives, mainly triangles. So now, we have two sets of triangles, S={S_1,S_2,\dots,S_n} and T={T_1,T_2,\dots,T_n} (for simplicity, we will assume that each set has the same number of triangles.)
The obvious thing to do is to check all triangles S_j against all triangles T_k for collisions, but this involves n^2 comparisons, which is highly inefficient. If possible, it is desirable to use a pruning algorithm to reduce the number of pairs of triangles we need to check.
The most widely used family of algorithms is known as the hierarchical bounding volumes method. As a preprocessing step, for each object (in our example, S and T) we will calculate a hierarchy of bounding volumes. Then, at each time step, when we need to check for collisions between S and T, the hierarchical bounding volumes are used to reduce the number of pairs of triangles under consideration. For simplicity, we will give an example using bounding spheres, although it has been noted that spheres are undesirable in many cases.June 2008
If E is a set of triangles, we can precalculate a bounding sphere B(E). There are many ways of choosing B(E), we only assume that B(E) is a sphere that completely contains E and is as small as possible.
Ahead of time, we can compute B(S) and B(T). Clearly, if these two spheres do not intersect (and that is very easy to test), then neither do S and T. This is not much better than an n-body pruning algorithm, however.
If 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,\dots,E_{m/2} and R(E):={E_{m/2+1},\dots,E_{m-1},E_m}. We can do this to S and T, and we can calculate (ahead of time) the bounding spheres B(L(S)),B(R(S)) and B(L(T)),B(R(T)). The hope here is that these bounding spheres are much smaller than B(S) and B(T). And, if, for instance, B(S) and B(L(T)) do not intersect, then there is no sense in checking any triangle in S against any triangle in 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 represents a set of triangles, and its two children represent L(N) and R(N). At each node in the tree, we can precompute the bounding sphere 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). 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.
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.