Design

The include/osg/KdTree header contains osg::KdTree and osg::KdTreeBuilder.

The osg::KdTree class is subclassed osg::Shape, and is designed to be attached to osg::Geometry leaves. There are two key methods in KdTree:

/** Build the kdtree from the specified source geometry object.
 * retun true on success. */
virtual bool build(BuildOptions& buildOptions, osg::Geometry* geometry);

and

/** compute the intersection of a line segment and the kdtree, return true if an intersection has been found.*/
virtual bool intersect(const osg::Vec3& start, const osg::Vec3& end, LineSegmentIntersections& intersections) const;

Note, both these are virtual so if you want to create your own custom way of building KdTree's or intersecting KdTree's then you go ahead and implement your own methods.

A companion class KdTreeBuilder is a NodeVisitor that has a prototype osg::KdTree that it clones each time it encounters an osg::Geometry, it then calls kdTree->build(..) on this clone, if a valid KdTree is built then it'll assign to KdTree to the geometry via geometry->setShape(kdTree). The use of the prototype allows you to provide your own subclasses from KdTree so that we KdTree's are built then automatically use your version.

Usage

To enable automatic generation of KdTree's osgDB was extended 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.

set OSG_BUILD_KDTREES=on
osgpick cow.osg

Or programatically you can enable building of KdTrees via:

osgDB::Registry::instance()->setBuildKdTreesHint(osgDB::ReaderWriter::Options::BUILD_KDTREES);

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
{
   NO_PREFERENCE,
   DO_NOT_BUILD_KDTREES,
   BUILD_KDTREES
};

/** 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 NO_PREFERNCE.

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.

For help with testing KdTree during intersections there exists an optional pair of methods in the IntersectionVisitor:

/** 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; }

Performance

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 routines.

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. 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.