1 /**
  2  * Constructs a new collision constraint. The default search radius is 10, and
  3  * the default repeat count is 1. A radius function must be specified to compute
  4  * the radius of particles.
  5  *
  6  * @class Constraints circles to avoid overlap. Each particle is treated as a
  7  * circle, with the radius of the particle computed using a specified function.
  8  * For example, if the particle has an <tt>r</tt> attribute storing the radius,
  9  * the radius <tt>function(d) d.r</tt> specifies a collision constraint using
 10  * this radius. The radius function is passed each {@link pv.Particle} as the
 11  * first argument.
 12  *
 13  * <p>To accelerate collision detection, this implementation uses a quadtree and
 14  * a search radius. The search radius is computed as the maximum radius of all
 15  * particles in the simulation.
 16  *
 17  * @see pv.Constraint
 18  * @param {function} radius the radius function.
 19  */
 20 pv.Constraint.collision = function(radius) {
 21   var n = 1, // number of times to repeat the constraint
 22       r1,
 23       px1,
 24       py1,
 25       px2,
 26       py2,
 27       constraint = {};
 28 
 29   if (!arguments.length) r1 = 10; // default search radius
 30 
 31   /**
 32    * Sets or gets the repeat count. If the repeat count is greater than 1, the
 33    * constraint will be applied repeatedly; this is a form of the Gauss-Seidel
 34    * method for constraints relaxation. Repeating the collision constraint makes
 35    * the constraint have more of an effect when there is a potential for many
 36    * co-occurring collisions.
 37    *
 38    * @function
 39    * @name pv.Constraint.collision.prototype.repeat
 40    * @param {number} x the number of times to repeat this constraint.
 41    * @returns {pv.Constraint.collision} this.
 42    */
 43   constraint.repeat = function(x) {
 44     if (arguments.length) {
 45       n = Number(x);
 46       return constraint;
 47     }
 48     return n;
 49   };
 50 
 51   /** @private */
 52   function constrain(n, p, x1, y1, x2, y2) {
 53     if (!n.leaf) {
 54       var sx = (x1 + x2) * .5,
 55           sy = (y1 + y2) * .5,
 56           top = sy > py1,
 57           bottom = sy < py2,
 58           left = sx > px1,
 59           right = sx < px2;
 60       if (top) {
 61         if (n.c1 && left) constrain(n.c1, p, x1, y1, sx, sy);
 62         if (n.c2 && right) constrain(n.c2, p, sx, y1, x2, sy);
 63       }
 64       if (bottom) {
 65         if (n.c3 && left) constrain(n.c3, p, x1, sy, sx, y2);
 66         if (n.c4 && right) constrain(n.c4, p, sx, sy, x2, y2);
 67       }
 68     }
 69     if (n.p && (n.p != p)) {
 70       var dx = p.x - n.p.x,
 71           dy = p.y - n.p.y,
 72           l = Math.sqrt(dx * dx + dy * dy),
 73           d = r1 + radius(n.p);
 74       if (l < d) {
 75         var k = (l - d) / l * .5;
 76         dx *= k;
 77         dy *= k;
 78         p.x -= dx;
 79         p.y -= dy;
 80         n.p.x += dx;
 81         n.p.y += dy;
 82       }
 83     }
 84   }
 85 
 86   /**
 87    * Applies this constraint to the specified particles.
 88    *
 89    * @function
 90    * @name pv.Constraint.collision.prototype.apply
 91    * @param {pv.Particle} particles particles to which to apply this constraint.
 92    * @param {pv.Quadtree} q a quadtree for spatial acceleration.
 93    */
 94   constraint.apply = function(particles, q) {
 95     var p, r, max = -Infinity;
 96     for (p = particles; p; p = p.next) {
 97       r = radius(p);
 98       if (r > max) max = r;
 99     }
100     for (var i = 0; i < n; i++) {
101       for (p = particles; p; p = p.next) {
102         r = (r1 = radius(p)) + max;
103         px1 = p.x - r;
104         px2 = p.x + r;
105         py1 = p.y - r;
106         py2 = p.y + r;
107         constrain(q.root, p, q.xMin, q.yMin, q.xMax, q.yMax);
108       }
109     }
110   };
111 
112   return constraint;
113 };
114