Its quite a hack, but it works pretty well. I went through the texture atlas code and added little quirky log messages everywhere to debug the stuff. I was quite surprised to be greeted with this message at one point while re-running the application:
ERROR: Quadtree appears to be corrupted.
This made me lol, because wtf kind of error message is that? It "appears" to be corrupted, okay. So I go into the code to see where I put this message, and right above it -
// none of the children are large enough? Should never happen.
LOL. Okay, so something is borked. The problem is kind of complicated to explain, but essentially when a quad was broken up and had all its pieces filled, it would "lie" about how much space it had left. Wasn't that hard to fix though :3
But yeah. Thanks for the awesome idea, HopeDagger! <3