第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();
}

© 版权声明
THE END
喜欢就支持一下吧
点赞0 分享
评论 抢沙发
头像
欢迎您留下宝贵的见解!
提交
头像

昵称

取消
昵称表情代码图片