Hilo/build/physics/physics.js

/**
 * Hilo 1.0.1 for physics
 * Copyright 2016 alibaba.com
 * Licensed under the MIT License
 */
(function(){
/* Copyright (c) 2007 Scott Lembcke
 *
 * Permission is hereby granted, free of charge, to any person obtaining a copy
 * of this software and associated documentation files (the "Software"), to deal
 * in the Software without restriction, including without limitation the rights
 * to use, copy, modify, merge, publish, distribute, sublicense, and/or sell
 * copies of the Software, and to permit persons to whom the Software is
 * furnished to do so, subject to the following conditions:
 *
 * The above copyright notice and this permission notice shall be included in
 * all copies or substantial portions of the Software.
 *
 * THE SOFTWARE IS PROVIDED "AS IS", WITHOUT WARRANTY OF ANY KIND, EXPRESS OR
 * IMPLIED, INCLUDING BUT NOT LIMITED TO THE WARRANTIES OF MERCHANTABILITY,
 * FITNESS FOR A PARTICULAR PURPOSE AND NONINFRINGEMENT. IN NO EVENT SHALL THE
 * AUTHORS OR COPYRIGHT HOLDERS BE LIABLE FOR ANY CLAIM, DAMAGES OR OTHER
 * LIABILITY, WHETHER IN AN ACTION OF CONTRACT, TORT OR OTHERWISE, ARISING FROM,
 * OUT OF OR IN CONNECTION WITH THE SOFTWARE OR THE USE OR OTHER DEALINGS IN THE
 * SOFTWARE.
 */

Object.create = Object.create || function(o) {
    function F() {}
    F.prototype = o;
    return new F();
};

//var VERSION = CP_VERSION_MAJOR + "." + CP_VERSION_MINOR + "." + CP_VERSION_RELEASE;

var cp;
if(typeof exports === 'undefined'){
    cp = {};

    if(typeof window === 'object'){
        window.cp = cp;
    }
} else {
    cp = exports;
}

var assert = function(value, message)
{
    return
    if (!value) {
        throw new Error('Assertion failed: ' + message);
    }
};

var assertSoft = function(value, message)
{
    return
    if(!value && console && console.warn) {
        console.warn("ASSERTION FAILED: " + message);
        if(console.trace) {
            console.trace();
        }
    }
};

var mymin = function(a, b)
{
    return a < b ? a : b;
};
var mymax = function(a, b)
{
    return a > b ? a : b;
};

var min, max;
if (typeof window === 'object' && window.navigator.userAgent.indexOf('Firefox') > -1){
    // On firefox, Math.min and Math.max are really fast:
    // http://jsperf.com/math-vs-greater-than/8
    min = Math.min;
    max = Math.max;
} else {
    // On chrome and safari, Math.min / max are slooow. The ternery operator above is faster
    // than the builtins because we only have to deal with 2 arguments that are always numbers.
    min = mymin;
    max = mymax;
}

/* The hashpair function takes two numbers and returns a hash code for them.
 * Required that hashPair(a, b) === hashPair(b, a).
 * Chipmunk's hashPair function is defined as:
 *   #define CP_HASH_COEF (3344921057ul)
 *   #define CP_HASH_PAIR(A, B) ((cpHashValue)(A)*CP_HASH_COEF ^ (cpHashValue)(B)*CP_HASH_COEF)
 * But thats not suitable in javascript because multiplying by a large number will make the number
 * a large float.
 *
 * The result of hashPair is used as the key in objects, so it returns a string.
 */
var hashPair = function(a, b)
{
    //assert(typeof(a) === 'number', "HashPair used on something not a number");
    return a < b ? a + ' ' + b : b + ' ' + a;
};

var deleteObjFromList = function(arr, obj)
{
    for(var i=0; i<arr.length; i++){
        if(arr[i] === obj){
            arr[i] = arr[arr.length - 1];
            arr.length--;

            return;
        }
    }
};

var closestPointOnSegment = function(p, a, b)
{
    var delta = vsub(a, b);
    var t = clamp01(vdot(delta, vsub(p, b))/vlengthsq(delta));
    return vadd(b, vmult(delta, t));
};

var closestPointOnSegment2 = function(px, py, ax, ay, bx, by)
{
    var deltax = ax - bx;
    var deltay = ay - by;
    var t = clamp01(vdot2(deltax, deltay, px - bx, py - by)/vlengthsq2(deltax, deltay));
    return new Vect(bx + deltax * t, by + deltay * t);
};

cp.momentForCircle = function(m, r1, r2, offset)
{
    return m*(0.5*(r1*r1 + r2*r2) + vlengthsq(offset));
};

cp.areaForCircle = function(r1, r2)
{
    return Math.PI*Math.abs(r1*r1 - r2*r2);
};

cp.momentForSegment = function(m, a, b)
{
    var offset = vmult(vadd(a, b), 0.5);
    return m*(vdistsq(b, a)/12 + vlengthsq(offset));
};

cp.areaForSegment = function(a, b, r)
{
    return r*(Math.PI*r + 2*vdist(a, b));
};

cp.momentForPoly = function(m, verts, offset)
{
    var sum1 = 0;
    var sum2 = 0;
    var len = verts.length;
    for(var i=0; i<len; i+=2){
        var v1x = verts[i] + offset.x;
        var v1y = verts[i+1] + offset.y;
        var v2x = verts[(i+2)%len] + offset.x;
        var v2y = verts[(i+3)%len] + offset.y;

        var a = vcross2(v2x, v2y, v1x, v1y);
        var b = vdot2(v1x, v1y, v1x, v1y) + vdot2(v1x, v1y, v2x, v2y) + vdot2(v2x, v2y, v2x, v2y);

        sum1 += a*b;
        sum2 += a;
    }

    return (m*sum1)/(6*sum2);
};

cp.areaForPoly = function(verts)
{
    var area = 0;
    for(var i=0, len=verts.length; i<len; i+=2){
        area += vcross(new Vect(verts[i], verts[i+1]), new Vect(verts[(i+2)%len], verts[(i+3)%len]));
    }

    return -area/2;
};

cp.centroidForPoly = function(verts)
{
    var sum = 0;
    var vsum = new Vect(0,0);

    for(var i=0, len=verts.length; i<len; i+=2){
        var v1 = new Vect(verts[i], verts[i+1]);
        var v2 = new Vect(verts[(i+2)%len], verts[(i+3)%len]);
        var cross = vcross(v1, v2);

        sum += cross;
        vsum = vadd(vsum, vmult(vadd(v1, v2), cross));
    }

    return vmult(vsum, 1/(3*sum));
};

cp.recenterPoly = function(verts)
{
    var centroid = cp.centroidForPoly(verts);

    for(var i=0; i<verts.length; i+=2){
        verts[i] -= centroid.x;
        verts[i+1] -= centroid.y;
    }
};

cp.momentForBox = function(m, width, height)
{
    return m*(width*width + height*height)/12;
};

cp.momentForBox2 = function(m, box)
{
    var width = box.r - box.l;
    var height = box.t - box.b;
    var offset = vmult([box.l + box.r, box.b + box.t], 0.5);

    // TODO NaN when offset is 0 and m is INFINITY
    return cp.momentForBox(m, width, height) + m*vlengthsq(offset);
};

// Quick hull

var loopIndexes = cp.loopIndexes = function(verts)
{
    var start = 0, end = 0;
    var minx, miny, maxx, maxy;
    minx = maxx = verts[0];
    miny = maxy = verts[1];

    var count = verts.length >> 1;
  for(var i=1; i<count; i++){
        var x = verts[i*2];
        var y = verts[i*2 + 1];

    if(x < minx || (x == minx && y < miny)){
            minx = x;
            miny = y;
      start = i;
    } else if(x > maxx || (x == maxx && y > maxy)){
            maxx = x;
            maxy = y;
            end = i;
        }
    }
    return [start, end];
};

var SWAP = function(arr, idx1, idx2)
{
    var tmp = arr[idx1*2];
    arr[idx1*2] = arr[idx2*2];
    arr[idx2*2] = tmp;

    tmp = arr[idx1*2+1];
    arr[idx1*2+1] = arr[idx2*2+1];
    arr[idx2*2+1] = tmp;
};

var QHullPartition = function(verts, offs, count, a, b, tol)
{
    if(count === 0) return 0;

    var max = 0;
    var pivot = offs;

    var delta = vsub(b, a);
    var valueTol = tol * vlength(delta);

    var head = offs;
    for(var tail = offs+count-1; head <= tail;){
        var v = new Vect(verts[head * 2], verts[head * 2 + 1]);
        var value = vcross(delta, vsub(v, a));
        if(value > valueTol){
            if(value > max){
                max = value;
                pivot = head;
            }

            head++;
        } else {
            SWAP(verts, head, tail);
            tail--;
        }
    }

    // move the new pivot to the front if it's not already there.
    if(pivot != offs) SWAP(verts, offs, pivot);
    return head - offs;
};

var QHullReduce = function(tol, verts, offs, count, a, pivot, b, resultPos)
{
    if(count < 0){
        return 0;
    } else if(count == 0) {
        verts[resultPos*2] = pivot.x;
        verts[resultPos*2+1] = pivot.y;
        return 1;
    } else {
        var left_count = QHullPartition(verts, offs, count, a, pivot, tol);
        var left = new Vect(verts[offs*2], verts[offs*2+1]);
        var index = QHullReduce(tol, verts, offs + 1, left_count - 1, a, left, pivot, resultPos);

        var pivotPos = resultPos + index++;
        verts[pivotPos*2] = pivot.x;
        verts[pivotPos*2+1] = pivot.y;

        var right_count = QHullPartition(verts, offs + left_count, count - left_count, pivot, b, tol);
        var right = new Vect(verts[(offs+left_count)*2], verts[(offs+left_count)*2+1]);
        return index + QHullReduce(tol, verts, offs + left_count + 1, right_count - 1, pivot, right, b, resultPos + index);
    }
};

// QuickHull seemed like a neat algorithm, and efficient-ish for large input sets.
// My implementation performs an in place reduction using the result array as scratch space.
//
// Pass an Array into result to put the result of the calculation there. Otherwise, pass null
// and the verts list will be edited in-place.
//
// Expects the verts to be described in the same way as cpPolyShape - which is to say, it should
// be a list of [x1,y1,x2,y2,x3,y3,...].
//
// tolerance is in world coordinates. Eg, 2.
cp.convexHull = function(verts, result, tolerance)
{
    if(result){
        // Copy the line vertexes into the empty part of the result polyline to use as a scratch buffer.
        for (var i = 0; i < verts.length; i++){
            result[i] = verts[i];
        }
    } else {
        // If a result array was not specified, reduce the input instead.
        result = verts;
    }

    // Degenerate case, all points are the same.
    var indexes = loopIndexes(verts);
    var start = indexes[0], end = indexes[1];
    if(start == end){
        //if(first) (*first) = 0;
        result.length = 2;
        return result;
    }

    SWAP(result, 0, start);
    SWAP(result, 1, end == 0 ? start : end);

    var a = new Vect(result[0], result[1]);
    var b = new Vect(result[2], result[3]);

    var count = verts.length >> 1;
    //if(first) (*first) = start;
    var resultCount = QHullReduce(tolerance, result, 2, count - 2, a, b, a, 1) + 1;
    result.length = resultCount*2;

    assertSoft(polyValidate(result),
        "Internal error: cpConvexHull() and cpPolyValidate() did not agree." +
        "Please report this error with as much info as you can.");
    return result;
};

/// Clamp @c f to be between @c min and @c max.
var clamp = function(f, minv, maxv)
{
    return min(max(f, minv), maxv);
};

/// Clamp @c f to be between 0 and 1.
var clamp01 = function(f)
{
    return max(0, min(f, 1));
};

/// Linearly interpolate (or extrapolate) between @c f1 and @c f2 by @c t percent.
var lerp = function(f1, f2, t)
{
    return f1*(1 - t) + f2*t;
};

/// Linearly interpolate from @c f1 to @c f2 by no more than @c d.
var lerpconst = function(f1, f2, d)
{
    return f1 + clamp(f2 - f1, -d, d);
};

/* Copyright (c) 2007 Scott Lembcke
 *
 * Permission is hereby granted, free of charge, to any person obtaining a copy
 * of this software and associated documentation files (the "Software"), to deal
 * in the Software without restriction, including without limitation the rights
 * to use, copy, modify, merge, publish, distribute, sublicense, and/or sell
 * copies of the Software, and to permit persons to whom the Software is
 * furnished to do so, subject to the following conditions:
 *
 * The above copyright notice and this permission notice shall be included in
 * all copies or substantial portions of the Software.
 *
 * THE SOFTWARE IS PROVIDED "AS IS", WITHOUT WARRANTY OF ANY KIND, EXPRESS OR
 * IMPLIED, INCLUDING BUT NOT LIMITED TO THE WARRANTIES OF MERCHANTABILITY,
 * FITNESS FOR A PARTICULAR PURPOSE AND NONINFRINGEMENT. IN NO EVENT SHALL THE
 * AUTHORS OR COPYRIGHT HOLDERS BE LIABLE FOR ANY CLAIM, DAMAGES OR OTHER
 * LIABILITY, WHETHER IN AN ACTION OF CONTRACT, TORT OR OTHERWISE, ARISING FROM,
 * OUT OF OR IN CONNECTION WITH THE SOFTWARE OR THE USE OR OTHER DEALINGS IN THE
 * SOFTWARE.
 */

// I'm using an array tuple here because (at time of writing) its about 3x faster
// than an object on firefox, and the same speed on chrome.

//var numVects = 0;

var Vect = cp.Vect = function(x, y)
{
    this.x = x;
    this.y = y;
    //numVects++;

//  var s = new Error().stack;
//  traces[s] = traces[s] ? traces[s]+1 : 1;
};

cp.v = function (x,y) { return new Vect(x, y) };

var vzero = cp.vzero = new Vect(0,0);

// The functions below *could* be rewritten to be instance methods on Vect. I don't
// know how that would effect performance. For now, I'm keeping the JS similar to
// the original C code.

/// Vector dot product.
var vdot = cp.v.dot = function(v1, v2)
{
    return v1.x*v2.x + v1.y*v2.y;
};

var vdot2 = function(x1, y1, x2, y2)
{
    return x1*x2 + y1*y2;
};

/// Returns the length of v.
var vlength = cp.v.len = function(v)
{
    return Math.sqrt(vdot(v, v));
};

var vlength2 = cp.v.len2 = function(x, y)
{
    return Math.sqrt(x*x + y*y);
};

/// Check if two vectors are equal. (Be careful when comparing floating point numbers!)
var veql = cp.v.eql = function(v1, v2)
{
    return (v1.x === v2.x && v1.y === v2.y);
};

/// Add two vectors
var vadd = cp.v.add = function(v1, v2)
{
    return new Vect(v1.x + v2.x, v1.y + v2.y);
};

Vect.prototype.add = function(v2)
{
    this.x += v2.x;
    this.y += v2.y;
    return this;
};

/// Subtract two vectors.
var vsub = cp.v.sub = function(v1, v2)
{
    return new Vect(v1.x - v2.x, v1.y - v2.y);
};

Vect.prototype.sub = function(v2)
{
    this.x -= v2.x;
    this.y -= v2.y;
    return this;
};

/// Negate a vector.
var vneg = cp.v.neg = function(v)
{
    return new Vect(-v.x, -v.y);
};

Vect.prototype.neg = function()
{
    this.x = -this.x;
    this.y = -this.y;
    return this;
};

/// Scalar multiplication.
var vmult = cp.v.mult = function(v, s)
{
    return new Vect(v.x*s, v.y*s);
};

Vect.prototype.mult = function(s)
{
    this.x *= s;
    this.y *= s;
    return this;
};

/// 2D vector cross product analog.
/// The cross product of 2D vectors results in a 3D vector with only a z component.
/// This function returns the magnitude of the z value.
var vcross = cp.v.cross = function(v1, v2)
{
    return v1.x*v2.y - v1.y*v2.x;
};

var vcross2 = function(x1, y1, x2, y2)
{
    return x1*y2 - y1*x2;
};

/// Returns a perpendicular vector. (90 degree rotation)
var vperp = cp.v.perp = function(v)
{
    return new Vect(-v.y, v.x);
};

/// Returns a perpendicular vector. (-90 degree rotation)
var vpvrperp = cp.v.pvrperp = function(v)
{
    return new Vect(v.y, -v.x);
};

/// Returns the vector projection of v1 onto v2.
var vproject = cp.v.project = function(v1, v2)
{
    return vmult(v2, vdot(v1, v2)/vlengthsq(v2));
};

Vect.prototype.project = function(v2)
{
    this.mult(vdot(this, v2) / vlengthsq(v2));
    return this;
};

/// Uses complex number multiplication to rotate v1 by v2. Scaling will occur if v1 is not a unit vector.
var vrotate = cp.v.rotate = function(v1, v2)
{
    return new Vect(v1.x*v2.x - v1.y*v2.y, v1.x*v2.y + v1.y*v2.x);
};

Vect.prototype.rotate = function(v2)
{
    this.x = this.x * v2.x - this.y * v2.y;
    this.y = this.x * v2.y + this.y * v2.x;
    return this;
};

/// Inverse of vrotate().
var vunrotate = cp.v.unrotate = function(v1, v2)
{
    return new Vect(v1.x*v2.x + v1.y*v2.y, v1.y*v2.x - v1.x*v2.y);
};

/// Returns the squared length of v. Faster than vlength() when you only need to compare lengths.
var vlengthsq = cp.v.lengthsq = function(v)
{
    return vdot(v, v);
};

var vlengthsq2 = cp.v.lengthsq2 = function(x, y)
{
    return x*x + y*y;
};

/// Linearly interpolate between v1 and v2.
var vlerp = cp.v.lerp = function(v1, v2, t)
{
    return vadd(vmult(v1, 1 - t), vmult(v2, t));
};

/// Returns a normalized copy of v.
var vnormalize = cp.v.normalize = function(v)
{
    return vmult(v, 1/vlength(v));
};

/// Returns a normalized copy of v or vzero if v was already vzero. Protects against divide by zero errors.
var vnormalize_safe = cp.v.normalize_safe = function(v)
{
    return (v.x === 0 && v.y === 0 ? vzero : vnormalize(v));
};

/// Clamp v to length len.
var vclamp = cp.v.clamp = function(v, len)
{
    return (vdot(v,v) > len*len) ? vmult(vnormalize(v), len) : v;
};

/// Linearly interpolate between v1 towards v2 by distance d.
var vlerpconst = cp.v.lerpconst = function(v1, v2, d)
{
    return vadd(v1, vclamp(vsub(v2, v1), d));
};

/// Returns the distance between v1 and v2.
var vdist = cp.v.dist = function(v1, v2)
{
    return vlength(vsub(v1, v2));
};

/// Returns the squared distance between v1 and v2. Faster than vdist() when you only need to compare distances.
var vdistsq = cp.v.distsq = function(v1, v2)
{
    return vlengthsq(vsub(v1, v2));
};

/// Returns true if the distance between v1 and v2 is less than dist.
var vnear = cp.v.near = function(v1, v2, dist)
{
    return vdistsq(v1, v2) < dist*dist;
};

/// Spherical linearly interpolate between v1 and v2.
var vslerp = cp.v.slerp = function(v1, v2, t)
{
    var omega = Math.acos(vdot(v1, v2));

    if(omega) {
        var denom = 1/Math.sin(omega);
        return vadd(vmult(v1, Math.sin((1 - t)*omega)*denom), vmult(v2, Math.sin(t*omega)*denom));
    } else {
        return v1;
    }
};

/// Spherical linearly interpolate between v1 towards v2 by no more than angle a radians
var vslerpconst = cp.v.slerpconst = function(v1, v2, a)
{
    var angle = Math.acos(vdot(v1, v2));
    return vslerp(v1, v2, min(a, angle)/angle);
};

/// Returns the unit length vector for the given angle (in radians).
var vforangle = cp.v.forangle = function(a)
{
    return new Vect(Math.cos(a), Math.sin(a));
};

/// Returns the angular direction v is pointing in (in radians).
var vtoangle = cp.v.toangle = function(v)
{
    return Math.atan2(v.y, v.x);
};

/// Returns a string representation of v. Intended mostly for debugging purposes and not production use.
var vstr = cp.v.str = function(v)
{
    return "(" + v.x.toFixed(3) + ", " + v.y.toFixed(3) + ")";
};

/* Copyright (c) 2007 Scott Lembcke
 *
 * Permission is hereby granted, free of charge, to any person obtaining a copy
 * of this software and associated documentation files (the "Software"), to deal
 * in the Software without restriction, including without limitation the rights
 * to use, copy, modify, merge, publish, distribute, sublicense, and/or sell
 * copies of the Software, and to permit persons to whom the Software is
 * furnished to do so, subject to the following conditions:
 *
 * The above copyright notice and this permission notice shall be included in
 * all copies or substantial portions of the Software.
 *
 * THE SOFTWARE IS PROVIDED "AS IS", WITHOUT WARRANTY OF ANY KIND, EXPRESS OR
 * IMPLIED, INCLUDING BUT NOT LIMITED TO THE WARRANTIES OF MERCHANTABILITY,
 * FITNESS FOR A PARTICULAR PURPOSE AND NONINFRINGEMENT. IN NO EVENT SHALL THE
 * AUTHORS OR COPYRIGHT HOLDERS BE LIABLE FOR ANY CLAIM, DAMAGES OR OTHER
 * LIABILITY, WHETHER IN AN ACTION OF CONTRACT, TORT OR OTHERWISE, ARISING FROM,
 * OUT OF OR IN CONNECTION WITH THE SOFTWARE OR THE USE OR OTHER DEALINGS IN THE
 * SOFTWARE.
 */

/// Chipmunk's axis-aligned 2D bounding box type along with a few handy routines.

var numBB = 0;

// Bounding boxes are JS objects with {l, b, r, t} = left, bottom, right, top, respectively.
var BB = cp.BB = function(l, b, r, t)
{
    this.l = l;
    this.b = b;
    this.r = r;
    this.t = t;

    numBB++;
};

cp.bb = function(l, b, r, t) { return new BB(l, b, r, t); };

var bbNewForCircle = function(p, r)
{
    return new BB(
            p.x - r,
            p.y - r,
            p.x + r,
            p.y + r
        );
};

/// Returns true if @c a and @c b intersect.
var bbIntersects = function(a, b)
{
    return (a.l <= b.r && b.l <= a.r && a.b <= b.t && b.b <= a.t);
};
var bbIntersects2 = function(bb, l, b, r, t)
{
    return (bb.l <= r && l <= bb.r && bb.b <= t && b <= bb.t);
};

/// Returns true if @c other lies completely within @c bb.
var bbContainsBB = function(bb, other)
{
    return (bb.l <= other.l && bb.r >= other.r && bb.b <= other.b && bb.t >= other.t);
};

/// Returns true if @c bb contains @c v.
var bbContainsVect = function(bb, v)
{
    return (bb.l <= v.x && bb.r >= v.x && bb.b <= v.y && bb.t >= v.y);
};
var bbContainsVect2 = function(l, b, r, t, v)
{
    return (l <= v.x && r >= v.x && b <= v.y && t >= v.y);
};

/// Returns a bounding box that holds both bounding boxes.
var bbMerge = function(a, b){
    return new BB(
            min(a.l, b.l),
            min(a.b, b.b),
            max(a.r, b.r),
            max(a.t, b.t)
        );
};

/// Returns a bounding box that holds both @c bb and @c v.
var bbExpand = function(bb, v){
    return new BB(
            min(bb.l, v.x),
            min(bb.b, v.y),
            max(bb.r, v.x),
            max(bb.t, v.y)
        );
};

/// Returns the area of the bounding box.
var bbArea = function(bb)
{
    return (bb.r - bb.l)*(bb.t - bb.b);
};

/// Merges @c a and @c b and returns the area of the merged bounding box.
var bbMergedArea = function(a, b)
{
    return (max(a.r, b.r) - min(a.l, b.l))*(max(a.t, b.t) - min(a.b, b.b));
};

var bbMergedArea2 = function(bb, l, b, r, t)
{
    return (max(bb.r, r) - min(bb.l, l))*(max(bb.t, t) - min(bb.b, b));
};

/// Return true if the bounding box intersects the line segment with ends @c a and @c b.
var bbIntersectsSegment = function(bb, a, b)
{
    return (bbSegmentQuery(bb, a, b) != Infinity);
};

/// Clamp a vector to a bounding box.
var bbClampVect = function(bb, v)
{
    var x = min(max(bb.l, v.x), bb.r);
    var y = min(max(bb.b, v.y), bb.t);
    return new Vect(x, y);
};

// TODO edge case issue
/// Wrap a vector to a bounding box.
var bbWrapVect = function(bb, v)
{
    var ix = Math.abs(bb.r - bb.l);
    var modx = (v.x - bb.l) % ix;
    var x = (modx > 0) ? modx : modx + ix;

    var iy = Math.abs(bb.t - bb.b);
    var mody = (v.y - bb.b) % iy;
    var y = (mody > 0) ? mody : mody + iy;

    return new Vect(x + bb.l, y + bb.b);
};
/* Copyright (c) 2007 Scott Lembcke
 *
 * Permission is hereby granted, free of charge, to any person obtaining a copy
 * of this software and associated documentation files (the "Software"), to deal
 * in the Software without restriction, including without limitation the rights
 * to use, copy, modify, merge, publish, distribute, sublicense, and/or sell
 * copies of the Software, and to permit persons to whom the Software is
 * furnished to do so, subject to the following conditions:
 *
 * The above copyright notice and this permission notice shall be included in
 * all copies or substantial portions of the Software.
 *
 * THE SOFTWARE IS PROVIDED "AS IS", WITHOUT WARRANTY OF ANY KIND, EXPRESS OR
 * IMPLIED, INCLUDING BUT NOT LIMITED TO THE WARRANTIES OF MERCHANTABILITY,
 * FITNESS FOR A PARTICULAR PURPOSE AND NONINFRINGEMENT. IN NO EVENT SHALL THE
 * AUTHORS OR COPYRIGHT HOLDERS BE LIABLE FOR ANY CLAIM, DAMAGES OR OTHER
 * LIABILITY, WHETHER IN AN ACTION OF CONTRACT, TORT OR OTHERWISE, ARISING FROM,
 * OUT OF OR IN CONNECTION WITH THE SOFTWARE OR THE USE OR OTHER DEALINGS IN THE
 * SOFTWARE.
 */

/// Segment query info struct.
/* These are created using literals where needed.
typedef struct cpSegmentQueryInfo {
    /// The shape that was hit, null if no collision occured.
    cpShape *shape;
    /// The normalized distance along the query segment in the range [0, 1].
    cpFloat t;
    /// The normal of the surface hit.
    cpVect n;
} cpSegmentQueryInfo;
*/

var shapeIDCounter = 0;

var CP_NO_GROUP = cp.NO_GROUP = 0;
var CP_ALL_LAYERS = cp.ALL_LAYERS = ~0;

cp.resetShapeIdCounter = function()
{
    shapeIDCounter = 0;
};

/// The cpShape struct defines the shape of a rigid body.
//
/// Opaque collision shape struct. Do not create directly - instead use
/// PolyShape, CircleShape and SegmentShape.
var Shape = cp.Shape = function(body) {
    /// The rigid body this collision shape is attached to.
    this.body = body;

    /// The current bounding box of the shape.
    this.bb_l = this.bb_b = this.bb_r = this.bb_t = 0;

    this.hashid = shapeIDCounter++;

    /// Sensor flag.
    /// Sensor shapes call collision callbacks but don't produce collisions.
    this.sensor = false;

    /// Coefficient of restitution. (elasticity)
    this.e = 0;
    /// Coefficient of friction.
    this.u = 0;
    /// Surface velocity used when solving for friction.
    this.surface_v = vzero;

    /// Collision type of this shape used when picking collision handlers.
    this.collision_type = 0;
    /// Group of this shape. Shapes in the same group don't collide.
    this.group = 0;
    // Layer bitmask for this shape. Shapes only collide if the bitwise and of their layers is non-zero.
    this.layers = CP_ALL_LAYERS;

    this.space = null;

    // Copy the collision code from the prototype into the actual object. This makes collision
    // function lookups slightly faster.
    this.collisionCode = this.collisionCode;
};

Shape.prototype.setElasticity = function(e) { this.e = e; };
Shape.prototype.setFriction = function(u) { this.body.activate(); this.u = u; };
Shape.prototype.setLayers = function(layers) { this.body.activate(); this.layers = layers; };
Shape.prototype.setSensor = function(sensor) { this.body.activate(); this.sensor = sensor; };
Shape.prototype.setCollisionType = function(collision_type) { this.body.activate(); this.collision_type = collision_type; };
Shape.prototype.getBody = function() { return this.body; };

Shape.prototype.active = function()
{
// return shape->prev || (shape->body && shape->body->shapeList == shape);
    return this.body && this.body.shapeList.indexOf(this) !== -1;
};

Shape.prototype.setBody = function(body)
{
    assert(!this.active(), "You cannot change the body on an active shape. You must remove the shape from the space before changing the body.");
    this.body = body;
};

Shape.prototype.cacheBB = function()
{
    return this.update(this.body.p, this.body.rot);
};

Shape.prototype.update = function(pos, rot)
{
    assert(!isNaN(rot.x), 'Rotation is NaN');
    assert(!isNaN(pos.x), 'Position is NaN');
    this.cacheData(pos, rot);
};

Shape.prototype.pointQuery = function(p)
{
    var info = this.nearestPointQuery(p);
    if (info.d < 0) return info;
};

Shape.prototype.getBB = function()
{
    return new BB(this.bb_l, this.bb_b, this.bb_r, this.bb_t);
};

/* Not implemented - all these getters and setters. Just edit the object directly.
CP_DefineShapeStructGetter(cpBody*, body, Body);
void cpShapeSetBody(cpShape *shape, cpBody *body);

CP_DefineShapeStructGetter(cpBB, bb, BB);
CP_DefineShapeStructProperty(cpBool, sensor, Sensor, cpTrue);
CP_DefineShapeStructProperty(cpFloat, e, Elasticity, cpFalse);
CP_DefineShapeStructProperty(cpFloat, u, Friction, cpTrue);
CP_DefineShapeStructProperty(cpVect, surface_v, SurfaceVelocity, cpTrue);
CP_DefineShapeStructProperty(cpDataPointer, data, UserData, cpFalse);
CP_DefineShapeStructProperty(cpCollisionType, collision_type, CollisionType, cpTrue);
CP_DefineShapeStructProperty(cpGroup, group, Group, cpTrue);
CP_DefineShapeStructProperty(cpLayers, layers, Layers, cpTrue);
*/

/// Extended point query info struct. Returned from calling pointQuery on a shape.
var PointQueryExtendedInfo = function(shape)
{
    /// Shape that was hit, NULL if no collision occurred.
    this.shape = shape;
    /// Depth of the point inside the shape.
    this.d = Infinity;
    /// Direction of minimum norm to the shape's surface.
    this.n = vzero;
};

var NearestPointQueryInfo = function(shape, p, d)
{
    /// The nearest shape, NULL if no shape was within range.
    this.shape = shape;
    /// The closest point on the shape's surface. (in world space coordinates)
    this.p = p;
    /// The distance to the point. The distance is negative if the point is inside the shape.
    this.d = d;
};

var SegmentQueryInfo = function(shape, t, n)
{
    /// The shape that was hit, NULL if no collision occured.
    this.shape = shape;
    /// The normalized distance along the query segment in the range [0, 1].
    this.t = t;
    /// The normal of the surface hit.
    this.n = n;
};

/// Get the hit point for a segment query.
SegmentQueryInfo.prototype.hitPoint = function(start, end)
{
    return vlerp(start, end, this.t);
};

/// Get the hit distance for a segment query.
SegmentQueryInfo.prototype.hitDist = function(start, end)
{
    return vdist(start, end) * this.t;
};

// Circles.

var CircleShape = cp.CircleShape = function(body, radius, offset)
{
    this.c = this.tc = offset;
    this.r = radius;

    this.type = 'circle';

    Shape.call(this, body);
};

CircleShape.prototype = Object.create(Shape.prototype);

CircleShape.prototype.cacheData = function(p, rot)
{
    //var c = this.tc = vadd(p, vrotate(this.c, rot));
    var c = this.tc = vrotate(this.c, rot).add(p);
    //this.bb = bbNewForCircle(c, this.r);
    var r = this.r;
    this.bb_l = c.x - r;
    this.bb_b = c.y - r;
    this.bb_r = c.x + r;
    this.bb_t = c.y + r;
};

/// Test if a point lies within a shape.
/*CircleShape.prototype.pointQuery = function(p)
{
    var delta = vsub(p, this.tc);
    var distsq = vlengthsq(delta);
    var r = this.r;

    if(distsq < r*r){
        var info = new PointQueryExtendedInfo(this);

        var dist = Math.sqrt(distsq);
        info.d = r - dist;
        info.n = vmult(delta, 1/dist);
        return info;
    }
};*/

CircleShape.prototype.nearestPointQuery = function(p)
{
    var deltax = p.x - this.tc.x;
    var deltay = p.y - this.tc.y;
    var d = vlength2(deltax, deltay);
    var r = this.r;

    var nearestp = new Vect(this.tc.x + deltax * r/d, this.tc.y + deltay * r/d);
    return new NearestPointQueryInfo(this, nearestp, d - r);
};

var circleSegmentQuery = function(shape, center, r, a, b, info)
{
    // offset the line to be relative to the circle
    a = vsub(a, center);
    b = vsub(b, center);

    var qa = vdot(a, a) - 2*vdot(a, b) + vdot(b, b);
    var qb = -2*vdot(a, a) + 2*vdot(a, b);
    var qc = vdot(a, a) - r*r;

    var det = qb*qb - 4*qa*qc;

    if(det >= 0)
    {
        var t = (-qb - Math.sqrt(det))/(2*qa);
        if(0 <= t && t <= 1){
            return new SegmentQueryInfo(shape, t, vnormalize(vlerp(a, b, t)));
        }
    }
};

CircleShape.prototype.segmentQuery = function(a, b)
{
    return circleSegmentQuery(this, this.tc, this.r, a, b);
};

// The C API has these, and also getters. Its not idiomatic to
// write getters and setters in JS.
/*
CircleShape.prototype.setRadius = function(radius)
{
    this.r = radius;
}

CircleShape.prototype.setOffset = function(offset)
{
    this.c = offset;
}*/

// Segment shape

var SegmentShape = cp.SegmentShape = function(body, a, b, r)
{
    this.a = a;
    this.b = b;
    this.n = vperp(vnormalize(vsub(b, a)));

    this.ta = this.tb = this.tn = null;

    this.r = r;

    this.a_tangent = vzero;
    this.b_tangent = vzero;

    this.type = 'segment';
    Shape.call(this, body);
};

SegmentShape.prototype = Object.create(Shape.prototype);

SegmentShape.prototype.cacheData = function(p, rot)
{
    this.ta = vadd(p, vrotate(this.a, rot));
    this.tb = vadd(p, vrotate(this.b, rot));
    this.tn = vrotate(this.n, rot);

    var l,r,b,t;

    if(this.ta.x < this.tb.x){
        l = this.ta.x;
        r = this.tb.x;
    } else {
        l = this.tb.x;
        r = this.ta.x;
    }

    if(this.ta.y < this.tb.y){
        b = this.ta.y;
        t = this.tb.y;
    } else {
        b = this.tb.y;
        t = this.ta.y;
    }

    var rad = this.r;

    this.bb_l = l - rad;
    this.bb_b = b - rad;
    this.bb_r = r + rad;
    this.bb_t = t + rad;
};

SegmentShape.prototype.nearestPointQuery = function(p)
{
    var closest = closestPointOnSegment(p, this.ta, this.tb);

    var deltax = p.x - closest.x;
    var deltay = p.y - closest.y;
    var d = vlength2(deltax, deltay);
    var r = this.r;

    var nearestp = (d ? vadd(closest, vmult(new Vect(deltax, deltay), r/d)) : closest);
    return new NearestPointQueryInfo(this, nearestp, d - r);
};

SegmentShape.prototype.segmentQuery = function(a, b)
{
    var n = this.tn;
    var d = vdot(vsub(this.ta, a), n);
    var r = this.r;

    var flipped_n = (d > 0 ? vneg(n) : n);
    var n_offset = vsub(vmult(flipped_n, r), a);

    var seg_a = vadd(this.ta, n_offset);
    var seg_b = vadd(this.tb, n_offset);
    var delta = vsub(b, a);

    if(vcross(delta, seg_a)*vcross(delta, seg_b) <= 0){
        var d_offset = d + (d > 0 ? -r : r);
        var ad = -d_offset;
        var bd = vdot(delta, n) - d_offset;

        if(ad*bd < 0){
            return new SegmentQueryInfo(this, ad/(ad - bd), flipped_n);
        }
    } else if(r !== 0){
        var info1 = circleSegmentQuery(this, this.ta, this.r, a, b);
        var info2 = circleSegmentQuery(this, this.tb, this.r, a, b);

        if (info1){
            return info2 && info2.t < info1.t ? info2 : info1;
        } else {
            return info2;
        }
    }
};

SegmentShape.prototype.setNeighbors = function(prev, next)
{
    this.a_tangent = vsub(prev, this.a);
    this.b_tangent = vsub(next, this.b);
};

SegmentShape.prototype.setEndpoints = function(a, b)
{
    this.a = a;
    this.b = b;
    this.n = vperp(vnormalize(vsub(b, a)));
};

/*
cpSegmentShapeSetRadius(cpShape *shape, cpFloat radius)
{
    this.r = radius;
}*/

/*
CP_DeclareShapeGetter(cpSegmentShape, cpVect, A);
CP_DeclareShapeGetter(cpSegmentShape, cpVect, B);
CP_DeclareShapeGetter(cpSegmentShape, cpVect, Normal);
CP_DeclareShapeGetter(cpSegmentShape, cpFloat, Radius);
*/

/* Copyright (c) 2007 Scott Lembcke
 *
 * Permission is hereby granted, free of charge, to any person obtaining a copy
 * of this software and associated documentation files (the "Software"), to deal
 * in the Software without restriction, including without limitation the rights
 * to use, copy, modify, merge, publish, distribute, sublicense, and/or sell
 * copies of the Software, and to permit persons to whom the Software is
 * furnished to do so, subject to the following conditions:
 *
 * The above copyright notice and this permission notice shall be included in
 * all copies or substantial portions of the Software.
 *
 * THE SOFTWARE IS PROVIDED "AS IS", WITHOUT WARRANTY OF ANY KIND, EXPRESS OR
 * IMPLIED, INCLUDING BUT NOT LIMITED TO THE WARRANTIES OF MERCHANTABILITY,
 * FITNESS FOR A PARTICULAR PURPOSE AND NONINFRINGEMENT. IN NO EVENT SHALL THE
 * AUTHORS OR COPYRIGHT HOLDERS BE LIABLE FOR ANY CLAIM, DAMAGES OR OTHER
 * LIABILITY, WHETHER IN AN ACTION OF CONTRACT, TORT OR OTHERWISE, ARISING FROM,
 * OUT OF OR IN CONNECTION WITH THE SOFTWARE OR THE USE OR OTHER DEALINGS IN THE
 * SOFTWARE.
 */

/// Check that a set of vertexes is convex and has a clockwise winding.
var polyValidate = function(verts)
{
    var len = verts.length;
    for(var i=0; i<len; i+=2){
        var ax = verts[i];
        var ay = verts[i+1];
        var bx = verts[(i+2)%len];
        var by = verts[(i+3)%len];
        var cx = verts[(i+4)%len];
        var cy = verts[(i+5)%len];

        //if(vcross(vsub(b, a), vsub(c, b)) > 0){
        if(vcross2(bx - ax, by - ay, cx - bx, cy - by) > 0){
            return false;
        }
    }

    return true;
};

/// Initialize a polygon shape.
/// The vertexes must be convex and have a clockwise winding.
var PolyShape = cp.PolyShape = function(body, verts, offset)
{
    this.setVerts(verts, offset);
    this.type = 'poly';
    Shape.call(this, body);
};

PolyShape.prototype = Object.create(Shape.prototype);

var SplittingPlane = function(n, d)
{
    this.n = n;
    this.d = d;
};

SplittingPlane.prototype.compare = function(v)
{
    return vdot(this.n, v) - this.d;
};

PolyShape.prototype.setVerts = function(verts, offset)
{
    assert(verts.length >= 4, "Polygons require some verts");
    assert(typeof(verts[0]) === 'number',
            'Polygon verticies should be specified in a flattened list (eg [x1,y1,x2,y2,x3,y3,...])');

    // Fail if the user attempts to pass a concave poly, or a bad winding.
    assert(polyValidate(verts), "Polygon is concave or has a reversed winding. Consider using cpConvexHull()");

    var len = verts.length;
    var numVerts = len >> 1;

    // This a pretty bad way to do this in javascript. As a first pass, I want to keep
    // the code similar to the C.
    this.verts = new Array(len);
    this.tVerts = new Array(len);
    this.planes = new Array(numVerts);
    this.tPlanes = new Array(numVerts);

    for(var i=0; i<len; i+=2){
        //var a = vadd(offset, verts[i]);
        //var b = vadd(offset, verts[(i+1)%numVerts]);
        var ax = verts[i] + offset.x;
        var ay = verts[i+1] + offset.y;
        var bx = verts[(i+2)%len] + offset.x;
        var by = verts[(i+3)%len] + offset.y;

        // Inefficient, but only called during object initialization.
        var n = vnormalize(vperp(new Vect(bx-ax, by-ay)));

        this.verts[i  ] = ax;
        this.verts[i+1] = ay;
        this.planes[i>>1] = new SplittingPlane(n, vdot2(n.x, n.y, ax, ay));
        this.tPlanes[i>>1] = new SplittingPlane(new Vect(0,0), 0);
    }
};

/// Initialize a box shaped polygon shape.
var BoxShape = cp.BoxShape = function(body, width, height)
{
    var hw = width/2;
    var hh = height/2;

    return BoxShape2(body, new BB(-hw, -hh, hw, hh));
};

/// Initialize an offset box shaped polygon shape.
var BoxShape2 = cp.BoxShape2 = function(body, box)
{
    var verts = [
        box.l, box.b,
        box.l, box.t,
        box.r, box.t,
        box.r, box.b,
    ];

    return new PolyShape(body, verts, vzero);
};

PolyShape.prototype.transformVerts = function(p, rot)
{
    var src = this.verts;
    var dst = this.tVerts;

    var l = Infinity, r = -Infinity;
    var b = Infinity, t = -Infinity;

    for(var i=0; i<src.length; i+=2){
        //var v = vadd(p, vrotate(src[i], rot));
        var x = src[i];
        var y = src[i+1];

        var vx = p.x + x*rot.x - y*rot.y;
        var vy = p.y + x*rot.y + y*rot.x;

        //console.log('(' + x + ',' + y + ') -> (' + vx + ',' + vy + ')');

        dst[i] = vx;
        dst[i+1] = vy;

        l = min(l, vx);
        r = max(r, vx);
        b = min(b, vy);
        t = max(t, vy);
    }

    this.bb_l = l;
    this.bb_b = b;
    this.bb_r = r;
    this.bb_t = t;
};

PolyShape.prototype.transformAxes = function(p, rot)
{
    var src = this.planes;
    var dst = this.tPlanes;

    for(var i=0; i<src.length; i++){
        var n = vrotate(src[i].n, rot);
        dst[i].n = n;
        dst[i].d = vdot(p, n) + src[i].d;
    }
};

PolyShape.prototype.cacheData = function(p, rot)
{
    this.transformAxes(p, rot);
    this.transformVerts(p, rot);
};

PolyShape.prototype.nearestPointQuery = function(p)
{
    var planes = this.tPlanes;
    var verts = this.tVerts;

    var v0x = verts[verts.length - 2];
    var v0y = verts[verts.length - 1];
    var minDist = Infinity;
    var closestPoint = vzero;
    var outside = false;

    for(var i=0; i<planes.length; i++){
        if(planes[i].compare(p) > 0) outside = true;

        var v1x = verts[i*2];
        var v1y = verts[i*2 + 1];
        var closest = closestPointOnSegment2(p.x, p.y, v0x, v0y, v1x, v1y);

        var dist = vdist(p, closest);
        if(dist < minDist){
            minDist = dist;
            closestPoint = closest;
        }

        v0x = v1x;
        v0y = v1y;
    }

    return new NearestPointQueryInfo(this, closestPoint, (outside ? minDist : -minDist));
};

PolyShape.prototype.segmentQuery = function(a, b)
{
    var axes = this.tPlanes;
    var verts = this.tVerts;
    var numVerts = axes.length;
    var len = numVerts * 2;

    for(var i=0; i<numVerts; i++){
        var n = axes[i].n;
        var an = vdot(a, n);
        if(axes[i].d > an) continue;

        var bn = vdot(b, n);
        var t = (axes[i].d - an)/(bn - an);
        if(t < 0 || 1 < t) continue;

        var point = vlerp(a, b, t);
        var dt = -vcross(n, point);
        var dtMin = -vcross2(n.x, n.y, verts[i*2], verts[i*2+1]);
        var dtMax = -vcross2(n.x, n.y, verts[(i*2+2)%len], verts[(i*2+3)%len]);

        if(dtMin <= dt && dt <= dtMax){
            // josephg: In the original C code, this function keeps
            // looping through axes after finding a match. I *think*
            // this code is equivalent...
            return new SegmentQueryInfo(this, t, n);
        }
    }
};

PolyShape.prototype.valueOnAxis = function(n, d)
{
    var verts = this.tVerts;
    var m = vdot2(n.x, n.y, verts[0], verts[1]);

    for(var i=2; i<verts.length; i+=2){
        m = min(m, vdot2(n.x, n.y, verts[i], verts[i+1]));
    }

    return m - d;
};

PolyShape.prototype.containsVert = function(vx, vy)
{
    var planes = this.tPlanes;

    for(var i=0; i<planes.length; i++){
        var n = planes[i].n;
        var dist = vdot2(n.x, n.y, vx, vy) - planes[i].d;
        if(dist > 0) return false;
    }

    return true;
};

PolyShape.prototype.containsVertPartial = function(vx, vy, n)
{
    var planes = this.tPlanes;

    for(var i=0; i<planes.length; i++){
        var n2 = planes[i].n;
        if(vdot(n2, n) < 0) continue;
        var dist = vdot2(n2.x, n2.y, vx, vy) - planes[i].d;
        if(dist > 0) return false;
    }

    return true;
};

// These methods are provided for API compatibility with Chipmunk. I recommend against using
// them - just access the poly.verts list directly.
PolyShape.prototype.getNumVerts = function() { return this.verts.length / 2; };
PolyShape.prototype.getVert = function(i)
{
    return new Vect(this.verts[i * 2], this.verts[i * 2 + 1]);
};

/* Copyright (c) 2007 Scott Lembcke
 *
 * Permission is hereby granted, free of charge, to any person obtaining a copy
 * of this software and associated documentation files (the "Software"), to deal
 * in the Software without restriction, including without limitation the rights
 * to use, copy, modify, merge, publish, distribute, sublicense, and/or sell
 * copies of the Software, and to permit persons to whom the Software is
 * furnished to do so, subject to the following conditions:
 *
 * The above copyright notice and this permission notice shall be included in
 * all copies or substantial portions of the Software.
 *
 * THE SOFTWARE IS PROVIDED "AS IS", WITHOUT WARRANTY OF ANY KIND, EXPRESS OR
 * IMPLIED, INCLUDING BUT NOT LIMITED TO THE WARRANTIES OF MERCHANTABILITY,
 * FITNESS FOR A PARTICULAR PURPOSE AND NONINFRINGEMENT. IN NO EVENT SHALL THE
 * AUTHORS OR COPYRIGHT HOLDERS BE LIABLE FOR ANY CLAIM, DAMAGES OR OTHER
 * LIABILITY, WHETHER IN AN ACTION OF CONTRACT, TORT OR OTHERWISE, ARISING FROM,
 * OUT OF OR IN CONNECTION WITH THE SOFTWARE OR THE USE OR OTHER DEALINGS IN THE
 * SOFTWARE.
 */

/// @defgroup cpBody cpBody
/// Chipmunk's rigid body type. Rigid bodies hold the physical properties of an object like
/// it's mass, and position and velocity of it's center of gravity. They don't have an shape on their own.
/// They are given a shape by creating collision shapes (cpShape) that point to the body.
/// @{

var Body = cp.Body = function(m, i) {
    /// Mass of the body.
    /// Must agree with cpBody.m_inv! Use body.setMass() when changing the mass for this reason.
    //this.m;
    /// Mass inverse.
    //this.m_inv;

    /// Moment of inertia of the body.
    /// Must agree with cpBody.i_inv! Use body.setMoment() when changing the moment for this reason.
    //this.i;
    /// Moment of inertia inverse.
    //this.i_inv;

    /// Position of the rigid body's center of gravity.
    this.p = new Vect(0,0);
    /// Velocity of the rigid body's center of gravity.
    this.vx = this.vy = 0;
    /// Force acting on the rigid body's center of gravity.
    this.f = new Vect(0,0);

    /// Rotation of the body around it's center of gravity in radians.
    /// Must agree with cpBody.rot! Use cpBodySetAngle() when changing the angle for this reason.
    //this.a;
    /// Angular velocity of the body around it's center of gravity in radians/second.
    this.w = 0;
    /// Torque applied to the body around it's center of gravity.
    this.t = 0;

    /// Cached unit length vector representing the angle of the body.
    /// Used for fast rotations using cpvrotate().
    //cpVect rot;

    /// Maximum velocity allowed when updating the velocity.
    this.v_limit = Infinity;
    /// Maximum rotational rate (in radians/second) allowed when updating the angular velocity.
    this.w_limit = Infinity;

    // This stuff is all private.
    this.v_biasx = this.v_biasy = 0;
    this.w_bias = 0;

    this.space = null;

    this.shapeList = [];
    this.arbiterList = null; // These are both wacky linked lists.
    this.constraintList = null;

    // This stuff is used to track information on the collision graph.
    this.nodeRoot = null;
    this.nodeNext = null;
    this.nodeIdleTime = 0;

    // Set this.m and this.m_inv
    this.setMass(m);

    // Set this.i and this.i_inv
    this.setMoment(i);

    // Set this.a and this.rot
    this.rot = new Vect(0,0);
    this.setAngle(0);
};

// I wonder if this should use the constructor style like Body...
var createStaticBody = function()
{
    var body = new Body(Infinity, Infinity);
    body.nodeIdleTime = Infinity;

    return body;
};

if (typeof DEBUG !== 'undefined' && DEBUG) {
    var v_assert_nan = function(v, message){assert(v.x == v.x && v.y == v.y, message); };
    var v_assert_infinite = function(v, message){assert(Math.abs(v.x) !== Infinity && Math.abs(v.y) !== Infinity, message);};
    var v_assert_sane = function(v, message){v_assert_nan(v, message); v_assert_infinite(v, message);};

    Body.prototype.sanityCheck = function()
    {
        assert(this.m === this.m && this.m_inv === this.m_inv, "Body's mass is invalid.");
        assert(this.i === this.i && this.i_inv === this.i_inv, "Body's moment is invalid.");

        v_assert_sane(this.p, "Body's position is invalid.");
        v_assert_sane(this.f, "Body's force is invalid.");
        assert(this.vx === this.vx && Math.abs(this.vx) !== Infinity, "Body's velocity is invalid.");
        assert(this.vy === this.vy && Math.abs(this.vy) !== Infinity, "Body's velocity is invalid.");

        assert(this.a === this.a && Math.abs(this.a) !== Infinity, "Body's angle is invalid.");
        assert(this.w === this.w && Math.abs(this.w) !== Infinity, "Body's angular velocity is invalid.");
        assert(this.t === this.t && Math.abs(this.t) !== Infinity, "Body's torque is invalid.");

        v_assert_sane(this.rot, "Body's rotation vector is invalid.");

        assert(this.v_limit === this.v_limit, "Body's velocity limit is invalid.");
        assert(this.w_limit === this.w_limit, "Body's angular velocity limit is invalid.");
    };
} else {
    Body.prototype.sanityCheck = function(){};
}

Body.prototype.getPos = function() { return this.p; };
Body.prototype.getVel = function() { return new Vect(this.vx, this.vy); };
Body.prototype.getAngVel = function() { return this.w; };

/// Returns true if the body is sleeping.
Body.prototype.isSleeping = function()
{
    return this.nodeRoot !== null;
};

/// Returns true if the body is static.
Body.prototype.isStatic = function()
{
    return this.nodeIdleTime === Infinity;
};

/// Returns true if the body has not been added to a space.
Body.prototype.isRogue = function()
{
    return this.space === null;
};

// It would be nicer to use defineProperty for this, but its about 30x slower:
// http://jsperf.com/defineproperty-vs-setter
Body.prototype.setMass = function(mass)
{
    assert(mass > 0, "Mass must be positive and non-zero.");

    //activate is defined in cpSpaceComponent
    this.activate();
    this.m = mass;
    this.m_inv = 1/mass;
};

Body.prototype.setMoment = function(moment)
{
    assert(moment > 0, "Moment of Inertia must be positive and non-zero.");

    this.activate();
    this.i = moment;
    this.i_inv = 1/moment;
};

Body.prototype.addShape = function(shape)
{
    this.shapeList.push(shape);
};

Body.prototype.removeShape = function(shape)
{
    // This implementation has a linear time complexity with the number of shapes.
    // The original implementation used linked lists instead, which might be faster if
    // you're constantly editing the shape of a body. I expect most bodies will never
    // have their shape edited, so I'm just going to use the simplest possible implemention.
    deleteObjFromList(this.shapeList, shape);
};

var filterConstraints = function(node, body, filter)
{
    if(node === filter){
        return node.next(body);
    } else if(node.a === body){
        node.next_a = filterConstraints(node.next_a, body, filter);
    } else {
        node.next_b = filterConstraints(node.next_b, body, filter);
    }

    return node;
};

Body.prototype.removeConstraint = function(constraint)
{
    // The constraint must be in the constraints list when this is called.
    this.constraintList = filterConstraints(this.constraintList, this, constraint);
};

Body.prototype.setPos = function(pos)
{
    this.activate();
    this.sanityCheck();
    // If I allow the position to be set to vzero, vzero will get changed.
    if (pos === vzero) {
        pos = cp.v(0,0);
    }
    this.p = pos;
};

Body.prototype.setVel = function(velocity)
{
    this.activate();
    this.vx = velocity.x;
    this.vy = velocity.y;
};

Body.prototype.setAngVel = function(w)
{
    this.activate();
    this.w = w;
};

Body.prototype.setAngleInternal = function(angle)
{
    assert(!isNaN(angle), "Internal Error: Attempting to set body's angle to NaN");
    this.a = angle;//fmod(a, (cpFloat)M_PI*2.0f);

    //this.rot = vforangle(angle);
    this.rot.x = Math.cos(angle);
    this.rot.y = Math.sin(angle);
};

Body.prototype.setAngle = function(angle)
{
    this.activate();
    this.sanityCheck();
    this.setAngleInternal(angle);
};

Body.prototype.velocity_func = function(gravity, damping, dt)
{
    //this.v = vclamp(vadd(vmult(this.v, damping), vmult(vadd(gravity, vmult(this.f, this.m_inv)), dt)), this.v_limit);
    var vx = this.vx * damping + (gravity.x + this.f.x * this.m_inv) * dt;
    var vy = this.vy * damping + (gravity.y + this.f.y * this.m_inv) * dt;

    //var v = vclamp(new Vect(vx, vy), this.v_limit);
    //this.vx = v.x; this.vy = v.y;
    var v_limit = this.v_limit;
    var lensq = vx * vx + vy * vy;
    var scale = (lensq > v_limit*v_limit) ? v_limit / Math.sqrt(lensq) : 1;
    this.vx = vx * scale;
    this.vy = vy * scale;

    var w_limit = this.w_limit;
    this.w = clamp(this.w*damping + this.t*this.i_inv*dt, -w_limit, w_limit);

    this.sanityCheck();
};

Body.prototype.position_func = function(dt)
{
    //this.p = vadd(this.p, vmult(vadd(this.v, this.v_bias), dt));

    //this.p = this.p + (this.v + this.v_bias) * dt;
    this.p.x += (this.vx + this.v_biasx) * dt;
    this.p.y += (this.vy + this.v_biasy) * dt;

    this.setAngleInternal(this.a + (this.w + this.w_bias)*dt);

    this.v_biasx = this.v_biasy = 0;
    this.w_bias = 0;

    this.sanityCheck();
};

Body.prototype.resetForces = function()
{
    this.activate();
    this.f = new Vect(0,0);
    this.t = 0;
};

Body.prototype.applyForce = function(force, r)
{
    this.activate();
    this.f = vadd(this.f, force);
    this.t += vcross(r, force);
};

Body.prototype.applyImpulse = function(j, r)
{
    this.activate();
    apply_impulse(this, j.x, j.y, r);
};

Body.prototype.getVelAtPoint = function(r)
{
    return vadd(new Vect(this.vx, this.vy), vmult(vperp(r), this.w));
};

/// Get the velocity on a body (in world units) at a point on the body in world coordinates.
Body.prototype.getVelAtWorldPoint = function(point)
{
    return this.getVelAtPoint(vsub(point, this.p));
};

/// Get the velocity on a body (in world units) at a point on the body in local coordinates.
Body.prototype.getVelAtLocalPoint = function(point)
{
    return this.getVelAtPoint(vrotate(point, this.rot));
};

Body.prototype.eachShape = function(func)
{
    for(var i = 0, len = this.shapeList.length; i < len; i++) {
        func(this.shapeList[i]);
    }
};

Body.prototype.eachConstraint = function(func)
{
    var constraint = this.constraintList;
    while(constraint) {
        var next = constraint.next(this);
        func(constraint);
        constraint = next;
    }
};

Body.prototype.eachArbiter = function(func)
{
    var arb = this.arbiterList;
    while(arb){
        var next = arb.next(this);

        arb.swappedColl = (this === arb.body_b);
        func(arb);

        arb = next;
    }
};

/// Convert body relative/local coordinates to absolute/world coordinates.
Body.prototype.local2World = function(v)
{
    return vadd(this.p, vrotate(v, this.rot));
};

/// Convert body absolute/world coordinates to  relative/local coordinates.
Body.prototype.world2Local = function(v)
{
    return vunrotate(vsub(v, this.p), this.rot);
};

/// Get the kinetic energy of a body.
Body.prototype.kineticEnergy = function()
{
    // Need to do some fudging to avoid NaNs
    var vsq = this.vx*this.vx + this.vy*this.vy;
    var wsq = this.w * this.w;
    return (vsq ? vsq*this.m : 0) + (wsq ? wsq*this.i : 0);
};

/* Copyright (c) 2010 Scott Lembcke
 *
 * Permission is hereby granted, free of charge, to any person obtaining a copy
 * of this software and associated documentation files (the "Software"), to deal
 * in the Software without restriction, including without limitation the rights
 * to use, copy, modify, merge, publish, distribute, sublicense, and/or sell
 * copies of the Software, and to permit persons to whom the Software is
 * furnished to do so, subject to the following conditions:
 *
 * The above copyright notice and this permission notice shall be included in
 * all copies or substantial portions of the Software.
 *
 * THE SOFTWARE IS PROVIDED "AS IS", WITHOUT WARRANTY OF ANY KIND, EXPRESS OR
 * IMPLIED, INCLUDING BUT NOT LIMITED TO THE WARRANTIES OF MERCHANTABILITY,
 * FITNESS FOR A PARTICULAR PURPOSE AND NONINFRINGEMENT. IN NO EVENT SHALL THE
 * AUTHORS OR COPYRIGHT HOLDERS BE LIABLE FOR ANY CLAIM, DAMAGES OR OTHER
 * LIABILITY, WHETHER IN AN ACTION OF CONTRACT, TORT OR OTHERWISE, ARISING FROM,
 * OUT OF OR IN CONNECTION WITH THE SOFTWARE OR THE USE OR OTHER DEALINGS IN THE
 * SOFTWARE.
 */

/**
    @defgroup cpSpatialIndex cpSpatialIndex

    Spatial indexes are data structures that are used to accelerate collision detection
    and spatial queries. Chipmunk provides a number of spatial index algorithms to pick from
    and they are programmed in a generic way so that you can use them for holding more than
    just Shapes.

    It works by using pointers to the objects you add and using a callback to ask your code
    for bounding boxes when it needs them. Several types of queries can be performed an index as well
    as reindexing and full collision information. All communication to the spatial indexes is performed
    through callback functions.

    Spatial indexes should be treated as opaque structs.
    This means you shouldn't be reading any of the fields directly.

    All spatial indexes define the following methods:

    // The number of objects in the spatial index.
    count = 0;

    // Iterate the objects in the spatial index. @c func will be called once for each object.
    each(func);

    // Returns true if the spatial index contains the given object.
    // Most spatial indexes use hashed storage, so you must provide a hash value too.
    contains(obj, hashid);

    // Add an object to a spatial index.
    insert(obj, hashid);

    // Remove an object from a spatial index.
    remove(obj, hashid);

    // Perform a full reindex of a spatial index.
    reindex();

    // Reindex a single object in the spatial index.
    reindexObject(obj, hashid);

    // Perform a point query against the spatial index, calling @c func for each potential match.
    // A pointer to the point will be passed as @c obj1 of @c func.
    // func(shape);
    pointQuery(point, func);

    // Perform a segment query against the spatial index, calling @c func for each potential match.
    // func(shape);
    segmentQuery(vect a, vect b, t_exit, func);

    // Perform a rectangle query against the spatial index, calling @c func for each potential match.
    // func(shape);
    query(bb, func);

    // Simultaneously reindex and find all colliding objects.
    // @c func will be called once for each potentially overlapping pair of objects found.
    // If the spatial index was initialized with a static index, it will collide it's objects against that as well.
    reindexQuery(func);
*/

var SpatialIndex = cp.SpatialIndex = function(staticIndex)
{
    this.staticIndex = staticIndex;


    if(staticIndex){
        if(staticIndex.dynamicIndex){
            throw new Error("This static index is already associated with a dynamic index.");
        }
        staticIndex.dynamicIndex = this;
    }
};

// Collide the objects in an index against the objects in a staticIndex using the query callback function.
SpatialIndex.prototype.collideStatic = function(staticIndex, func)
{
    if(staticIndex.count > 0){
        var query = staticIndex.query;

        this.each(function(obj) {
            query(obj, new BB(obj.bb_l, obj.bb_b, obj.bb_r, obj.bb_t), func);
        });
    }
};


/* Copyright (c) 2009 Scott Lembcke
 *
 * Permission is hereby granted, free of charge, to any person obtaining a copy
 * of this software and associated documentation files (the "Software"), to deal
 * in the Software without restriction, including without limitation the rights
 * to use, copy, modify, merge, publish, distribute, sublicense, and/or sell
 * copies of the Software, and to permit persons to whom the Software is
 * furnished to do so, subject to the following conditions:
 *
 * The above copyright notice and this permission notice shall be included in
 * all copies or substantial portions of the Software.
 *
 * THE SOFTWARE IS PROVIDED "AS IS", WITHOUT WARRANTY OF ANY KIND, EXPRESS OR
 * IMPLIED, INCLUDING BUT NOT LIMITED TO THE WARRANTIES OF MERCHANTABILITY,
 * FITNESS FOR A PARTICULAR PURPOSE AND NONINFRINGEMENT. IN NO EVENT SHALL THE
 * AUTHORS OR COPYRIGHT HOLDERS BE LIABLE FOR ANY CLAIM, DAMAGES OR OTHER
 * LIABILITY, WHETHER IN AN ACTION OF CONTRACT, TORT OR OTHERWISE, ARISING FROM,
 * OUT OF OR IN CONNECTION WITH THE SOFTWARE OR THE USE OR OTHER DEALINGS IN THE
 * SOFTWARE.
 */

// This file implements a modified AABB tree for collision detection.

var BBTree = cp.BBTree = function(staticIndex)
{
    SpatialIndex.call(this, staticIndex);

    this.velocityFunc = null;

    // This is a hash from object ID -> object for the objects stored in the BBTree.
    this.leaves = {};
    // A count of the number of leaves in the BBTree.
    this.count = 0;

    this.root = null;

    // A linked list containing an object pool of tree nodes and pairs.
    this.pooledNodes = null;
    this.pooledPairs = null;

    this.stamp = 0;
};

BBTree.prototype = Object.create(SpatialIndex.prototype);

var numNodes = 0;

var Node = function(tree, a, b)
{
    this.obj = null;
    this.bb_l = min(a.bb_l, b.bb_l);
    this.bb_b = min(a.bb_b, b.bb_b);
    this.bb_r = max(a.bb_r, b.bb_r);
    this.bb_t = max(a.bb_t, b.bb_t);
    this.parent = null;

    this.setA(a);
    this.setB(b);
};

BBTree.prototype.makeNode = function(a, b)
{
    var node = this.pooledNodes;
    if(node){
        this.pooledNodes = node.parent;
        node.constructor(this, a, b);
        return node;
    } else {
        numNodes++;
        return new Node(this, a, b);
    }
};

var numLeaves = 0;
var Leaf = function(tree, obj)
{
    this.obj = obj;
    tree.getBB(obj, this);

    this.parent = null;

    this.stamp = 1;
    this.pairs = null;
    numLeaves++;
};

// **** Misc Functions

BBTree.prototype.getBB = function(obj, dest)
{
    var velocityFunc = this.velocityFunc;
    if(velocityFunc){
        var coef = 0.1;
        var x = (obj.bb_r - obj.bb_l)*coef;
        var y = (obj.bb_t - obj.bb_b)*coef;

        var v = vmult(velocityFunc(obj), 0.1);

        dest.bb_l = obj.bb_l + min(-x, v.x);
        dest.bb_b = obj.bb_b + min(-y, v.y);
        dest.bb_r = obj.bb_r + max( x, v.x);
        dest.bb_t = obj.bb_t + max( y, v.y);
    } else {
        dest.bb_l = obj.bb_l;
        dest.bb_b = obj.bb_b;
        dest.bb_r = obj.bb_r;
        dest.bb_t = obj.bb_t;
    }
};

BBTree.prototype.getStamp = function()
{
    var dynamic = this.dynamicIndex;
    return (dynamic && dynamic.stamp ? dynamic.stamp : this.stamp);
};

BBTree.prototype.incrementStamp = function()
{
    if(this.dynamicIndex && this.dynamicIndex.stamp){
        this.dynamicIndex.stamp++;
    } else {
        this.stamp++;
    }
}

// **** Pair/Thread Functions

var numPairs = 0;
// Objects created with constructors are faster than object literals. :(
var Pair = function(leafA, nextA, leafB, nextB)
{
    this.prevA = null;
    this.leafA = leafA;
    this.nextA = nextA;

    this.prevB = null;
    this.leafB = leafB;
    this.nextB = nextB;
};

BBTree.prototype.makePair = function(leafA, nextA, leafB, nextB)
{
    //return new Pair(leafA, nextA, leafB, nextB);
    var pair = this.pooledPairs;
    if (pair)
    {
        this.pooledPairs = pair.prevA;

        pair.prevA = null;
        pair.leafA = leafA;
        pair.nextA = nextA;

        pair.prevB = null;
        pair.leafB = leafB;
        pair.nextB = nextB;

        //pair.constructor(leafA, nextA, leafB, nextB);
        return pair;
    } else {
        numPairs++;
        return new Pair(leafA, nextA, leafB, nextB);
    }
};

Pair.prototype.recycle = function(tree)
{
    this.prevA = tree.pooledPairs;
    tree.pooledPairs = this;
};

var unlinkThread = function(prev, leaf, next)
{
    if(next){
        if(next.leafA === leaf) next.prevA = prev; else next.prevB = prev;
    }

    if(prev){
        if(prev.leafA === leaf) prev.nextA = next; else prev.nextB = next;
    } else {
        leaf.pairs = next;
    }
};

Leaf.prototype.clearPairs = function(tree)
{
    var pair = this.pairs,
        next;

    this.pairs = null;

    while(pair){
        if(pair.leafA === this){
            next = pair.nextA;
            unlinkThread(pair.prevB, pair.leafB, pair.nextB);
        } else {
            next = pair.nextB;
            unlinkThread(pair.prevA, pair.leafA, pair.nextA);
        }
        pair.recycle(tree);
        pair = next;
    }
};

var pairInsert = function(a, b, tree)
{
    var nextA = a.pairs, nextB = b.pairs;
    var pair = tree.makePair(a, nextA, b, nextB);
    a.pairs = b.pairs = pair;

    if(nextA){
        if(nextA.leafA === a) nextA.prevA = pair; else nextA.prevB = pair;
    }

    if(nextB){
        if(nextB.leafA === b) nextB.prevA = pair; else nextB.prevB = pair;
    }
};

// **** Node Functions

Node.prototype.recycle = function(tree)
{
    this.parent = tree.pooledNodes;
    tree.pooledNodes = this;
};

Leaf.prototype.recycle = function(tree)
{
    // Its not worth the overhead to recycle leaves.
};

Node.prototype.setA = function(value)
{
    this.A = value;
    value.parent = this;
};

Node.prototype.setB = function(value)
{
    this.B = value;
    value.parent = this;
};

Leaf.prototype.isLeaf = true;
Node.prototype.isLeaf = false;

Node.prototype.otherChild = function(child)
{
    return (this.A == child ? this.B : this.A);
};

Node.prototype.replaceChild = function(child, value, tree)
{
    assertSoft(child == this.A || child == this.B, "Node is not a child of parent.");

    if(this.A == child){
        this.A.recycle(tree);
        this.setA(value);
    } else {
        this.B.recycle(tree);
        this.setB(value);
    }

    for(var node=this; node; node = node.parent){
        //node.bb = bbMerge(node.A.bb, node.B.bb);
        var a = node.A;
        var b = node.B;
        node.bb_l = min(a.bb_l, b.bb_l);
        node.bb_b = min(a.bb_b, b.bb_b);
        node.bb_r = max(a.bb_r, b.bb_r);
        node.bb_t = max(a.bb_t, b.bb_t);
    }
};

Node.prototype.bbArea = Leaf.prototype.bbArea = function()
{
    return (this.bb_r - this.bb_l)*(this.bb_t - this.bb_b);
};

var bbTreeMergedArea = function(a, b)
{
    return (max(a.bb_r, b.bb_r) - min(a.bb_l, b.bb_l))*(max(a.bb_t, b.bb_t) - min(a.bb_b, b.bb_b));
};

// **** Subtree Functions

// Would it be better to make these functions instance methods on Node and Leaf?

var bbProximity = function(a, b)
{
    return Math.abs(a.bb_l + a.bb_r - b.bb_l - b.bb_r) + Math.abs(a.bb_b + a.bb_t - b.bb_b - b.bb_t);
};

var subtreeInsert = function(subtree, leaf, tree)
{
//  var s = new Error().stack;
//  traces[s] = traces[s] ? traces[s]+1 : 1;

    if(subtree == null){
        return leaf;
    } else if(subtree.isLeaf){
        return tree.makeNode(leaf, subtree);
    } else {
        var cost_a = subtree.B.bbArea() + bbTreeMergedArea(subtree.A, leaf);
        var cost_b = subtree.A.bbArea() + bbTreeMergedArea(subtree.B, leaf);

        if(cost_a === cost_b){
            cost_a = bbProximity(subtree.A, leaf);
            cost_b = bbProximity(subtree.B, leaf);
        }

        if(cost_b < cost_a){
            subtree.setB(subtreeInsert(subtree.B, leaf, tree));
        } else {
            subtree.setA(subtreeInsert(subtree.A, leaf, tree));
        }

//      subtree.bb = bbMerge(subtree.bb, leaf.bb);
        subtree.bb_l = min(subtree.bb_l, leaf.bb_l);
        subtree.bb_b = min(subtree.bb_b, leaf.bb_b);
        subtree.bb_r = max(subtree.bb_r, leaf.bb_r);
        subtree.bb_t = max(subtree.bb_t, leaf.bb_t);

        return subtree;
    }
};

Node.prototype.intersectsBB = Leaf.prototype.intersectsBB = function(bb)
{
    return (this.bb_l <= bb.r && bb.l <= this.bb_r && this.bb_b <= bb.t && bb.b <= this.bb_t);
};

var subtreeQuery = function(subtree, bb, func)
{
    //if(bbIntersectsBB(subtree.bb, bb)){
    if(subtree.intersectsBB(bb)){
        if(subtree.isLeaf){
            func(subtree.obj);
        } else {
            subtreeQuery(subtree.A, bb, func);
            subtreeQuery(subtree.B, bb, func);
        }
    }
};

/// Returns the fraction along the segment query the node hits. Returns Infinity if it doesn't hit.
var nodeSegmentQuery = function(node, a, b)
{
    var idx = 1/(b.x - a.x);
    var tx1 = (node.bb_l == a.x ? -Infinity : (node.bb_l - a.x)*idx);
    var tx2 = (node.bb_r == a.x ?  Infinity : (node.bb_r - a.x)*idx);
    var txmin = min(tx1, tx2);
    var txmax = max(tx1, tx2);

    var idy = 1/(b.y - a.y);
    var ty1 = (node.bb_b == a.y ? -Infinity : (node.bb_b - a.y)*idy);
    var ty2 = (node.bb_t == a.y ?  Infinity : (node.bb_t - a.y)*idy);
    var tymin = min(ty1, ty2);
    var tymax = max(ty1, ty2);

    if(tymin <= txmax && txmin <= tymax){
        var min_ = max(txmin, tymin);
        var max_ = min(txmax, tymax);

        if(0.0 <= max_ && min_ <= 1.0) return max(min_, 0.0);
    }

    return Infinity;
};

var subtreeSegmentQuery = function(subtree, a, b, t_exit, func)
{
    if(subtree.isLeaf){
        return func(subtree.obj);
    } else {
        var t_a = nodeSegmentQuery(subtree.A, a, b);
        var t_b = nodeSegmentQuery(subtree.B, a, b);

        if(t_a < t_b){
            if(t_a < t_exit) t_exit = min(t_exit, subtreeSegmentQuery(subtree.A, a, b, t_exit, func));
            if(t_b < t_exit) t_exit = min(t_exit, subtreeSegmentQuery(subtree.B, a, b, t_exit, func));
        } else {
            if(t_b < t_exit) t_exit = min(t_exit, subtreeSegmentQuery(subtree.B, a, b, t_exit, func));
            if(t_a < t_exit) t_exit = min(t_exit, subtreeSegmentQuery(subtree.A, a, b, t_exit, func));
        }

        return t_exit;
    }
};

BBTree.prototype.subtreeRecycle = function(node)
{
    if(node.isLeaf){
        this.subtreeRecycle(node.A);
        this.subtreeRecycle(node.B);
        node.recycle(this);
    }
};

var subtreeRemove = function(subtree, leaf, tree)
{
    if(leaf == subtree){
        return null;
    } else {
        var parent = leaf.parent;
        if(parent == subtree){
            var other = subtree.otherChild(leaf);
            other.parent = subtree.parent;
            subtree.recycle(tree);
            return other;
        } else {
            parent.parent.replaceChild(parent, parent.otherChild(leaf), tree);
            return subtree;
        }
    }
};

// **** Marking Functions

/*
typedef struct MarkContext {
    bbTree *tree;
    Node *staticRoot;
    cpSpatialIndexQueryFunc func;
} MarkContext;
*/

var bbTreeIntersectsNode = function(a, b)
{
    return (a.bb_l <= b.bb_r && b.bb_l <= a.bb_r && a.bb_b <= b.bb_t && b.bb_b <= a.bb_t);
};

Leaf.prototype.markLeafQuery = function(leaf, left, tree, func)
{
    if(bbTreeIntersectsNode(leaf, this)){
    if(left){
      pairInsert(leaf, this, tree);
    } else {
      if(this.stamp < leaf.stamp) pairInsert(this, leaf, tree);
      if(func) func(leaf.obj, this.obj);
    }
  }
};

Node.prototype.markLeafQuery = function(leaf, left, tree, func)
{
    if(bbTreeIntersectsNode(leaf, this)){
    this.A.markLeafQuery(leaf, left, tree, func);
    this.B.markLeafQuery(leaf, left, tree, func);
    }
};

Leaf.prototype.markSubtree = function(tree, staticRoot, func)
{
    if(this.stamp == tree.getStamp()){
        if(staticRoot) staticRoot.markLeafQuery(this, false, tree, func);

        for(var node = this; node.parent; node = node.parent){
            if(node == node.parent.A){
                node.parent.B.markLeafQuery(this, true, tree, func);
            } else {
                node.parent.A.markLeafQuery(this, false, tree, func);
            }
        }
    } else {
        var pair = this.pairs;
        while(pair){
            if(this === pair.leafB){
                if(func) func(pair.leafA.obj, this.obj);
                pair = pair.nextB;
            } else {
                pair = pair.nextA;
            }
        }
    }
};

Node.prototype.markSubtree = function(tree, staticRoot, func)
{
  this.A.markSubtree(tree, staticRoot, func);
  this.B.markSubtree(tree, staticRoot, func);
};

// **** Leaf Functions

Leaf.prototype.containsObj = function(obj)
{
    return (this.bb_l <= obj.bb_l && this.bb_r >= obj.bb_r && this.bb_b <= obj.bb_b && this.bb_t >= obj.bb_t);
};

Leaf.prototype.update = function(tree)
{
    var root = tree.root;
    var obj = this.obj;

    //if(!bbContainsBB(this.bb, bb)){
    if(!this.containsObj(obj)){
        tree.getBB(this.obj, this);

        root = subtreeRemove(root, this, tree);
        tree.root = subtreeInsert(root, this, tree);

        this.clearPairs(tree);
        this.stamp = tree.getStamp();

        return true;
    }

    return false;
};

Leaf.prototype.addPairs = function(tree)
{
    var dynamicIndex = tree.dynamicIndex;
    if(dynamicIndex){
        var dynamicRoot = dynamicIndex.root;
        if(dynamicRoot){
            dynamicRoot.markLeafQuery(this, true, dynamicIndex, null);
        }
    } else {
        var staticRoot = tree.staticIndex.root;
        this.markSubtree(tree, staticRoot, null);
    }
};

// **** Insert/Remove

BBTree.prototype.insert = function(obj, hashid)
{
    var leaf = new Leaf(this, obj);

    this.leaves[hashid] = leaf;
    this.root = subtreeInsert(this.root, leaf, this);
    this.count++;

    leaf.stamp = this.getStamp();
    leaf.addPairs(this);
    this.incrementStamp();
};

BBTree.prototype.remove = function(obj, hashid)
{
    var leaf = this.leaves[hashid];

    delete this.leaves[hashid];
    this.root = subtreeRemove(this.root, leaf, this);
    this.count--;

    leaf.clearPairs(this);
    leaf.recycle(this);
};

BBTree.prototype.contains = function(obj, hashid)
{
    return this.leaves[hashid] != null;
};

// **** Reindex
var voidQueryFunc = function(obj1, obj2){};

BBTree.prototype.reindexQuery = function(func)
{
    if(!this.root) return;

    // LeafUpdate() may modify this.root. Don't cache it.
    var hashid,
        leaves = this.leaves;
    for (hashid in leaves)
    {
        leaves[hashid].update(this);
    }

    var staticIndex = this.staticIndex;
    var staticRoot = staticIndex && staticIndex.root;

    this.root.markSubtree(this, staticRoot, func);
    if(staticIndex && !staticRoot) this.collideStatic(this, staticIndex, func);

    this.incrementStamp();
};

BBTree.prototype.reindex = function()
{
    this.reindexQuery(voidQueryFunc);
};

BBTree.prototype.reindexObject = function(obj, hashid)
{
    var leaf = this.leaves[hashid];
    if(leaf){
        if(leaf.update(this)) leaf.addPairs(this);
        this.incrementStamp();
    }
};

// **** Query

// This has since been removed from upstream Chipmunk - which recommends you just use query() below
// directly.
BBTree.prototype.pointQuery = function(point, func)
{
    this.query(new BB(point.x, point.y, point.x, point.y), func);
};

BBTree.prototype.segmentQuery = function(a, b, t_exit, func)
{
    if(this.root) subtreeSegmentQuery(this.root, a, b, t_exit, func);
};

BBTree.prototype.query = function(bb, func)
{
    if(this.root) subtreeQuery(this.root, bb, func);
};

// **** Misc

BBTree.prototype.count = function()
{
    return this.count;
};

BBTree.prototype.each = function(func)
{
    var hashid;
    for(hashid in this.leaves)
    {
        func(this.leaves[hashid].obj);
    }
};

// **** Tree Optimization

var bbTreeMergedArea2 = function(node, l, b, r, t)
{
    return (max(node.bb_r, r) - min(node.bb_l, l))*(max(node.bb_t, t) - min(node.bb_b, b));
};

var partitionNodes = function(tree, nodes, offset, count)
{
    if(count == 1){
        return nodes[offset];
    } else if(count == 2) {
        return tree.makeNode(nodes[offset], nodes[offset + 1]);
    }

    // Find the AABB for these nodes
    //var bb = nodes[offset].bb;
    var node = nodes[offset];
    var bb_l = node.bb_l,
        bb_b = node.bb_b,
        bb_r = node.bb_r,
        bb_t = node.bb_t;

    var end = offset + count;
    for(var i=offset + 1; i<end; i++){
        //bb = bbMerge(bb, nodes[i].bb);
        node = nodes[i];
        bb_l = min(bb_l, node.bb_l);
        bb_b = min(bb_b, node.bb_b);
        bb_r = max(bb_r, node.bb_r);
        bb_t = max(bb_t, node.bb_t);
    }

    // Split it on it's longest axis
    var splitWidth = (bb_r - bb_l > bb_t - bb_b);

    // Sort the bounds and use the median as the splitting point
    var bounds = new Array(count*2);
    if(splitWidth){
        for(var i=offset; i<end; i++){
            bounds[2*i + 0] = nodes[i].bb_l;
            bounds[2*i + 1] = nodes[i].bb_r;
        }
    } else {
        for(var i=offset; i<end; i++){
            bounds[2*i + 0] = nodes[i].bb_b;
            bounds[2*i + 1] = nodes[i].bb_t;
        }
    }

    bounds.sort(function(a, b) {
        // This might run faster if the function was moved out into the global scope.
        return a - b;
    });
    var split = (bounds[count - 1] + bounds[count])*0.5; // use the median as the split

    // Generate the child BBs
    //var a = bb, b = bb;
    var a_l = bb_l, a_b = bb_b, a_r = bb_r, a_t = bb_t;
    var b_l = bb_l, b_b = bb_b, b_r = bb_r, b_t = bb_t;

    if(splitWidth) a_r = b_l = split; else a_t = b_b = split;

    // Partition the nodes
    var right = end;
    for(var left=offset; left < right;){
        var node = nodes[left];
//  if(bbMergedArea(node.bb, b) < bbMergedArea(node.bb, a)){
        if(bbTreeMergedArea2(node, b_l, b_b, b_r, b_t) < bbTreeMergedArea2(node, a_l, a_b, a_r, a_t)){
            right--;
            nodes[left] = nodes[right];
            nodes[right] = node;
        } else {
            left++;
        }
    }

    if(right == count){
        var node = null;
        for(var i=offset; i<end; i++) node = subtreeInsert(node, nodes[i], tree);
        return node;
    }

    // Recurse and build the node!
    return NodeNew(tree,
        partitionNodes(tree, nodes, offset, right - offset),
        partitionNodes(tree, nodes, right, end - right)
    );
};

//static void
//bbTreeOptimizeIncremental(bbTree *tree, int passes)
//{
//  for(int i=0; i<passes; i++){
//      Node *root = tree.root;
//      Node *node = root;
//      int bit = 0;
//      unsigned int path = tree.opath;
//
//      while(!NodeIsLeaf(node)){
//          node = (path&(1<<bit) ? node.a : node.b);
//          bit = (bit + 1)&(sizeof(unsigned int)*8 - 1);
//      }
//
//      root = subtreeRemove(root, node, tree);
//      tree.root = subtreeInsert(root, node, tree);
//  }
//}

BBTree.prototype.optimize = function()
{
    var nodes = new Array(this.count);
    var i = 0;

    for (var hashid in this.leaves)
    {
        nodes[i++] = this.nodes[hashid];
    }

    tree.subtreeRecycle(root);
    this.root = partitionNodes(tree, nodes, nodes.length);
};

// **** Debug Draw

var nodeRender = function(node, depth)
{
    if(!node.isLeaf && depth <= 10){
        nodeRender(node.A, depth + 1);
        nodeRender(node.B, depth + 1);
    }

    var str = '';
    for(var i = 0; i < depth; i++) {
        str += ' ';
    }

    console.log(str + node.bb_b + ' ' + node.bb_t);
};

BBTree.prototype.log = function(){
    if(this.root) nodeRender(this.root, 0);
};

/*
static void
NodeRender(Node *node, int depth)
{
    if(!NodeIsLeaf(node) && depth <= 10){
        NodeRender(node.a, depth + 1);
        NodeRender(node.b, depth + 1);
    }

    bb bb = node.bb;

//  GLfloat v = depth/2.0f;
//  glColor3f(1.0f - v, v, 0.0f);
    glLineWidth(max(5.0f - depth, 1.0f));
    glBegin(GL_LINES); {
        glVertex2f(bb.l, bb.b);
        glVertex2f(bb.l, bb.t);

        glVertex2f(bb.l, bb.t);
        glVertex2f(bb.r, bb.t);

        glVertex2f(bb.r, bb.t);
        glVertex2f(bb.r, bb.b);

        glVertex2f(bb.r, bb.b);
        glVertex2f(bb.l, bb.b);
    }; glEnd();
}

void
bbTreeRenderDebug(cpSpatialIndex *index){
    if(index.klass != &klass){
        cpAssertWarn(false, "Ignoring bbTreeRenderDebug() call to non-tree spatial index.");
        return;
    }

    bbTree *tree = (bbTree *)index;
    if(tree.root) NodeRender(tree.root, 0);
}
*/
/* Copyright (c) 2007 Scott Lembcke
 *
 * Permission is hereby granted, free of charge, to any person obtaining a copy
 * of this software and associated documentation files (the "Software"), to deal
 * in the Software without restriction, including without limitation the rights
 * to use, copy, modify, merge, publish, distribute, sublicense, and/or sell
 * copies of the Software, and to permit persons to whom the Software is
 * furnished to do so, subject to the following conditions:
 *
 * The above copyright notice and this permission notice shall be included in
 * all copies or substantial portions of the Software.
 *
 * THE SOFTWARE IS PROVIDED "AS IS", WITHOUT WARRANTY OF ANY KIND, EXPRESS OR
 * IMPLIED, INCLUDING BUT NOT LIMITED TO THE WARRANTIES OF MERCHANTABILITY,
 * FITNESS FOR A PARTICULAR PURPOSE AND NONINFRINGEMENT. IN NO EVENT SHALL THE
 * AUTHORS OR COPYRIGHT HOLDERS BE LIABLE FOR ANY CLAIM, DAMAGES OR OTHER
 * LIABILITY, WHETHER IN AN ACTION OF CONTRACT, TORT OR OTHERWISE, ARISING FROM,
 * OUT OF OR IN CONNECTION WITH THE SOFTWARE OR THE USE OR OTHER DEALINGS IN THE
 * SOFTWARE.
 */

/// @defgroup cpArbiter cpArbiter
/// The cpArbiter struct controls pairs of colliding shapes.
/// They are also used in conjuction with collision handler callbacks
/// allowing you to retrieve information on the collision and control it.


// **** Collision Handlers
//
// Collision handlers are user-defined objects to describe the behaviour of colliding
// objects.
var CollisionHandler = cp.CollisionHandler = function()
{
    // The collision type
    this.a = this.b = 0;
};

/// Collision begin event callback
/// Returning false from a begin callback causes the collision to be ignored until
/// the the separate callback is called when the objects stop colliding.
CollisionHandler.prototype.begin = function(arb, space){return true;};

/// Collision pre-solve event callback
/// Returning false from a pre-step callback causes the collision to be ignored until the next step.
CollisionHandler.prototype.preSolve = function(arb, space){return true;};

/// Collision post-solve event function callback type.
CollisionHandler.prototype.postSolve = function(arb, space){};
/// Collision separate event function callback type.
CollisionHandler.prototype.separate = function(arb, space){};


var CP_MAX_CONTACTS_PER_ARBITER = 4;

// Arbiter states
//
// Arbiter is active and its the first collision.
//  'first coll'
// Arbiter is active and its not the first collision.
//  'normal',
// Collision has been explicitly ignored.
// Either by returning false from a begin collision handler or calling cpArbiterIgnore().
//  'ignore',
// Collison is no longer active. A space will cache an arbiter for up to cpSpace.collisionPersistence more steps.
//  'cached'

/// A colliding pair of shapes.
var Arbiter = function(a, b) {
    /// Calculated value to use for the elasticity coefficient.
    /// Override in a pre-solve collision handler for custom behavior.
    this.e = 0;
    /// Calculated value to use for the friction coefficient.
    /// Override in a pre-solve collision handler for custom behavior.
    this.u = 0;
    /// Calculated value to use for applying surface velocities.
    /// Override in a pre-solve collision handler for custom behavior.
    this.surface_vr = vzero;

    this.a = a; this.body_a = a.body;
    this.b = b; this.body_b = b.body;

    this.thread_a_next = this.thread_a_prev = null;
    this.thread_b_next = this.thread_b_prev = null;

    this.contacts = null;

    this.stamp = 0;
    this.handler = null;
    this.swappedColl = false;
    this.state = 'first coll';
};

Arbiter.prototype.getShapes = function()
{
    if (this.swappedColl){
        return [this.b, this.a];
    }else{
        return [this.a, this.b];
    }
}

/// Calculate the total impulse that was applied by this arbiter.
/// This function should only be called from a post-solve, post-step or cpBodyEachArbiter callback.
Arbiter.prototype.totalImpulse = function()
{
    var contacts = this.contacts;
    var sum = new Vect(0,0);

    for(var i=0, count=contacts.length; i<count; i++){
        var con = contacts[i];
        sum.add(vmult(con.n, con.jnAcc));
    }

    return this.swappedColl ? sum : sum.neg();
};

/// Calculate the total impulse including the friction that was applied by this arbiter.
/// This function should only be called from a post-solve, post-step or cpBodyEachArbiter callback.
Arbiter.prototype.totalImpulseWithFriction = function()
{
    var contacts = this.contacts;
    var sum = new Vect(0,0);

    for(var i=0, count=contacts.length; i<count; i++){
        var con = contacts[i];
        sum.add(new Vect(con.jnAcc, con.jtAcc).rotate(con.n));
    }

    return this.swappedColl ? sum : sum.neg();
};

/// Calculate the amount of energy lost in a collision including static, but not dynamic friction.
/// This function should only be called from a post-solve, post-step or cpBodyEachArbiter callback.
Arbiter.prototype.totalKE = function()
{
    var eCoef = (1 - this.e)/(1 + this.e);
    var sum = 0;

    var contacts = this.contacts;
    for(var i=0, count=contacts.length; i<count; i++){
        var con = contacts[i];
        var jnAcc = con.jnAcc;
        var jtAcc = con.jtAcc;

        sum += eCoef*jnAcc*jnAcc/con.nMass + jtAcc*jtAcc/con.tMass;
    }

    return sum;
};

/// Causes a collision pair to be ignored as if you returned false from a begin callback.
/// If called from a pre-step callback, you will still need to return false
/// if you want it to be ignored in the current step.
Arbiter.prototype.ignore = function()
{
    this.state = 'ignore';
};

/// Return the colliding shapes involved for this arbiter.
/// The order of their cpSpace.collision_type values will match
/// the order set when the collision handler was registered.
Arbiter.prototype.getA = function()
{
    return this.swappedColl ? this.b : this.a;
};

Arbiter.prototype.getB = function()
{
    return this.swappedColl ? this.a : this.b;
};

/// Returns true if this is the first step a pair of objects started colliding.
Arbiter.prototype.isFirstContact = function()
{
    return this.state === 'first coll';
};

/// A struct that wraps up the important collision data for an arbiter.
var ContactPoint = function(point, normal, dist)
{
    this.point = point;
    this.normal = normal;
    this.dist = dist;
};

/// Return a contact set from an arbiter.
Arbiter.prototype.getContactPointSet = function()
{
    var set = new Array(this.contacts.length);

    var i;
    for(i=0; i<set.length; i++){
        set[i] = new ContactPoint(this.contacts[i].p, this.contacts[i].n, this.contacts[i].dist);
    }

    return set;
};

/// Get the normal of the @c ith contact point.
Arbiter.prototype.getNormal = function(i)
{
    var n = this.contacts[i].n;
    return this.swappedColl ? vneg(n) : n;
};

/// Get the position of the @c ith contact point.
Arbiter.prototype.getPoint = function(i)
{
    return this.contacts[i].p;
};

/// Get the depth of the @c ith contact point.
Arbiter.prototype.getDepth = function(i)
{
    return this.contacts[i].dist;
};

/*
Arbiter.prototype.threadForBody = function(body)
{
    return (this.body_a === body ? this.thread_a : this.thread_b);
};*/

var unthreadHelper = function(arb, body, prev, next)
{
    // thread_x_y is quite ugly, but it avoids making unnecessary js objects per arbiter.
    if(prev){
        // cpArbiterThreadForBody(prev, body)->next = next;
        if(prev.body_a === body) {
            prev.thread_a_next = next;
        } else {
            prev.thread_b_next = next;
        }
    } else {
        body.arbiterList = next;
    }

    if(next){
        // cpArbiterThreadForBody(next, body)->prev = prev;
        if(next.body_a === body){
            next.thread_a_prev = prev;
        } else {
            next.thread_b_prev = prev;
        }
    }
};

Arbiter.prototype.unthread = function()
{
    unthreadHelper(this, this.body_a, this.thread_a_prev, this.thread_a_next);
    unthreadHelper(this, this.body_b, this.thread_b_prev, this.thread_b_next);
    this.thread_a_prev = this.thread_a_next = null;
    this.thread_b_prev = this.thread_b_next = null;
};

//cpFloat
//cpContactsEstimateCrushingImpulse(cpContact *contacts, int numContacts)
//{
//  cpFloat fsum = 0;
//  cpVect vsum = vzero;
//
//  for(int i=0; i<numContacts; i++){
//      cpContact *con = &contacts[i];
//      cpVect j = vrotate(con.n, v(con.jnAcc, con.jtAcc));
//
//      fsum += vlength(j);
//      vsum = vadd(vsum, j);
//  }
//
//  cpFloat vmag = vlength(vsum);
//  return (1 - vmag/fsum);
//}

Arbiter.prototype.update = function(contacts, handler, a, b)
{
    // Arbiters without contact data may exist if a collision function rejected the collision.
    if(this.contacts){
        // Iterate over the possible pairs to look for hash value matches.
        for(var i=0; i<this.contacts.length; i++){
            var old = this.contacts[i];

            for(var j=0; j<contacts.length; j++){
                var new_contact = contacts[j];

                // This could trigger false positives, but is fairly unlikely nor serious if it does.
                if(new_contact.hash === old.hash){
                    // Copy the persistant contact information.
                    new_contact.jnAcc = old.jnAcc;
                    new_contact.jtAcc = old.jtAcc;
                }
            }
        }
    }

    this.contacts = contacts;

    this.handler = handler;
    this.swappedColl = (a.collision_type !== handler.a);

    this.e = a.e * b.e;
    this.u = a.u * b.u;
    this.surface_vr = vsub(a.surface_v, b.surface_v);

    // For collisions between two similar primitive types, the order could have been swapped.
    this.a = a; this.body_a = a.body;
    this.b = b; this.body_b = b.body;

    // mark it as new if it's been cached
    if(this.state == 'cached') this.state = 'first coll';
};

Arbiter.prototype.preStep = function(dt, slop, bias)
{
    var a = this.body_a;
    var b = this.body_b;

    for(var i=0; i<this.contacts.length; i++){
        var con = this.contacts[i];

        // Calculate the offsets.
        con.r1 = vsub(con.p, a.p);
        con.r2 = vsub(con.p, b.p);

        // Calculate the mass normal and mass tangent.
        con.nMass = 1/k_scalar(a, b, con.r1, con.r2, con.n);
        con.tMass = 1/k_scalar(a, b, con.r1, con.r2, vperp(con.n));

        // Calculate the target bias velocity.
        con.bias = -bias*min(0, con.dist + slop)/dt;
        con.jBias = 0;

        // Calculate the target bounce velocity.
        con.bounce = normal_relative_velocity(a, b, con.r1, con.r2, con.n)*this.e;
    }
};

Arbiter.prototype.applyCachedImpulse = function(dt_coef)
{
    if(this.isFirstContact()) return;

    var a = this.body_a;
    var b = this.body_b;

    for(var i=0; i<this.contacts.length; i++){
        var con = this.contacts[i];
        //var j = vrotate(con.n, new Vect(con.jnAcc, con.jtAcc));
        var nx = con.n.x;
        var ny = con.n.y;
        var jx = nx*con.jnAcc - ny*con.jtAcc;
        var jy = nx*con.jtAcc + ny*con.jnAcc;
        //apply_impulses(a, b, con.r1, con.r2, vmult(j, dt_coef));
        apply_impulses(a, b, con.r1, con.r2, jx * dt_coef, jy * dt_coef);
    }
};

// TODO is it worth splitting velocity/position correction?

var numApplyImpulse = 0;
var numApplyContact = 0;

Arbiter.prototype.applyImpulse = function()
{
    numApplyImpulse++;
    //if (!this.contacts) { throw new Error('contacts is undefined'); }
    var a = this.body_a;
    var b = this.body_b;
    var surface_vr = this.surface_vr;
    var friction = this.u;

    for(var i=0; i<this.contacts.length; i++){
        numApplyContact++;
        var con = this.contacts[i];
        var nMass = con.nMass;
        var n = con.n;
        var r1 = con.r1;
        var r2 = con.r2;

        //var vr = relative_velocity(a, b, r1, r2);
        var vrx = b.vx - r2.y * b.w - (a.vx - r1.y * a.w);
        var vry = b.vy + r2.x * b.w - (a.vy + r1.x * a.w);

        //var vb1 = vadd(vmult(vperp(r1), a.w_bias), a.v_bias);
        //var vb2 = vadd(vmult(vperp(r2), b.w_bias), b.v_bias);
        //var vbn = vdot(vsub(vb2, vb1), n);

        var vbn = n.x*(b.v_biasx - r2.y * b.w_bias - a.v_biasx + r1.y * a.w_bias) +
                n.y*(r2.x*b.w_bias + b.v_biasy - r1.x * a.w_bias - a.v_biasy);

        var vrn = vdot2(vrx, vry, n.x, n.y);
        //var vrt = vdot(vadd(vr, surface_vr), vperp(n));
        var vrt = vdot2(vrx + surface_vr.x, vry + surface_vr.y, -n.y, n.x);

        var jbn = (con.bias - vbn)*nMass;
        var jbnOld = con.jBias;
        con.jBias = max(jbnOld + jbn, 0);

        var jn = -(con.bounce + vrn)*nMass;
        var jnOld = con.jnAcc;
        con.jnAcc = max(jnOld + jn, 0);

        var jtMax = friction*con.jnAcc;
        var jt = -vrt*con.tMass;
        var jtOld = con.jtAcc;
        con.jtAcc = clamp(jtOld + jt, -jtMax, jtMax);

        //apply_bias_impulses(a, b, r1, r2, vmult(n, con.jBias - jbnOld));
        var bias_x = n.x * (con.jBias - jbnOld);
        var bias_y = n.y * (con.jBias - jbnOld);
        apply_bias_impulse(a, -bias_x, -bias_y, r1);
        apply_bias_impulse(b, bias_x, bias_y, r2);

        //apply_impulses(a, b, r1, r2, vrotate(n, new Vect(con.jnAcc - jnOld, con.jtAcc - jtOld)));
        var rot_x = con.jnAcc - jnOld;
        var rot_y = con.jtAcc - jtOld;

        // Inlining apply_impulses decreases speed for some reason :/
        apply_impulses(a, b, r1, r2, n.x*rot_x - n.y*rot_y, n.x*rot_y + n.y*rot_x);
    }
};

Arbiter.prototype.callSeparate = function(space)
{
    // The handler needs to be looked up again as the handler cached on the arbiter may have been deleted since the last step.
    var handler = space.lookupHandler(this.a.collision_type, this.b.collision_type);
    handler.separate(this, space);
};

// From chipmunk_private.h
Arbiter.prototype.next = function(body)
{
    return (this.body_a == body ? this.thread_a_next : this.thread_b_next);
};
/* Copyright (c) 2007 Scott Lembcke
 *
 * Permission is hereby granted, free of charge, to any person obtaining a copy
 * of this software and associated documentation files (the "Software"), to deal
 * in the Software without restriction, including without limitation the rights
 * to use, copy, modify, merge, publish, distribute, sublicense, and/or sell
 * copies of the Software, and to permit persons to whom the Software is
 * furnished to do so, subject to the following conditions:
 *
 * The above copyright notice and this permission notice shall be included in
 * all copies or substantial portions of the Software.
 *
 * THE SOFTWARE IS PROVIDED "AS IS", WITHOUT WARRANTY OF ANY KIND, EXPRESS OR
 * IMPLIED, INCLUDING BUT NOT LIMITED TO THE WARRANTIES OF MERCHANTABILITY,
 * FITNESS FOR A PARTICULAR PURPOSE AND NONINFRINGEMENT. IN NO EVENT SHALL THE
 * AUTHORS OR COPYRIGHT HOLDERS BE LIABLE FOR ANY CLAIM, DAMAGES OR OTHER
 * LIABILITY, WHETHER IN AN ACTION OF CONTRACT, TORT OR OTHERWISE, ARISING FROM,
 * OUT OF OR IN CONNECTION WITH THE SOFTWARE OR THE USE OR OTHER DEALINGS IN THE
 * SOFTWARE.
 */

var numContacts = 0;

var Contact = function(p, n, dist, hash)
{
    this.p = p;
    this.n = n;
    this.dist = dist;

    this.r1 = this.r2 = vzero;
    this.nMass = this.tMass = this.bounce = this.bias = 0;

    this.jnAcc = this.jtAcc = this.jBias = 0;

    this.hash = hash;
    numContacts++;
};

var NONE = [];

// Add contact points for circle to circle collisions.
// Used by several collision tests.
var circle2circleQuery = function(p1, p2, r1, r2)
{
    var mindist = r1 + r2;
    var delta = vsub(p2, p1);
    var distsq = vlengthsq(delta);
    if(distsq >= mindist*mindist) return;

    var dist = Math.sqrt(distsq);

    // Allocate and initialize the contact.
    return new Contact(
        vadd(p1, vmult(delta, 0.5 + (r1 - 0.5*mindist)/(dist ? dist : Infinity))),
        (dist ? vmult(delta, 1/dist) : new Vect(1, 0)),
        dist - mindist,
        0
    );
};

// Collide circle shapes.
var circle2circle = function(circ1, circ2)
{
    var contact = circle2circleQuery(circ1.tc, circ2.tc, circ1.r, circ2.r);
    return contact ? [contact] : NONE;
};

var circle2segment = function(circleShape, segmentShape)
{
    var seg_a = segmentShape.ta;
    var seg_b = segmentShape.tb;
    var center = circleShape.tc;

    var seg_delta = vsub(seg_b, seg_a);
    var closest_t = clamp01(vdot(seg_delta, vsub(center, seg_a))/vlengthsq(seg_delta));
    var closest = vadd(seg_a, vmult(seg_delta, closest_t));

    var contact = circle2circleQuery(center, closest, circleShape.r, segmentShape.r);
    if(contact){
        var n = contact.n;

        // Reject endcap collisions if tangents are provided.
        return (
            (closest_t === 0 && vdot(n, segmentShape.a_tangent) < 0) ||
            (closest_t === 1 && vdot(n, segmentShape.b_tangent) < 0)
        ) ? NONE : [contact];
    } else {
        return NONE;
    }
}

// Find the minimum separating axis for the given poly and axis list.
//
// This function needs to return two values - the index of the min. separating axis and
// the value itself. Short of inlining MSA, returning values through a global like this
// is the fastest implementation.
//
// See: http://jsperf.com/return-two-values-from-function/2
var last_MSA_min = 0;
var findMSA = function(poly, planes)
{
    var min_index = 0;
    var min = poly.valueOnAxis(planes[0].n, planes[0].d);
    if(min > 0) return -1;

    for(var i=1; i<planes.length; i++){
        var dist = poly.valueOnAxis(planes[i].n, planes[i].d);
        if(dist > 0) {
            return -1;
        } else if(dist > min){
            min = dist;
            min_index = i;
        }
    }

    last_MSA_min = min;
    return min_index;
};

// Add contacts for probably penetrating vertexes.
// This handles the degenerate case where an overlap was detected, but no vertexes fall inside
// the opposing polygon. (like a star of david)
var findVertsFallback = function(poly1, poly2, n, dist)
{
    var arr = [];

    var verts1 = poly1.tVerts;
    for(var i=0; i<verts1.length; i+=2){
        var vx = verts1[i];
        var vy = verts1[i+1];
        if(poly2.containsVertPartial(vx, vy, vneg(n))){
            arr.push(new Contact(new Vect(vx, vy), n, dist, hashPair(poly1.hashid, i)));
        }
    }

    var verts2 = poly2.tVerts;
    for(var i=0; i<verts2.length; i+=2){
        var vx = verts2[i];
        var vy = verts2[i+1];
        if(poly1.containsVertPartial(vx, vy, n)){
            arr.push(new Contact(new Vect(vx, vy), n, dist, hashPair(poly2.hashid, i)));
        }
    }

    return arr;
};

// Add contacts for penetrating vertexes.
var findVerts = function(poly1, poly2, n, dist)
{
    var arr = [];

    var verts1 = poly1.tVerts;
    for(var i=0; i<verts1.length; i+=2){
        var vx = verts1[i];
        var vy = verts1[i+1];
        if(poly2.containsVert(vx, vy)){
            arr.push(new Contact(new Vect(vx, vy), n, dist, hashPair(poly1.hashid, i>>1)));
        }
    }

    var verts2 = poly2.tVerts;
    for(var i=0; i<verts2.length; i+=2){
        var vx = verts2[i];
        var vy = verts2[i+1];
        if(poly1.containsVert(vx, vy)){
            arr.push(new Contact(new Vect(vx, vy), n, dist, hashPair(poly2.hashid, i>>1)));
        }
    }

    return (arr.length ? arr : findVertsFallback(poly1, poly2, n, dist));
};

// Collide poly shapes together.
var poly2poly = function(poly1, poly2)
{
    var mini1 = findMSA(poly2, poly1.tPlanes);
    if(mini1 == -1) return NONE;
    var min1 = last_MSA_min;

    var mini2 = findMSA(poly1, poly2.tPlanes);
    if(mini2 == -1) return NONE;
    var min2 = last_MSA_min;

    // There is overlap, find the penetrating verts
    if(min1 > min2)
        return findVerts(poly1, poly2, poly1.tPlanes[mini1].n, min1);
    else
        return findVerts(poly1, poly2, vneg(poly2.tPlanes[mini2].n), min2);
};

// Like cpPolyValueOnAxis(), but for segments.
var segValueOnAxis = function(seg, n, d)
{
    var a = vdot(n, seg.ta) - seg.r;
    var b = vdot(n, seg.tb) - seg.r;
    return min(a, b) - d;
};

// Identify vertexes that have penetrated the segment.
var findPointsBehindSeg = function(arr, seg, poly, pDist, coef)
{
    var dta = vcross(seg.tn, seg.ta);
    var dtb = vcross(seg.tn, seg.tb);
    var n = vmult(seg.tn, coef);

    var verts = poly.tVerts;
    for(var i=0; i<verts.length; i+=2){
        var vx = verts[i];
        var vy = verts[i+1];
        if(vdot2(vx, vy, n.x, n.y) < vdot(seg.tn, seg.ta)*coef + seg.r){
            var dt = vcross2(seg.tn.x, seg.tn.y, vx, vy);
            if(dta >= dt && dt >= dtb){
                arr.push(new Contact(new Vect(vx, vy), n, pDist, hashPair(poly.hashid, i)));
            }
        }
    }
};

// This one is complicated and gross. Just don't go there...
// TODO: Comment me!
var seg2poly = function(seg, poly)
{
    var arr = [];

    var planes = poly.tPlanes;
    var numVerts = planes.length;

    var segD = vdot(seg.tn, seg.ta);
    var minNorm = poly.valueOnAxis(seg.tn, segD) - seg.r;
    var minNeg = poly.valueOnAxis(vneg(seg.tn), -segD) - seg.r;
    if(minNeg > 0 || minNorm > 0) return NONE;

    var mini = 0;
    var poly_min = segValueOnAxis(seg, planes[0].n, planes[0].d);
    if(poly_min > 0) return NONE;
    for(var i=0; i<numVerts; i++){
        var dist = segValueOnAxis(seg, planes[i].n, planes[i].d);
        if(dist > 0){
            return NONE;
        } else if(dist > poly_min){
            poly_min = dist;
            mini = i;
        }
    }

    var poly_n = vneg(planes[mini].n);

    var va = vadd(seg.ta, vmult(poly_n, seg.r));
    var vb = vadd(seg.tb, vmult(poly_n, seg.r));
    if(poly.containsVert(va.x, va.y))
        arr.push(new Contact(va, poly_n, poly_min, hashPair(seg.hashid, 0)));
    if(poly.containsVert(vb.x, vb.y))
        arr.push(new Contact(vb, poly_n, poly_min, hashPair(seg.hashid, 1)));

    // Floating point precision problems here.
    // This will have to do for now.
//  poly_min -= cp_collision_slop; // TODO is this needed anymore?

    if(minNorm >= poly_min || minNeg >= poly_min) {
        if(minNorm > minNeg)
            findPointsBehindSeg(arr, seg, poly, minNorm, 1);
        else
            findPointsBehindSeg(arr, seg, poly, minNeg, -1);
    }

    // If no other collision points are found, try colliding endpoints.
    if(arr.length === 0){
        var mini2 = mini * 2;
        var verts = poly.tVerts;

        var poly_a = new Vect(verts[mini2], verts[mini2+1]);

        var con;
        if((con = circle2circleQuery(seg.ta, poly_a, seg.r, 0, arr))) return [con];
        if((con = circle2circleQuery(seg.tb, poly_a, seg.r, 0, arr))) return [con];

        var len = numVerts * 2;
        var poly_b = new Vect(verts[(mini2+2)%len], verts[(mini2+3)%len]);
        if((con = circle2circleQuery(seg.ta, poly_b, seg.r, 0, arr))) return [con];
        if((con = circle2circleQuery(seg.tb, poly_b, seg.r, 0, arr))) return [con];
    }

//  console.log(poly.tVerts, poly.tPlanes);
//  console.log('seg2poly', arr);
    return arr;
};

// This one is less gross, but still gross.
// TODO: Comment me!
var circle2poly = function(circ, poly)
{
    var planes = poly.tPlanes;

    var mini = 0;
    var min = vdot(planes[0].n, circ.tc) - planes[0].d - circ.r;
    for(var i=0; i<planes.length; i++){
        var dist = vdot(planes[i].n, circ.tc) - planes[i].d - circ.r;
        if(dist > 0){
            return NONE;
        } else if(dist > min) {
            min = dist;
            mini = i;
        }
    }

    var n = planes[mini].n;

    var verts = poly.tVerts;
    var len = verts.length;
    var mini2 = mini<<1;

    //var a = poly.tVerts[mini];
    //var b = poly.tVerts[(mini + 1)%poly.tVerts.length];
    var ax = verts[mini2];
    var ay = verts[mini2+1];
    var bx = verts[(mini2+2)%len];
    var by = verts[(mini2+3)%len];

    var dta = vcross2(n.x, n.y, ax, ay);
    var dtb = vcross2(n.x, n.y, bx, by);
    var dt = vcross(n, circ.tc);

    if(dt < dtb){
        var con = circle2circleQuery(circ.tc, new Vect(bx, by), circ.r, 0, con);
        return con ? [con] : NONE;
    } else if(dt < dta) {
        return [new Contact(
            vsub(circ.tc, vmult(n, circ.r + min/2)),
            vneg(n),
            min,
            0
        )];
    } else {
        var con = circle2circleQuery(circ.tc, new Vect(ax, ay), circ.r, 0, con);
        return con ? [con] : NONE;
    }
};

// The javascripty way to do this would be either nested object or methods on the prototypes.
//
// However, the *fastest* way is the method below.
// See: http://jsperf.com/dispatch

// These are copied from the prototypes into the actual objects in the Shape constructor.
CircleShape.prototype.collisionCode = 0;
SegmentShape.prototype.collisionCode = 1;
PolyShape.prototype.collisionCode = 2;

CircleShape.prototype.collisionTable = [
    circle2circle,
    circle2segment,
    circle2poly
];

SegmentShape.prototype.collisionTable = [
    null,
    function(segA, segB) { return NONE; }, // seg2seg
    seg2poly
];

PolyShape.prototype.collisionTable = [
    null,
    null,
    poly2poly
];

var collideShapes = cp.collideShapes = function(a, b)
{
    assert(a.collisionCode <= b.collisionCode, 'Collided shapes must be sorted by type');
    return a.collisionTable[b.collisionCode](a, b);
};

/* Copyright (c) 2007 Scott Lembcke
 *
 * Permission is hereby granted, free of charge, to any person obtaining a copy
 * of this software and associated documentation files (the "Software"), to deal
 * in the Software without restriction, including without limitation the rights
 * to use, copy, modify, merge, publish, distribute, sublicense, and/or sell
 * copies of the Software, and to permit persons to whom the Software is
 * furnished to do so, subject to the following conditions:
 *
 * The above copyright notice and this permission notice shall be included in
 * all copies or substantial portions of the Software.
 *
 * THE SOFTWARE IS PROVIDED "AS IS", WITHOUT WARRANTY OF ANY KIND, EXPRESS OR
 * IMPLIED, INCLUDING BUT NOT LIMITED TO THE WARRANTIES OF MERCHANTABILITY,
 * FITNESS FOR A PARTICULAR PURPOSE AND NONINFRINGEMENT. IN NO EVENT SHALL THE
 * AUTHORS OR COPYRIGHT HOLDERS BE LIABLE FOR ANY CLAIM, DAMAGES OR OTHER
 * LIABILITY, WHETHER IN AN ACTION OF CONTRACT, TORT OR OTHERWISE, ARISING FROM,
 * OUT OF OR IN CONNECTION WITH THE SOFTWARE OR THE USE OR OTHER DEALINGS IN THE
 * SOFTWARE.
 */

var defaultCollisionHandler = new CollisionHandler();

/// Basic Unit of Simulation in Chipmunk
var Space = cp.Space = function() {
    this.stamp = 0;
    this.curr_dt = 0;

    this.bodies = [];
    this.rousedBodies = [];
    this.sleepingComponents = [];

    this.staticShapes = new BBTree(null);
    this.activeShapes = new BBTree(this.staticShapes);

    this.arbiters = [];
    this.contactBuffersHead = null;
    this.cachedArbiters = {};
    //this.pooledArbiters = [];

    this.constraints = [];

    this.locked = 0;

    this.collisionHandlers = {};
    this.defaultHandler = defaultCollisionHandler;

    this.postStepCallbacks = [];

    /// Number of iterations to use in the impulse solver to solve contacts.
    this.iterations = 10;

    /// Gravity to pass to rigid bodies when integrating velocity.
    this.gravity = vzero;

    /// Damping rate expressed as the fraction of velocity bodies retain each second.
    /// A value of 0.9 would mean that each body's velocity will drop 10% per second.
    /// The default value is 1.0, meaning no damping is applied.
    /// @note This damping value is different than those of cpDampedSpring and cpDampedRotarySpring.
    this.damping = 1;

    /// Speed threshold for a body to be considered idle.
    /// The default value of 0 means to let the space guess a good threshold based on gravity.
    this.idleSpeedThreshold = 0;

    /// Time a group of bodies must remain idle in order to fall asleep.
    /// Enabling sleeping also implicitly enables the the contact graph.
    /// The default value of Infinity disables the sleeping algorithm.
    this.sleepTimeThreshold = Infinity;

    /// Amount of encouraged penetration between colliding shapes..
    /// Used to reduce oscillating contacts and keep the collision cache warm.
    /// Defaults to 0.1. If you have poor simulation quality,
    /// increase this number as much as possible without allowing visible amounts of overlap.
    this.collisionSlop = 0.1;

    /// Determines how fast overlapping shapes are pushed apart.
    /// Expressed as a fraction of the error remaining after each second.
    /// Defaults to pow(1.0 - 0.1, 60.0) meaning that Chipmunk fixes 10% of overlap each frame at 60Hz.
    this.collisionBias = Math.pow(1 - 0.1, 60);

    /// Number of frames that contact information should persist.
    /// Defaults to 3. There is probably never a reason to change this value.
    this.collisionPersistence = 3;

    /// Rebuild the contact graph during each step. Must be enabled to use the cpBodyEachArbiter() function.
    /// Disabled by default for a small performance boost. Enabled implicitly when the sleeping feature is enabled.
    this.enableContactGraph = false;

    /// The designated static body for this space.
    /// You can modify this body, or replace it with your own static body.
    /// By default it points to a statically allocated cpBody in the cpSpace struct.
    this.staticBody = new Body(Infinity, Infinity);
    this.staticBody.nodeIdleTime = Infinity;

    // Cache the collideShapes callback function for the space.
    this.collideShapes = this.makeCollideShapes();
};

Space.prototype.getCurrentTimeStep = function() { return this.curr_dt; };

Space.prototype.setIterations = function(iter) { this.iterations = iter; };

/// returns true from inside a callback and objects cannot be added/removed.
Space.prototype.isLocked = function()
{
    return this.locked;
};

var assertSpaceUnlocked = function(space)
{
    assert(!space.locked, "This addition/removal cannot be done safely during a call to cpSpaceStep() \
 or during a query. Put these calls into a post-step callback.");
};

// **** Collision handler function management

/// Set a collision handler to be used whenever the two shapes with the given collision types collide.
/// You can pass null for any function you don't want to implement.
Space.prototype.addCollisionHandler = function(a, b, begin, preSolve, postSolve, separate)
{
    assertSpaceUnlocked(this);

    // Remove any old function so the new one will get added.
    this.removeCollisionHandler(a, b);

    var handler = new CollisionHandler();
    handler.a = a;
    handler.b = b;
    if(begin) handler.begin = begin;
    if(preSolve) handler.preSolve = preSolve;
    if(postSolve) handler.postSolve = postSolve;
    if(separate) handler.separate = separate;

    this.collisionHandlers[hashPair(a, b)] = handler;
};

/// Unset a collision handler.
Space.prototype.removeCollisionHandler = function(a, b)
{
    assertSpaceUnlocked(this);

    delete this.collisionHandlers[hashPair(a, b)];
};

/// Set a default collision handler for this space.
/// The default collision handler is invoked for each colliding pair of shapes
/// that isn't explicitly handled by a specific collision handler.
/// You can pass null for any function you don't want to implement.
Space.prototype.setDefaultCollisionHandler = function(begin, preSolve, postSolve, separate)
{
    assertSpaceUnlocked(this);

    var handler = new CollisionHandler();
    if(begin) handler.begin = begin;
    if(preSolve) handler.preSolve = preSolve;
    if(postSolve) handler.postSolve = postSolve;
    if(separate) handler.separate = separate;

    this.defaultHandler = handler;
};

Space.prototype.lookupHandler = function(a, b)
{
    return this.collisionHandlers[hashPair(a, b)] || this.defaultHandler;
};

// **** Body, Shape, and Joint Management

/// Add a collision shape to the simulation.
/// If the shape is attached to a static body, it will be added as a static shape.
Space.prototype.addShape = function(shape)
{
    var body = shape.body;
    if(body.isStatic()) return this.addStaticShape(shape);

    assert(!shape.space, "This shape is already added to a space and cannot be added to another.");
    assertSpaceUnlocked(this);

    body.activate();
    body.addShape(shape);

    shape.update(body.p, body.rot);
    this.activeShapes.insert(shape, shape.hashid);
    shape.space = this;

    return shape;
};

/// Explicity add a shape as a static shape to the simulation.
Space.prototype.addStaticShape = function(shape)
{
    assert(!shape.space, "This shape is already added to a space and cannot be added to another.");
    assertSpaceUnlocked(this);

    var body = shape.body;
    body.addShape(shape);

    shape.update(body.p, body.rot);
    this.staticShapes.insert(shape, shape.hashid);
    shape.space = this;

    return shape;
};

/// Add a rigid body to the simulation.
Space.prototype.addBody = function(body)
{
    assert(!body.isStatic(), "Static bodies cannot be added to a space as they are not meant to be simulated.");
    assert(!body.space, "This body is already added to a space and cannot be added to another.");
    assertSpaceUnlocked(this);

    this.bodies.push(body);
    body.space = this;

    return body;
};

/// Add a constraint to the simulation.
Space.prototype.addConstraint = function(constraint)
{
    assert(!constraint.space, "This shape is already added to a space and cannot be added to another.");
    assertSpaceUnlocked(this);

    var a = constraint.a, b = constraint.b;

    a.activate();
    b.activate();
    this.constraints.push(constraint);

    // Push onto the heads of the bodies' constraint lists
    constraint.next_a = a.constraintList; a.constraintList = constraint;
    constraint.next_b = b.constraintList; b.constraintList = constraint;
    constraint.space = this;

    return constraint;
};

Space.prototype.filterArbiters = function(body, filter)
{
    for (var hash in this.cachedArbiters)
    {
        var arb = this.cachedArbiters[hash];

        // Match on the filter shape, or if it's null the filter body
        if(
            (body === arb.body_a && (filter === arb.a || filter === null)) ||
            (body === arb.body_b && (filter === arb.b || filter === null))
        ){
            // Call separate when removing shapes.
            if(filter && arb.state !== 'cached') arb.callSeparate(this);

            arb.unthread();

            deleteObjFromList(this.arbiters, arb);
            //this.pooledArbiters.push(arb);

            delete this.cachedArbiters[hash];
        }
    }
};

/// Remove a collision shape from the simulation.
Space.prototype.removeShape = function(shape)
{
    var body = shape.body;
    if(body.isStatic()){
        this.removeStaticShape(shape);
    } else {
        assert(this.containsShape(shape),
            "Cannot remove a shape that was not added to the space. (Removed twice maybe?)");
        assertSpaceUnlocked(this);

        body.activate();
        body.removeShape(shape);
        this.filterArbiters(body, shape);
        this.activeShapes.remove(shape, shape.hashid);
        shape.space = null;
    }
};

/// Remove a collision shape added using addStaticShape() from the simulation.
Space.prototype.removeStaticShape = function(shape)
{
    assert(this.containsShape(shape),
        "Cannot remove a static or sleeping shape that was not added to the space. (Removed twice maybe?)");
    assertSpaceUnlocked(this);

    var body = shape.body;
    if(body.isStatic()) body.activateStatic(shape);
    body.removeShape(shape);
    this.filterArbiters(body, shape);
    this.staticShapes.remove(shape, shape.hashid);
    shape.space = null;
};

/// Remove a rigid body from the simulation.
Space.prototype.removeBody = function(body)
{
    assert(this.containsBody(body),
        "Cannot remove a body that was not added to the space. (Removed twice maybe?)");
    assertSpaceUnlocked(this);

    body.activate();
//  this.filterArbiters(body, null);
    deleteObjFromList(this.bodies, body);
    body.space = null;
};

/// Remove a constraint from the simulation.
Space.prototype.removeConstraint = function(constraint)
{
    assert(this.containsConstraint(constraint),
        "Cannot remove a constraint that was not added to the space. (Removed twice maybe?)");
    assertSpaceUnlocked(this);

    constraint.a.activate();
    constraint.b.activate();
    deleteObjFromList(this.constraints, constraint);

    constraint.a.removeConstraint(constraint);
    constraint.b.removeConstraint(constraint);
    constraint.space = null;
};

/// Test if a collision shape has been added to the space.
Space.prototype.containsShape = function(shape)
{
    return (shape.space === this);
};

/// Test if a rigid body has been added to the space.
Space.prototype.containsBody = function(body)
{
    return (body.space == this);
};

/// Test if a constraint has been added to the space.
Space.prototype.containsConstraint = function(constraint)
{
    return (constraint.space == this);
};

Space.prototype.uncacheArbiter = function(arb)
{
    delete this.cachedArbiters[hashPair(arb.a.hashid, arb.b.hashid)];
    deleteObjFromList(this.arbiters, arb);
};


// **** Iteration

/// Call @c func for each body in the space.
Space.prototype.eachBody = function(func)
{
    this.lock(); {
        var bodies = this.bodies;

        for(var i=0; i<bodies.length; i++){
            func(bodies[i]);
        }

        var components = this.sleepingComponents;
        for(var i=0; i<components.length; i++){
            var root = components[i];

            var body = root;
            while(body){
                var next = body.nodeNext;
                func(body);
                body = next;
            }
        }
    } this.unlock(true);
};

/// Call @c func for each shape in the space.
Space.prototype.eachShape = function(func)
{
    this.lock(); {
        this.activeShapes.each(func);
        this.staticShapes.each(func);
    } this.unlock(true);
};

/// Call @c func for each shape in the space.
Space.prototype.eachConstraint = function(func)
{
    this.lock(); {
        var constraints = this.constraints;

        for(var i=0; i<constraints.length; i++){
            func(constraints[i]);
        }
    } this.unlock(true);
};

// **** Spatial Index Management

/// Update the collision detection info for the static shapes in the space.
Space.prototype.reindexStatic = function()
{
    assert(!this.locked, "You cannot manually reindex objects while the space is locked. Wait until the current query or step is complete.");

    this.staticShapes.each(function(shape){
        var body = shape.body;
        shape.update(body.p, body.rot);
    });
    this.staticShapes.reindex();
};

/// Update the collision detection data for a specific shape in the space.
Space.prototype.reindexShape = function(shape)
{
    assert(!this.locked, "You cannot manually reindex objects while the space is locked. Wait until the current query or step is complete.");

    var body = shape.body;
    shape.update(body.p, body.rot);

    // attempt to rehash the shape in both hashes
    this.activeShapes.reindexObject(shape, shape.hashid);
    this.staticShapes.reindexObject(shape, shape.hashid);
};

/// Update the collision detection data for all shapes attached to a body.
Space.prototype.reindexShapesForBody = function(body)
{
    for(var shape = body.shapeList; shape; shape = shape.next){
        this.reindexShape(shape);
    }
};

/// Switch the space to use a spatial has as it's spatial index.
Space.prototype.useSpatialHash = function(dim, count)
{
    throw new Error('Spatial Hash not implemented.');

    var staticShapes = new SpaceHash(dim, count, null);
    var activeShapes = new SpaceHash(dim, count, staticShapes);

    this.staticShapes.each(function(shape){
        staticShapes.insert(shape, shape.hashid);
    });
    this.activeShapes.each(function(shape){
        activeShapes.insert(shape, shape.hashid);
    });

    this.staticShapes = staticShapes;
    this.activeShapes = activeShapes;
};

/* Copyright (c) 2007 Scott Lembcke
 *
 * Permission is hereby granted, free of charge, to any person obtaining a copy
 * of this software and associated documentation files (the "Software"), to deal
 * in the Software without restriction, including without limitation the rights
 * to use, copy, modify, merge, publish, distribute, sublicense, and/or sell
 * copies of the Software, and to permit persons to whom the Software is
 * furnished to do so, subject to the following conditions:
 *
 * The above copyright notice and this permission notice shall be included in
 * all copies or substantial portions of the Software.
 *
 * THE SOFTWARE IS PROVIDED "AS IS", WITHOUT WARRANTY OF ANY KIND, EXPRESS OR
 * IMPLIED, INCLUDING BUT NOT LIMITED TO THE WARRANTIES OF MERCHANTABILITY,
 * FITNESS FOR A PARTICULAR PURPOSE AND NONINFRINGEMENT. IN NO EVENT SHALL THE
 * AUTHORS OR COPYRIGHT HOLDERS BE LIABLE FOR ANY CLAIM, DAMAGES OR OTHER
 * LIABILITY, WHETHER IN AN ACTION OF CONTRACT, TORT OR OTHERWISE, ARISING FROM,
 * OUT OF OR IN CONNECTION WITH THE SOFTWARE OR THE USE OR OTHER DEALINGS IN THE
 * SOFTWARE.
 */

/// **** Sleeping Functions

Space.prototype.activateBody = function(body)
{
    assert(!body.isRogue(), "Internal error: Attempting to activate a rogue body.");

    if(this.locked){
        // cpSpaceActivateBody() is called again once the space is unlocked
        if(this.rousedBodies.indexOf(body) === -1) this.rousedBodies.push(body);
    } else {
        this.bodies.push(body);

        for(var i = 0; i < body.shapeList.length; i++){
            var shape = body.shapeList[i];
            this.staticShapes.remove(shape, shape.hashid);
            this.activeShapes.insert(shape, shape.hashid);
        }

        for(var arb = body.arbiterList; arb; arb = arb.next(body)){
            var bodyA = arb.body_a;
            if(body === bodyA || bodyA.isStatic()){
                //var contacts = arb.contacts;

                // Restore contact values back to the space's contact buffer memory
                //arb.contacts = cpContactBufferGetArray(this);
                //memcpy(arb.contacts, contacts, numContacts*sizeof(cpContact));
                //cpSpacePushContacts(this, numContacts);

                // Reinsert the arbiter into the arbiter cache
                var a = arb.a, b = arb.b;
                this.cachedArbiters[hashPair(a.hashid, b.hashid)] = arb;

                // Update the arbiter's state
                arb.stamp = this.stamp;
                arb.handler = this.lookupHandler(a.collision_type, b.collision_type);
                this.arbiters.push(arb);
            }
        }

        for(var constraint = body.constraintList; constraint; constraint = constraint.nodeNext){
            var bodyA = constraint.a;
            if(body === bodyA || bodyA.isStatic()) this.constraints.push(constraint);
        }
    }
};

Space.prototype.deactivateBody = function(body)
{
    assert(!body.isRogue(), "Internal error: Attempting to deactivate a rogue body.");

    deleteObjFromList(this.bodies, body);

    for(var i = 0; i < body.shapeList.length; i++){
        var shape = body.shapeList[i];
        this.activeShapes.remove(shape, shape.hashid);
        this.staticShapes.insert(shape, shape.hashid);
    }

    for(var arb = body.arbiterList; arb; arb = arb.next(body)){
        var bodyA = arb.body_a;
        if(body === bodyA || bodyA.isStatic()){
            this.uncacheArbiter(arb);

            // Save contact values to a new block of memory so they won't time out
            //size_t bytes = arb.numContacts*sizeof(cpContact);
            //cpContact *contacts = (cpContact *)cpcalloc(1, bytes);
            //memcpy(contacts, arb.contacts, bytes);
            //arb.contacts = contacts;
        }
    }

    for(var constraint = body.constraintList; constraint; constraint = constraint.nodeNext){
        var bodyA = constraint.a;
        if(body === bodyA || bodyA.isStatic()) deleteObjFromList(this.constraints, constraint);
    }
};

var componentRoot = function(body)
{
    return (body ? body.nodeRoot : null);
};

var componentActivate = function(root)
{
    if(!root || !root.isSleeping(root)) return;
    assert(!root.isRogue(), "Internal Error: componentActivate() called on a rogue body.");

    var space = root.space;
    var body = root;
    while(body){
        var next = body.nodeNext;

        body.nodeIdleTime = 0;
        body.nodeRoot = null;
        body.nodeNext = null;
        space.activateBody(body);

        body = next;
    }

    deleteObjFromList(space.sleepingComponents, root);
};

Body.prototype.activate = function()
{
    if(!this.isRogue()){
        this.nodeIdleTime = 0;
        componentActivate(componentRoot(this));
    }
};

Body.prototype.activateStatic = function(filter)
{
    assert(this.isStatic(), "Body.activateStatic() called on a non-static body.");

    for(var arb = this.arbiterList; arb; arb = arb.next(this)){
        if(!filter || filter == arb.a || filter == arb.b){
            (arb.body_a == this ? arb.body_b : arb.body_a).activate();
        }
    }

    // TODO should also activate joints!
};

Body.prototype.pushArbiter = function(arb)
{
    assertSoft((arb.body_a === this ? arb.thread_a_next : arb.thread_b_next) === null,
        "Internal Error: Dangling contact graph pointers detected. (A)");
    assertSoft((arb.body_a === this ? arb.thread_a_prev : arb.thread_b_prev) === null,
        "Internal Error: Dangling contact graph pointers detected. (B)");

    var next = this.arbiterList;
    assertSoft(next === null || (next.body_a === this ? next.thread_a_prev : next.thread_b_prev) === null,
        "Internal Error: Dangling contact graph pointers detected. (C)");

    if(arb.body_a === this){
        arb.thread_a_next = next;
    } else {
        arb.thread_b_next = next;
    }

    if(next){
        if (next.body_a === this){
            next.thread_a_prev = arb;
        } else {
            next.thread_b_prev = arb;
        }
    }
    this.arbiterList = arb;
};

var componentAdd = function(root, body){
    body.nodeRoot = root;

    if(body !== root){
        body.nodeNext = root.nodeNext;
        root.nodeNext = body;
    }
};

var floodFillComponent = function(root, body)
{
    // Rogue bodies cannot be put to sleep and prevent bodies they are touching from sleeping anyway.
    // Static bodies (which are a type of rogue body) are effectively sleeping all the time.
    if(!body.isRogue()){
        var other_root = componentRoot(body);
        if(other_root == null){
            componentAdd(root, body);
            for(var arb = body.arbiterList; arb; arb = arb.next(body)){
                floodFillComponent(root, (body == arb.body_a ? arb.body_b : arb.body_a));
            }
            for(var constraint = body.constraintList; constraint; constraint = constraint.next(body)){
                floodFillComponent(root, (body == constraint.a ? constraint.b : constraint.a));
            }
        } else {
            assertSoft(other_root === root, "Internal Error: Inconsistency detected in the contact graph.");
        }
    }
};

var componentActive = function(root, threshold)
{
    for(var body = root; body; body = body.nodeNext){
        if(body.nodeIdleTime < threshold) return true;
    }

    return false;
};

Space.prototype.processComponents = function(dt)
{
    var sleep = (this.sleepTimeThreshold !== Infinity);
    var bodies = this.bodies;

    // These checks can be removed at some stage (if DEBUG == undefined)
    for(var i=0; i<bodies.length; i++){
        var body = bodies[i];

        assertSoft(body.nodeNext === null, "Internal Error: Dangling next pointer detected in contact graph.");
        assertSoft(body.nodeRoot === null, "Internal Error: Dangling root pointer detected in contact graph.");
    }

    // Calculate the kinetic energy of all the bodies
    if(sleep){
        var dv = this.idleSpeedThreshold;
        var dvsq = (dv ? dv*dv : vlengthsq(this.gravity)*dt*dt);

        for(var i=0; i<bodies.length; i++){
            var body = bodies[i];

            // Need to deal with infinite mass objects
            var keThreshold = (dvsq ? body.m*dvsq : 0);
            body.nodeIdleTime = (body.kineticEnergy() > keThreshold ? 0 : body.nodeIdleTime + dt);
        }
    }

    // Awaken any sleeping bodies found and then push arbiters to the bodies' lists.
    var arbiters = this.arbiters;
    for(var i=0, count=arbiters.length; i<count; i++){
        var arb = arbiters[i];
        var a = arb.body_a, b = arb.body_b;

        if(sleep){
            if((b.isRogue() && !b.isStatic()) || a.isSleeping()) a.activate();
            if((a.isRogue() && !a.isStatic()) || b.isSleeping()) b.activate();
        }

        a.pushArbiter(arb);
        b.pushArbiter(arb);
    }

    if(sleep){
        // Bodies should be held active if connected by a joint to a non-static rouge body.
        var constraints = this.constraints;
        for(var i=0; i<constraints.length; i++){
            var constraint = constraints[i];
            var a = constraint.a, b = constraint.b;

            if(b.isRogue() && !b.isStatic()) a.activate();
            if(a.isRogue() && !a.isStatic()) b.activate();
        }

        // Generate components and deactivate sleeping ones
        for(var i=0; i<bodies.length;){
            var body = bodies[i];

            if(componentRoot(body) === null){
                // Body not in a component yet. Perform a DFS to flood fill mark
                // the component in the contact graph using this body as the root.
                floodFillComponent(body, body);

                // Check if the component should be put to sleep.
                if(!componentActive(body, this.sleepTimeThreshold)){
                    this.sleepingComponents.push(body);
                    for(var other = body; other; other = other.nodeNext){
                        this.deactivateBody(other);
                    }

                    // deactivateBody() removed the current body from the list.
                    // Skip incrementing the index counter.
                    continue;
                }
            }

            i++;

            // Only sleeping bodies retain their component node pointers.
            body.nodeRoot = null;
            body.nodeNext = null;
        }
    }
};

Body.prototype.sleep = function()
{
    this.sleepWithGroup(null);
};

Body.prototype.sleepWithGroup = function(group){
    assert(!this.isStatic() && !this.isRogue(), "Rogue and static bodies cannot be put to sleep.");

    var space = this.space;
    assert(space, "Cannot put a rogue body to sleep.");
    assert(!space.locked, "Bodies cannot be put to sleep during a query or a call to cpSpaceStep(). Put these calls into a post-step callback.");
    assert(group === null || group.isSleeping(), "Cannot use a non-sleeping body as a group identifier.");

    if(this.isSleeping()){
        assert(componentRoot(this) === componentRoot(group), "The body is already sleeping and it's group cannot be reassigned.");
        return;
    }

    for(var i = 0; i < this.shapeList.length; i++){
        this.shapeList[i].update(this.p, this.rot);
    }
    space.deactivateBody(this);

    if(group){
        var root = componentRoot(group);

        this.nodeRoot = root;
        this.nodeNext = root.nodeNext;
        this.nodeIdleTime = 0;

        root.nodeNext = this;
    } else {
        this.nodeRoot = this;
        this.nodeNext = null;
        this.nodeIdleTime = 0;

        space.sleepingComponents.push(this);
    }

    deleteObjFromList(space.bodies, this);
};

Space.prototype.activateShapesTouchingShape = function(shape){
    if(this.sleepTimeThreshold !== Infinity){
        this.shapeQuery(shape, function(shape, points) {
            shape.body.activate();
        });
    }
};

/* Copyright (c) 2007 Scott Lembcke
 *
 * Permission is hereby granted, free of charge, to any person obtaining a copy
 * of this software and associated documentation files (the "Software"), to deal
 * in the Software without restriction, including without limitation the rights
 * to use, copy, modify, merge, publish, distribute, sublicense, and/or sell
 * copies of the Software, and to permit persons to whom the Software is
 * furnished to do so, subject to the following conditions:
 *
 * The above copyright notice and this permission notice shall be included in
 * all copies or substantial portions of the Software.
 *
 * THE SOFTWARE IS PROVIDED "AS IS", WITHOUT WARRANTY OF ANY KIND, EXPRESS OR
 * IMPLIED, INCLUDING BUT NOT LIMITED TO THE WARRANTIES OF MERCHANTABILITY,
 * FITNESS FOR A PARTICULAR PURPOSE AND NONINFRINGEMENT. IN NO EVENT SHALL THE
 * AUTHORS OR COPYRIGHT HOLDERS BE LIABLE FOR ANY CLAIM, DAMAGES OR OTHER
 * LIABILITY, WHETHER IN AN ACTION OF CONTRACT, TORT OR OTHERWISE, ARISING FROM,
 * OUT OF OR IN CONNECTION WITH THE SOFTWARE OR THE USE OR OTHER DEALINGS IN THE
 * SOFTWARE.
 */

// Point query functions

/// Query the space at a point and call @c func for each shape found.
Space.prototype.pointQuery = function(point, layers, group, func)
{
    var helper = function(shape){
        if(
            !(shape.group && group === shape.group) && (layers & shape.layers) &&
            shape.pointQuery(point)
        ){
            func(shape);
        }
    };

    var bb = new BB(point.x, point.y, point.x, point.y);
    this.lock(); {
        this.activeShapes.query(bb, helper);
        this.staticShapes.query(bb, helper);
    } this.unlock(true);
};

/// Query the space at a point and return the first shape found. Returns null if no shapes were found.
Space.prototype.pointQueryFirst = function(point, layers, group)
{
    var outShape = null;
    this.pointQuery(point, layers, group, function(shape) {
        if(!shape.sensor) outShape = shape;
    });

    return outShape;
};

// Nearest point query functions

Space.prototype.nearestPointQuery = function(point, maxDistance, layers, group, func)
{
    var helper = function(shape){
        if(!(shape.group && group === shape.group) && (layers & shape.layers)){
            var info = shape.nearestPointQuery(point);

            if(info.d < maxDistance) func(shape, info.d, info.p);
        }
    };

    var bb = bbNewForCircle(point, maxDistance);

    this.lock(); {
        this.activeShapes.query(bb, helper);
        this.staticShapes.query(bb, helper);
    } this.unlock(true);
};

// Unlike the version in chipmunk, this returns a NearestPointQueryInfo object. Use its .shape
// property to get the actual shape.
Space.prototype.nearestPointQueryNearest = function(point, maxDistance, layers, group)
{
    var out;

    var helper = function(shape){
        if(!(shape.group && group === shape.group) && (layers & shape.layers) && !shape.sensor){
            var info = shape.nearestPointQuery(point);

            if(info.d < maxDistance && (!out || info.d < out.d)) out = info;
        }
    };

    var bb = bbNewForCircle(point, maxDistance);
    this.activeShapes.query(bb, helper);
    this.staticShapes.query(bb, helper);

    return out;
};

/// Perform a directed line segment query (like a raycast) against the space calling @c func for each shape intersected.
Space.prototype.segmentQuery = function(start, end, layers, group, func)
{
    var helper = function(shape){
        var info;

        if(
            !(shape.group && group === shape.group) && (layers & shape.layers) &&
            (info = shape.segmentQuery(start, end))
        ){
            func(shape, info.t, info.n);
        }

        return 1;
    };

    this.lock(); {
        this.staticShapes.segmentQuery(start, end, 1, helper);
        this.activeShapes.segmentQuery(start, end, 1, helper);
    } this.unlock(true);
};

/// Perform a directed line segment query (like a raycast) against the space and return the first shape hit.
/// Returns null if no shapes were hit.
Space.prototype.segmentQueryFirst = function(start, end, layers, group)
{
    var out = null;

    var helper = function(shape){
        var info;

        if(
            !(shape.group && group === shape.group) && (layers & shape.layers) &&
            !shape.sensor &&
            (info = shape.segmentQuery(start, end)) &&
            (out === null || info.t < out.t)
        ){
            out = info;
        }

        return out ? out.t : 1;
    };

    this.staticShapes.segmentQuery(start, end, 1, helper);
    this.activeShapes.segmentQuery(start, end, out ? out.t : 1, helper);

    return out;
};

/// Perform a fast rectangle query on the space calling @c func for each shape found.
/// Only the shape's bounding boxes are checked for overlap, not their full shape.
Space.prototype.bbQuery = function(bb, layers, group, func)
{
    var helper = function(shape){
        if(
            !(shape.group && group === shape.group) && (layers & shape.layers) &&
            bbIntersects2(bb, shape.bb_l, shape.bb_b, shape.bb_r, shape.bb_t)
        ){
            func(shape);
        }
    };

    this.lock(); {
        this.activeShapes.query(bb, helper);
        this.staticShapes.query(bb, helper);
    } this.unlock(true);
};

/// Query a space for any shapes overlapping the given shape and call @c func for each shape found.
Space.prototype.shapeQuery = function(shape, func)
{
    var body = shape.body;

    //var bb = (body ? shape.update(body.p, body.rot) : shape.bb);
    if(body){
        shape.update(body.p, body.rot);
    }
    var bb = new BB(shape.bb_l, shape.bb_b, shape.bb_r, shape.bb_t);

    //shapeQueryContext context = {func, data, false};
    var anyCollision = false;

    var helper = function(b){
        var a = shape;
        // Reject any of the simple cases
        if(
            (a.group && a.group === b.group) ||
            !(a.layers & b.layers) ||
            a === b
        ) return;

        var contacts;

        // Shape 'a' should have the lower shape type. (required by collideShapes() )
        if(a.collisionCode <= b.collisionCode){
            contacts = collideShapes(a, b);
        } else {
            contacts = collideShapes(b, a);
            for(var i=0; i<contacts.length; i++) contacts[i].n = vneg(contacts[i].n);
        }

        if(contacts.length){
            anyCollision = !(a.sensor || b.sensor);

            if(func){
                var set = new Array(contacts.length);
                for(var i=0; i<contacts.length; i++){
                    set[i] = new ContactPoint(contacts[i].p, contacts[i].n, contacts[i].dist);
                }

                func(b, set);
            }
        }
    };

    this.lock(); {
        this.activeShapes.query(bb, helper);
        this.staticShapes.query(bb, helper);
    } this.unlock(true);

    return anyCollision;
};

/* Copyright (c) 2007 Scott Lembcke
 *
 * Permission is hereby granted, free of charge, to any person obtaining a copy
 * of this software and associated documentation files (the "Software"), to deal
 * in the Software without restriction, including without limitation the rights
 * to use, copy, modify, merge, publish, distribute, sublicense, and/or sell
 * copies of the Software, and to permit persons to whom the Software is
 * furnished to do so, subject to the following conditions:
 *
 * The above copyright notice and this permission notice shall be included in
 * all copies or substantial portions of the Software.
 *
 * THE SOFTWARE IS PROVIDED "AS IS", WITHOUT WARRANTY OF ANY KIND, EXPRESS OR
 * IMPLIED, INCLUDING BUT NOT LIMITED TO THE WARRANTIES OF MERCHANTABILITY,
 * FITNESS FOR A PARTICULAR PURPOSE AND NONINFRINGEMENT. IN NO EVENT SHALL THE
 * AUTHORS OR COPYRIGHT HOLDERS BE LIABLE FOR ANY CLAIM, DAMAGES OR OTHER
 * LIABILITY, WHETHER IN AN ACTION OF CONTRACT, TORT OR OTHERWISE, ARISING FROM,
 * OUT OF OR IN CONNECTION WITH THE SOFTWARE OR THE USE OR OTHER DEALINGS IN THE
 * SOFTWARE.
 */

// **** Post Step Callback Functions

/// Schedule a post-step callback to be called when cpSpaceStep() finishes.
Space.prototype.addPostStepCallback = function(func)
{
    assertSoft(this.locked,
        "Adding a post-step callback when the space is not locked is unnecessary. " +
        "Post-step callbacks will not called until the end of the next call to cpSpaceStep() or the next query.");

    this.postStepCallbacks.push(func);
};

Space.prototype.runPostStepCallbacks = function()
{
    // Don't cache length because post step callbacks may add more post step callbacks
    // directly or indirectly.
    for(var i = 0; i < this.postStepCallbacks.length; i++){
        this.postStepCallbacks[i]();
    }
    this.postStepCallbacks = [];
};

// **** Locking Functions

Space.prototype.lock = function()
{
    this.locked++;
};

Space.prototype.unlock = function(runPostStep)
{
    this.locked--;
    assert(this.locked >= 0, "Internal Error: Space lock underflow.");

    if(this.locked === 0 && runPostStep){
        var waking = this.rousedBodies;
        for(var i=0; i<waking.length; i++){
            this.activateBody(waking[i]);
        }

        waking.length = 0;

        this.runPostStepCallbacks();
    }
};

// **** Contact Buffer Functions

/* josephg:
 *
 * This code might be faster in JS than just allocating objects each time - I'm
 * really not sure. If the contact buffer solution is used, there will also
 * need to be changes in cpCollision.js to fill a passed array instead of creating
 * new arrays each time.
 *
 * TODO: Benchmark me once chipmunk is working.
 */

/*
var ContactBuffer = function(stamp, splice)
{
    this.stamp = stamp;
    // Contact buffers are a circular linked list.
    this.next = splice ? splice.next : this;
    this.contacts = [];
};

Space.prototype.pushFreshContactBuffer = function()
{
    var stamp = this.stamp;

    var head = this.contactBuffersHead;

    if(!head){
        // No buffers have been allocated, make one
        this.contactBuffersHead = new ContactBuffer(stamp, null);
    } else if(stamp - head.next.stamp > this.collisionPersistence){
        // The tail buffer is available, rotate the ring
        var tail = head.next;
        tail.stamp = stamp;
        tail.contacts.length = 0;
        this.contactBuffersHead = tail;
    } else {
        // Allocate a new buffer and push it into the ring
        var buffer = new ContactBuffer(stamp, head);
        this.contactBuffersHead = head.next = buffer;
    }
};

cpContact *
cpContactBufferGetArray(cpSpace *space)
{
    if(space.contactBuffersHead.numContacts + CP_MAX_CONTACTS_PER_ARBITER > CP_CONTACTS_BUFFER_SIZE){
        // contact buffer could overflow on the next collision, push a fresh one.
        space.pushFreshContactBuffer();
    }

    cpContactBufferHeader *head = space.contactBuffersHead;
    return ((cpContactBuffer *)head)->contacts + head.numContacts;
}

void
cpSpacePushContacts(cpSpace *space, int count)
{
    cpAssertHard(count <= CP_MAX_CONTACTS_PER_ARBITER, "Internal Error: Contact buffer overflow!");
    space.contactBuffersHead.numContacts += count;
}

static void
cpSpacePopContacts(cpSpace *space, int count){
    space.contactBuffersHead.numContacts -= count;
}
*/

// **** Collision Detection Functions

/* Use this to re-enable object pools.
static void *
cpSpaceArbiterSetTrans(cpShape **shapes, cpSpace *space)
{
    if(space.pooledArbiters.num == 0){
        // arbiter pool is exhausted, make more
        int count = CP_BUFFER_BYTES/sizeof(cpArbiter);
        cpAssertHard(count, "Internal Error: Buffer size too small.");

        cpArbiter *buffer = (cpArbiter *)cpcalloc(1, CP_BUFFER_BYTES);
        cpArrayPush(space.allocatedBuffers, buffer);

        for(int i=0; i<count; i++) cpArrayPush(space.pooledArbiters, buffer + i);
    }

    return cpArbiterInit((cpArbiter *)cpArrayPop(space.pooledArbiters), shapes[0], shapes[1]);
}*/

// Callback from the spatial hash.
Space.prototype.makeCollideShapes = function()
{
    // It would be nicer to use .bind() or something, but this is faster.
    var space_ = this;
    return function(a, b){
        var space = space_;

        // Reject any of the simple cases
        if(
            // BBoxes must overlap
            //!bbIntersects(a.bb, b.bb)
            !(a.bb_l <= b.bb_r && b.bb_l <= a.bb_r && a.bb_b <= b.bb_t && b.bb_b <= a.bb_t)
            // Don't collide shapes attached to the same body.
            || a.body === b.body
            // Don't collide objects in the same non-zero group
            || (a.group && a.group === b.group)
            // Don't collide objects that don't share at least on layer.
            || !(a.layers & b.layers)
        ) return;

        var handler = space.lookupHandler(a.collision_type, b.collision_type);

        var sensor = a.sensor || b.sensor;
        if(sensor && handler === defaultCollisionHandler) return;

        // Shape 'a' should have the lower shape type. (required by cpCollideShapes() )
        if(a.collisionCode > b.collisionCode){
            var temp = a;
            a = b;
            b = temp;
        }

        // Narrow-phase collision detection.
        //cpContact *contacts = cpContactBufferGetArray(space);
        //int numContacts = cpCollideShapes(a, b, contacts);
        var contacts = collideShapes(a, b);
        if(contacts.length === 0) return; // Shapes are not colliding.
        //cpSpacePushContacts(space, numContacts);

        // Get an arbiter from space.arbiterSet for the two shapes.
        // This is where the persistant contact magic comes from.
        var arbHash = hashPair(a.hashid, b.hashid);
        var arb = space.cachedArbiters[arbHash];
        if (!arb){
            arb = space.cachedArbiters[arbHash] = new Arbiter(a, b);
        }

        arb.update(contacts, handler, a, b);

        // Call the begin function first if it's the first step
        if(arb.state == 'first coll' && !handler.begin(arb, space)){
            arb.ignore(); // permanently ignore the collision until separation
        }

        if(
            // Ignore the arbiter if it has been flagged
            (arb.state !== 'ignore') &&
            // Call preSolve
            handler.preSolve(arb, space) &&
            // Process, but don't add collisions for sensors.
            !sensor
        ){
            space.arbiters.push(arb);
        } else {
            //cpSpacePopContacts(space, numContacts);

            arb.contacts = null;

            // Normally arbiters are set as used after calling the post-solve callback.
            // However, post-solve callbacks are not called for sensors or arbiters rejected from pre-solve.
            if(arb.state !== 'ignore') arb.state = 'normal';
        }

        // Time stamp the arbiter so we know it was used recently.
        arb.stamp = space.stamp;
    };
};

// Hashset filter func to throw away old arbiters.
Space.prototype.arbiterSetFilter = function(arb)
{
    var ticks = this.stamp - arb.stamp;

    var a = arb.body_a, b = arb.body_b;

    // TODO should make an arbiter state for this so it doesn't require filtering arbiters for
    // dangling body pointers on body removal.
    // Preserve arbiters on sensors and rejected arbiters for sleeping objects.
    // This prevents errant separate callbacks from happenening.
    if(
        (a.isStatic() || a.isSleeping()) &&
        (b.isStatic() || b.isSleeping())
    ){
        return true;
    }

    // Arbiter was used last frame, but not this one
    if(ticks >= 1 && arb.state != 'cached'){
        arb.callSeparate(this);
        arb.state = 'cached';
    }

    if(ticks >= this.collisionPersistence){
        arb.contacts = null;

        //cpArrayPush(this.pooledArbiters, arb);
        return false;
    }

    return true;
};

// **** All Important cpSpaceStep() Function

var updateFunc = function(shape)
{
    var body = shape.body;
    shape.update(body.p, body.rot);
};

/// Step the space forward in time by @c dt.
Space.prototype.step = function(dt)
{
    // don't step if the timestep is 0!
    if(dt === 0) return;

    assert(vzero.x === 0 && vzero.y === 0, "vzero is invalid");

    this.stamp++;

    var prev_dt = this.curr_dt;
    this.curr_dt = dt;

    var i;
    var j;
    var hash;
    var bodies = this.bodies;
    var constraints = this.constraints;
    var arbiters = this.arbiters;

    // Reset and empty the arbiter lists.
    for(i=0; i<arbiters.length; i++){
        var arb = arbiters[i];
        arb.state = 'normal';

        // If both bodies are awake, unthread the arbiter from the contact graph.
        if(!arb.body_a.isSleeping() && !arb.body_b.isSleeping()){
            arb.unthread();
        }
    }
    arbiters.length = 0;

    this.lock(); {
        // Integrate positions
        for(i=0; i<bodies.length; i++){
            bodies[i].position_func(dt);
        }

        // Find colliding pairs.
        //this.pushFreshContactBuffer();
        this.activeShapes.each(updateFunc);
        this.activeShapes.reindexQuery(this.collideShapes);
    } this.unlock(false);

    // Rebuild the contact graph (and detect sleeping components if sleeping is enabled)
    this.processComponents(dt);

    this.lock(); {
        // Clear out old cached arbiters and call separate callbacks
        for(hash in this.cachedArbiters) {
            if(!this.arbiterSetFilter(this.cachedArbiters[hash])) {
                delete this.cachedArbiters[hash];
            }
        }

        // Prestep the arbiters and constraints.
        var slop = this.collisionSlop;
        var biasCoef = 1 - Math.pow(this.collisionBias, dt);
        for(i=0; i<arbiters.length; i++){
            arbiters[i].preStep(dt, slop, biasCoef);
        }

        for(i=0; i<constraints.length; i++){
            var constraint = constraints[i];

            constraint.preSolve(this);
            constraint.preStep(dt);
        }

        // Integrate velocities.
        var damping = Math.pow(this.damping, dt);
        var gravity = this.gravity;
        for(i=0; i<bodies.length; i++){
            bodies[i].velocity_func(gravity, damping, dt);
        }

        // Apply cached impulses
        var dt_coef = (prev_dt === 0 ? 0 : dt/prev_dt);
        for(i=0; i<arbiters.length; i++){
            arbiters[i].applyCachedImpulse(dt_coef);
        }

        for(i=0; i<constraints.length; i++){
            constraints[i].applyCachedImpulse(dt_coef);
        }

        // Run the impulse solver.
        for(i=0; i<this.iterations; i++){
            for(j=0; j<arbiters.length; j++){
                arbiters[j].applyImpulse();
            }

            for(j=0; j<constraints.length; j++){
                constraints[j].applyImpulse();
            }
        }

        // Run the constraint post-solve callbacks
        for(i=0; i<constraints.length; i++){
            constraints[i].postSolve(this);
        }

        // run the post-solve callbacks
        for(i=0; i<arbiters.length; i++){
            arbiters[i].handler.postSolve(arbiters[i], this);
        }
    } this.unlock(true);
};

/* Copyright (c) 2007 Scott Lembcke
 *
 * Permission is hereby granted, free of charge, to any person obtaining a copy
 * of this software and associated documentation files (the "Software"), to deal
 * in the Software without restriction, including without limitation the rights
 * to use, copy, modify, merge, publish, distribute, sublicense, and/or sell
 * copies of the Software, and to permit persons to whom the Software is
 * furnished to do so, subject to the following conditions:
 *
 * The above copyright notice and this permission notice shall be included in
 * all copies or substantial portions of the Software.
 *
 * THE SOFTWARE IS PROVIDED "AS IS", WITHOUT WARRANTY OF ANY KIND, EXPRESS OR
 * IMPLIED, INCLUDING BUT NOT LIMITED TO THE WARRANTIES OF MERCHANTABILITY,
 * FITNESS FOR A PARTICULAR PURPOSE AND NONINFRINGEMENT. IN NO EVENT SHALL THE
 * AUTHORS OR COPYRIGHT HOLDERS BE LIABLE FOR ANY CLAIM, DAMAGES OR OTHER
 * LIABILITY, WHETHER IN AN ACTION OF CONTRACT, TORT OR OTHERWISE, ARISING FROM,
 * OUT OF OR IN CONNECTION WITH THE SOFTWARE OR THE USE OR OTHER DEALINGS IN THE
 * SOFTWARE.
 */

// These are utility routines to use when creating custom constraints.
// I'm not sure if this should be part of the private API or not.
// I should probably clean up the naming conventions if it is...

//#define J_MAX(constraint, dt) (((cpConstraint *)constraint)->maxForce*(dt))

// a and b are bodies.
var relative_velocity = function(a, b, r1, r2){
    //var v1_sum = vadd(a.v, vmult(vperp(r1), a.w));
    var v1_sumx = a.vx + (-r1.y) * a.w;
    var v1_sumy = a.vy + ( r1.x) * a.w;

    //var v2_sum = vadd(b.v, vmult(vperp(r2), b.w));
    var v2_sumx = b.vx + (-r2.y) * b.w;
    var v2_sumy = b.vy + ( r2.x) * b.w;

//  return vsub(v2_sum, v1_sum);
    return new Vect(v2_sumx - v1_sumx, v2_sumy - v1_sumy);
};

var normal_relative_velocity = function(a, b, r1, r2, n){
    //return vdot(relative_velocity(a, b, r1, r2), n);
    var v1_sumx = a.vx + (-r1.y) * a.w;
    var v1_sumy = a.vy + ( r1.x) * a.w;
    var v2_sumx = b.vx + (-r2.y) * b.w;
    var v2_sumy = b.vy + ( r2.x) * b.w;

    return vdot2(v2_sumx - v1_sumx, v2_sumy - v1_sumy, n.x, n.y);
};

/*
var apply_impulse = function(body, j, r){
    body.v = vadd(body.v, vmult(j, body.m_inv));
    body.w += body.i_inv*vcross(r, j);
};

var apply_impulses = function(a, b, r1, r2, j)
{
    apply_impulse(a, vneg(j), r1);
    apply_impulse(b, j, r2);
};
*/

var apply_impulse = function(body, jx, jy, r){
//  body.v = body.v.add(vmult(j, body.m_inv));
    body.vx += jx * body.m_inv;
    body.vy += jy * body.m_inv;
//  body.w += body.i_inv*vcross(r, j);
    body.w += body.i_inv*(r.x*jy - r.y*jx);
};

var apply_impulses = function(a, b, r1, r2, jx, jy)
{
    apply_impulse(a, -jx, -jy, r1);
    apply_impulse(b, jx, jy, r2);
};

var apply_bias_impulse = function(body, jx, jy, r)
{
    //body.v_bias = vadd(body.v_bias, vmult(j, body.m_inv));
    body.v_biasx += jx * body.m_inv;
    body.v_biasy += jy * body.m_inv;
    body.w_bias += body.i_inv*vcross2(r.x, r.y, jx, jy);
};

/*
var apply_bias_impulses = function(a, b, r1, r2, j)
{
    apply_bias_impulse(a, vneg(j), r1);
    apply_bias_impulse(b, j, r2);
};*/

var k_scalar_body = function(body, r, n)
{
    var rcn = vcross(r, n);
    return body.m_inv + body.i_inv*rcn*rcn;
};

var k_scalar = function(a, b, r1, r2, n)
{
    var value = k_scalar_body(a, r1, n) + k_scalar_body(b, r2, n);
    assertSoft(value !== 0, "Unsolvable collision or constraint.");

    return value;
};

// k1 and k2 are modified by the function to contain the outputs.
var k_tensor = function(a, b, r1, r2, k1, k2)
{
    // calculate mass matrix
    // If I wasn't lazy and wrote a proper matrix class, this wouldn't be so gross...
    var k11, k12, k21, k22;
    var m_sum = a.m_inv + b.m_inv;

    // start with I*m_sum
    k11 = m_sum; k12 = 0;
    k21 = 0;     k22 = m_sum;

    // add the influence from r1
    var a_i_inv = a.i_inv;
    var r1xsq =  r1.x * r1.x * a_i_inv;
    var r1ysq =  r1.y * r1.y * a_i_inv;
    var r1nxy = -r1.x * r1.y * a_i_inv;
    k11 += r1ysq; k12 += r1nxy;
    k21 += r1nxy; k22 += r1xsq;

    // add the influnce from r2
    var b_i_inv = b.i_inv;
    var r2xsq =  r2.x * r2.x * b_i_inv;
    var r2ysq =  r2.y * r2.y * b_i_inv;
    var r2nxy = -r2.x * r2.y * b_i_inv;
    k11 += r2ysq; k12 += r2nxy;
    k21 += r2nxy; k22 += r2xsq;

    // invert
    var determinant = k11*k22 - k12*k21;
    assertSoft(determinant !== 0, "Unsolvable constraint.");

    var det_inv = 1/determinant;

    k1.x =  k22*det_inv; k1.y = -k12*det_inv;
    k2.x = -k21*det_inv; k2.y =  k11*det_inv;
};

var mult_k = function(vr, k1, k2)
{
    return new Vect(vdot(vr, k1), vdot(vr, k2));
};

var bias_coef = function(errorBias, dt)
{
    return 1 - Math.pow(errorBias, dt);
};

/* Copyright (c) 2007 Scott Lembcke
 *
 * Permission is hereby granted, free of charge, to any person obtaining a copy
 * of this software and associated documentation files (the "Software"), to deal
 * in the Software without restriction, including without limitation the rights
 * to use, copy, modify, merge, publish, distribute, sublicense, and/or sell
 * copies of the Software, and to permit persons to whom the Software is
 * furnished to do so, subject to the following conditions:
 *
 * The above copyright notice and this permission notice shall be included in
 * all copies or substantial portions of the Software.
 *
 * THE SOFTWARE IS PROVIDED "AS IS", WITHOUT WARRANTY OF ANY KIND, EXPRESS OR
 * IMPLIED, INCLUDING BUT NOT LIMITED TO THE WARRANTIES OF MERCHANTABILITY,
 * FITNESS FOR A PARTICULAR PURPOSE AND NONINFRINGEMENT. IN NO EVENT SHALL THE
 * AUTHORS OR COPYRIGHT HOLDERS BE LIABLE FOR ANY CLAIM, DAMAGES OR OTHER
 * LIABILITY, WHETHER IN AN ACTION OF CONTRACT, TORT OR OTHERWISE, ARISING FROM,
 * OUT OF OR IN CONNECTION WITH THE SOFTWARE OR THE USE OR OTHER DEALINGS IN THE
 * SOFTWARE.
 */

// TODO: Comment me!

// a and b are bodies that the constraint applies to.
var Constraint = cp.Constraint = function(a, b)
{
    /// The first body connected to this constraint.
    this.a = a;
    /// The second body connected to this constraint.
    this.b = b;

    this.space = null;

    this.next_a = null;
    this.next_b = null;

    /// The maximum force that this constraint is allowed to use.
    this.maxForce = Infinity;
    /// The rate at which joint error is corrected.
    /// Defaults to pow(1 - 0.1, 60) meaning that it will
    /// correct 10% of the error every 1/60th of a second.
    this.errorBias = Math.pow(1 - 0.1, 60);
    /// The maximum rate at which joint error is corrected.
    this.maxBias = Infinity;
};

Constraint.prototype.activateBodies = function()
{
    if(this.a) this.a.activate();
    if(this.b) this.b.activate();
};

/// These methods are overridden by the constraint itself.
Constraint.prototype.preStep = function(dt) {};
Constraint.prototype.applyCachedImpulse = function(dt_coef) {};
Constraint.prototype.applyImpulse = function() {};
Constraint.prototype.getImpulse = function() { return 0; };

/// Function called before the solver runs. This can be overridden by the user
/// to customize the constraint.
/// Animate your joint anchors, update your motor torque, etc.
Constraint.prototype.preSolve = function(space) {};

/// Function called after the solver runs. This can be overridden by the user
/// to customize the constraint.
/// Use the applied impulse to perform effects like breakable joints.
Constraint.prototype.postSolve = function(space) {};

Constraint.prototype.next = function(body)
{
    return (this.a === body ? this.next_a : this.next_b);
};

/* Copyright (c) 2007 Scott Lembcke
 *
 * Permission is hereby granted, free of charge, to any person obtaining a copy
 * of this software and associated documentation files (the "Software"), to deal
 * in the Software without restriction, including without limitation the rights
 * to use, copy, modify, merge, publish, distribute, sublicense, and/or sell
 * copies of the Software, and to permit persons to whom the Software is
 * furnished to do so, subject to the following conditions:
 *
 * The above copyright notice and this permission notice shall be included in
 * all copies or substantial portions of the Software.
 *
 * THE SOFTWARE IS PROVIDED "AS IS", WITHOUT WARRANTY OF ANY KIND, EXPRESS OR
 * IMPLIED, INCLUDING BUT NOT LIMITED TO THE WARRANTIES OF MERCHANTABILITY,
 * FITNESS FOR A PARTICULAR PURPOSE AND NONINFRINGEMENT. IN NO EVENT SHALL THE
 * AUTHORS OR COPYRIGHT HOLDERS BE LIABLE FOR ANY CLAIM, DAMAGES OR OTHER
 * LIABILITY, WHETHER IN AN ACTION OF CONTRACT, TORT OR OTHERWISE, ARISING FROM,
 * OUT OF OR IN CONNECTION WITH THE SOFTWARE OR THE USE OR OTHER DEALINGS IN THE
 * SOFTWARE.
 */

var PinJoint = cp.PinJoint = function(a, b, anchr1, anchr2)
{
    Constraint.call(this, a, b);

    this.anchr1 = anchr1;
    this.anchr2 = anchr2;

    // STATIC_BODY_CHECK
    var p1 = (a ? vadd(a.p, vrotate(anchr1, a.rot)) : anchr1);
    var p2 = (b ? vadd(b.p, vrotate(anchr2, b.rot)) : anchr2);
    this.dist = vlength(vsub(p2, p1));

    assertSoft(this.dist > 0, "You created a 0 length pin joint. A pivot joint will be much more stable.");

    this.r1 = this.r2 = null;
    this.n = null;
    this.nMass = 0;

    this.jnAcc = this.jnMax = 0;
    this.bias = 0;
};

PinJoint.prototype = Object.create(Constraint.prototype);

PinJoint.prototype.preStep = function(dt)
{
    var a = this.a;
    var b = this.b;

    this.r1 = vrotate(this.anchr1, a.rot);
    this.r2 = vrotate(this.anchr2, b.rot);

    var delta = vsub(vadd(b.p, this.r2), vadd(a.p, this.r1));
    var dist = vlength(delta);
    this.n = vmult(delta, 1/(dist ? dist : Infinity));

    // calculate mass normal
    this.nMass = 1/k_scalar(a, b, this.r1, this.r2, this.n);

    // calculate bias velocity
    var maxBias = this.maxBias;
    this.bias = clamp(-bias_coef(this.errorBias, dt)*(dist - this.dist)/dt, -maxBias, maxBias);

    // compute max impulse
    this.jnMax = this.maxForce * dt;
};

PinJoint.prototype.applyCachedImpulse = function(dt_coef)
{
    var j = vmult(this.n, this.jnAcc*dt_coef);
    apply_impulses(this.a, this.b, this.r1, this.r2, j.x, j.y);
};

PinJoint.prototype.applyImpulse = function()
{
    var a = this.a;
    var b = this.b;
    var n = this.n;

    // compute relative velocity
    var vrn = normal_relative_velocity(a, b, this.r1, this.r2, n);

    // compute normal impulse
    var jn = (this.bias - vrn)*this.nMass;
    var jnOld = this.jnAcc;
    this.jnAcc = clamp(jnOld + jn, -this.jnMax, this.jnMax);
    jn = this.jnAcc - jnOld;

    // apply impulse
    apply_impulses(a, b, this.r1, this.r2, n.x*jn, n.y*jn);
};

PinJoint.prototype.getImpulse = function()
{
    return Math.abs(this.jnAcc);
};

/* Copyright (c) 2007 Scott Lembcke
 *
 * Permission is hereby granted, free of charge, to any person obtaining a copy
 * of this software and associated documentation files (the "Software"), to deal
 * in the Software without restriction, including without limitation the rights
 * to use, copy, modify, merge, publish, distribute, sublicense, and/or sell
 * copies of the Software, and to permit persons to whom the Software is
 * furnished to do so, subject to the following conditions:
 *
 * The above copyright notice and this permission notice shall be included in
 * all copies or substantial portions of the Software.
 *
 * THE SOFTWARE IS PROVIDED "AS IS", WITHOUT WARRANTY OF ANY KIND, EXPRESS OR
 * IMPLIED, INCLUDING BUT NOT LIMITED TO THE WARRANTIES OF MERCHANTABILITY,
 * FITNESS FOR A PARTICULAR PURPOSE AND NONINFRINGEMENT. IN NO EVENT SHALL THE
 * AUTHORS OR COPYRIGHT HOLDERS BE LIABLE FOR ANY CLAIM, DAMAGES OR OTHER
 * LIABILITY, WHETHER IN AN ACTION OF CONTRACT, TORT OR OTHERWISE, ARISING FROM,
 * OUT OF OR IN CONNECTION WITH THE SOFTWARE OR THE USE OR OTHER DEALINGS IN THE
 * SOFTWARE.
 */

var SlideJoint = cp.SlideJoint = function(a, b, anchr1, anchr2, min, max)
{
    Constraint.call(this, a, b);

    this.anchr1 = anchr1;
    this.anchr2 = anchr2;
    this.min = min;
    this.max = max;

    this.r1 = this.r2 = this.n = null;
    this.nMass = 0;

    this.jnAcc = this.jnMax = 0;
    this.bias = 0;
};

SlideJoint.prototype = Object.create(Constraint.prototype);

SlideJoint.prototype.preStep = function(dt)
{
    var a = this.a;
    var b = this.b;

    this.r1 = vrotate(this.anchr1, a.rot);
    this.r2 = vrotate(this.anchr2, b.rot);

    var delta = vsub(vadd(b.p, this.r2), vadd(a.p, this.r1));
    var dist = vlength(delta);
    var pdist = 0;
    if(dist > this.max) {
        pdist = dist - this.max;
        this.n = vnormalize_safe(delta);
    } else if(dist < this.min) {
        pdist = this.min - dist;
        this.n = vneg(vnormalize_safe(delta));
    } else {
        this.n = vzero;
        this.jnAcc = 0;
    }

    // calculate mass normal
    this.nMass = 1/k_scalar(a, b, this.r1, this.r2, this.n);

    // calculate bias velocity
    var maxBias = this.maxBias;
    this.bias = clamp(-bias_coef(this.errorBias, dt)*pdist/dt, -maxBias, maxBias);

    // compute max impulse
    this.jnMax = this.maxForce * dt;
};

SlideJoint.prototype.applyCachedImpulse = function(dt_coef)
{
    var jn = this.jnAcc * dt_coef;
    apply_impulses(this.a, this.b, this.r1, this.r2, this.n.x * jn, this.n.y * jn);
};

SlideJoint.prototype.applyImpulse = function()
{
    if(this.n.x === 0 && this.n.y === 0) return;  // early exit

    var a = this.a;
    var b = this.b;

    var n = this.n;
    var r1 = this.r1;
    var r2 = this.r2;

    // compute relative velocity
    var vr = relative_velocity(a, b, r1, r2);
    var vrn = vdot(vr, n);

    // compute normal impulse
    var jn = (this.bias - vrn)*this.nMass;
    var jnOld = this.jnAcc;
    this.jnAcc = clamp(jnOld + jn, -this.jnMax, 0);
    jn = this.jnAcc - jnOld;

    // apply impulse
    apply_impulses(a, b, this.r1, this.r2, n.x * jn, n.y * jn);
};

SlideJoint.prototype.getImpulse = function()
{
    return Math.abs(this.jnAcc);
};

/* Copyright (c) 2007 Scott Lembcke
 *
 * Permission is hereby granted, free of charge, to any person obtaining a copy
 * of this software and associated documentation files (the "Software"), to deal
 * in the Software without restriction, including without limitation the rights
 * to use, copy, modify, merge, publish, distribute, sublicense, and/or sell
 * copies of the Software, and to permit persons to whom the Software is
 * furnished to do so, subject to the following conditions:
 *
 * The above copyright notice and this permission notice shall be included in
 * all copies or substantial portions of the Software.
 *
 * THE SOFTWARE IS PROVIDED "AS IS", WITHOUT WARRANTY OF ANY KIND, EXPRESS OR
 * IMPLIED, INCLUDING BUT NOT LIMITED TO THE WARRANTIES OF MERCHANTABILITY,
 * FITNESS FOR A PARTICULAR PURPOSE AND NONINFRINGEMENT. IN NO EVENT SHALL THE
 * AUTHORS OR COPYRIGHT HOLDERS BE LIABLE FOR ANY CLAIM, DAMAGES OR OTHER
 * LIABILITY, WHETHER IN AN ACTION OF CONTRACT, TORT OR OTHERWISE, ARISING FROM,
 * OUT OF OR IN CONNECTION WITH THE SOFTWARE OR THE USE OR OTHER DEALINGS IN THE
 * SOFTWARE.
 */

// Pivot joints can also be created with (a, b, pivot);
var PivotJoint = cp.PivotJoint = function(a, b, anchr1, anchr2)
{
    Constraint.call(this, a, b);

    if(typeof anchr2 === 'undefined') {
        var pivot = anchr1;

        anchr1 = (a ? a.world2Local(pivot) : pivot);
        anchr2 = (b ? b.world2Local(pivot) : pivot);
    }

    this.anchr1 = anchr1;
    this.anchr2 = anchr2;

    this.r1 = this.r2 = vzero;

    this.k1 = new Vect(0,0); this.k2 = new Vect(0,0);

    this.jAcc = vzero;

    this.jMaxLen = 0;
    this.bias = vzero;
};

PivotJoint.prototype = Object.create(Constraint.prototype);

PivotJoint.prototype.preStep = function(dt)
{
    var a = this.a;
    var b = this.b;

    this.r1 = vrotate(this.anchr1, a.rot);
    this.r2 = vrotate(this.anchr2, b.rot);

    // Calculate mass tensor. Result is stored into this.k1 & this.k2.
    k_tensor(a, b, this.r1, this.r2, this.k1, this.k2);

    // compute max impulse
    this.jMaxLen = this.maxForce * dt;

    // calculate bias velocity
    var delta = vsub(vadd(b.p, this.r2), vadd(a.p, this.r1));
    this.bias = vclamp(vmult(delta, -bias_coef(this.errorBias, dt)/dt), this.maxBias);
};

PivotJoint.prototype.applyCachedImpulse = function(dt_coef)
{
    apply_impulses(this.a, this.b, this.r1, this.r2, this.jAcc.x * dt_coef, this.jAcc.y * dt_coef);
};

PivotJoint.prototype.applyImpulse = function()
{
    var a = this.a;
    var b = this.b;

    var r1 = this.r1;
    var r2 = this.r2;

    // compute relative velocity
    var vr = relative_velocity(a, b, r1, r2);

    // compute normal impulse
    var j = mult_k(vsub(this.bias, vr), this.k1, this.k2);
    var jOld = this.jAcc;
    this.jAcc = vclamp(vadd(this.jAcc, j), this.jMaxLen);

    // apply impulse
    apply_impulses(a, b, this.r1, this.r2, this.jAcc.x - jOld.x, this.jAcc.y - jOld.y);
};

PivotJoint.prototype.getImpulse = function()
{
    return vlength(this.jAcc);
};

/* Copyright (c) 2007 Scott Lembcke
 *
 * Permission is hereby granted, free of charge, to any person obtaining a copy
 * of this software and associated documentation files (the "Software"), to deal
 * in the Software without restriction, including without limitation the rights
 * to use, copy, modify, merge, publish, distribute, sublicense, and/or sell
 * copies of the Software, and to permit persons to whom the Software is
 * furnished to do so, subject to the following conditions:
 *
 * The above copyright notice and this permission notice shall be included in
 * all copies or substantial portions of the Software.
 *
 * THE SOFTWARE IS PROVIDED "AS IS", WITHOUT WARRANTY OF ANY KIND, EXPRESS OR
 * IMPLIED, INCLUDING BUT NOT LIMITED TO THE WARRANTIES OF MERCHANTABILITY,
 * FITNESS FOR A PARTICULAR PURPOSE AND NONINFRINGEMENT. IN NO EVENT SHALL THE
 * AUTHORS OR COPYRIGHT HOLDERS BE LIABLE FOR ANY CLAIM, DAMAGES OR OTHER
 * LIABILITY, WHETHER IN AN ACTION OF CONTRACT, TORT OR OTHERWISE, ARISING FROM,
 * OUT OF OR IN CONNECTION WITH THE SOFTWARE OR THE USE OR OTHER DEALINGS IN THE
 * SOFTWARE.
 */

var GrooveJoint = cp.GrooveJoint = function(a, b, groove_a, groove_b, anchr2)
{
    Constraint.call(this, a, b);

    this.grv_a = groove_a;
    this.grv_b = groove_b;
    this.grv_n = vperp(vnormalize(vsub(groove_b, groove_a)));
    this.anchr2 = anchr2;

    this.grv_tn = null;
    this.clamp = 0;
    this.r1 = this.r2 = null;

    this.k1 = new Vect(0,0);
    this.k2 = new Vect(0,0);

    this.jAcc = vzero;
    this.jMaxLen = 0;
    this.bias = null;
};

GrooveJoint.prototype = Object.create(Constraint.prototype);

GrooveJoint.prototype.preStep = function(dt)
{
    var a = this.a;
    var b = this.b;

    // calculate endpoints in worldspace
    var ta = a.local2World(this.grv_a);
    var tb = a.local2World(this.grv_b);

    // calculate axis
    var n = vrotate(this.grv_n, a.rot);
    var d = vdot(ta, n);

    this.grv_tn = n;
    this.r2 = vrotate(this.anchr2, b.rot);

    // calculate tangential distance along the axis of r2
    var td = vcross(vadd(b.p, this.r2), n);
    // calculate clamping factor and r2
    if(td <= vcross(ta, n)){
        this.clamp = 1;
        this.r1 = vsub(ta, a.p);
    } else if(td >= vcross(tb, n)){
        this.clamp = -1;
        this.r1 = vsub(tb, a.p);
    } else {
        this.clamp = 0;
        this.r1 = vsub(vadd(vmult(vperp(n), -td), vmult(n, d)), a.p);
    }

    // Calculate mass tensor
    k_tensor(a, b, this.r1, this.r2, this.k1, this.k2);

    // compute max impulse
    this.jMaxLen = this.maxForce * dt;

    // calculate bias velocity
    var delta = vsub(vadd(b.p, this.r2), vadd(a.p, this.r1));
    this.bias = vclamp(vmult(delta, -bias_coef(this.errorBias, dt)/dt), this.maxBias);
};

GrooveJoint.prototype.applyCachedImpulse = function(dt_coef)
{
    apply_impulses(this.a, this.b, this.r1, this.r2, this.jAcc.x * dt_coef, this.jAcc.y * dt_coef);
};

GrooveJoint.prototype.grooveConstrain = function(j){
    var n = this.grv_tn;
    var jClamp = (this.clamp*vcross(j, n) > 0) ? j : vproject(j, n);
    return vclamp(jClamp, this.jMaxLen);
};

GrooveJoint.prototype.applyImpulse = function()
{
    var a = this.a;
    var b = this.b;

    var r1 = this.r1;
    var r2 = this.r2;

    // compute impulse
    var vr = relative_velocity(a, b, r1, r2);

    var j = mult_k(vsub(this.bias, vr), this.k1, this.k2);
    var jOld = this.jAcc;
    this.jAcc = this.grooveConstrain(vadd(jOld, j));

    // apply impulse
    apply_impulses(a, b, this.r1, this.r2, this.jAcc.x - jOld.x, this.jAcc.y - jOld.y);
};

GrooveJoint.prototype.getImpulse = function()
{
    return vlength(this.jAcc);
};

GrooveJoint.prototype.setGrooveA = function(value)
{
    this.grv_a = value;
    this.grv_n = vperp(vnormalize(vsub(this.grv_b, value)));

    this.activateBodies();
};

GrooveJoint.prototype.setGrooveB = function(value)
{
    this.grv_b = value;
    this.grv_n = vperp(vnormalize(vsub(value, this.grv_a)));

    this.activateBodies();
};

/* Copyright (c) 2007 Scott Lembcke
 *
 * Permission is hereby granted, free of charge, to any person obtaining a copy
 * of this software and associated documentation files (the "Software"), to deal
 * in the Software without restriction, including without limitation the rights
 * to use, copy, modify, merge, publish, distribute, sublicense, and/or sell
 * copies of the Software, and to permit persons to whom the Software is
 * furnished to do so, subject to the following conditions:
 *
 * The above copyright notice and this permission notice shall be included in
 * all copies or substantial portions of the Software.
 *
 * THE SOFTWARE IS PROVIDED "AS IS", WITHOUT WARRANTY OF ANY KIND, EXPRESS OR
 * IMPLIED, INCLUDING BUT NOT LIMITED TO THE WARRANTIES OF MERCHANTABILITY,
 * FITNESS FOR A PARTICULAR PURPOSE AND NONINFRINGEMENT. IN NO EVENT SHALL THE
 * AUTHORS OR COPYRIGHT HOLDERS BE LIABLE FOR ANY CLAIM, DAMAGES OR OTHER
 * LIABILITY, WHETHER IN AN ACTION OF CONTRACT, TORT OR OTHERWISE, ARISING FROM,
 * OUT OF OR IN CONNECTION WITH THE SOFTWARE OR THE USE OR OTHER DEALINGS IN THE
 * SOFTWARE.
 */

var defaultSpringForce = function(spring, dist){
    return (spring.restLength - dist)*spring.stiffness;
};

var DampedSpring = cp.DampedSpring = function(a, b, anchr1, anchr2, restLength, stiffness, damping)
{
    Constraint.call(this, a, b);

    this.anchr1 = anchr1;
    this.anchr2 = anchr2;

    this.restLength = restLength;
    this.stiffness = stiffness;
    this.damping = damping;
    this.springForceFunc = defaultSpringForce;

    this.target_vrn = this.v_coef = 0;

    this.r1 = this.r2 = null;
    this.nMass = 0;
    this.n = null;
};

DampedSpring.prototype = Object.create(Constraint.prototype);

DampedSpring.prototype.preStep = function(dt)
{
    var a = this.a;
    var b = this.b;

    this.r1 = vrotate(this.anchr1, a.rot);
    this.r2 = vrotate(this.anchr2, b.rot);

    var delta = vsub(vadd(b.p, this.r2), vadd(a.p, this.r1));
    var dist = vlength(delta);
    this.n = vmult(delta, 1/(dist ? dist : Infinity));

    var k = k_scalar(a, b, this.r1, this.r2, this.n);
    assertSoft(k !== 0, "Unsolvable this.");
    this.nMass = 1/k;

    this.target_vrn = 0;
    this.v_coef = 1 - Math.exp(-this.damping*dt*k);

    // apply this force
    var f_spring = this.springForceFunc(this, dist);
    apply_impulses(a, b, this.r1, this.r2, this.n.x * f_spring * dt, this.n.y * f_spring * dt);
};

DampedSpring.prototype.applyCachedImpulse = function(dt_coef){};

DampedSpring.prototype.applyImpulse = function()
{
    var a = this.a;
    var b = this.b;

    var n = this.n;
    var r1 = this.r1;
    var r2 = this.r2;

    // compute relative velocity
    var vrn = normal_relative_velocity(a, b, r1, r2, n);

    // compute velocity loss from drag
    var v_damp = (this.target_vrn - vrn)*this.v_coef;
    this.target_vrn = vrn + v_damp;

    v_damp *= this.nMass;
    apply_impulses(a, b, this.r1, this.r2, this.n.x * v_damp, this.n.y * v_damp);
};

DampedSpring.prototype.getImpulse = function()
{
    return 0;
};

/* Copyright (c) 2007 Scott Lembcke
 *
 * Permission is hereby granted, free of charge, to any person obtaining a copy
 * of this software and associated documentation files (the "Software"), to deal
 * in the Software without restriction, including without limitation the rights
 * to use, copy, modify, merge, publish, distribute, sublicense, and/or sell
 * copies of the Software, and to permit persons to whom the Software is
 * furnished to do so, subject to the following conditions:
 *
 * The above copyright notice and this permission notice shall be included in
 * all copies or substantial portions of the Software.
 *
 * THE SOFTWARE IS PROVIDED "AS IS", WITHOUT WARRANTY OF ANY KIND, EXPRESS OR
 * IMPLIED, INCLUDING BUT NOT LIMITED TO THE WARRANTIES OF MERCHANTABILITY,
 * FITNESS FOR A PARTICULAR PURPOSE AND NONINFRINGEMENT. IN NO EVENT SHALL THE
 * AUTHORS OR COPYRIGHT HOLDERS BE LIABLE FOR ANY CLAIM, DAMAGES OR OTHER
 * LIABILITY, WHETHER IN AN ACTION OF CONTRACT, TORT OR OTHERWISE, ARISING FROM,
 * OUT OF OR IN CONNECTION WITH THE SOFTWARE OR THE USE OR OTHER DEALINGS IN THE
 * SOFTWARE.
 */

var defaultSpringTorque = function(spring, relativeAngle){
    return (relativeAngle - spring.restAngle)*spring.stiffness;
}

var DampedRotarySpring = cp.DampedRotarySpring = function(a, b, restAngle, stiffness, damping)
{
    Constraint.call(this, a, b);

    this.restAngle = restAngle;
    this.stiffness = stiffness;
    this.damping = damping;
    this.springTorqueFunc = defaultSpringTorque;

    this.target_wrn = 0;
    this.w_coef = 0;
    this.iSum = 0;
};

DampedRotarySpring.prototype = Object.create(Constraint.prototype);

DampedRotarySpring.prototype.preStep = function(dt)
{
    var a = this.a;
    var b = this.b;

    var moment = a.i_inv + b.i_inv;
    assertSoft(moment !== 0, "Unsolvable spring.");
    this.iSum = 1/moment;

    this.w_coef = 1 - Math.exp(-this.damping*dt*moment);
    this.target_wrn = 0;

    // apply this torque
    var j_spring = this.springTorqueFunc(this, a.a - b.a)*dt;
    a.w -= j_spring*a.i_inv;
    b.w += j_spring*b.i_inv;
};

// DampedRotarySpring.prototype.applyCachedImpulse = function(dt_coef){};

DampedRotarySpring.prototype.applyImpulse = function()
{
    var a = this.a;
    var b = this.b;

    // compute relative velocity
    var wrn = a.w - b.w;//normal_relative_velocity(a, b, r1, r2, n) - this.target_vrn;

    // compute velocity loss from drag
    // not 100% certain spring is derived correctly, though it makes sense
    var w_damp = (this.target_wrn - wrn)*this.w_coef;
    this.target_wrn = wrn + w_damp;

    //apply_impulses(a, b, this.r1, this.r2, vmult(this.n, v_damp*this.nMass));
    var j_damp = w_damp*this.iSum;
    a.w += j_damp*a.i_inv;
    b.w -= j_damp*b.i_inv;
};

// DampedRotarySpring.prototype.getImpulse = function(){ return 0; };

/* Copyright (c) 2007 Scott Lembcke
 *
 * Permission is hereby granted, free of charge, to any person obtaining a copy
 * of this software and associated documentation files (the "Software"), to deal
 * in the Software without restriction, including without limitation the rights
 * to use, copy, modify, merge, publish, distribute, sublicense, and/or sell
 * copies of the Software, and to permit persons to whom the Software is
 * furnished to do so, subject to the following conditions:
 *
 * The above copyright notice and this permission notice shall be included in
 * all copies or substantial portions of the Software.
 *
 * THE SOFTWARE IS PROVIDED "AS IS", WITHOUT WARRANTY OF ANY KIND, EXPRESS OR
 * IMPLIED, INCLUDING BUT NOT LIMITED TO THE WARRANTIES OF MERCHANTABILITY,
 * FITNESS FOR A PARTICULAR PURPOSE AND NONINFRINGEMENT. IN NO EVENT SHALL THE
 * AUTHORS OR COPYRIGHT HOLDERS BE LIABLE FOR ANY CLAIM, DAMAGES OR OTHER
 * LIABILITY, WHETHER IN AN ACTION OF CONTRACT, TORT OR OTHERWISE, ARISING FROM,
 * OUT OF OR IN CONNECTION WITH THE SOFTWARE OR THE USE OR OTHER DEALINGS IN THE
 * SOFTWARE.
 */

var RotaryLimitJoint = cp.RotaryLimitJoint = function(a, b, min, max)
{
    Constraint.call(this, a, b);

    this.min = min;
    this.max = max;

    this.jAcc = 0;

    this.iSum = this.bias = this.jMax = 0;
};

RotaryLimitJoint.prototype = Object.create(Constraint.prototype);

RotaryLimitJoint.prototype.preStep = function(dt)
{
    var a = this.a;
    var b = this.b;

    var dist = b.a - a.a;
    var pdist = 0;
    if(dist > this.max) {
        pdist = this.max - dist;
    } else if(dist < this.min) {
        pdist = this.min - dist;
    }

    // calculate moment of inertia coefficient.
    this.iSum = 1/(1/a.i + 1/b.i);

    // calculate bias velocity
    var maxBias = this.maxBias;
    this.bias = clamp(-bias_coef(this.errorBias, dt)*pdist/dt, -maxBias, maxBias);

    // compute max impulse
    this.jMax = this.maxForce * dt;

    // If the bias is 0, the joint is not at a limit. Reset the impulse.
    if(!this.bias) this.jAcc = 0;
};

RotaryLimitJoint.prototype.applyCachedImpulse = function(dt_coef)
{
    var a = this.a;
    var b = this.b;

    var j = this.jAcc*dt_coef;
    a.w -= j*a.i_inv;
    b.w += j*b.i_inv;
};

RotaryLimitJoint.prototype.applyImpulse = function()
{
    if(!this.bias) return; // early exit

    var a = this.a;
    var b = this.b;

    // compute relative rotational velocity
    var wr = b.w - a.w;

    // compute normal impulse
    var j = -(this.bias + wr)*this.iSum;
    var jOld = this.jAcc;
    if(this.bias < 0){
        this.jAcc = clamp(jOld + j, 0, this.jMax);
    } else {
        this.jAcc = clamp(jOld + j, -this.jMax, 0);
    }
    j = this.jAcc - jOld;

    // apply impulse
    a.w -= j*a.i_inv;
    b.w += j*b.i_inv;
};

RotaryLimitJoint.prototype.getImpulse = function()
{
    return Math.abs(joint.jAcc);
};

/* Copyright (c) 2007 Scott Lembcke
 *
 * Permission is hereby granted, free of charge, to any person obtaining a copy
 * of this software and associated documentation files (the "Software"), to deal
 * in the Software without restriction, including without limitation the rights
 * to use, copy, modify, merge, publish, distribute, sublicense, and/or sell
 * copies of the Software, and to permit persons to whom the Software is
 * furnished to do so, subject to the following conditions:
 *
 * The above copyright notice and this permission notice shall be included in
 * all copies or substantial portions of the Software.
 *
 * THE SOFTWARE IS PROVIDED "AS IS", WITHOUT WARRANTY OF ANY KIND, EXPRESS OR
 * IMPLIED, INCLUDING BUT NOT LIMITED TO THE WARRANTIES OF MERCHANTABILITY,
 * FITNESS FOR A PARTICULAR PURPOSE AND NONINFRINGEMENT. IN NO EVENT SHALL THE
 * AUTHORS OR COPYRIGHT HOLDERS BE LIABLE FOR ANY CLAIM, DAMAGES OR OTHER
 * LIABILITY, WHETHER IN AN ACTION OF CONTRACT, TORT OR OTHERWISE, ARISING FROM,
 * OUT OF OR IN CONNECTION WITH THE SOFTWARE OR THE USE OR OTHER DEALINGS IN THE
 * SOFTWARE.
 */

var RatchetJoint = cp.RatchetJoint = function(a, b, phase, ratchet)
{
    Constraint.call(this, a, b);

    this.angle = 0;
    this.phase = phase;
    this.ratchet = ratchet;

    // STATIC_BODY_CHECK
    this.angle = (b ? b.a : 0) - (a ? a.a : 0);

    this.iSum = this.bias = this.jAcc = this.jMax = 0;
};

RatchetJoint.prototype = Object.create(Constraint.prototype);

RatchetJoint.prototype.preStep = function(dt)
{
    var a = this.a;
    var b = this.b;

    var angle = this.angle;
    var phase = this.phase;
    var ratchet = this.ratchet;

    var delta = b.a - a.a;
    var diff = angle - delta;
    var pdist = 0;

    if(diff*ratchet > 0){
        pdist = diff;
    } else {
        this.angle = Math.floor((delta - phase)/ratchet)*ratchet + phase;
    }

    // calculate moment of inertia coefficient.
    this.iSum = 1/(a.i_inv + b.i_inv);

    // calculate bias velocity
    var maxBias = this.maxBias;
    this.bias = clamp(-bias_coef(this.errorBias, dt)*pdist/dt, -maxBias, maxBias);

    // compute max impulse
    this.jMax = this.maxForce * dt;

    // If the bias is 0, the joint is not at a limit. Reset the impulse.
    if(!this.bias) this.jAcc = 0;
};

RatchetJoint.prototype.applyCachedImpulse = function(dt_coef)
{
    var a = this.a;
    var b = this.b;

    var j = this.jAcc*dt_coef;
    a.w -= j*a.i_inv;
    b.w += j*b.i_inv;
};

RatchetJoint.prototype.applyImpulse = function()
{
    if(!this.bias) return; // early exit

    var a = this.a;
    var b = this.b;

    // compute relative rotational velocity
    var wr = b.w - a.w;
    var ratchet = this.ratchet;

    // compute normal impulse
    var j = -(this.bias + wr)*this.iSum;
    var jOld = this.jAcc;
    this.jAcc = clamp((jOld + j)*ratchet, 0, this.jMax*Math.abs(ratchet))/ratchet;
    j = this.jAcc - jOld;

    // apply impulse
    a.w -= j*a.i_inv;
    b.w += j*b.i_inv;
};

RatchetJoint.prototype.getImpulse = function(joint)
{
    return Math.abs(joint.jAcc);
};

/* Copyright (c) 2007 Scott Lembcke
 *
 * Permission is hereby granted, free of charge, to any person obtaining a copy
 * of this software and associated documentation files (the "Software"), to deal
 * in the Software without restriction, including without limitation the rights
 * to use, copy, modify, merge, publish, distribute, sublicense, and/or sell
 * copies of the Software, and to permit persons to whom the Software is
 * furnished to do so, subject to the following conditions:
 *
 * The above copyright notice and this permission notice shall be included in
 * all copies or substantial portions of the Software.
 *
 * THE SOFTWARE IS PROVIDED "AS IS", WITHOUT WARRANTY OF ANY KIND, EXPRESS OR
 * IMPLIED, INCLUDING BUT NOT LIMITED TO THE WARRANTIES OF MERCHANTABILITY,
 * FITNESS FOR A PARTICULAR PURPOSE AND NONINFRINGEMENT. IN NO EVENT SHALL THE
 * AUTHORS OR COPYRIGHT HOLDERS BE LIABLE FOR ANY CLAIM, DAMAGES OR OTHER
 * LIABILITY, WHETHER IN AN ACTION OF CONTRACT, TORT OR OTHERWISE, ARISING FROM,
 * OUT OF OR IN CONNECTION WITH THE SOFTWARE OR THE USE OR OTHER DEALINGS IN THE
 * SOFTWARE.
 */

var GearJoint = cp.GearJoint = function(a, b, phase, ratio)
{
    Constraint.call(this, a, b);

    this.phase = phase;
    this.ratio = ratio;
    this.ratio_inv = 1/ratio;

    this.jAcc = 0;

    this.iSum = this.bias = this.jMax = 0;
};

GearJoint.prototype = Object.create(Constraint.prototype);

GearJoint.prototype.preStep = function(dt)
{
    var a = this.a;
    var b = this.b;

    // calculate moment of inertia coefficient.
    this.iSum = 1/(a.i_inv*this.ratio_inv + this.ratio*b.i_inv);

    // calculate bias velocity
    var maxBias = this.maxBias;
    this.bias = clamp(-bias_coef(this.errorBias, dt)*(b.a*this.ratio - a.a - this.phase)/dt, -maxBias, maxBias);

    // compute max impulse
    this.jMax = this.maxForce * dt;
};

GearJoint.prototype.applyCachedImpulse = function(dt_coef)
{
    var a = this.a;
    var b = this.b;

    var j = this.jAcc*dt_coef;
    a.w -= j*a.i_inv*this.ratio_inv;
    b.w += j*b.i_inv;
};

GearJoint.prototype.applyImpulse = function()
{
    var a = this.a;
    var b = this.b;

    // compute relative rotational velocity
    var wr = b.w*this.ratio - a.w;

    // compute normal impulse
    var j = (this.bias - wr)*this.iSum;
    var jOld = this.jAcc;
    this.jAcc = clamp(jOld + j, -this.jMax, this.jMax);
    j = this.jAcc - jOld;

    // apply impulse
    a.w -= j*a.i_inv*this.ratio_inv;
    b.w += j*b.i_inv;
};

GearJoint.prototype.getImpulse = function()
{
    return Math.abs(this.jAcc);
};

GearJoint.prototype.setRatio = function(value)
{
    this.ratio = value;
    this.ratio_inv = 1/value;
    this.activateBodies();
};

/* Copyright (c) 2007 Scott Lembcke
 *
 * Permission is hereby granted, free of charge, to any person obtaining a copy
 * of this software and associated documentation files (the "Software"), to deal
 * in the Software without restriction, including without limitation the rights
 * to use, copy, modify, merge, publish, distribute, sublicense, and/or sell
 * copies of the Software, and to permit persons to whom the Software is
 * furnished to do so, subject to the following conditions:
 *
 * The above copyright notice and this permission notice shall be included in
 * all copies or substantial portions of the Software.
 *
 * THE SOFTWARE IS PROVIDED "AS IS", WITHOUT WARRANTY OF ANY KIND, EXPRESS OR
 * IMPLIED, INCLUDING BUT NOT LIMITED TO THE WARRANTIES OF MERCHANTABILITY,
 * FITNESS FOR A PARTICULAR PURPOSE AND NONINFRINGEMENT. IN NO EVENT SHALL THE
 * AUTHORS OR COPYRIGHT HOLDERS BE LIABLE FOR ANY CLAIM, DAMAGES OR OTHER
 * LIABILITY, WHETHER IN AN ACTION OF CONTRACT, TORT OR OTHERWISE, ARISING FROM,
 * OUT OF OR IN CONNECTION WITH THE SOFTWARE OR THE USE OR OTHER DEALINGS IN THE
 * SOFTWARE.
 */

var SimpleMotor = cp.SimpleMotor = function(a, b, rate)
{
    Constraint.call(this, a, b);

    this.rate = rate;

    this.jAcc = 0;

    this.iSum = this.jMax = 0;
};

SimpleMotor.prototype = Object.create(Constraint.prototype);

SimpleMotor.prototype.preStep = function(dt)
{
    // calculate moment of inertia coefficient.
    this.iSum = 1/(this.a.i_inv + this.b.i_inv);

    // compute max impulse
    this.jMax = this.maxForce * dt;
};

SimpleMotor.prototype.applyCachedImpulse = function(dt_coef)
{
    var a = this.a;
    var b = this.b;

    var j = this.jAcc*dt_coef;
    a.w -= j*a.i_inv;
    b.w += j*b.i_inv;
};

SimpleMotor.prototype.applyImpulse = function()
{
    var a = this.a;
    var b = this.b;

    // compute relative rotational velocity
    var wr = b.w - a.w + this.rate;

    // compute normal impulse
    var j = -wr*this.iSum;
    var jOld = this.jAcc;
    this.jAcc = clamp(jOld + j, -this.jMax, this.jMax);
    j = this.jAcc - jOld;

    // apply impulse
    a.w -= j*a.i_inv;
    b.w += j*b.i_inv;
};

SimpleMotor.prototype.getImpulse = function()
{
    return Math.abs(this.jAcc);
};

})();
(function(){
    var Class = Hilo.Class;
    var EventMixin = Hilo.EventMixin;
    var View = Hilo.View;

    var DEG2RAD = Math.PI/180;
    var RAD2DEG = 1/DEG2RAD;

    /**
     * PhysicsViewMixin是一个包含物理相关功能的mixin。可以通过 Class.mix(target, PhysicsViewMixin) 来为target增加物理功能。
     * @property {cpBody} body view绑定的物理对象，可直接操作改变物理属性
     * @mixin PhysicsViewMixin
     */
    var PhysicsViewMixin = {
        space:null,
        body:null,
        shape:null,
        /**
         * 施加冲量
         * @memberOf PhysicsViewMixin
         * @param  {Object} impulse 冲量，格式：{x:0, y:0}
         * @param  {Object} pos 施力位置离重心相对偏移量，默认0，格式：{x:0, y:0}
         */
        applyImpulse:function(impulse, pos){
            pos = pos||{x:0,y:0};
            this.body.applyImpulse(cp.v(impulse.x, impulse.y), cp.v(pos.x, pos.y));
        },
        /**
         * 施加力
         * @memberOf PhysicsViewMixin
         * @param  {Object} force 力，格式：{x:0, y:0}
         * @param  {Object} pos 施力位置离重心相对偏移量，默认0，格式：{x:0, y:0}
         */
        applyForce:function(force, pos){
            pos = pos||{x:0,y:0};
            this.body.applyForce(cp.v(force.x, force.y), cp.v(pos.x, pos.y));
        },
        /**
         * 设置位置
         * @memberOf PhysicsViewMixin
         * @param {Number} x
         * @param {Number} y
         */
        setPosition:function(x, y){
            this.body.setPos(new cp.Vect(x, y));
            if(this.body.isStaticBody){
                this.space.needReindexStatic = true;
            }
        },
        /**
         * 设置角度
         * @memberOf PhysicsViewMixin
         * @param {Number} rotation 单位角度制
         */
        setRotation:function(rotation){
            this.body.setAngle(rotation * DEG2RAD);
            if(this.body.isStaticBody){
                this.space.needReindexStatic = true;
            }
        },
        /**
         * 重写render
         * @memberOf PhysicsViewMixin
         * @private
         * @param  {Renderer} renderer 渲染器
         * @param  {Number} delta    间隔时间
         */
        render:function(renderer, delta){
            this._physicsRender();
            this._viewRender.call(this, renderer, delta);
        },
        /**
         * 物理属性渲染
         * @memberOf PhysicsViewMixin
         * @private
         */
        _physicsRender: function() {
            this.x = this.body.p.x;
            this.y = this.body.p.y;
            this.rotation = this.body.a * RAD2DEG;
        }
    };

    /**
     * 物理世界
     * @class  Physics
     * @param  {Object} gravity 重力加速度
     * @param  {Number} gravity.x 重力加速度x
     * @param  {Number} gravity.y 重力加速度y
     * @param  {Object} cfg     世界属性配置
     * @return {Physic}
     */
    var Physics = Class.create(/** @lends Physics.prototype */{
        Mixes:EventMixin,
        Statics:{
            SHAPE_RECT:"rect",
            SHAPE_CIRCLE:"circle",
            SHAPE_POLYGEN:"polygen"
        },
        /**
         * @private
        */
        constructor:function(gravity, cfg){
            this._init(gravity, cfg);
        },
        /**
         * @private
         */
        _init:function(gravity, cfg){
            var space = new cp.Space();
            space.iterations = 20;
            space.gravity = new cp.Vect(gravity.x, gravity.y);
            space.collisionSlop = 0.5;
            space.sleepTimeThreshold = 0.5;

            if(cfg){
                for(var i in cfg){
                    space[i] = cfg[i];
                }
            }

            this.space = space;
            this.staticBody = space.staticBody;

            this._deleteBodies = [];
        },
        /**
         * tick方法，供Hilo.Ticker调用
         * @private
         * @param  {Number} dt 间隔
         */
        tick:function(dt){
            var space = this.space;
            dt = dt > 32?16:dt;

            if(space.needReindexStatic){
                space.reindexStatic();
                space.needReindexStatic = false;
            }
            space.step(dt * .001);

            //delete bodies and shapes
            for(var i = this._deleteBodies.length - 1;i >= 0;i --){
                var body = this._deleteBodies[i];
                var shapeList = body.shapeList;
                for(var j = shapeList.length - 1;j >= 0;j --){
                    space.removeShape(shapeList[j]);
                }
                space.removeBody(body);
            }
        },
        /**
         * 绑定物理刚体
         * @param  {View} view 要绑定的view
         * @param  {Object} cfg  物理参数
         * @param  {String} cfg.type  形状类型，SHAPE_RECT|SHAPE_CIRCLE|SHAPE_POLYGEN , 默认矩形
         * @param  {Number} cfg.restitution  弹力，默认0.4
         * @param  {Number} cfg.friction  摩擦力，默认1
         * @param  {Number} cfg.mass  质量，默认1
         * @param  {Number} cfg.collisionType  碰撞类型，默认1
         * @param  {Uint} cfg.group  碰撞组标识，默认为0，零组与任何组都碰撞，相同的非零组之间不会互相碰撞
         * @param  {Uint} cfg.layers  碰撞层的掩码，默认为~0，两个层的按位与不为0时(a.layers & b.layers != 0)会发生碰撞
         * @param  {Boolean} cfg.isStatic  是否静态刚体，默认false
         * @param  {Number} cfg.width  宽，type为SHAPE_RECT时有效，默认为view宽
         * @param  {Number} cfg.height  高，type为SHAPE_RECT时有效，默认为view高
         * @param  {Number} cfg.radius  半径，type为SHAPE_CIRCLE时有效，默认为view宽的一半
         * @param  {Array} cfg.boundsArea  顶点数组，type为SHAPE_POLYGEN时有效, 顶点顺序必须逆时针，[{x:0, y:0}, {x:100, y:0}, {x:50, y:50}]
         */
        bindView:function(view, cfg){
            if(view.body){
                this.unbindView(view);
            }

            var cfg = cfg||{};
            var mass = cfg.mass || 1;
            var type = cfg.type || Physics.SHAPE_RECT;
            var group = cfg.group === undefined?0:cfg.group;
            var layers = cfg.layers === undefined?~0:cfg.layers;
            var width = view.width * view.scaleX;
            var height = view.height * view.scaleY;

            var body, shape;
            if(type === Physics.SHAPE_POLYGEN && !(view.boundsArea||cfg.boundsArea)){
                type = Physics.SHAPE_RECT;
            }

            switch(type){
                case Physics.SHAPE_RECT:
                    width = cfg.width||width;
                    height = cfg.height||height;
                    body = cfg.isStatic?this._createStaticBody():new cp.Body(mass, cp.momentForBox(mass, width, height));
                    shape = new cp.BoxShape(body, width, height);
                    break;
                case Physics.SHAPE_CIRCLE:
                    radius = cfg.radius||width*.5;
                    body = cfg.isStatic?this._createStaticBody():new cp.Body(mass, cp.momentForCircle(mass, 0, radius, new cp.Vect(0, 0)));
                    shape = new cp.CircleShape(body, radius, new cp.Vect(0, 0));
                    break;
                case Physics.SHAPE_POLYGEN:
                    var boundsArea = cfg.boundsArea||view.boundsArea;
                    verts = [];
                    boundsArea.forEach(function(point){
                        verts.push(point.x);
                        verts.push(point.y);
                    });
                    view.boundsArea = boundsArea;
                    body = cfg.isStatic?this._createStaticBody():new cp.Body(mass, cp.momentForPoly(mass, verts, new cp.Vect(0, 0)));
                    shape = new cp.PolyShape(body, verts, new cp.Vect(0, 0));
                    break;
                default:
                    break;
            }

            body.setAngle(view.rotation * DEG2RAD);
            body.setPos(new cp.Vect(view.x, view.y));

            shape.setElasticity(cfg.restitution||.4);
            shape.setFriction(cfg.friction||1);
            shape.setCollisionType(cfg.collisionType||1);
            shape.layers = layers;
            shape.group = group;

            view._viewRender = view.render;
            Class.mix(view, PhysicsViewMixin);


            view.body = body;
            view.shape = shape;
            view.space = this.space;
            body.view = view;

	       //物理对象中心点必须在中心
            view.pivotX = view.width * .5;
            view.pivotY = view.height * .5;

            if(cfg.isStatic){
                this.space.addShape(shape);
            }
            else{
                this.space.addBody(body);
                this.space.addShape(shape);
            }


            view._physicsRender();
        },
        /**
         * 增加关节
         * @param {Joint} joint 关节
         * @return {Joint}
         */
        addConstraint:function(joint){
            return this.space.addConstraint(joint);
        },
        /**
         * 移除关节
         * @param  {Joint} joint 关节
         * @return {Joint}
         */
        removeConstraint:function(joint){
            return this.space.removeConstraint(joint);
        },
        /**
         * 解绑物理刚体
         * @param  {View}  view 要解绑的view
         * @param  {Boolean} isDelView 是否删除view，默认不删除
         */
        unbindView:function(view, isDelView){
            var body = view.body;
            if(body){
                view.body = null;
                body.view = null;

                //延迟删除
                if(this._deleteBodies.indexOf(body) < 0){
                    this._deleteBodies.push(body);
                }
            }

            for(var prop in PhysicsViewMixin){
                view[prop] = null;
            }

            if(view._viewRender){
                view.render = view._viewRender;
            }

            if(isDelView){
                view.removeFromParent();
            }
        },
        /**
         * 添加碰撞监听
         * @param {Number} typeA 碰撞类型A
         * @param {Number} typeB 碰撞类型B
         * @param {Object} listenerConfig 回调函数配置
         * @param {Physics~collisionCallback} listenerConfig.begin 开始接触回调
         * @param {Physics~collisionCallback} listenerConfig.preSolve 处理前碰撞回调
         * @param {Physics~collisionCallback} listenerConfig.postSolve 处理后碰撞回调
         * @param {Physics~collisionCallback} listenerConfig.separate 分离回调
         */
        addCollisionListener:function(typeA, typeB, listenerConfig){
            var begin = listenerConfig.begin||function(arbiter){
                return true;
            };

            var preSolve = listenerConfig.preSolve||function(arbiter){
                return true;
            };

            var postSolve = listenerConfig.postSolve||function(arbiter){

            };

            var separate = listenerConfig.separate||function(arbiter){

            };

            this.space.addCollisionHandler(typeA, typeB, begin, preSolve, postSolve, separate);
        },
        /**
         * 添加边框
         * @param  {Number} width  宽
         * @param  {Number} height 高
         */
        createBounds:function(width, height){
            this._createBound({x:0, y:height}, {x:width, y:height}, 1);
            this._createBound({x:0, y:0}, {x:0, y:height}, 1);
            this._createBound({x:width, y:0}, {x:width, y:height}, 1);
        },
        _createBound: function(p0, p1, height) {
            var floor = this.space.addShape(new cp.SegmentShape(this.staticBody, cp.v(p0.x, p0.y), cp.v(p1.x, p1.y), height));
            floor.setElasticity(1);
            floor.setFriction(1);
        },
        _createStaticBody:function(){
            var body = new cp.Body(Infinity, Infinity);
            body.nodeIdleTime = Infinity;
            body.isStaticBody = true;
            return body;
        }
    });

    /**
     * 调试显示对象
     * @class  PhysicsDebugView
     * @param {Object} properties 属性
     * @param {Physics} properties.world 物理世界
     * @param {Boolean} properties.showShapes 是否显示shape，默认true
     * @param {Boolean} properties.showConstraints 是否显示constraint，默认true
     */
    var PhysicsDebugView = Class.create( /** @lends PhysicsDebugView.prototype */ {
        Extends: View,
        constructor: function(properties) {
            properties = properties || {};
            this.id = this.id || properties.id || Hilo.getUid('PhysicsDebugView');
            this.showShapes = true;
            this.showConstraints = true;
            PhysicsDebugView.superclass.constructor.call(this, properties);

            this.space = properties.world.space;
            this.pointerEnabled = false;
            this.pointerChildren = false;

            this.initDebugDraw();
        },
        render: function(renderer, delta) {
            var me = this,
                canvas = renderer.canvas,
                ctx = renderer.context;

            if (canvas.getContext && ctx) {
                this.showShapes && this.space.eachShape(function(shape){
                    if(!shape.hideDebugView){
                        ctx.fillStyle = shape.style();
                        shape.draw(ctx);
                    }
                });

                this.showConstraints && this.space.eachConstraint(function(c) {
                    if(!c.hideDebugView && c.draw){
                        c.draw(ctx);
                    }
                });
            }
        },
        initDebugDraw: function() {
            if (!this._isInit) {
                this._isInit = true;
                //draw shapes and constraints, copy from https://github.com/josephg/Chipmunk-js/blob/master/cp.extra.js
                var v = cp.v;var drawCircle = function(ctx, c, radius, isFill) {ctx.beginPath(); ctx.arc(c.x, c.y, radius, 0, 2 * Math.PI, false); if (isFill === undefined) {isFill = true; } isFill && ctx.fill(); ctx.stroke(); }; var drawLine = function(ctx, a, b) {ctx.beginPath(); ctx.moveTo(a.x, a.y); ctx.lineTo(b.x, b.y); ctx.stroke(); }; var springPoints = [v(0.00, 0.0), v(0.20, 0.0), v(0.25, 0.5), v(0.30, -1.0), v(0.35, 1.0), v(0.40, -1.0), v(0.45, 1.0), v(0.50, -1.0), v(0.55, 1.0), v(0.60, -1.0), v(0.65, 1.0), v(0.70, -1.0), v(0.75, 0.5), v(0.80, 0.0), v(1.00, 0.0) ]; var drawSpring = function(ctx, a, b, width) {if (width == null) width = 6; ctx.beginPath(); ctx.moveTo(a.x, a.y); var delta = v.sub(b, a); var len = v.len(delta); var rot = v.mult(delta, 1 / len); for (var i = 1; i < springPoints.length; i++) {var p = v.add(a, v.rotate(v(springPoints[i].x * len, springPoints[i].y * width), rot)); ctx.lineTo(p.x, p.y); } ctx.stroke(); }; cp.PolyShape.prototype.draw = function(ctx) {ctx.beginPath(); var verts = this.tVerts; var len = verts.length; var lastPoint = new cp.Vect(verts[len - 2], verts[len - 1]); ctx.moveTo(lastPoint.x, lastPoint.y); for (var i = 0; i < len; i += 2) {var p = new cp.Vect(verts[i], verts[i + 1]); ctx.lineTo(p.x, p.y); } ctx.fill(); ctx.stroke(); };cp.SegmentShape.prototype.draw = function(ctx) {var oldLineWidth = ctx.lineWidth; ctx.lineWidth = Math.max(1, this.r * 2); drawLine(ctx, this.ta, this.tb); ctx.lineWidth = oldLineWidth; }; cp.CircleShape.prototype.draw = function(ctx) {drawCircle(ctx, this.tc, this.r); drawLine(ctx, this.tc, cp.v.mult(this.body.rot, this.r).add(this.tc)); }; cp.PinJoint.prototype.draw = function(ctx) {var a = this.a.local2World(this.anchr1); var b = this.b.local2World(this.anchr2); ctx.lineWidth = 2; ctx.strokeStyle = "grey"; drawLine(ctx, a, b); }; cp.SlideJoint.prototype.draw = function(ctx) {var a = this.a.local2World(this.anchr1); var b = this.b.local2World(this.anchr2); var midpoint = v.add(a, v.clamp(v.sub(b, a), this.min)); ctx.lineWidth = 2; ctx.strokeStyle = "grey"; drawLine(ctx, a, b); ctx.strokeStyle = "red"; drawLine(ctx, a, midpoint); }; cp.PivotJoint.prototype.draw = function(ctx) {var a = this.a.local2World(this.anchr1); var b = this.b.local2World(this.anchr2); ctx.strokeStyle = "grey"; ctx.fillStyle = "grey"; drawCircle(ctx, a, 2); drawCircle(ctx, b, 2); }; cp.GrooveJoint.prototype.draw = function(ctx) {var a = this.a.local2World(this.grv_a); var b = this.a.local2World(this.grv_b); var c = this.b.local2World(this.anchr2); ctx.strokeStyle = "grey"; drawLine(ctx, a, b); drawCircle(ctx, c, 3); }; cp.DampedSpring.prototype.draw = function(ctx) {var a = this.a.local2World(this.anchr1); var b = this.b.local2World(this.anchr2); ctx.strokeStyle = "grey"; drawSpring(ctx, a, b); }; cp.SimpleMotor.prototype.draw = function(ctx) {ctx.save(); ctx.strokeStyle = "#aa0000"; ctx.lineWidth = 0.5; drawCircle(ctx, this.a.p, 7, false); drawCircle(ctx, this.b.p, 7, false); ctx.restore(); };var randColor = function() {return Math.floor(Math.random() * 256); }; var styles = []; for (var i = 0; i < 100; i++) {styles.push("rgb(" + randColor() + ", " + randColor() + ", " + randColor() + ")"); } cp.Shape.prototype.style = function() {var body; if (this.sensor) {return "rgba(255,255,255,0)"; } else {body = this.body; if (body.isSleeping()) {return "rgb(50,50,50)"; } else if (body.nodeIdleTime > this.space.sleepTimeThreshold) {return "rgb(170,170,170)"; } else {return styles[this.hashid % styles.length]; } } };
            }
        }
    });

    Hilo.Physics = Physics;
    Hilo.PhysicsDebugView = PhysicsDebugView;
})();

/**
 * 碰撞回调函数格式
 * @callback Physics~collisionCallback
 * @param {Object} arbiter 回调数据
 * @param {Shape} arbiter.a 碰撞a形状
 * @param {Shape} arbiter.b 碰撞b形状
 */