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

i think the code is incomplete, you deal with non moving object, however code is clean and readable.

There is a place for jittering, you just haven't discovered it yet, not to mention that you will go through walls, i can see no querying of closest hits, you only check if there's a collision and that's all, to get it working you have to do better,

as far as i know one of the best practices is to make stairs and floor and walls surrounding these stairs and push camera under the stairs, floor and wall

anyway.. how you bounce back object makes all the diffrence

Yes, the code is incomplete. This is just the minimum effort for detecting collision with Sphere against a mesh. And if moving too fast you will go through the walls. No sweep test In this demo.

Fun that you mention stairs with surrounding walls bevause that is exact how my Collisionlevel looks like. ?

No jittering thoug even on complex places with obtuse or convex shapes. If you add velocity clipping it will even be better.

Next up will be raycasting/sweeping and OOB, AABB box tests. Should be fun!

my game that i work on will be a story driven inventory / puzzle game. no action or shooting ?

Thanks for feedback on the code.