衝突判定(しょうとつはんてい、Collision Detection)とは、「2つ以上のオブジェクトの交差を検出する」という計算機科学上の問題であり、具体的には「ある物体が別の物体に当たったか(衝突したか)どうか」を判定するプログラム処理のことを指す。ロボット工学計算物理学コンピュータゲームコンピュータシミュレーション計算幾何学など、さまざまなコンピューティング分野で応用されている。






Collision detection in computer simulation編集

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.

A posteriori (discrete) versus a priori (continuous)編集

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.

Exploiting temporal coherence編集

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 [1], 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  ). A common algorithm for collision detection of bounding boxes is sweep and prune. We observe that two such boxes,   and   intersect if, and only if,   intersects  ,   intersects   and   intersects  . We suppose that, from one time step to the next,   and   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  , 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   matrix   of zeroes and ones:   is 1 if intervals   and   intersect, and 0 if they do not intersect.

By our assumption, the matrix   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   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.

Pairwise pruning編集

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,   and   (for simplicity, we will assume that each set has the same number of triangles.)

The obvious thing to do is to check all triangles   against all triangles   for collisions, but this involves   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,   and  ) we will calculate a hierarchy of bounding volumes. Then, at each time step, when we need to check for collisions between   and  , 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.[要出典]

If   is a set of triangles, we can precalculate a bounding sphere  . There are many ways of choosing  , we only assume that   is a sphere that completely contains   and is as small as possible.

Ahead of time, we can compute   and  . Clearly, if these two spheres do not intersect (and that is very easy to test), then neither do   and  . This is not much better than an n-body pruning algorithm, however.

If   is a set of triangles, then we can split it into two halves   and  . We can do this to   and  , and we can calculate (ahead of time) the bounding spheres   and  . The hope here is that these bounding spheres are much smaller than   and  . And, if, for instance,   and   do not intersect, then there is no sense in checking any triangle in   against any triangle in  .

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   represents a set of triangles, and its two children represent   and  . At each node in the tree, we can precompute the bounding sphere  .

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  . 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.

Exact pairwise collision detection編集

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. That is, if the triangles are   and   where each   is a vector in  , then we can take three vertices,  , find a plane going through all three vertices, and check to see if this is a separating plane. If any such plane is a separating plane, then the triangles are deemed to be disjoint. On the other hand, if none of these planes are separating planes, then the triangles are deemed to intersect. There are twenty such planes.

If the triangles are coplanar, this test is not entirely successful. One can add some extra planes, for instance, planes that are normal to triangle edges, to fix the problem entirely. In other cases, objects that meet at a flat face must necessarily also meet at an angle elsewhere, hence the overall collision detection will be able to find the collision.

Better methods have since been developed. Very fast algorithms are available for finding the closest points on the surface of two convex polyhedral objects. Early work by Ming C. Lin[2] used a variation on the simplex algorithm from linear programming. The Gilbert-Johnson-Keerthi distance algorithm has superseded that approach. These algorithms approach constant time when applied repeatedly to pairs of stationary or slow-moving objects, when used with starting points from the previous collision check.

The end result of all this algorithmic work is that collision detection can be done efficiently for thousands of moving objects in real time on typical personal computers and game consoles.

A priori pruning編集

Where most of the objects involved are fixed, as is typical of video games, a priori methods using precomputation can be used to speed up execution.

Pruning is also desirable here, both n-body pruning and pairwise pruning, but the algorithms must take time and the types of motions used in the underlying physical system into consideration.

When it comes to the exact pairwise collision detection, this is highly trajectory dependent, and one almost has to use a numerical root-finding algorithm to compute the instant of impact.

As an example, consider two triangles moving in time   and  . At any point in time, the two triangles can be checked for intersection using the twenty planes previously mentioned. However, we can do better, since these twenty planes can all be tracked in time. If   is the plane going through points   in   then there are twenty planes   to track. Each plane needs to be tracked against three vertices, this gives sixty values to track. Using a root finder on these sixty functions produces the exact collision times for the two given triangles and the two given trajectory. We note here that if the trajectories of the vertices are assumed to be linear polynomials in   then the final sixty functions are in fact cubic polynomials, and in this exceptional case, it is possible to locate the exact collision time using the formula for the roots of the cubic. Some numerical analysts suggest that using the formula for the roots of the cubic is not as numerically stable as using a root finder for polynomials.[要出典]

