以下图的两个Box为例
1) 先是分别以Box_A和Box_B的模型空间坐标轴为分离轴，求出在轴上的投影重叠长度，判断是否相交。
Collide.cpp的Collide函数
// Setup Vec2 hA = 0.5f * bodyA->width; Vec2 hB = 0.5f * bodyB->width; Vec2 posA = bodyA->position; Vec2 posB = bodyB->position; Mat22 RotA(bodyA->rotation), RotB(bodyB->rotation); //localToWorld Mat22 RotAT = RotA.Transpose(); //转置矩阵(等于逆矩阵), worldToLocal_A Vec2 dp = posB - posA; //中心连线向量 Vec2 dA = RotAT * dp; //中心连线向量, 在boxA的模型空间x, y轴上的投影 Mat22 C = RotAT * RotB; //localBToLocalA, 先把B内的local转为world, 然后world再转成A内的local Mat22 absC = Abs(C); // Box A faces Vec2 faceA = Abs(dA) - hA - absC * hB; if (faceA.x > 0.0f || faceA.y > 0.0f) return 0; Mat22 RotBT = RotB.Transpose(); //worldToLocal_B Vec2 dB = RotBT * dp; //中心连线向量, 在boxB的模型空间x, y轴上的投影 Mat22 absCT = absC.Transpose(); //localAToLocalB // Box B faces Vec2 faceB = Abs(dB) - absCT * hA - hB; if (faceB.x > 0.0f || faceB.y > 0.0f) return 0;
判断依据：
1-1) 相对Box_A的模型空间时：
a) 如果中心连线在Box_A模型空间x轴上的投影 > Box_A的halfSize.x + Box_B相对Box_A模型空间包围盒的halfSize.x，则它们在x方向不相交；
b) 如果中心连线在Box_A模型空间y轴上的投影 > Box_A的halfSize.y + Box_B相对Box_A模型空间包围盒的halfSize.y，则它们在y方向不相交；
Box_A模型空间x轴方向不相交的情况
相交的情况
1-2) 相对Box_B的模型空间时：
a) 如果中心连线在Box_B模型空间x轴上的投影 > Box_B的halfSize.x + Box_A相对Box_B模型空间包围盒的halfSize.x，则它们在x方向不相交；
b) 如果中心连线在Box_B模型空间y轴上的投影 > Box_B的halfSize.y + Box_A相对Box_B模型空间包围盒的halfSize.y，则它们在y方向不相交；
相交的情况
2) 根据最小重叠区域确定分离轴和分离长度。
// Find best axis Axis axis; float separation; Vec2 normal; // Box A faces axis = FACE_A_X; separation = faceA.x; normal = dA.x > 0.0f ? RotA.col1 : -RotA.col1; //B在A的右侧用x轴正方形，左侧用x轴负方向 const float relativeTol = 0.95f; const float absoluteTol = 0.01f; //找最小重叠区域长度: 即穿透深度更浅的(这边是负数, 所以用>) if (faceA.y > relativeTol * separation + absoluteTol * hA.y) //y方向的穿透深度, 比x方向的穿透深度95%-半高的1%更浅 { axis = FACE_A_Y; separation = faceA.y; normal = dA.y > 0.0f ? RotA.col2 : -RotA.col2; //B在A的上方用y轴正方向，下方用y轴负反向 } // Box B faces if (faceB.x > relativeTol * separation + absoluteTol * hB.x) { axis = FACE_B_X; separation = faceB.x; normal = dB.x > 0.0f ? RotB.col1 : -RotB.col1; } if (faceB.y > relativeTol * separation + absoluteTol * hB.y) { axis = FACE_B_Y; separation = faceB.y; normal = dB.y > 0.0f ? RotB.col2 : -RotB.col2; }
最小重叠区域在Box_A模型空间的x轴上，分离距离为faceA.x
3) 确定本次可能发生碰撞的点和关联边。
// Setup clipping plane data based on the separating axis Vec2 frontNormal, sideNormal; ClipVertex incidentEdge[2]; float front, negSide, posSide; char negEdge, posEdge; // Compute the clipping lines and the line segment to be clipped. switch (axis) { case FACE_A_X: //分离距离在BoxA的模型空间x轴方向上 { frontNormal = normal; //分离方向: 模型空间的x轴正或负方向 ComputeIncidentEdge(incidentEdge, hB, posB, RotB, frontNormal); front = Dot(posA, frontNormal) + hA.x; sideNormal = RotA.col2; //另一个方向, 模型空间y轴正方向 float side = Dot(posA, sideNormal); negSide = -side + hA.y; posSide = side + hA.y; negEdge = EDGE3; posEdge = EDGE1; } break; case FACE_A_Y: { frontNormal = normal; front = Dot(posA, frontNormal) + hA.y; sideNormal = RotA.col1; //另一个方向, 模型空间x轴正方向 float side = Dot(posA, sideNormal); negSide = -side + hA.x; //Box的left边mid的abs(localX) posSide = side + hA.x; //Box的right边mid的localX值 negEdge = EDGE2; posEdge = EDGE4; ComputeIncidentEdge(incidentEdge, hB, posB, RotB, frontNormal); } break; case FACE_B_X: { frontNormal = -normal; front = Dot(posB, frontNormal) + hB.x; sideNormal = RotB.col2; float side = Dot(posB, sideNormal); negSide = -side + hB.y; posSide = side + hB.y; negEdge = EDGE3; posEdge = EDGE1; ComputeIncidentEdge(incidentEdge, hA, posA, RotA, frontNormal); } break; case FACE_B_Y: { frontNormal = -normal; front = Dot(posB, frontNormal) + hB.y; sideNormal = RotB.col1; float side = Dot(posB, sideNormal); negSide = -side + hB.x; posSide = side + hB.x; negEdge = EDGE2; posEdge = EDGE4; ComputeIncidentEdge(incidentEdge, hA, posA, RotA, frontNormal); } break; }
static void ComputeIncidentEdge(ClipVertex resultCV[2], const Vec2& halfSize, const Vec2& pos, const Mat22& Rot, const Vec2& normal) { // The normal is from the reference box. Convert it // to the incident boxe's frame and flip sign. Mat22 RotT = Rot.Transpose(); //worldToLocal_B Vec2 n = -(RotT * normal); //分离向量转换到BoxB的模型空间下; 负号是为了从Box_B指向Box_A Vec2 nAbs = Abs(n); //将模型空间的坐标轴按角度分成4块区域, (-45, 45), [45, 135], (135, -135), [-135, -45] if (nAbs.x > nAbs.y) //在1,3区域 { if (Sign(n.x) > 0.0f) //在1区域则 { resultCV[0].v.Set(halfSize.x, -halfSize.y); //right-bottom resultCV[0].fp.e.inEdge2 = EDGE3; resultCV[0].fp.e.outEdge2 = EDGE4; resultCV[1].v.Set(halfSize.x, halfSize.y); //right-top resultCV[1].fp.e.inEdge2 = EDGE4; resultCV[1].fp.e.outEdge2 = EDGE1; } else //在3区域 { resultCV[0].v.Set(-halfSize.x, halfSize.y); //left-top resultCV[0].fp.e.inEdge2 = EDGE1; resultCV[0].fp.e.outEdge2 = EDGE2; resultCV[1].v.Set(-halfSize.x, -halfSize.y); //left-bottom resultCV[1].fp.e.inEdge2 = EDGE2; resultCV[1].fp.e.outEdge2 = EDGE3; } } else //在2,4区域 { if (Sign(n.y) > 0.0f) //在2区域 { resultCV[0].v.Set(halfSize.x, halfSize.y); resultCV[0].fp.e.inEdge2 = EDGE4; resultCV[0].fp.e.outEdge2 = EDGE1; resultCV[1].v.Set(-halfSize.x, halfSize.y); resultCV[1].fp.e.inEdge2 = EDGE1; resultCV[1].fp.e.outEdge2 = EDGE2; } else //在4区域 { resultCV[0].v.Set(-halfSize.x, -halfSize.y); resultCV[0].fp.e.inEdge2 = EDGE2; resultCV[0].fp.e.outEdge2 = EDGE3; resultCV[1].v.Set(halfSize.x, -halfSize.y); resultCV[1].fp.e.inEdge2 = EDGE3; resultCV[1].fp.e.outEdge2 = EDGE4; } } //转为世界坐标 resultCV[0].v = pos + Rot * resultCV[0].v; resultCV[1].v = pos + Rot * resultCV[1].v; }
3) 检查会发生碰撞的点，是否在主Box的边界外，如果在边界外，则进行剪切，并更新为新的可能碰撞点。
int np; ClipVertex clipPoints1[2]; // Clip to box side 1 np = ClipSegmentToLine(clipPoints1, incidentEdge, -sideNormal, negSide, negEdge); if (np < 2) return 0; ClipVertex clipPoints2[2]; // Clip to negative box side 1 np = ClipSegmentToLine(clipPoints2, clipPoints1, sideNormal, posSide, posEdge); if (np < 2) return 0;
int ClipSegmentToLine(ClipVertex vOut[2], ClipVertex vIn[2], const Vec2& normal, float offset, char clipEdge) { // Start with no output points int numOut = 0; // Calculate the distance of end points to the line float distance0 = Dot(normal, vIn[0].v) - offset; float distance1 = Dot(normal, vIn[1].v) - offset; // If the points are behind the plane if (distance0 <= 0.0f) vOut[numOut++] = vIn[0]; if (distance1 <= 0.0f) vOut[numOut++] = vIn[1]; // If the points are on different sides of the plane if (distance0 * distance1 < 0.0f) { // Find intersection point of edge and plane float interp = distance0 / (distance0 - distance1); //比例值 vOut[numOut].v = vIn[0].v + interp * (vIn[1].v - vIn[0].v); if (distance0 > 0.0f) { vOut[numOut].fp = vIn[0].fp; vOut[numOut].fp.e.inEdge1 = clipEdge; vOut[numOut].fp.e.inEdge2 = NO_EDGE; } else { vOut[numOut].fp = vIn[1].fp; vOut[numOut].fp.e.outEdge1 = clipEdge; vOut[numOut].fp.e.outEdge2 = NO_EDGE; } ++numOut; } return numOut; }
-sideNormal方向
sideNormal方向
4) 计算出实际的碰撞点（对于发生了穿透的情况，就是刚碰到还没穿透时的那个点）。
int numContacts = 0; for (int i = 0; i < 2; ++i) { float separation = Dot(frontNormal, clipPoints2[i].v) - front; if (separation <= 0) { contacts[numContacts].separation = separation; contacts[numContacts].normal = normal; // slide contact point onto reference face (easy to cull) contacts[numContacts].position = clipPoints2[i].v - separation * frontNormal; //刚碰到时的接触点 /* contacts[numContacts].feature = clipPoints2[i].fp; if (axis == FACE_B_X || axis == FACE_B_Y) Flip(contacts[numContacts].feature); */ ++numContacts; } }
参考
Box2D-Lite源码阅读笔记(6)_front normal的作用-CSDN博客
Box2D-Lite源码阅读笔记(7)_box2d lite-CSDN博客
Box2D-Lite源码阅读笔记(8)_clipedge函数-CSDN博客
box2d.org/files/ErinCatto_SequentialImpulses_GDC2006.pdf