3.3 Octree 场景管理
3.2 讲的是「6 平面怎么判单个包围盒」。但这套逐盒判定每帧要跑,场景里几万对象时开销不小——能不能先按空间分桶,一次判一桶?OctreeSceneManager 插件(PlugIns/OctreeSceneManager)给 SceneManager 提供了答案:把场景节点按世界包围盒插进一棵松八叉树(loose octree),可见性收集与各种范围查询先拿「桶」的松包围盒剪枝,命中桶再逐节点精测。
本章与站内既有内容的分工
3.1 的场景查询是基类 SceneQuery 的通用语义,OctreeSceneManager 只是它的一个实现载体;3.2 的 Frustum::isVisible 给出的是两态判定(可见/不可见)。本节把这两者升级成三态:OctreeCamera 把盒判定细分为 NONE/PARTIAL/FULL,配合桶级剪枝形成真正的分层剔除;同时给出 findNodesIn 一族基于八叉树的加速查询。卷一 ogre-core 5.3 讲过 SceneNode 挂接对象,本节把「对象怎么进空间索引、怎么随移动重挂」补齐。
松八叉树:为何每个八分格要重叠
普通八叉树要求对象完整落入某个子格才能下放,跨界对象只能卡在高位——树越深越容易失衡。OctreeSceneManager 用的是松八叉树:每个子格相对兄弟重叠 0.5,只要对象尺寸不超过父格半尺寸就能塞进某个子格,无需切分对象:
// PlugIns/OctreeSceneManager/include/OgreOctree.h:Octree 类注释(v14.6.3 源码摘录,已删减)
/** This is a loose octree implementation, meaning that each
octant child of the octree actually overlaps it's siblings by a factor
of .5. This guarantees that any thing that is half the size of the parent will
fit completely into a child, with no splitting necessary.
*/
松的定义落在两个函数上。_isTwiceSize 判断「对象盒尺寸是否不超过本格半尺寸」——只有这样才能再下放一层;无限盒永远停在根:
// PlugIns/OctreeSceneManager/src/OgreOctree.cpp:Octree::_isTwiceSize(v14.6.3 源码摘录,已删减)
/** Returns true is the box will fit in a child.
*/
bool Octree::_isTwiceSize( const AxisAlignedBox &box ) const
{
// infinite boxes never fit in a child - always root node
if (box.isInfinite())
return false;
Vector3 halfMBoxSize = mBox.getHalfSize();
Vector3 boxSize = box.getSize();
return ((boxSize.x <= halfMBoxSize.x) && (boxSize.y <= halfMBoxSize.y) && (boxSize.z <= halfMBoxSize.z));
}
而 _getChildIndexes 决定下放去 8 个分叉中的哪一个——因为是松树,只看盒中心与格中心的比较,不必管对象是否跨界:
// PlugIns/OctreeSceneManager/src/OgreOctree.cpp:Octree::_getChildIndexes(v14.6.3 源码摘录,已删减)
/** It's assumed the the given box has already been proven to fit into
* a child. Since it's a loose octree, only the centers need to be
* compared to find the appropriate node.
*/
void Octree::_getChildIndexes( const AxisAlignedBox &box, int *x, int *y, int *z ) const
{
Vector3 center = mBox.getMaximum().midPoint( mBox.getMinimum() );
Vector3 ncenter = box.getMaximum().midPoint( box.getMinimum() );
if ( ncenter.x > center.x )
* x = 1;
else
*x = 0;
if ( ncenter.y > center.y )
* y = 1;
else
*y = 0;
if ( ncenter.z > center.z )
* z = 1;
else
*z = 0;
}
_addOctreeNode:深度受限的递归下放
插入从根开始,只要「没到最大深度」且「格能装下对象」就下放;子格按需懒创建,子格的 mBox 与 mHalfSize 由父格沿对应轴对半劈得到:
// PlugIns/OctreeSceneManager/src/OgreOctreeSceneManager.cpp:OctreeSceneManager::_addOctreeNode(v14.6.3 源码摘录,已删减)
void OctreeSceneManager::_addOctreeNode( OctreeNode * n, Octree *octant, int depth )
{
const AxisAlignedBox& bx = n -> _getWorldAABB();
//if the octree is twice as big as the scene node,
//we will add it to a child.
if ( ( depth < mMaxDepth ) && octant -> _isTwiceSize( bx ) )
{
int x, y, z;
octant -> _getChildIndexes( bx, &x, &y, &z );
if ( octant -> mChildren[ x ][ y ][ z ] == 0 )
{
octant -> mChildren[ x ][ y ][ z ] = OGRE_NEW Octree( octant );
const Vector3& octantMin = octant -> mBox.getMinimum();
const Vector3& octantMax = octant -> mBox.getMaximum();
Vector3 min, max;
if ( x == 0 )
{
min.x = octantMin.x;
max.x = ( octantMin.x + octantMax.x ) / 2;
}
else
{
min.x = ( octantMin.x + octantMax.x ) / 2;
max.x = octantMax.x;
}
...
octant -> mChildren[ x ][ y ][ z ] -> mBox.setExtents( min, max );
octant -> mChildren[ x ][ y ][ z ] -> mHalfSize = ( max - min ) / 2;
}
_addOctreeNode( n, octant -> mChildren[ x ][ y ][ z ], ++depth );
}
else
{
octant -> _addNode( n );
}
}
注意终止条件有两个:深度耗尽(depth < mMaxDepth 为假),或格装不下(_isTwiceSize 为假)。对象移动时 _updateOctreeNode 复用同一条规则——一旦对象中心或尺寸让 _isIn 失败,就从原 octant 摘除并重插;根盒都装不下的对象直接挂根。
OctreeCamera:三态可见性
Frustum::isVisible 是布尔,OctreeCamera::getVisibility 把同一套 6 平面测试升级成三态。布尔剔除只能回答「扔不扔」,三态能回答「这一整桶是不是全在里面」——全在里面(FULL)就整桶免测直接入队:
// PlugIns/OctreeSceneManager/include/OgreOctreeCamera.h:OctreeCamera::Visibility(v14.6.3 源码摘录,已删减)
/** Visibility types */
enum Visibility
{
NONE,
PARTIAL,
FULL
};
// PlugIns/OctreeSceneManager/src/OgreOctreeCamera.cpp:OctreeCamera::getVisibility(v14.6.3 源码摘录,已删减)
OctreeCamera::Visibility OctreeCamera::getVisibility( const AxisAlignedBox &bound )
{
// Null boxes always invisible
if ( bound.isNull() )
return NONE;
// Get centre of the box
Vector3 centre = bound.getCenter();
// Get the half-size of the box
Vector3 halfSize = bound.getHalfSize();
bool all_inside = true;
for ( uchar plane = 0; plane < 6; ++plane )
{
// Skip far plane if infinite view frustum
if (plane == FRUSTUM_PLANE_FAR && mFarDist == 0)
continue;
Plane::Side side = getFrustumPlane(plane).getSide(centre, halfSize);
if(side == Plane::NEGATIVE_SIDE) return NONE;
// We can't return now as the box could be later on the negative side of a plane.
if(side == Plane::BOTH_SIDE)
all_inside = false;
}
if ( all_inside )
return FULL;
else
return PARTIAL;
}
与 3.2 的布尔版对照:NEGATIVE_SIDE 立即 return NONE(剔除);6 平面全部 POSITIVE_SIDE 才是 FULL;只要出现一个 BOTH_SIDE 就降级为 PARTIAL。桶级判定用的是 _getCullBounds 算出的松包围盒(mBox ± mHalfSize),所以跨界对象虽然不装在桶里,也仍会被桶的松区域覆盖。
walkOctree:把三态用起来
_findVisibleObjects 从根递归 walkOctree:已确定可见的桶直接以 FULL 传给子树(foundvisible 旗标),否则对每个桶先做 getVisibility;只有 PARTIAL 的桶才需要对其挂载的节点逐个 isVisible,FULL 的桶里所有节点免测入队:
// PlugIns/OctreeSceneManager/src/OgreOctreeSceneManager.cpp:walkOctree 判定部分(v14.6.3 源码摘录,已删减)
void OctreeSceneManager::walkOctree( OctreeCamera *camera, RenderQueue *queue,
Octree *octant, VisibleObjectsBoundsInfo* visibleBounds,
bool foundvisible, bool onlyShadowCasters )
{
//return immediately if nothing is in the node.
if ( octant -> numNodes() == 0 )
return ;
OctreeCamera::Visibility v = OctreeCamera::NONE;
if ( foundvisible )
{
v = OctreeCamera::FULL;
}
else if ( octant == mOctree )
{
v = OctreeCamera::PARTIAL;
}
else
{
AxisAlignedBox box;
octant -> _getCullBounds( &box );
v = camera -> getVisibility( box );
}
// if the octant is visible, or if it's the root node...
if ( v != OctreeCamera::NONE )
{
...
// if this octree is partially visible, manually cull all
// scene nodes attached directly to this level.
if ( v == OctreeCamera::PARTIAL )
vis = camera -> isVisible( sn -> _getWorldAABB() );
...
}
}
这条链路正是 3.2 里 SceneNode::_findVisibleObjects 的插件化替换:不是沿场景树级联,而是沿八叉树级联,桶不可见即整棵子树跳过。范围查询 findNodesIn 走同一思路——先用桶的松包围盒与查询体做 intersect,完全落入查询(INSIDE)就整桶收集(full 加速),部分相交才逐节点精测:
// PlugIns/OctreeSceneManager/src/OgreOctreeSceneManager.cpp:_findNodes 剪枝骨架(v14.6.3 源码摘录,已删减)
static void _findNodes( const AxisAlignedBox &t, std::list< SceneNode * > &list, SceneNode *exclude, bool full, Octree *octant )
{
if ( !full )
{
AxisAlignedBox obox;
octant -> _getCullBounds( &obox );
Intersection isect = intersect( t, obox );
if ( isect == OUTSIDE )
return ;
full = ( isect == INSIDE );
}
Octree::NodeList::iterator it = octant -> mNodes.begin();
while ( it != octant -> mNodes.end() )
{
OctreeNode * on = ( *it );
if ( on != exclude )
{
if ( full )
{
list.push_back( on );
}
else
{
Intersection nsect = intersect( t, on -> _getWorldAABB() );
if ( nsect != OUTSIDE )
{
list.push_back( on );
}
}
}
++it;
}
// 递归 8 个 mChildren[ x ][ y ][ z ],非空即继续
}
这个 _findNodes 模板函数对盒、球、平面有界体积、射线四种查询体各有一份实例,上层 findNodesIn(const AxisAlignedBox&, ...) 等即 3.1 里各 SceneQuery::execute 的底层实现。
源码定位
PlugIns/OctreeSceneManager/include/OgreOctree.h:Octree类与_isTwiceSize/_getChildIndexes/_getCullBounds声明PlugIns/OctreeSceneManager/src/OgreOctree.cpp:上述三函数的实现PlugIns/OctreeSceneManager/src/OgreOctreeSceneManager.cpp:_addOctreeNode、_updateOctreeNode、walkOctree、_findNodes族PlugIns/OctreeSceneManager/include/OgreOctreeCamera.h与src/OgreOctreeCamera.cpp:Visibility三态与getVisibilityPlugIns/OctreeSceneManager/include/OgreOctreeNode.h与src/OgreOctreeNode.cpp:_isIn、_updateBounds重插逻辑
上游引用固定到 OGRE v14.6.3 源码 。
可运行产物:C++ 最小验证
下面复现松八叉树核心链路:_isTwiceSize 准入判定、_getChildIndexes 中心定下标、_addOctreeNode 深度受限递归下放、_updateOctreeNode 移动重挂、findNodesIn 的 _getCullBounds 剪枝 + full 加速范围查询。它与 src/03-3-octree-scene.cpp 逐字节一致:
// file: src/03-3-octree-scene.cpp
// tier: L1
// verify: clang++ -std=c++20 -I. src/03-3-octree-scene.cpp -o bin/03-3-octree-scene && ./bin/03-3-octree-scene
//
// 复现 OctreeSceneManager 插件(OgreOctree.h/OgreOctree.cpp/
// OgreOctreeSceneManager.cpp)的 loose octree 场景管理:
// Octree::_isTwiceSize:盒尺寸 <= 父半尺寸才可能下放子节点;
// Octree::_getChildIndexes:只比较盒中心定 8 分叉下标;
// OctreeSceneManager::_addOctreeNode:深度受限的递归下放,
// 子节点按需懒创建,细分出的 mBox/mHalfSize 由父半劈得到;
// OctreeSceneManager::_updateOctreeNode:移动后出当前 octant 即
// 摘除重插,出根盒则直接挂根;
// _findNodes:盒范围查询,用 _getCullBounds(松包围盒)剪枝,
// 完全落入查询即 full 加速,其余逐节点 intersect。
// 独立最小验证,非 OGRE 源码。
#include "verify.h"
#include <algorithm>
#include <cmath>
#include <list>
#include <vector>
namespace ogre_repro {
struct Vec3 {
float x, y, z;
};
inline Vec3 operator+(const Vec3& a, const Vec3& b) {
return Vec3{a.x + b.x, a.y + b.y, a.z + b.z};
}
inline Vec3 operator-(const Vec3& a, const Vec3& b) {
return Vec3{a.x - b.x, a.y - b.y, a.z - b.z};
}
inline Vec3 operator/(const Vec3& v, float s) {
return Vec3{v.x / s, v.y / s, v.z / s};
}
inline bool operator<(const Vec3& a, const Vec3& b) {
return a.x < b.x && a.y < b.y && a.z < b.z;
}
inline bool operator>(const Vec3& a, const Vec3& b) {
return a.x > b.x && a.y > b.y && a.z > b.z;
}
inline bool vecEq(const Vec3& a, const Vec3& b) {
return a.x == b.x && a.y == b.y && a.z == b.z;
}
// 世界空间轴对齐盒:isNull / isInfinite / 中心 / 半尺寸 / 尺寸
struct AABB {
Vec3 min, max;
bool isNull() const { return min.x > max.x; }
bool isInfinite() const {
return min.x == -1e20f && min.y == -1e20f && min.z == -1e20f &&
max.x == 1e20f && max.y == 1e20f && max.z == 1e20f;
}
Vec3 getCenter() const { return (min + max) / 2; }
Vec3 getHalfSize() const { return (max - min) / 2; }
Vec3 getSize() const { return max - min; }
};
// 对应 OgreOctree.h:node 的简化版(只保留世界盒 + octant 指针)
class Octree;
class OctreeNode {
public:
AABB mWorldAABB;
Octree* mOctant = nullptr;
explicit OctreeNode(const AABB& box) : mWorldAABB(box) {}
const AABB& getWorldAABB() const { return mWorldAABB; }
Octree* getOctant() { return mOctant; }
void setOctant(Octree* o) { mOctant = o; }
// 对应 OgreOctreeNode.cpp:松树只查中心 + 尺寸须小于当前 octant 盒
bool _isIn(AABB& box) {
if (box.isNull()) return false;
if (box.isInfinite()) return true;
Vec3 center = mWorldAABB.getCenter();
bool centre = (box.max > center && box.min < center);
if (!centre) return false;
Vec3 octreeSize = box.max - box.min;
Vec3 nodeSize = mWorldAABB.max - mWorldAABB.min;
return nodeSize < octreeSize;
}
};
// 对应 OgreOctree.h / OgreOctree.cpp:8 分叉 + 松包围盒
class Octree {
public:
Octree* mParent = nullptr;
AABB mBox;
Vec3 mHalfSize;
Octree* mChildren[2][2][2] = {};
std::vector<OctreeNode*> mNodes;
int mNumNodes = 0;
explicit Octree(Octree* parent) : mParent(parent) {}
// 对应 Octree::_isTwiceSize
bool _isTwiceSize(const AABB& box) const {
if (box.isInfinite()) return false;
Vec3 halfMBoxSize = mBox.getHalfSize();
Vec3 boxSize = box.getSize();
return boxSize.x <= halfMBoxSize.x && boxSize.y <= halfMBoxSize.y &&
boxSize.z <= halfMBoxSize.z;
}
// 对应 Octree::_getChildIndexes:只比较中心定下标
void _getChildIndexes(const AABB& box, int* x, int* y, int* z) const {
Vec3 center = (mBox.max + mBox.min) / 2;
Vec3 ncenter = (box.max + box.min) / 2;
*x = (ncenter.x > center.x) ? 1 : 0;
*y = (ncenter.y > center.y) ? 1 : 0;
*z = (ncenter.z > center.z) ? 1 : 0;
}
// 对应 Octree::_getCullBounds:盒 ± 半尺寸,松重叠区
void _getCullBounds(AABB& b) const {
b.min = mBox.min - mHalfSize;
b.max = mBox.max + mHalfSize;
}
void _addNode(OctreeNode* n) {
mNodes.push_back(n);
n->setOctant(this);
_ref();
}
void _removeNode(OctreeNode* n) {
mNodes.erase(std::find(mNodes.begin(), mNodes.end(), n));
n->setOctant(nullptr);
_unref();
}
int numNodes() const { return mNumNodes; }
private:
// 对应 Octree::_ref/_unref:自身 + 所有祖先计数
void _ref() {
mNumNodes++;
if (mParent) mParent->_ref();
}
void _unref() {
mNumNodes--;
if (mParent) mParent->_unref();
}
};
// 对应 OgreOctreeSceneManager.cpp 顶部 Intersection 枚举
enum Intersection { OUTSIDE = 0, INSIDE = 1, INTERSECT = 2 };
// 对应静态 intersect(AABB one, AABB two):盒-盒相交判定
Intersection intersect(const AABB& one, const AABB& two) {
if (one.isNull() || two.isNull()) return OUTSIDE;
if (one.isInfinite()) return INSIDE;
if (two.isInfinite()) return INTERSECT;
const Vec3& insideMin = two.min;
const Vec3& insideMax = two.max;
const Vec3& outsideMin = one.min;
const Vec3& outsideMax = one.max;
if (insideMax.x < outsideMin.x || insideMax.y < outsideMin.y ||
insideMax.z < outsideMin.z || insideMin.x > outsideMax.x ||
insideMin.y > outsideMax.y || insideMin.z > outsideMax.z)
return OUTSIDE;
bool full = (insideMin.x > outsideMin.x && insideMin.y > outsideMin.y &&
insideMin.z > outsideMin.z && insideMax.x < outsideMax.x &&
insideMax.y < outsideMax.y && insideMax.z < outsideMax.z);
return full ? INSIDE : INTERSECT;
}
// 对应 OctreeSceneManager 的插入/更新/查询子集
class OctreeSceneManager {
public:
Octree* mOctree = nullptr;
int mMaxDepth = 0;
OctreeSceneManager(const AABB& box, int depth) {
mOctree = new Octree(nullptr);
mMaxDepth = depth;
mOctree->mBox = box;
mOctree->mHalfSize = (box.max - box.min) / 2;
}
// 对应 OctreeSceneManager::_addOctreeNode:深度受限递归下放
void _addOctreeNode(OctreeNode* n, Octree* octant, int depth = 0) {
const AABB& bx = n->getWorldAABB();
if ((depth < mMaxDepth) && octant->_isTwiceSize(bx)) {
int x, y, z;
octant->_getChildIndexes(bx, &x, &y, &z);
if (octant->mChildren[x][y][z] == nullptr) {
octant->mChildren[x][y][z] = new Octree(octant);
const Vec3& octantMin = octant->mBox.min;
const Vec3& octantMax = octant->mBox.max;
Vec3 min, max;
if (x == 0) {
min.x = octantMin.x;
max.x = (octantMin.x + octantMax.x) / 2;
} else {
min.x = (octantMin.x + octantMax.x) / 2;
max.x = octantMax.x;
}
if (y == 0) {
min.y = octantMin.y;
max.y = (octantMin.y + octantMax.y) / 2;
} else {
min.y = (octantMin.y + octantMax.y) / 2;
max.y = octantMax.y;
}
if (z == 0) {
min.z = octantMin.z;
max.z = (octantMin.z + octantMax.z) / 2;
} else {
min.z = (octantMin.z + octantMax.z) / 2;
max.z = octantMax.z;
}
octant->mChildren[x][y][z]->mBox = AABB{min, max};
octant->mChildren[x][y][z]->mHalfSize = (max - min) / 2;
}
_addOctreeNode(n, octant->mChildren[x][y][z], depth + 1);
} else {
octant->_addNode(n);
}
}
// 对应 OctreeSceneManager::_updateOctreeNode
void _updateOctreeNode(OctreeNode* onode) {
const AABB& box = onode->getWorldAABB();
if (box.isNull()) return;
if (onode->getOctant() == nullptr) {
// 不在根盒内 → 直接挂根;否则从根下放
if (!onode->_isIn(mOctree->mBox))
mOctree->_addNode(onode);
else
_addOctreeNode(onode, mOctree);
return;
}
if (!onode->_isIn(onode->getOctant()->mBox)) {
_removeOctreeNode(onode);
if (!onode->_isIn(mOctree->mBox))
mOctree->_addNode(onode);
else
_addOctreeNode(onode, mOctree);
}
}
void _removeOctreeNode(OctreeNode* n) {
Octree* oct = n->getOctant();
if (oct) oct->_removeNode(n);
n->setOctant(nullptr);
}
// 对应 OctreeSceneManager::findNodesIn:盒范围查询
void findNodesIn(const AABB& box, std::list<OctreeNode*>& list,
OctreeNode* exclude = nullptr) {
_findNodes(box, list, exclude, false, mOctree);
}
private:
// 对应静态 _findNodes(const AxisAlignedBox&, ...):cull 剪枝 + full 加速
static void _findNodes(const AABB& t, std::list<OctreeNode*>& list,
OctreeNode* exclude, bool full, Octree* octant) {
if (!full) {
AABB obox;
octant->_getCullBounds(obox);
Intersection isect = intersect(t, obox);
if (isect == OUTSIDE) return;
full = (isect == INSIDE);
}
for (OctreeNode* on : octant->mNodes) {
if (on == exclude) continue;
if (full) {
list.push_back(on);
} else if (intersect(t, on->getWorldAABB()) != OUTSIDE) {
list.push_back(on);
}
}
for (int i = 0; i < 2; ++i)
for (int j = 0; j < 2; ++j)
for (int k = 0; k < 2; ++k) {
Octree* child = octant->mChildren[i][j][k];
if (child) _findNodes(t, list, exclude, full, child);
}
}
};
} // namespace ogre_repro
int main() {
using namespace ogre_repro;
// 根盒 [-100,100]^3,最大深度 4
AABB rootBox{{-100, -100, -100}, {100, 100, 100}};
OctreeSceneManager sm(rootBox, 4);
CHECK_EQ(sm.mOctree->mHalfSize.x, 100.0f);
CHECK_EQ(sm.mOctree->mHalfSize.y, 100.0f);
CHECK_EQ(sm.mOctree->mHalfSize.z, 100.0f);
// 四个测试对象
OctreeNode* a = new OctreeNode(AABB{{4, 4, 4}, {6, 6, 6}}); // 中心(5,5,5) 尺寸2
OctreeNode* b = new OctreeNode(AABB{{-62, -62, -62}, {-58, -58, -58}}); // 中心(-60,-60,-60) 尺寸4
OctreeNode* c = new OctreeNode(AABB{{-45, -45, -45}, {45, 45, 45}}); // 中心(0,0,0) 尺寸90
OctreeNode* d = new OctreeNode(AABB{{499, 499, 499}, {501, 501, 501}}); // 中心(500,500,500) 根外
// _isTwiceSize:能塞进子节点 = 尺寸 <= 父半尺寸
AABB smallBox{{0, 0, 0}, {10, 10, 10}};
CHECK(sm.mOctree->_isTwiceSize(smallBox));
AABB infinite{{-1e20f, -1e20f, -1e20f}, {1e20f, 1e20f, 1e20f}};
CHECK(!sm.mOctree->_isTwiceSize(infinite));
AABB hugeBox{{-150, -150, -150}, {150, 150, 150}};
CHECK(!sm.mOctree->_isTwiceSize(hugeBox));
AABB boundaryBox{{-50, -50, -50}, {50, 50, 50}}; // 尺寸100 == halfSize
CHECK(sm.mOctree->_isTwiceSize(boundaryBox));
// _getChildIndexes:只比较中心
int x, y, z;
AABB boxNeg{{-6, -6, -6}, {-4, -4, -4}}; // 中心(-5,-5,-5)
sm.mOctree->_getChildIndexes(boxNeg, &x, &y, &z);
CHECK_EQ(x, 0);
CHECK_EQ(y, 0);
CHECK_EQ(z, 0);
AABB boxMix{{4, -6, -6}, {6, -4, -4}}; // 中心(5,-5,-5)
sm.mOctree->_getChildIndexes(boxMix, &x, &y, &z);
CHECK_EQ(x, 1);
CHECK_EQ(y, 0);
CHECK_EQ(z, 0);
AABB boxPos{{4, 4, 4}, {6, 6, 6}}; // 中心(5,5,5)
sm.mOctree->_getChildIndexes(boxPos, &x, &y, &z);
CHECK_EQ(x, 1);
CHECK_EQ(y, 1);
CHECK_EQ(z, 1);
// A 沿 (1,1,1) 下放 4 层 → [0,12.5]^3
sm._addOctreeNode(a, sm.mOctree);
CHECK(a->getOctant() != nullptr);
CHECK(vecEq(a->getOctant()->mBox.min, Vec3{0, 0, 0}));
CHECK(vecEq(a->getOctant()->mBox.max, Vec3{12.5f, 12.5f, 12.5f}));
CHECK_EQ(sm.mOctree->numNodes(), 1);
// B 沿 (-1,-1,-1) 下放 4 层 → [-62.5,-50]^3
sm._addOctreeNode(b, sm.mOctree);
CHECK(vecEq(b->getOctant()->mBox.min, Vec3{-62.5f, -62.5f, -62.5f}));
CHECK(vecEq(b->getOctant()->mBox.max, Vec3{-50, -50, -50}));
CHECK_EQ(sm.mOctree->numNodes(), 2);
// C 尺寸 90 在根盒还能下放一层,但子盒半尺寸 50 容不下 → 停在下层 octant
sm._addOctreeNode(c, sm.mOctree);
CHECK(vecEq(c->getOctant()->mBox.min, Vec3{-100, -100, -100}));
CHECK(vecEq(c->getOctant()->mBox.max, Vec3{0, 0, 0}));
CHECK_EQ(sm.mOctree->numNodes(), 3);
// A 移动到 (80,80,80):出原 octant → 摘除重插,计数不变
a->mWorldAABB = AABB{{79, 79, 79}, {81, 81, 81}};
sm._updateOctreeNode(a);
CHECK(vecEq(a->getOctant()->mBox.min, Vec3{75, 75, 75}));
CHECK(vecEq(a->getOctant()->mBox.max, Vec3{87.5f, 87.5f, 87.5f}));
CHECK_EQ(sm.mOctree->numNodes(), 3);
// D 在根盒外 → 直接挂根
sm._updateOctreeNode(d);
CHECK(d->getOctant() == sm.mOctree);
CHECK_EQ(sm.mOctree->numNodes(), 4);
// 范围查询
std::list<OctreeNode*> res;
sm.findNodesIn(AABB{{-10, -10, -10}, {10, 10, 10}}, res);
CHECK_EQ(res.size(), 1u);
CHECK(res.front() == c);
res.clear();
sm.findNodesIn(AABB{{75, 75, 75}, {85, 85, 85}}, res);
CHECK_EQ(res.size(), 1u);
CHECK(res.front() == a);
res.clear();
sm.findNodesIn(AABB{{75, 75, 75}, {85, 85, 85}}, res, a);
CHECK_EQ(res.size(), 0u);
res.clear();
sm.findNodesIn(AABB{{-65, -65, -65}, {-55, -55, -55}}, res);
CHECK_EQ(res.size(), 1u);
CHECK(res.front() == b);
// 松包围盒:根盒 ± 半尺寸 = [-200,200]^3
AABB cull;
sm.mOctree->_getCullBounds(cull);
CHECK(vecEq(cull.min, Vec3{-200, -200, -200}));
CHECK(vecEq(cull.max, Vec3{200, 200, 200}));
return lab::report("03-3 Octree 场景管理:插入/移动/范围查询");
}
本机实测(Apple clang 16,clang++ -std=c++20 -Wall):编译零警告,断言 40/40 通过。
小结
- 松八叉树让每个八分格重叠 0.5,只要对象尺寸不超过父格半尺寸就能整体下放,无需切分。
_isTwiceSize准入、_getChildIndexes只看中心定下标,二者共同决定下放路径。_addOctreeNode深度受限递归,子格懒创建、由父格对半劈;移动出格即摘除重插,出根盒挂根。OctreeCamera把 6 平面判定升级为 NONE/PARTIAL/FULL 三态,FULL 桶整桶免测入队。findNodesIn用松包围盒做桶级剪枝,完全落入查询的桶整桶收集,其余逐节点精测。
阅读导航:上一节:3.2 视锥剔除 · 下一节:4.1 光源类型 。
继续阅读
探索更多技术文章
浏览归档,发现更多关于系统设计、工具链和工程实践的内容。