引擎技术研究之场景管理------四叉树与视椎剔除技术

先说一下视椎的概念：视椎是摄像机可见的空间体积，外观就像截掉顶部的金字塔。视椎剔除就是将在视锥外的物体不进行渲染操作，以加快运行速度。大型场景经常用四叉树的技术来管理，即用四叉树的方式进行空间划分。

一：场景管理中四叉树的划分

现以一地面为例讨论四叉树的划分技术。

地面是由很多个三角形组成，两个三角形合成一正方形。如不进行四叉树划分，则需遍历所有三角形以确定被剔除物体，算法复杂度大。如下图所示：

当我们用四茶树来管理物体时，可把地面看成一大正方形，将视椎的横截面与地面重合,并作第一次四等分划分，如此，对四个正方形区域作第一次遍历后，只需对视椎截面所在的上两个正方形作第二次深入遍历。如图所示：

将有视椎截面的区域作第二次四等分划分，同理再作第三次划分，同样只需对视椎截面所在的区域进行下一次深入的划分。如图所示：

这样不断地划分，而所需遍历的三角形随着划分层次的增加而减少，从而降低了复杂度，加快了渲染速度。

二：四叉树的构建：

其基本属性有：四个子节点及其索引和坐标，父节点，节点所在层次，节点的可见状态等。如图：

下面计算各节点索引及其坐标：

设子节点0索引Index[0]为0，四个子节点坐标pos由外面传入,地面宽度为width, 长度为lenght,划分层次为3，则有8行8列总共64个节点。

Index[0]=0，

Index[1]=width,

Index[2]=(width+1)*length,

Index[3]=(width+1)*(lenght+1)-1

经第一次划分后生成四个正方形：

（0,down,left,center）(down,1,center,right) (left,center,2,up) (center,right,up,3)

节点down索引：Index[down]=(Index[1]+Index[0])/2

节点left索引: Index[left]=(Index[0]+Index[2])/2

节点 up 索引：Index[ up ]=(Index[2]+Index[3])/2

节点right索引：Index[right]=(Index[1]+Index[3])/2

节点center索引:Index[center]=(Index[up]+Index[down])/2

同理可根据各节点坐标计算其四个子节点坐标，如此循环计算，即得各层节点索引和坐标。

三：四叉树在场景中的应用

怎样把具体物体和四叉树联系起来呢?方法如下：

首先根据地形参数生成一四叉树，然后在四叉树的所有节点中寻找这样的节点:当前物体的位置在该节点的四个子节点围成的正方形区域里。接着将此物体加入该节点的objects列表，object类型为物体的类型，再设计算法利用当前摄像机计算出每个节点的可见状态，分完全可见，完全不可见，部分可见三个状态：若全部可见，则该节点及其所有下层子节点均设为可见状态。若完全不可见，则该节点及其所有下层子节点均设为不可见状态，若部分可见，则设该节点为可见后，再用算法计算其四个子节点的可见状态，如此递归调用该算法，再根据节点是否是叶子节点来设置其附属object的可见性。到渲染阶段，根据节点中object的可见性，确定其渲染状态。

四：场景划分在优化碰撞检测中的应用

在复杂场景中，由于用户的交互和物体的运动，物体间经常可能发生碰撞，此时为保持环境的真实性，需要及时检测到这些碰撞，并计算相应的碰撞反应，更新绘制结果，否则物体建会发生穿透现象，破坏场景的真实感。先举个碰撞检测的例子：场景里有个人，人行走的时候需要与场景的物体进行碰撞检测，那样才能使人不至于走到物体内部。这里有两个问题需要解决，一是检测到碰撞的发生和碰撞的位置，二是计算碰撞后的反应。而碰撞检测是计算碰撞反应的先决条件，因此，碰撞检测是复杂场景中必不可少的部分。而复杂场景中通常包含大量物体，加上物体的形状复杂，假如不做场景管理，那就要遍历场景里的所有物体，看看它有没有与人体发生碰撞。场景里物体愈多，那检测起来就越慢。因此，复杂场景中碰撞检测的研究目标是如何在很高的实时交互的要求下完成对大量复杂物体的碰撞检测。若有了场景管理，譬如用四叉树进行空间划分，那可以先计算出人物在哪个节点里，然后在碰撞检测的时候，就可以只检测与它相同（以及邻接）节点里的物体就够了，就不需要检测所有物体。