| adie's blog |
|
· Blender
· CUDA 笔记 · Windows平台编译 ffmpeg 一 (含H265 on RTMP, libsrt) · Windows平台编译 ffmpeg 二 · Samba 配置只能上传下载不能删除修改的方法   
|
八叉树
2012-08-14 16:11:22
一，引入八叉树的动机：
渲染一个场景，就是渲染一个三角形列表TriangleList，最简单的算法就是：遍历它，渲染其中每个三角形。考虑到并非所有三角形都是视见体之内，可以对上述方法进行改进，即只渲染可见的三角形。于是提出如何高效地检索可见的三角形的问题。因为顺序查找表效率低，所以就用查找树表，于是就有了八叉树。（可见，八叉树思想与大学数据结构课本中“查找”一章思路如出一辙）。
二，八叉树机制流程：
（1）离线阶段建立八叉树（所以对算法效率没有限制）。
（2）游戏开始后每一帧使用八叉树检索可见面。
三，八叉树的实现：
1，建立八叉树：
make8dTree(TriangleList,proot){//根据三角形列表TriangleList建立八叉树proot 注：按以上算法建立的八叉树具有以下特点：
（1）八叉树的每个非叶节点的度均为8。
（2）八叉树所有叶子节点的TriangleList均为空。
（3）每个三角形都被放置到了包含它的体积最小的节点中。
2，检索八叉树并渲染场景：
search8dTree_and_renderScene(proot){//检索八叉树同时渲染场景 四，八叉树的应用范围：
由于八叉树是离线创建，以后不更新，所以只适用于场景的静态部分。
▲评论 |
