1、問題描述

我們為什么使用googlEarth或者osgEarth的時候，原則上可以加載無限大的數據呢，其原因就是因為其使用的是樹狀的組織結構，如下：

我們仍然來拿地球來想象，Level0是最粗的球，我們離的很遠的時候是這個球。Level1是我們拉近一點，地球會一分為八，然后我們再對著其中一個角拉近就分裂成Level2的模樣，這個角又一分為八。

粗的級別就顯示粗的內容，細的級別就加載細的內容，就像高清影像的瓦片一樣，第0級可以是整個地球，分辨率是256X256，然后一分為八，每張圖片的范圍變成了第0級的八分之一，但是分辨率仍然是256x256，就越往下拉越清晰。

本節我們就來構建這樣一個八叉樹的結構，本節如果你搞明白了，就入門了八叉樹的結構，因為在構建樹狀結構的時候往往會用到遞歸。理解起來還是有點費勁的。LOD和PagedLOD都大量的用作構建數字地球等，其實原理都和本節差不多。

2、本節功能

1、隨機生成5000個球，坐標范圍在[-500, 500]。
2、對這5000個球生成八叉樹，其結束條件是這樣的：當結點的孩子小于16個時認為是葉結點，就不再往下分了。或者樹的深度大于32也不往下分了。3、每一層我們用一個LOD來保存，當離的很遠時顯示父親（把包圍盒繪制出來），當拉近時父親就一分為八。直到顯示葉結點。

3、具體實現

osgPro227.cpp

// osgPro227.cpp : 此文件包含 "main" 函數。程序執行將在此處開始并結束。#include <osg/Group> #include <osgDB/ReadFile> #include <osgUtil/PrintVisitor> #include <osgViewer/ViewerEventHandlers> #include <osgViewer/Viewer> #include <osgViewer/ViewerEventHandlers> //事件監聽 #include <osgGA/StateSetManipulator> //事件響應類，對渲染狀態進行控制#include "OctreeBuilder.h"#pragma comment(lib, "OpenThreadsd.lib") #pragma comment(lib, "osgd.lib") #pragma comment(lib, "osgDBd.lib") #pragma comment(lib, "osgUtild.lib") #pragma comment(lib, "osgGAd.lib") #pragma comment(lib, "osgViewerd.lib") #pragma comment(lib, "osgTextd.lib")float randomValue(float min, float max) {return (min + (float)rand() / (RAND_MAX + 1.0f) * (max - min)); }osg::Vec3 randomVector(float min, float max) {return osg::Vec3(randomValue(min, max),randomValue(min, max),randomValue(min, max)); } class PrintNameVisitor : public osgUtil::PrintVisitor { public:PrintNameVisitor(std::ostream& out) : osgUtil::PrintVisitor(out) {}void apply(osg::Node& node){if (!node.getName().empty()){output() << node.getName() << std::endl;enter();traverse(node);leave();}else osgUtil::PrintVisitor::apply(node);} };int main(int argc, char** argv) {osg::BoundingBox globalBound;std::vector<OctreeBuilder::ElementInfo> globalElements;for (unsigned int i = 0; i < 5000; ++i){osg::Vec3 pos = randomVector(-500.0f, 500.0f);float radius = randomValue(0.5f, 20.0f);std::stringstream ss; ss << "Ball-" << i + 1;osg::Vec3 min = pos - osg::Vec3(radius, radius, radius);osg::Vec3 max = pos + osg::Vec3(radius, radius, radius);osg::BoundingBox region(min, max);globalBound.expandBy(region);globalElements.push_back(OctreeBuilder::ElementInfo(ss.str(), region));}OctreeBuilder octree;osg::ref_ptr<osg::Group> root = octree.build(0, globalBound, globalElements);std::ofstream out("octree_output.txt");PrintNameVisitor printer(out);root->accept(printer);osg::ref_ptr <osgViewer::Viewer> viewer = new osgViewer::Viewer;viewer->setSceneData(root.get());viewer->addEventHandler(new osgGA::StateSetManipulator(viewer->getCamera()->getOrCreateStateSet()));viewer->addEventHandler(new osgViewer::StatsHandler());//實現狀態信息統計viewer->addEventHandler(new osgViewer::WindowSizeHandler());return viewer->run(); }

