You can usually whip up a 100 liner to solve a problems, if your input is cloud of random points. This is what pretty much all the Java code out there does, but the input data for your game is not a random point cloud!
I hate computation geometry, but yet it is so important! It drives me crazy.
I was recently looking for a robust 3D convex hull algorithm which would work for a couple of hundred points in realtime. That is, something sub 2.0 ms on a 2GHz Core Duo.
I wrote a couple of solutions myself, including one which was O(n^4) and surprisingly did not scale beyond 25 points. Finally I was hinted towards this patch for Bullet Physics, and it turned out to be a real gem!
It is fast, scales well (it's O(n log h)), and is robust too. My litmus test is a grid of 4x4x4 points. It passes that and even handles coplanar input. Pretty much all the Java code out there fails on that input.
So I took that patch, regexp'd it, copy pasted some Bullet code, deleted stuff I did not need, shuffled things around a bit, and made it output triangles and I'm finally a happy man!