Spatial partitioning編集

Alternative algorithms are grouped under the spatial partitioning umbrella, which includes octrees, binary space partitioning (or BSP trees) and other, similar approaches. If one splits space into a number of simple cells, and if two objects can be shown not to be in the same cell, then they need not be checked for intersection. Since BSP trees can be precomputed, that approach is well suited to handling walls and fixed obstacles in games. These algorithms are generally older than the algorithms described above.

Bounding boxes編集

Bounding boxes (or bounding volumes) are most often a 2D rectangle or 3D cuboid, but other shapes are possible. A bounding box in a video game is sometimes called a Hitbox. The bounding diamond, the minimum bounding parallelogram, the convex hull, the bounding circle or bounding ball, and the bounding ellipse have all been tried, but bounding boxes remain the most popular due to their simplicity.[3] Bounding boxes are typically used in the early (pruning) stage of collision detection, so that only objects with overlapping bounding boxes need be compared in detail.

Triangle centroid segments編集

A triangle mesh object is commonly used in 3D body modeling. Normally the collision function is a triangle to triangle intercept or a bounding shape associated with the mesh. A triangle centroid is a center of mass location such that it would balance on a pencil tip. The simulation need only add a centroid dimension to the physics parameters. Given centroid points in both object and target it is possible to define the line segment connecting these two points.

The position vector of the centroid of a triangle is the average of the position vectors of its vertices. So if its vertices have Cartesian coordinates  ,   and   then the centroid is  .

Here is the function for a line segment distance between two 3D points.  

Here the length/distance of the segment is an adjustable "hit" criteria size of segment. As the objects approach the length decreases to the threshold value. A triangle sphere becomes the effective geometry test. A sphere centered at the centroid can be sized to encompass all the triangle's vertices.







シミュレーションの堅実性は、あらゆる入力に合理的な方法で反応するかどうかで決まる。たとえば超高速なレーシングゲームを想像すると、1つのシミュレーションステップから次のシミュレーションステップへと移行するごとに(つまり、1フレームごとに)、車はレーシングトラックに沿ってかなりの距離を進むことが想定される。もしトラックに薄い障害物(レンガの壁など)があった場合、フレームごとの移動距離が大きすぎて衝突判定が間に合わず、車が壁をすり抜けるバグが起こりがちだが、現実世界では車が壁をすり抜ける可能性はまったくない。シミュレーションと言う観点からすると、これは非常に望ましくないバグである。他の例を挙げると、事後衝突判定アルゴリズムが必要とする「軌道修正(フィックス)」が正しく実装されていないため、キャラクターがフィールドに復帰できず、壁の中にキャラクターが閉じ込められたり、キャラクターが壁を通過したりして、下に床が無い場合は無限に落下し続ける致命的なバグが発生することがある。「無限落下」や「ケツワープ」などと呼ばれるバグが知られている。これらのバグは、衝突判定および物理シミュレーションシステムの欠陥によるものである。『Big Rigs:Over the Road Racing』は、衝突判定システムにバグがある、もしくは衝突判定システムが欠如していることにより、「史上最低のクソゲー」として名高い。



ヒットボックスは、キャラクターと敵の打撃や弾丸との衝突判定を取る場合など、「一方向」の衝突を検出するために使用される。衝突によってフィードバックが発生する場合、例えば壁にぶつかった際にフィードバックによって反発が起き、すぐ次のフレームでは壁から引き離される、と言うような場合は、ヒットボックスの位置が絶えず変化することになり、ヒットボックスの位置の管理がとても面倒になるので、ヒットボックス方式を使うのは適していない。このような場合はヒットボックス方式より単純な実装である「軸並行境界ボックス方式(Axis-Aligned Bounding Box、AABB方式)」を使うのが適している。しかしプレーヤー目線では、これらの実装方式を区別せず、どちらも単に「ヒットボックス」と言う場合も多い。






