1 /**
  2  * The Render Engine
  3  * ConvexColliderComponent
  4  *
  5  * @fileoverview A collision component which determines collisions using
  6  *               the Separating Axis Theorem and a convex hull.
  7  *
  8  * @author: Brett Fattori (brettf@renderengine.com)
  9  *
 10  * @author: $Author: bfattori@gmail.com $
 11  * @version: $Revision: 1570 $
 12  *
 13  * Copyright (c) 2011 Brett Fattori (brettf@renderengine.com)
 14  *
 15  * Permission is hereby granted, free of charge, to any person obtaining a copy
 16  * of this software and associated documentation files (the "Software"), to deal
 17  * in the Software without restriction, including without limitation the rights
 18  * to use, copy, modify, merge, publish, distribute, sublicense, and/or sell
 19  * copies of the Software, and to permit persons to whom the Software is
 20  * furnished to do so, subject to the following conditions:
 21  *
 22  * The above copyright notice and this permission notice shall be included in
 23  * all copies or substantial portions of the Software.
 24  *
 25  * THE SOFTWARE IS PROVIDED "AS IS", WITHOUT WARRANTY OF ANY KIND, EXPRESS OR
 26  * IMPLIED, INCLUDING BUT NOT LIMITED TO THE WARRANTIES OF MERCHANTABILITY,
 27  * FITNESS FOR A PARTICULAR PURPOSE AND NONINFRINGEMENT. IN NO EVENT SHALL THE
 28  * AUTHORS OR COPYRIGHT HOLDERS BE LIABLE FOR ANY CLAIM, DAMAGES OR OTHER
 29  * LIABILITY, WHETHER IN AN ACTION OF CONTRACT, TORT OR OTHERWISE, ARISING FROM,
 30  * OUT OF OR IN CONNECTION WITH THE SOFTWARE OR THE USE OR OTHER DEALINGS IN
 31  * THE SOFTWARE.
 32  *
 33  */
 34 
 35 // The class this file defines and its required classes
 36 R.Engine.define({
 37     "class":"R.components.collision.Convex",
 38     "requires":[
 39         "R.components.Collider",
 40         "R.math.Point2D",
 41         "R.math.Vector2D",
 42         "R.math.Rectangle2D",
 43         "R.math.Math2D",
 44         "R.collision.ConvexHull",
 45         "R.struct.CollisionData"
 46     ]
 47 });
 48 
 49 /**
 50  * @class An extension of the {@link ColliderComponent} which will check the
 51  *        object's convex collision hulls using the Separating Axis Theorm (SAT).  Each object must
 52  *        have a collision hull assigned to it with {@link R.objects.Object2D#setCollisionHull}.
 53  *        <p/>
 54  *        The SAT states that, if an axis can be found where the two object's hulls
 55  *        don't overlap, then the two objects cannot be colliding.  When a collision
 56  *        is determined, querying {@link #getCollisionData} will return a {@link R.struct.CollisionData}
 57  *        object which can be used to determine the collision normal, what shapes collided, the amount
 58  *        of overlap, and a vector to separate the objects.
 59  *        <p/>
 60  *        The data can also be manipulated to simulate physical forces such as
 61  *        bounciness and friction.
 62  *
 63  * @param name {String} Name of the component
 64  * @param collisionModel {R.spatial.AbstractSpatialContainer} The collision model
 65  * @param priority {Number} Between 0.0 and 1.0, with 1.0 being highest
 66  *
 67  * @extends R.components.Collider
 68  * @constructor
 69  * @description Creates a collider component for SAT collision testing.  Each object's
 70  *              collision will be determined using its convex collision hull.
 71  */
 72 R.components.collision.Convex = function () {
 73     "use strict";
 74     return R.components.Collider.extend(/** @scope R.components.collision.Convex.prototype */{
 75 
 76         hasMethods:null,
 77 
 78 
 79         /**
 80          * @private
 81          */
 82         constructor:function (name, collisionModel, priority) {
 83             this.base(name, collisionModel, priority);
 84             this.hasMethods = [];
 85 
 86             // Convex hull colliders can only produce detailed tests
 87             this.setTestMode(R.components.Collider.DETAILED_TEST);
 88         },
 89 
 90         /**
 91          * Release the component back into the object pool.
 92          */
 93         release:function () {
 94             this.base();
 95         },
 96 
 97         /**
 98          * Deprecated in favor of {@link #setGameObject}
 99          * @deprecated
100          */
101         setHostObject:function (gameObject) {
102             this.setGameObject(gameObject);
103         },
104 
105         /**
106          * Establishes the link between this component and its game object.
107          * When you assign components to a game object, it will call this method
108          * so that each component can refer to its game object, the same way
109          * a game object can refer to a component with {@link R.engine.GameObject#getComponent}.
110          *
111          * @param gameObject {R.engine.GameObject} The object which hosts this component
112          */
113         setGameObject:function (gameObject) {
114             this.base(gameObject);
115             this.hasMethods = [gameObject.getCollisionHull != undefined];
116             /* pragma:DEBUG_START */
117             // Test if the host has getCollisionHull
118             AssertWarn(this.hasMethods[0], "Object " + gameObject.toString() + " does not have getCollisionHull() method");
119             /* pragma:DEBUG_END */
120         },
121 
122         /**
123          * If a collision occurs, calls the game object's <tt>onCollide()</tt> method,
124          * passing the time of the collision, the potential collision object, and the game object
125          * and target's masks.  The return value should either tell the collision tests to continue or stop.
126          *
127          * @param time {Number} The engine time (in milliseconds) when the potential collision occurred
128          * @param dt {Number} The delta between the world time and the last time the world was updated
129          *          in milliseconds.
130          * @param collisionObj {R.engine.GameObject} The game object with which the collision potentially occurs
131          * @param objectMask {Number} The collision mask for the host object
132          * @param targetMask {Number} The collision mask for <tt>collisionObj</tt>
133          * @return {Number} A status indicating whether to continue checking, or to stop
134          */
135         testCollision:function (time, dt, collisionObj, objectMask, targetMask) {
136             if (this.getCollisionData() != null) {
137                 // Clean up old data first
138                 this.getCollisionData().destroy();
139                 this.setCollisionData(null);
140             }
141 
142             // Fast-out test if no method(s)
143             var host = this.getGameObject();
144             if (!this.hasMethods[0] && !collisionObj.getCollisionHull) {
145                 return R.components.Collider.CONTINUE;		// Can't perform test
146             }
147 
148             // Use distance of bounding circle's to perform an early out test
149             // if the objects are too far apart
150             var hull1 = host.getCollisionHull();
151             if (collisionObj.isDestroyed()) {
152                 // The collision object has already been destroyed, skip it
153                 return R.components.Collider.CONTINUE;
154             }
155 
156             var hull2 = collisionObj.getCollisionHull();
157 
158             if (!hull1 || !hull2) {
159                 return R.components.Collider.CONTINUE;		// No collision hull defined!
160             }
161 
162             // Look for potential for collision before doing full test
163             var tRad = hull1.getRadius() + hull2.getRadius();
164             var c1 = hull1.getCenter();
165             var c2 = hull2.getCenter();
166             var distSqr = (c1.x - c2.x) * (c1.x - c2.x) +
167                 (c1.y - c2.y) * (c1.y - c2.y);
168             if (distSqr > tRad * tRad) {
169                 // Too far apart to be colliding
170                 return R.components.Collider.CONTINUE;
171             }
172 
173             // Perform the test, passing along the circle data so we don't recalc
174             this.setCollisionData(R.components.collision.Convex.test(hull1, hull2, time, dt, distSqr, tRad));
175 
176             // If a collision occurred, there will be a data structure describing it
177             if (this.getCollisionData() != null) {
178                 return this.base(time, dt, collisionObj, objectMask, targetMask);
179             }
180 
181             return R.components.Collider.CONTINUE;
182         }
183 
184         /* pragma:DEBUG_START */, execute:function (renderContext, time, dt) {
185             this.base(renderContext, time, dt);
186             // Debug the collision hull
187             if (R.Engine.getDebugMode() && !this.isDestroyed()) {
188                 renderContext.pushTransform();
189                 renderContext.setLineStyle("yellow");
190                 var cHull = this.getGameObject().getCollisionHull();
191                 if (cHull.getType() == R.collision.ConvexHull.CONVEX_NGON) {
192                     renderContext.drawPolygon(cHull.getUntransformedVertexes());
193                 } else {
194                     renderContext.drawArc(R.math.Point2D.ZERO, cHull.getRadius(), 0, 359);
195                 }
196                 renderContext.popTransform();
197             }
198         }
199         /* pragma:DEBUG_END */
200 
201     }, /** @scope R.components.collision.Convex.prototype */{
202 
203         /**
204          * Get the class name of this object
205          * @return {String} "R.components.collision.Convex"
206          */
207         getClassName:function () {
208             return "R.components.collision.Convex";
209         },
210 
211         /**
212          * Performs the SAT collision test for <code>shape1</code> against <code>shape2</code>.
213          * Each shape is either a convex hull or a circle (AABB or box is considered a polygon).
214          * If a collision is observed, the method will return a repulsion vector for the first
215          * shape to not collide with the second shape.  If no collision is determined, the
216          * repulsion vector will be {@link R.math.Vector2D#ZERO}.
217          * <p/>
218          * The resulting tests used by this component can be found at:<br/>
219          * http://rocketmandevelopment.com/2010/05/19/separation-of-axis-theorem-for-collision-detection/
220          *
221          * @param shape1 {R.collision.ConvexHull}
222          * @param shape2 {R.collision.ConvexHull}
223          * @param time {Number} The world time
224          * @param dt {Number} The delta between the world time and the last time the world was updated
225          *          in milliseconds.
226          * @return {R.math.Vector2D}
227          */
228         test:function (shape1, shape2, time, dt /*, distSqr, tRad */) {
229             /* pragma:DEBUG_START */
230             if (R.Engine.getDebugMode()) {
231                 var rc = shape1.getGameObject().getRenderContext(), c1 = R.math.Point2D.create(shape1.getCenter()), c2 =
232                     R.math.Point2D.create(shape2.getCenter());
233                 rc.postRender(function () {
234                     this.setLineStyle("yellow");
235                     this.setLineWidth(2);
236                     this.drawLine(c1, c2);
237                 });
238             }
239             /* pragma:DEBUG_END */
240 
241 
242             if (shape1.getType() == R.collision.ConvexHull.CONVEX_CIRCLE &&
243                 shape2.getType() == R.collision.ConvexHull.CONVEX_CIRCLE) {
244                 // Perform circle-circle test if both shapes are circles
245                 // We've passed in the distSqr and tRad from the early-out test, pass it along
246                 // so we're not re-running the calculations
247                 return R.components.collision.Convex.ccTest(shape1, shape2, time, dt, arguments[4], arguments[5]);
248             } else if (shape1.getType() != R.collision.ConvexHull.CONVEX_CIRCLE &&
249                 shape2.getType() != R.collision.ConvexHull.CONVEX_CIRCLE) {
250                 // Perform polygon test if both shapes are NOT circles
251                 return R.components.collision.Convex.ppTest(shape1, shape2, time, dt);
252             } else {
253                 // One shape is a circle, the other is an polygon, do that test
254                 return R.components.collision.Convex.cpTest(shape1, shape2, time, dt);
255             }
256         },
257 
258         /**
259          * Circle-circle test
260          * @private
261          */
262         ccTest:function (shape1, shape2, time, dt, distSqr, tRad) {
263             // If we got here, we've already done 95% of the work in the early-out test above
264             var c1 = shape1.getCenter(), c2 = shape2.getCenter();
265 
266             // How much to separate shape1 from shape2
267             var diff = tRad - Math.sqrt(distSqr);
268 
269             // If we got here, there is a collision
270             var sep = R.math.Vector2D.create((c2.x - c1.x) * diff, (c2.y - c1.y) * diff);
271             return R.struct.CollisionData.create(sep.len(),
272                 R.math.Vector2D.create(c2.x - c1.x, c2.y - c1.y).normalize(),
273                 shape1.getGameObject(),
274                 shape2.getGameObject(),
275                 sep,
276                 time,
277                 dt);
278         },
279 
280         /**
281          * Poly-poly test
282          * @private
283          */
284         ppTest:function (shape1, shape2, time, dt) {
285             var test1, test2, testNum, min1, min2, max1, max2, offset, temp;
286             var axis = R.math.Vector2D.create(0, 0);
287             var vectorOffset = R.math.Vector2D.create(0, 0);
288             var vectors1 = shape1.getVertexes();		// This time we want transformed verts
289             var vectors2 = shape2.getVertexes();
290             var shortestDistance = 0x7FFFFFF;
291             var unitVec = null;
292             var overlap = 0;
293 
294             if (vectors1.length == 2) {
295                 // Pad to fix the test
296                 temp = R.math.Vector2D.create(-(vectors1[1].y - vectors1[0].y),
297                     vectors1[1].x - vectors1[0].x);
298                 vectors1.push(vectors1[1].add(temp));
299                 temp.destroy();
300             }
301             if (vectors2.length == 2) {
302                 temp = R.math.Vector2D.create(-(vectors2[1].y - vectors2[0].y),
303                     vectors2[1].x - vectors2[0].x);
304                 vectors2.push(vectors2[1].add(temp));
305                 temp.destroy();
306             }
307 
308             // Find vertical offset
309             var sc1 = shape1.getCenter();
310             var sc2 = shape2.getCenter();
311             vectorOffset.set(sc1.x - sc2.x, sc1.y - sc2.y);
312 
313             // Loop to begin projection
314             for (var i = 0; i < vectors1.length; i++) {
315                 R.components.collision.Convex.findNormalAxis(axis, vectors1, i);
316 
317                 // project polygon 1
318                 min1 = axis.dot(vectors1[0]);
319                 max1 = min1;	// Set max and min equal
320 
321                 var j;
322                 for (j = 1; j < vectors1.length; j++) {
323                     testNum = axis.dot(vectors1[j]);	// Project each point
324                     if (testNum < min1) min1 = testNum;	// Test for new smallest
325                     if (testNum > max1) max1 = testNum;	// Test for new largest
326                 }
327 
328                 // project polygon 2
329                 min2 = axis.dot(vectors2[0]);
330                 max2 = min2;	// Set 2's max and min
331 
332                 for (j = 1; j < vectors2.length; j++) {
333                     testNum = axis.dot(vectors2[j]);	// Project the point
334                     if (testNum < min2) min2 = testNum;	// Test for new min
335                     if (testNum > max2) max2 = testNum; // Test for new max
336                 }
337 
338                 // Test if they are touching
339                 test1 = min1 - max2;	// Test min1 and max2
340                 test2 = min2 - max1; // Test min2 and max1
341 
342                 // Test for a gap
343                 if (test1 > 0 || test2 > 0) {
344                     // Clean up before returning
345                     axis.destroy();
346                     vectorOffset.destroy();
347                     // If either is greater than zero, there is a gap
348                     return null;
349                 }
350 
351                 var dist = -(max2 - min1);
352                 var aDist = Math.abs(dist);
353                 if (aDist < shortestDistance) {
354                     unitVec = axis;
355                     overlap = dist;
356                     shortestDistance = aDist;
357                 }
358             }
359 
360             if (unitVec == null) {
361                 // Something is wrong
362                 return null;
363             }
364 
365             // If you're here, there is a collision
366             var cData = R.struct.CollisionData.create(overlap,
367                 unitVec,
368                 shape1.getGameObject(),
369                 shape2.getGameObject(),
370                 R.math.Vector2D.create(unitVec.x * overlap, unitVec.y * overlap),
371                 time,
372                 dt);
373 
374             // Clean up before returning
375             vectorOffset.destroy();
376 
377             // Return the collision data
378             return cData;
379         },
380 
381         /**
382          * @private
383          */
384         findNormalAxis:function (axis, vertices, index) {
385             var vector1 = vertices[index];
386             var vector2 = (index >= vertices.length - 1) ? vertices[0] : vertices[index + 1];
387             axis.set(-(vector2.y - vector1.y), vector2.x - vector1.x);
388             axis.normalize();
389         },
390 
391         /**
392          * Circle-poly test
393          * @private
394          */
395         cpTest:function (shape1, shape2, time, dt) {
396             var test1, test2, test, min1, max1, min2, max2, offset, distance, temp;
397             var vectorOffset = R.math.Vector2D.create(0, 0);
398             var vectors, center, radius, poly;
399             var testDistance = 0x7FFFFFFF;
400             var shortestDistance = 0x7FFFFFFF;
401             var closestVertex = R.math.Vector2D.create(0, 0);
402             var normalAxis = R.math.Vector2D.create(0, 0);
403             var unitVec = null;
404             var overlap = 0;
405 
406             // Determine which shape is the circle and which is the polygon
407             // We don't want the transformed vertexes here, we transform them later
408             if (shape1.getType() != R.collision.ConvexHull.CONVEX_CIRCLE) {
409                 vectors = shape1.getUntransformedVertexes();
410                 poly = shape1.getCenter();
411                 center = shape2.getCenter();
412                 radius = shape2.getRadius();
413             } else {
414                 vectors = shape2.getUntransformedVertexes();
415                 poly = shape2.getCenter();
416                 center = shape1.getCenter();
417                 radius = shape1.getRadius();
418             }
419 
420             // Find offset
421             var pC = poly;
422             var cC = center;
423             vectorOffset.set(pC.x - cC.x, pC.y - cC.y);
424 
425             if (vectors.length == 2) {
426                 // Pad to fix the test
427                 temp = R.math.Vector2D.create(-(vectors[1].y - vectors[0].y),
428                     vectors[1].x - vectors[0].x);
429                 vectors.push(vectors[1].add(temp));
430                 temp.destroy();
431             }
432 
433             // Find the closest vertex to use to find normal
434             var i, j;
435             for (i = 0; i < vectors.length; i++) {
436                 // These points have been transformed
437                 distance = (cC.x - (pC.x + vectors[i].x)) * (cC.x - (pC.x + vectors[i].x)) +
438                     (cC.y - (pC.y + vectors[i].y)) * (cC.y - (pC.y + vectors[i].y));
439                 if (distance < testDistance) {
440                     // Closest has the lowest distance
441                     testDistance = distance;
442                     closestVertex.set(pC.x + vectors[i].x, pC.y + vectors[i].y);
443                 }
444             }
445 
446             // Get the normal vector from the poly to the circle
447             normalAxis.set(closestVertex.x - cC.x, closestVertex.y - cC.y);
448             normalAxis.normalize();	// set length to 1
449 
450             // We'll remember this so that we can use it in the collision data
451             unitVec = R.math.Vector2D.create(normalAxis);
452 
453             // Project the polygon's points against the circle
454             min1 = normalAxis.dot(vectors[0]);
455             max1 = min1;
456 
457             for (j = 1; j < vectors.length; j++) {
458                 test = normalAxis.dot(vectors[j]);
459                 if (test < min1) min1 = test;
460                 if (test > max1) max1 = test;
461             }
462 
463             // Project the circle
464             max2 = radius;
465             min2 = -radius;
466 
467             // Offset the polygon's max/min
468             offset = normalAxis.dot(vectorOffset);
469             min1 += offset;
470             max1 += offset;
471 
472             // First test
473             test1 = min1 - max2;
474             test2 = min2 - max1;
475 
476             if (test1 > 0 || test2 > 0) {
477                 // Clean up before returning
478                 unitVec.destroy();
479                 normalAxis.destroy();
480                 vectorOffset.destroy();
481                 closestVertex.destroy();
482 
483                 // Not colliding
484                 return null;
485             }
486 
487             // Now project the circle against the polygon
488             for (i = 0; i < vectors.length; i++) {
489                 R.components.collision.Convex.findNormalAxis(normalAxis, vectors, i);
490                 min1 = normalAxis.dot(vectors[0]);
491                 max1 = min1;
492 
493                 for (j = 1; j < vectors.length; j++) {
494                     test = normalAxis.dot(vectors[j]);
495                     if (test < min1) min1 = test;
496                     if (test > max1) max1 = test;
497                 }
498 
499                 // Project the circle
500                 max2 = radius;
501                 min2 = -radius;
502 
503                 // offset points
504                 offset = normalAxis.dot(vectorOffset);
505                 min1 += offset;
506                 max1 += offset;
507 
508                 // Second Test
509                 test1 = min1 - max2;
510                 test2 = min2 - max1;
511 
512                 if (test1 > 0 || test2 > 0) {
513                     // Clean up before returning
514                     unitVec.destroy();
515                     normalAxis.destroy();
516                     vectorOffset.destroy();
517                     closestVertex.destroy();
518 
519                     // Not colliding
520                     return null;
521                 }
522             }
523 
524             // The overlap is the nearest poly point to the center of the circle, minus the radius
525             var c = R.math.Vector2D.create(center);
526             overlap = c.sub(closestVertex).len();
527             overlap -= radius;
528 
529             // If we got here, there is a collision
530             var cData = R.struct.CollisionData.create(overlap,
531                 unitVec,
532                 shape1.getGameObject(),
533                 shape2.getGameObject(),
534                 R.math.Vector2D.create(unitVec.x * overlap,
535                     unitVec.y * overlap),
536                 time,
537                 dt);
538 
539             // Clean up before returning
540             c.destroy();
541             vectorOffset.destroy();
542             closestVertex.destroy();
543 
544             // Return the collision data
545             return cData;
546         }
547     });
548 };