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 };