Content deleted Content added
Maxeto0910 (talk | contribs) →Overview: period after sentence |
GoobRobinson (talk | contribs) m Insert comma and change "objects moves" to "objects move" |
||
Line 26:
=== Spatial partitioning ===
Several approaches can grouped under the [[spatial partitioning]] umbrella, which includes [[octree]]s (for 3D), [[quadtree]]s (for 2D), [[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. Dynamic scenes and deformable objects require updating the partitioning which can add overhead.
===Bounding volume hierarchy===
Line 36:
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 be approximated well with [[axis-aligned bounding box]]es, the [[sweep and prune]] algorithm<ref name=":0" /> can be a suitable approach.
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 (making sorting algorithms optimized for almost-sorted lists suitable for this application). The algorithm keeps track of currently intersecting boxes, and as objects
=== Pairwise pruning ===
| |||