Collision Detection Performance (Volume 2)

Yikes, I’m getting backlogged on the stuff I want to write about!  <Insert generic complaint about how work is eating up most of my time here>

Anyway, this will probably be way shorter than it deserves, but my memory on the subject is about 3 months old.  Basically, this will be more or less a short chronicle of the dumb story of the mesh vs. mesh tests.

Appearances Can Be And Are Frequently Deceiving

When I started work on the collision detection observation, there was one surprising fact: the mesh vs. mesh code (used to determine whether the player was intersecting enemy ships) was working at full speed!  I didn’t seem to have to do any optimization at all on it to get it working.

I did, however, opt to go ahead and change the functions to not be recursive (as the current implementation was, of course, recursing into both meshes’ sphere trees).  When I finished that work, suddenly, the routine was much, much slower.  Was, in this case, the recursion overhead better than what it took to handle the double tree recursion in a non-recursive way?

The Answer May Surprise You

While I was working out the kinks in the non-recursive version, I had added some visual feedback to display unambiguously when the meshes were colliding.  While experimenting, I reverted back to the old (recursive) method, and found out something surprising: the collision results weren’t accurate!  It was reporting collision in cases where the player was inside of the object’s space, but nowhere near any edges!

Turns out, there was an erroneous fall-through case, and it was falling through to a “true” result, causing the entire collision test to short-circuit with an invalid collision result.  Sure the original routine was fast, but it didn’t work at ALL.  Now that I’d fixed that and had an accurate version, it was super, super slow.  Now it became an imperative to optimize.

Double Dribble

Through the course of optimizing the routine, I tried all sorts of crazy stuff.  I eliminated the recursion, I tried AABB vs. Rotated AABB tests, I tried Sphere vs. AABB tests, etc.  There was nothing that I could do.  As I was stepping through the code, however, I started noticing something odd: there were duplicate triangles all over the place.  I would see the same triangle tens of times in a given collision test.

As it turns out, the way I was dividing up the mesh in the tree creation routine was boneheaded.  What I would do was as follows:

1. If the current set of triangles has less than a specified number of entries, stop splitting the mesh, we’ve reached a leaf node.
2. Figure out the bounding box of the current set of triangles
3. Find the axis on which it was best to split the set of triangles (where best was determined as the most balanced split, i.e. where the difference between triangle counts on the left and right of the split was lowest)
4. For each triangle
   1. If the triangle has a vertex to the left of the split, add it to the left side.
   2. If the triangle has a vertex to the right of the split, add it to the right side.
5. Once the mesh is divided into the two sets, recurse into each set to split it further as necessary

Now, a cursory analysis of this algorithm should tell you that step 4 is horribly broken.  If a triangle straddles the split, it would get added into both sides, thus expanding the bounding boxes of each sub element to encompass all triangles that straddle the split, causing there to be tons of duplicates of the same triangles throughout the code.

The correct way to do it would be:

1. If the current set of triangles has less than a specified number of entries, stop splitting the mesh, we’ve reached a leaf node.
2. Figure out the bounding box of the current set of triangles
3. Find the axis on which it was best to split the set of triangles (where best was determined as the most balanced split, i.e. where the difference between triangle counts on the left and right of the split was lowest)
4. For each triangle
   1. Calculate the centroid of the triangle (i.e. average the 3 vertices).
   2. If the centroid is less than the split, add the triangle to the left, OTHERWISE add it to the right.
5. Once the mesh is divided into the two sets, recurse into each set to split it further as necessary

There, now a triangle only gets added to the side that it’s MOSTLY on, and there are no duplicates.  This change greatly boosted the speed of the collision, however there were cases where it would still cause a framerate dip.  Curses and drat!

All the King’s Horses…

Try as I might, I could not get the mesh vs. mesh intersection test to perform well.  So what happened when you get into a situation like that?  You do what every game developer does: you cheat!

What existed at the time was a wicked fast sphere vs. mesh collision test.  So rather than treat the player ship as a mesh, I opted to treat it as a representative collection of spheres (There are 29 spheres total, and it’s a pretty good approximation of the player ship – in fact, it’s probably better than necessary).

Suddenly, player vs. enemy collision performance was great!  Since this was the only place that I had needed a mesh vs. mesh, I could get rid of that slow beast.

~fin~

All of the collision code is complete, now, so next (give or take a post or two) I’ll talk about something with a bit more of a visual element – Bolts of lightning!