2008/7/15 Robert Osfield <[EMAIL PROTECTED]>: > Hi Adrian, > > On Tue, Jul 15, 2008 at 7:44 PM, Adrian Egli OpenSceneGraph (3D) > <[EMAIL PROTECTED]> 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 > [email protected] > http://lists.openscenegraph.org/listinfo.cgi/osg-users-openscenegraph.org > -- ******************************************** Adrian Egli
_______________________________________________ osg-users mailing list [email protected] http://lists.openscenegraph.org/listinfo.cgi/osg-users-openscenegraph.org
