有了四叉树之后，如何利用它的优势呢？首先我们考虑简单的视见体裁剪(View Frustum Culling，以下简称VFC)。相信很多接触过基本图形优化的人都应该熟悉VFC，VFC的作用既是对那些明显位于可见平截头体之外的多边形在把它们传给显卡之前剔除掉。这个过程由CPU来完成。虽然简单，但它却非常有效。VFC过程如下：
1.为每个节点计算包围球。包围球可以简单的以中心顶点为球心，最大坐标值点(节点所覆盖的所有顶点的最大X、Y、Z值作为此点的坐标值)到球心的距离为半径。
2.根据当前的投影和变换矩阵计算此时可视平截头体的六个平面方程。这一步可以参考Azure的Blog上的一篇文章，这篇文章给出了VFC的具体代码。单击这里。
3.从树的根结点以深度优先的顺序遍历树。每次访问节点时，测试该节点包围球与视见体的相交情况。在下面的情况下，包围球与视见体相交：
1) 球心在六个平面所包围的凸状区域内部。
2) 球心在六个平面所包围的凸状区域外部，但球心到某个平面的距离小于半径。
4.如果相交测试显示包围球和视见体存在交集，继续递归遍历此节点的4个子节点，如果此节点已经是叶节点，则这个节点应被绘制。如果不存在交集，放弃这个节点，对于这个节点的所有子节点不再递归检查。因为如果一个节点不可见，那么其子节点一定不可见。
这样，我们剔除了那些不在视见体内的地形区域，节约了一些资源。但这还不够。在某些情况下，VFC可能还会指出整个地形都可见，在这种情况下，将这么多三角形都画出显然是不可取的。
因此还要考虑地形的细节层次(LOD)。我们应该考虑到，地形不可能所有部分都一样平坦或陡峭。对于平坦的部分，我们用过多的三角形去描述是没有意义的。而对于起伏程度较大的区域，只有较多的三角形数量才不让人感到尖锐的棱角。再者，无论地形起伏程度如何，那些距离视点很远的区域，也没有必要花费太多的资源去渲染，毕竟它们投影到屏幕上的面积很小，对其进行简化也是必要的。
既然我们要对起伏程度不同的区域采用不同的细节级别，我们首先必须找到一种描述地形起伏程度的量。与其说起伏程度，不如说是地形的某个顶点因为被简化后而产生的误差。要计算这个误差，我们先要了解地形是如何被简化的。
考虑下图所示的地形块，它的渲染结果如下图右图所示。
现在如果要对所需渲染的三角形进行简化，我们可以考虑这个地形块每条边中间的顶点(下图左侧红色点)：
如果将这些红色的顶点剔除，我们可以得到上图右边所示的简化后的网格。误差就在这一步产生。由于红色的顶点被剔除后，原本由红色顶点所表示的地形高度现在变成了两侧黑色顶点插值后的高度。这个高度就是误差。如下图。
因此，对于每个节点，我们先计算这个节点所有边中点被删除后所造成的误差，分别记为ΔH1, ΔH2, ΔH3, ΔH4。如果这个节点包含子节点，递归计算子节点的误差，并把四个子节点的误差记为ΔHs1, ΔHs2, ΔHs3, ΔHs4。这个节点的误差就是这八个误差值中的最大值。由于这是一个递归的过程，因此应该把这个过程加到四叉树的生成过程中，并向四叉树的数据结构中加入一个误差变量。如下。
struct QuadTreeNode
{
QuadTreeNode *Children;
int CenterX,CenterY;
int HalfRange;
float DeltaH; //节点误差值
}
下面来看一下地形的具体渲染过程。
首先，我们位于四叉树的根结点。我们此时考虑根结点的误差，如果这个误差小于一个阈值，直接使用根结点的中心点以及此节点的四个边角点作为顶点渲染一个三角扇形，这个三角扇形就是渲染出来的地形。但是更经常的情况下，根结点的误差值是很大的，因此算法认为要对根结点进行细分，以展现更多细节。于是对于根结点的每个子节点，重复这个步骤，即检查它的误差值是否大于阈值，如果大于，直接渲染这个节点，如果小于，递归细分节点。目前我们的算法伪代码如下。
procedure DrawTerrain(QuadTreeNode *node)
{
if (node->DeltaH > k)
{
for (i=0;i<4;i++)
{
DrawTerrain(node->Children);//递归划分
}
}
else
{
GraphicsAPI->DrawPrimitive(node);//以节点的中心点和四个边角点绘制三角扇形
}
}
这个伪代码在一个较高的层次上表述了算法的基本思想。然而我们还有许多问题要考虑。其一是目前我们仅仅考虑了地形的细节层次和地形表面起伏程度的关系，但还应该考虑地形块距离视点远近跟地形细节层次的关系。解决这个问题很简单，我们只需在伪代码的条件中加入距离这一因素即可。即把
if (node->DeltaH > k)
{
...
}
else ...
改为：
if (node->DeltaH / d > k)
{
...
}
else ...
其中d为节点中心点与视点之间的距离。而事实上，当细节程度与距离的平方成反比时，能够减少更多的三角形，而且视觉效果更好，只要阈值k设置得当，根本感觉不出地形因为视点的移动而发生几何形变。因此，我们最终的条件式为：
node->DeltaH / d2 > k
还有一个很重要的问题，就是这个算法所产生的地形会因为节点之间细节层次的不同而产生裂缝。下图说明了裂缝的产生原因。
有两个方法可以解决这个问题，一个方法是删除左侧节点中产生裂缝的顶点，使两条边能够重合。另一种方法是人为地在右侧地形块中插入一条边，这条边连接中心点和造成裂缝的顶点，从而消除裂缝。在渲染地形时，可以采取下面的办法避免裂缝的产生：
1.在预处理阶段，为所有顶点创建一个标记数组，标记以该顶点为中心点的节点在某一帧是否被细分。如果被细分则标记为1，否则标记0。
2.从根节点开始，以广度优先的顺序遍历四叉树，使用之前提出的条件式判断节点是否需要分割。如果公式表明需要分割，并且与节点相邻的四个节点的中心点都被标记为1，那么把这个节点及其四个子节点的标记设为1，并递归细分这个节点。否则，将这个节点的标记设为1，把这个节点的四个子节点的标记设为0，然后采用下面的方法绘制这个地形块：
1)将节点的中心顶点和四个边角点添加到即将绘制的三角扇形列表中。
2)依次检查与四条边相邻的节点的标记数组，如果相应的标记为1，那么将该点添加到三角扇形的顶点列表中，否则跳过该点。
3)绘制三角扇形。
我们最终的伪代码如下。
bool IsNodeInFrustum(QuadTreeNode *node)
{
return (node->BoudingSphere in frustum);
}
bool NeighbourIsValid(QuadTreeNode *node)
{
return (all four neighbours of node are identified as 1)
}
void RenderTerrain()
{
list<QuadTreeNode *>next,current,draw;
int level =0;
current.push_back(root);
while (current.size()!=0)
{
for each thisNode in current
{
if (!IsNodeInFrustum(thisNode))
continue;
if (level == MaxResolution)
draw.push_back(thisNode);
else
if (thisNode->DeltaH/(distance*distance) > k
&& NeighbourIsValid(thisNode) )
{
SetFlag(thisNode,1);
for j= 1 to 4
{
next.push_back(thisNode->Children[j]);
SetFlag(thisNode->Children[j],1)
}
}
else
{
SetFlag(thisNode,1);
for j= 1 to 4
{
draw.push_back(thisNode->Children[j]);
SetFlag(thisNode->Children[j],0);
}
}
}
SwapList(current,next);
next.clear();
level++;
}
GraphicsAPI->DrawPrimitives(draw);
} | 
IP卡
狗仔卡
发表于 2006-8-7 15:32:39
2006-7-31 15:48:08)
提升卡
置顶卡
沉默卡
喧嚣卡
变色卡
千斤顶
显身卡
楼主
