Hi Adrian, On Tue, Jul 15, 2008 at 8:15 AM, Adrian Egli OpenSceneGraph (3D) <[EMAIL PROTECTED]> wrote: > Thanks for your eMail. First of all i like to do a review of the current > kdTree code, w.r.t. the build method. As we know form the publications about > kdTree based Real Time Ray Tracer the build method and some heuristics are > more important than the traversal. May the sah heuristic will boost our > kdTree, if this would be true, and the build methode is still efficient in > time and memory i will change directly the current kd-Tree code.
The surface area heuristic might provide a little improvement on pure KdTree intersection performance - but at a cost of building. Please remember that it's intended that KdTree will be built on the fly, such as when paging in databases, you absolutely don't want to cost of build to be greater than the cost reduction in intersection that it provides - if you are paging lots of data all the time, and only doing a moderate number of intersections per frame the balance far from pure in favour of optimizing the final KdTree traversal. Another factor in this is that the actual scene graph traversal is currently more costly then the KdTree traversal, so doubling the speed of the KdTree traversal won't come close to doubling the speed of intersection, it might only have a 5% improvement. So its really important to benchmark all aspect in the context that most users will use it. Going for more sophisticated build techniques make do more overall harm for some users types of usage models than others - your benchmark is far from the most common usage that users will put intersection traversal through. The OSG is not a ray tracing engine, its a general purpose scene graph that uses OpenGL for rendering, and just happens to support intersections to help users out. Given this context, I'm not about to merge new algorithms in place of the existing ones if they impact on build performance. There is no harm in having multiple KdTree implementations, the design is intended for this. If you want to extend it go ahead, if the implementation ticks all the boxes then I'll consider merging it as the default. Robert. _______________________________________________ osg-users mailing list [email protected] http://lists.openscenegraph.org/listinfo.cgi/osg-users-openscenegraph.org
