[osg-submissions] KDTree fix

[Adrian Egli OpenSceneGraph (3D)]

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
-------------- next part --------------
An HTML attachment was scrubbed...
URL: <http://lists.openscenegraph.org/pipermail/osg-submissions-openscenegraph.org/attachments/20080716/b4f3be22/attachment-0001.htm>
-------------- next part --------------
A non-text attachment was scrubbed...
Name: KdTree.cpp
Type: text/x-c++src
Size: 28120 bytes
Desc: not available
URL: <http://lists.openscenegraph.org/pipermail/osg-submissions-openscenegraph.org/attachments/20080716/b4f3be22/attachment-0001.cpp>