The brute-force implementation of broad phase for n objects consists in conducting n(n-1)/2 collision tests. Thus it has a complexity of O(n 2).
Alternative algorithms, such as sort and sweep(described in Section 32.1.1) or spatial subdivision (described in Section 32.1.2), achieve an average complexity of O(n log n) (their worst-case complexity remains O(n2)).
Sort and Sweep
One approach to the broad phase, as mentioned, is the sort and sweep algorithm (Witkin and Baraff 1997). In this approach, the bounding volume of each object i is projected onto the x, y, or z axis, defining the one-dimensional collision interval [bi , ei ] of the object along this axis; bi marks the beginning of the collision interval, and ei marks its end. Two objects whose collision intervals do not overlap cannot possibly collide with each other, leading to the algorithm that follows. The two markers of each object are inserted into a list with 2n entries (two markers for each object). Next, this list is sorted in ascending order. Finally, the list is traversed from beginning to end. Whenever a bi marker is found in the list, object i is added to a list of active objects. Whenever an ei marker is found, object i is removed from the list of active objects. Collision tests for object i are performed only between object i and all objects currently in the list of active objects at the moment when object i itself is added to this list of active objects. An example with three objects is illustrated in Figure 32-1.
Sort and sweep is simple to implement, and it is a great starting point for a broad-phase collision detection algorithm. Additionally, due to spatial coherency between one frame of simulation and the next, one can often use an O(n 2) sort such as insertion sort in an efficient manner to accelerate the algorithm, because of its improved O(n) performance when applied to mostly sorted lists.
[2,4],// [object Array] (2)
[3,2],// [object Array] (2)
[4,4],// [object Array] (2)
[5,2],// [object Array] (2)
[6,3],// [object Array] (2)
[8,3],// [object Array] (2)
[9,5],// [object Array] (2)
[10,1],// [object Array] (2)
[11,5],// [object Array] (2)
[12,1]
// A simple implementation of the Sweep-And-Prune broad phase collision detection scheme
function sap(polygons, v) {
let n = polygons.length;
let pairs = [];
let proj = [];
polygons.forEach((poly, i) => {
let min = Number.POSITIVE_INFINITY;
let max = Number.NEGATIVE_INFINITY;
for (let p of poly) {
let dot = vec2.dot(p, v);
min = Math.min(min, dot);
max = Math.max(max, dot);
}
proj.push([min, i], [max, i]);
});
proj.sort((a, b) => a[0] - b[0]);
let inside = new Set();
for (let [_, i] of proj) {
if (inside.has(i)) {
inside.delete(i);
} else {
pairs[i] = [];
for (let j of inside) {
if (i < j) pairs[j].push(i);
else pairs[i].push(j);
}
inside.add(i);
}
}
return pairs;
}With lots of methods
function sortAxisList(a, axisIndex){
axisIndex = axisIndex|0;
for(var i=1,l=a.length; i<l; i++) {
var v = a[i];
for(var j=i - 1;j>=0;j--) {
if(a[j].aabb.lowerBound[axisIndex] <= v.aabb.lowerBound[axisIndex]){
break;
}
a[j+1] = a[j];
}
a[j+1] = v;
}
return a;
}SAPBroadphase.prototype.sortList = function(){
var bodies = this.axisList,
axisIndex = this.axisIndex;
// Sort the lists
sortAxisList(bodies, axisIndex);
};get potential colliding pairs
/**
* Get the colliding pairs
* @method getCollisionPairs
* @param {World} world
* @return {Array}
*/
SAPBroadphase.prototype.getCollisionPairs = function(/*world*/){
var bodies = this.axisList,
result = this.result,
axisIndex = this.axisIndex;
result.length = 0;
// Update all AABBs if needed
var l = bodies.length;
while(l--){
var b = bodies[l];
if(b.aabbNeedsUpdate){
b.updateAABB();
}
}
// Sort the lists
this.sortList();
// Look through the X list
for(var i=0, N=bodies.length|0; i!==N; i++){
var bi = bodies[i];
for(var j=i+1; j<N; j++){
var bj = bodies[j];
// Bounds overlap?
var overlaps = (bj.aabb.lowerBound[axisIndex] <= bi.aabb.upperBound[axisIndex]);
if(!overlaps){
break;
}
if(Broadphase.canCollide(bi,bj) && this.boundingVolumeCheck(bi,bj)){
result.push(bi,bj);
}
}
}
return result;
};Method to get bodies within a AABB
/**
* Returns all the bodies within an AABB.
* @method aabbQuery
* @param {World} world
* @param {AABB} aabb
* @param {array} result An array to store resulting bodies in.
* @return {array}
* @todo since the list is sorted, optimization can be done
*/
SAPBroadphase.prototype.aabbQuery = function(world, aabb, result){
result = result || [];
this.sortList();
var axisList = this.axisList;
for(var i = 0; i < axisList.length; i++){
var b = axisList[i];
if(b.aabbNeedsUpdate){
b.updateAABB();
}
if(b.aabb.overlaps(aabb)){
result.push(b);
}
}
return result;
};Useful References
JavaScriptでSweep and Pruneによる衝突判定
Comments