当前位置:网站首页>Use octree structure to manage scenes
Use octree structure to manage scenes
2022-07-20 15:34:00 【Autodesk_ Glodon】
1、 Problem description
Why do we use googlEarth perhaps osgEarth When , In principle, infinite data can be loaded , The reason is that it uses a tree like organizational structure , as follows :
Let's still imagine the earth ,Level0 It's the thickest ball , When we were far away, it was this ball .Level1 Let's pull closer , The earth will be divided into eight , Then we pull closer to one of the corners and split into Level2 The appearance of , This corner is divided into eight .
The coarse level shows the coarse content , Fine level loads fine content , Just like the tiles of high-definition images , The first 0 Level can be the whole earth , The resolution is 256X256, Then it is divided into eight , The range of each picture becomes 0 One eighth of grade , But the resolution is still 256x256, The more you pull down, the clearer it becomes .
In this section, we will build such an octree structure , If you understand this section , You'll get to the structure of octree , Because recursion is often used when building a tree structure . It's still a little hard to understand .LOD and PagedLOD Are widely used to build a digital earth , In fact, the principle is similar to this section .
2、 Functions of this section
1、 Random generation 5000 A ball , The coordinate range is [-500, 500].
2、 For this 5000 A ball generates an octree , The end condition is like this : When the child of the node is less than 16 It is considered as a leaf node , No further points . Or the depth of the tree is greater than 32 No further points .3、 We use one for each floor LOD To preserve , When far away, it shows father ( Draw the bounding box ), When I get closer, my father is divided into eight . Until the leaf node is displayed .
3、 Concrete realization
osgPro227.cpp
// osgPro227.cpp : This file contains "main" function . Program execution will start and end here .
#include <osg/Group>
#include <osgDB/ReadFile>
#include <osgUtil/PrintVisitor>
#include <osgViewer/ViewerEventHandlers>
#include <osgViewer/Viewer>
#include <osgViewer/ViewerEventHandlers> // Event monitoring
#include <osgGA/StateSetManipulator> // Event response class , Control the rendering state
#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());// Realize status information statistics
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)
// The maximum size of the current bounding box 、 middle 、 The smallest , Prepare for the division of octree
osg::Vec3 extentSet[3] = {
total._min,
(total._max + total._min) * 0.5f,
total._max
};
std::vector<ElementInfo> childData;
// Traverse all children of the parent node , Let the... Contained in the current box , Not completely contained but with the midpoint in the box , Are pressed into the child nodes of the current box
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);
}
}
}
// If the number of children in the current node has reached the standard , Or the number of layers has reached the standard , It is considered as leaf node
bool isLeafNode = false;
if ((int)childData.size() <= _maxChildNumber || depth > _maxTreeDepth)
{
isLeafNode = true;
}
// Current octree root
osg::ref_ptr<osg::Group> group = new osg::Group;
// If it's not a leaf node , Continue to divide , Divide the space into eight
if ( !isLeafNode )
{
osg::ref_ptr<osg::Group> childNodes[8];
// Space is divided into eight 2*2*2
for ( 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 Is the smallest ,1 It's in the middle ,2 It's the biggest
// The following small algorithm is a bit annoying , Find out separately min and max Of x, y, z Try pushing a few by yourself
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];
}
// So please id To ensure uniqueness
int id = s[0] + (2 * s[1]) + (4 * s[2]);
childNodes[id] = build( depth+1, osg::BoundingBox(min, max), childData );
}
}
}
// After the construction of eight sub nodes , Add to the root node
for ( unsigned int i=0; i<8; ++i )
{
if ( childNodes[i] && childNodes[i]->getNumChildren() )
group->addChild( childNodes[i] );
}
}
else // Find the leaf node , The recursion is over
{
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;
// Create a ball
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;
// Finally, create a LOD, Far away from the display debugging box , Close to the group showing the component
osg::LOD* level = createNewLevel( depth, center, radius );
level->insertChild( 0, createBoxForDebug(total._max, total._min) ); // For debug use
level->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();
}
边栏推荐
猜你喜欢
Analysis scaffold
C# 在Word中添加多行多列文字水印
机器翻译做到头了?Meta开源NLLB翻译模型,支持200种语言互译
文件同步工具 rsync 常用选项使用介绍及通过服务同步数据
函数递归习题(easy版)
[special topic of golang database 5] golang language operation redis for addition, deletion, modification and query
npm warn config global `--global`, `--local` are deprecated. use `--location 解决方法
能解决80%故障的排查思路
SCCM2012R2网络部署重装系统
GCD spanning tree of provincial selection and special training
随机推荐
Apicloud AVM framework creates digital scrolling components
Zhiyuan admitted plagiarizing the paper, and the relevant responsible person has resigned!
[mindspire] [model reasoning] whether the model trained using the unfit CPU API can perform reasoning on the CPU
才22岁!这位'00后'博士拟任职985高校!
openresty lua-resty-mlcache多级缓存
In depth explanation of the development function of Multi Chain Wallet system and analysis of the development principle of multi currency wallet system
机器翻译做到头了?Meta开源NLLB翻译模型,支持200种语言互译
pytorch,nonzero 实例 使用
mindspore 8卡V100训练到101个epoch的时候报读取数据超时的错误
【mindspore】【警告原因】进行模型训练的时候报警告
超详细的MySQL基本操作
自动机器学习库:TPOT の 学习笔记
Leetcode424.替换后的最长重复字符
Function recursion exercises (easy version)
Svn compares local changes relative to the previous version
实验二 货物进销管理系统
[pkusc2018] main fighting ground of provincial selection and special training
关于响应式布局,你必须要知道的
【Mindspore】【读取图数据】无法读取Mindrecord格式图数据
技术人如何打响个人品牌?五大顶级KOL独家传授