设计

KdTree是用来大幅提高碰撞检测效率的方法。

在include/osg/KdTree 头文件中，包含 osg::KdTree 和 osg::KdTreeBuilder。

osg::KdTree 是 osg::Shape的子类，这样设计使得其可以绑定geometry叶结点，在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;

需要注意这两个都是虚函数，需要用户自己去实现。

一个兄弟类是用来构建KdTree的，叫做 KdTreeBuilder，是一个NodeVisitor，它会逐个遍历结点，当遍历到geometry时，会对其构建KdTree，并最后调用geometry->setShape(kdTree)方法。之所以使用kdTree类，是给用户提供了自己实现自己的构建kdTree算法的接口。

使用

可以打开自动构建KdTree的开关，此时osgDB会查觉，之后setBuildKdTreesHint，然后DatabaserPager会通过osgDB知识是否需要构建KdTree，然后调用osgDB::Registry的接口去构建KdTreeBuilder。可以通过指定环境变量OSG_BUILD_KDTREES为ON来打开自动构建KdTree方法。

set OSG_BUILD_KDTREES=on
osgpick cow.osg

或者可以在代码中这样：

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

上面的代码需要在读取任何模型之前来设置。另一种方式是在osgDB::ReadNodeFile时，使用ReaderWriter::Options来指定需要构建KDTREES。下面是具体的枚举：

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

显然不指定的是话是：NO_PREFERNCE。osgDB::Registry::setBuildKdTreesHint() 默认值也是 NO_PREFERNCE.

osgUtil::IntersectionVisitor / LineSegmentIntersector默认的情况下是支持KdTree的，它在做碰撞检测时，是会先去查看是否包含了KdTree。因此使用osgUtil::IntersectionVisitor / LineSegmentIntersector求交时，构建了KdTree时，不需要写其它的求交代码以来支持KdTree。

为了方便测试，在IntersectionVisitor中设置了以下方法用来关闭和打开是否使用KdTree:

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

性能数据

当做碰撞检测时，KdTree究竟表现怎么样呢?

构建KdTree是相当快速的，对于大模型也是毫秒级的，特大模型最多10毫秒。而且这也不是在主线程里面完成的，是在databasepaging线程里做的，因此性能上几乎可以忽略。

碰撞检测的效率提升也非常显著，能提升N倍到N百倍的效率相比老旧的碰撞检测方法。

对于结点结构大而多又复杂的场景结构（比如有一亿个树，每个树有十万亿个Geometry），效率提升没有这么明显，原因是浪费在树遍历上的时间太多，这样就导致对单个KdTree的效率提升相对不太明显。

上述的表意是针对KdTree和osgUtil::IntersectionVisitor / LineSegmentIntersector是不必要的，因为它们已经够优秀了，真正要做的是优化你的场景结构。