![](https://blogger.googleusercontent.com/img/b/R29vZ2xl/AVvXsEi7F3JGxrKXPdgAHys1zYxAiyzOWwEwxRymSg6YEldNHHYnrM2g4glEg_Vew8iJIW7gE_QO74tJsaYhsWafBYrnoVk9hmsL5CAhy9_IrXouw712HVRwfqAO21DOnMN4yRzFcc3jX1K_bMGe/s400/Screen+shot+2010-12-10+at+6.19.18+PM.png)
Computational Geometry is hard. Most of the examples out there are crap and the good stuff is without exception hard to understand.
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!