八叉树

一，引入八叉树的动机：

  渲染一个场景，就是渲染一个三角形列表TriangleList，最简单的算法就是：遍历它，渲染其中每个三角形。考虑到并非所有三角形都是视见体之内，可以对上述方法进行改进，即只渲染可见的三角形。于是提出如何高效地检索可见的三角形的问题。因为顺序查找表效率低，所以就用查找树表，于是就有了八叉树。（可见，八叉树思想与大学数据结构课本中“查找”一章思路如出一辙）。

二，八叉树机制流程：

（1）离线阶段建立八叉树（所以对算法效率没有限制）。

（2）游戏开始后每一帧使用八叉树检索可见面。

三，八叉树的实现：

1，建立八叉树：

make8dTree(TriangleList,proot){//根据三角形列表TriangleList建立八叉树proot  

    proot->space=space;  

    proot->TriangleList=TriangleList;  

    //开始递归  

    make8dTree_inn(proot);  

}  

make8dTree_inn(p){//递归核心  

    if(p->TriangleList.size()==0)return;  

    //建立八个子节点  

    for(i=0;i<=7;i++){  

        p->p=new Cnod();  

        p->p->space=subSpace(p->space,i);  

    }  

    //将父节点TriangleList中的三角形分发给子节点（跨子节点的三角形父节点自己保留）  

    for(i=0;i<=p->TriangleList.size()-1;i++){  

        if(p->TriangleList不跨子节点){  

            将p->TriangleList加入到包含它的子节点  

                将p->TriangleList从p->TriangleList中删除  

        }  

    }  

    //对子节点进行递归  

    for(i=0;i<=p->p.size()-1;i++){  

        make3dTree_inn(p->p);  

    }  

}  

注：按以上算法建立的八叉树具有以下特点：

（1）八叉树的每个非叶节点的度均为8。

（2）八叉树所有叶子节点的TriangleList均为空。

（3）每个三角形都被放置到了包含它的体积最小的节点中。

2，检索八叉树并渲染场景：

search8dTree_and_renderScene(proot){//检索八叉树同时渲染场景  

    search8dTree_and_renderScene_inn(proot);  

}  

search8dTree_and_renderScene_inn(p){//递归核心  

    if(p->space与视锥不相交)return;  

    渲染p->TriangleList中的每个三角形  

        //对子节点进行递归  

        for(i=0;i<=7;i++){  

            search8dTree_and_renderScene_inn(p->p);  

        }  

} 

四，八叉树的应用范围：

  由于八叉树是离线创建，以后不更新，所以只适用于场景的静态部分。