The article seems to have a really bad tune, it was back then me writing this and i learned a whole lot later on, i don't find this to be a decent article to follow through and i wouldn't recommend it anymore per se, i'm thinking of doing a complete rewrite of this with my own simplified implementation of it (which isn't perfect and contains errors, but would be quite good for understanding), it still contains some useful information however in case you're interested.
And the little rant has been removed since I've found it to be distracting and not helpful, i've learned that they have a good use for some other things, I still don't recommend the GJK + EPA combination however, but they have some useful uses.
Some helpful resources for the time being:
Dirk Gregorius, The Seperating Axis Test https://www.gdcvault.com/play/1017646/Physics-for-Game-Programmers-The
Dirk Gregorius, Implementing Quickhull https://www.gdcvault.com/play/1020606/Physics-for-Game-Programmers
Dirk Gregorius, Robust Contact Creation for Physics Simulation https://dev.gdcvault.com/play/1022193/Physics-for-Game-Programmers-Robust
before we begin, i want to thank Randy Gaul for his implementation that's hosted on github: https://github.com/RandyGaul/qu3e, which is what we're basing our article on on his OBB-OBB collision detection & resolution code
another thing i want to mention is that there's a discord server i want to recommend that's related to physics programming, where there are a bunch of experts in there that you could ask questions about various things physics related! they are cool to talk to, here's the link
- WARNING -
i would only recommend this article as a reference/learning case, you shouldn't implement exactly the way this collision code works since it contains tons and tons of optimizations that obfuscates the code and makes it significantly harder to understand and are very specific, the main goal here is to take inspiration from how it solves problems and hopefully useful as a decent guidance on what's going on behind this specific implementation
lately i've had a working game physics engine (thanks to various resources i've found and books), i wanted to explain various concepts of how one's game physics engine works internally, nowadays there's barely any good resource that really tries to explain things clearly and intuitively, and people on the other hand have a hard time making sense of them and building their own
especially resources not making intense use of motion media, where you can see things moving around frame-to-frame, it's really important because physics by itself, well, happens to be the study of motion, and things don't happen in a single time interval, in fact it happens over multiple time intervals, this alone makes a gigantic difference, reading a bunch of text and trying to make sense of them or seeing a graph is not enough (and don't get me wrong, there are people who make up motion media, just not enough), unlike in graphics programming where you could teach with a bunch of stand-still images because there's not much movement most of the time
and even then, geometry also gets even further in the way, it's usually the topic that gets brought up too
i'm planning on making a site teaching various physics & geometry concepts that are helpful in making a physics engine, may come out at some point
Randy Gaul's box-box collision code makes use of separating axis theorem (SAT) as a way to detect the separating axis to extract the normal and the depth, the trick here is to figure out which features that we used to compare (in this case, face-something and edge-edge overlaps), the face-something technique is inspired by Erin Catto's incident-reference clipping method, and the edge-edge uses the closest points between the two lines, that's all there is to them
now let's start from the top of the void q3BoxtoBox( q3Manifold* m, q3Box* a, q3Box* b ) function, here's the link to the source code: https://github.com/RandyGaul/qu3e/blob/master/src/collision/q3Collide.cpp#L480C1-L480C53
q3Transform atx = a->body->GetTransform( );
q3Transform btx = b->body->GetTransform( );
/* NOTE(Memresable):
we could safely ignore these since they are related to entity hierarchy
transformations and they don't help us much right now
q3Transform aL = a->local;
q3Transform bL = b->local;
atx = q3Mul( atx, aL );
btx = q3Mul( btx, bL );
*/
q3Vec3 eA = a->e;
q3Vec3 eB = b->e;the first lines of code are essentially getting the initial state of both bodies transforms
also along the extent from the center of bodies to the furthest corner of the box (eA and eB), which is shown in the following image (imagine it this way: x -> width, y -> height, z -> depth)
q3Transform type is essentially a struct that contains both position and rotation
struct q3Transform
{
q3Vec3 position;
q3Mat3 rotation;
};the reason for rotation being a 3x3 matrix instead of a quaternion is for the SAT phase, which we would explain in a little bit
// B's frame in A's space
q3Mat3 C = q3Transpose( atx.rotation ) * btx.rotation;here it's putting the B's space into A's local space using the transpose, rotation matrices are always orthogonal matrices, which means transposing them just reverses the orientation direction,
and it's the same as doing the inverse, so transpose(A) * A is just the identity matrix! just like inverse(A) * A
now in the following image, let's say we want to put blue box's orientation into purple box's local space of orientation, this is how it would look like
neat! here the purple box in the yellow area has it's local orientation, and it became an axis aligned box (AABB), and the blue one is oriented in purple's local space, the problem now turned from OBB-OBB to AABB-OBB, this alone significantly simplifies computations and complexity, so that's definitely a good reason why we're doing this!
we're going to be using that pattern quite a lot, so that's an important thing to remember
q3Mat3 absC;
bool parallel = false;
const r32 kCosTol = r32( 1.0e-6 );
for ( i32 i = 0; i < 3; ++i )
{
for ( i32 j = 0; j < 3; ++j )
{
r32 val = q3Abs( C[ i ][ j ] );
absC[ i ][ j ] = val;
if ( val + kCosTol >= r32( 1.0 ) )
parallel = true;
}
}now this next bit chunk of code is going to be a little tough to explain... but bare with me
here we're taking the absolute value of each scalar of the matrix, which seems like kind of a nonsensical move at first, and also if one of the axis are close or equal to one, then that means one of the axis is parallel which lets us avoid another 9 edge-edge tests completely, this is mainly related to face vs something collision resolution phase, but let's ignore that chunk of code for a second
// Vector from center A to center B in A's space
q3Vec3 t = q3MulT( atx.rotation, btx.position - atx.position );now the t vector is essentially a vector that goes from A to B in A's local space, it essentially looks like the following image
nothing fancy yet...
// a's x axis
s = q3Abs( t.x ) - (eA.x + q3Dot( absC.Column0( ), eB ));now this is where the fun starts, it's essentially saying how much both of the two bodies are separated or overlapping in A's x-axis, if q3Abs(t.x) is more than (eA.x + q3Dot( absC.Column0( ), eB )), then that means they are separating, otherwise overlapping like the following image (and you can see there's a gap and that indicates there's no overlap)
for the first part of the equation q3Abs(t.x), taking the absolute value of t.x is essentially trying to ignore the direction in the x-axis, and we don't really care about the other side of the box
essentially we have the positive side and the negative side of a box, the direction vector we're using here goes from positive to negative side
one side of a box's extent is a copy of the other side's extent, so technically we don't care at all, we just need the magnitude in the x-axis
now to the other part of the equation: eA.x + q3Dot( absC.Column0( ), eB ), what the hell does this mean?
when we said that the extents of both sides of the box being equal no matter what the orientation is, that's precisely what we cared about, we only care about one side of both two boxes, and to do this we just sum eA.x and eB.x, since they're just the extents of one side of a box, and then that's it, right?
well, for eA, it's already axis aligned in this case in it's local space, so we don't need to do much on that part, but eB still needs to be oriented, because if you look at the following image
magnitude is more than zero on the left side (axis aligned), but the magnitude is zero on the right side (oriented)
so we essentially just do q3Dot(C.Column0(), eB) to take orientation of B in A's local space into account
but that could give us a negative or positive value depending on B's orientation, and we said we don't care about one side or the other, so to fix this, we simply take the absolute value of all C scalar values to avoid this exact problem, which now explains why we have absC matrix in the first place! (and yes, we could've simply just taken the absolute value right away instead of constructing absC, but constructing absC ahead of time saves us tons of branch operations, which is great!)
if ( q3TrackFaceAxis( &aAxis, 0, s, &aMax, atx.rotation.ex, &nA ) )
return;the q3TrackFaceAxis(...) function main purpose is, well, to track axis...
more specifically this is what the function does
inline bool q3TrackFaceAxis( i32* axis, i32 n, r32 s, r32* sMax, const q3Vec3& normal, q3Vec3* axisNormal )
{
if ( s > r32( 0.0 ) )
return true;
if ( s > *sMax )
{
*sMax = s;
*axis = n;
*axisNormal = normal;
}
return false;
}r32 s is the separation amount, if it's positive then it's going to return as an indication that it's separated, otherwise overlapping
now if ( s > *sMax ) indicates if the overlapping amount is shorter in this axis than the previous axis, pick the axis normal along the axis index and the shorter overlapping magnitude
the reason being for taking the least amount of overlap is if you take a look at the following two images
the first image has an overlap in the y-axis, but the second image shows separation in x-axis, we mainly care about the least amount of overlap in an axis because that's the axis they're most likely penetrating in
// Face axis checks
// a's x axis
s = q3Abs( t.x ) - (eA.x + q3Dot( absC.Column0( ), eB ));
if ( q3TrackFaceAxis( &aAxis, 0, s, &aMax, atx.rotation.ex, &nA ) )
return;
// a's y axis
s = q3Abs( t.y ) - (eA.y + q3Dot( absC.Column1( ), eB ));
if ( q3TrackFaceAxis( &aAxis, 1, s, &aMax, atx.rotation.ey, &nA ) )
return;
// a's z axis
s = q3Abs( t.z ) - (eA.z + q3Dot( absC.Column2( ), eB ));
if ( q3TrackFaceAxis( &aAxis, 2, s, &aMax, atx.rotation.ez, &nA ) )
return;
// b's x axis
s = q3Abs( q3Dot( t, C.ex ) ) - (eB.x + q3Dot( absC.ex, eA ));
if ( q3TrackFaceAxis( &bAxis, 3, s, &bMax, btx.rotation.ex, &nB ) )
return;
...now it's just doing the same thing for each face axis in both A and B spaces
now to the edges, which basically does the exact same thing, but gets more complicated since this applies only to 3D and requires cross products
if ( !parallel )
{
// ...
}in case none of the axis of absC matrix is parallel, then we execute this branch, this is going to involve the edge-edge axis tests from each box, and to do this we simply take the cross product between every two oriented axis from each box, the reason we're doing this is to take both boxes orientations into account more aggressively, since the orientation of the faces alone aren't enough anymore in 3D
and an example would be like in the following image
here we're taking the cross product of both oriented x unit axis vectors, and this will produce an outer vector with it's magnitude being dependent on how orthogonal and long both vectors are (notice how it's not going to be a unit vector anymore at times because of the product, that would be taken into account later!), and then we use that to do SAT on it
there's even a table for the edge combinations (taken from Real-Time Collision Detection book, page 103)
it's perfectly fine to ignore it since we're already familiar with how face tests were done, it basically does the exact same thing but with more combination of axis like A's x oriented axis with B's oriented axis, and then A's x oriented axis with B's y oriented axis and so on, nothing to worry about at all here, just some boring extra details :)
// Edge axis checks
r32 rA;
r32 rB;
// Cross( a.x, b.x )
rA = eA.y * absC[ 0 ][ 2 ] + eA.z * absC[ 0 ][ 1 ];
rB = eB.y * absC[ 2 ][ 0 ] + eB.z * absC[ 1 ][ 0 ];
s = q3Abs( t.z * C[ 0 ][ 1 ] - t.y * C[ 0 ][ 2 ] ) - (rA + rB);
if ( q3TrackEdgeAxis( &eAxis, 6, s, &eMax, q3Vec3( r32( 0.0 ), -C[ 0 ][ 2 ], C[ 0 ][ 1 ] ), &nE ) )
return;not much to cover here...
now into the q3TrackEdgeAxis(...) function
inline bool q3TrackEdgeAxis( i32* axis, i32 n, r32 s, r32* sMax, const q3Vec3& normal, q3Vec3* axisNormal )
{
if ( s > r32( 0.0 ) )
return true;
r32 l = r32( 1.0 ) / q3Length( normal );
s *= l;
if ( s > *sMax )
{
*sMax = s;
*axis = n;
*axisNormal = normal * l;
}
return false;
}it's almost exactly the same as q3TrackFaceAxis(...) function, nothing different here except for the r32 l = ...; variable which we need to take into account, since we're dealing with weird combination of cross products and at times that wouldn't give us a unit sized s relative to the space we're colliding our objects in, so we "normalize" it and then it becomes a scalar that's in a normalized space
if that sounds nonsensical, say if you have non-unit axis 2x and you go in 4 steps in that axis, the 4 steps becomes 8 in comparison to the unit axis that our collided boxes are in, which is two times the magnitude and that's no good, so to fix this we basically "normalize" it by dividing the axis's length which then becomes 4 like normal, and the reason behind this is we're doing our collision calculations in an orthogonal unit space x(1, 0, 0) y(0, 1, 0) z(0, 0, 1) that we're originally in, so we wanna make sure s is normalized
and after the rest of the branch, that's it! we're done with the SAT testing phase \^o^/
now in case there was an overlap on all axes, we're going to try and select the features using the normal from SAT, then resolve the collision using either Erin Catto's incident-reference face clipping method or the edge-edge method depending on two conditions like the following
// Artificial axis bias to improve frame coherence
/* NOTE(Memresable): ignored
const r32 kRelTol = r32( 0.95 );
const r32 kAbsTol = r32( 0.01 );
*/
i32 axis;
r32 sMax;
q3Vec3 n;
r32 faceMax = q3Max( aMax, bMax );
if ( /* kRelTol * */ eMax > faceMax /* + kAbsTol */ )
{
axis = eAxis;
sMax = eMax;
n = nE;
}
else
{
if ( /* kRelTol * */ bMax > aMax /* + kAbsTol */)
{
axis = bAxis;
sMax = bMax;
n = nB;
}
else
{
axis = aAxis;
sMax = aMax;
n = nA;
}
}here i commented the frame coherence improvement parts because i don't really know what it really does and how it helps, i'm not sure where it even came from but i've tried to run the sim without them and it seemed to go on just fine, so... ¯\_(ツ)_/¯
and just a quick note, eAxis, aAxis and bAxis are integers, essentially the axis are numbered like so
-> 0-2 | A Axis
-> 3-5 | B Axis
-> 6-15 | Edge Axis
in case the minimum axis of penetration is eMax, then we get into that branch and we later go on to edge-edge collision resolution phase, otherwise in case of faceMax we select one of the two boxes as the reference box, so that the other box then becomes the incident, this is related to the incident-reference clipping phase we're going to be explaining later
if ( q3Dot( n, btx.position - atx.position ) < r32( 0.0 ) )
n = -n;in case the vector that goes from A to B is not facing in the same direction as the normal, reverse the normal direction
if ( axis < 6 )
{
// face-something collision resolution phase
// ...
}
else
{
// edge-edge collision resolution phase
// ...
}now in case we have axis less than 6, then it's going to involve face-something collision resolution phase, otherwise it's going to be edge-edge collision resolution phase
we're going to cover the face-something branch first
q3Transform rtx;
q3Transform itx;
q3Vec3 eR;
q3Vec3 eI;
bool flip;
if ( axis < 3 )
{
rtx = atx;
itx = btx;
eR = eA;
eI = eB;
flip = false;
}
else
{
rtx = btx;
itx = atx;
eR = eB;
eI = eA;
flip = true;
n = -n;
}at first, we're facing this chunk of code, essentially if the axis is from A's side then we choose A as the reference and B as the incident, or the opposite, we take both orientations and extents as well, however one thing that's weird here is the flip variable
we're going to come back to it in a second
// Compute reference and incident edge information necessary for clipping
q3ClipVertex incident[ 4 ];
q3ComputeIncidentFace( itx, eI, n, incident );
u8 clipEdges[ 4 ];
q3Mat3 basis;
q3Vec3 e;
q3ComputeReferenceEdgesAndBasis( eR, rtx, n, axis, clipEdges, &basis, &e );here we get the reference and incident faces that we want to clip
inside the q3ComputeIncidentFace(...) function, we find something interesting at first
n = -q3MulT( itx.rotation, n );
q3Vec3 absN = q3Abs( n );now this should explain why we had the flip variable there and flipped the normal in case B was the reference box
the reason being is if we've chosen B as the reference, A isn't going to be on the right side of the normal that's relative to B here, so the normal would be going in the opposite direction and the clipping routine would go wrong like so
we would've chosen the wrong "features" that we didn't want to use for clipping (and btw, features here means parts of the shape (faces, edges or vertices), in this case it's edges)
so to fix that, we temporarily flip the normal for the sake of making sure clipping doesn't go wrong, then later get it back to normal when we want to output the contact points
and now into selecting incident features
if ( absN.x > absN.y && absN.x > absN.z )
{
// ...
}
else if ( absN.y > absN.x && absN.y > absN.z )
{
// ...
}
else
{
// ...
}now let's imagine the following case
what we're interested in here is the most parallel axis that we could choose, in case absN.y is higher than absN.x and absN.z, then we know that Y must be the most parallel axis in which there will be two faces that are closely facing at each other at that axis, they're the most likely faces to collide with so it makes intuitive sense
and that's really all there is to these branches
else if ( absN.y > absN.x && absN.y > absN.z )
{
if ( n.y > r32( 0.0 ) )
{
out[ 0 ].v.Set( -e.x, e.y, e.z );
out[ 1 ].v.Set( e.x, e.y, e.z );
out[ 2 ].v.Set( e.x, e.y, -e.z );
out[ 3 ].v.Set( -e.x, e.y, -e.z );
out[ 0 ].f.inI = 3;
out[ 0 ].f.outI = 0;
out[ 1 ].f.inI = 0;
out[ 1 ].f.outI = 1;
out[ 2 ].f.inI = 1;
out[ 2 ].f.outI = 2;
out[ 3 ].f.inI = 2;
out[ 3 ].f.outI = 3;
}
else
{
out[ 0 ].v.Set( e.x, -e.y, e.z );
out[ 1 ].v.Set( -e.x, -e.y, e.z );
out[ 2 ].v.Set( -e.x, -e.y, -e.z );
out[ 3 ].v.Set( e.x, -e.y, -e.z );
out[ 0 ].f.inI = 7;
out[ 0 ].f.outI = 4;
out[ 1 ].f.inI = 4;
out[ 1 ].f.outI = 5;
out[ 2 ].f.inI = 5;
out[ 2 ].f.outI = 6;
out[ 3 ].f.inI = 5;
out[ 3 ].f.outI = 6;
}
}now this next chunk of code may seem really daunting, but bare with me
if ( n.y > r32( 0.0 ) )
{
// ...
}
else
{
// ...
}for the two branches comparing the signs, in case the value is positive, choose the top face of the incident box, otherwise if it was negative, choose the bottom face of the incident box, along choosing the features indices which is very useful for tracking features and keeping our contact manifolds later stable
however the indices turned out to be a little random and i couldn't make much sense of it, i don't really know why they are valued the way they are and not sure if it's a bug, but you could easily make up your own indices if you want ¯\_(ツ)_/¯ (though for this specific collision code it doesn't matter for us right now, it's mainly there to track collided features which is more relevant to contact constraint warm starting so that, again, checking if the features match or not and simplfying the process it involves further)
for ( i32 i = 0; i < 4; ++i )
out[ i ].v = q3Mul( itx, out[ i ].v );now at the bottom of the function we turn the edges vertices from local space to incident's world space and output them to out vertex array, that's really it for the function
now getting into the q3ComputeReferenceEdgesAndBasis(...) function
n = q3MulT( rtx.rotation, n );not much to explain here...
if ( axis >= 3 )
axis -= 3;here we're decrementing the axis numbering in case it was higher than or equal to 3, which then would be the B box that we've chosen as a reference box
switch ( axis )
{
case 0:
if ( n.x > r32( 0.0 ) )
{
// ...
}
else
{
// ...
}
break;
case 1:
if ( n.y > r32( 0.0 ) )
{
// ...
}
else
{
// ...
}
break;
case 2:
if ( n.z > r32( 0.0 ) )
{
// ...
}
else
{
// ...
}
break;
}again we pick a face that's right nearby the incident face depending on the axis value, let's say we've previously chosen the bottom face of the incident box, then here we instead choose the upper face of the reference box, that's really it
however, you would also see something like this
e->Set( eR.z, eR.x, eR.y );
basis->SetRows( rtx.rotation.ez, rtx.rotation.ex, rtx.rotation.ey );what we're doing here is rotating everything around the x-axis about 90 degrees, which essentially gives us the following
the y-axis is now facing us in the z direction, but notice how it's on the xy plane like a 2D mapping, which is clever but i feel like this is a bit overkill and does complicate things a little more than necessary? since we could instead construct tangent and bitangent vectors relative to the face normal and orient the tangent and bitangent vectors later to construct more proper clipping planes this way, it's much simpler than the Randy's approach, but it would be less efficient, though it should be more than fine in most cases, but whatever
then we should be done with the function and now we have chosen our reference face!
the last thing is the q3Clip(...) function, which is the main core of the face-something collision resolution phase
i32 q3Clip( const q3Vec3& rPos, const q3Vec3& e, u8* clipEdges, const q3Mat3& basis, q3ClipVertex* incident, q3ClipVertex* outVerts, r32* outDepths )
{
i32 inCount = 4;
i32 outCount;
q3ClipVertex in[ 8 ];
q3ClipVertex out[ 8 ];
for ( i32 i = 0; i < 4; ++i )
in[ i ].v = q3MulT( basis, incident[ i ].v - rPos );
outCount = q3Orthographic( r32( 1.0 ), e.x, 0, clipEdges[ 0 ], in, inCount, out );
if ( !outCount )
return 0;
inCount = q3Orthographic( r32( 1.0 ), e.y, 1, clipEdges[ 1 ], out, outCount, in );
if ( !inCount )
return 0;
outCount = q3Orthographic( r32( -1.0 ), e.x, 0, clipEdges[ 2 ], in, inCount, out );
if ( !outCount )
return 0;
inCount = q3Orthographic( r32( -1.0 ), e.y, 1, clipEdges[ 3 ], out, outCount, in );
// Keep incident vertices behind the reference face
outCount = 0;
for ( i32 i = 0; i < inCount; ++i )
{
r32 d = in[ i ].v.z - e.z;
if ( d <= r32( 0.0 ) )
{
outVerts[ outCount ].v = q3Mul( basis, in[ i ].v ) + rPos;
outVerts[ outCount ].f = in[ i ].f;
outDepths[ outCount++ ] = d;
}
}
assert( outCount <= 8 );
return outCount;
}what we're really interested in here is the q3Orthographic(...) function, we're calling it four times in a row with each different plane of both positives and negatives of x and y, and we're clipping the incident edges into all four sides of the reference, most of this is essentially Sutherland-Hodgman algorithm (the last looping bit of this function is for a different purpose), it's a dead simple algorithm and it can be generalized just fine to various 2D polygons, not just quads/rectangles like in this case
now going on...
for ( i32 i = 0; i < 4; ++i )
in[ i ].v = q3MulT( basis, incident[ i ].v - rPos );this essentially rotates the incident vertices to the local space of the reference box in with the new basis matrix that we constructed earlier
and now to the real deal
outCount = q3Orthographic( r32( 1.0 ), e.x, 0, clipEdges[ 0 ], in, inCount, out );inside the q3Orthographic(...) function, we're presented with the following
i32 q3Orthographic( r32 sign, r32 e, i32 axis, i32 clipEdge, q3ClipVertex* in, i32 inCount, q3ClipVertex* out )
{
i32 outCount = 0;
q3ClipVertex a = in[ inCount - 1 ];
for ( i32 i = 0; i < inCount; ++i )
{
q3ClipVertex b = in[ i ];
r32 da = sign * a.v[ axis ] - e;
r32 db = sign * b.v[ axis ] - e;
q3ClipVertex cv;
// B
if ( ((InFront( da ) && InFront( db )) || On( da ) || On( db )) )
{
assert( outCount < 8 );
out[ outCount++ ] = b;
}
// I
else if ( InFront( da ) && Behind( db ) )
{
cv.f = b.f;
cv.v = a.v + (b.v - a.v) * (da / (da - db));
cv.f.outR = clipEdge;
cv.f.outI = 0;
assert( outCount < 8 );
out[ outCount++ ] = cv;
}
// I, B
else if ( Behind( da ) && InFront( db ) )
{
cv.f = a.f;
cv.v = a.v + (b.v - a.v) * (da / (da - db));
cv.f.inR = clipEdge;
cv.f.inI = 0;
assert( outCount < 8 );
out[ outCount++ ] = cv;
assert( outCount < 8 );
out[ outCount++ ] = b;
}
a = b;
}
return outCount;
}this should be obvious and straightforward to understand hopefully
q3ClipVertex a = in[ inCount - 1 ];
for ( i32 i = 0; i < inCount; ++i )
{
q3ClipVertex b = in[ i ];
// ...
}here we pick the last vertex from the in array, and then pick the first one and going on with the loop, and we essentially are starting with an edge here
r32 da = sign * a.v[ axis ] - e;
r32 db = sign * b.v[ axis ] - e;then we take the distance from the point to the plane, and we flip the sign depending on the plane we're dealing with (x+, x-, y+ or y- planes)
now the next branches are going to rely on the following macros
#define InFront( a ) \
((a) < r32( 0.0 ))
#define Behind( a ) \
((a) >= r32( 0.0 ))
#define On( a ) \
((a) < r32( 0.005 ) && (a) > -r32( 0.005 ))InFront essentially says make sure the point is in front of the plane relative to whatever plane, and so on... the image should tell what's going on (and an example of the x- plane)
in case the edges hit the plane, the points behind the plane get clipped to the green lines that's drawn on the image (which would be on the plane), and the points infront of the plane are kept as they are
in case an entire edge is behind the plane, it gets ridden off completely and it's points are not counted in anymore
and the process repeats for all edges for that plane we're dealing with, and that's it
once we exit from the function, we repeat the exact same process for all remaining planes
// Keep incident vertices behind the reference face
outCount = 0;
for ( i32 i = 0; i < inCount; ++i )
{
r32 d = in[ i ].v.z - e.z;
if ( d <= r32( 0.0 ) )
{
outVerts[ outCount ].v = q3Mul( basis, in[ i ].v ) + rPos;
outVerts[ outCount ].f = in[ i ].f;
outDepths[ outCount++ ] = d;
}
}then this should be obvious as well, in case the point is infront of the reference face, just don't count it in as part of the contacts anymore, otherwise if it's behind then turn it back into world space point and output the depth and the pairs too
and that's pretty much it for the q3Clip(...) function!
the rest of the face-something collision resolution phase branch is just outputting the remaining contacts and that's about it, and also in case the flip was set to true, it would just flip the normal along swapping the collided feature pairs as well
now into the edge-edge collision resolution phase, here we want to select two edge features and get the closest points between them
here the normal is the axis that we tested earlier from the SAT test, and it's in world space because of the following
n = atx.rotation * n;the normal previously when we did SAT tests was in A's local space because of the C matrix we used earlier, so in order to convert it back to world space we just multiply it by A's orientation
in the earlier image, the yellow vectors are the most parallel oriented axis relative to the normal (in case of the blue box, it's the oriented z axis and x axis that are the most parallel relative to the normal, the least parallel is the oriented y axis)
the reason being is if you notice the following
the least parallel axis relative to the normal in this case is the y axis, since the normal is mostly looking towards x and z axis, and it's actually quite what we wanted and it does feature the edges we asked for! now that was the case for the blue box
in the case of the purple box, we find that the least parallel axis relative to the normal is the z axis, so we pick that
if this is confusing, basically what we're doing here is we want the least parallel axis (which is the opposite in the face-something case and it's choosing most parallel axis)
q3Vec3 PA, QA;
q3Vec3 PB, QB;
q3SupportEdge( atx, eA, n, &PA, &QA );
q3SupportEdge( btx, eB, -n, &PB, &QB );that's pretty much what this block of code does for both boxes, it outputs two edges at the end and also moves the edges around depending on the signs of the normal from each box, there's not much further things to explain at this point, that's all it really does
q3Vec3 CA, CB;
q3EdgesContact( &CA, &CB, PA, QA, PB, QB );here we take the closest points from both edges and output them, more specifically this is what the q3EdgesContact(...) function does
inline void q3EdgesContact( q3Vec3 *CA, q3Vec3 *CB, const q3Vec3& PA, const q3Vec3& QA, const q3Vec3& PB, const q3Vec3& QB )
{
q3Vec3 DA = QA - PA;
q3Vec3 DB = QB - PB;
q3Vec3 r = PA - PB;
r32 a = q3Dot( DA, DA );
r32 e = q3Dot( DB, DB );
r32 f = q3Dot( DB, r );
r32 c = q3Dot( DA, r );
r32 b = q3Dot( DA, DB );
r32 denom = a * e - b * b;
r32 TA = (b * f - c * e) / denom;
r32 TB = (b * TA + f) / e;
*CA = PA + DA * TA;
*CB = PB + DB * TB;
}it's a fairly complex function to make sense of, but the gist of it is that you get two closest points from both edges like so
if you need an in-depth explanation, here's a link
and then that's it for the edge-edge contact function (it really isn't "contact" per se, it's just getting the closest points after all), the rest of the edge-edge collision resolution phase branch is just spitting out the point along the normal and the feature pair
and we're finally done! thanks for reading the article :)