Hi Adrian, On Thu, Jun 5, 2008 at 7:34 AM, Adrian Egli OpenSceneGraph (3D) <[EMAIL PROTECTED]> wrote: > important in each kd-tree implementation for line / ray intersection testing > is the SAH heuristic for good kd trees. SAH like kd-trees are a little bit > slover in building but much faster in intersection testing. Alsi BIH could > be an good choice for speed up the intersection testing for dynamic scenes. > www.ompf.org / or the publication of > http://www.sci.utah.edu/~wald/Publications/ > > http://www.sci.utah.edu/~wald/Publications/2007///FastBuild/download//fastbuild.pdf
Thanks for the links. My initial implementation I'll be going for a very simple division strategy - each axis division made at the centre of each bb, which should be faster to create, but in theory less efficient to traverse. The approach will be to use a very simple kdNode objects that is just a pair of short or int indices, everything will be inlined, no virtual functions, and the whole kdNode network stored in a flat std::vector<>. This approach should lead to small memory footprint and good cache coherency vs more sophisticated kdTree structures, which will offset the extra traversal one will need to do vs an non optimized tree. Once this is working we can look at experimenting with other data structures and build strategies, it'd be then interesting to compare the different approaches - the minimal but memory/cache efficient vs sophisticated but large memory footprint/more memory fragmentation. I must add though, if the basic approach works well enough then I may just check it in, and leave experimentation with other approaches to others, as I do have plenty of other tasks contending for my time. > For what could we also use a kd-tree based geometry: > # kd-tree implementation for haptic rendering, achieve for high res > geometries a fps about 150-200 fps for a common haptic device (sensable > phantom) > # kd-tree collision detection Using a kd-tree for doing haptic collision makes far more sense then rendering to OpenGL like API. For this current round of work I'm focussing on just intersection testing, rather than collision detection though, others are welcome to dive in once I have the basics in place. Robert. _______________________________________________ osg-users mailing list [email protected] http://lists.openscenegraph.org/listinfo.cgi/osg-users-openscenegraph.org
