衝突判定
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.
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.
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 {\displaystyle S} and T {\displaystyle T} ) we will calculate a hierarchy of bounding volumes. Then, at each time step, when we need to check for collisions between S {\displaystyle S} and T {\displaystyle T} , the hierarchical bounding volumes are used to reduce the number of pairs of triangles under consideration.
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.
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.
ビリヤードの物理シミュレーションをする場合を考えて欲しい。剛体運動と弾性衝突と言う両軸に従って跳ね回るビリヤードの球の物理学は、おそらく読者諸君もよく理解しているだろう。シミュレーションを始める前に、まず、ビリヤード台とボールの非常に正確な物理的記述、そしてすべてのボールの初期位置という、初期状態が提示される。キューボールに「力が加えられる(おそらくはプレーヤーがキュースティックでボールを打ったことが想定される)」という事象が適用された場合、コンピューターのプログラムに従い、すべての球の軌道、正確な動き、および球の最終的な休止場所が算出される。このゲームをシミュレートするプログラムは、いくつかのプログラムのまとまりによって構成されているが、そのうちの1つはビリヤードの球どうしの正確な衝撃を計算する役目を果たす。もちろん、しくじることもある。計算に小さなエラーがあると、ビリヤードボールの最終的な位置が大幅に変化することになる。
ゲームで衝突判定を行う場合もだいたい同じであるが、いくつかの重要な違いがある。一般的なコンピュータシミュレーションでは、現実世界の物理を可能な限り正確にシミュレートする必要があるが、コンピュータゲームにおいては、ハードの性能が許す範囲内で、リアルタイム性を損なわず、なおかつバグが起きないようにシミュレートする必要がある。シミュレーションで得られた結果が、ゲームのプレーヤーが十分満足する範囲内である限り、妥協は許される。
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. 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.