2D空間において、それぞれの矩形を座標(x, y) と幅・高さ(lx, ly) で表す。ふたつの矩形A・矩形B について衝突判定を行うには、以下の条件が成り立っているかどうかを調べる。成り立てば当たり、そうでなければ外れと判定できる。


3D空間においては、衝突判定を取りたい双方のオブジェクトを「直方体」とみなし、幅・高さ・奥行き(lx, ly, lz) で表す以外は上と同じである。




円を中心(x,y)、半径 r で表すと、二つの円 A, B が当たっていることは「Aの中心とBの中心の距離が、Aの半径とBの半径の和以下である」ことと同値であるから、円どうしの衝突判定は


これを3次元に拡張すると、球と球の衝突判定を行うことができる。球形の境界ボックスのことを「境界球(Bounding Sphere)」と呼ぶが、やはりこれも「ヒットボックス」と呼ぶことが多い。



特に3D空間で衝突判定を取る場合において、上記の方式では管理が面倒になる場合は「軸並行境界ボックス方式(Axis Aligned Bounding Box, AABB方式)」を使う。

ヒットボックス方式の「基本的な方法」ではオブジェクトのバウンディングボックス(境界ボックス)の左上の点をオブジェクト自体の座標とみなし、そこから右下までの長さを取るのが一般的なのに対して、AABB方式ではヒットボックスの中心座標をオブジェクト自体の座標とみなし、そこからxyz軸方向に±何mの広がりがある、という表し方をする。ヒットボックスの中心を(x,y,z), 双方向への広がりの大きさを(rx,ry,rz)とすると、このヒットボックスは x方向については x-rx ~ x+rx, y方向には y-ry ~ y+ry, z方向には z-rz ~ z+rz の範囲を占める。軸並行境界ボックス方式を用いてふたつのヒットボックスA・Bについて衝突判定を行うには、以下のようになる。





有向境界ボックス(Oriented Bounding Box)。

ピクセルパーフェクト方式(pixel perfect collision detectionまたはper-pixel collision detection, PPCD)編集

2Dゲームにおいて、ピクセル単位で衝突判定を取る方式。スプライト画像をベースとする衝突判定の方式なのでimage-based collision detectionともいう。1980年代頃までの8bit機ではスプライトの表示位置ごとの衝突判定を取ることしかできなかったが(当時のスプライトの大きさは基本的に8x8であったため、8ドット単位の衝突判定になった)、この方式を用いることで、1ドット単位の衝突判定が可能になる。





バイナリ空間分割木(Binary space partitioning, BSP木)を用いる方法。広大な3D空間において衝突判定を行いたい場合、空間をいくつかの区画に分割して刈り込む、と言う方法を取る。


上記の衝突判定ではすべて、オブジェクト同士が衝突しているかどうかを「1フレームごと」にチェックする、つまり「離散的(Discrete)」な衝突検出法を用いた。1フレームごとにしか衝突判定を行わないことで、高速な衝突判定が行えるが、しかしこの方式を用いた場合、オブジェクトが速すぎてヒットボックスが1フレーム以下の時間で壁を通り過ぎてしまって衝突判定が行われない、トンネリング(いわゆる「壁抜け」)が起こりがちである。それを防ぐためには、1フレームごとに離散的に衝突判定を行うのではなく、連続的に衝突判定を行う「連続的衝突判定」(Continuous Collision Detection, CCD)と言う手法を取るのが一般的である。そのための最も一般的な手法がこれである。

オブジェクトを球体で近似する。この球が、現在の速度で直線的に動くと考え、「ある点」から「ある点」まで移動することで出来る軌跡を考える。この結果できた、カプセルのような形をしたボリューム(掃引体)のことを「球体スウィープボリューム(sphere-swept volume:SSV)」と言う。このボリュームが別のオブジェクトと接触していた場合、衝突が発生していると考えられる。

