[osg-users] KD-Tree Performance Challenge....

Robert Osfield robert.osfield at gmail.com
Tue Jul 15 02:48:53 PDT 2008

Hi Adrian,

On Tue, Jul 15, 2008 at 8:15 AM, Adrian Egli OpenSceneGraph (3D)
<3dhelp at gmail.com> 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

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.


More information about the osg-users mailing list