OctreeBuilder.h

#ifndef H_COOKBOOK_CH8_OCTREEBUILDER #define H_COOKBOOK_CH8_OCTREEBUILDER#include <osg/Geode> #include <osg/LOD>class OctreeBuilder { public:OctreeBuilder() : _maxChildNumber(16), _maxTreeDepth(8), _maxLevel(0) {}int getMaxLevel() const { return _maxLevel; }void setMaxChildNumber( int max ) { _maxChildNumber = max; }int getMaxChildNumber() const { return _maxChildNumber; }void setMaxTreeDepth( int max ) { _maxTreeDepth = max; }int getMaxTreeDepth() const { return _maxTreeDepth; }typedef std::pair<std::string, osg::BoundingBox> ElementInfo;osg::Group* build( int depth, const osg::BoundingBox& total,std::vector<ElementInfo>& elements );protected:osg::LOD* createNewLevel( int level, const osg::Vec3& center, float radius );osg::Node* createElement( const std::string& id, const osg::Vec3& center, float radius );osg::Geode* createBoxForDebug( const osg::Vec3& max, const osg::Vec3& min );int _maxChildNumber;int _maxTreeDepth;int _maxLevel; };#endif

OctreeBuilder.cpp

#include <windows.h> #include <iostream> #include <fstream> #include <sstream> using namespace std;#include <osg/ShapeDrawable> #include <osg/Geometry> #include <osg/PolygonMode> #include "OctreeBuilder.h"osg::Group* OctreeBuilder::build( int depth, const osg::BoundingBox& total,std::vector<ElementInfo>& elements ) {int s[3]; // axis sides (0 or 1)//存放當前包圍盒的最大、中間、最小點，以為劃分八叉樹做準備osg::Vec3 extentSet[3] = {total._min,(total._max + total._min) * 0.5f,total._max};std::vector<ElementInfo> childData;//遍歷父結點的所有孩子，讓包含在當前盒子里的，不完全包含但是中點在盒子里的，都壓入到當前盒子的子結點for ( unsigned int i=0; i<elements.size(); ++i ){const ElementInfo& obj = elements[i];if ( total.contains(obj.second._min) && total.contains(obj.second._max) )childData.push_back( obj );else if ( total.intersects(obj.second) ){osg::Vec3 center = (obj.second._max + obj.second._min) * 0.5f;if (total.contains(center)){childData.push_back(obj);}}}//如果當前結點的孩子數量已經達標，或者層數已經達標，則認為是葉結點bool isLeafNode = false;if ((int)childData.size() <= _maxChildNumber || depth > _maxTreeDepth){isLeafNode = true;}//當前八叉樹根osg::ref_ptr<osg::Group> group = new osg::Group;//如果不是葉結點，繼續分，把空間一分為八if ( !isLeafNode ){osg::ref_ptr<osg::Group> childNodes[8];//空間一分為八2*2*2for ( s[0]=0; s[0]<2; ++s[0] ) //x{for ( s[1]=0; s[1]<2; ++s[1] ) //y{for ( s[2]=0; s[2]<2; ++s[2] ) //z{// Calculate the child extent//extentSet 0是最小，1是中間，2是最大//下面這個小算法有點磨人，分別求出min和max的x, y, z自己好好推幾個試試osg::Vec3 min, max;for ( int a=0; a<3; ++a ){min[a] = (extentSet[s[a] + 0])[a];max[a] = (extentSet[s[a] + 1])[a];}//這么求id是為了確保唯一性int id = s[0] + (2 * s[1]) + (4 * s[2]);childNodes[id] = build( depth+1, osg::BoundingBox(min, max), childData );}}}//八個子結點構建完畢后，加入到根結點當中for ( unsigned int i=0; i<8; ++i ){if ( childNodes[i] && childNodes[i]->getNumChildren() )group->addChild( childNodes[i] );}}else //找到葉結點，遞歸就結束了{for ( unsigned int i=0; i<childData.size(); ++i ){const ElementInfo& obj = childData[i];osg::Vec3 center = (obj.second._max + obj.second._min) * 0.5;float radius = (obj.second._max - obj.second._min).length() * 0.5f;//創建一個球group->addChild( createElement(obj.first, center, radius) );}}osg::Vec3 center = (total._max + total._min) * 0.5;float radius = (total._max - total._min).length() * 0.5f;//最后創建一個LOD，離的遠了顯示調試盒子，離的近了顯示分的組osg::LOD* level = createNewLevel( depth, center, radius );level->insertChild( 0, createBoxForDebug(total._max, total._min) ); // For debug uselevel->insertChild( 1, group.get() );return level; }osg::LOD* OctreeBuilder::createNewLevel( int level, const osg::Vec3& center, float radius ) {osg::ref_ptr<osg::LOD> lod = new osg::LOD;lod->setCenterMode( osg::LOD::USER_DEFINED_CENTER );lod->setCenter( center );lod->setRadius( radius );lod->setRange( 0, radius * 5.0f, FLT_MAX );lod->setRange( 1, 0.0f, radius * 5.0f );if ( _maxLevel<level ) _maxLevel = level;return lod.release(); }osg::Node* OctreeBuilder::createElement( const std::string& id, const osg::Vec3& center, float radius ) {osg::ref_ptr<osg::Geode> geode = new osg::Geode;geode->addDrawable( new osg::ShapeDrawable(new osg::Sphere(center, radius)) );geode->setName( id );return geode.release(); }osg::Geode* OctreeBuilder::createBoxForDebug( const osg::Vec3& max, const osg::Vec3& min ) {osg::Vec3 dir = max - min;osg::ref_ptr<osg::Vec3Array> va = new osg::Vec3Array(10);(*va)[0] = min + osg::Vec3(0.0f, 0.0f, 0.0f);(*va)[1] = min + osg::Vec3(0.0f, 0.0f, dir[2]);(*va)[2] = min + osg::Vec3(dir[0], 0.0f, 0.0f);(*va)[3] = min + osg::Vec3(dir[0], 0.0f, dir[2]);(*va)[4] = min + osg::Vec3(dir[0], dir[1], 0.0f);(*va)[5] = min + osg::Vec3(dir[0], dir[1], dir[2]);(*va)[6] = min + osg::Vec3(0.0f, dir[1], 0.0f);(*va)[7] = min + osg::Vec3(0.0f, dir[1], dir[2]);(*va)[8] = min + osg::Vec3(0.0f, 0.0f, 0.0f);(*va)[9] = min + osg::Vec3(0.0f, 0.0f, dir[2]);osg::ref_ptr<osg::Geometry> geom = new osg::Geometry;geom->setVertexArray( va.get() );geom->addPrimitiveSet( new osg::DrawArrays(GL_QUAD_STRIP, 0, 10) );osg::ref_ptr<osg::Geode> geode = new osg::Geode;geode->addDrawable( geom.get() );geode->getOrCreateStateSet()->setAttribute(new osg::PolygonMode(osg::PolygonMode::FRONT_AND_BACK, osg::PolygonMode::LINE) );geode->getOrCreateStateSet()->setMode( GL_LIGHTING, osg::StateAttribute::OFF );return geode.release(); }

總結

以上是生活随笔為你收集整理的使用八叉树结构来管理场景的全部內容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網站內容還不錯，歡迎將生活随笔推薦給好友。