Collision detection: Difference between revisions

Revision as of 03:42, 13 November 2024

Revision as of 04:26, 13 November 2024

Line 37:

{{Unreferenced section|date=July 2024}}|section=y}}

During the broad-phase, when the objects in the world move or deform, the data-structures used to cull collisions have to be updated. In cases where the changes between two frames or time-steps are small and the objects can approximated well with an [[axis-aligned bounding box]]es the [[sweep and prune]] algorithm<ref name=":0" /> can be a suitable approach.

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.

Several key observation make the implementation efficient: Two bounding-boxes intersect [[If and only if|if, and only if]], there is overlap along all three axes; overlap can be determined, for each axis separately, by sorting the intervals for all the boxes; and lastly, between two frames updates are typically small. The algorithm keeps track of currently intersecting boxes, and as objects moves, re-sorting the intervals helps keep track of the status<ref>{{Cite book |last=Ericson |first=Christer |url=https://realtimecollisiondetection.net/books/rtcd/ |title=Real-time collision detection |date= |publisher=Elsevier |isbn=978-1-55860-732-3 |edition=Nachdr. |series=Morgan Kaufmann series in interactive 3D technology |___location=Amsterdam Heidelberg |pages=329–338}}</ref> - making sorting algorithms optimized for almost-sorted lists suitable for this application.

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]] [http://www.cs.berkeley.edu/~jfc/mirtich/collDet.html], who suggested using [[axis-aligned bounding box]]es for all ''n'' bodies in the scene.

Each box is represented by the product of three intervals (i.e., a box would be <math>I_1 \times I_2 \times I_3=[a_1,b_1] \times [a_2,b_2] \times [a_3,b_3]</math>). A common algorithm for collision detection of bounding boxes is [[sweep and prune]]. Observe that two such boxes, <math>I_1 \times I_2 \times I_3</math> and <math>J_1 \times J_2 \times J_3</math> intersect [[If and only if|if, and only if]], <math>I_1</math> intersects <math>J_1</math>, <math>I_2</math> intersects <math>J_2</math> and <math>I_3</math> intersects <math>J_3</math>. It is supposed that, from one time step to the next, if <math>I_k</math> and <math>J_k</math> 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 <math>n</math>, 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 <math>n \times n</math> [[matrix (math)|matrix]] <math>M=(m_{ij})</math> of zeroes and ones: <math>m_{ij}</math> is 1 if intervals <math>i</math> and <math>j</math> intersect, and 0 if they do not intersect.

By our assumption, the matrix <math>M</math> 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 [[sorting algorithm|sort]] the list by coordinates, and update the matrix <math>M</math> 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 ===