1/* 2 * Copyright (c) 2007-2009 Erin Catto http://www.box2d.org 3 * 4 * This software is provided 'as-is', without any express or implied 5 * warranty. In no event will the authors be held liable for any damages 6 * arising from the use of this software. 7 * Permission is granted to anyone to use this software for any purpose, 8 * including commercial applications, and to alter it and redistribute it 9 * freely, subject to the following restrictions: 10 * 1. The origin of this software must not be misrepresented; you must not 11 * claim that you wrote the original software. If you use this software 12 * in a product, an acknowledgment in the product documentation would be 13 * appreciated but is not required. 14 * 2. Altered source versions must be plainly marked as such, and must not be 15 * misrepresented as being the original software. 16 * 3. This notice may not be removed or altered from any source distribution. 17 */ 18 19#include <Box2D/Collision/b2Collision.h> 20#include <Box2D/Collision/Shapes/b2CircleShape.h> 21#include <Box2D/Collision/Shapes/b2EdgeShape.h> 22#include <Box2D/Collision/Shapes/b2PolygonShape.h> 23 24 25// Compute contact points for edge versus circle. 26// This accounts for edge connectivity. 27void b2CollideEdgeAndCircle(b2Manifold* manifold, 28 const b2EdgeShape* edgeA, const b2Transform& xfA, 29 const b2CircleShape* circleB, const b2Transform& xfB) 30{ 31 manifold->pointCount = 0; 32 33 // Compute circle in frame of edge 34 b2Vec2 Q = b2MulT(xfA, b2Mul(xfB, circleB->m_p)); 35 36 b2Vec2 A = edgeA->m_vertex1, B = edgeA->m_vertex2; 37 b2Vec2 e = B - A; 38 39 // Barycentric coordinates 40 float32 u = b2Dot(e, B - Q); 41 float32 v = b2Dot(e, Q - A); 42 43 float32 radius = edgeA->m_radius + circleB->m_radius; 44 45 b2ContactFeature cf; 46 cf.indexB = 0; 47 cf.typeB = b2ContactFeature::e_vertex; 48 49 // Region A 50 if (v <= 0.0f) 51 { 52 b2Vec2 P = A; 53 b2Vec2 d = Q - P; 54 float32 dd = b2Dot(d, d); 55 if (dd > radius * radius) 56 { 57 return; 58 } 59 60 // Is there an edge connected to A? 61 if (edgeA->m_hasVertex0) 62 { 63 b2Vec2 A1 = edgeA->m_vertex0; 64 b2Vec2 B1 = A; 65 b2Vec2 e1 = B1 - A1; 66 float32 u1 = b2Dot(e1, B1 - Q); 67 68 // Is the circle in Region AB of the previous edge? 69 if (u1 > 0.0f) 70 { 71 return; 72 } 73 } 74 75 cf.indexA = 0; 76 cf.typeA = b2ContactFeature::e_vertex; 77 manifold->pointCount = 1; 78 manifold->type = b2Manifold::e_circles; 79 manifold->localNormal.SetZero(); 80 manifold->localPoint = P; 81 manifold->points[0].id.key = 0; 82 manifold->points[0].id.cf = cf; 83 manifold->points[0].localPoint = circleB->m_p; 84 return; 85 } 86 87 // Region B 88 if (u <= 0.0f) 89 { 90 b2Vec2 P = B; 91 b2Vec2 d = Q - P; 92 float32 dd = b2Dot(d, d); 93 if (dd > radius * radius) 94 { 95 return; 96 } 97 98 // Is there an edge connected to B? 99 if (edgeA->m_hasVertex3) 100 { 101 b2Vec2 B2 = edgeA->m_vertex3; 102 b2Vec2 A2 = B; 103 b2Vec2 e2 = B2 - A2; 104 float32 v2 = b2Dot(e2, Q - A2); 105 106 // Is the circle in Region AB of the next edge? 107 if (v2 > 0.0f) 108 { 109 return; 110 } 111 } 112 113 cf.indexA = 1; 114 cf.typeA = b2ContactFeature::e_vertex; 115 manifold->pointCount = 1; 116 manifold->type = b2Manifold::e_circles; 117 manifold->localNormal.SetZero(); 118 manifold->localPoint = P; 119 manifold->points[0].id.key = 0; 120 manifold->points[0].id.cf = cf; 121 manifold->points[0].localPoint = circleB->m_p; 122 return; 123 } 124 125 // Region AB 126 float32 den = b2Dot(e, e); 127 b2Assert(den > 0.0f); 128 b2Vec2 P = (1.0f / den) * (u * A + v * B); 129 b2Vec2 d = Q - P; 130 float32 dd = b2Dot(d, d); 131 if (dd > radius * radius) 132 { 133 return; 134 } 135 136 b2Vec2 n(-e.y, e.x); 137 if (b2Dot(n, Q - A) < 0.0f) 138 { 139 n.Set(-n.x, -n.y); 140 } 141 n.Normalize(); 142 143 cf.indexA = 0; 144 cf.typeA = b2ContactFeature::e_face; 145 manifold->pointCount = 1; 146 manifold->type = b2Manifold::e_faceA; 147 manifold->localNormal = n; 148 manifold->localPoint = A; 149 manifold->points[0].id.key = 0; 150 manifold->points[0].id.cf = cf; 151 manifold->points[0].localPoint = circleB->m_p; 152} 153 154// This structure is used to keep track of the best separating axis. 155struct b2EPAxis 156{ 157 enum Type 158 { 159 e_unknown, 160 e_edgeA, 161 e_edgeB 162 }; 163 164 Type type; 165 int32 index; 166 float32 separation; 167}; 168 169// This holds polygon B expressed in frame A. 170struct b2TempPolygon 171{ 172 b2Vec2 vertices[b2_maxPolygonVertices]; 173 b2Vec2 normals[b2_maxPolygonVertices]; 174 int32 count; 175}; 176 177// Reference face used for clipping 178struct b2ReferenceFace 179{ 180 int32 i1, i2; 181 182 b2Vec2 v1, v2; 183 184 b2Vec2 normal; 185 186 b2Vec2 sideNormal1; 187 float32 sideOffset1; 188 189 b2Vec2 sideNormal2; 190 float32 sideOffset2; 191}; 192 193// This class collides and edge and a polygon, taking into account edge adjacency. 194struct b2EPCollider 195{ 196 void Collide(b2Manifold* manifold, const b2EdgeShape* edgeA, const b2Transform& xfA, 197 const b2PolygonShape* polygonB, const b2Transform& xfB); 198 b2EPAxis ComputeEdgeSeparation(); 199 b2EPAxis ComputePolygonSeparation(); 200 201 enum VertexType 202 { 203 e_isolated, 204 e_concave, 205 e_convex 206 }; 207 208 b2TempPolygon m_polygonB; 209 210 b2Transform m_xf; 211 b2Vec2 m_centroidB; 212 b2Vec2 m_v0, m_v1, m_v2, m_v3; 213 b2Vec2 m_normal0, m_normal1, m_normal2; 214 b2Vec2 m_normal; 215 VertexType m_type1, m_type2; 216 b2Vec2 m_lowerLimit, m_upperLimit; 217 float32 m_radius; 218 bool m_front; 219}; 220 221// Algorithm: 222// 1. Classify v1 and v2 223// 2. Classify polygon centroid as front or back 224// 3. Flip normal if necessary 225// 4. Initialize normal range to [-pi, pi] about face normal 226// 5. Adjust normal range according to adjacent edges 227// 6. Visit each separating axes, only accept axes within the range 228// 7. Return if _any_ axis indicates separation 229// 8. Clip 230void b2EPCollider::Collide(b2Manifold* manifold, const b2EdgeShape* edgeA, const b2Transform& xfA, 231 const b2PolygonShape* polygonB, const b2Transform& xfB) 232{ 233 m_xf = b2MulT(xfA, xfB); 234 235 m_centroidB = b2Mul(m_xf, polygonB->m_centroid); 236 237 m_v0 = edgeA->m_vertex0; 238 m_v1 = edgeA->m_vertex1; 239 m_v2 = edgeA->m_vertex2; 240 m_v3 = edgeA->m_vertex3; 241 242 bool hasVertex0 = edgeA->m_hasVertex0; 243 bool hasVertex3 = edgeA->m_hasVertex3; 244 245 b2Vec2 edge1 = m_v2 - m_v1; 246 edge1.Normalize(); 247 m_normal1.Set(edge1.y, -edge1.x); 248 float32 offset1 = b2Dot(m_normal1, m_centroidB - m_v1); 249 float32 offset0 = 0.0f, offset2 = 0.0f; 250 bool convex1 = false, convex2 = false; 251 252 // Is there a preceding edge? 253 if (hasVertex0) 254 { 255 b2Vec2 edge0 = m_v1 - m_v0; 256 edge0.Normalize(); 257 m_normal0.Set(edge0.y, -edge0.x); 258 convex1 = b2Cross(edge0, edge1) >= 0.0f; 259 offset0 = b2Dot(m_normal0, m_centroidB - m_v0); 260 } 261 262 // Is there a following edge? 263 if (hasVertex3) 264 { 265 b2Vec2 edge2 = m_v3 - m_v2; 266 edge2.Normalize(); 267 m_normal2.Set(edge2.y, -edge2.x); 268 convex2 = b2Cross(edge1, edge2) > 0.0f; 269 offset2 = b2Dot(m_normal2, m_centroidB - m_v2); 270 } 271 272 // Determine front or back collision. Determine collision normal limits. 273 if (hasVertex0 && hasVertex3) 274 { 275 if (convex1 && convex2) 276 { 277 m_front = offset0 >= 0.0f || offset1 >= 0.0f || offset2 >= 0.0f; 278 if (m_front) 279 { 280 m_normal = m_normal1; 281 m_lowerLimit = m_normal0; 282 m_upperLimit = m_normal2; 283 } 284 else 285 { 286 m_normal = -m_normal1; 287 m_lowerLimit = -m_normal1; 288 m_upperLimit = -m_normal1; 289 } 290 } 291 else if (convex1) 292 { 293 m_front = offset0 >= 0.0f || (offset1 >= 0.0f && offset2 >= 0.0f); 294 if (m_front) 295 { 296 m_normal = m_normal1; 297 m_lowerLimit = m_normal0; 298 m_upperLimit = m_normal1; 299 } 300 else 301 { 302 m_normal = -m_normal1; 303 m_lowerLimit = -m_normal2; 304 m_upperLimit = -m_normal1; 305 } 306 } 307 else if (convex2) 308 { 309 m_front = offset2 >= 0.0f || (offset0 >= 0.0f && offset1 >= 0.0f); 310 if (m_front) 311 { 312 m_normal = m_normal1; 313 m_lowerLimit = m_normal1; 314 m_upperLimit = m_normal2; 315 } 316 else 317 { 318 m_normal = -m_normal1; 319 m_lowerLimit = -m_normal1; 320 m_upperLimit = -m_normal0; 321 } 322 } 323 else 324 { 325 m_front = offset0 >= 0.0f && offset1 >= 0.0f && offset2 >= 0.0f; 326 if (m_front) 327 { 328 m_normal = m_normal1; 329 m_lowerLimit = m_normal1; 330 m_upperLimit = m_normal1; 331 } 332 else 333 { 334 m_normal = -m_normal1; 335 m_lowerLimit = -m_normal2; 336 m_upperLimit = -m_normal0; 337 } 338 } 339 } 340 else if (hasVertex0) 341 { 342 if (convex1) 343 { 344 m_front = offset0 >= 0.0f || offset1 >= 0.0f; 345 if (m_front) 346 { 347 m_normal = m_normal1; 348 m_lowerLimit = m_normal0; 349 m_upperLimit = -m_normal1; 350 } 351 else 352 { 353 m_normal = -m_normal1; 354 m_lowerLimit = m_normal1; 355 m_upperLimit = -m_normal1; 356 } 357 } 358 else 359 { 360 m_front = offset0 >= 0.0f && offset1 >= 0.0f; 361 if (m_front) 362 { 363 m_normal = m_normal1; 364 m_lowerLimit = m_normal1; 365 m_upperLimit = -m_normal1; 366 } 367 else 368 { 369 m_normal = -m_normal1; 370 m_lowerLimit = m_normal1; 371 m_upperLimit = -m_normal0; 372 } 373 } 374 } 375 else if (hasVertex3) 376 { 377 if (convex2) 378 { 379 m_front = offset1 >= 0.0f || offset2 >= 0.0f; 380 if (m_front) 381 { 382 m_normal = m_normal1; 383 m_lowerLimit = -m_normal1; 384 m_upperLimit = m_normal2; 385 } 386 else 387 { 388 m_normal = -m_normal1; 389 m_lowerLimit = -m_normal1; 390 m_upperLimit = m_normal1; 391 } 392 } 393 else 394 { 395 m_front = offset1 >= 0.0f && offset2 >= 0.0f; 396 if (m_front) 397 { 398 m_normal = m_normal1; 399 m_lowerLimit = -m_normal1; 400 m_upperLimit = m_normal1; 401 } 402 else 403 { 404 m_normal = -m_normal1; 405 m_lowerLimit = -m_normal2; 406 m_upperLimit = m_normal1; 407 } 408 } 409 } 410 else 411 { 412 m_front = offset1 >= 0.0f; 413 if (m_front) 414 { 415 m_normal = m_normal1; 416 m_lowerLimit = -m_normal1; 417 m_upperLimit = -m_normal1; 418 } 419 else 420 { 421 m_normal = -m_normal1; 422 m_lowerLimit = m_normal1; 423 m_upperLimit = m_normal1; 424 } 425 } 426 427 // Get polygonB in frameA 428 m_polygonB.count = polygonB->m_count; 429 for (int32 i = 0; i < polygonB->m_count; ++i) 430 { 431 m_polygonB.vertices[i] = b2Mul(m_xf, polygonB->m_vertices[i]); 432 m_polygonB.normals[i] = b2Mul(m_xf.q, polygonB->m_normals[i]); 433 } 434 435 m_radius = 2.0f * b2_polygonRadius; 436 437 manifold->pointCount = 0; 438 439 b2EPAxis edgeAxis = ComputeEdgeSeparation(); 440 441 // If no valid normal can be found than this edge should not collide. 442 if (edgeAxis.type == b2EPAxis::e_unknown) 443 { 444 return; 445 } 446 447 if (edgeAxis.separation > m_radius) 448 { 449 return; 450 } 451 452 b2EPAxis polygonAxis = ComputePolygonSeparation(); 453 if (polygonAxis.type != b2EPAxis::e_unknown && polygonAxis.separation > m_radius) 454 { 455 return; 456 } 457 458 // Use hysteresis for jitter reduction. 459 const float32 k_relativeTol = 0.98f; 460 const float32 k_absoluteTol = 0.001f; 461 462 b2EPAxis primaryAxis; 463 if (polygonAxis.type == b2EPAxis::e_unknown) 464 { 465 primaryAxis = edgeAxis; 466 } 467 else if (polygonAxis.separation > k_relativeTol * edgeAxis.separation + k_absoluteTol) 468 { 469 primaryAxis = polygonAxis; 470 } 471 else 472 { 473 primaryAxis = edgeAxis; 474 } 475 476 b2ClipVertex ie[2]; 477 b2ReferenceFace rf; 478 if (primaryAxis.type == b2EPAxis::e_edgeA) 479 { 480 manifold->type = b2Manifold::e_faceA; 481 482 // Search for the polygon normal that is most anti-parallel to the edge normal. 483 int32 bestIndex = 0; 484 float32 bestValue = b2Dot(m_normal, m_polygonB.normals[0]); 485 for (int32 i = 1; i < m_polygonB.count; ++i) 486 { 487 float32 value = b2Dot(m_normal, m_polygonB.normals[i]); 488 if (value < bestValue) 489 { 490 bestValue = value; 491 bestIndex = i; 492 } 493 } 494 495 int32 i1 = bestIndex; 496 int32 i2 = i1 + 1 < m_polygonB.count ? i1 + 1 : 0; 497 498 ie[0].v = m_polygonB.vertices[i1]; 499 ie[0].id.cf.indexA = 0; 500 ie[0].id.cf.indexB = static_cast<uint8>(i1); 501 ie[0].id.cf.typeA = b2ContactFeature::e_face; 502 ie[0].id.cf.typeB = b2ContactFeature::e_vertex; 503 504 ie[1].v = m_polygonB.vertices[i2]; 505 ie[1].id.cf.indexA = 0; 506 ie[1].id.cf.indexB = static_cast<uint8>(i2); 507 ie[1].id.cf.typeA = b2ContactFeature::e_face; 508 ie[1].id.cf.typeB = b2ContactFeature::e_vertex; 509 510 if (m_front) 511 { 512 rf.i1 = 0; 513 rf.i2 = 1; 514 rf.v1 = m_v1; 515 rf.v2 = m_v2; 516 rf.normal = m_normal1; 517 } 518 else 519 { 520 rf.i1 = 1; 521 rf.i2 = 0; 522 rf.v1 = m_v2; 523 rf.v2 = m_v1; 524 rf.normal = -m_normal1; 525 } 526 } 527 else 528 { 529 manifold->type = b2Manifold::e_faceB; 530 531 ie[0].v = m_v1; 532 ie[0].id.cf.indexA = 0; 533 ie[0].id.cf.indexB = static_cast<uint8>(primaryAxis.index); 534 ie[0].id.cf.typeA = b2ContactFeature::e_vertex; 535 ie[0].id.cf.typeB = b2ContactFeature::e_face; 536 537 ie[1].v = m_v2; 538 ie[1].id.cf.indexA = 0; 539 ie[1].id.cf.indexB = static_cast<uint8>(primaryAxis.index); 540 ie[1].id.cf.typeA = b2ContactFeature::e_vertex; 541 ie[1].id.cf.typeB = b2ContactFeature::e_face; 542 543 rf.i1 = primaryAxis.index; 544 rf.i2 = rf.i1 + 1 < m_polygonB.count ? rf.i1 + 1 : 0; 545 rf.v1 = m_polygonB.vertices[rf.i1]; 546 rf.v2 = m_polygonB.vertices[rf.i2]; 547 rf.normal = m_polygonB.normals[rf.i1]; 548 } 549 550 rf.sideNormal1.Set(rf.normal.y, -rf.normal.x); 551 rf.sideNormal2 = -rf.sideNormal1; 552 rf.sideOffset1 = b2Dot(rf.sideNormal1, rf.v1); 553 rf.sideOffset2 = b2Dot(rf.sideNormal2, rf.v2); 554 555 // Clip incident edge against extruded edge1 side edges. 556 b2ClipVertex clipPoints1[2]; 557 b2ClipVertex clipPoints2[2]; 558 int32 np; 559 560 // Clip to box side 1 561 np = b2ClipSegmentToLine(clipPoints1, ie, rf.sideNormal1, rf.sideOffset1, rf.i1); 562 563 if (np < b2_maxManifoldPoints) 564 { 565 return; 566 } 567 568 // Clip to negative box side 1 569 np = b2ClipSegmentToLine(clipPoints2, clipPoints1, rf.sideNormal2, rf.sideOffset2, rf.i2); 570 571 if (np < b2_maxManifoldPoints) 572 { 573 return; 574 } 575 576 // Now clipPoints2 contains the clipped points. 577 if (primaryAxis.type == b2EPAxis::e_edgeA) 578 { 579 manifold->localNormal = rf.normal; 580 manifold->localPoint = rf.v1; 581 } 582 else 583 { 584 manifold->localNormal = polygonB->m_normals[rf.i1]; 585 manifold->localPoint = polygonB->m_vertices[rf.i1]; 586 } 587 588 int32 pointCount = 0; 589 for (int32 i = 0; i < b2_maxManifoldPoints; ++i) 590 { 591 float32 separation; 592 593 separation = b2Dot(rf.normal, clipPoints2[i].v - rf.v1); 594 595 if (separation <= m_radius) 596 { 597 b2ManifoldPoint* cp = manifold->points + pointCount; 598 599 if (primaryAxis.type == b2EPAxis::e_edgeA) 600 { 601 cp->localPoint = b2MulT(m_xf, clipPoints2[i].v); 602 cp->id = clipPoints2[i].id; 603 } 604 else 605 { 606 cp->localPoint = clipPoints2[i].v; 607 cp->id.cf.typeA = clipPoints2[i].id.cf.typeB; 608 cp->id.cf.typeB = clipPoints2[i].id.cf.typeA; 609 cp->id.cf.indexA = clipPoints2[i].id.cf.indexB; 610 cp->id.cf.indexB = clipPoints2[i].id.cf.indexA; 611 } 612 613 ++pointCount; 614 } 615 } 616 617 manifold->pointCount = pointCount; 618} 619 620b2EPAxis b2EPCollider::ComputeEdgeSeparation() 621{ 622 b2EPAxis axis; 623 axis.type = b2EPAxis::e_edgeA; 624 axis.index = m_front ? 0 : 1; 625 axis.separation = FLT_MAX; 626 627 for (int32 i = 0; i < m_polygonB.count; ++i) 628 { 629 float32 s = b2Dot(m_normal, m_polygonB.vertices[i] - m_v1); 630 if (s < axis.separation) 631 { 632 axis.separation = s; 633 } 634 } 635 636 return axis; 637} 638 639b2EPAxis b2EPCollider::ComputePolygonSeparation() 640{ 641 b2EPAxis axis; 642 axis.type = b2EPAxis::e_unknown; 643 axis.index = -1; 644 axis.separation = -FLT_MAX; 645 646 b2Vec2 perp(-m_normal.y, m_normal.x); 647 648 for (int32 i = 0; i < m_polygonB.count; ++i) 649 { 650 b2Vec2 n = -m_polygonB.normals[i]; 651 652 float32 s1 = b2Dot(n, m_polygonB.vertices[i] - m_v1); 653 float32 s2 = b2Dot(n, m_polygonB.vertices[i] - m_v2); 654 float32 s = b2Min(s1, s2); 655 656 if (s > m_radius) 657 { 658 // No collision 659 axis.type = b2EPAxis::e_edgeB; 660 axis.index = i; 661 axis.separation = s; 662 return axis; 663 } 664 665 // Adjacency 666 if (b2Dot(n, perp) >= 0.0f) 667 { 668 if (b2Dot(n - m_upperLimit, m_normal) < -b2_angularSlop) 669 { 670 continue; 671 } 672 } 673 else 674 { 675 if (b2Dot(n - m_lowerLimit, m_normal) < -b2_angularSlop) 676 { 677 continue; 678 } 679 } 680 681 if (s > axis.separation) 682 { 683 axis.type = b2EPAxis::e_edgeB; 684 axis.index = i; 685 axis.separation = s; 686 } 687 } 688 689 return axis; 690} 691 692void b2CollideEdgeAndPolygon( b2Manifold* manifold, 693 const b2EdgeShape* edgeA, const b2Transform& xfA, 694 const b2PolygonShape* polygonB, const b2Transform& xfB) 695{ 696 b2EPCollider collider; 697 collider.Collide(manifold, edgeA, xfA, polygonB, xfB); 698} 699