RE: [Algorithms] Octree\KD tree Generation for better cache coher ence...

[Chris B. <Chr...@ma...>]

(Apologies for the HTML. My mail administrators are still working on it. Something to do with the mail system ignoring the client settings. If this goes on much longer I'll switch to a native SMTP client and talk to a unix box.)

I've been thinking recently about how to best structure the data in ram to make best use of my cache. Initially I was thinking about a tightly packed array that stores the data\splitting planes hierarchically top down. Using this method I could use pointer math to move around within the tree's data, which I'm not sure is a good thing or not from a performance point.

The other idea I had recently is to store my tree in traversal order. Obviously this wouldn't be optimised for every situation but the more traversal that you do the greater you efficiency would be as all the data will likely be in order until you start skipping hunks of the tree. 

I'm guessing that this is probably one or the more important things to optimise in an engine. The only source I've ever seen to do with these kinds of tree's was on flipcode(ask midnight) and that used dynamic memory allocation for storage. 

One last question. When you perform frustum culling to get your list of visible nodes do you use a special traversal technique to get a front to back order or do you just read them in any order then blast them through a radix sort. I have seen some references to techniques that do this but I'm not sure if the unusual traversal order would be worse on the cache than just reading them in as you find them and then doing a fast sort. In my case I'm only expecting to find perhaps 150-250 nodes at most.

Many thanks

Chris