Re: [Algorithms] Octree\KD tree Generation for better cache coherence...

[Conor S. <cs...@tp...>]

RE: [Algorithms] Octree\KD tree Generation for better cache =
coherence...Well, I would say your best bet for cache coherance is to =
actually optimise for size. But it doesn't really matter that much, =
because the trees don't have that many nodes, and traversal doesn't =
happen often (unless you have a raytracer).=20

Kd-tree tends to be the better I find (maybe not in terms of storage, =
but in terms of speed/flexibility).=20

If you don't wanna fragment RAM, the easiest way would be to just =
allocate a chunk, and use your own memory handler. Although, the easiest =
way to write a kd-tree or octree generation system tends to be with =
recursive constructors.=20

When it comes to in order traversal, both systems can be used to easily =
traverse in order (although, for frustum culling it isn't needed). A =
kd-tree is the same to do back to front as a BSP, except all your planes =
to test are axis aligned (means you only need a single compare to =
traverse).=20

Front to back for a kd-tree (sorta pseudo cody stuff warning):

class kdtreenode {
    float m_partition;
    UINT8 m_axii;
    kdtreenode* m_children[2];
public:
    void Traverse(float* camera,FifoStack* fs);
};

void kdtreenode::Traverse(float* camera,FifoStack* fs) {
    if (m_children[0]) { // Test leaf
        // Not leaf, traverse further
        UINT8 travtest=3D(m_partition>camera[m_axii]);
        m_children[travtest]->Traverse(camera);
        m_children[travtest^1]->Traverse(camera);
    } else {
        // Is leaf, put on stack (in order)=20
        fs->Push(this);       =20
    }
}

An octree can be traversed similarily, although you do 3 axii tests at =
once, and use binary logic for the sort.=20

Conor Stokes

  ----- Original Message -----=20
  From: Chris Brodie=20
  To: 'gda...@li...'=20
  Sent: Thursday, August 31, 2000 8:57 AM
  Subject: RE: [Algorithms] Octree\KD tree Generation for better cache =
coherence...


  (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.=20

  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=20

  Chris=20