void OctreeSceneManager::_addOctreeNode( OctreeNode * n, Octree *octant, int depth )
{
// Skip if octree has been destroyed (shutdown conditions)
if (!mOctree)
return;
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 ) )//深度从0开始递归,octree根结点是n包围盒的两倍
{
int x, y, z;
octant -> _getChildIndexes( bx, &x, &y, &z );//octant有八个空间,或者说是坐标系的八个象限，bx
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;
}
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;
}//根据n所在的象限的位置，计算包围盒
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 );//至到父包围的半径小于子包围盒的两倍，则挂在当前结点上
}
}
void _findNodes( const Ray &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 );//如果在扩张后的包围盒内部，但不相交，则full = true,否则full = false
}
while ( it != octant -> mNodes.end() )//向下遍历
{
OctreeNode * on = ( *it );
if ( on != exclude ) //排除exclude节点
{
if ( full ) //在扩张后的包围盒内部
{
list.push_back( on );
}
else //如果不在扩张后的包围盒内部，则和原始包围盒重新求交
{
Intersection nsect = intersect( t, on -> _getWorldAABB() );
++it;
}
Octree* child;//重新向下遍历
if ( (child=octant -> mChildren[ 1 ][ 0 ][ 0 ]) != 0 )
_findNodes( t, list, exclude, full, child );
if ( (child=octant -> mChildren[ 0 ][ 1 ][ 0 ]) != 0 )
_findNodes( t, list, exclude, full, child );
if ( (child=octant -> mChildren[ 1 ][ 1 ][ 0 ]) != 0 )
_findNodes( t, list, exclude, full, child );
if ( (child=octant -> mChildren[ 0 ][ 0 ][ 1 ]) != 0 )
_findNodes( t, list, exclude, full, child );
if ( (child=octant -> mChildren[ 1 ][ 0 ][ 1 ]) != 0 )
_findNodes( t, list, exclude, full, child );
if ( (child=octant -> mChildren[ 0 ][ 1 ][ 1 ]) != 0 )
_findNodes( t, list, exclude, full, child );
if ( (child=octant -> mChildren[ 1 ][ 1 ][ 1 ]) != 0 )
_findNodes( t, list, exclude, full, child );
}
注:其他类型求交，只是换了intersector函数
void OctreeSceneManager::_updateOctreeNode( OctreeNode * onode )
{
const AxisAlignedBox& box = onode -> _getWorldAABB();
if ( box.isNull() )
return ;
// Skip if octree has been destroyed (shutdown conditions)
if (!mOctree)//根结点已经破坏
return;
if ( onode -> getOctant() == 0 )//没有挂到节点上
{
//if outside the octree, force into the root node.
if ( ! onode -> _isIn( mOctree -> mBox ) )//onode不在父节点的包围盒内，在直接挂在父节点
mOctree->_addNode( onode );
else
_addOctreeNode( onode, mOctree ); //否则遍历，挂在合适的节点下
return ;
}
if ( ! onode -> _isIn( onode -> getOctant() -> mBox ) )//onode不再父节点的包围盒
{
_removeOctreeNode( onode );
//if outside the octree, force into the root node.
if ( ! onode -> _isIn( mOctree -> mBox ) ) //不在根节点包围盒内，则直接挂在根结点
mOctree->_addNode( onode );
else
_addOctreeNode( onode, mOctree );
}
}
void OctreeSceneManager::resize( const AxisAlignedBox &box )
{
std::list < SceneNode * > nodes;
std::list < SceneNode * > ::iterator it;
_findNodes( mOctree->mBox, nodes, 0, true, mOctree );//在包围盒box内部的nodes
OGRE_DELETE mOctree;
mOctree = OGRE_NEW Octree( 0 ); //生成新的根节点
mOctree->mBox = box;
const Vector3 min = box.getMinimum();
const Vector3 max = box.getMaximum();
mOctree->mHalfSize = ( max - min ) * 0.5f;
it = nodes.begin();
while ( it != nodes.end() )
{
OctreeNode * on = static_cast < OctreeNode * > ( *it ); //重新挂在新的根节点下
on -> setOctant( 0 );
_updateOctreeNode( on );
++it;
}
}