[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
> > we should do. the ray or just a line with starting point s and ending
> > e is during the whole intersection test static, so we can precalculate
> > 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
> > center point. Very bad geometry
> > but then we can never seperate them, so we will get a kdTree with max
> > 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
> > ,... 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.
> osg-users mailing list
> osg-users at lists.openscenegraph.org
-------------- next part --------------
An HTML attachment was scrubbed...
More information about the osg-users