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

Adrian Egli OpenSceneGraph (3D) 3dhelp at gmail.com
Tue Jul 15 11:44:05 PDT 2008

Hi Robert,

thanks for the answer, i understand very well what kind of optimisation we
can do and what kind of optimisation we should implement in a new class.
the design of osg does still nicely preview such custom optimisation.

I played with the osg::KDtree.cpp and did a review. then after thinking a
while how we can reduce the number of flops, i found one first optimisation
we should do. the ray or just a line with starting point s and ending point
e is during the whole intersection test static, so we can precalculate the
direction and also the inverse direction and store this information in dir /


the performance win is about 10-12%

** should be check in **


we can assume that we can get in general a very bad posed problem. assume
that we have a scene with n triangles and each triangle has exactly the same
center point. Very bad geometry
but then we can never seperate them, so we will get a kdTree with max number
of levels. i assumed, if there is a split with too less seperation
behaviour, we do just a 50-50 split. may this isn't yet the best idea, but i
helps. But i know we should talk about this, because the kdTree should be as
small as possible with "best" performance in building and intersection check
,... not only line / ray.

2-kdTree.cpp based on 1-kdTree.cpp

i have to read some further papers about this part. but anyway
the performance win is about 5-10% and the building time has not really

(Total win compared to SVN about 18-22%)

Is there someone who has well understood how we can avoid this behavoiur ?

2-kdTree.cpp :
462.726K rays/sec:

OpenSceneGraph's KD-Tree (SVN) :
386.464K rays/sec:

2008/7/15 Robert Osfield <robert.osfield at gmail.com>:

> 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
> 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
> osg-users at lists.openscenegraph.org
> http://lists.openscenegraph.org/listinfo.cgi/osg-users-openscenegraph.org

Adrian Egli
-------------- next part --------------
An HTML attachment was scrubbed...
URL: <http://lists.openscenegraph.org/pipermail/osg-users-openscenegraph.org/attachments/20080715/e45b00c5/attachment-0003.htm>
-------------- next part --------------
A non-text attachment was scrubbed...
Name: 1-KdTree.cpp
Type: text/x-c++src
Size: 24806 bytes
Desc: not available
URL: <http://lists.openscenegraph.org/pipermail/osg-users-openscenegraph.org/attachments/20080715/e45b00c5/attachment-0006.cpp>
-------------- next part --------------
A non-text attachment was scrubbed...
Name: 2-KdTree.cpp
Type: text/x-c++src
Size: 25701 bytes
Desc: not available
URL: <http://lists.openscenegraph.org/pipermail/osg-users-openscenegraph.org/attachments/20080715/e45b00c5/attachment-0007.cpp>

More information about the osg-users mailing list