[osg-users] Further Design Question: KDTree

Robert Osfield robert.osfield at gmail.com
Wed Jul 16 08:17:42 PDT 2008

Hi Adrian,

If the alternate KdTree algorithms can be easily managed as an enum
for build and intersections then this would be a relatively easy way
to go, but... it's more intrusive w.r.t the core KdTree
implementation, which means there needs to be more interaction with
myself to get things tested and merged.

The extensible approach I've taken with osg::KdTree is meant to help
alternate implementations are easy to develop separately from the core
OSG, and then later merged if appropriate/once the implementation
settles down.

I'd suggest one takes advantage of the extensibility when developing
new KdTree build/intersection algorithms, then when an implementation
looks like its well worth merging with the core we can add an enum
into core KdTree implementation.

With a stable release imminent it's important that I focus on this,
rather than get drawn in protected discussions about a single
particular topic - the KdTree extensibility offers the opportunity for
these alternate versions to be developed without dragging me into all
the details.


On Wed, Jul 16, 2008 at 3:40 PM, Adrian Egli OpenSceneGraph (3D)
<3dhelp at gmail.com> wrote:
> 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
> 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>:
> 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 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