|
|
实时三维地形渲染
摘要：本文讨论了实时三维地形渲染中常用的层次细节和可见性测试技术，给出了一种基于DirectX和索引缓冲区的实现。为了防止了跳跃现象的出现，对高度值的改变进行了平滑处理。使用阴影体技术实现实时阴影的构造
关键词：层次细节；地形渲染；可见性测试；实时优化自适应网格；阴影体
Real-Time 3D Terrain Rendering
Faculty of Computer & Information Science，Southwest China University，Chongqing 400715，China
Abstract: This article talks about common technologies in terrain rendering：level of detail and field of view and provide a implementation using DirectX and index buffers. Height values are changed smoothly to ease poping. Build real-time shadows with shadow volumn
Key word: LOD, Terrain Rendering, Field of View, ROAM, Shadow Volumn
目录
一．什么是地形，什么是地形渲染 …………………………………………………… 5
二．地形信息的组织 …………………………………………………………………… 5
1. 高度图 ………………………………………………………………………………… 5
2 地形结构……………………………………………………………………………… 5
3. 与Patch对齐的纹理…………………………………………………………………… 6
三．层次细节(LOD: Level of Detail) ………………………………………………… 6
1．高度图的局限性……………………………………………………………………… 6
2．层次细节的引入……………………………………………………………………… 6
3．分割决策……………………………………………………………………………… 7
4．三角形的合并………………………………………………………………………… 9
5．对三角形二叉树的维护……………………………………………………………… 9
6. 三角池 ……………………………………………………………………………… 9
7．对缝隙的处理………………………………………………………………………… 11
8.平滑处理 ……………………………………………………………………………… 14
四．可见性测试 ………………………………………………………………………… 16
1．可见性测试的目的…………………………………………………………………… 16
2. 视域的构造 …………………………………………………………………………… 16
3．圆柱体剔除…………………………………………………………………………… 18
4．大尺度的可见性测试——四叉树…………………………………………………… 19
5．可见性信息的保存…………………………………………………………………… 20
五．输出三角形………………………………………………………………………… 20
1.索引缓冲区的使用…………………………………………………………………… 20
2．三角形的输出过程 ………………………………………………………………… 21
3．菱形边界问题 ……………………………………………………………………… 22
4．Patch边界问题 ……………………………………………………………………… 23
5．背面剔除 …………………………………………………………………………… 24
6．进入渲染管线 ……………………………………………………………………… 24
六．整体流程 …………………………………………………………………………… 25
七．关于HLSL ……………………………………………………………………… 25
八．阴影构造 ……………………………………………………………………… 27
1.阴影体网格的生成 ………………………………………………………………… 27
2．渲染阴影体 ……………………………………………………………………… 28
九．关于示例代码……………………………………………………………………… 29
参考文献 …………………………………………………………………………… 29
致谢 ……………………………………………………………………………………… 29
一．什么是地形，什么是地形渲染
地形是对各种不同的地表形态的描述：险峻的山脉，广阔的草原，崎岖的丘陵等等。地形渲染最基本的研究内容就是如何高效地、实时地将这些自然特征渲染到屏幕上。在此基础上，它还要研究其他自然元素的渲染，比如河流、云雾等等。
二．地形信息的组织
1.高度图
高度图(Height Map)是地形的高度信息在内存中的表示。高度图可以理解为地形高度值的二维数组HeightMap[m][n],m和n分别表示世界的宽和高。对于地形上横坐标为x，纵坐标为y的一点A，它的高度为HeightMap[y][x]。高度值通常用一个无符号的字节来表示，0表示最低高度，255表示最高高度。
高度图有一个很好的特性，那就是它可以与一张灰度位图(Grayscale Bitmap)相互映射。位图的每一个象素点的值也用一个字节来存储，它的值(0-255)与地形高度值的范围相一致，这使得灰度位图成为高度图的理想存储方式。
2．地形结构
整个地形在水平面（既X和Z坐标轴确定的平面）的投影是一个矩形，用T表示，它与一张高度图对应。在X和Z方向上用等距离的直线对T进行分割，形成等大的方格(Patch)。在示例程序中，我们把地形分割成8*8的方格。把每个方格分割成两个等腰直角三角形(图一)。根据高度图中的数据改变三角形每个顶点的高度值（既Y坐标），就得到了地形的最初表示。
图一 高度图被分割成Patch
Figure1 Heightmap can be split into patches
每个Patch表示地形的一个区域，这个区域的地形信息用CPatchMap类的对象来表示。
class CPatchMap
{
public:
static CHeightMap *ms_pHeightMap; // 高度图的指针
WORD m_wX, m_wY; // Patch左上角点的位置
};
3.与Patch对齐的纹理
高度图只能提供地形的高度特征，而自然界中的草地、岩石、冰川等地貌特征仅仅通过高度图是无法刻画的，要刻画这些细节特征需要使用纹理。
每个Patch都对应着一张纹理，这使得纹理资源可以在Patch之间共享，相邻的Patch很可能具有相同的地貌特征，比如都是草地。在代码实现中，使用一个资源池来管理所有的纹理，在加载Patch的纹理之前，首先判断它是否已经被加载到了资源池中，如果在纹理池中没有找到该纹理，再从硬盘上读取，并将其放入资源池。
三．层次细节(LOD: Level of Detail)
1．高度图的局限性
单纯使用高度图的渲染方式实际上是一种Brute Force，现实的地形具有很大的维度，如果把这种大规模的地形分割成相同大小的Patch，Patch的大小如何设置呢？过小的Patch会产生太多的三角形，使得渲染速度达不到要求。过大的Patch会造成渲染出来的地形与实际相差过大，至少我们希望在视点(View Point)附近的地形是相对准确的。
2．层次细节的引入
高度图在实际中的不可用从根本上源于它的完全静态，它提供的是全局一致的细节程度，要模糊就哪里都模糊，要清晰就必须所有的部分都清晰。而我们需要的是基于视点距离的细节，假设我们要开发一款越野赛车的游戏，我们希望眼前出现的地形是清晰而准确的，而远处作为背景的山脉可以是模糊而粗略的。这就是所谓的层次细节。
以下所做的工作可以看作是对高度图的扩展，我们的地形依然以灰度位图作为数据输入，依然是由Patch的2D数组构成的。但是每个Path不再是简单地由两个三角形构成的了。
图二 一个等腰直角三角形可以被分割成两个小的等腰直角三角形
Figure2 A right triangle can be split into two right triangles
LOD依赖于等腰直角三角形的性质。如图二所示，直角顶点和斜边中点的连线可以把一个等腰直角三角形分割成两个全等的等腰直角三角形，这种分割过程可以无限的进行下去。每一个三角形都是两个较小三角形的父三角形，所有的三角形构成了一个二叉树的层次结构。总的来说，LOD就是一种维护三角形二叉树的方法，它根据视点的位置动态的决定哪些三角形应该被分割，哪些三角形应该被合并从而实时的改变渲染地形的细节程度。由这些动态生成的三角形构成的网格叫做动态优化自适应网格(ROAM: Real-time Optimized Adapting Mesh)。
使用TriangleTreeNode结构来描述三角形二叉树中的一个三角形。
typedef struct TriangleTreeNode
{
// conectivity information
TriangleTreeNode *pLChild; // 左子三角形
TriangleTreeNode *pRChild; // 右子三角形
// …
} TriangleTreeNode, *LPTriangleTreeNode;
现在，每个Path是两个三角形二叉树的所有者
class CPatch
{
TriangleTreeNode m_LBase; // Left base child
TriangleTreeNode m_RBase; // Right base child
// …
}
每当三角形被分割的时候，都会有一个新的顶点被生成，它的x和z坐标分别是斜边两个端点的x和z坐标的平均值，y坐标（既高度）从灰度位图得到。这个新生成的顶点代表了灰度位图能够提供的最精确地形信息，而在未分割之前，我们实际上是通过斜边中点来近似的代表这个值的，它们的高度之间存在一个误差值。这就是分割的结果：分割出的三角形二叉树越深，ROAM所刻画的地形与从灰度位图得到的地形信息也就越接近，所需要的系统资源也就越多。
3．分割决策（Split Decisions）
如何来判断一个三角形是否应该被分割呢？我们使用四个量来控制三角形的分割：
1． 距离：所考虑的三角形斜边中点到观察者所处位置的距离。用D表示。
2． 误差值：如图四所分析。用E表示
3． 缩放系数：用S表示。
4． 界限值，用L表示
分割决策可以用以下公式来表示：
Split ? = E * S / D > L
这个公式在进行分割决策的时候综合考虑到了两方面的因素：一、观察者的位置；二、地形本身的特点。靠近观察者的区域有更多的被分割机会，误差值大的区域，比如起伏的山地也有更多的被分割机会。而对于其他的区域，分割得到的三角形二叉树的深度就比较小。
S可以在全局范围内改变层次细节。当S>1的时候，E被放大，更多的三角形等到被分割的机会，且S越大，分割出的三角形数目越多；当S<1的时候，误差值被缩小，三角形被分割的机会减少，且S越小，分割出的三角形数目越少。S值还具有调节视点距离和地形的误差值在分割决策时的优先级的作用：较大的S值使误差值的优先级高，较小的S值使视点距离的优先级高。
在这两个因素中，D值会随着观察者的移动而改变，需要在每一桢都重新计算，而E值反映地形本身的特点，应该在初始化的时候预先计算。具体的做法是：为Patch的两个三角二叉树分别建立一个误差树，误差树是完全二叉树，它的深度为三角二叉树可能被分割到的最大深度（在示例代码中定义为8层），误差树的每个结点存储一定深度的E值。因为是完全二叉树，所以误差树可以用一维数组来存储。
同样可以预先计算的是三角型的高度值，在三角形二叉树中，叶子结点三角形的高度值被定义为三个顶点高度值的最大值，而非叶子结点的三角形的高度被定义为两个子三角形高度值中的最大值。三角形的高度值在进行视域剪裁是必须的（对视域剪裁的讨论将会在稍后进行）。我们把三角形误差的预先计算和高度值的预先计算放在一起进行，误差树的结点也包含高度数据。
typedef struct VarianceTreeNode
{
BYTE btVariance; //agregated variance
BYTE btHeight; //maximum height
} VarianceTreeNode, *LPVarianceTreeNode;
4．三角形的合并
合并是与分割相对应的三角形操作，它只对有且仅有一层子三角形的非叶子结点三角形进行，对于那些误差值小于一定界限的三角形，应当删除它的子三角型，用高度的估计值代替真实值，并且重新调整三角形之间的关联，使得原来与子三角形的关联与本身相关联。在示例代码中，为了防止抖动现象，既三角形频繁的交替进行分割和合并操作，分别设置分割和合并的界限：
图三 分割与合并边界
Figure3 Split and merge limit
5．对三角形二叉树的维护
事实上，从Patch的根结点开始建立三角形二叉树的过程只进行了一次，在这次完整的建立过程中，只存在分割操作，不存在合并操作，且所有的操作都是对叶子结点进行的。
从第二桢开始，只需要对树的根结点进行操作，进行分割或者合并的判断。因为合并最终是对叶子结点的父结点进行的操作，所以需要在结点中保存其父结点的指针。
6．三角池(Triangle Pool)
new和delete运算符基于CRT的malloc和free函数，它们适用于分配和释放大的对象，作为整个系统的核心，如果每次都调用new和delete运算符来生成子三角形、合并三角形，其效率肯定不甚理想。所以有必要专门为三角形提供一种内存管理机制，这就是三角池。
在初始化的时候，三角池会一次性的分配足够的内存，并用初始状态的三角形填充这块内存。
BOOL CTrianglePool::Init(int maxNode)
{
int size = maxNode * sizeof( TriangleTreeNode );
m_pPool = (TriangleTreeNode*)malloc(size);
m_pPool->Reset();
std::uninitialized_fill_n(m_pPool+1, maxNode-1, *m_pPool);
m_cnMaxNode = maxNode;
m_cnNextAvailable = 0;
return TRUE;
}
在合并三角形的时候，它的子三角形的内存并不释放，而是把它们在三角形池中的索引保存在一个容器中：
void CTrianglePool::ReleaseTriangle( TriangleTreeNode* pTriangle )
{
pTriangle->Reset();
int index = pTriangle - this->m_pPool;
recycleVector.push_back( index );
}
当分割三角形的时候，如果容器不为空，就从容器中分配，否则从三角形池初始分配的那些三角形中分配一个新的三角形出来：
BOOL CTrianglePool::AllocTriangle( LPTriangleTreeNode* ppTriangle )
{
int size = recycleVector.size();
if( size != 0 )
{
int index = recycleVector[size -1];
recycleVector.pop_back();
*ppTriangle = m_pPool + index;
return TRUE;
}
else
{
if( m_cnNextAvailable < m_cnMaxNode )
{
*ppTriangle = m_pPool + m_cnNextAvailable;
m_cnNextAvailable++;
return TRUE;
}
else
{
MessageBox( NULL, “三角池内存耗尽”, NULL, MB_OK );
return FALSE;
}
}
}
三角池也起到了内存控制的作用，当三角形的数量超过了初始化时指定的数量时，将分配失败，从而防止不合理的S和L值造成三角形二叉树的深度过大，三角形的数量过多，耗尽系统资源。
因为每一桢都要根据视点的位置重新建立每个Patch的左右三角形二叉树，所以从三角池中分配出去的三角形不会再返回到三角池中去，只需要在每桢开始的时候把三角池Reset成初始状态。
void CTrianglePool::Reset()
{
for( int i=0; i<m_cnNextAvailable; i++)
{
m_pPool.Reset();
}
m_cnNextAvailable = 0;
}
三角池在全局范围内为三角形的分割提供内存，我希望此计中的代码以后可以被扩展成一个可重用的3D地形引擎，对于将使用这个引擎的客户程序员，如果它不了解三角池的内部机制，就有可能生成多个CTrianglePool的实例，而这显然是不合理的。为了确保CTrianglePool在全局最多存在一个实例，我对它使用Singleton设计模式进行了封装。
class CTrianglePool
{
public:
static CTrianglePool* Instance();
private:
static CTrianglePool* ms_pInstance;
CTrianglePool(void);
CTrianglePool( const CTrianglePool& );
CTrianglePool& operator= ( const CTrianglePool& );
// …
};
CTrianglePool* CTrianglePool::Instance()
{
if( ms_pInstance == NULL )
{
ms_pInstance = new CTrianglePool;
}
return ms_pInstance;
}
7．对缝隙的处理
如图五所示当一个三角形被分割的时候，在新生成的顶点位置会出现一个缝隙。同样，当三角形被合并时，也会出现类似的缝隙，要修正这种缝隙，必须保证当一个三角形被分割或合并的时候，与它共享斜边的三角形也要被分割或合并。
图3 分割造成的缝隙
Figure3 Splitting can result in gaps
要做到这一点，一个三角形除了要与它的两个子三角形保持联系外，还要与跟它相邻的三个三角形保持联系。现做以下定义：
左相邻三角形：共享左直角边的三角形。
右相邻三角形：共享右直角边的三角形。
基相邻三角形：共享斜边的三角形。
在TriangleTreeNode结构中加入对应的成员：
typedef struct TriangleTreeNode
{
TriangleTreeNode *pDNeighbor; //基相邻三角形
TriangleTreeNode *pLNeighbor; //左相邻三角形
TriangleTreeNode *pRNeighbor; //右相邻三角形
// …
} TriangleTreeNode, *LPTriangleTreeNode;;
图四 菱形不存在的情况
Figure4 When a diamond can`t be found
当一个三角形被分割的时候，会出现两种可能的情况：一、被分割三角形和它的基相邻三角形构成一个菱形，既基三角形的基三角形就是被分割三角形，这种情况可以直接分割基相邻三角形。二、不存在这样的菱形，既被分割三角形是它基三角形的左相邻三角形或右相邻三角形。基相邻三角形要被递归的分割，直到菱形的出现（图六）。
当基相邻三角形被分割的时候又会造成它的基相邻三角形的分割，所以三角形的分割是一个递归的过程。在分割的时候，三角形之间的关联信息必须得到合理的更新。
void TriangleTreeNode::Split()
{
// 已分割则退出
if( this->pLChild != NULL )
{
return;
}
//如果小方格不存在，分割基相邻三角形以形成小方格
if( this->pDNeighbor!=NULL )
{
if( this->pDNeighbor->pDNeighbor!= this )
{
this->pDNeighbor->Split();
}
}
// 生成左右子三角形
g_pTrianglePool->AllocTriangle( &this->pLChild );
g_pTrianglePool->AllocTriangle( &this->pRChild );
// 为子三角形建立联系
this->pLChild->pDNeighbor = this->pLNeighbor;
this->pLChild->pLNeighbor = this->pRChild;
this->pRChild->pDNeighbor = this->pRNeighbor;
this->pRChild->pRNeighbor = this->pLChild;
//更新左相邻三角形的联系
if( this->pLNeighbor != NULL )
{
if( this->pLNeighbor->pLNeighbor == this )
{
this->pLNeighbor->pLNeighbor = this->pLChild;
}
if( this->pLNeighbor->pRNeighbor == this )
{
this->pLNeighbor->pRNeighbor = this->pLChild;
}
if( this->pLNeighbor->pDNeighbor == this )
{
this->pLNeighbor->pDNeighbor = this->pLChild;
}
}
//更新左相邻三角形的联系
//与更新左相邻三角形的联系相似，省略
//分割基相邻三角形
if( this->pDNeighbor != NULL )
{
this->pDNeighbor->Split();
//建立子三角形和基相邻三角形的子三角形之间的联系
this->pLChild->pRNeighbor = this->pDNeighbor->pRChild;
this->pRChild->pLNeighbor = this->pDNeighbor->pLChild;
}
}
采用这种方式进行分割，可以保证当要合并一个三角形的时候，此三角形一定有一个和它构成菱形的基相邻三角形，它们彼此都有且只有一层子三角形。在合并完一个三角形之后，要对它的基相邻三角形进行分割。
8.平滑处理
现在通过使用层次细节的方法对三角形进行分割或者合并，可以动态的根据观察者的位置调整地形显示的细节程度。但是，分割或合并三角形会造成地形上某一点的高度值产生瞬间的变化，变化量取决于地形本身的特点，在地形中高度差异比较大的区域，变化量就会比较大。在一桢中如果有很多的点高度值产生较大的瞬间变化，就会出现地形的跳跃（Poping）现象。需要对两桢之间顶点高度的改变进行控制，实现高度的平滑过度。下面是在示例代码中使用的平滑处理方法。
在加载高度图时，对它进行拷贝，得到一张工作高度图。原始高度图存储地形的准确高度，而工作高度图存储平滑处理所需要的及时数据。
memcpy( m_workingMap, m_pbtMap, size );
第一桢不需要平滑处理，从第二桢开始，当一个三角形需要被分割的时候，先将它斜边两端点高度的平均值写入工作高度图的中斜边中点对应的位置。
if( !bFirstFrame )
this->m_pMap->SetWorkH( cx, cy, nowH );
tri->Split();
在输出三角形的时候，计算原始高度图和工作高度图中高度值的差值，如果差值不为0，说明这个位置的点是分割三角形得到的。使工作高度图中的高度值向原始高度图中的高度值变化，为了得到高度平滑过度的效果，变化量应该小于一个预先定义的值。
合并的平滑处理稍微复杂一些。在确定一个三角形要被合并的时候，先不执行合并操作，而是对这个三角形设置一个合并标记。在后边的循环中，如果发现一个三角形是带有合并标记的，先计算合并产生的高度改变，如果高度改变不够大，就直接对三角形执行合并操作，否则先暂时不执行合并，将调整后的高度值写入工作高度图，具体过程如下：
if( tri->bMerging )
{
BYTE dist = 0;
BYTE lastH = m_pMap->GetH( cx, cy );
BOOL doMerge = TRUE;
if( nowH > lastH )
{
dist = nowH - lastH;
if( dist > HEIGHT_DELTA )
{
dist = HEIGHT_DELTA;
lastH += dist;
doMerge = FALSE;
}
}
if( nowH < lastH )
{
dist = lastH - nowH;
if( dist > HEIGHT_DELTA )
{
dist = HEIGHT_DELTA;
lastH -= dist;
doMerge = FALSE;
}
}
If( doMerge )
{
tri->Merge();
tri->bMerging = FALSE;
if( tri->pDNeighbor != NULL )
{
tri->pDNeighbor->Merge();
tri->pDNeighbor->bMerging = FALSE;
}
}
else
{
this->m_pMap->SetWorkH( cx, cy, lastH );
}
}
在输出三角形的时候也要做出调整。所输出的都是叶子结点的三角形，它的斜边两个端点不会受到分割标记的影响，但是在数据直角顶点时，要判断它的父三角形时候被设置了分割标记，如果是，就直接从工作高度图中读取高度值，而不需要使其向原始高度图中的高度值变化。
四．可见性测试
1．可见性测试的目的
设想我们开发的是一款飞行模拟游戏，玩家控制者最新式的战斗机做特技飞行，当他俯冲的时候可以看到我们使用实时地形引擎构造的连绵起伏的高山；当他拉起控制杆冲向蓝天的时候，就不应该对玩家看不到的地形部分进行复杂的LOD三角形分割和ROAM的构造。
判断几何体是否可见的过程就是可见性测试。D3D的渲染管线本身具有可见性测试的功能，但是这份免费的午餐并不好吃。首先，我们要求可见性测试在将几何体送入渲染管线之前就要进行，因为不可见的部分不能进行分割。其次，D3D的渲染管线会对三角形进行逐个的可见性测试，而我们的三角形已经被组织成了三角形二叉树，当父三角形不可见的时候，它的所有子孙三角形的可见性测试都可以被跳过。所以，有必要进行自定义的可见性测试。
2. 视域的构造
我们完全根据照相机的成象原理来构造视域(Viewing Frustrum). 视域是空间中与视点位置相关的一块3D区域。视域是一梯形台，由远近、左右、上下六个剪裁平面构成。
图五 视域
Figure5 Viewing Frustum
class CFrustum
{
// clipping planes
D3DXPLANE m_planeNear;
D3DXPLANE m_planeFar;
D3DXPLANE m_planeLeft;
D3DXPLANE m_planeRight;
D3DXPLANE m_planeUp;
D3DXPLANE m_planeDown;
// …
};
视域的位置和方向取决于照相机的位置和方向。可以使用三个向量来描述：1、镜头所在点vFrom。2、镜头直线观察到的一点vAt.。3、镜头向上的方向vUp，一般为(0, 1, 0)。从这三个向量可以生成一个视点矩阵。
D3DXMATRIX matView;
D3DXMatrixLookAtLH((D3DXMATRIX*) &matView, (D3DXVECTOR3*)&vFrom,
(D3DXVECTOR3*)&vAt,(D3DXVECTOR3*) &vUp );
视域的形状取决于镜头的属性：1、镜头的横纵比(Aspec)。2、镜头视野的纵向夹角(fovy)。3、镜头能看到的最近距离zn。4、镜头能看到的最远距离zf。由这四个值可以生成一个投影矩阵。
D3DXMATRIX matProj;
D3DXMatrixPerspectiveForLH( &matProj, fovy, zn, zf );
Gill Gribb和Klaus Hartmann找到了从视点矩阵和投影矩阵得到视野域的六个剪裁平面的方法。以下的SetViewTransform函数有一个很好的特性：如果传入的参数是投影矩阵，得到的View Frustum六个平面的坐标都是在相机坐标系(Camera Coordinate System)中定义的，如果传入的参数是视点矩阵和投影矩阵的乘积，得到的剪裁平面就具有在世界坐标系(World Coordinate System)的坐标。Patch和三角形都是在世界坐标系定义的，所以后者是本系统的合理运算。
void CFrustum::SetViewTransform( D3DXMATRIX matView )
{
m_planeNear.a = matView._13;
m_planeNear.b = matView._23;
m_planeNear.c = matView._33;
m_planeNear.d = matView._43;
m_planeFar.a = matView._14 - matView._13;
m_planeFar.b = matView._24 - matView._23;
m_planeFar.c = matView._34 - matView._33;
m_planeFar.d = matView._44 - matView._43;
m_planeLeft.a = matView._14 + matView._11;
m_planeLeft.b = matView._24 + matView._21;
m_planeLeft.c = matView._34 + matView._31;
m_planeLeft.d = matView._44 + matView._41;
m_planeRight.a = matView._14 - matView._11;
m_planeRight.b = matView._24 - matView._21;
m_planeRight.c = matView._34 - matView._31;
m_planeRight.d = matView._44 - matView._41;
m_planeUp.a = matView._14 - matView._12;
m_planeUp.b = matView._24 - matView._22;
m_planeUp.c = matView._34 - matView._32;
m_planeUp.d = matView._44 - matView._42;
m_planeDown.a = matView._14 + matView._12;
m_planeDown.b = matView._24 + matView._22;
m_planeDown.c = matView._34 + matView._32;
m_planeDown.d = matView._44 + matView._42;
}
3．圆柱体剔除（Cylinder Culling）
在视域构造好以后,要进行地形的可见性测试，就要使用某种几何体将地形包围，判断几何体与视域的位置关系，几何体是完全在视域之外，完全在视域之内，还是与视域相交。从而近似地得到被包围的地形与视域的位置关系。
这里使用圆柱体作为包围地形的几何体。构成我们地形的元素——Patch，以及构成Patch的三角形，它们在水平面上的投影分别是矩形和直角三角形。分别以矩形和直角三角形的外接圆作为圆柱体的底面圆，以Patch和三角形的高度作为圆柱体的高，来构造Patch和三角形的包围圆柱体。
等腰直角三角形外接圆的圆心是它斜边的中点，这个外接圆还包含了它的基相邻三角形，外接圆的半径与直角边长度的比值是sqrt(2) / 2。半径有是子三角形的直角边长度。我们预先计算从Patch的根结点三角形到最大深度三角形的外接圆半径，并将计算结果保存到一个数组中。
this->m_fLenthHypo[0] = PATCH_SIDE;
for( int i=1; i<32; i++ )
{
m_fLenthHypo = m_fLenthHypo[i-1] * 0.7071067f; // root(2) / 2
}
使用圆柱体剔除的原因在于圆柱体与视域的位置关系判断最终可以简化为两个点与视域的位置关系判断。把圆的半径线段投影到平面的法线方向上，得到的线段称为圆到平面的有效半径：
有效半径 = 半径 * Factor
Factor = cos A
A = 平面法线和圆面法线的夹角
Patch和三角形的圆柱体的轴线都是与y坐标轴平行的。包围视域的每个平面的解析表达式为：
ax + by + cz + d = 0;
其中b为平面法线和y坐标轴夹角的sin值，所以：
Facotr = sqrt(1 ? b*b)
在每次进行可见性测试之前，先计算视域每个平面的Factor，它对于所有的地形元素都是一样的。在判断一个地形元素的可见性时，计算它的包围圆柱体到平面的距离d1，d2，和有效半径R，判断过程如下：
如果. d1 < R 或 d2 < R 与视域相交
否则 d1 与 d2 符号相反 与视域相交
否则 d1 > 0 且 d2 > 0 在视域内
否则 d21 < 0 且 d2 < 2 在视域外
4．大尺度的可见性测试——四叉树
首先进行大尺度的可见性测试，使用四叉树对所有的PATCH进行组织。整个地形包含所有的PATCH（在示例中使用8*8个PATCH），它是四叉树的根结点；把整个地形在X和Z方向上用直线等分，形成四个全等的矩形，每个矩形表示地形中的一个区域，是根结点的一个子结点；再对每个矩形用相同的方式分割，直到分割出的矩形是一PATCH为止。每个结点存储一个高度值，如果是叶子结点，这个高度值是左右两个三角二叉树的最大值；如果是非叶子结点，这个高度值是四个子结点高度的最大值。高度是与视点无关的，所以四叉树接点的值可以预先计算。又因为使用的是完全四叉树，所有结点的值可以用一维数组储存在一起。
图六 四叉树的建立过程
Figure6 Quadtree`s building process
这样，在进行可见性测试的时候，先使用四叉数在大尺度上将不可见的PATCH剔除出去。对于完全或者部分可见的PATCH，对用LOD方法对其建立左右三角形二叉树，在建立过程中，一但发现三角形不可见，分割过程就立即停止。
5．可见性信息的保存
在一桢当中，视点的位置是相同的，这就意味着在建立三角形二叉树时进行可见性测试得到的信息（包括大尺度的四叉树每个结点的可见性和小尺度的三角形可见性），在判断应当将地形的哪些部分送入渲染管线时依然有效，所以必须对这些信息进行保存，以消除冗余的可见性测试。四叉树的可见性信息可以用数组来保存，三角形的可见性信息就存储在三角形结点当中。
五．输出三角形
1.索引缓冲区的使用
ROAM顶点格式如下：
typedef struct VER_POS_TEX
{
float x, y, z;
float tu, tv;
} VER_POS_TEX, *LPVER_POS_TEX;
在ROAM中，很多顶点是被几个三角形共用的，一个顶点要占用20个字节。而一个索引只需要两个字节，所以索引的使用能够极大的减少显卡内存的消耗。
所有的PATCH共用一个顶点缓冲区，因为每个PATCH要使用到不同的纹理，所以每个PATCH都有一个索引缓冲区。
图七 三角形的输出过程
Figure7 Output Triangles
2．三角形的输出过程
在输出一个三角形的过程中，它的顶点可能已经在输出相邻三角形时输出了。在输出之前，所有顶点的索引值都设置为0xffff，当一个顶点输出到顶点缓冲区以后，它的索引值被修改为其在顶点缓冲区中的索引，图七说明了的顶点的递归输出过程：
状态1：输出Patch的左基三角形CBA（以斜边左顶点，斜边右顶点，直角顶点为序，下同）。
状态2：输出CBA的左子三角形ACD。
状态3：输出ACD的左子三角形DAE。
状态4：输出DAE的左子三角形EDG，EDG为叶子结点，顶点的当前索引值分别为：E=0xFFFF, D=0xFFFF, G=0xFFFF，将EDG的顶点数据放入顶点缓冲区，得到它们在顶点缓冲区中的索引值分别为E=1，D=2，G=3，将索引值输出到索引缓冲区。
状态5：输出DAE的右子三角形AEG，AEG为叶子结点，顶点的当前索引值分别为：
A=0xFFFF，E=1, G=3。将A的顶点数据放入顶点缓冲区，得到A的索引为4，输出索引4，1，3到索引缓冲区。
状态6：输出ACD的右子三角形CDE
状态7：输出CDE的左子三角形ECH，ECH为叶子结点。顶点的当前索引值分别为：E=1，C=0xFFFF，H=0xFFFF。将C、H放入顶点缓冲区，得到C的索引为5，H的索引为6，输出索引1，5，6到索引缓冲区。
状态8：输出CDE的左子三角形DEH，DEH为叶子结点。顶点的当前索引值分别为：D=2，E=1，H=6。输出索引2，1，6到索引缓冲区。
状态9：输出CBA的右子三角形BAD
现在顶点缓冲区中有6个顶点，在索引缓冲区中有12个索引值，分别为：1，2，3，4，1，3，1，5，6，2，1，6
3．菱形边界问题
上述以递归方式输出三角形二叉树的过程可用代码表示为：
if( tri->pLChild != NULL )
{
WORD indexC; // 斜边中点索引
RecurseBuildBuff( tri->pLChild, ax, ay, indexA,
lx, ly, indexL,
cx, cy, &indexC
);
RecurseBuildBuff( tri->pRChild, rx, ry, indexR,
ax, ay, indexA,
cx, cy, &indexC );
);
如果这样输出三角形二叉树，在顶点缓冲区中仍然会有重复的顶点。考虑如EDG和DEH构成的菱形，如果EDG和DEH分别被进一步分割，当递归结束，函数返回，作为临时变量的indexC从函数调用堆栈弹出。当输出基相邻三角形时，它会为已经在顶点缓冲区中存在的斜边中点再输出一个顶点。为了修正这个问题，我们给三角形二叉树的结点再添加一个成员变量，表示斜边中点的索引，当输出左右子三角形后，如果和基相邻三角形构成菱形，则更新基相邻三角形的索引。修正后的整个递归过程为：
if( tri->pLChild != NULL )
{
RecurseBuildBuff( tri->pLChild, ax, ay, indexA,
lx, ly, indexL,
cx, cy, &tri->index );
RecurseBuildBuff( tri->pRChild, rx, ry, indexR,
ax, ay, indexA,
cx, cy, &tri->index);
if( tri->pDNeighbor!= NULL
&& tri->pDNeighbor->pDNeighbor == tri )
{
tri->pDNeighbor->index = tri->index;
}
}
4．Patch边界问题
图八：纹理的镜向处理
Figure8: Mirroring Textures
现在考虑在Patch之间共享顶点的情况。在Patch的边界上共享顶点的情况有两种：一是Patch的顶点会被共享；二是一个三角形的基相邻三角形和它构成菱形且在另外的Patch中。顶点的坐标在Patch之间共享没有任何问题，但顶点的纹理坐标在Patch之间不能被简单的共享。一种解决方案是把顶点索引限制在Patch边界之内，但这不够理想。我们使用这样的解决方案：分别在U，V方向每隔一个Patch，对纹理坐标进行镜象处理，如图八所示。在将顶点放入顶点缓冲区的时候，根据所在的Patch判断是否对纹理坐标进行调整。
if( m_bMirrorX )
g_pTerrain->m_pVerData[g_pTerrain->m_iVerNum].tu = 1.0f - tu;
else
g_pTerrain->m_pVerData[g_pTerrain->m_iVerNum].tu = tu;
if( m_bMirrorY )
g_pTerrain->m_pVerData[g_pTerrain->m_iVerNum].tv = 1.0f - tv;
else
g_pTerrain->m_pVerData[g_pTerrain->m_iVerNum].tv = tv;
问题还没有完全解决。为了抗锯齿，我们通常使用双线性过滤的方式对纹理进行采样。所下图是一张4*4的纹理。
图九：纹理的双线形过滤
Figure9：Bilinear Texture Filtering
如对UV：(0.5, 0.5)位置进行采样，需要根据此点到周围四个图素(Texel)的距离计算它们的加权平均数，得到灰色。
0.25 * (255, 0, 0)
0.25 * (0, 255, 0)
0.25 * (0, 0, 255)
+ 0.25 * (255, 255, 255)
------------------------
= (128, 128, 128)
当给定的纹理坐标的一边没有图素时，比如给定图九的纹理，当U坐标<0.125时，左边没有图素。在这种情况下DirectX会在概念上向纹理的最左边添加一列图素，在默认情况下，DirectX使用Wrap的方式添加，既把最右边的一列图素作为添加列。这显然不是我们想要的，把两个边缘的图素相混合会造成Patch出现明显的边界。我们要使用的是镜向的添加方式，既把最左边的一列作为添加列，这需要设置如下的渲染状态：
pd3dDevice->SetSamplerState( 0, D3DSAMP_MINFILTER, D3DTEXF_LINEAR );
pd3dDevice->SetSamplerState( 0, D3DSAMP_MAGFILTER, D3DTEXF_LINEAR );
pd3dDevice->SetSamplerState( 0, D3DSAMP_ADDRESSU, D3DTADDRESS_MIRROR);
pd3dDevice->SetSamplerState( 0, D3DSAMP_ADDRESSV, D3DTADDRESS_MIRROR);
5．背面剔除
DirectX的渲染管线会将背向观察者的三角形剔除掉。在默认状态下，如果三角形的三个顶点在顶点缓冲区中以逆时针的顺序出现就会被认为是背向观察者的。在程序中为了计算方便，使用斜边左顶点，斜边右顶点，直角顶点的顺序输出三角形的顶点，所以要剔除的应该是顶点顺时针出现的三角形。
6．进入渲染管线
现在，地形被分割成了ROAM，ROAM的顶点写入了顶点缓冲区，顶点的索引写入了Patch的索引缓冲区。大功即将告成，只要分别渲染每个Patch，我们所要做的就是等待地形出现在屏幕上了：
for( int i=0; i <m_iTotalNum; i++ )
{
pTexture = m_pPatches.m_pTexture;
if( pTexture->wNumTriangle == 0 ) continue;
m_pd3dDevice->SetTexture( 0, pTexture->pTexture );
m_pd3dDevice->SetIndices( pTexture->pIB );
m_pd3dDevice->DrawIndexedPrimitive( D3DPT_TRIANGLELIST, 0, 0, m_iVerNum, 0, pTexture->wNumTriangle );
}
六．整体流程
为了方便大家更好的理解上述理论，这里对地形从建立到渲染的整个过程作一下总结。如图十所示。本文只是说明了地形渲染的主体部分，其他的一些辅助功能，像相机的控制，FPS值的统计，用户输入的接受等没有给出实现过程，在流程图中也不展现它们。
七．关于HLSL
在DirectX中 使用固定功能的渲染管线，调用DrawPrimitive函数后，顶点信息进入系统提供的渲染管线。要对固定功能渲染管线的行为进行干预，只能调用设置渲染状态的函数，比如SetRenderState，SetTextureStageState等。固定功能的渲染管线只提供了常规的功能，若要求渲染管线提供特殊的功能，就必须使用可编程的渲染管线。
并不是渲染管线的每个步骤都是可编程的，简单的说，渲染管线可以被分解以下步骤：
1．顶点处理：包括顶点变换，逐顶点的雾化计算和逐顶点的光照。
2．图元处理：包括剪裁，背面剔除，为了进行光栅化，要进行每图元的属性求值。
3．像素处理，这个步骤可以被分解为以下两个子步骤：
子步骤1：对纹理采样，将采样结果与光照计算的结果相融和。
子步骤2：包括所有决定如何写如桢缓冲区的操作，包括Alpha测试，深度测试，蒙版测试，进行每像素的雾化效果计算，进行gama矫正。
顶点处理的过程和像素处理的第一个子步骤是可编程的，用户可以使用自定义的顶点着色器（vertex shader）和像素（pixel shader）着色器来扩展渲染管线的功能。但是在Direct9以前
图十 整体流程
Figure10 Overall Flow Chart
编写shader只能使用汇编语言，不同的显卡在寄存器的分配、提供的指令等诸多方面都集存在差异，这使得用汇编语言编写的Shader移植性很差。
DirectX9的新特性中最为吸引人的一点就是高级着色器语言(High Level Shader Language), 使用HLSL，Shader的编写者可以把注意力集中到Shader本身的逻辑上，而不用考虑复杂的硬件细节。另外，作为一种高级语言，HLSL使得Shader代码的可读性和可重用性都大大提高。
在示例代码中，所有的渲染都是通过HLSL编写的Shader来完成的。
八．阴影构造
1．阴影体网格的生成
生成一个静态的阴影体网格，用顶点着色器拉伸它的顶点。这样做的好处在于只需要很少的CPU时钟周期来渲染阴影。阴影体网格一旦生成，无论光源的位置怎样变化，它都不需要改变了，顶点着色器会把从渲染管线得到的阴影体网格的顶点向合适的方向拉伸。生成阴影体网格的工作是由GenerateShadowMesh函数完成的，它接受一个输入网格，输出一个表示其阴影体的网格。
对于输入网格的每一条边，函数会把它分割成两条边，共享这条边的两个三角形也就被分割了。然后，一个矩形被创建出来（由两个三角形构成），它连接了被分割的三角形。此时，矩形是退化的，它没有面积。这个过程由下图所示：
图十一 分割面，插入矩形
Figure11 Mesh faces are split, quads are inserted
生成阴影体的算法迭带输入三角形中的每个面，进行以下工作：
首先，生成三个新的顶点和一个新的面，每个面都要有三个独立的顶点，因为因为面已经被退化的矩形分割了。
然后，顶点的法线被设置为面的法线。这样做的原因是顶点着色器要进行顶点的拉伸，而顶点着色器只能看到顶点的法线而看不到面的法线。
最后，面的三条边被添加到边影射表。边影射表中的每一项包含三条边，一条是输入网格中的边（源边），另外两条是它被分割的两条边（目标边）。对面的每一条边，如果在边映射表中不存在以它为源边的项，算法就创建一个新项到边影射表中，并设置源边和第一条目标边；否则如找到，就把它作为第二目标边添加到找到的项中，边两条目标边构成的矩形输出到结果网格，并从边影射表中删除此项。
2．渲染阴影体
从总体上说，渲染过程由以下步骤组成：
A．用暗淡的环境光渲染整个场景
B．禁用对深度缓冲区和桢缓冲区的写入
用顶点拉伸着色器渲染阴影体网格，根据像素是否在阴影体内设置蒙版缓冲区
C．启用对深度缓冲区和桢缓冲区的写入
D．根据蒙版缓冲区中的值，用明亮的环境光渲染真个场景
E．把A和D的渲染结果做Alpha融合
在顶点着色器中，先判断顶点的法线。如果法线指向光源，不对它做处理；否则，如果法线指向远离光源的方向，顶点就被沿着法线方向拉伸到无限远处。在阴影体网格中，因为面是被插入的矩形连接着的，如果被连接的两个面中只有一个被拉伸，连接它们的矩形就不再是退化的了，它被拉伸成为阴影体的侧部。如图十二所示。
图十二 拉伸顶点
Figure12 Vertex Extruding
在像素着色器中，使用深度失败（Depth Fail）技术渲染阴影体网格，首先渲染背面的三角形，如果一个像素的深度测试失败（像素的的深度值大于深度缓冲区中的值），这个像素的蒙版值被增加。然后渲染正面三角形，如果像素的深度测试失败，像素的蒙版值被减小。当整个阴影体网格被渲染后，被阴影体覆盖的像素区域具有非零的蒙版值，其他像素区域具有零蒙版值，如图十三所示。明亮环境光的渲染步骤只对零蒙版值的像素进行。
图十三 用深度失败渲染阴影体
Figure13 Render shadow volumn with depth fail
九．关于示例代码
代码使用Microsoft Visual C++.net 2003编写，使用的DirectX SDK是2007年4月的9.0版本。
在进程中，使用方向键控制机器人的移动，使用WSAD键和鼠标控制视点位置和方向。快捷键为：ESC推出，F8切换线框和实体模式，F3重新加载参数。
参考文献:
[1] Turner Bryan, Real-Time Dynamic Level of Detail Terrain Rendering with ROAM[J]: Gamasutra, March, 2004
[2] Microsoft Corporation, The DirectX 9 SDK Documentation[K]：2006.2
[3] DeLoura, Mark; Lengyel, Eric; Game Programming Gems A Fast Cylinder-Frustum Intersection Test[J]:
August 2000
[4] Jeromy Walsh, Normal Computations for Heightfield Lighting[J], Gamedev.net August 4, 2005
[5] David Clyde, Adding Realistic Rivers to Random Terrain[J], Gamedev.net March 15, 2004
[6] Greg Snook, Real-Time 3D Terrain Engines Using C++ And Directx[M], Charles River Media; 1 edition June 2003
[7] Trend Polack, Focus on 3D Terrain Programming[M]: Course Technology PTR ,December 11, 2002
[8] Scott Meyers, Effective STL[M]: 50 Specific Ways to Improve Your Use of the Standard Template Library, Addison-Wesley Professional; 1st edition, June 6, 2001
致谢:
感谢父母对我一贯的支持。
感谢程静老师，是她让我对程序设计产生了浓厚的兴趣。
感谢指导老师程小平，他给了我不少有用的建议。
感谢Scott Meyers和Stanley Lippman两位大师，他们的著作消除了我很多疑惑。
|
|
发表于 2007-6-7 13:57:00
楼主