At the end of last week’s blog post I went on about BEPU Physics: this fantastic, open source Physics engine written in pure C#. Now don’t get me wrong, I am still of that opinion. It is fantastic but I had a bit of a change of heart on whether to use it or not. Eventually I chose to implement my own, more basic collision and response system. This implementation is what took up most of my week!
Why Write My Own Collision and Response System?
I started this week pushing ahead with getting BEPU working in the engine. It seemed to be going reasonably well, but there was this nagging feeling in my mind while doing it. It didn’t feel perfect - I felt like I was shoe-horning something in. There were problems arising where, for instance, BEPU introduced its own vector and matrix library or it used programming constructs I wouldn’t have necessarily chosen. Little things like having to convert all of my data structures into their data structures or restructuring how I did things to work with their design was bugging me. This was my engine and I wanted it to work how I wanted it.
Eventually, I got frustrated with how much my code base was changing just to get this to work and I took a step back. I realised I didn’t actually need all of those features BEPU was advertising - they would have just been nice additions. All I really needed was the basic ability to bump into things and climb stairs. Therefore, I went ahead and researched techniques that I could implement myself so I could ditch the BEPU dependency.
The Swept Sphere Technique
After a good rummage through the likes of Stack-Overflow and various forums, I eventually happened on a tutorial-like paper called “Improved Collision detection and Response” by Kasper Fauerby. This has been an absolute life-saver, and the paper does an excellent job of explaining the maths behind the “Swept Sphere Technique” Fauerby used for his collision detection and response.
The technique itself involves some pretty simple linear algebra thankfully, so the implementation has gone pretty smoothly so far. The basic gist is that the algorithm is split into two stages: the collision stage and the response stage. The collision stage is all about detecting whether a sphere has collided with an arbitrary polygon given a velocity, and the response stage is about calculating the final position of the sphere given that the polygon is solid. For instance, it may just stop against the polygon if the sphere is pushing directly into it, or it might slide along the surface of the polygon if the velocity vector is at an angle to the surface. Each stage has multiple steps to it and the paper is well worth a read if you’ve ever wondered about how collision might work in a game engine!
Unfortunately I have not quite finished implementing it yet. The entire system is in place, but I need to iron out some bugs. It is also working in a very brute-force fashion at the minute and will not be very efficient for large scenes. My plan is to implement an octree, where I only test for collision in the same quadrant as the character (or any other colliding object.) Hopefully by next week I will have proper collision and response in place!
Improving my Level Editor
The other thing I did this week quickly was slightly improve my level editor addon for Blender. This was a direct result of writing my own collision system of course. Since the new collision system works for arbitrary polygons (i.e. it doesn’t just have to be a box or something, we could have collision meshes of any shape and size) the collision mesh data is now embedded into the level data and loaded in by the engine. This also gave me the wonderful excuse to use screenshots of Blender for this week’s blog images instead of more screenshots of the same in-engine scene I have used for the past two weeks. Maybe I should just shove something else into the scene to spice it up a bit?