[osg-users] KdTree support now checked in

Robert Osfield robert.osfield at gmail.com
Fri Jul 11 13:09:50 PDT 2008

Argggg.... accidentally pressed a control combination and gmail kindly
dispatched the email before complete...

Rejoining the previous email...

To enable automatic generation of KdTree's I have extended osgDB so
that the Registry and DatabasePager are both KdTree aware, and if
KdTree build option is enabled it'll use the Registry's new
KdTreeBuilder object to build KdTree's on loaded models.  To enable
this building you simple set the env var OSG_BUILD_KDTREES to on, i.e.

  osgpick cow.osg

Or programatically you can enable building of KdTrees via:


You'll need to call this before you load any models that you wish to
have BUILD_KDTREES set.  Another option is that you can control the
building of KdTrees per file load via the ReaderWriter::Options
object, that now has the enum and set/get pair:

                /// range of options of whether to build kdtrees
automatically on loading
                enum BuildKdTreesHint

                /** Set whether the KdTrees should be built for
geometry in the loader model. */
                void setBuildKdTreesHint(BuildKdTreesHint hint) {
_buildKdTreesHint = hint; }

                /** Get whether the KdTrees should be built for
geometry in the loader model. */
                BuildKdTreesHint getBuildKdTreesHint() const { return
_buildKdTreesHint; }

The ReaderWriter::Options overrides what is set in osgDB::Registry
when the hint is set to anything other than the default of

The osgDB::Registry::setBuildKdTreesHint() default value is also NO_PREFERNCE.


In terms of intersection traversals, the osgUtil::IntersectionVisitor
/ LineSegmentIntersector now both have KdTree support built into them,
and by default they will use any Geometries KdTree for intersection if
one is available.   This means if you are already using
IntersectionVisitor/LineSegmentIntersector then you'll automatically
have support, and you won't need to do any further code changes - just
recompile the OSG and your app and you'll have it all there.

To help with testing I've also made the use of KdTree during
intersections optional via a pair of methods added to the

        /** Set whether the intersectors should use KdTrees when they
are found on the scene graph.*/
        void setUseKdTreeWhenAvailable(bool useKdTrees) {
_useKdTreesWhenAvailable = useKdTrees; }

        /** Set whether the intersectors should use KdTrees.*/
        bool getUseKdTreeWhenAvailable() const { return
_useKdTreesWhenAvailable; }

I've used this to help profile the older way of doing intersections vs
the new KdTree intersections.


So what of the performance of building KdTree and intersecting with them?

Building is pretty fast, for most models it'll be just ms to build,
for big models it might be 10's of milliseconds.  The speed of
building allows us to use when paging data in without any noticeable
hit - especially as the build is done by the paging thread, not the
main thread or rendering threads.

Intersecting performance improvement varies a lot - from just a couple
times faster on some models/intersection tests through to 3000x faster
with polygon rich models and certain ray test.  For the whole earth
models I've been doing a lot of testing against the typical
performance delta is 5 to 40x the speed of the old intersection

The reason for much of the variation is the effect of the
IntersectionVisitor traversal - if the scene graph is large and
complex then the traversal time can easily swamp the cost of the
KdTree intersections.  I have also found that just creating the
intersection data containers that record the intersections for the
user are relatively expensive compared to the cost of KdTree traversal
- the KdTree traversal is just so darn fast that everything else the
IntersectionVisitor does it slow in comparison!

What this means is that spending more time on optimizing the KdTree
build and intersect methods is probably not worth it right now, rather
it's high level management of how you set up the intersections calls
the KdTree that needs to be carefully managed if you want to get
maximum performance.  For most users this probably won't be necessary,
the performance boost from the existing IntersectionVisitor when using
KdTree will be sufficient.


Another little side effect of this work is that I tracked down and
fixed precision problems that were occurring when handling whole earth
models.  These fixes means it's possible to drop down on to the
surface of the earth with the Terrain or Drive Manipulator and get
solid intersections/camera positions without any jitter.


To wrap, all these changes on now in SVN trunk and will be part of
2.5.4 and hence the up coming 2.6.  If you enable the build of
automatic KdTrees of load and use
IntersectionVisitor/LineSegmentIntersector then you'll be able to go
straight ahead of use KdTree intersections without lifting a further
finger ;-)

Have fun!

More information about the osg-users mailing list