この項目「衝突判定」は途中まで翻訳されたものです。（原文：en:Collision detection（22:10, 5 November 2020）
）この記事は検証可能な参考文献や出典が全く示されていないか、不十分です。出典を追加して記事の信頼性向上にご協力ください。（このテンプレートの使い方）
出典検索?: "衝突判定" ? ニュース ・ 書籍 ・ スカラー ・ CiNii ・ J-STAGE ・ NDL ・ dlib.jp ・ ジャパンサーチ ・ TWL（2021年3月）
衝突判定（しょうとつはんてい、Collision Detection）とは、「2つ以上のオブジェクトの交差を検出する」という計算機科学上の問題であり、具体的には「ある物体が別の物体に当たったか（衝突したか）どうか」を判定するプログラム処理のことを指す。ロボット工学、計算物理学、コンピュータゲーム、コンピュータシミュレーション、計算幾何学など、さまざまなコンピューティング分野で応用されている。
衝突判定のアルゴリズムは、2Dオブジェクト同士の衝突判定と3Dオブジェクト同士の衝突判定に分けることができる[1]。
概要古典的な例だが、衝突判定を科学的に考える上で、ビリヤードの球同士がどのように当たるのかを考えてみるのもよい
ビリヤードの物理シミュレーションをする場合を考えて欲しい。剛体運動と弾性衝突と言う両軸に従って跳ね回るビリヤードの球の物理学は、おそらく読者諸君もよく理解しているだろう。シミュレーションを始める前に、まず、ビリヤード台とボールの非常に正確な物理的記述、そしてすべてのボールの初期位置という、初期状態が提示される。キューボールに「力が加えられる（おそらくはプレーヤーがキュースティックでボールを打ったことが想定される）」という事象が適用された場合、コンピューターのプログラムに従い、すべての球の軌道、正確な動き、および球の最終的な休止場所が算出される。このゲームをシミュレートするプログラムは、いくつかのプログラムのまとまりによって構成されているが、そのうちの1つはビリヤードの球どうしの正確な衝撃を計算する役目を果たす。もちろん、しくじることもある。計算に小さなエラーがあると、ビリヤードボールの最終的な位置が大幅に変化することになる。
ゲームで衝突判定を行う場合もだいたい同じであるが、いくつかの重要な違いがある。一般的なコンピュータシミュレーションでは、現実世界の物理を可能な限り正確にシミュレートする必要があるが、コンピュータゲームにおいては、ハードの性能が許す範囲内で、リアルタイム性を損なわず、なおかつバグが起きないようにシミュレートする必要がある。シミュレーションで得られた結果が、ゲームのプレーヤーが十分満足する範囲内である限り、妥協は許される。 物質は衝突時の反応方法が当然異なるので。物理シミュレーターでは材質の柔らかさを利用して力を計算するものがある。これにより、現実と同様に次の時間ステップで衝突が解決される。しかし、一部のマテリアルは柔軟性が低いものがあり、これをシミュレーションするとには CPU に非常に高い負荷をかけることとなる。これは演算のレイテンシにつながるため 線形補間やシミュレーションの ロールバック
コンピューターシミュレーションによる衝突判定
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
A posteriori (discrete) versus a priori (continuous)
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 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
Optimization
Exploiting temporal coherence
Each box is represented by the product of three intervals (i.e., a box would be I 1 × I 2 × I 3 = [ a 1 , b 1 ] × [ a 2 , b 2 ] × [ a 3 , b 3 ] {\displaystyle 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 × I 2 × I 3 {\displaystyle I_{1}\times I_{2}\times I_{3}} and J 1 × J 2 × J 3 {\displaystyle J_{1}\times J_{2}\times J_{3}} intersect if, and only if, I 1 {\displaystyle I_{1}} intersects J 1 {\displaystyle J_{1}} , I 2 {\displaystyle I_{2}} intersects J 2 {\displaystyle J_{2}} and I 3 {\displaystyle I_{3}} intersects J 3 {\displaystyle J_{3}} . We suppose that, from one time step to the next, I k {\displaystyle I_{k}} and J k {\displaystyle 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.
