欢迎访问 如意编程网!

如意编程网

当前位置: 首页 > 编程资源 > 编程问答 >内容正文

编程问答

使用八叉树结构来管理场景

发布时间:2024/5/15 编程问答 2 豆豆
如意编程网 收集整理的这篇文章主要介绍了 使用八叉树结构来管理场景 小编觉得挺不错的,现在分享给大家,帮大家做个参考.

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

总结

以上是如意编程网为你收集整理的使用八叉树结构来管理场景的全部内容,希望文章能够帮你解决所遇到的问题。

如果觉得如意编程网网站内容还不错,欢迎将如意编程网推荐给好友。