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

Adrian Egli OpenSceneGraph (3D) 3dhelp at gmail.com
Tue Jul 15 13:42:20 PDT 2008


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

> 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
> osg-submissions.
>
:-)

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

correct :-)




>
> 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/72ebb5f2/attachment-0003.htm>


More information about the osg-users mailing list