Saturday, 2 August 2014

My code - AABB vs. triangle collision with least translation vector

Recently, I did one SM64-esque demo while working on some collision code. This in all in preparation to the upcoming development of 3D games. I have now completed my quest into the world of collision detection, and I shall narrate it.

While I previously had working triangle vs. AABB collision, that implementation was of little use to game development due to the lack of a "least translation vector", that is, the minimum displacement that makes two objects to stop overlapping each other.

That implementation was based on this code, by Tomas Akenine Moller. I merely translated his code to Javascript, without understanding it. His code is pretty bad, I must say. It has horrible macros, including defining "X", "Y" and "Z" as "0", "1" and "2" (obviously for accessing elements of vectors). Any decent programmer knows why calling a macro by a single, uppercase letter is very stupid, namely, because then you can never use that letter in your code, ever, without replacing it with the macro. I also looked at some code at this site called Geometric Tools. It is also horrible. The collision functions try to be very good for performance and everything, but then the guy writes a class to do collision detection. For every single different type of collision. Now that's some stupid C++. I, however, am pretty sure of the root of such computer science horror. That is academic code. Written by academics. Who don't know how to write code that is meant to be actually used for doing something actually interesting. Precisely the same reason why they don't care to provide the least translation vector, because they don't know the real needs of game developers. They only care about publishing their clever papers about how smart they are and how much optimization they can fit into their little math puzzles.

However, since collision detection involves quite an amount of mathematics, and we humble non-academic mortals have no time to deal with those, we have no choice but to succumb to those academics. I was advised to look for a certain book, "Real time collision detection", by Christer Ericson. Of course it doesn't tell you about the least translation vector, because Mr. Ericson is an academic and did not research what game developers actually need for collision detection. I then could actually understand what Mr. Moller's horrible code was doing. And then I could make my own implementation of triangle vs. AABB collision detection, without as much bullshit and including the least translation vector (that was actually quite trivial to include, once I understood the vector operations between the separating axis theorem, it was only a matter of normalizing some vectors and including a few dot products).

I then had an almost 500 lines of code long function that of course I had to debug. Now, this kind of thing is horrible to debug, because any silly math mistake like a 0 instead of a 1 or a - instead of a + goes unseen but makes the result completely wrong. And in my case both things happened. I had to add some quick & dirty  debugging to show which axis was claiming to separate to solve the false negatives, and then to correct the errors in the least translation vector. Those last actually required checking the entire function anyway, because one of the possible candidates to least translation vector was longer than it should be and therefore would not appear in the debugging, instead a longer vector would be selected causing the box to jump around due to unnecessarily high displacement.

In the process of debugging, I made this little demonstration of the collision detection. It has a randomly positioned box and triangle, you can move the box around, and it makes the box change colors if it collides against the triangle and also shows the least translation vector as a 3D arrow. You can even move the box around.

But now I am over this horrible episode. Hopefully I will actually be able to create something with this. Except my vacations are almost over and then I won't have time. Oh well.

Check out the github repository of my triangle vs. AABB collision code by clicking the Octocat below:

P.S.: someone that has been asking me about collision detection asked me why I think this is one of the most useful forms of collision detection and why it's more useful than box vs. box collision detection. The trivial answer is that you can make a level with arbitrary geometry in any 3D modelling program and load it and collide the bounding box of your character against it.

No comments:

Post a Comment