Collision Detection Is Hard

I was always afraid of rolling a custom solution for collision detection. This is why in the past I’ve tried to use 3rd party libraries for physics and such, but it always felt wrong to me. Most of the physics libraries I’ve used were very big and bloated. They would increase my build times by a lot and they all come with their own math classes and other utilities, which I’ve had already implemented. I don’t want to have multiple classes for vectors, matrices, etc. in my codebase. And I don’t want to have stupid glue code, to make it behave the way I want it to behave.

I decided to roll my own physics code, however I have had zero experience in writing professional grade collision code. This destinction here is important. If you are anything like me you read tutorials online and watch YouTube videos explaining stuff. However the stuff which is available on YouTube is not usable in a professional game engine. Let me explain why. Most of the stuff you can find online are only mearly scratching the surface of this topic, but are presented in a way that make you think that after finishing the tutorial that you can go and build your custom collision solution. Unfortunately this is not the case. There are so many “game devs” who themselves don’t know what they don’t know about the topic. They will showcase their phyics systems and try to impress you with visuals.

Oh look, how many objects ““my”” code can handle

Most of those “devs” also just copy/pasted code and made it look like they came up with something great.

If you are lucky you will come across more advanced stuff like GJK or some derivative of it. However they will not mention, that GJK is not a silver bullet.

All of the videos I’ve seen only attempt to solve a “static collision resolution”, meaning they just compare objects in fixed time intervals to check if any are stuck inside each other. They don’t solve for “dynamic collisions” or perform “continious collision detection”. The moment you realize that static collision detection is really not suitable for player movement, bullet movement, or any movement which does affect gameplay, you understand how screwed you are. People try cope by trying to increase the physics update frequency by 2x, 4x, etc. in order to not miss collisions. However, even if collisions are not missed they are not resolved properly. You don’t JUST want to “uncollide” objects, but you want to prevent penetration. You want to slide along walls, you don’t want to get stuck on corners or geometry edges.

And this is where the journey actually begins. Researching continious collision detection was a painful experience.

I came across a variety of potential solutions. Namely Sphere vs. Sphere CCD, Ellipsoid CCD, etc. Besides a poorly performing GJK CCD derivative I didn’t find anything which did solve generic cases. I did manage to write a custom solution for AABB vs AABB, which actually works really great. It has wall sliding, not getting stuck on geometry edges and performing well.

// AABB vs. AABB only!
void MOVEMENT_MoveSceneObject( SceneObject *scene_object, const Vec3 &total_move, 
								std::list< SceneObject * > &scene, eMoveType type, uint32 flags ) {
	if ( VectorLengthSquared( total_move ) <= 0.0f )
		return;

	const float move_epsilon_sq = Square( 0.005f );
	const int32 max_recursions = 7;

	Vec3 valid_move = total_move;

	bool recurse = true;
	for ( int32 i = 0; ( i < max_recursions ) && recurse; i++ ) {
		const Bounds &bounds = scene_object->GetBounds();
		const Vec3 bounds_center = bounds.GetCenter();

		float move_length;
		const Vec3 move_dir = VectorNormalizeOrZero( valid_move, move_length );
		recurse = false;

		// hit and sort
		std::vector< Collision > collisions;
		for ( SceneObject *obj: scene ) {
			const Bounds &other_bounds = obj->GetBounds();
			IntersectionInfo info = MovingBoundsIntersectsBounds( bounds, valid_move, other_bounds, true );
			info.scene_object = obj;

			// Don't clip since we want to detect seams
			if ( info.did_hit )
				collisions.push_back( { info, other_bounds } );
		}

		// Find closest hit to object
		const Plane sorting_plane( bounds_center, move_dir );
		std::sort( collisions.begin(), collisions.end(),
				   [ &bounds_center, &sorting_plane ]( const Collision &a, const Collision &b ) {
					   if ( a.info.distance == b.info.distance ) {
						   return SignedDistanceToPlane( ClosestPointInBounds( a.bounds, bounds_center ), sorting_plane )
								  < SignedDistanceToPlane( ClosestPointInBounds( b.bounds, bounds_center ), sorting_plane );
					   }

					   return a.info.distance < b.info.distance;
				   } );

		// do collision in sorted order and resolve
		if ( collisions.size() > 0 ) {
			const IntersectionInfo &hit_info = collisions[0].info;
			valid_move *= hit_info.dt; // Clip movement

			if ( type == MOVE_SLIDE ) {
				Vec3 slide_move = VectorReject( move_dir, hit_info.surf_norm ) * ( move_length - hit_info.distance );
				recurse = VectorLengthSquared( slide_move ) > move_epsilon_sq;
				valid_move = slide_move;
				scene_object->transform.SetPosition(
						hit_info.final_position + hit_info.surf_norm * 0.001f ); // Poor man's fix to avoid seams
			} else {
				recurse = false;
				scene_object->transform.SetPosition( hit_info.final_position );
			}
		} else {
			recurse = false;
			scene_object->transform.SetPosition( scene_object->transform.GetPosition() + valid_move );
		}
	}
}

