+1 for Rtree. if you want i can throw my version at you. (not that it is bug-free or neat to read)
i wouldn’t start off with tile-sort. it’s not always better than quadratic and always worse with “few” triangles.
it would suffer from the same OO-memory hazard issue tho’. yet, as Cas said, since your triangles are static, you might like to try to convert the object quad/oct/r -tree into a bytebuffer version. memory issue fixed, plus it’s directly useable by shaders.
I’d really like that! I’m currently exploring some alternatives, but more information would be great! How did your construction code work? Was it the R*-tree version?
well … sort of R*. i like r-tree cos’ they’re very dynamic. fast delete/insert on the fly without knowing the total size of objects.
that is not possible with tilesort so i stopped coding further into it. it works somehow but it’s more like top-down-binary-split-rebalancing kd-tree-like procedure. it is useful but slow and it breaks deleting objects after a bit. i bet there are enough bugs in it i dont know about yet.
i was following http://www-db.deis.unibo.it/courses/SI-LS/papers/Gut84.pdf and exended it with what i understood from tilesort.
i’ll poke you on skype. posting that code here would probably get riven a heart attack 
o/
You don’t need to traverse interior nodes of spatial data-structures except in rare cases. Leaves need to know how to access neighbor leaves.