OMG. It must have been 15 years since i became obsessed with collision detection and resolving/response for the first time. Boy, was i a bad programmer then with very little understanding of 3D math.
I remember giving up and was so jellous of some of the forum members (olii for example) of the math skills. hehe
Today i have 10 years of business programming experience and i can tell you that i quit two years ago.
I love programming and the creativity that goes on, but business applications today isnt even programming anymore. Just lots of NuGet Packages and frameworks and mapping / config. No algorithms and functions just mapping data from point A to B all day long.
Last week i fired DirectX11 up again and tried to make the same demo as before. 3D Math is so much fun, i will continue to learn as much as i can as long as i live. I had much easier this time to solve all my problems that i had before.
So i thought i should show my working collision and resolving without any jitter / glitches and support for all kinds of shapes. I dont clip the velocity in the code but that could be implemented pretty easily.
The collision model is loaded with assimp.
Good to be back! =)
#include "CollisionDetection.h"
void CollisionDetection::ResolveCollisions(Mesh* mesh, Camera* camera)
{
if (collisionRecursions > MAX_COLLISION_DETECTION_RECURSIONS) //Bail out, player stuck. Go to safe point, last free position frame?
return;
//Take the complete Mesh as a parameter instead.
//Take all the indicies and get the vertex from that list.
auto faces = mesh->GetFaces();
for (int i = 0; i < faces->size(); i ++) {
//this is how to access a pointer std vector?
XMVECTOR a = faces[0][i].a;
XMVECTOR b = faces[0][i].b;
XMVECTOR c = faces[0][i].c;
XMVECTOR normal = faces[0][i].normal;
XMVECTOR p = camera->GetPosition();
//TODO: Check against each vertex trangle aswell? do we really need it since we do line segment?
this->ResolveLineSegmentCollision(p, a, b, mesh, camera);
this->ResolveLineSegmentCollision(p, b, c, mesh, camera);
this->ResolveLineSegmentCollision(p, c, a, mesh, camera);
//resolve if collision is with plane and point is inside triangle / plane
ResolvePlaneCollision(p, normal, a, b, c, mesh, camera);
}
//reset collision recursion count
collisionRecursions = 0;
}
void CollisionDetection::ResolvePlaneCollision(XMVECTOR p, XMVECTOR planeNormal, XMVECTOR a, XMVECTOR b, XMVECTOR c, Mesh* mesh, Camera* camera) {
XMVECTOR closest = this->GetClosestPointOnPlane(planeNormal, a, p);
float distanceToPlane = XMVectorGetX(XMVector3Length(closest - p));
bool isInfrontOfPlane = distanceToPlane > 0.0f; //Negative values and we are behind the plane.
//check minimum distance to Plane
if (distanceToPlane < MIN_DISTANCE && isInfrontOfPlane) {
//if distance to plane is under min then check if point is inside triangle
if (this->PointInTriangle(p, a, b, c)) {
//we have a collision inside the plane, push camera out.
XMVECTOR planePushOut = planeNormal * ((MIN_DISTANCE - distanceToPlane) + EPSILON);
camera->Move(planePushOut); //EPSILON, use the same as Carmack! =)
collisionRecursions++;
ResolveCollisions(mesh, camera); // check again after we update the camera position, could be stuck again.
}
}
}
void CollisionDetection::ResolveLineSegmentCollision(XMVECTOR p, XMVECTOR a, XMVECTOR b, Mesh* mesh, Camera* camera) {
XMVECTOR closestPointLineSegment = this->GetClosestPointOnLineSegment(p, a, b); // Remove later
float distanceToLineSegment = XMVectorGetX(XMVector3Length(closestPointLineSegment - p));
if (distanceToLineSegment < MIN_DISTANCE) {
//instead of Normal Vector we use the vector from closest to point and push out. This is normalized and multiplied with the push out distance.
XMVECTOR vPushOut = XMVector3Normalize(p - closestPointLineSegment) * ((MIN_DISTANCE - distanceToLineSegment) + EPSILON); //EPSILON, use the same as Carmack! =)
camera->Move(vPushOut);
collisionRecursions++;
ResolveCollisions(mesh, camera); // check again after we update the camera position, could be stuck again.
}
}
float CollisionDetection::PlanePointDistanceByNormalUnitVector(XMVECTOR planeNormal, XMVECTOR pointOnPlane, XMVECTOR point)
{
//Shortest distance Point to Plane
//The shortest distance, D, from a point, q(x0, y0, z0), to the plane, P(n, d) : Point, q, lies in the plane if and only if D=0
//w = vector that is subtracted from point - planeNormal, a new vector from planes Normal to our point.
// D = | n * w | / || n || //Distance = DotProduct(n,w) / n.Length() (or Magnitude of Plane Normal)
XMVECTOR w = point - pointOnPlane;
//must be Unit Vector so we project distance on Normal and returned dot value.
XMVECTOR n = XMVector3Normalize(planeNormal);
return XMVectorGetX(XMVector3Dot(w, n));
}
//Must be infront on the triangle!
//compare all the cross products against LINE A-B Point - B and A-B and B-C
//this is really slow, try to make it with Dot-Product instead
bool CollisionDetection::PointInTriangle(XMVECTOR p, XMVECTOR a, XMVECTOR b, XMVECTOR c)
{
XMVECTOR ap = a - p;
XMVECTOR ab = a - b;
XMVECTOR ac = a - c;
XMVECTOR cp1a = XMVector3Cross(ab, ac);
XMVECTOR cp2a = XMVector3Cross(ab, ap);
float dota = XMVectorGetX(XMVector3Dot(cp1a, cp2a));
XMVECTOR bp = b - p;
XMVECTOR bc = b - c;
XMVECTOR ba = b - a;
XMVECTOR cp1b = XMVector3Cross(bc, ba);
XMVECTOR cp2b = XMVector3Cross(bc, bp);
float dotb = XMVectorGetX(XMVector3Dot(cp1b, cp2b));
XMVECTOR cp = c - p;
XMVECTOR ca = c - a;
XMVECTOR cb = c - b;
XMVECTOR cp1c = XMVector3Cross(ca, cb);
XMVECTOR cp2c = XMVector3Cross(ca, cp);
float dotc = XMVectorGetX(XMVector3Dot(cp1c, cp2c));
if (dota < 0.0f || dotb < 0.0f || dotc < 0.0f)
return false;
return true;
}
XMVECTOR CollisionDetection::GetClosestPointOnPlane(XMVECTOR planeNormal, XMVECTOR pointOnPlane, XMVECTOR point)
{
XMVECTOR n = XMVector3Normalize(planeNormal);
float distance = this->PlanePointDistanceByNormalUnitVector(n, pointOnPlane, point);
return point + (-n * distance);
}
XMVECTOR CollisionDetection::GetClosestPointOnLineSegment(XMVECTOR p, XMVECTOR a, XMVECTOR b)
{
XMVECTOR ab = b - a; // points from A to B
float dot1 = XMVectorGetX(XMVector3Dot(p - a, ab)); //mass of point and Line
float dot2 = XMVectorGetX(XMVector3Dot(ab, ab)); //totalt mass of line
float t = dot1 / dot2;
//if outside of segment, clamp becuase we only want closest in segment, not infinite line.
if (t < 0.0f) t = 0.0f;
if (t > 1.0f) t = 1.0f;
return a + t * ab;
}