However I did not want to limit myself to just AABB collisions. So I had to come up with something more flexible.

At this point I have started digging through Quake 1 source code once again and started researching how they’ve solved it in the 90s. I found some articles and random forum posts about the collision system Carmack wrote for Q1.

“Collision detection was pretty hard,” he admitted. “There was a good period where we were making interesting pictures, but movement only worked smoothly as long as you were sliding along walls with obtuse angles—you would get ‘stuck’ on sharp corners.”

Carmack refined code until he arrived at a solution, albeit not an optimal one. Quake’s collision detection functions by expanding the size of every object on a map by half the player’s size, treating players as a point moving through terrain. “This was robust and extremely efficient, but it meant that each unique size of entity that moved through the world had to have a special version of the map automatically generated for it,” said Carmack. “This cost both memory and processing time during level building.”

Shack News

I can’t speak for Quake 3, I heard somewhere they were using the brushes, but Q1 definitely uses axis-aligned bounding boxes for the objects and collides them with the BSP tree. The way they do this is that they store 4 different trees, one regular tree used for culling and three collision hull trees, used for 3 different sized objects (missiles, small things, people).

The BSP trees are ‘expanded’ at compile time which means that the collision engine only needs to clip a single line segment into the BSP tree in order to determine whether it is in solid or in space (and also where the collision takes place). The actual technique is a little more involved (requires bevelling) so try searching the web

GameDev

After reading all that I was a bit disappointed. I did not want to prebake BSP trees and I certainly did not want to limit myself to using only a handful of AABB sizes. I came across a paper by Stefan Melanx about dynamic collisions with BSP trees, where he introduced the concept of shifting planes.

Dynamic Plane Shifting BSP Traversal

BSP Collision Detection As Used In MDK2 and NeverWinter Nights

BTW: I dont want to “push” BSP’s on anyone. For example, if you can bang off a simple robust AABB implementation in a day, and it does what you need, then why not just use that? BSP algorithms can be harder to understand and implement. Every technology (BSP, aabb, obb, loose octtree, etc.) has advantages and disadvantages. When deciding, ignore any religious based arguments in favor of technical analysis.- Stefan Melax

[Algorithms] BSP bevelling

After having seen my options, I felt super overwhelmed and tried to code something up to just have a working solution.

Having spent bunch of time on this, I found some more info on how to solve it for generic cases in this thread. There’s a reference to Doom3 and this paper. TLDR; There are only two cases one must account for to solve CCD for generic triangle based shapes.

  1. Vertex vs. Polygon Face
  2. Edge vs. Edge

In that paper a method is outlined using Plücker coordinates, which was used in Doom3. I copied the entire collision system from Doom3, only to find out that it’s not perfect and that there are certain edge cases where collisions are missed and the player can walk through walls or gets stuck on corners.

I tried coming up with custom functions to solve the above mentioned 2 cases and it worked, but it didn’t work very well due to precision issues and other stuff. I looked into modern CCD projects on github, which come with implementations for those functions and found Tight-Inclusion and some others in the same repos. I had troubles getting them to work properly and when I did manage to get them semi working, the performance was too bad to be usable in a game.

I could’ve lived with those edge cases, however when I started creating more detailed levels the solution would tank in performance. I did use the axis aligned BSP implementation provided by Doom3, but it still wasn’t fast enough I assume or I made mistakes copying it (totally possible). However I was too annoyed to bother even looking how to speed it up, etc.

So after more wasted time and effort on trying to fix these issues I had to bite the bullet and use a 3d physics library. Seemingly randomly I discoverd Jolt, which on the surface looks like everything I needed. After integrating it into my engine and removing all the other physics code I was left, with disappointment. The character controller was working quite well, but still it had a bunch of edge cases uncovered and there was annoying jittering going on when moving up steep surfaces. At this point I was fed up with all of it.

Having said that I decided to go with the most bloated lib I could find in the hopes that it would cover my needs. I decided to go with NVidia physx. But not just any version of it, no. Of course these geniuses make it seemingly extra hard for people to compile their stupid library. They do use CMake, however it is a clusterfuck to include it in your own project. I had to use this version. Fortunetly a guy already has suffered through this and has created a CMake-fied version of physx, which can be included as part of your CMake project to build from source.

Having compiled it and got it running, I had to do a lot of reading in their API / docs on how to set this thing up etc. I spent some days on it, but at the end I had a moving character. Here again, the character controller they provide does not cover all “edge” cases and I had to patch ~3 bad behaviors in the physx to make it work was intended.

It still isn’t as perfect as I want it to be, but at least it performs well.

What I am trying to say here is: Maybe, you should consider using a premade library for collision detection. It is by far the most painful topic I had to deal with. Besides giving you collision detection tools, they also come with already implemented acceleration structures, etc. PhysX and Jolt both have visual debugging built in. Try it out first, before you decide to roll your own.