[osg-submissions] KDTree fix

[Robert Osfield]

Hi Adrian,

I have just done a review of your latest KdTree, and now understand
the optimization - it's actually one I considered too, but didn't
implement out of concern of build performance.  Your results suggest
the the new bb compute code adds a further 50% in build time over the
previous technique, you don't mention the performance figures.   A 50%
hit on build time is not good news for people who are paging
databases.   The performance improvement on intersection also needs to
be put in the context of how the
IntersectionVisitor/LineSegmenetIntersector are used typically, as the
costs of scene graph traversal typically swap that of KdTree traversal
so a 50% improvement in KdTree might only give us 5% improvement, alas
the build time is far less swamped by scene graph traversal.

I think the best one could do to try and balance things for different
usages - would be to either have different KdTree subclasses or have
different build/intersect algorithms that are chosen by KdTree
options.  Note, we already have a KdTree::BuildOptions object that is
passed into the build option already - this could be used to provide
hints on whether quick builds vs slower builds that optimize
intersections should be preferred.

Robert.

On Wed, Jul 16, 2008 at 8:46 AM, Adrian Egli OpenSceneGraph (3D)
<3dhelp at gmail.com> wrote:
> Hi Robert,
>
> This morning i was about 1hour in train, and reviewed again the kdTree
> implementation. Yesterday i wrote that the kdTree has some strange behaviour
> when triangles have equal center points. yes this is still true, and we can
> (as you told) ignore such bad geometries. but one thing i worked out is that
> the kdTree isn't oriented to the geometry topology, assume we have a torus
> like box, then the bounding boxes are far away from a optional kdTree-based
> bounding box hierarchy. for line intersection checks this is not as bad as
> it sounds, but for further more complex checks, like polytop intersection,
> haptic rendering this will turn in a more expensive overhead. so i propose
> to use the latest code, with the ADRIAN_DIVIDE_BB_FIX define switch on.
>
> to compare the kdTree, performance, nodes, leafs, i added some statistics to
> the code: #define VERBOSE_OUTPUT_TREE_INFO
>
> the building time still fast enough, but of course no for free :-(, the tree
> is smaller. he is not just smaller, it's more correct w.r.t  kdTree spatial
> datastructure / bounding hierarchy.
>
> adrian
>
>
>
> ## ADRIAN ##
> #define ADRIAN_DIVIDE_BB_FIX
>
> KD-Tree Build Time      =       0.0590638s
>    + TriList        = 69451
>       + Nodes       = 23776
>         + depth sum = 316836
>         + avg depth = 13.3259
>       + Leaves      = 23777
>         + depth sum = 364388
>         + avg depth = 15.3252
>         + max depth = 19
>         + min depth = 9
>
>
>
> ## SVN ##
>
> KD-Tree Build Time      =       0.0404889s
>    + TriList        = 69451
>       + Nodes       = 32084
>         + depth sum = 520696
>         + avg depth = 16.2291
>       + Leaves      = 23143
>         + depth sum = 436283
>         + avg depth = 18.8516
>         + max depth = 22
>         + min depth = 7
>
>
>
>
>  23776  / 32084 / -8303    / ~33% win
>  23777  / 23143 / +634     / ~ 0% lost
>  0.059  / 0.040 / +0.019   / ~33% lost
>
>  ******  win ******
>  memory ....
>  intersection speed ...
>  :-)
>
>  ****** pay with build time *****
>  :-(
>
> --
> ********************************************
> Adrian Egli
> _______________________________________________
> osg-submissions mailing list
> osg-submissions at lists.openscenegraph.org
> http://lists.openscenegraph.org/listinfo.cgi/osg-submissions-openscenegraph.org
>
>