KdTrees

作者: osgChina 发布于2018-10-22 09:32:00 分类 : 编程指南

设计

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是不必要的,因为它们已经够优秀了,真正要做的是优化你的场景结构。