Hi Guy, The algorithm for building and traversing are closely coupled so it may well be best to just provide a base class the provides a high level interface for building and intersecting, and then have subclasses implement the build and intersecting methods.
It's still early days for kd-tree support so I don't yet have anything concrete, through this week I do hope to get a first build/intersecting implementation checked in, my aim is to have fast build, a minimal memory footprint as well as accelerating intersections. My own goal isn't related to real-time ray tracing, so optimizing the intersecting cost is not a goal that precludes all other considerations - as long as the code is solves the current intersection bottleneck that can occur on intersection test I won't bother spending time trying to optimizing it further. For instance is the cost of a intersection traversal is 20ms on a current test model and hence breaking frame, and I get it down to 1ms I'm done - bottleneck is gone. Robert. On Sun, Jun 8, 2008 at 8:00 AM, Guy <[EMAIL PROTECTED]> wrote: > Hello, > > Maybe it's arrogant of me to mention anything, but anyway… > > > > I don't know what kd-tree is, only guessing from your discussion, but if as > Adrian says the performance is a combination of building, and traversing the > tree, I think these sections should be implemented in generic classes so > their implementation could be easily replaced later. Like the callbacks > mechanism for example. > > > > Guy. > > > > ________________________________ > > From: [EMAIL PROTECTED] > [mailto:[EMAIL PROTECTED] On Behalf Of Adrian Egli > OpenSceneGraph (3D) > Sent: Friday, June 06, 2008 4:55 PM > To: OpenSceneGraph Users > Subject: Re: [osg-users] kdtree example > > > > Hi all, > > once we have a working version of kd-Tree, we can start a contest :-) there > exist hunderds of heuristics, tricks for traversing, and so on. Performance > of kd-Tree traversing depends not only the method of traversing, the > performance depends much more on the build strategy than on the traversing. > of course both are important, kd-Tree build and the software enginiering > tricks for fast traversing. > > :-) in my first kd-tree traversing algorithme, basic kd-tree i had about > 27s, after some optimisation i could do same thing in less than one second. > but i know some kd-tree based raytracing algorithme working much much faster > :-) > > /adrian > > 2008/6/6 Robert Osfield <[EMAIL PROTECTED]>: > > Hi Paul, > > On Fri, Jun 6, 2008 at 3:20 PM, Paul Melis <[EMAIL PROTECTED]> wrote: >> As it is still work in progress you might have this on your list already, >> but changing the traversal to use a while loop with a stack rather than >> use >> recursive calls on traverse() should increase intersection performance >> quite >> a bit. > > Use a local stack rather than recursive is something I'm already > considering. The current build code uses recursion, and the intersect > traversal I'll implement initially with recursion for simplicity. > Once these are both working sweetly I'll implement the alternative non > recursive. > > Robert. > > _______________________________________________ > osg-users mailing list > osg-users@lists.openscenegraph.org > http://lists.openscenegraph.org/listinfo.cgi/osg-users-openscenegraph.org > > > -- > ******************************************** > Adrian Egli > > _______________________________________________ > osg-users mailing list > osg-users@lists.openscenegraph.org > http://lists.openscenegraph.org/listinfo.cgi/osg-users-openscenegraph.org > > _______________________________________________ osg-users mailing list osg-users@lists.openscenegraph.org http://lists.openscenegraph.org/listinfo.cgi/osg-users-openscenegraph.org