球体スウィープボリューム同士の衝突判定を行うことで、高速に動くオブジェクト同士の衝突判定も行える。動く球同士の衝突判定の取り方を説明すると、動く球は、移動開始時の中心・速度ベクトルV・半径、で表すことができる。現在のフレーム(フレーム0)と次のフレーム(フレーム1)の間の時間において、0 < t < 1 となる媒介変数 t を使うと、球Aの中心は (A0 + t Va), 球Bの中心は (B0 + t Vb) と表せる。このように動いていく球A・球Bの中心どうしの距離が、半径の和以下になるような時刻 t が存在するか? を求める。






  • 球と直方体であたり判定を取る場合、双方を球か直方体で近似すると計算が簡単になるが、見た目と衝突判定が食い違うのでプレイヤーが不満を抱く。一方でポリゴン同士の衝突判定とみなして衝突判定を行うと計算量が膨大になる。これらを緩和するため、直方体を楕円形で近似して衝突判定を行う方法がある(コナミの3DO M2用ゲーム『とべ!ポリスターズ』開発チームのちちびんたつかさが開発した手法[8])。
  • ヒットボックスを「点」で近似する手法がある。衝突判定のプログラムが格段に簡単になる上、自機の当たり判定が極小(1ドット)になってプレーヤーも満足する。
  • 複雑なポリゴンモデルの衝突判定を取る場合、複数のポリゴンを一つのポリゴンとみなして衝突判定を行ったり、一旦ボクセルに変換して衝突判定を行う手法がある。また、投影像の画素ごとの奥行き値を比較して衝突判定を行うという手法もある。これらは3DOを擁する松下電器産業の開発した技術[9]
  • 「壁抜け」を防ぐために、単に「フレームレートを限界まで上げる」という手法がある。ハードウェアを自作するならともかく、既定のスペックがあるゲーム機などでは厳しい。



  1. ^ Collision Detection for Deformable Objects. doi:10.1111/j.1467-8659.2005.00829.x. https://hal.inria.fr/inria-00394479/document. 
  2. ^ Lin, Ming C (1993). Efficient Collision Detection for Animation and Robotics (thesis). University of California, Berkeley. https://wwwx.cs.unc.edu/~geom/papers/documents/dissertations/lin93.pdf. 
  3. ^ Caldwell, Douglas R. (2005-08-29). Unlocking the Mysteries of the Bounding Box. US Army Engineer Research & Development Center, Topographic Engineering Center, Research Division, Information Generation and Management Branch. オリジナルの2012-07-28時点におけるアーカイブ。. https://web.archive.org/web/20120728180104/http://www.stonybrook.edu/libmap/coordinates/seriesa/no2/a2.htm 2014年5月13日閲覧。. 
  4. ^ Components of the Amiga: The MC68000 and the Amiga Custom Chips”. 2018年7月17日時点のオリジナルよりアーカイブ。2018年7月17日閲覧。 “Additionally, you can use system hardware to detect collisions between objects and have your program react to such collisions.”
  5. ^ Hitbox”. Valve Developer Community. Valve. 2011年9月18日閲覧。
  6. ^ 特開平7-230559「衝突判定処理システムおよびこれを用いた画像処理装置」。ちなみにこのセガの特許はゲーム業界では非常に重要な特許であったようで、セガがゲーム機から撤退する前には競合機においてこれを回避するかのような特許が出願されている他、セガがサードパーティになった後は例えば任天堂株式会社の特開2017-217334「ゲーム装置、ゲーム制御方法およびゲームプログラム」(Wii Uの特許)などでも引用されている。なお1994年に出願したものであり、2014年に失効している。
  7. ^ ビデオゲームの語り部たち 第2部:「バーチャファイター」のプロトタイプに込められた石井精一氏の人生
  8. ^ 特開平10-165648「当たり判定装置,及びコンピュータプログラムを記録した媒体」
  9. ^ 特開平11-328445「衝突判定装置および方法、および衝突判定方法を記録した媒体」。おそらくは競合機セガサターンを展開する前記のセガの特許を回避するためである