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

Robert Osfield robert.osfield at gmail.com
Tue Jul 15 12:06:34 PDT 2008

Hi Adrian,

On Tue, Jul 15, 2008 at 7:44 PM, Adrian Egli OpenSceneGraph (3D)
<3dhelp at gmail.com> wrote:
> 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 /
> invdir.
> 1-KdTree.cpp
> the performance win is about 10-12%
> ** should be check in **

If you feel its appropriate to check in could you please post to

> 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.

Um.... well if someone has this extreme example of worst possible
triangle set up then there apps is screwed up anyway so if KdTree
doesn't perform perfect well then too bad, garbage in garbage out.  Is
see no reason to go trying to catch silly cases.

In the case of the current implement such a silly case would just
under up with a single branch down to the max level number of
division, there wouldn't be any side branches.  You wouldn't see any
division, so you wouldn't get a performance improvement, but then the
cost of traversing down the levels will be trivial anyway.  It's
basically a non issue.

> 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.

As long as it works well in the vast majority of cases I'm happy.  One
could try and gun for "best" performance, but you are almost certainly
wasting most of your time in developing.  As I've said before the
KdTree traversal isn't the bottleneck on normal IntersectionVisitor
traversal its the actual scene graph traversal - this is where the
bottleneck is which is the most important to address.

As for other intersection types, for 2.6 I'm happy with what we have.
We can add other intersections types on a need be basis.


More information about the osg-users mailing list