<!DOCTYPE html>
<html lang="en">
<head>
<meta charset="utf-8">
<title>src/collision/SAPBroadphase.js - cannon</title>
<link rel="stylesheet" href="http://yui.yahooapis.com/3.9.1/build/cssgrids/cssgrids-min.css">
<link rel="stylesheet" href="../assets/vendor/prettify/prettify-min.css">
<link rel="stylesheet" href="../assets/css/main.css" id="site_styles">
<link rel="icon" href="../assets/favicon.ico">
<script src="http://yui.yahooapis.com/combo?3.9.1/build/yui/yui-min.js"></script>
</head>
<body class="yui3-skin-sam">
<div id="doc">
<div id="hd" class="yui3-g header">
<div class="yui3-u-3-4">
<h1><img src="../assets/css/logo.png" title="cannon" width="117" height="52"></h1>
</div>
<div class="yui3-u-1-4 version">
<em>API Docs for: 0.6.1</em>
</div>
</div>
<div id="bd" class="yui3-g">
<div class="yui3-u-1-4">
<div id="docs-sidebar" class="sidebar apidocs">
<div id="api-list">
<h2 class="off-left">APIs</h2>
<div id="api-tabview" class="tabview">
<ul class="tabs">
<li><a href="#api-classes">Classes</a></li>
<li><a href="#api-modules">Modules</a></li>
</ul>
<div id="api-tabview-filter">
<input type="search" id="api-filter" placeholder="Type to filter APIs">
</div>
<div id="api-tabview-panel">
<ul id="api-classes" class="apis classes">
<li><a href="../classes/AABB.html">AABB</a></li>
<li><a href="../classes/ArrayCollisionMatrix.html">ArrayCollisionMatrix</a></li>
<li><a href="../classes/Body.html">Body</a></li>
<li><a href="../classes/Box.html">Box</a></li>
<li><a href="../classes/Broadphase.html">Broadphase</a></li>
<li><a href="../classes/ConeEquation.html">ConeEquation</a></li>
<li><a href="../classes/ConeTwistConstraint.html">ConeTwistConstraint</a></li>
<li><a href="../classes/Constraint.html">Constraint</a></li>
<li><a href="../classes/ContactEquation.html">ContactEquation</a></li>
<li><a href="../classes/ContactMaterial.html">ContactMaterial</a></li>
<li><a href="../classes/ConvexPolyhedron.html">ConvexPolyhedron</a></li>
<li><a href="../classes/Cylinder.html">Cylinder</a></li>
<li><a href="../classes/Demo.html">Demo</a></li>
<li><a href="../classes/DistanceConstraint.html">DistanceConstraint</a></li>
<li><a href="../classes/Equation.html">Equation</a></li>
<li><a href="../classes/EventTarget.html">EventTarget</a></li>
<li><a href="../classes/FrictionEquation.html">FrictionEquation</a></li>
<li><a href="../classes/GridBroadphase.html">GridBroadphase</a></li>
<li><a href="../classes/GSSolver.html">GSSolver</a></li>
<li><a href="../classes/Heightfield.html">Heightfield</a></li>
<li><a href="../classes/HingeConstraint.html">HingeConstraint</a></li>
<li><a href="../classes/JacobianElement.html">JacobianElement</a></li>
<li><a href="../classes/LockConstraint.html">LockConstraint</a></li>
<li><a href="../classes/Mat3.html">Mat3</a></li>
<li><a href="../classes/Material.html">Material</a></li>
<li><a href="../classes/NaiveBroadphase.html">NaiveBroadphase</a></li>
<li><a href="../classes/Narrowphase.html">Narrowphase</a></li>
<li><a href="../classes/ObjectCollisionMatrix.html">ObjectCollisionMatrix</a></li>
<li><a href="../classes/Octree.html">Octree</a></li>
<li><a href="../classes/OctreeNode.html">OctreeNode</a></li>
<li><a href="../classes/Particle.html">Particle</a></li>
<li><a href="../classes/Plane.html">Plane</a></li>
<li><a href="../classes/PointToPointConstraint.html">PointToPointConstraint</a></li>
<li><a href="../classes/Pool.html">Pool</a></li>
<li><a href="../classes/Quaternion.html">Quaternion</a></li>
<li><a href="../classes/Ray.html">Ray</a></li>
<li><a href="../classes/RaycastResult.html">RaycastResult</a></li>
<li><a href="../classes/RaycastVehicle.html">RaycastVehicle</a></li>
<li><a href="../classes/RigidVehicle.html">RigidVehicle</a></li>
<li><a href="../classes/RotationalEquation.html">RotationalEquation</a></li>
<li><a href="../classes/RotationalMotorEquation.html">RotationalMotorEquation</a></li>
<li><a href="../classes/SAPBroadphase.html">SAPBroadphase</a></li>
<li><a href="../classes/Shape.html">Shape</a></li>
<li><a href="../classes/Solver.html">Solver</a></li>
<li><a href="../classes/Sphere.html">Sphere</a></li>
<li><a href="../classes/SPHSystem.html">SPHSystem</a></li>
<li><a href="../classes/SplitSolver.html">SplitSolver</a></li>
<li><a href="../classes/Spring.html">Spring</a></li>
<li><a href="../classes/Transform.html">Transform</a></li>
<li><a href="../classes/Trimesh.html">Trimesh</a></li>
<li><a href="../classes/TupleDictionary.html">TupleDictionary</a></li>
<li><a href="../classes/Vec3.html">Vec3</a></li>
<li><a href="../classes/Vec3Pool.html">Vec3Pool</a></li>
<li><a href="../classes/WheelInfo.html">WheelInfo</a></li>
<li><a href="../classes/World.html">World</a></li>
</ul>
<ul id="api-modules" class="apis modules">
</ul>
</div>
</div>
</div>
</div>
</div>
<div class="yui3-u-3-4">
<div id="api-options">
Show:
<label for="api-show-inherited">
<input type="checkbox" id="api-show-inherited" checked>
Inherited
</label>
<label for="api-show-protected">
<input type="checkbox" id="api-show-protected">
Protected
</label>
<label for="api-show-private">
<input type="checkbox" id="api-show-private">
Private
</label>
<label for="api-show-deprecated">
<input type="checkbox" id="api-show-deprecated">
Deprecated
</label>
</div>
<div class="apidocs">
<div id="docs-main">
<div class="content">
<h1 class="file-heading">File: src/collision/SAPBroadphase.js</h1>
<div class="file">
<pre class="code prettyprint linenums">
var Shape = require('../shapes/Shape');
var Broadphase = require('../collision/Broadphase');
module.exports = SAPBroadphase;
/**
* Sweep and prune broadphase along one axis.
*
* @class SAPBroadphase
* @constructor
* @param {World} [world]
* @extends Broadphase
*/
function SAPBroadphase(world){
Broadphase.apply(this);
/**
* List of bodies currently in the broadphase.
* @property axisList
* @type {Array}
*/
this.axisList = [];
/**
* The world to search in.
* @property world
* @type {World}
*/
this.world = null;
/**
* Axis to sort the bodies along. Set to 0 for x axis, and 1 for y axis. For best performance, choose an axis that the bodies are spread out more on.
* @property axisIndex
* @type {Number}
*/
this.axisIndex = 0;
var axisList = this.axisList;
this._addBodyHandler = function(e){
axisList.push(e.body);
};
this._removeBodyHandler = function(e){
var idx = axisList.indexOf(e.body);
if(idx !== -1){
axisList.splice(idx,1);
}
};
if(world){
this.setWorld(world);
}
}
SAPBroadphase.prototype = new Broadphase();
/**
* Change the world
* @method setWorld
* @param {World} world
*/
SAPBroadphase.prototype.setWorld = function(world){
// Clear the old axis array
this.axisList.length = 0;
// Add all bodies from the new world
for(var i=0; i<world.bodies.length; i++){
this.axisList.push(world.bodies[i]);
}
// Remove old handlers, if any
world.removeEventListener("addBody", this._addBodyHandler);
world.removeEventListener("removeBody", this._removeBodyHandler);
// Add handlers to update the list of bodies.
world.addEventListener("addBody", this._addBodyHandler);
world.addEventListener("removeBody", this._removeBodyHandler);
this.world = world;
this.dirty = true;
};
/**
* @static
* @method insertionSortX
* @param {Array} a
* @return {Array}
*/
SAPBroadphase.insertionSortX = function(a) {
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.x <= v.aabb.lowerBound.x){
break;
}
a[j+1] = a[j];
}
a[j+1] = v;
}
return a;
};
/**
* @static
* @method insertionSortY
* @param {Array} a
* @return {Array}
*/
SAPBroadphase.insertionSortY = function(a) {
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.y <= v.aabb.lowerBound.y){
break;
}
a[j+1] = a[j];
}
a[j+1] = v;
}
return a;
};
/**
* @static
* @method insertionSortZ
* @param {Array} a
* @return {Array}
*/
SAPBroadphase.insertionSortZ = function(a) {
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.z <= v.aabb.lowerBound.z){
break;
}
a[j+1] = a[j];
}
a[j+1] = v;
}
return a;
};
/**
* Collect all collision pairs
* @method collisionPairs
* @param {World} world
* @param {Array} p1
* @param {Array} p2
*/
SAPBroadphase.prototype.collisionPairs = function(world,p1,p2){
var bodies = this.axisList,
N = bodies.length,
axisIndex = this.axisIndex,
i, j;
if(this.dirty){
this.sortList();
this.dirty = false;
}
// Look through the list
for(i=0; i !== N; i++){
var bi = bodies[i];
for(j=i+1; j < N; j++){
var bj = bodies[j];
if(!this.needBroadphaseCollision(bi,bj)){
continue;
}
if(!SAPBroadphase.checkBounds(bi,bj,axisIndex)){
break;
}
this.intersectionTest(bi,bj,p1,p2);
}
}
};
SAPBroadphase.prototype.sortList = function(){
var axisList = this.axisList;
var axisIndex = this.axisIndex;
var N = axisList.length;
// Update AABBs
for(var i = 0; i!==N; i++){
var bi = axisList[i];
if(bi.aabbNeedsUpdate){
bi.computeAABB();
}
}
// Sort the list
if(axisIndex === 0){
SAPBroadphase.insertionSortX(axisList);
} else if(axisIndex === 1){
SAPBroadphase.insertionSortY(axisList);
} else if(axisIndex === 2){
SAPBroadphase.insertionSortZ(axisList);
}
};
/**
* Check if the bounds of two bodies overlap, along the given SAP axis.
* @static
* @method checkBounds
* @param {Body} bi
* @param {Body} bj
* @param {Number} axisIndex
* @return {Boolean}
*/
SAPBroadphase.checkBounds = function(bi, bj, axisIndex){
var biPos;
var bjPos;
if(axisIndex === 0){
biPos = bi.position.x;
bjPos = bj.position.x;
} else if(axisIndex === 1){
biPos = bi.position.y;
bjPos = bj.position.y;
} else if(axisIndex === 2){
biPos = bi.position.z;
bjPos = bj.position.z;
}
var ri = bi.boundingRadius,
rj = bj.boundingRadius,
boundA1 = biPos - ri,
boundA2 = biPos + ri,
boundB1 = bjPos - rj,
boundB2 = bjPos + rj;
return boundB1 < boundA2;
};
/**
* Computes the variance of the body positions and estimates the best
* axis to use. Will automatically set property .axisIndex.
* @method autoDetectAxis
*/
SAPBroadphase.prototype.autoDetectAxis = function(){
var sumX=0,
sumX2=0,
sumY=0,
sumY2=0,
sumZ=0,
sumZ2=0,
bodies = this.axisList,
N = bodies.length,
invN=1/N;
for(var i=0; i!==N; i++){
var b = bodies[i];
var centerX = b.position.x;
sumX += centerX;
sumX2 += centerX*centerX;
var centerY = b.position.y;
sumY += centerY;
sumY2 += centerY*centerY;
var centerZ = b.position.z;
sumZ += centerZ;
sumZ2 += centerZ*centerZ;
}
var varianceX = sumX2 - sumX*sumX*invN,
varianceY = sumY2 - sumY*sumY*invN,
varianceZ = sumZ2 - sumZ*sumZ*invN;
if(varianceX > varianceY){
if(varianceX > varianceZ){
this.axisIndex = 0;
} else{
this.axisIndex = 2;
}
} else if(varianceY > varianceZ){
this.axisIndex = 1;
} else{
this.axisIndex = 2;
}
};
/**
* 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}
*/
SAPBroadphase.prototype.aabbQuery = function(world, aabb, result){
result = result || [];
if(this.dirty){
this.sortList();
this.dirty = false;
}
var axisIndex = this.axisIndex, axis = 'x';
if(axisIndex === 1){ axis = 'y'; }
if(axisIndex === 2){ axis = 'z'; }
var axisList = this.axisList;
var lower = aabb.lowerBound[axis];
var upper = aabb.upperBound[axis];
for(var i = 0; i < axisList.length; i++){
var b = axisList[i];
if(b.aabbNeedsUpdate){
b.computeAABB();
}
if(b.aabb.overlaps(aabb)){
result.push(b);
}
}
return result;
};
</pre>
</div>
</div>
</div>
</div>
</div>
</div>
</div>
<script src="../assets/vendor/prettify/prettify-min.js"></script>
<script>prettyPrint();</script>
<script src="../assets/js/yui-prettify.js"></script>
<script src="../assets/../api.js"></script>
<script src="../assets/js/api-filter.js"></script>
<script src="../assets/js/api-list.js"></script>
<script src="../assets/js/api-search.js"></script>
<script src="../assets/js/apidocs.js"></script>
</body>
</html>
