I have been tinkering with data structures and associated kdtree build algorithms, and so far got basic kdtree generation working for vertices. Initially I had the KDNode's as simple pair of int/short which was stored directly in a std::vector<> for cache efficiency, and KDLeaf as a separate object, this work pretty well with me getting a build rate around of around 4M vertices per second. Re jigging the KDLeaf to be a std::pair<> and storing it in a std::vector<> bumped performance up to around 9M vertices per second build rate.
Once I add in the support for placing primitives in the Leaves of the kdtree I'll need to add a bigger processing overhead, so my performance figures will come a bit, but not by a huge amount. I shouldn't need to add much more complexity into the data structures to support primitives so I expect to keep the cache efficient nature of the implementation - i.e. will have contiguous blocks of memory to store the whole kdtree for each osg::Geometry in the scene, the memory footprint of this form of kdtree is also looking to be pretty low, again something that should be friendly to the cache and memory bandwidth requirements. I have a list of submissions awaiting review so I'll now move on to these, and probably won't have much time left to continue work on kdtree support this week. Next week I'm away training so I'll be back on the case the week after. Then... we'll find out just how fast a cache friendly kdtree implementation can be :-) Robert. _______________________________________________ osg-users mailing list [email protected] http://lists.openscenegraph.org/listinfo.cgi/osg-users-openscenegraph.org
