《OGRE 3D 渲染引擎原理与架构》3.3 Octree 场景管理

OctreeSceneManager 用松八叉树把场景节点按包围盒下放到深度受限的 8 分叉里:尺寸能塞进子盒就按中心定下标递归下放,否则停在本层;可见性收集与范围查询都用松包围盒剪枝。lab 复现插入/移动/范围查询全过程。

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 的底层实现。

源码定位

上游引用固定到 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 光源类型 。

继续阅读

探索更多技术文章

浏览归档,发现更多关于系统设计、工具链和工程实践的内容。

全部文章 返回首页

「books」更多文章

  1. 《大规模分布式计算深入解析》15.3 落地:从 Neo4j 到自研图引擎
  2. 《大规模分布式计算深入解析·图计算与图数据库内核》 · 目录与学习路径(45 篇)
  3. 《大规模分布式计算深入解析》15.2 十一卷主线:从切分到图