[osg-users] Further Design Question: KDTree

Paul Melis paul at science.uva.nl
Wed Jul 16 08:28:50 PDT 2008

Just a note on this topic...

Adrian Egli OpenSceneGraph (3D) wrote:
> 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.
I haven't looked in detail what splitting method the current KD-tree 
implementation uses, but the "binning algorithm" in section 3 of [1] 
seems to provide quite a good trade-off between tree quality and build 
time, while being fairly simple to implement. They basically use a 
clever coarse-grained SAH evaluation for the upper part of the tree and 
switch to full SAH for nodes with a small number of primitives. The 
"parallel" in the title does not apply to that section, although the 
authors have gone quite far in doing parallel tree building.

And if low build times is really the main goal for the intersection 
structure, especially for paged databases, then an alternative structure 
to a KD-tree might be worth exploring. Bounding volume hierarchies are 
awefully fast to construct, at the cost of having some problems with 
models containing wildly different sized primitives. But even for the 
latter problem solutions are beginning to emerge, e.g. the edge volume 
heuristic ([2]).

[1] "Highly parallel fast kd-tree construction for interactive  ray 
tracing of dynamic scenes" (kesen.huang.googlepages.com/Intel-EG07.pdf)
[2] "The Edge Volume Heuristic - Robust Triangle Subdivision for 
Improved BVH Performance"

In case any students are looking for an interesting topic, I suspect 
trying out the different options would make for a great master's thesis...


> The question is how we can design the kdTree build for most 
> application working
> 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 do.
> /adrian
> 2008/7/16 Robert Osfield <robert.osfield at gmail.com 
> <mailto: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
> 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 <mailto: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
> ------------------------------------------------------------------------
> _______________________________________________
> osg-users mailing list
> osg-users at lists.openscenegraph.org
> http://lists.openscenegraph.org/listinfo.cgi/osg-users-openscenegraph.org

More information about the osg-users mailing list