第22.9节性能篇-使用KdTree来做性能优化-卡核

天下武功，唯快不破

最近网友问了关于点云、倾斜摄影数据的性能优化问题。本来想刀枪剑戟、斧钺勾叉给弄了，但是后来想性能其实是个系统问题，要在第22节分成数小节扎扎实实的讲一讲。

鸣谢

非常感谢王锐王大神的cookbook，我准备主要参考它里面关于性能的一章。也就是第8章。

本节资源

本文集包括本节所有资源包括模型代码都在此下载，按节的序号有文件或文件夹：

注意： 务必使用浏览器打开：
【击此打开网盘资源链接】

本节知识点

1、我们要在场景中做点选，其实是先判断与包围是不是相交，相交了再与包围盒内的物体做碰撞。那问题来了，假如这个物体有1万个三角形，要做碰撞怎么碰呢？

1.1、与每个三角形做碰撞。
1.2、把这些三角形分成两堆儿，左边一堆，右边一堆，这两堆分别有自己的包围盒，与这两堆的包围盒分别求交，这样就简单了。比如与左边的包围盒求交了，交着了，然后左边的再分成两堆儿，直到撞击到叶结点为止，这个时候也许只需要判断与1个三角形的求交。听起来是不是就是个树状的结构。

大家一听，这不是很容易吗，其实不那么容易，就拿分堆儿来说吧，用什么标准来分堆就是大家争相研究的对象，复杂的分堆儿算法会让点击变得高效，但是分堆儿的时间就会长。具体这个树状结构构建的数学理论，网上一查一大堆我就不再详细说了。树的名字都一大堆。

具体实现

在OSG中没有那么复杂，所有的顶点都在Shape中，OSG中有个类叫做:
class KdTree : public osg::Shape

它就是继承自Shape，然后对Node中的Shape进行改造，按KdTree的算法进行分堆儿，构建KdTree这个类，在这个类中对碰撞检测的操作进行了按KdTree的结构来进行了优化。

然后再有个类叫做：
class KdTreeBuilder : public osg::NodeVisitor

它用来把Node中的geometry中的Shape给遍历出来，改造成KdTree 。就齐活了。

我们只需要这样写，所有的读取模型就会构造KdTree

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

我们也可以在读取结点的时候这么写，就单独对某一个模型进行改造：

cpp osg::ref_ptr<osgDB::Options> options = new osgDB::Options;
options->setBuildKdTreesHint( osgDB::Options::BUILD_KDTREES );
osg::Node* model = osgDB::readNodeFile( "cow.osg", options.get() );

然后构建KdTree之后我们来看看效果（提升是非常明显的）：
在这里插入图片描述

还有一个小知识点

当我们点选PagedLod这种数据的时候，就发现交点不准，为什么呢？因为高精度的还没有加载，点的是低精度的。这个问题要怎么解决呢？OSG中也有个机制：

点选相关的类我们都是继承自：osgGA::GUIEventHandler，它有个默认的成员函数叫做：_pagedReader，在点选时，假如遇到了PagedLOD结点，它会把下一级的文件名传给_pagedReader，问怎么办，我们可以这样定义：

    picker->_pagedReader = new PagedReaderCallback;
    struct PagedReaderCallback : public osgUtil::IntersectionVisitor::ReadCallback
{
    virtual osg::ref_ptr<osg::Node> readNodeFile(const std::string& filename)
    {
        return osgDB::readNodeFile(filename);
    }
};

相当于直接就用文件名读出来模型，再点这个模型，这个模型再是PagedLOD，依次递归。直到找到最高级。这样能确保点选精确，但是会大大的降低点选的性能，因为要从硬盘中请求文件。如果要提高效率就要想一些做缓存的机制了。感觉也不太可行，如果对结果的实时性要求不高也可以想想多线程之类的。

以下是本节全部代码，至此性能篇结束

/* -*-c++-*- OpenSceneGraph Cookbook
 * Chapter 8 Recipe 9
 * Author: Wang Rui <wangray84 at gmail dot com>
*/

#include <osg/Group>
#include <osgDB/ReadFile>
#include <osgViewer/ViewerEventHandlers>
#include <osgViewer/Viewer>
#include <sstream>
#include <iostream>

#define FAST_INTERSECTION  // Comment this to disable the use of kd-tree
//#define ACCURATE_INTERSECTION  // Comment this to disable computation of paged LODs

class PagedPickHandler : public osgGA::GUIEventHandler
{
public:
    virtual bool handle(const osgGA::GUIEventAdapter& ea, osgGA::GUIActionAdapter& aa)
    {
        if (ea.getEventType() == osgGA::GUIEventAdapter::FRAME)
            return false;
        if (ea.getEventType() == ea.PUSH)
        {
            osgViewer::View* viewer = dynamic_cast<osgViewer::View*>(&aa);
            if (viewer)
            {
                osg::Timer_t t1 = osg::Timer::instance()->tick();
                osg::ref_ptr<osgUtil::LineSegmentIntersector> intersector =
                    new osgUtil::LineSegmentIntersector(osgUtil::Intersector::WINDOW, ea.getX(), ea.getY());
                osgUtil::IntersectionVisitor iv(intersector.get());
                iv.setReadCallback(_pagedReader.get());
                viewer->getCamera()->accept(iv);

                if (intersector->containsIntersections())
                {
                    osgUtil::LineSegmentIntersector::Intersection result = *(intersector->getIntersections().begin());
                    osg::Vec3 point = result.getWorldIntersectPoint();
                    osg::Timer_t t2 = osg::Timer::instance()->tick();

                    std::cout << "X = " << point.x() << "; ";
                    std::cout << "Y = " << point.y() << "; ";
                    std::cout << "Z = " << point.z() << "; ";
                    std::cout << "Delta time = " << osg::Timer::instance()->delta_m(t1, t2)
                        << "ms" << std::endl;
                }
            }
        }
        return false;
    }
    osg::ref_ptr<osgUtil::IntersectionVisitor::ReadCallback> _pagedReader;
};

struct PagedReaderCallback : public osgUtil::IntersectionVisitor::ReadCallback
{
    virtual osg::ref_ptr<osg::Node> readNodeFile(const std::string& filename)
    {
        return osgDB::readNodeFile(filename);
    }
};

int main(int argc, char** argv)
{
    osg::ArgumentParser arguments(&argc, argv);
#ifdef FAST_INTERSECTION
    osgDB::Registry::instance()->setBuildKdTreesHint(osgDB::Options::BUILD_KDTREES);
#endif
    osg::ref_ptr<osg::Node> loadedModel = osgDB::readNodeFile("./model/Block/Block.osgb");

    osg::ref_ptr<osg::Group> root = new osg::Group;
    root->addChild(loadedModel.get());

    osg::ref_ptr<PagedPickHandler> picker = new PagedPickHandler;

#ifdef ACCURATE_INTERSECTION
    picker->_pagedReader = new PagedReaderCallback;
#endif

    osgViewer::Viewer viewer;
    viewer.setSceneData(root.get());
    viewer.addEventHandler(picker.get());
    viewer.addEventHandler(new osgViewer::StatsHandler);
    return viewer.run();
}