banner.gif adie's blog
主页 博客 胭脂泪,相留醉,几时重,自是人生长恨水长东
统计
日志总数: 127
评论总数: 123
日志分类
日志归档
最近日志
最近评论
订阅
rss2.gif

atom.gif

google_rss
zt.gif 【编程】 阅读 6145 次

八叉树

2012-08-14 16:11:22
一,引入八叉树的动机:
  渲染一个场景,就是渲染一个三角形列表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);  
  •         }  


  • 四,八叉树的应用范围:
      由于八叉树是离线创建,以后不更新,所以只适用于场景的静态部分。

    ▲评论

    X 正在回复:
    姓 名: 留下更多信息
    性 别:
    邮 件:
    主 页:
    Q Q:
    来 自:
    职 业:
    评 论:
    验 证:


    Valid HTML 4.01 Strict Valid CSS!
    Copyleft.A!die Software Studio.ADSS
    Power by webmaster@adintr.com