<div dir="ltr"><br><br><div class="gmail_quote">2008/7/15 Robert Osfield <<a href="mailto:robert.osfield@gmail.com">robert.osfield@gmail.com</a>>:<br><blockquote class="gmail_quote" style="border-left: 1px solid rgb(204, 204, 204); margin: 0pt 0pt 0pt 0.8ex; padding-left: 1ex;">
Hi Adrian,<br>
<div class="Ih2E3d"><br>
On Tue, Jul 15, 2008 at 7:44 PM, Adrian Egli OpenSceneGraph (3D)<br>
<<a href="mailto:3dhelp@gmail.com">3dhelp@gmail.com</a>> wrote:<br>
> I played with the osg::KDtree.cpp and did a review. then after thinking a<br>
> while how we can reduce the number of flops, i found one first optimisation<br>
> we should do. the ray or just a line with starting point s and ending point<br>
> e is during the whole intersection test static, so we can precalculate the<br>
> direction and also the inverse direction and store this information in dir /<br>
> invdir.<br>
><br>
> 1-KdTree.cpp<br>
><br>
> the performance win is about 10-12%<br>
><br>
> ** should be check in **<br>
<br>
</div>If you feel its appropriate to check in could you please post to<br>
osg-submissions.<br>
<div class="Ih2E3d"></div></blockquote><div>:-)  <br></div><blockquote class="gmail_quote" style="border-left: 1px solid rgb(204, 204, 204); margin: 0pt 0pt 0pt 0.8ex; padding-left: 1ex;"><div class="Ih2E3d"><br>
<br>
> we can assume that we can get in general a very bad posed problem. assume<br>
> that we have a scene with n triangles and each triangle has exactly the same<br>
> center point. Very bad geometry<br>
> but then we can never seperate them, so we will get a kdTree with max number<br>
> of levels. i assumed, if there is a split with too less seperation<br>
> behaviour, we do just a 50-50 split. may this isn't yet the best idea, but i<br>
> helps.<br>
<br>
</div>Um.... well if someone has this extreme example of worst possible<br>
triangle set up then there apps is screwed up anyway so if KdTree<br>
doesn't perform perfect well then too bad, garbage in garbage out.  Is<br>
see no reason to go trying to catch silly cases.<br>
<br>
In the case of the current implement such a silly case would just<br>
under up with a single branch down to the max level number of<br>
division, there wouldn't be any side branches.  You wouldn't see any<br>
division, so you wouldn't get a performance improvement, but then the<br>
cost of traversing down the levels will be trivial anyway.  It's<br>
basically a non issue.<br>
<div class="Ih2E3d"><br>
> But i know we should talk about this, because the kdTree should be as<br>
> small as possible with "best" performance in building and intersection check<br>
> ,... not only line / ray.<br>
<br>
</div>As long as it works well in the vast majority of cases I'm happy.  One<br>
could try and gun for "best" performance, but you are almost certainly<br>
wasting most of your time in developing.  As I've said before the<br>
KdTree traversal isn't the bottleneck on normal IntersectionVisitor<br>
traversal its the actual scene graph traversal - this is where the<br>
bottleneck is which is the most important to address.<br>
<br>
As for other intersection types, for 2.6 I'm happy with what we have.<br>
We can add other intersections types on a need be basis.<br>
<div><div></div><div class="Wj3C7c"></div></div></blockquote><div><br>correct :-) <br><br><br> </div><blockquote class="gmail_quote" style="border-left: 1px solid rgb(204, 204, 204); margin: 0pt 0pt 0pt 0.8ex; padding-left: 1ex;">
<div><div class="Wj3C7c"><br>
Robert.<br>
_______________________________________________<br>
osg-users mailing list<br>
<a href="mailto:osg-users@lists.openscenegraph.org">osg-users@lists.openscenegraph.org</a><br>
<a href="http://lists.openscenegraph.org/listinfo.cgi/osg-users-openscenegraph.org" target="_blank">http://lists.openscenegraph.org/listinfo.cgi/osg-users-openscenegraph.org</a><br>
</div></div></blockquote></div><br><br clear="all"><br>-- <br>********************************************<br>Adrian Egli
</div>