[osg-users] Further Design Question: KDTree

Adrian Egli OpenSceneGraph (3D) 3dhelp at gmail.com
Wed Jul 16 07:40:44 PDT 2008

Hi Robert,

I understand your comment really well, and w.r.t. to building performance
this is true. for all paged database the building performance is much more
important then the intersection check. Especially for terrain rendering.

The question is how we can design the kdTree build for most application
with max performance. Either we reimplement a second, third, .. kdTree class
or we use the
BuildOptions for the decision how the tree should be constructed.
For each application it can be different, event for different geometries we
can have different builds.
Actually we have a new member in osgDB::Registry to define the KdTreeBuilder
with it's option and
the kdTree prototype. If we assume that each user can has he's own kdTree,
then the option
would no longer be needed, because we can handle the different techniques in
the kdTree
subclasses. So should we think this way, or should we think in combination.
We could
use our own inherited kdTree classes for own modifications, and we could
implement in the default
kdTree class some common building techniques. May the user can handle the
building by a simple enumeration
in the buidling option, like  { FAST_BUILD ,  CENTER_TOPOLOGY_ALIGNED  ,
...    , SAH , ..  }
or what would be best design ?

i am aware of the real time openGL rendering, and for what we use the line
intersection check. and i am also aware
that each kdTree tuning is 'overhead' for current applications. but may for
collision checks, and so on, we can get
better performance linearly to the kdTree perf win in each optimisation we


2008/7/16 Robert Osfield <robert.osfield at gmail.com>:
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
> 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 Egli
-------------- next part --------------
An HTML attachment was scrubbed...
URL: <http://lists.openscenegraph.org/pipermail/osg-users-openscenegraph.org/attachments/20080716/f83dfe34/attachment-0002.htm>

More information about the osg-users mailing list