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

【击此打开网盘资源链接】

### 本节知识点

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

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

### 具体实现

class KdTree : public osg::Shape

class KdTreeBuilder : public osg::NodeVisitor

``````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() );
``````

### 还有一个小知识点

``````    picker->_pagedReader = new PagedReaderCallback;
{
{
}
};
``````

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

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

#include <osg/Group>
#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:
{
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());
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;
}
};

{
{
}
};

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::Group> root = new osg::Group;

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

#ifdef ACCURATE_INTERSECTION
#endif

osgViewer::Viewer viewer;
viewer.setSceneData(root.get());