Collision detection: Difference between revisions

Revision as of 00:27, 31 October 2024

Revision as of 04:03, 1 November 2024

Line 102:

</ref> 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 ===

Line 142:

=== Bounding Volume Hierarchy ===

When the space of the objects we are computing collision for is complex, a single bounding volume may not provide tight enough approximation to considerably reduce the number of exact collision detections we have to perform. In such cases [[Bounding volume hierarchy| Bounding Volume Hierarchy]] (BVH) may be used. A BVH is a tree structure over a set of bounding volumes. BVH can be used with deformable objects such as cloth or soft-bodies but the volume hierarchy has to be adjusted as the shape deforms. For deformable objects we need to be concerned about self-collisions or self intersections. BVH can be used for that end as well. Collision between two objects is computed by computing intersection between the bounding volumes of the root of the tree as there are collision we dive into the sub-trees that intersect. Exact collisions between the actual objects, or its parts (often triangles of a [[triangle mesh]]) need to be computed only between intersecting leaves.<ref>

{{cite journal

| last1 = Klosowski

Line 163:

| doi = 10.1109/2945.675649

}}

</ref>. The same approach works for pair wise collision and self-collisions.

=== Triangle centroid segments ===