地形制作全攻略（转载）

由于今年10月我就要找工作了，7月20号开始我准备学SHADER了，我给出的执行文件可以说是地形DEMO 1.0版本，等我找完工作，我可能再添加粒子引擎。我只是给大家一个DEMO，先不放出源代码，希望大家见谅，等到我找完工作后，我一定把源程序毫不保留的放出来，在这之前不要说我吝啬，一个好的工作是给我的最大肯定。

这个文章几乎涉及到一个室外游戏中用到所有技术，程序实现是用D3D 9.0制作，没有用任何SHADER，因为我的机器很烂，是2003年12月24日买的联想笔记本，9999元，CPU迅池一代1.4（相当于 P4 2.0），显卡集成的，没有任何SHADER功能，显存还是很内存共用的。引擎制作花了我半年时间，地形制作花了我2个多月，这是个漫长的过程，引擎我改了又改，到最后我还是认为有个地方不满意，但我实在不想改了，有些烦了，没有技术含量，只是体力活。

写完这个文章后，我只检查了一遍，难免有些错误。但技术上，我认为绝对没有错误，因为我把它实现了，我有证据，说明这么做就是对的。

如果有不明白的或者有书写错误的，或者想和我讨论问题。请大家和我联系。

QQ：79134054（请注明：编程好友。否则我不加的）

最后感谢我的导师他教会了我怎么学习，授人于鱼，不如授人于渔。

吉林大学2006级研究生

图形与图象处理专业

程东哲（阿哲VS自己）

2008年7月13日

一想到我要花很上时间我把实现过的详细写出来，我就有些厌倦，把这些字打来打去的，是很大的工作量，但又一想到中国的游戏行业，中国制作游戏的热血青年，我还是坚持把这些写了出来，让他们少走些弯路。我现在才明白一个好的程序员为什么不愿意写文档，写注释了，他们实在没有时间重复这些没有意思的事，因为如果要是有一天真的都忘了，就算有文档，也要花好长时间才能看懂自己写的代码，但实现过程我想自己永远也不会忘记的。

我之所以写这篇文章，一个原因，以后我有一天写关于游戏引擎方面的书，我有些参考，毕竟当年做过这个，并写了出来。再一个原因，我的实现和现在世面上可以见到的代码不一样，要么他们写的说明不是很详细，要么就根本只有程序，连一点点注释都没有。

编程确实是体力和脑力，耐力的挑战，有时一个简单的理论，你要花好长时间才可以实现。确实理论和现实还是有差距的。我这个地形是用Dricte3D做的四叉树LOD，加了很多别的室外场景。本来还想实现一个BSP和OCTREE，分别用它们做渲染和碰撞，如果可能的话，是找完工作后是事情，但现在没时间了。今年8月份就要学SHADER了，为找一个好工作做最后的努力。

说实话，我现在只能做DEMO，因为我是一个人在战斗，没有志同道合的人和我并肩做战。真正的游戏是希望有一个场景编辑器来帮助编辑的，这个工作量不是一个人可以完成的，为了减少，要么硬编码，要么使用简单的脚本。我想做为一个还没有走出学生时代的在校学生，我做到这样已经很不容易了，我现在太需要外界的刺激，因为学校太封闭了，根本不能完成自己的使命，在学校只是一种理论积累，我想我的基础应该达到我想要的程度。

上面发了一堆牢骚，闲话少说了，开始写怎么编写地形。我这里的很多知识都是来自《FOCUS ON 3D TERRIAN》这本书，但我不得不说，这本书有些关键地方解释太不详细，作者让你去读他参考的论文，而且是用OPGL实现的，OPGL的渲染管理和D3D是不同的，所以渲染地形过程还是有很大差别，而且还改写很多技术细节，后面的光晕，阴影体，地形物体，碰撞，无限地形，都是我自己写的。

我今天准备详细介绍每一个细节，争取让所以看了这篇文章的人都能看明白，基于四叉树LOD地形渲染究竟是怎么回事。

下载演示程序

我要介绍的内容是：

零．地形简介

一．2个地形生成算法

二．地形上的纹理

三．四叉树LOD渲染地形

四．相机剪裁地形

五．天空盒

六．简单海水

七．广告牌

八．光晕

九．地形场景物体与BVH

十．阴影体

十一．碰撞

十二．无限地形

一个完整地形渲染也就需要这么多东西，看起来很多，但确实很多，也不是很容易。

零．地形简介

这一部分是我后加进来的，我想把读者当成对地形一点没有了解的人。Andre LaMothe是我最佩服的游戏编程大师，他作为大师一点也不假，他的书写的诙谐幽默，把读者完全当做傻子一样，写的很详细。中国翻译人员也没有辜负他，他的两本书都翻译的很棒！

我想继承大师的风格，把我的文章写的深入浅出，诙谐幽默。

如果你对3D没有什么概念的话，建议还是别看这里。等你对3D编程有了解，你在看这个。

现在就开始了。计算机模拟地形，还是没有逃离基于顶点的三角形，当然现在基本所有的3D都是基于顶点三角形的。

图1

看上图（俯视），所有绿色的都顶点，假设些顶点都在一个平面上，当然这里只有顶点，还没有连三角形（红色的线，只是为了大家看方便），连接三角形有很多方法，下面就是一种方法。

图2

连接三角形有多方法。当然真正的地形就是把顶点高度都相对降低和提升，我给的例子是一个平地。一但降低和提升后，就能出来地形，当然你别瞎提升和降低，弄得个地形很诡异，我们要得是很符合实际的地形，你做一个星球大战之类太空游戏，地形诡异点也没问题，因为这个地形不是地球上的。

下面我就介绍2个地形生成算法，来创造符合实际的地形，也就是看起来比较真实的地形顶点数据。

一．地形生成算法

其实地形生成算法有很多，在《FOCUS ON 3D TERRIAN》介绍2种，我这里也主要介绍这2种，当然我还见过用噪声方法来生成云纹理图来作为地形的高程图。好，现在是介绍高程图的时候了，高程图就是一张图片，它的每一个象素值来表示相对顶点高度（这里说“相对”的意思是，一般高程图只用256色 8位图来表示，即使用24位表示，RGB值也都一样的。所以高度只能是0——255，真实地形顶点高度能是0——255吗？不可能，所以说相对。当你想调节到真实数据时，可以用一个高度缩放因子来乘以这个相对高度，达到你想要的真实高度范围）

图3

如图，右面的就是高程图，它和顶点对应关系。一但顶点有了高度数据（一般默认高度方向为Y轴）再乘以高度缩放因子，水平和竖直方向用X和Z轴来表示，每个在高程图里相临顶点都是按数组排列的，都差一个单位，再用一个宽度因子相乘，这个顶点的实际数据就生成了。

例如高程数组 HeightMap[2][3] 变成顶点为 (2 * WidthRatio, HeightMap[2][3] * HeightRatio , 3 * WidthRatio,)，也就是说X，Z坐标用的数组下标乘以宽度比例。

下面我就详细说下地形高程图生成算法

1．Fault Formation

图4

如图如果你的地形是m*n 的宽度（其实多大尺寸都一样），在上面随机取一直线条线，给直线一端的所有点一个高度h，当然可以取任意条直线，每次高度叠加，然后在用平滑滤波算法把整个高程图进行平滑处理，重复这个过程，这样一个地形高程图就生成了。

上面介绍是算法的基本过程。

第一个难点就是怎么随机取一个条直线，然后判断那些点在直线一端，那些点在直线另一端。

其实在实现上并不是真正取一条直线，而是取一个向量，在数学上，向量是一个有方向的量，我不是搞物理或者数学的所以很难给出一个严格定义，但向量确实是数学和物理的基础东西，如果你不是很明白，希望自己查阅下，高等数学和高中物理，基本上过大学高数课程的，这个都应该明白。

图5

这里只介绍2D向量，因为只用到2D向量，3D向量其实和它是一个道理。

我们的主要目的是判断，那些点在直线L一端，那些点在直线L另一端，

我们先随机取2点A，B，但A，B不能重合，然后做AB向量，就是2点A，B做减法，取过A点和AB垂直的直线为L，这样就确定L ，然后判断点c位于直线L那一端，向量AC和向量AB做点积，也就是AC和AB夹角COS值，如果大于0，表示在直线一侧，如果小于0，表示在直线一侧。

//重复这个迭代过程，也就是直线取多少条，nIterations表示取直线条数

for( nCurrentIteration=0; nCurrentIteration < nIterations; nCurrentIteration++ )

{

//每次增加的高度，nMaxHeight，nMinHeight表示想要的最大最小高度

//高度为什么用这个等式，我也不是很清楚，书上也没说，只留下了关于这个算法的论文。

fHeight = nMaxHeight -

( ( nMaxHeight - nMinHeight ) * nCurrentIteration * 1.0f) / nIterations;

//先随机取一点

nRandX1= rand( ) % m_nSize;

nRandZ1= rand( ) % m_nSize;

//然后随机取另一个点

{

nRandX2= rand( ) % m_nSize;

nRandZ2= rand( ) % m_nSize;

} while ( nRandX2 == nRandX1 && nRandZ2 == nRandZ1 );

//形成向量，这样就确定直线L

nDirX1= nRandX2-nRandX1;

nDirZ1= nRandZ2-nRandZ1;

//遍历所有点，看点都位于直线L哪侧

for( int z=0; z < m_nSize; z++ )

{

for( int x=0; x < m_nSize; x++ )

{

//和A点做向量

nDirX2= x - nRandX1;

nDirZ2= z - nRandZ1;

//大于0，则叠加高度

if( ( nDirX2 * nDirZ1 - nDirX1 * nDirZ2 ) > 0 )

{

pTempBuffer[( z * m_nSize ) + x] += ( float )fHeight;

}

//平滑滤波

FilterHeightField( pTempBuffer, fFilter );

}

上面代码显示了整个算法过程，唯一没有说的就是平滑滤波函数FilterHeightField

fFilter 是表示滤波指标

滤波算法有很多，作者采用的是下面等式处理，

B = fFilter * A + ( 1 - fFilter ) * B;

这里看出fFilte范围[0，1]

作者分别对行进行从做到右和从右到左滤波，对列从上到下和从下到少滤波

//left to right

for( i = 0 ; i < m_nSize ; i++ )

FilterHeightBand( &fpHeightData[m_nSize*i], 1, m_nSize, fFilter );

//right to left

for( i = 0 ; i < m_nSize ; i++ )

FilterHeightBand( &fpHeightData[m_nSize*i+m_nSize-1], -1, m_nSize, fFilter );

//top to bottom

for( i = 0 ; i < m_nSize ; i++ )

FilterHeightBand( &fpHeightData[i], m_nSize, m_nSize, fFilter);

//bottom to top

for( i = 0 ; i < m_nSize ; i++ )

FilterHeightBand(&fpHeightData[m_nSize*(m_nSize-1)+i],-m_nSize,m_nSize, fFilter );

下面详细介绍FilterHeightBand函数，nStride 表示相隔两个点多少个宽度进行滤波，nCount表示一共多少点。

FilterHeightBand( float* fpBand, int nStride, int nCount, float fFilter )

{

float v= fpBand[0];

int j = nStride;

int i;

for( i = 0 ; i < nCount-1 ; i++ )

{

fpBand[j] = fFilter * v + ( 1 - fFilter ) * fpBand[j];

v = fpBand[j];

j += nStride;

}

上面算法可以看出，前一个点为v，后一个点为fpBand[j]，如果fFilter = 1则后一个点等于前一个点，如此迭代最后形成了高度为fpBand[0]的平面，如果fFilter = 0则，和没有滤波一个效果。

}

最后高度按线形比例缩放到0到255之间

ChangeDateRange(pTempBuffer, 0.0f, 255.0f);

Void ChangeDateRange(float* fpHeightData ,float fMinHeight,float fMaxheight)

{

float fMin, fMax;

float fHeight;

float fHeightDelta;

if(!fpHeightData)

return ;

//要缩放的高度差

fHeightDelta = fMaxheight - fMinHeight;

if( fHeightDelta < 0)

return ;

fMin= fpHeightData[0];

fMax= fpHeightData[0];

//查找最大值

for( int i = 1; i < m_nSize * m_nSize ; i++ )

{

if( fpHeightData[i]>fMax )

fMax= fpHeightData[i];

else if( fpHeightData[i]<fMin )

fMin= fpHeightData[i];

}

if( fMax<=fMin )

return;

//找出实际高度差

fHeight = fMax-fMin;

//这就是一个线形方程变换，如果你这个不明白说明你的数学真的是很。。。。

//我就不说别的了，把数学学好吧！

for( i = 0 ; i < m_nSize * m_nSize ; i++ )

fpHeightData[i]= ( ( fpHeightData[i] - fMin ) / fHeight )

* fHeightDelta + fMinHeight;

}

这样一个高程图就生成完毕。

图6

这个就是经过取64次直线，但没有进行滤波的高程256色图象

图7

经过4，8，16，32 次没有滤波的高程256色图象

图8

经过64直线，但滤波因子分别为0.0f ，0.2f ，0.4f

2．Midpoint Displacement

这个算法和上一个算法表现为不同的地形类型，Fault算法生成的是小山，而这个算法则其中在连绵的山。这个算法有个优点，由于算法本身的特性，它可以保证地形边界左右是连续的，上下是连续的，也就是说如果把生成的地形进行拼接，形成无限地形，它是可以实现的。后面我会说到怎么做无限地形。这个算法有个缺点是必须要求地形是2的n 次方，我们后面要做四叉树LOD，必须要用2的n 次方+1 大小的地形，这个我做了一个小小处理，让它既保持优点，又能适合四叉树LOD。现在我开始讲解原始算法。

图9

正如算法名称写的那样，中点取代。这里任何一个点都是用周围4个点取平均再加上一个随机高度求得。例如求G，因为G左面没有顶点，算法要求，超出边界就要取模运算，所以G求得用AECE四个点。第一次迭代为，根据边界A,B,C,D的四个点求中点E，然后再求边界G和F。第一次迭代结束，然后分别对AFEG，FDHE，EHDI，GEIC重复这个过程。（之所以求G和F是为了下一迭代，也就是求AFEG的中点做准备，为什么不求H和I呢？下一步FBHE也要求中点需要H值，之所以不求H和I，是因为H和G是相等的，F和I是相等的。前面我说过，这个算法有个限制是必须是2的n 次方，算法要求，超出边界就要取模运算，原因就在这里。大家仔细看实际上程序中求中点E，B如果超出了Size，它是要取模运算的）如果上图9是第一次迭代，也就是RectSize = Size，B其实是和A相等的，D和A ，C和A也相等，也就保证了为什么这个地形为什么边界是可以连接的，也就是上面和下面，左面和右面是可以不经过任何处理就可以拼接,也就是说坐标点有可能超出Size的，就要用模运算。,G的坐标是（i，j +RectSize / 2），G要用4个点求得，上面点A（i，j），下面点C（i , (j + RectSize）% Size），右面点E（(i+RectSize/2)，(j+RectSize/2)），左面点为（(i-RectSize/2+RealSize)%RealSize，j +RectSize / 2），这里也用到了模，这样才能保证地形可以拼接，如果是第一次迭代，也就是RectSize = Size，你可以算出的，（(i-RectSize/2+Size)% Size，j +RectSize / 2）其实就是E点坐标，而H点坐标和G点其实是相等的。同理知道F应该怎么求吧，F和I为什么相等。所以只需要求左侧中点和上面中点，就可以了。

现在我给出代码更加直观。

int iRectSize = m_nSize - 1 ;//之所以减1，是因为我们程序里m_nSize是2的n 次方+1

int iRealSize = m_nSize - 1;

float fHeight = iRectSize/2;

//这个算法是一个广度递归，用函数处理每个方块是深度递归，只有当前子树所有中值

//和中值边的中点都求出，才能进行下一部递归。所以不能用深度递归。

while( iRectSize>0 )

{

第一步 求出当前方块的中点值，这个循环把当前大小相同的方块中点值都求了出来

a........b

. .

. e .

. .

c.........d

e = (a+b+c+d)/4 + random

In the code below:

a = (i,j)

b = (ni,j)

c = (i,nj)

d = (ni,nj)

e = (mi,mj)

for( i=0; i<iRealSize; i+=iRectSize )

{

for( j=0; j<iRealSize; j+=iRectSize )

{

ni= ( i+iRectSize )%iRealSize;

nj= ( j+iRectSize )%iRealSize;

mi= ( i+iRectSize/2 );

mj= ( j+iRectSize/2 );

pTempBuffer[mi+mj*m_nSize]= ( float )

( ( pTempBuffer[i+j*m_nSize] + pTempBuffer[ni+j*m_nSize] + pTempBuffer[i+nj*m_nSize] + pTempBuffer[ni+nj*m_nSize] )/4

+ RangedRandom( -fHeight/2, fHeight/2 ) );

}

/*求出方块的左边中点和上边中点，右面的中点，正好是相临右方块的左边，

所以当处理右面方块时，就自然求出。下边中点同理。本循环处理了所有当前大小相同方块的左边和上边中点，只有整个地形大方块最右面和最下面没有求出。但上一个循环当iRectSize为1时，就会进行平均计算，把边界算进去

.......

. .

. d .

. .

......a…g…b…

. . .

. e h f .

. . .

......c......

g = (d+f+a+b)/4 + random

h = (a+c+e+f)/4 + random

In the code below:

a = (i,j)

b = (ni,j)

c = (i,nj)

d = (mi,pmj)

e = (pmi,mj)

f = (mi,mj)

g = (mi,j)

h = (i,mj)*/

for( i=0; i<iRealSize; i+=iRectSize )

{

for( j=0; j<iRealSize; j+=iRectSize )

{

ni= (i+iRectSize)%iRealSize;

nj= (j+iRectSize)%iRealSize;

mi= (i+iRectSize/2);

mj= (j+iRectSize/2);

pmi= (i-iRectSize/2+iRealSize)%iRealSize;

pmj= (j-iRectSize/2+iRealSize)%iRealSize;

//上边界

pTempBuffer[mi+j*m_nSize]= ( float )( ( pTempBuffer[i+j*m_nSize]+

pTempBuffer[ni+j*m_nSize] +

pTempBuffer[mi+pmj*m_nSize]+

pTempBuffer[mi+mj*m_nSize] )/4+

RangedRandom( -fHeight/2,fHeight/2 ) );

//左边界

pTempBuffer[i+mj*m_nSize]= ( float )( ( pTempBuffer[i+j*m_nSize]+

pTempBuffer[i+nj*m_nSize]+

pTempBuffer[pmi+mj*m_nSize]+

pTempBuffer[mi+mj*m_nSize] )/4+

RangedRandom( -fHeight/2, fHeight/2 ) );

}

iRectSize/= 2;

//减小高度范围

fHeight*= fHeightReducer;

}

还有一个没有提到的就是，加了个随机高度RangedRandom( -fHeight/2, fHeight/2 ) )

而每次迭代后fHeight*= fHeightReducer; fHeightReducer是平滑因子，fHeightReducer= ，float fHeightReducer= ( float )pow(2, -1*fRoughness); fRoughness越小地形越粗糙，越大越平滑。

图10

最后一个要处理的，因为我们的四叉树LOD必须要用2的n 次方+1 大小的地形，而我们的算法是2的n 次方。当完成作完上面程序后，2的n 次方+1 大小的高程图，还有最后一行和最后一列没有高程数据，我做了简单处理，让最后一行和第一行相等，让最后一列和第一列相等。让最后一个值和第一个值相等。这样就可以保持整个算法的优越性了。

//处理最后一行行

memcpy(&pTempBuffer[(m_nSize-1)*m_nSize],&pTempBuffer[0],sizeof(float)*m_nSize);

//处理最后一列

for(int column = 0 ; column < m_nSize ; column ++)

{

pTempBuffer[column * m_nSize + m_nSize - 1] =pTempBuffer[column*m_nSize];

}

//处理最后一个元素

pTempBuffer[m_nSize * m_nSize - 1] = pTempBuffer[0];

最后别忘了，把高度数据缩放到0到255之间。

ChangeDateRange(pTempBuffer, 0.0f, 255.0f);

二．地形中的纹理

1．地形纹理介绍

很多时候，我们看见的地形就是用一个大纹理图直接映射到上面的，而这个大纹理是作图工具配合你地形生成出来的。当然地形高程数据，也是用作图工具生成的。《FOCUS ON 3D TERRAIN》这本书介绍的地形很详细，它回避了用作图工具来生成高程图和纹理图，而是讲解这些是怎么做的。

图11

这是一个地形的大纹理，当然你的纹理要配合你的高程图数据，这样看起来才能真实。

你要给你的地形顶点计算纹理坐标

图12

为了把整个纹理映射到地形上，需要按照上图一样设置纹理坐标，

for(int index_z = 0 ; index_z < m_nSize ; index_z++)

{

int z_width = index_z * m_nSize;

for(int index_x = 0 ; index_x < m_nSize ; index_x++)

{

m_pVertex[z_width_x].texture.x = index_x * ((1.0f) / （m_nSize - 1）);

m_pVertex[z_width_x].texture.y = index_z * ((1.0f) /（m_nSize - 1）);

}

这段代码表示怎么求纹理坐标，其实很简单的。

我举个例子：比如顶点A在高程图数组下标为（6，8），高程图尺寸为17*17

则顶点A的纹理坐标为（6/17，8/17）。

当然我这里主要不是要说的这些，这些只是介绍下，下面才是关键。

2．小纹理插值生成大纹理。

现在是纹理介绍的重点，很多人对“插值”这个词语不是很了解，其实数学里面经常用到，我就详细解释下。先从数学上解释函数F(x ,y , z……..),已经知道一个符合这个函数的常量A其中x，y，z等参数都已经知道,和符合这个函数的常量B，参数也知道，现在要求的是一个C（t），C（t）在F(x ,y , z……..)上，这里t是变量，范围为0到1，当t = 0 时，

C（0）= A ，当t = 1时 C（1）= B。也就是说，给定一个t，在A和B之间求这个C（t）。

如果知道C（t） = K( A,B,t ) 的这个方程是什么，很容易就求出C（t）。例如线形插值

C（t） = A+（B - A）t。还有四元数插值等等把。

回到正式轨道上来，如果你的高程数据已经生成，现在我们要生成一个大纹理来符合这个高程数据。当然我们的方法是你必须提供小纹理，这些小纹理代表不同高度地形纹理。

例如：

图13 图14

图15 图16

上面4个图分别代表不同高度纹理，地形由低到高的排列次序为图13à图14à图15à图16

我们的高程图数据范围是0到255，把这个4个图划分下高度范围，也就是图13表示高度范围为（0，255 / 4），图14表示高度范围为（255 / 4，255 / 4 * 2），图15表示高度范围为（255 / 4 * 2，255 / 4 * 3），图16表示高度范围为（255 / 4 * 3，255 / 4 * 4），这个划分是均等划分，当然你也可以让用户指定每个图表示的高度范围。我的程序没有指定，就按照这样均等划分，效果也很好。

做完了范围划分之后，你还要处理一个问题，就是纹理过渡带的问题。例如相临两个点A，B高度分别为255 / 4 - 1和255 / 4 + 1，如果我们直接把A贴图13，B贴图14，就有明显的断带区域，连一个过渡都没有。

图17

图17很好的说明了这个问题，出现明显的断带。为了处理这个问题我们就要重新处理范围问题。

图18

对于4个纹理图，我们现在划分成4+1个高度层次

图19

每个图片覆盖的高度区域为2个相临区域。

图20

图20是一个小纹理图覆盖的区域。中间点为100%混合这个纹理，两端为0%，以及以外都是0%。

例如：图14占区域为255/5 到 255/5 *3，它之外的区域都是占这个图14象素0%，如果现在给的高度为255/5*2，则这个高度对应纹理象素就是100%图14象素，如果给定高度X小于255/5*2并且大于255/5 则占，按线性插值来求占百分比，（X – 255/5）/（255/5*2 - 255/5）

如果X大于255/5*2，小于255/5*3，按线性插值来求占百分比，（X – 255/5*2）/（255/5*3 - 255/5*2）

typedef struct TEXTURE_REGION_TYPE

{

int m_iLowHeight; //影响的最低值 (0%)

int m_iOptimalHeight; //影响最好值 (100%)

int m_iHighHeight; //影响最高值 (0%)

}TEXTURE_REGION;

这个结构就来表示高度影响范围

如果有一个顶点A高度ucFinalHeight为，现在就要求出顶点A的纹理象素,下面是伪代码

具体过程就是遍历所有小纹理，然后每个小纹理上取一个象素，然后在求得混合因子，也就是影响比例，和象素乘积，最后相加。

FOR 所有小纹理i

{

ucColor = 当前纹理i上的一个象素点。//在小纹理上究竟取得哪个象素，后面介绍

float fBlend;

if(ucFinalHeight < 当前纹理最小高度影响值（iLowHeight）||

ucFinalHeight >当前纹理最大高度影响值iHighHeight)

fBlend = 0.0f;

else

{

if(ucFinalHeight >= 当前纹理最好高度影响值m_iOptimalHeight)

{

float fTemp1 =m_iHighHeight- m_iOptimalHeight;

float fTemp2 = m_iHighHeight - ucFinalHeight;

fBlend = fTemp2 / fTemp1 ;

}

else

{

float fTemp1 = m_iOptimalHeight -.m_iLowHeight;

float fTemp2 = ucFinalHeight - m_region.m_iLowHeight;

fBlend = fTemp2 / fTemp1 ;

}

//计算颜色

fTotalColor += ucColor * fBlend;

}

我们继续，现在你要准备生成大纹理图了，假设你的纹理图尺寸为 m * n ,你现在要做的就是为这个大纹理图的每个象素点找到它对应的值。首先你要找到大纹理图上每个象素点对应的具体高度。

X = U * (高程图WidthSize – 1) /( m – 1)

Y = V * (高程图heightSize – 1)/ (n – 1)

U>= 0 && U < = m -1 V>=0 && V < = n - 1

HeightMap[X+WidthSize * Y]就是所要求的高度。

其实，这里的X，Y 都取了整数部分，这样做是很不精确的。

因此，我采用了双线形滤波，重新求得高度。

图21

已经知道求出高程图下标为（5.7 ，6.7）。如果取整的话，下标为（5，6）直接取高度33为这个象素对应高度。但实际上，我们要混合（5，6）（6，6）（5，7）（6，7）这四个点，最后求得最终高度。可以看出所求高度占（5，6）点面积为30%*30%（注释：（1 – （5.7 – 5））和（1 – （6.7 –6））），占（6，6）为70%*30% ，占（5，7）30%*70%，占（6，7）70%*70%

用他们各自的高度乘以各自的比例，然后相加就为最后所求最终高度。

float fMapRatio= ( float )((m_nSize - 1) * 1.0f)/ (nSize - 1);

//求出当前象素点对应的高度

//计算纹理图下标X，Z对应的高度，对4个高度进行滤波

//就Z方向的误差

float fHeightDateZ = z * fMapRatio;

int iHeightDateZ = (int)fHeightDateZ;

int iHeightDateZ_1= iHeightDateZ + 1;

if(iHeightDateZ_1 >= m_nSize)

iHeightDateZ_1 = iHeightDateZ;

float fPercentZ_1 = fHeightDateZ - iHeightDateZ;

float fPercentZ = 1.0f - fPercentZ_1;

float fHeightDateX = x * fMapRatio ;

int iHeightDateX = (int)fHeightDateX;

int iHeightDateX_1 = iHeightDateX + 1;

if(iHeightDateX_1 >= m_nSize)

iHeightDateX_1 = iHeightDateX;

float fPercentX_1 = fHeightDateX - iHeightDateX;

float fPercentX = 1.0f - fPercentX_1;

UCHAR ucHeightZ_X = GetHeightDate(iHeightDateX,iHeightDateZ);

UCHAR ucHeightZ_X_1 = GetHeightDate(iHeightDateX_1,iHeightDateZ);

UCHAR ucHeightZ_1_X = GetHeightDate(iHeightDateX,iHeightDateZ_1);

UCHAR ucHeightZ_1_X_1 = GetHeightDate(iHeightDateX_1,iHeightDateZ_1);

UCHAR ucFinalHeight = UCHAR (ucHeightZ_X * fPercentX * fPercentZ +

ucHeightZ_X_1 * fPercentX_1 * fPercentZ +

ucHeightZ_1_X * fPercentX * fPercentZ_1 +

ucHeightZ_1_X_1 * fPercentX_1 * fPercentZ_1);

现在已经纹理图下标X，Z对应的高度，就可以按照介绍前面混合小纹理插值的方法得到纹理下标X，Z的象素值。

前面我有一个地方没有说，就是小纹理混合伪代码中有这段代码

ucColor = 当前纹理i上的一个象素点。//在小纹理上取得哪个象素，后面介绍

现在说是最合适的。取得一个象素，小纹理图是p*q尺寸的，小纹理上有p*q个点象素点，究竟取那一个。当然可以随机取，效果也不错。

我还是采用了《FOCUS ON 3D TERRIAN》上的方法，按照D3D纹理重叠映射方式来取得。

图22

红色为小纹理重叠的方式，黑色为大纹理，大纹理上一个点X，Z，映射到小纹理坐标为X%TileWidth, Z%TileHeight, TileWidth, TileHeight为小纹理的宽和高。

图23

图25表示了整个纹理产生的过程。

图24

图25

图24是高程图，图25是根据图24，和图13，图14，图15，图16小纹理生成大纹理

3．添加细节纹理

为什么要添加细节纹理？这个问的好，我先举个例子，你看了就明白。然后我再讲解。

图26（未添加细节纹理）

图27（添加细节纹理）

图26和图27可以看出地形上明显的不同，可以看出图27的效果要比图26的效果好，只花一点点的努力就可以做到图27的效果，为什么不去做呢？好，现在我就来说明这个。

其实很简单，D3D支持多重纹理渲染，只不过在添加一层细节纹理

图28

图28为细节纹理，和地形纹理不同的是，不能把这个纹理按照1对1的贴上去，下图说明了这个问题

图29

如果把一整个细节纹理贴到地形上的话，细节纹理就会给拉伸，细节层次就模糊。用重叠的方式来贴图，就可以解决纹理被拉伸。其实没什么难的，就是设置顶点的纹理坐标。由于细节纹理坐标和地形纹理坐标不同，所以要再顶点格式里面再添加一个纹理坐标。

for(int index_z = 0 ; index_z < m_nSize ; index_z++)

{

int z_width = index_z * m_nSize;

for(int index_x = 0 ; index_x < m_nSize ; index_x++)

{

int z_width_x = z_width + index_x;

m_pVertex[z_width_x].texture1.x=index_x * ((1.0f) / m_nSize) * m_niDetailRepeat;

m_pVertex[z_width_x].texture1.y=index_z * ((1.0f) / m_nSize) * m_niDetailRepeat;

}

m_niDetailRepeat为重叠贴图的次数。

至于纹理混合运算，我用的MODULATE2X。

如果对这个还是不了解的话，就看看D3D中WRAP纹理映射方式。

4．添加光照贴图

如果地形中没有光照，那实在是太没意思了。D3D中有4种光，提供我们使用，环境光，点光源，平行光，聚光灯。但这只是“光照”，没有阴影，看起来还是不够真实。

游戏中很多光照都用光照贴图来完成，如果你再加一个光照贴图，你纹理层一共有了3层——地形纹理，细节纹理，光照纹理。光照纹理不象细节纹理那样，纹理坐标和地形纹理坐标一样就可以。

图30

图30是一个光照贴图，直接添加到纹理层进行混合，D3D中很简单就可以应用的。我这里要说的是，怎么生成真实光照贴图（图30太假了，不是地形的光照贴图），根据太阳的位置和地形来生成真正的光照纹理。

请允许我发点牢骚，写这个太不容易了，今天是2008年6月21日，他爷爷的， 天气热的要命，我都不愿意动了。又是一个四六级的日子，我四级四年前过了72.5，靠，6级3年半前，我考了59，郁闷死我了。上研究生时就考了一次，还没过，我实在没时间复习6级，真的不是借口，我为了学好游戏编程，坚实的打好每一个基础，大师编程的2本书，代码我用自己的方法几乎全重写，十几万行呀，还要学D3D，学引擎。不是我讨厌英语，我每天都看英文电影、每天都看图形学计算机方面的英文书，随叫咱们是搞游戏的，国内那点中文的，根本就不够添饱我学习游戏、游戏引擎的欲望。我学看3D GAME ENGINE PROGRAMING 1000多页全英文，我至少看2编，里面的精髓被我拿到我引擎里面了，6级英语和我学计算机英语真是2马事，花同样的时间，我学3D编程要比花到6级英语上效率高的多，收获的也很多。请让我说一声“不是我讨厌英语，是我真的很讨厌6级”。

我用的是《FOCUS ON 3D TERRIAN》中的方法，其实这个方法也不是作者发明的，他告诉了读者，这个方法的出处。这个方法优点是速度快，可以支持实时整个地形阴影调整。当然好的东西，总会有坏的一面，缺点是：实际上这个算法是在2D上模拟，而且只支持8个方向的光源。当然效果很好，人类愚蠢的眼睛经常被自己欺骗。

图31

看到没有？是不是很COOL？我知道你一定很着急！再不介绍给你，你就要打我了。哈哈，现在开始吧！

我前面说过，这个算法是实际上是2D的。假设你的光照纹理图是m*n，开始时，你纹理图里没有任何象素，这里很多步骤和地形的小纹理生成大纹理一样，你需要做的是找到光照贴图每个象素对应的高度，然后根据算法，来填充这个象素一个颜色值。

先介绍算法基本思想

图32

看图32，拿象素A来举例子，现在要求A的象素值，首先要找到逆光源方向A的上一个象素点，图32可以看出是象素B，求出A象素对应高度，B象素对应高度，也就是说B比A高，A就被遮挡，A就形成了阴影。

用下面公式计算最终光照象素值的强度。

fShade= 1.0f-( ucFinalHeight_D - ucFinalHeight)/m_fLightSoftness;

其中fShade为象素值强度，ucFinalHeight_D为B的高度，ucFinalHeight为A的高度，m_fLightSoftness为柔和度，这个柔和度是用来调节阴影强度的。也就是说m_fLightSoftness越小，fShade也越小，光照强度也小，所以阴影就越大。

当然计算完成之后还要调节fShade

if( fShade<m_fMinBrightness )

fShade= m_fMinBrightness;

if( fShade>m_fMaxBrightness )

fShade= m_fMaxBrightness;

m_fMinBrightness，m_fMaxBrightness这2个是让用户指定的最小强度和最大强度，必须是0到1之间的。

最后A的象素颜色为fShade * Color,这个如果你要让你光照是白色的话Color=（255，255，255），红色的话Color=（255，0，0）。

整个算法思想就这样，还有2个地方没有说。

一个是求象素对应的高度，这个很地形的小纹理生成大纹理求高度方法一样，我不想再重复了。如果你游戏真是实时改变光源方向话，光照贴图也要改变，为了速度快一些，你可以不用双线形纹理滤波，直接取整。当我不得不告诉你。当你光照贴图尺寸大于地形高程图尺寸时，就会失真。

图33

看图33，黑色是光照贴图尺寸大于地形高程图尺寸，兰色是光照贴图尺寸小于地形高程图尺寸，由于采用了取整方式，画红圈的区域的象素是高度相同的，所以他们之间没有遮挡，所以没有阴影。而只有在两个圈过渡地方，由于高度出现了不同才有阴影出现。所以阴影出现是一条一条的。

图34

当你光照贴图尺寸小于地形高程图尺寸时，是没有问题的。还看图33，兰色纹理，一个象素覆盖了几个高度顶点，即使取整，相临象素也有高度差，所以不影响阴影。

当然没有人愿意用大纹理来做光照贴图，用小于高程图尺寸的光照纹理也不错，用取整方法还不错，速度还快。

第二个问题是我还没介绍怎么根据逆光源方向找上相临象素。由于光照纹理数组是平面2维的，所以对于一个顶点只能有8个方向。

图35

这八个方向分别为（1，1）（1，-1）（-1，1）（-1，-1）（0，1）（0，-1）（-1，0）（1，0）。所以对于任意给定的方向，要调节到这8个方向某一个上面来。

图36

对于任意的光源方向，我们求出角度，然后在哪个角度范围区域内，就调节到这8个方向上来。

for(int i = 0 ; i < 8 ; i++)

{

m_FindTable[i] = cosf((1/16.0f + i /8.0f)*VS2PI);

}

// fDirectionX，fDirectionZ光源方向，让用户输入的，只关心X和Z方向

fCosAngle = fDirectionX / sqrtf(fDirectionX * fDirectionX + fDirectionZ * fDirectionZ);

if(fDirectionZ > 0)

{

if(m_FindTable[0] < fCosAngle && fCosAngle <= 1.0f)

{

m_iDirectionZ = 0;

m_iDirectionX = 1;

}

else if(m_FindTable[1] < fCosAngle && fCosAngle <= m_FindTable[0])

{

m_iDirectionZ = 1;

m_iDirectionX = 1;

}

else if(m_FindTable[2] < fCosAngle && fCosAngle <= m_FindTable[1])

{

m_iDirectionZ = 1;

m_iDirectionX = 0;

}

else if(m_FindTable[3] < fCosAngle && fCosAngle <= m_FindTable[2])

{

m_iDirectionZ = 1;

m_iDirectionX = -1;

}

else if(-1.0f <= fCosAngle && fCosAngle <= m_FindTable[3])

{

m_iDirectionZ = 0;

m_iDirectionX = -1;

}

else

{

if( -1.0f <= fCosAngle && fCosAngle <= m_FindTable[4])

{

m_iDirectionZ = 0;

m_iDirectionX = -1;

}

else if(m_FindTable[4]<fCosAngle&&fCosAngle<= m_FindTable[5])

{

m_iDirectionZ = -1;

m_iDirectionX = -1;

}

else if(m_FindTable[5]<fCosAngle&&fCosAngle<= m_FindTable[6])

{

m_iDirectionZ = -1;

m_iDirectionX = 0;

}

else if(m_FindTable[6]<fCosAngle&&fCosAngle<= m_FindTable[7])

{

m_iDirectionZ = -1;

m_iDirectionX = 1;

}

else if(m_FindTable[7] <= fCosAngle && fCosAngle <= 1.0f)

{

m_iDirectionZ = 0;

m_iDirectionX = 1;

}

下面是整个求出过程代码

float fShade = 0.0f;

float fMapRatio= ( float )((m_nSize - 1) * 1.0f)/ (m_nLightSize - 1);

for( int z=0; z < m_nLightSize ; z++ )

{

for( int x=0; x < m_nLightSize ; x++ )

{

//求出ucFinalHeight_D和ucFinalHeight 没有用双线形滤波，直接用的取整

float fHeightDateZ = z * fMapRatio;

float fHeightDateX = x * fMapRatio ;

int izTemp = z - m_iDirectionZ;

if(izTemp < 0)

izTemp = m_nLightSize - 1;

if(izTemp >= m_nLightSize)

izTemp = 0;

float fHeightDateZ_D = izTemp * fMapRatio;

int ixTemp = x - m_iDirectionX;

if(ixTemp < 0)

ixTemp = m_nLightSize - 1;

if(ixTemp >= m_nLightSize)

ixTemp = 0;

float fHeightDateX_D = ixTemp * fMapRatio ;

UCHAR ucFinalHeight=GetHeightDate(fHeightDateX,fHeightDateZ);

UCHAR ucFinalHeight_D=GetHeightDate(fHeightDateX_D,fHeightDateZ_D);

fShade=1.0f-(ucFinalHeight_D-ucFinalHeight)/m_fLightSoftness;

if( fShade<m_fMinBrightness )

fShade= m_fMinBrightness;

if( fShade>m_fMaxBrightness )

fShade= m_fMaxBrightness;

m_ucpLight[(x+z*m_nLightSize)*3]=(unsignedchar )( fShade*255 );

m_ucpLight[(x+z*m_nLightSize)*3+1]=(unsignedchar )( fShade*255 );

m_ucpLight[ (x + z * m_nLightSize) * 3 + 2] = ( unsigned char )( fShade*255 );

}

三．四叉树LOD渲染地形

这是一个关键的地方，我马上就要揭示怎么用D3D来渲染四叉树LOD地形。

1．LOD介绍

什么是LOD？LOD的英文缩写Level Of Detail ,中文翻译过来就是细节层次。3D用这个细节层次，是因为远处的物体根本就不用描绘那么多细节，因为人眼对于远出的物体细节判断能力很低，所以对于人眼从近到远，相应物体的层次细节为从高到低。

一般层次细节分为2种，一种是模型网格的层次细节，另一个是纹理层次细节。

D3D的PMESH函数接口支持网格的层次细节，也就是它内部有算法可以删除和增加顶点而使模型网格尽量不失真。这个函数大家可以实验下，D3D自己带的例子里面有，我在这里面就不说了。

对于纹理的细节层次，最常见的就是纹理MIPPING，远处的物体不要用那么高分辨率的纹理来帖图。

LOD一般都是根据视点到物体的距离来判断层次等级的，距离越大，LOD层次越小，显示细节越少。

2．地形LOD介绍

地形上用LOD是再好不过的了，《FOCUS ON 3D TERRAIN》上介绍了3种LOD，

第一种是GEOMIP-MAPPING LOD，这种LOD 有点象纹理MIP，算法很简单，唯一值得注意的就是，根据视点到PATCH距离决定PATCH等级，这个距离事先取定的，而四叉树LOD是计算的。也就是说多少到多少距离PATCH等级是1，多少到多少距离PATCH等级是2，等等。如果取不好就会出现相邻PATCH等级大于1，这样就形成了裂缝（Crack）。怎么处理，这个我就不介绍了，《FOCUS ON 3D TERRAIN》由于它距离取的好，所以没有形成裂缝，实际上它没有处理的。

第二种是ROAM，这个算法是属于三角抛分，作者写的太不详细了，它的代码几乎晦涩难懂，我是没有看明白。如果那位大哥看明白了，请告诉小弟。但作者留下了这个算法的英文论文，有时间我决定看下。因为作者实现四叉树LOD时，有些细节我也没看懂，但后来看了他参考的论文，才真正弄明白。

第三种就是四叉树LOD，我不得不说，作者写的真不是很详细，有些细节让我们读代码，它的代码写的真是庞大而且晦涩难东，我可以骄傲的说，我的代码写的比他好，而且我的实现整个思路很清晰，大家一看就明白（当然这里不是说作者思路不清晰，只是他没有完全写明白，或者是作者根本不想详细写，作者认为我们都是高手）。这里我要感谢《Visual C++ DirectX9 3D 游戏开发引导》这本书，我很多知识参考了它，因为这本书四叉树LOD基本思路还是对的，只是有些关键问题他没有解决好，比如：这本书的LOD简直无法运行，慢的要命，有2个致命的速度屏障作者根本没有解决，我不明白作者没有处理好这个问题为什么还要写出来。

我见过一个GPGL的代码写的LOD是第1种LOD，相对来说第1种LOD容易实现，而且可以用PVS算法处理被遮挡的PATCH。但我说过如果不同等级的PATCH距离没有取好，就要形成裂缝，所以这种灵活性很差。

我用第3种算法实现，LOD等级随便调节，而且可以预处理，无论怎么渲染都没有裂缝。但对于被遮挡的PATCH，我还没有想出一个快速的算法，如果你有，请把你的思路写出来，告诉我。

3．地形四叉树LOD详细介绍

我以前做过软件引擎（《3D游戏编程大师技巧》你看没有？就是把整个D3D流水线自己用代码全部实现，没有用显卡的任何3D功能。）当时我的流水线是基于单个三角形的，当时为了快速渲染地形、实现相机剪裁，我做了一个地形四叉树。

这里我要说的是地形四叉树LOD和地形四叉树不一样，地形四叉树，只不过是把地形的三角形用四叉树的方式进行分类，来进行快速相机剪裁或者是碰撞处理，而地形四叉树LOD和地形四叉树不同在于：

A．地形四叉树三角形网格不变的，而地形四叉树LOD网格随着视点动态变化的。

B．地形四叉树三角形网格相当于四叉树LOD网格的最高层次。

地形四叉树LOD有所有地形四叉树的优点，而且速度更快。

我知道你已经等不及了，现在我就来介绍基本算法，记住只是基本算法，具体细节我先不说，我只是让你对算法有个大体了解。

3．1 四叉树（QUATREE）划分介绍

图37

假设一个大的方块空间里面有很多个点，你现在只在意图37中显示的那个点。现在你要把这个点划分到一个小的子空间中，运用四叉树空间划分方法。

把整个空间等4等分。

图38

继续4等分这个点所在空间

图39

继续4等分这个点所在空间

图40

一直到某一个条件满足划分结束。这个条件根据不同应用是不同的，可能的条件有：多边形四叉树，多边形数目大于一定数目，物体级别四叉树，物体个数大于一定数目，还可以规定层次大于某个数目，等等。关键取决与你和你引擎用来干什么。

上面的过程说明了四叉树划分过程，下面让我们来正式介绍地形LOD四叉树。

3．2 地形LOD四叉树的划分矩阵

地形LOD四叉树是基于一个划分矩阵的，这个划分矩阵根据一个划分方法来记录每次的划分结果，然后渲染函数根据划分结果来渲染三角形扇形。这里简单的说了下基本方法，“一个划分方法”是什么方法，我们后面说，后面还有很多细节要说。下面介绍这个划分矩阵。

划分矩阵和高程图矩阵是同样大小的，而且为了做四叉树LOD，大小都必须是2的n次方+1。

图41

图41是一个划分矩阵，1表示以它为中心正方形被划分，0表示没有被划分。

图42

图42是划分后形成的网格，我们用的是三角形扇形，为什么用扇形，简单讲，因为用扇形处理LOD渲染很容易的。当划分矩阵形成之后，渲染函数要用划分矩阵来进行渲染，当遇到1的时候，进行4个子树的递归处理，如果遇到0就要进行以这个为中心点的扇形渲染，然后跳出结束当前函数，渲染其他的。这里还有个问题，后面再详细说，这里只是介绍。

图43

图43说明了一个中心点0和它四周顶点，这样就生成了一个扇形。

3．2．1递归求划分矩阵

求划分矩阵是递归求得的，当然任何递归都要有个满足条件，到达这个满足条件就要停止递归，当然我们的递归也有条件，而且是2个条件。

A．其中L是视点到划分正方形中心顶点的距离，也可以说成视点到四叉树节点的中心距离。D为这个正方形的边长。K为距离调节系数，C为高度调节系数，。当F小于1时，就划分这个节点。

如图45和43

Dh1 = （顶点3+顶点5）/2 - 顶点4

Dh2 = （顶点1+顶点3）/2 - 顶点2

Dh3 = （顶点1+顶点7）/2 - 顶点8

Dh4 = （顶点5+顶点7）/2 - 顶点6

Dh5 = （顶点1+顶点5）/2 - 顶点0

Dh6 = （顶点3+顶点7）/2 - 顶点0

从这个方程里面看，L越大，F越大，被划分的可能性就越小。D越大，F越小，划分的可能性就越大，C越大，F越小，划分的可能性就越大。

图44

图45

B．最小正方形边长大于等于2

图46

图47

看图46，47画蓝色圆圈的中心点和旁边的说明，你会明白的。也就是说为什么边长要大于等于2，换句话就是顶点宽度要大于等于3。3个顶点确定了2条边。

if( iEdgeLength > 3 )

{

if(用相机剪裁当前正方形PATCH)

{ //用来相机剪裁的，后面详细介绍

//渲染时只处理LOD矩阵为1和0，2是表示被剪裁所以就跳过了。

SetLODMatrix(iX,iZ ,2);

}

else

{

float fViewDistance, f;

int iChildOffset;

int iChildEdgeLength;

int iBlend;

fViewDistance= ( float )( fabs( m_fViewX - m_pVertex[iX + iZ * m_nSize].position.x)+

fabs( m_fViewY - m_pVertex[iX + iZ * m_nSize].position.y)+

fabs( m_fViewZ - m_pVertex[iX + iZ * m_nSize].position.z));

f= fViewDistance/( iEdgeLength * m_fMinResolution *

(MAX( m_fDetailLevel*GetDHMatrix(iX,iZ), 1.0f )) );

if( f<1.0f )

iBlend= 1;

else

iBlend= 0;

SetLODMatrix(iX,iZ ,iBlend);

if( iBlend == 1)

{

iChildOffset = ( ( iEdgeLength-1 ) >> 2 );

iChildEdgeLength= ( iEdgeLength+1 ) >> 1;

//lower left

UpDateLODNode( iX - iChildOffset, iZ - iChildOffset, iChildEdgeLength );

//lower right

UpDateLODNode( iX + iChildOffset, iZ - iChildOffset, iChildEdgeLength );

//upper left

UpDateLODNode( iX - iChildOffset, iZ + iChildOffset, iChildEdgeLength );

//upper right

UpDateLODNode( iX + iChildOffset, iZ + iChildOffset, iChildEdgeLength );

}

2个条件都介绍完毕，在生成划分矩阵之前，你还要用一个DH矩阵来存储的值，就象划分矩阵一样，只不过这里存储的不是0、1，而是高度值，这个DH矩阵不用每次更新，它是固定的。当然生成它很简单，但我这里要说的是一个关键性的问题。

3．3修改DH矩阵生成方法

为什么要修改DH矩阵，直接用这个公式，从最小的2条边的正方形一直遍历到整个大的地形正方形，都求得，然后存在DH矩阵里面，不可以吗？

答案是可以的，但这里有个问题。我们扇形渲染只是基于相临层次差别不大于1的。

图48

图48是相临层次差别等于1的时候，上图如果按照正常的三角形渲染就会出现图49那样的裂缝（Crack），我们用刨除点的方法（当然也可以用补点的方法，这个方法很麻烦）就要把A、B2个点拿掉，进行渲染。具体怎么处理到后面渲染再详细说，这里只是要说明，我们只能处理层次差别等于1的，当然层次相等根本用不着处理。

图49

问题就出现了，当层次差别大于1时，怎么办？我们怎么用刨除点的方法来处理裂缝？

图50

图50说明了这个问题，我们不可能用一个高效的方法来进行刨除点处理。所以我们要换一个角度来想这个问题，我们尽量保证相临的层次差别永远保持到小于等于1。

一种方法是用《Visual C++ DirectX9 3D 游戏开发引导》中的方法，当你生成划分矩阵后，重新调整相临层次大于1的。这是它的一个速度瓶颈，它之所以这么慢就是因为每次生成划分矩阵都要重新调整，浪费了很多时间。

难道有方法可以预先处理这个问题吗？答案是可以的。为了让你们明白这个，我又要讲数学了。

图51

图51，问题出在兰色正方形和红色正方形，也就是说，兰色正方形划分了，但红色正方形没有划分，或者说红色正方形没有划分，兰色正方形却划分了。所以这里有两种更改方法，一个是更改兰色的，让它层次变小，不划分，另一个是让红色的层次变大，进行划分。我们采用了依据小的正方形来影响大的正方形。也就是说当兰色正方形划分了，它相临的上2个层次正方形也要划分，这样保证相临层次小于等于1。

现在假设兰色划分值为F1，红色为F2。

也就是说F1小于1，那么F2也要小于1，才能保证红色划分。

那么F2<F1<1就可以保证，这个条件永远成立。

因为，所以

因为d2 = 2*d1，所以

图52

如果要满足条件必须，H2 / H1 < K

也就是说红色的最大高度<兰色最大高度*K 。

我现在说下就DH矩阵具体算法。

从最小的正方形开始，也就是边长为2（我的引擎里用的顶点数，也就是说边长为n，则连接这些边的顶点是n+1个，也就是为什么要求高程图为2的n 次方+1，其实边长为2的n次方）。求出它们的最大DH，做为H值，然后在遍历边长为4的，求出它们的各自DH，然后在和它相临的、小一个等级的所有正方形比较，求出最大的，作为H值，遍历边长为8的，重复这个过程，直到最大的正方形为止。

这个过程是广度遍历，不是深度递归，如果你了解深度递归原理，你就会很清楚，只能用广度遍历才能办到。

//这里的边长是用顶点个数来表示的，边长为2，顶点个数为3。

int iEdgeLength = 3;

while(iEdgeLength <= m_nSize)

{

int iEdgeOffset= ( iEdgeLength-1 )>>1; //边长的一半

int iChildOffset= ( iEdgeLength-1 )>>2; //它儿子的边长

for( int z = iEdgeOffset; z < m_nSize; z +=( iEdgeLength-1 ) )

{

for(int x = iEdgeOffset; x < m_nSize; x +=( iEdgeLength-1 ) )

{

if(iEdgeLength == 3)

{

//最小正方形,求出各边的DH，然后求最大值作为本正方形的//DH。

int iDH[6];

//BOTTOM

iDH[0] = ( int )ceil( abs( ( ( GetHeightDate( x-iEdgeOffset, z+iEdgeOffset )+GetHeightDate( x+iEdgeOffset, z+iEdgeOffset ) )>>1 )-

GetHeightDate( x,z+iEdgeOffset ) ) );

//RIGHT

iDH[1] = ( int )ceil( abs( ( ( GetHeightDate( x+iEdgeOffset, z+iEdgeOffset )+GetHeightDate( x+iEdgeOffset, z-iEdgeOffset ) )>>1 )-

GetHeightDate( x+iEdgeOffset,z ) ) );

//TOP

iDH[2] = ( int )ceil( abs( ( ( GetHeightDate( x-iEdgeOffset, z-iEdgeOffset )+GetHeightDate( x+iEdgeOffset, z-iEdgeOffset ) )>>1 )-

GetHeightDate( x,z-iEdgeOffset ) ) );

//LEFT

iDH[3] = ( int )ceil( abs( ( ( GetHeightDate( x-iEdgeOffset, z+iEdgeOffset )+GetHeightDate( x-iEdgeOffset, z-iEdgeOffset ) )>>1 )-

GetHeightDate( x-iEdgeOffset,z ) ) );

//LEFT-TOP TO RIGHT-BOTTOM

iDH[4] = ( int )ceil( abs( ((GetHeightDate(x-iEdgeOffset, z-iEdgeOffset )+GetHeightDate( x+iEdgeOffset, z+iEdgeOffset ) )>>1 )-

GetHeightDate( x,z ) ) );

//RIGHT-TOP TO LEFT-BOTTOM

iDH[5] = ( int )ceil( abs( ((GetHeightDate(x+iEdgeOffset, z-iEdgeOffset )+GetHeightDate( x-iEdgeOffset, z+iEdgeOffset ) )>>1 )-

GetHeightDate( x, z ) ) );

//求最大DH

int iDHMAX = iDH[0];

for( int i = 1 ; i < 6 ; i++)

{

if(iDHMAX < iDH[i])

iDHMAX = iDH[i];

}

SetDHMatrix(x,z,iDHMAX);

}

else

{

//如果不是最小正方形，要根据它相临的等级一样正方形的儿子//节点，求出DH

int iDH[14];

int iNumDH = 0;

float fK = 1.0f * m_fMinResolution / ( 2.0f * ( m_fMinResolution - 1.0f ) );

//LEFT TWO CHILD

int iNeighborX;

int iNeighborZ;

iNeighborX = x - (iEdgeLength -1);

iNeighborZ = z;

if(iNeighborX > 0)

{

iDH[iNumDH] = GetDHMatrix(iNeighborX + iChildOffset, iNeighborZ - iChildOffset);

iNumDH++;

iDH[iNumDH] = GetDHMatrix(iNeighborX + iChildOffset, iNeighborZ + iChildOffset);

iNumDH++;

}

//TOP TWO CHILD

iNeighborX = x ;

iNeighborZ = z - (iEdgeLength -1);

if(iNeighborZ > 0)

{

iDH[iNumDH] = GetDHMatrix(iNeighborX - iChildOffset, iNeighborZ + iChildOffset);

iNumDH++;

iDH[iNumDH] = GetDHMatrix(iNeighborX + iChildOffset, iNeighborZ + iChildOffset);

iNumDH++;

}

//RIGHT TWO CHILD

iNeighborX = x + (iEdgeLength -1);

iNeighborZ = z ;

if(iNeighborX < m_nSize)

{

iDH[iNumDH] = GetDHMatrix(iNeighborX - iChildOffset, iNeighborZ - iChildOffset);

iNumDH++;

iDH[iNumDH] = GetDHMatrix(iNeighborX - iChildOffset, iNeighborZ + iChildOffset);

iNumDH++;

}

//BOTTOM TWO CHILD

iNeighborX = x ;

iNeighborZ = z + (iEdgeLength -1);

if(iNeighborZ < m_nSize)

{

iDH[iNumDH] = GetDHMatrix(iNeighborX - iChildOffset, iNeighborZ - iChildOffset);

iNumDH++;

iDH[iNumDH] = GetDHMatrix(iNeighborX + iChildOffset, iNeighborZ - iChildOffset);

iNumDH++;

}

//然后求自身的DHi

//BOTTOM T

iDH[iNumDH] = ( int)ceil(abs(( ( GetHeightDate( x-iEdgeOffset, z+iEdgeOffset )+GetHeightDate( x+iEdgeOffset, z+iEdgeOffset ) )>>1 )-

GetHeightDate( x,z+iEdgeOffset ) ) );

iNumDH++;

//RIGHT

iDH[iNumDH]=( int )ceil( abs( ((GetHeightDate(x+iEdgeOffset,z+iEdgeOffset )+GetHeightDate( x+iEdgeOffset, z-iEdgeOffset ) )>>1 )-

GetHeightDate(x+iEdgeOffset,z ) ) );

iNumDH++;

//TOP

iDH[iNumDH] =(int)ceil(abs(((GetHeightDate(x-iEdgeOffset, z-iEdgeOffset )+GetHeightDate( x+iEdgeOffset, z-iEdgeOffset ) )>>1 )-

GetHeightDate( x,z-iEdgeOffset ) ) );

iNumDH++;

//LEFT

iDH[iNumDH]=(int)ceil(abs(((GetHeightDate(x-iEdgeOffset,z+iEdgeOffset )+GetHeightDate( x-iEdgeOffset, z-iEdgeOffset ) )>>1 )-

GetHeightDate( x-iEdgeOffset,z ) ) );

iNumDH++;

//LEFT-TOP TO RIGHT-BOTTOM

iDH[iNumDH]=(int)ceil(abs(((GetHeightDate(x-iEdgeOffset,z-iEdgeOffset )+GetHeightDate( x+iEdgeOffset, z+iEdgeOffset ) )>>1 )-

GetHeightDate( x,z ) ) );

iNumDH++;

//RIGHT-TOP TO LEFT-BOTTOM

DH[iNumDH] = ( int )ceil( abs(((GetHeightDate(x+iEdgeOffset, z-iEdgeOffset )+GetHeightDate( x-iEdgeOffset, z+iEdgeOffset ) )>>1 )-

GetHeightDate( x, z ) ) );

iNumDH++;

int iDHMAX = iDH[0];

for( int i = 1 ; i < iNumDH ; i++)

{

if(iDHMAX < iDH[i])

iDHMAX = iDH[i];

}

SetDHMatrix(x,z,(int)ceil(fK * iDHMAX));

}

iEdgeLength= ( iEdgeLength<<1 )-1;

}

这样就求完了DH 矩阵。

4．顶点管理器

以上过程我们已经生成了LOD划分矩阵，如果直接用D3D自己带的三角形扇形的渲染方式，在用刨除点的方法（后面详细说）就可以完成渲染了。

但我不得不告诉你，不能用D3D自己带的三角形扇形的渲染方式，它的速度很慢，尤其你渲染地形时，扇形很多，如果不能处理好CPU和显卡的关系话，你的渲染速度很糟糕，这就是《Visual C++ DirectX9 3D游戏开发引导》渲染慢的另一个原因。

那么我们要怎么处理CPU和GPU关系？怎么管理渲染的数据？

我先说下，CPU和GPU之间经常出现的问题是，CPU等待GPU的数据或者GPU等待CPU的数据，这样等待浪费了大量的时间。我们很难把CPU和GPU协调到最优的程度，但我们能尽量保证它们协调工作，也就是CPU处理数据时，GPU不用等待CPU，有数据进行渲染。解决它有一个最简单的方法就是，CPU处理完一部分数据，马上让GPU渲染，在GPU渲染的同时，然后CPU再处理另一部分数据，当CPU处理完这部分数据，再让GPU渲染，循环这个过程。

这个方法就是简单协调CPU和GPU关系。

从上面的方法可以看出，CPU处理的数据，然后给GPU渲染，这些数据是动态改变的，否则就不会让CPU进行计算，再给GPU渲染。如果对于静态不需要修改的数据，直接渲染就可以了。

由于地形LOD顶点数据是动态改变的，我们要用上面的方法进行管理。

好，现在我们想象下，我们动态顶点管理器中，应该有什么东西？

A．根据不同顶点格式，要用不同的缓冲区。

B．相同的顶点格式，不同的材质纹理要有不同的顶点缓冲区

说到这里很棘手，因为我的引擎里面还有材质和纹理管理器，顶点管理器包括动态顶点管理和静态顶点管理。如果这些全都讲了，我好象在说一个小引擎怎么做？工作量真的很大，其实这些大部分内容来自《3D GAME ENGINGE PROGRAMING》只不过我改了很多，但基本思想是一样的。所以这里我只是给出伪代码，我相信如果你3D编程能力还过得去，加上参考《3D GAME ENGINGE PROGRAMING》，应该自己可以实现的。

首先我们要根据材质纹理进行创建顶点缓冲。

//根据材质纹理进行创建顶点缓冲

class VSCacheD3D

{

Private:

UINT m_nNumVertsMax; //最大顶点个数

UINT m_nNumIndisMax; //最大索引个数

UINT m_nNumVerts; //顶点个数

UINT m_nNumIndis; //索引个数

UINT m_nStride; //顶点字节

UINT m_SkinID; //材质纹理管理器的ID

DWORD m_dwID; //这个顶点缓冲的ID

DWORD m_dwFVF; //顶点格式

//D3D里面的，这些应该能看明白。

LPDIRECT3DVERTEXBUFFER9 m_pVB;

LPDIRECT3DINDEXBUFFER9 m_pIB;

LPDIRECT3DDEVICE9 m_pDevice;

VSSkinManagerD3D *m_pSkinMan; //材质纹理管理器

VSVertexManagerD3D *m_pCacheMan; // 顶点管理器

}

#define NUM_CACHES_FVF 10

typedef struct VSCACHED3DFVF_TYPE

{

DWORD m_dwFVF; //顶点格式

UINT m_nStride; //顶点字节宽度

VSCacheD3D *m_Cache[NUM_CACHES_FVF];

}VSCACHED3DFVF;

//顶点管理器

class VSVertexManagerD3D

{

vector<VSCACHED3DFVF> m_vCacheSet;

}

现在我来详细说下，VSCacheD3D类是根据材质进行分类，VSCACHED3DFVF_TYPE是根据顶点格式分类的结构，里面包含了10个材质的顶点缓冲。VSVertexManagerD3D用来管理不同格式顶点缓冲。

图53

图53说明了整个类之间的组织管理，现在的问题时，我们要往 VSCacheD3D类对象里填充数据， VSVertexManagerD3D要管理这些数据，究竟怎么填充。

A．你要填充某些数据，必须提供给VSVertexManagerD3D对象顶点格式，顶点数据，顶点个数，顶点索引，顶点索引个数，还有材质纹理ID。

B．然后VSVertexManagerD3D根据提供顶点格式，找到对应的顶点格式缓冲。如果没有这个顶点格式，则创建。

C．找到顶点格式后，根据材质纹理ID添加到到对应的VSCacheD3D对象，也就是纹理材质顶点缓冲。

a) 如果找到，则查看当前纹理材质顶点缓冲区大小，是否有空间可以再添加这些数据，

i. 如果有，则添加。

ii. 没有，则马上渲染这个纹理材质顶点缓冲，清空后，（就是让，m_nNumVerts顶点个数，m_nNumIndis索引个数为0，这就足够了）添加数据。

b) 如果没有找到

i. 如果所有纹理材质顶点缓冲区都满，则找一个顶点数目最多纹理材质顶点缓冲，渲染它，然后清空，添加数据

ii. 如果还有纹理材质顶点空缓冲区，则添加，改写这个纹理材质顶点缓冲材质纹理ID

上面过程是整个添加数据过程，只有a) ii过程和b)i 过程才存在渲染，这个是不够的，为了让我们的顶点管理器能正常渲染，必须要在，改变D3D渲染状态时就要渲染整个的顶点管理器（设置ALPHA，深度缓存，世界矩阵等等，你仔细思考下后，其实这个过程很容易理解。），还有最后在翻转屏幕表面前，也要渲染整个的顶点管理器。这样就保证能正常渲染。这些你做引擎时，都要封装，不要用户做这些处理。

还有一个问题就是，如果你当前顶点格式并且指定的材质纹理ID的顶点数据，大于VSCacheD3D最大缓冲区时，怎么办？因为这个VSCacheD3D缓冲区是事先在创建时就申请好的，我一般设置可以容纳8000顶点大小，我们只不过是往里面添加数据，并且所有的材质纹理顶点缓冲都一样大。如果你把这个材质纹理顶点缓冲销毁，在重新申请，我想在真正游戏运行时，进行这个处理会很大影响速度，所以你事先就要指定一个足够大的空间，让这种情况不会出现。D3D LOCK确实很浪费时间，但我们的管理器只是很少的LOCK，即使添加完数据也不是马上渲染的，所以这个动态管理速度还是很快的。

最后一个问题就是创建材质纹理顶点缓冲时，要用D3D的D3DUSAGE__DYNAMIC，这个可以让用户修改D3D顶点缓冲。

整个动态管理的过程，我就介绍完了，当然很多实现的细节没有说，但我相信，如果你水平还可以，听我说完应该可能实现，你可以参考GAME ENGINGE PROGRAMING》这本书，至少要看完前6章，把代码每个部分都弄明白，它的引擎的底层，我想你就全掌握了。我认为他引擎有些部分细节地方做的不好，不方便用户的使用，所以我的引擎里面都改了过来。当然要把握它前6章的整个框架不是很容易的，多花些时间，再加上作者书里的解释，没关系，你一定行的。

5．渲染地形

终于走到地形渲染，很不容易，不知道上面的你是否看明白，我已经写的很详细了，千万别骂我，写的太垃圾。

这一部分主要内容是根据划分矩阵来渲染扇形，当然扇形的数据只是添加到顶点管理器，渲染由引擎自动来处理的（上一节，我说的什么时候进行渲染，那几种情况，你还记得吗？如果你记得，你就不会蒙。）实际上，这里如果你不在乎速度问题，完全可以用D3D自己带的扇形渲染来处理。

让我们正式入题，由于我没有用D3D自带的扇形渲染，而我的顶点管理器只接受顶点和顶点索引。所以我要自己定义一个扇形类。

//顶点格式，用了2个纹理坐标，地形纹理和光照纹理用texture，细节纹理//用texture1

typedef struct VERTEX_TYPE

{

D3DXVECTOR3 position;

D3DXVECTOR3 normal;

D3DXVECTOR2 texture;

D3DXVECTOR2 texture1;

}VSVERTEX, *PVSVERTEX;

//扇形类

class VSFan

{

public:

VSFan()

{

m_iNumVertex = 0;

m_iNumIndex = 0;

}

~VSFan(){};

WORD m_wFanIndex[24]; //最多8个三角形，24个索引，这里

//面的索引就是为了渲染方便，并没有节省任何空间。

VSVERTEX m_FanVertex[10];//最多10顶点

inline void AddVertex(const VSVERTEX & Vertex)

{

memcpy(&m_FanVertex[m_iNumVertex],&Vertex,sizeof(VSVERTEX));

m_iNumVertex++;

if(m_iNumVertex >= 3)

{

m_wFanIndex[m_iNumIndex] = 0;

m_iNumIndex++;

m_wFanIndex[m_iNumIndex] = m_iNumVertex - 2;

m_iNumIndex++;

m_wFanIndex[m_iNumIndex] = m_iNumVertex - 1;

m_iNumIndex++;

}

void Clear()

{

m_iNumVertex = 0;

m_iNumIndex = 0;

}

int m_iNumVertex; //顶点个数

int m_iNumIndex; //索引个数

};

图54

一个扇形其实9个顶点，但为了闭合，最后顶点点1还要加上。D3D中默认是顺时针可见，所以顶点的排列成三角形顺序为0、1、2 ， 0、2、3 ， 0、3、4………一直到0、8、9（为了闭合，要把顶点1多加一次，实际上顶点9是顶点1）。当你添加完你要渲染的扇形所有顶点时，你就可以，把这个扇形数据都加到用顶点管理器里。

现在要到关键的地方了，就是怎么根据划分矩阵渲染扇形？前面我们经过一系列的处理，保证相临的正方形层次等级小于等于1。

我们的渲染过程也是递归的，是深度递归，求划分矩阵也是深度递归，但求DH矩阵是广度遍历，我希望你能弄明白这个为什么只能用深度递归，不能用广度遍历。

如果当前节点的划分矩阵对应值为1，则继续递归4个儿子节点。

如果当前节点的划分矩阵对应值为2，也就是被相机剪裁掉了（后面讲具体怎么相机剪裁），不做任何处理。

如果当前节点的划分矩阵对应值为0，也就是要渲染了。

我们不可能把扇形的8个三角形都渲染出来，由于相临的层次等级不同，要适当的刨除一些点。如果你仔细观察这个问题，记住相临的正方形层次等级小于等于1，再看图54，可能刨除的顶点是顶点2，4，6，8。而0，1，3，5，7是永远不可能刨除的。之所以形成裂缝都是因为多了这4个点。

图55

看图55左面的兰色正方形比右面红色的大一个等级，所以左面兰色正方形的儿子绿色正方形添加了A点，造成了裂缝，也就是说，只有顶点2、4、6、8出现才造成了这个问题。刨除顶点只需要处理顶点2、4、6、8。

因为我们渲染是扇形，刨除顶点，换个角度，只许考虑顶点2、4、6、8是否应该应该添加进来。

我举个例子，当处理绿色正方形，考虑是否添加A顶点时，就要看绿色正方右面邻居黄色正方形对应划分矩阵是否为1，

如果是1（表明它右面邻居层次比它大），则添加顶点A。

如果是0，还要看黄色正方形的父亲节点（红色正方形）是否为1

如果是1，则添加顶点A

其他情况都是顶点A，不用添加的情况。

因为只有正方形节点划分矩阵对应值为0时，才做渲染才处理，才考虑这种情况，所以为了处理2、4、6、8四个点是否添加，要知道这个正方形是它父亲的哪个节点，也就是说，绿色正方形要知道它是它父亲（兰色正方形）右上儿子。必须要知道方位，这个方位递归时可以按参数传进来，。知道方位处理就变得很容易，这样我们考虑2、4、6、8四个点时，不用全考虑的。例如：对于绿色正方形，它只需要考虑是否添加顶点2和顶点4，因为和它共用顶点6、顶点8的正方形，它们是同一父亲节点，层次必然大于等于它，根本不用考虑直接添加。而且知道方位后，找邻居节点的父亲节点也非常容易。当然是否添加顶点时，还要看是否有相应的邻居，对于绿色正方形，没有上邻居，顶点2直接添加。

这个是处理兰色正方形右上节点绿色正方形时的情况，处理兰色正方形其他节点梢有不同，但基本方法是一样的。

我现在列出代码，很长，但逻辑很清晰。

图56

HRESULT VSTerrain::RendLODNode(int iX , int iZ, int iEdgeLength,int iChild)

{

// iX，iZ划分矩阵节点位置，边长iEdgeLength（我用的是顶点个数），iChild儿子方位

int iBlend = GetLODMatrix(iX,iZ);

//当前划分矩阵为1，则继续递归

if(iBlend == 1)

{

int iChildOffset = ( ( iEdgeLength-1 ) >> 2 );

int iChildEdgeLength= ( iEdgeLength+1 ) >> 1;

//lower left

RendLODNode( iX - iChildOffset, iZ - iChildOffset, iChildEdgeLength , 1);

//lower right

RendLODNode( iX + iChildOffset, iZ - iChildOffset, iChildEdgeLength , 2);

//upper left

RendLODNode( iX - iChildOffset, iZ + iChildOffset, iChildEdgeLength , 3);

//upper right

RendLODNode( iX + iChildOffset, iZ + iChildOffset, iChildEdgeLength , 4);

}如果为0，则添加节点，准备渲染

else if(iBlend == 0)

{

int iEdgeOffset= ( iEdgeLength-1 )>>1;

m_Fan.Clear();

VSVERTEX *Vertex = NULL;

int iNeighborZ;

int iNeighborX;

int iNeighborParentZ;

int iNeighborParentX;

//MIDDLE，处理中间顶点0

Vertex = GetRealDate(iX,iZ);

m_Fan.AddVertex(*Vertex);

//LEFT-TOP，处理顶点1，直接添加

Vertex = GetRealDate(iX - iEdgeOffset ,iZ - iEdgeOffset);

m_Fan.AddVertex(*Vertex);

//TOP-MIDDLE，处理顶点2，要看这个节点的儿子方位，也就是它父亲的哪个儿子

Vertex = GetRealDate(iX ,iZ - iEdgeOffset);

iNeighborZ = iZ - (iEdgeLength - 1);

iNeighborX = iX;

//如果当前节点是它父亲节点的下面俩个节点，方位为3，4，则它上面的邻接节点和它是用一个父亲，并且层次必然大于等于它，则直接添加节点，后面程序中添加顶点4，6，8处理方法根据节点方位不同，但基本思想是一样的

if(iChild == 3 || iChild == 4)

{

m_Fan.AddVertex(*Vertex);

}

else

{

if( iNeighborZ > 0) //是否有上邻居

{

//如果当前节点是它父亲节点的左上节点，考虑它上面邻接点

//如果上面邻接点是0，则还要考虑邻接点的父亲节点，如果

//邻接点的父亲节点是0，就不能添加这个点，如果邻接点的父亲节//点是1，可以添加。

//由于最开始生成DH矩阵的算法，已经保证相临层次不大与1，所//以不用再进一步检测邻接点的父亲节点的父亲节点。下面的算法同//理，只不过根据不同邻接节点，它父亲节点位置不同。

if(iChild == 1)

{

if(GetLODMatrix(iNeighborX , iNeighborZ) == 1) //上邻居层次比它大

{

m_Fan.AddVertex(*Vertex);

}

else //上邻居的层次比它小

{

//看它上邻居的父亲节点,父亲节点是它上邻居的右上的点

iNeighborParentX = iNeighborX + iEdgeOffset;

iNeighborParentZ = iNeighborZ - iEdgeOffset;

if(GetLODMatrix(iNeighborParentX ,iNeighborParentZ) == 1)

{

m_Fan.AddVertex(*Vertex);

}

}else if(iChild == 2)

{

if(GetLODMatrix(iNeighborX , iNeighborZ) == 1 ) //上邻居层次比它大

{

m_Fan.AddVertex(*Vertex);

}

else //上邻居的层次比它小

{

//看它上邻居的父亲节点,父亲节点是它上邻居的左上的点

iNeighborParentX = iNeighborX - iEdgeOffset;

iNeighborParentZ = iNeighborZ -iEdgeOffset;

if(GetLODMatrix(iNeighborParentX ,iNeighborParentZ) == 1)

{

m_Fan.AddVertex(*Vertex);

}

Else//没有上邻居直接添加

{

m_Fan.AddVertex(*Vertex);

}

//RIGHT-TOP，添加顶点3

Vertex = GetRealDate(iX + iEdgeOffset ,iZ - iEdgeOffset);

m_Fan.AddVertex(*Vertex);

//RIGHT-MIDDLE添加顶点4

Vertex = GetRealDate(iX + iEdgeOffset,iZ);

iNeighborZ = iZ ;

iNeighborX = iX + (iEdgeLength - 1);

//看方位，如果是1，3则直接添加

if(iChild == 1 || iChild == 3)

{

m_Fan.AddVertex(*Vertex);

}

else

{

if( iNeighborX < m_nSize) //是否有右邻居

{

if(iChild == 2)

{

if(GetLODMatrix(iNeighborX , iNeighborZ) == 1) //邻居层次和它是否相同

{

m_Fan.AddVertex(*Vertex);

}

else //右邻居的层次比它小

{

//看它邻居的父亲节点,父亲节点是它邻居的右下的点

iNeighborParentX = iNeighborX + iEdgeOffset;

iNeighborParentZ = iNeighborZ + iEdgeOffset;

if(GetLODMatrix(iNeighborParentX ,iNeighborParentZ) == 1)

{

m_Fan.AddVertex(*Vertex);

}

else if(iChild == 4)

{

if(GetLODMatrix(iNeighborX , iNeighborZ) == 1) //邻居层次和它是否相同

{

m_Fan.AddVertex(*Vertex);

}

else //右邻居的层次比它小

{

//看它邻居的父亲节点,父亲节点是它邻居的右上的点

iNeighborParentX = iNeighborX + iEdgeOffset;

iNeighborParentZ = iNeighborZ - iEdgeOffset;

if(GetLODMatrix(iNeighborParentX ,iNeighborParentZ) == 1)

{

m_Fan.AddVertex(*Vertex);

}

else

{

m_Fan.AddVertex(*Vertex);

}

//RIGHT-BOTTOM 顶点5

Vertex = GetRealDate(iX + iEdgeOffset ,iZ + iEdgeOffset);

m_Fan.AddVertex(*Vertex);

//BOTTOM-MIDDLE

Vertex = GetRealDate(iX ,iZ + iEdgeOffset);

iNeighborZ = iZ + (iEdgeLength - 1);

iNeighborX = iX ;

if(iChild == 1 || iChild == 2)

{

m_Fan.AddVertex(*Vertex);

}

else

{

if( iNeighborZ < m_nSize) //是否有下邻居

{

if(iChild == 3)

{

if(GetLODMatrix(iNeighborX , iNeighborZ) == 1) //邻居层次和它是否相同

{

m_Fan.AddVertex(*Vertex);

}

else //下邻居的层次比它小

{

//看它邻居的父亲节点,父亲节点是它邻居的右下的点

iNeighborParentX = iNeighborX + iEdgeOffset;

iNeighborParentZ = iNeighborZ + iEdgeOffset;

if(GetLODMatrix(iNeighborParentX ,iNeighborParentZ) == 1)

{

m_Fan.AddVertex(*Vertex);

}

else if(iChild == 4)

{

if(GetLODMatrix(iNeighborX , iNeighborZ) == 1) //邻居层次和它是否相同

{

m_Fan.AddVertex(*Vertex);

}

else //下邻居的层次比它小

{

//看它邻居的父亲节点,父亲节点是它邻居的左下的点

iNeighborParentX = iNeighborX - iEdgeOffset;

iNeighborParentZ = iNeighborZ + iEdgeOffset;

if(GetLODMatrix(iNeighborParentX ,iNeighborParentZ) == 1)

{

m_Fan.AddVertex(*Vertex);

}

else

{

m_Fan.AddVertex(*Vertex);

}

//LEFT-BOTTOM

Vertex = GetRealDate(iX - iEdgeOffset ,iZ + iEdgeOffset);

m_Fan.AddVertex(*Vertex);

//LEFT-MIDDLE

Vertex = GetRealDate(iX - iEdgeOffset,iZ );

iNeighborZ = iZ ;

iNeighborX = iX - (iEdgeLength - 1);

if(iChild == 2 || iChild == 4)

{

m_Fan.AddVertex(*Vertex);

}

else

{

if( iNeighborX > 0) //是否有左邻居

{

if(iChild == 1)

{

if(GetLODMatrix(iNeighborX , iNeighborZ) == 1) //邻居层次和它是否相同

{

m_Fan.AddVertex(*Vertex);

}

else //左邻居的层次比它小

{

//看它邻居的父亲节点,父亲节点是它邻居的左下的点

iNeighborParentX = iNeighborX - iEdgeOffset;

iNeighborParentZ = iNeighborZ + iEdgeOffset;

if(GetLODMatrix(iNeighborParentX ,iNeighborParentZ) == 1)

{

m_Fan.AddVertex(*Vertex);

}

else if(iChild == 3)

{

if(GetLODMatrix(iNeighborX , iNeighborZ) == 1 ) //邻居层次和它是否相同

{

m_Fan.AddVertex(*Vertex);

}

else //左邻居的层次比它小

{

//看它邻居的父亲节点,父亲节点是它邻居的左上的点

iNeighborParentX = iNeighborX - iEdgeOffset;

iNeighborParentZ = iNeighborZ - iEdgeOffset;

if(GetLODMatrix(iNeighborParentX ,iNeighborParentZ) == 1)

{

m_Fan.AddVertex(*Vertex);

}

else

{

m_Fan.AddVertex(*Vertex);

}

//LEFT-TOP

Vertex = GetRealDate(iX - iEdgeOffset ,iZ - iEdgeOffset);

m_Fan.AddVertex(*Vertex);

return AddFan();//把扇形添加到顶点缓冲中

}

RendLODNode函数整个代码挺多的，但如果你理解后，其实很简单的。

希望你能仔细阅读代码，这个RendLODNode只是完成往顶点管理器里添加数据，至于什么时候渲染数据，我在顶点管理器说了，渲染的情况。

四．相机剪裁地形

整个场景那么多多边形，如果不剪裁速度还是会很慢的。

图56

图56说明相机剪裁，画绿色圆圈的正方形PACTH（PATCH也就是LOD里面的一个正方形单元）都被剪裁，我在讲解生成划分矩阵的时候，添加了相机剪裁说明，只是没有给出代码，你可以看我给出划分矩阵代码，相机剪裁代码应该放在什么地方。看完后，你就会明白，实际上这也是和划分矩阵放在一起的递归过程，如果当前正方形PATCH被剪裁掉，我就把当前正方形划分矩阵设置为2。在渲染的时候忽略划分矩阵为2的，你可以回头看我给渲染LOD的函数代码，那里只处理了划分矩阵为1和0的情况。

相机剪裁我用的方法是：相机6个平面的视景体和当前正方形PACHT的AABB进行剪裁处理，如果AABB全都不在视景体里面就剪裁掉，部分在视景体里面，也是要继续递归的。

图57

AABB简介：AABB又称轴对齐有界箱。AABB是一个长方体，并且所有边都要和坐标轴平行。很多碰撞检测都用包含物体的最小AABB处理，虽然AABB进行碰撞不精确，但它速度快，容易实现。AABB可以由2种方式来定义，一种是2个顶点来定义，分别是X，Y ，Z都最大和都最小的两个顶点,图57 点A和点B。也可以用中心点和三个轴的长度来定义。我用的是第一种。

现在问题来了：

A．怎么获取视景体6个平面

B．有了6个平面怎么和AABB进行剪裁处理。

现在我来处理这个问题，我忘了D3D里面是否有获取视景体6个平面的函数，没有也没关系，我是自己写的。

其实我希望每个学3D的人能真正把3D流水线弄明白，我说的弄明白你要亲自写代码，然后运行，这样你才能深刻理解。所以我很推荐《3D游戏编程大师技巧》（它十几万代码，我都自己用C++重新了，当然也有40%代码是COPY它的，但60%是我自己理解后写的。）， 但它的3D变换过程和D3D稍微有些不同。D3D经过投影变换后，所有点的坐标都缩放到X[-1，1]，Y[-1，1]，Z[0，1]，而大师编程技巧里面没有这么做（你掌握了真正原理，其实怎么做都无所谓）投影矩阵没有加缩放因子，所以投影后的坐标范围X[-width , width]，Y[-height , height]，Z[nearZ , farZ]。其中width是投影面的宽度 , height投影面的高度 , nearZ、farZ分别为近远剪裁面距离。

现在我简单说下D3D 的 3D变换过程

物体的LOCAL坐标——>世界坐标——>相机坐标——>投影坐标——>屏幕坐标。

图58

如图58，可以看见世界坐标系下的视景体和投影后的视景体，对于一个世界坐标系下点W，经过相机坐标变换、投影坐标变换后才形成了投影坐标。

这里的过程我不知道有多少人真正理解的，实际上，从相机坐标变到投影坐标要有一个投影面，空间上所有的点最后都要落到上面，最后根据屏幕变换（记得D3D中SetViewport函数吗？这个函数设置屏幕视口矩阵）把投影坐标变换到屏幕坐标。这个投影变换可以是透视投影也可以是正交投影，一般我们用的是透视投影，也就是对物体有近大远小的感觉。而正交投影没有这种处理。（D3D中有建立透视投影和正交投影的函数，而且分别是建立左手坐标系和右手坐标系下的。我们一般都用左手坐标系，如果对坐标系定义不是很了解，对角度正负是逆时针还是顺时针分不清的，我希望看看《3D游戏数学基础：图形与游戏开发》，这本书是写3D数学基础的，写的很好。如果想要更高级的还有本《计算机图形学集合工具算法详解》这两本里面有代码的，所以我才说它好。如果你理论和实都很强并且英文还可以，看《Mathematics.for.3D.Game.Programming.and.

Computer.Graphics》。）我不能把整个数学基础都说了，是太大的工作量，希望大家谅解。继续说，当所有点都投影到投影面后，D3D中又进行了一次缩放，把 X，Y，Z缩放到分别为[-1，1][-1，1][0，1]区域，所以视景体经过投影变成了一个长方体。投影完成后，Z坐标是进行Z缓冲测试的，如果想了解怎么插值进行Z缓冲测试，看《3D游戏编程大师技巧》。

平面方程表达为Ax+By+cZ+D = 0，平面方程是根据一个方向L和空间中的一定点K来定义的，这个方向是垂直这个平面的，所以这个方向垂直平面上所有点。所以方向向量L（A，B，C）和（x – p , y – q , z - w）（其中（x，y，z）为平面上任意一个点，K（p,q,w）为定点）垂直，也就是正交。

所以平面方程为（A，B，C）*（x – p , y – q , z - w）= 0最后形式为Ax+By+cZ+D = 0 D = -pA-qB-wC。

D3D中我们知道视景体经过投影变成了一个长方体，范围为[-1，1][-1，1][0，1]，我们让法向量朝外，所以我们知道

left面为-x-1 = 0( x + 1 = 0 )

near面为 -z = 0

其他面同理

其实法向量向外和向里都无所谓，你做相机剪裁时，注意处理就可以了。

假设ViewProj为相机矩阵和投影矩阵的乘积

所以世界坐标下(x,y,z,1)任意一点经过这个矩阵变换后为(x',y',z',1)

(x,y,z,1)ViewProj = (x',y',z',1)''''''''''''''''''''''''''''''''''(1)

经过变换后的点的范围-1 <= x <= 1 , -1 <= y <= 1 ,0 <= z <= 1

假设平面位于世界坐标下的方程为ax + by + cz + d = 0

则有(x,y,z,1)( c ) = 0 '''''''''''''''''''''''''(2)

假设平面变换后的方程为a'x + b'y + c'z + d' = 0

则有(x',y',z',1)( c' ) = 0 ''''''''''''''''''''''''''(3)

(3)和(1)结合:

导出(x,y,z,1)ViewProj( c' ) = 0 '''''''''''''''''''''''''''''(4)

(4)和(2)导出

a a'

b b'

( c ) = ViewProj( c' )

d d'

所有平面的投影方程都知道(a',b',c',d'知道),就能求出a,b,c,d

上面的推导看不明白的，我希望自己把数学补习一下。想要做3D，想要做好3D，想要编好3D程序，想要做好3D技术，基础是很重要的，如果你想狗急跳墙，那你最后是黄粱一梦。所以你要付出太多艰辛和努力，如果你自己吃不了苦，那我可以说，你真的不适合学3D。

HRESULT VSGraphD3D::GetFrustrum(VSPlane *p)

{

// left plane

p[0].m_vcN.x = -(m_mViewProj._14 + m_mViewProj._11);

p[0].m_vcN.y = -(m_mViewProj._24 + m_mViewProj._21);

p[0].m_vcN.z = -(m_mViewProj._34 + m_mViewProj._31);

p[0].m_fD = -(m_mViewProj._44 + m_mViewProj._41);

// right plane

p[1].m_vcN.x = -(m_mViewProj._14 - m_mViewProj._11);

p[1].m_vcN.y = -(m_mViewProj._24 - m_mViewProj._21);

p[1].m_vcN.z = -(m_mViewProj._34 - m_mViewProj._31);

p[1].m_fD = -(m_mViewProj._44 - m_mViewProj._41);

// top plane

p[2].m_vcN.x = -(m_mViewProj._14 - m_mViewProj._12);

p[2].m_vcN.y = -(m_mViewProj._24 - m_mViewProj._22);

p[2].m_vcN.z = -(m_mViewProj._34 - m_mViewProj._32);

p[2].m_fD = -(m_mViewProj._44 - m_mViewProj._42);

// bottom plane

p[3].m_vcN.x = -(m_mViewProj._14 + m_mViewProj._12);

p[3].m_vcN.y = -(m_mViewProj._24 + m_mViewProj._22);

p[3].m_vcN.z = -(m_mViewProj._34 + m_mViewProj._32);

p[3].m_fD = -(m_mViewProj._44 + m_mViewProj._42);

// near plane

p[4].m_vcN.x = -m_mViewProj._13;

p[4].m_vcN.y = -m_mViewProj._23;

p[4].m_vcN.z = -m_mViewProj._33;

p[4].m_fD = -m_mViewProj._43;

// far plane

p[5].m_vcN.x = -(m_mViewProj._14 - m_mViewProj._13);

p[5].m_vcN.y = -(m_mViewProj._24 - m_mViewProj._23);

p[5].m_vcN.z = -(m_mViewProj._34 - m_mViewProj._33);

p[5].m_fD = -(m_mViewProj._44 - m_mViewProj._43);

for (int i=0;i<6;i++)

{

float fL = p[i].m_vcN.GetLength();

p[i].m_vcN /= fL;

p[i].m_fD /= fL;

}

return VS_OK;

}//GetFrustrum

最后我给出代码。这里用到了一个平面VSPlane类，我就不写出来了，这段代码很简单，我想你能看明白。

我要处理第2个问题了，怎么判断视景体和AABB剪裁。我想把这个问题说广点，也就是怎么判断封闭的多面体和AABB剪裁。

//AABB

class __declspec(dllexport) VSAabb

{

public:

VSVector vcMin, vcMax; // 最大,最小边界

VSVector vcCenter; // 中心

VSAabb(void) { ; }

inline void Set(const VSVector &_vcMin, const VSVector &_vcMax);

//从OBB构造AABB

void Construct(const VSObb *pObb);

//判断多面体和AABB位置关系(VSCULLED,VSCLIPPED,VSVISIBLE)

int Cull(const VSPlane *pPlanes, int nNumPlanes);

// 取得AABB的6个平面

void GetPlanes(VSPlane *pPlanes);

//判断线段是否在AABB内

bool Contains(const VSRay &Ray, float fL);

//是否与射线相交

//(算法P461)

bool Intersects(const VSRay &Ray, float *t);

//是否与线段相交

//(算法P461)

bool Intersects(const VSRay &Ray, float fL, float *t);

//是否与AABB相交

bool Intersects(const VSAabb &aabb);

//判断一点是否在AABB里

bool Intersects(const VSVector &vc0);

}; // class

/*----------------------------------------------------------------*/

这个是AABB类，里面有很多函数，我只介绍

//判断多面体和AABB位置关系(VSCULLED,VSCLIPPED,VSVISIBLE)

int Cull(const VSPlane *pPlanes, int nNumPlanes);

这个函数

（所有函数算法来自《计算机图形学几何工具算法详解释））

我们自己想象一个这个问题，现在有一个多面体S是封闭的，我要判断一个6面体（AABB）和它的位置关系，3种关系——被刨除、被剪裁、可以见。被刨除就是AABB完全在S外，被剪裁就是AABB和S相交，可以就是AABB完全在S内。

我这里介绍2个方法。记住我们的视景体法向量都是向外的。

第一种轴分离方法。

算法基本思想用多面体S的每个平面L，然后根据L的法向量3个分量，也就是相应X轴分量，Y轴分量，和Z轴分量，重新计算AABB和该平面L相关的最大最小点A、B，也就是按照平面法向量方向重新计算。因为AABB边界和坐标轴垂直，所以用轴分离方法很容易求A、B。

图59

看图59，AABB在兰色坐标轴下的最大最小点为红色的MAX和MIN，而经过轴分离后，按照平面L的法向量N方向重新计算后的最大最小点，为绿色的MAX和MIN。

这样求完最大最小点，判断平面和AABB的关系，只要AABB在任意一个平面之外，那么AABB被刨除，也就是MIN和平面做点积，如果大于0，就被刨除。如果MIN小于0。MAX大于0，则被剪裁，如果这些都不是，那么一定在里面了，可见的。

int VSAabb::Cull(const VSPlane *pPlanes, int nNumPlanes)

{

VSVector vcMin, vcMax;

bool bIntersects = false;

//轴分离求，MIN 和MAX

for (int i=0; i<nNumPlanes; i++)

{

// x

if (pPlanes[i].m_vcN.x >= 0.0f)

{

vcMin.x = this->vcMin.x;

vcMax.x = this->vcMax.x;

}

else

{

vcMin.x = this->vcMax.x;

vcMax.x = this->vcMin.x;

}

// y

if (pPlanes[i].m_vcN.y >= 0.0f)

{

vcMin.y = this->vcMin.y;

vcMax.y = this->vcMax.y;

}

else {

vcMin.y = this->vcMax.y;

vcMax.y = this->vcMin.y;

}

// z

if (pPlanes[i].m_vcN.z >= 0.0f)

{

vcMin.z = this->vcMin.z;

vcMax.z = this->vcMax.z;

}

else

{

vcMin.z = this->vcMax.z;

vcMax.z = this->vcMin.z;

}

//如果MIN和平面点积大于0，则刨除，并且返回

if ( ((pPlanes[i].m_vcN*vcMin) + pPlanes[i].m_fD) > 0.0f)

return VSCULLED;

//否则如果MAX和平面点积大于0，则剪裁

if ( ((pPlanes[i].m_vcN*vcMax) + pPlanes[i].m_fD) >= 0.0f)

bIntersects = true;

} // for

//如果没有剪裁，则可见。

if (bIntersects) return VSCLIPPED;

return VSVISIBLE;

} // Cull

第二种方法

第二种方法，在世面上很常见，也用的最多的，但它只判断被刨除和不被刨除2种关系。它的基本思想是用每个平面L和AABB每个平面做测试，AABB的所有平面和L面点乘都大于0，那么AABB被刨除。如果这些面都通过测试，则表示没有被刨除。

这个代码我就不给了，因为很常见。

这个剪裁方法都介绍完了。下面介绍怎么求地形正方形PATCH的AABB，由于地形初始完成后，每个正方形PACHT都已经确定（除非你想动态改变地形），所以它的AABB也确定了。

这里我们在弄一个矩阵，它的数据类型是AABB，先求边长为2的，正方形AABB，然后在求它上一个层次的AABB，迭代这个过程，最后求出最大的正方形AABB。算法过程和求DH矩阵很类似。

//求AABB矩阵

iEdgeLength = 3;//还是用顶点个数来表示的。最小边长为2，要用连接3个//顶点连接。

while(iEdgeLength <= m_nSize)

{

int iEdgeOffset= ( iEdgeLength-1 )>>1;

int iChildOffset= ( iEdgeLength-1 )>>2;

for( int z = iEdgeOffset; z < m_nSize; z +=( iEdgeLength-1 ) )

{

for(int x = iEdgeOffset; x < m_nSize; x +=( iEdgeLength-1 ) )

{

if(iEdgeLength == 3)

{

int iHeight[9];

//MIDDLE

iHeight[0] = GetHeightDate( x,z );

//TOP-LEFT

iHeight[1] =GetHeightDate(x-iEdgeOffset, z-iEdgeOffset );

//TOP-MIDDLE

iHeight[2] = GetHeightDate( x,z-iEdgeOffset );

//TOP-RIGHT

iHeight[3] =GetHeightDate(x+iEdgeOffset,z-iEdgeOffset );

//RIGHT-MIDDLE

iHeight[4] = GetHeightDate( x+iEdgeOffset, z );

//BOTTOM-RIGHT

iHeight[5]=GetHeightDate(x+iEdgeOffset,z+iEdgeOffset ) ;

//BOTTOM-MIDDLE

iHeight[6] = GetHeightDate( x,z+iEdgeOffset );

//BOTTOM-LEFT

iHeight[7] =GetHeightDate(x-iEdgeOffset,z+iEdgeOffset );

//LEFT-MIDDTL

iHeight[8] = GetHeightDate( x-iEdgeOffset, z);

int iHeightMAX = iHeight[0];

int iHeightMin = iHeight[0];

for( int i = 1 ; i < 9 ; i++)

{

if(iHeightMAX < iHeight[i])

iHeightMAX = iHeight[i];

if(iHeightMin > iHeight[i])

iHeightMin = iHeight[i];

}

VSVERTEX *Vertex = NULL;

Vertex = GetRealDate(x,z);

float iEdgeSize = (iEdgeLength - 1) * m_fWidthRatio;

VSVector vcMin, vcMax;

vcMin.x = Vertex->position.x - iEdgeSize;

vcMin.y = iHeightMin * m_fHeightRatio;

vcMin.z = Vertex->position.z - iEdgeSize;

vcMax.x = Vertex->position.x + iEdgeSize;

vcMax.y = iHeightMAX * m_fHeightRatio;

vcMax.z = Vertex->position.z + iEdgeSize;

VSAabb Aabb;

Aabb.Set(vcMin,vcMax);

SetAABBMatrix(x,z,Aabb);

}

else

{

//LEFT-TOP CHILD 1

VSAabb * pAabb = GetAABBMatrix(x - iChildOffset,z - iChildOffset);

float fHeightMax = pAabb->vcMax.y;

float fHeightMin = pAabb->vcMin.y;

//RIGHT-TOP CHILD 2

pAabb =GetAABBMatrix(x + iChildOffset,z - iChildOffset);

if(fHeightMax < pAabb->vcMax.y)

fHeightMax = pAabb->vcMax.y;

if(fHeightMin > pAabb->vcMin.y)

fHeightMin = pAabb->vcMin.y;

//RIGHT-BOTTOM CHILD 3

pAabb =GetAABBMatrix(x+ iChildOffset,z + iChildOffset);

if(fHeightMax < pAabb->vcMax.y)

fHeightMax = pAabb->vcMax.y;

if(fHeightMin > pAabb->vcMin.y)

fHeightMin = pAabb->vcMin.y;

//LEFT-BOTTOM

pAabb= GetAABBMatrix(x - iChildOffset,z + iChildOffset);

if(fHeightMax < pAabb->vcMax.y)

fHeightMax = pAabb->vcMax.y;

if(fHeightMin > pAabb->vcMin.y)

fHeightMin = pAabb->vcMin.y;

VSVERTEX *Vertex = NULL;

Vertex = GetRealDate(x,z);

float iEdgeSize = (iEdgeLength - 1) * m_fWidthRatio;

VSVector vcMin, vcMax;

vcMin.x = Vertex->position.x - iEdgeSize;

vcMin.y = fHeightMin;

vcMin.z = Vertex->position.z - iEdgeSize;

vcMax.x = Vertex->position.x + iEdgeSize;

vcMax.y = fHeightMax;

vcMax.z = Vertex->position.z + iEdgeSize;

VSAabb Aabb;

Aabb.Set(vcMin,vcMax);

SetAABBMatrix(x,z,Aabb);

}

iEdgeLength= ( iEdgeLength<<1 )-1;

}

然后在计算划分矩阵，相机剪裁的地方写上下面代码。

VSAabb *pAabb = GetAABBMatrix(iX,iZ);;

if(pAabb->Cull(m_pPlanes,6) == VSCULLED)

{

SetLODMatrix(iX,iZ ,2);

}else

{

…………..

}

五．天空盒

写完前面的部分，再写这部分已经相隔了好几天了。为添加了无限地形，添加树木，添加阴影体，花了很长时间，我发现渲染阴影体十分耗费时间，尤其是复杂的物体，即使提前计算也不行。后面讲到的时候我会进一部说明，我遇到的问题。总之如果你要做一个至少和我一样的地形，希望你遇到问题时，我的资料里可以找到解决办法。

渲染天空比较简单而且常用的方法就是用天空盒和天空球，这里我不想介绍天空球了，《Visual c++ Direct9 3D游戏开发引导》和《FOCUS ON 3D TERRAIN》里面有整个详细算法。相对渲染天空盒要容易，而且快。至于动态的天空怎么做，我没有仔细想过，但用天空球改变下纹理坐标就很容易实现，对于天空盒改变纹理坐标实现动态天空好象不是那么容易。

废话少说，我将详细介绍天空盒整个实现过程。

图60

看图60，天空盒只不过是一个6个面正方形，中心就是视点。上下左右前后分别贴上天空纹理后，基本天空盒就制作完成。当然还有些细节，一会再说。

TopTexture

BackTexture LeftTexture FrontTexture RightTexture

BottomTexture

上面就是天空盒的6个纹理，它们可以连接的，不要以为中间长条图片是一个图片，它是4个纹理图片。至于怎么制作天空盒的6个纹理，也就是最重要的怎么能让生成6个纹理可以拼接起来，我也不知道，至于作图软件怎么做，我也没有用过。希望高手能指点。

生成天空盒，注意的就是所有面是朝向里面的，也就是说你站在中心点，你无论看哪个三角形面，都是顺时针的（因为D3D默认顺时针可见，你也可以弄成逆时针的，设置D3D逆时针可见）

float fHlafSize = fSize / 2.0f;

m_TopVer[0].position = D3DXVECTOR3(-fHlafSize,fHlafSize,-fHlafSize);

m_TopVer[1].position = D3DXVECTOR3(fHlafSize,fHlafSize,-fHlafSize);

m_TopVer[2].position = D3DXVECTOR3(fHlafSize,fHlafSize,fHlafSize);

m_TopVer[3].position = D3DXVECTOR3(-fHlafSize,fHlafSize,fHlafSize);

m_TopVer[0].normal =D3DXVECTOR3(0.0f,-1.0f,0.0f);

m_TopVer[1].normal =D3DXVECTOR3(0.0f,-1.0f,0.0f);

m_TopVer[2].normal =D3DXVECTOR3(0.0f,-1.0f,0.0f);

m_TopVer[3].normal =D3DXVECTOR3(0.0f,-1.0f,0.0f);

m_BottomVer[0].position=D3DXVECTOR3(-fHlafSize,-fHlafSize,fHlafSize);

m_BottomVer[1].position= D3DXVECTOR3(fHlafSize,-fHlafSize,fHlafSize);

m_BottomVer[2].position=D3DXVECTOR3(fHlafSize,-fHlafSize,-fHlafSize);

m_BottomVer[3].position=D3DXVECTOR3(-fHlafSize,-fHlafSize,-fHlafSize);

m_BottomVer[0].normal =D3DXVECTOR3(0.0f,1.0f,0.0f);

m_BottomVer[1].normal =D3DXVECTOR3(0.0f,1.0f,0.0f);

m_BottomVer[2].normal =D3DXVECTOR3(0.0f,1.0f,0.0f);

m_BottomVer[3].normal =D3DXVECTOR3(0.0f,1.0f,0.0f);

m_LeftVer[0].position = D3DXVECTOR3(-fHlafSize,fHlafSize,-fHlafSize);

m_LeftVer[1].position = D3DXVECTOR3(-fHlafSize,fHlafSize,fHlafSize);

m_LeftVer[2].position = D3DXVECTOR3(-fHlafSize,-fHlafSize,fHlafSize);

m_LeftVer[3].position = D3DXVECTOR3(-fHlafSize,-fHlafSize,-fHlafSize);

m_LeftVer[0].normal =D3DXVECTOR3(1.0f,0.0f,0.0f);

m_LeftVer[1].normal =D3DXVECTOR3(1.0f,0.0f,0.0f);

m_LeftVer[2].normal =D3DXVECTOR3(1.0f,0.0f,0.0f);

m_LeftVer[3].normal =D3DXVECTOR3(1.0f,0.0f,0.0f);

m_RightVer[0].position = D3DXVECTOR3(fHlafSize,fHlafSize,fHlafSize);

m_RightVer[1].position = D3DXVECTOR3(fHlafSize,fHlafSize,-fHlafSize);

m_RightVer[2].position = D3DXVECTOR3(fHlafSize,-fHlafSize,-fHlafSize);

m_RightVer[3].position = D3DXVECTOR3(fHlafSize,-fHlafSize,fHlafSize);

m_RightVer[0].normal =D3DXVECTOR3(-1.0f,0.0f,0.0f);

m_RightVer[1].normal =D3DXVECTOR3(-1.0f,0.0f,0.0f);

m_RightVer[2].normal =D3DXVECTOR3(-1.0f,0.0f,0.0f);

m_RightVer[3].normal =D3DXVECTOR3(-1.0f,0.0f,0.0f);

m_FrontVer[0].position = D3DXVECTOR3(-fHlafSize,fHlafSize,fHlafSize);

m_FrontVer[1].position = D3DXVECTOR3(fHlafSize,fHlafSize,fHlafSize);

m_FrontVer[2].position = D3DXVECTOR3(fHlafSize,-fHlafSize,fHlafSize);

m_FrontVer[3].position = D3DXVECTOR3(-fHlafSize,-fHlafSize,fHlafSize);

m_FrontVer[0].normal =D3DXVECTOR3(0.0f,0.0f,-1.0f);

m_FrontVer[1].normal =D3DXVECTOR3(0.0f,0.0f,-1.0f);

m_FrontVer[2].normal =D3DXVECTOR3(0.0f,0.0f,-1.0f);

m_FrontVer[3].normal =D3DXVECTOR3(0.0f,0.0f,-1.0f);

m_BackVer[0].position = D3DXVECTOR3(fHlafSize,fHlafSize,-fHlafSize);

m_BackVer[1].position = D3DXVECTOR3(-fHlafSize,fHlafSize,-fHlafSize);

m_BackVer[2].position = D3DXVECTOR3(-fHlafSize,-fHlafSize,-fHlafSize);

m_BackVer[3].position = D3DXVECTOR3(fHlafSize,-fHlafSize,-fHlafSize);

m_BackVer[0].normal =D3DXVECTOR3(0.0f,0.0f,1.0f);

m_BackVer[1].normal =D3DXVECTOR3(0.0f,0.0f,1.0f);

m_BackVer[2].normal =D3DXVECTOR3(0.0f,0.0f,1.0f);

m_BackVer[3].normal =D3DXVECTOR3(0.0f,0.0f,1.0f);

顶点设置完毕。

WORD SkyIndex[6] =

{

0,1,3,

2,3,1

};

设置索引，我设置的是顺时针可见。

下面说下纹理坐标，按照普通方法设置纹理坐标成（0 0）( 1 0 ) (1 1 ) ( 0 1 )设置时，你会发现渲染天空盒时，在边界处没有拼接上，出现了一个细线。出现这个问题的原因，是因为D3D纹理影射本身的原因。

D3D纹理影射函数为：

Tx =（U * Mx）- 0.5

Ty = (V * My)) – 0.5

U，V为用户使用的纹理坐标 范围为0 ——1，Mx,My为纹理宽度和高度

如果读过《3D游戏编程大师技巧》就知道，纹理影射需要的纹理坐标是整数，D3D为了得到整数，用了一个小变换，就是减去0.5。所以如果你想让你天空盒拼接完美，就要把这0。5在加回去。

我们现在把（0 0）( 1 0 ) (1 1 ) ( 0 1 )坐标带进去你就会发现最后结果为-0.5或者为Mx – 0.5,My – 0.5。为了真正取到 0 和 Mx 、My要做下调整。

也就是说当Tx = 0时U = 0.5 / Mx Ty = 0时 V = 0.5 / My

Tx = Mx时 U = 1 – 0.5 / Mx Ty = My 时 V = 1 – 0.5/My

m_TopVer[0].texture=D3DXVECTOR2(0.5f/Texture->nWidth,0.5f/Texture->nHeight);

m_TopVer[1].texture=D3DXVECTOR2(1.0f-0.5f/Texture->nWidth,0.5f/Texture->nHeight);

m_TopVer[2].texture=D3DXVECTOR2(1.0f-0.5f/Texture->nWidth,1.0f-0.5f/Texture->nHeight);

m_TopVer[3].texture=D3DXVECTOR2(0.5f/Texture->nWidth,1.0f-0.5f/Texture->nHeight);

把所有顶点都这么设置就可以了。

因为天空盒不可能是无限的，移动相机有可能走出天空盒，我们要始终让视点位于天空盒中间，这样就好象天空是无限的。

开始时，我们把相机设置到天空盒中间，为了保持相机始终位于中间，也就是说，无论怎么移动，保持相机和天空盒的相对距离是不变的。

图61

我把这个例子简单化，可以模拟成，相机和物体A相对距离不变，也就是相机和A的两点间的距离。大家都知道A经过相机变换后，从世界坐标变成了相机坐标，这个过程经历了平移和旋转2个过程。平移量分别是相机位置的3个分量的负值。如果我们不做平移变换，只做旋转就可以保证相机和物体A相对距离不变。

这个过程你仔细想下，旋转只是改变方向，无论你怎么用旋转矩阵变换A，A和相机距离是不变的，而改变相对距离的只能是平移。我们不用平移变换物体A，所以相机和物体A相对距离不变。

这里有2个方法渲染物体A，一个是在渲染物体A时，重新设置相机矩阵，把原来相机矩阵平移分量拿掉。第二个是还用原来的相机矩阵，因为你已经平移一次，这次还要平移回去。这两个方法那个都可以，相对来讲第一个比较好。

第一个很简单，只要把矩阵的_41,_42,_43的分量设置为0，就可以了。

第二个方法虽然麻烦，但毕竟让大家看看怎么回事。

Delta.x = vcCamPos.x;

Delta.y = vcCamPos.y;

Delta.z = vcCamPos.z;

for(int i = 0 ; i < 4 ; i++)

{

m_TopTempVer[i] = m_TopVer[i].position + Delta;

m_BottomTempVer[i] = m_BottomVer[i].position + Delta;

m_LeftTempVer[i] = m_LeftVer[i].position + Delta;

。。。。。。。。。。。。。。。。。

}

第2个方法还要设置一个临时缓冲区，每次都要把顶点平移回去，然后渲染临时缓冲区。这里

Delta.x = vcCamPos.x;

Delta.y = vcCamPos.y;

Delta.z = vcCamPos.z;

绝对不是

Delta.x = - vcCamPos.x;

Delta.y = - vcCamPos.y;

Delta.z = -vcCamPos.z;

没有想明白的，好好复习流水线过程。

最后是渲染天空盒，我们的天空盒是有大小的，所以我们渲染时禁止Z缓冲写入，否则渲染时，天空盒Z大小都写了进去，导致超出天空盒大小的场景渲染不了，而且还要最先渲染，否则因为你禁止Z缓冲写入，先渲染场景再渲染天空盒，天空盒把整个场景覆盖了。

六．简单海水

我这里只用简单的方法模拟了海水，复杂的方法要涉及到很多计算。这个简单的确实很简单，涉及的计算少，而且容易实现，效果也不错。

实际上就弄一个正方形，然后加入一个海水的纹理，海水纹理要用WRAP贴图，否则海平面很大，被拉神了可不好看了，当然还要用半透明APHLA。流动的函数就是让纹理坐标每次更新就可以了。

设置开始纹理坐标

m_Vertex[0].texture.x = 0.0f;

m_Vertex[1].texture.x = (m_fWidth*1.0f)/Texture->nWidth;

m_Vertex[2].texture.x = (m_fWidth*1.0f)/Texture->nWidth;

m_Vertex[3].texture.x = 0.0f;

m_Vertex[0].texture.y = 0.0f;

m_Vertex[1].texture.y = 0.0f;

m_Vertex[2].texture.y = (m_fHeight*1.0f)/Texture->nHeight;

m_Vertex[3].texture.y = (m_fHeight*1.0f)/Texture->nHeight;

更新纹理坐标，这里只更新了y坐标也就是说让它一个方向流动，如果y 到头了还要循环回去。Elapsed变量是每次循环花费的时间。为了平衡不同机器的快慢，都要用时间来计算，可以达到同步。

void VSEffectWater::UpDate(DWORD Elapsed)

{

float fSpeed = Elapsed/1000.0f;

m_Vertex[0].texture.y = m_Vertex[0].texture.y + fSpeed;

m_Vertex[1].texture.y = m_Vertex[1].texture.y + fSpeed;

m_Vertex[2].texture.y = m_Vertex[2].texture.y + fSpeed;

m_Vertex[3].texture.y = m_Vertex[3].texture.y + fSpeed;

if(m_Vertex[0].texture.y > 1.1f)

{

m_Vertex[0].texture.y = 0.1f;

m_Vertex[1].texture.y = 0.1f;

m_Vertex[2].texture.y = (m_fHeight*1.0f)/ Texture->nHeight;

m_Vertex[3].texture.y = m_Vertex[2].texture.y;

}

七．广告牌

广告牌我想大家都再熟悉不过了，但我还是要详细说下。

广告牌有2种，一种是完全朝向相机的广告牌，广告牌顶点X、Y、Z 3个向量都要旋转。另一种是只是广告牌顶点某二个向量旋转，有一个向量不旋转，最常用的就是X，Z向量绕Y轴旋转，Y向量不旋转。

这里说的“完全朝向”指的是广告牌面法向量和相机Z方向平行，也可以说相机Z方向和广告牌面垂直，并且可见面朝向相机。

这2个方法，不同就是在旋转上的差别，如果你想让它永远朝向相机，就用第一种，例如粒子（如果你不用D3D的点精灵格式渲染）。第2个方法渲染实例就是树，草木之类。

图62

图63

如图62是第一种方法，图63是第2种方法。同一个角度，用墙纹理渲染的网格，是为了衬托一下。

闲话少说，我现在来详细介绍下广告牌的实现过程。

图64

如图64，开始时，你需要这样的一个矩形，也就是2个三角形索引为：013，231。注意次序，只渲染顺时针的。

然后设置顶点坐标，我引擎里面所有的广告牌都是正方形的，，也就是给用户一个接口让他输入边长的一半做为参数。

m_Pos[0].position.x = -fHalfSize;

m_Pos[0].position.y = fHalfSize;

m_Pos[0].position.z = 0.0f;

m_Pos[0].normal.x = 0.0f;

m_Pos[0].normal.y = 0.0f;

m_Pos[0].normal.z = -1.0f;

m_Pos[0].texture.x = 0.0f;

m_Pos[0].texture.y = 0.0f;

m_Pos[1].position.x = fHalfSize;

m_Pos[1].position.y = fHalfSize;

m_Pos[1].position.z = 0.0f;

m_Pos[1].normal.x = 0.0f;

m_Pos[1].normal.y = 0.0f;

m_Pos[1].normal.z = -1.0f;

m_Pos[1].texture.x = 1.0f;

m_Pos[1].texture.y = 0.0f;

m_Pos[2].position.x = fHalfSize;

m_Pos[2].position.y = -fHalfSize;

m_Pos[2].position.z = 0.0f;

m_Pos[2].normal.x = 0.0f;

m_Pos[2].normal.y = 0.0f;

m_Pos[2].normal.z = -1.0f;

m_Pos[2].texture.x = 1.0f;

m_Pos[2].texture.y = 1.0f;

m_Pos[3].position.x = -fHalfSize;

m_Pos[3].position.y = -fHalfSize;

m_Pos[3].position.z = 0.0f;

m_Pos[3].normal.x = 0.0f;

m_Pos[3].normal.y = 0.0f;

m_Pos[3].normal.z = -1.0f;

m_Pos[3].texture.x = 0.0f;

m_Pos[3].texture.y = 1.0f;

我把广告牌的中心设置为局部LOCAL坐标原点，然后用平移变换，变换到世界坐标下。

假设现在坐标变换距阵为M(world)、M(view_translation)、M(view_rot)、M(view)

其中M(world)为广告牌世界距阵，M(view)为相机距阵，为M(view_translation) 相机距阵的平移距阵部分，M(view_rot)为相机距阵的旋转距阵部分。

M(view) = M(view_translation) * M(view_rot)

相机距阵是先平移然后再旋转，不是先旋转再平移。这两个过程是不同的。旋转是在当前坐标系下，绕当前坐标轴旋转。

图65旋转再平移

图66平移再旋转

如果不知道距阵各个分量那些承担旋转，平移，和缩放的，希望大家自己找资料复习一下。

原始整个变换过程为：

T(view) = T (local) * M(world)* M(view_translation) * M(view_rot)

为了让广告牌面向相机，就要旋转广告牌顶点，实际上这个是相机变换旋转部分的逆变换，所有旋转角度都是和相机相反的。

M(view_rot)的逆距阵* M(view_rot) = E（单位距阵）

新的变换过程

T(view) = T (local) * M(view_rot)的逆距阵* M(world)* M(view_translation) * M(view_rot)

对于如何求逆距阵就是线性代数的知识了，我不想说了。但相机距阵的旋转部分都是可逆距阵，并且是正交距阵，所以M(view_rot)的逆距阵 = M(view_rot)转置。

线性代数是高等数学中必学的，也是考研必考的，一般上过大学理工科都应该学过。我不想再过多介绍了。

对与第2种广告牌，只是让y向量不变，X、Z向量绕Y轴旋转。我做一个假设，对于第一种广告牌，假设相机始终只绕Y轴旋转，这样广告牌就变成了第2种广告牌，也就是说，相机坐标旋转时，y向量不变，X、Z向量绕Y轴旋转。

如果只进行按Y轴旋转，那么只需要假设相机矩阵A的Y分量是(0,1,0)就可以了。

A逆 * A = E

x1,y1,z1

A=( x2,y2,z2 )

x3,y3,z3

a1,a2,a3

A逆=( b1,b2,b3 )

c1,c2,c3

因为A为正交矩阵，从列看，也就是列向量为单位向量，且两两正交，也就是点积为0

所以A逆也为正交矩阵，从行看。

其实正交矩阵从行从列看都无所谓，只不过为了和相机矩阵列向量结合，讲解方便

为了只让广告牌只绕Y轴旋转，我们假设相机矩阵Y轴向量始终为(0,1,0),也就说相机矩阵Y分量向上，这样求出的逆矩阵也只能绕Y轴旋转了。

但我们不用在重新设置相机矩阵，只需要修改逆矩阵就可以。

假设

x1,0,z1

A=( x2,1,z2 )

x3,0,z3

这样改完后，因为X列向量和Z列向量是按照严格相机矩阵过程求得。

相机距阵实际求得过程为假设Y向上(0,1,0),然后求视点和观察点向量E，它们做叉积，求得右向量R，然后在用右向量R和E求得上方向向量。

修改后的A，我们这里没有在继续求上方向，所以不能保证A为正交矩阵

a1,a2,a3

A逆=( 0,1,0 )

c1,c2,c3

void VSBillboard::Draw(bool bAxisY)

{

D3DXMATRIX Temp;

//取相机旋转部分逆距阵

m_Graph->GetInverViewTransform((VSMatrix*)&Temp);

//设置平移距阵

Temp._41 = m_CentralPos.x;

Temp._42 = m_CentralPos.y;

Temp._43 = m_CentralPos.z;

//如果按照Y轴旋转

if(bAxisY)

{

Temp._21 = 0.0f;

Temp._22 = 1.0f;

Temp._23 = 0.0f;

}

把Temp设置成世界变换矩阵

渲染

}

八．光晕

告诉自己加把劲，快写完了，确实没多少。现在游戏里面好象很少有带光晕，只有前几年的游戏里面带这个。不管怎么样，既然我会了，我就要把它实现告诉大家。

图65

我第一见到光晕时，我在想它是怎么实现的，给我第一个感觉，是用太阳位置和视点连线，在这条直线上放些光晕的光圈，这些光圈用APLHA广告牌来实现。图66说明这个。

图66

这个方法确实能实现，但这里有个问题，太阳要设置多远，太阳设置近了，移动相机很容易发现这个太阳离我们很近，不真实。如果太阳设置很远，用广告牌渲染的光圈，要设置多么大，设置在直线什么位置。

我现在举个例子，简单的例子。

现在相机位置为（0，0，0），而太阳位置为（100000，0，0），100000已经很远了。现在问题，你要把太阳广告牌设置多大，设置小了，投影到屏幕上时，我们根本就看不见。100000这个距离，如果要看见太阳，要广告牌要设置的很大。当然你可以控制你的引擎，所有的单位都很小，比如一个场景，可能最大范围就为10左右，相机移动单位为零点零几，或者零点零零几。这样你的太阳，设置到1000的距离左右就可以了。但还有个问题，你渲染单位都很小时，你的近剪裁面要设置的很小，比如0。1，或者0。01。当近剪裁面设置很小的时候，渲染远出的问题会不正常，这个问题是D3D的问题。

所以我们用上面的方法，存在着很多问题。

但仔细想想，之所以出现这些问题，是因为太阳离我们太远，我们控制太阳和光圈的大小很成问题，当然不是不能实现，你可以设置的很大。好，现在换个角度，我们在2维的空间来思考，我们把太阳位置投影到屏幕上，在这个2维空间中，做刚才的想法。

图67

现在太阳已经投影到屏幕上了，我们都用屏幕坐标来实现这个过程，连接太阳和屏幕中心，然后在它们连线上用2D渲染ALPHA光圈，就这么简单。

为了更加精确模拟光晕，我们还要模拟光晕的强度。也就是说，太阳投影在屏幕范围了光晕的强度最强，当移出屏幕时，逐渐衰减，最后消失。

图68

记住，我们把太阳投影到屏幕上后，所有的操作都是在2D屏幕坐标上进行的。我们定义衰减区域的宽度为fIntensityBorder。如果太阳落在屏幕上，强度就为1。如果太阳落在衰减区域，根据太阳屏幕边界的距离来判断Away，也就是说，太阳越靠近屏幕强度越大，越靠近衰减区域红色线，强度越小。

LightPos.x，LightPos.y为太阳投影后的坐标

//计算X方向和边界距离

int iAwayX;

if(LightPos.x < 0)

{

iAwayX = -LightPos.x;

}

Else

{

If(LightPos.x > iScreenWidth)

{

iAwayX = LightPos.x-iScreenWidth

}

else

{

iAwayX = 0;

}

//计算Y方向和边界距离

int iAwayY;

if(LightPos.y < 0)

{

iAwayY = -LightPos.y;

}

Else

{

If(LightPos.y > iScreenHiehg)

{

iAwayY = LightPos.x-iScreenHight

}

else

{

iAwayY = 0;

}

//取最大的

float fAway = float((iAwayX > iAwayY) ? iAwayX : iAwayY);

if (fAway > m_fIntensityBorder) return ;

fRealIntensity = 1.0f - (fAway / m_fIntensityBorder);

现在重点是怎么求出太阳投影后的屏幕坐标，我们一般给的太阳坐标都是世界坐标下的点，要经过相机变换、投影变换、视口变换、最后才成为屏幕坐标。

相机变换矩阵和投影变换矩阵很容易得到，关键是视口变换。经过相机变换、投影变换后，所以的点都被投影到X[-1，1]、Y[-1，1]、Z[0，1]的范围，但我们屏幕坐标范围是X[0，width]Y[0,height]，并且我们屏幕Y的正方向是向下的，而投影坐标系Y正方向是向上的。

图69

投影坐标很容易求，用分别和变换矩阵和投影变换矩阵相乘，记住相乘后要除以W分量。

（x,y,z 1）* ViewPro = ( X,Y,Z W)

(X/W, Y/W, Z/W ,1)

把投影坐标变到屏幕坐标，要经过平移和缩放两个过程，还要把Y轴方向颠倒下。我先把它们都从-1——1平移到0——2，然后分别乘以widht/2,height/2,就可以了

//视口大小

dwWidth = m_dD3Dvp[m_nStage].Width,

dwHeight = m_dD3Dvp[m_nStage].Height;

//视口大小一半

fClip_x = (float)(dwWidth >> 1);

fClip_y = (float)(dwHeight >> 1);

//投影坐标范围为[-1,1]要变成[0,2]并且屏幕坐标y方向向下,需要反转

pt.x = (LONG)( (1.0f + (fXp)) * fClip_x );

pt.y = (LONG)( ((fYp) - 1.0f ) * (-fClip_y) );

整个代码过程为

POINT VSGraphD3D::Transform3Dto2D(const VSVector &vcPoint,bool *bClip)

{

POINT pt;

float fClip_x, fClip_y;

float fXp, fYp, fZp,fWp;

DWORD dwWidth, dwHeight;

dwWidth = m_dD3Dvp[m_nStage].Width,

dwHeight = m_dD3Dvp[m_nStage].Height;

fClip_x = (float)(dwWidth >> 1);

fClip_y = (float)(dwHeight >> 1);

//变成投影坐标

fXp = (m_mViewProj._11*vcPoint.x) + (m_mViewProj._21*vcPoint.y)

+ (m_mViewProj._31*vcPoint.z) + m_mViewProj._41;

fYp = (m_mViewProj._12*vcPoint.x) + (m_mViewProj._22*vcPoint.y)

+ (m_mViewProj._32*vcPoint.z) + m_mViewProj._42;

fZp = (m_mView3D._13*vcPoint.x) + (m_mView3D._23*vcPoint.y)

+ (m_mView3D._33*vcPoint.z) + m_mView3D._43;

//如果被投影到后面，也就是Z为负的，就要剪裁掉。

if(fZp <= 0)

{

*bClip = true;

}

else

{

*bClip = false;

}

fWp = (m_mViewProj._14*vcPoint. x) + (m_mViewProj._24*vcPoint.y)

+ (m_mViewProj._34*vcPoint.z) + m_mViewProj._44;

float fWpInv = 1.0f / fWp;

//投影坐标范围为[-1,1]要变成[0,2]并且屏幕坐标y方向向下,需要反转

pt.x = (LONG)( (1.0f + (fXp * fWpInv)) * fClip_x );

pt.y = (LONG)( ((fYp * fWpInv) - 1.0f ) * (-fClip_y) );

return pt;

}

上面的过程应该很简单，如果对这个过程还是不明白，赶快3D基础要恶补下，记住如果你想走的更远基础很重要。现在我来说明光晕的详细过程。

首先，要用太阳的屏幕坐标和屏幕中心连接直线。

这条直线上的点可以用下面的方程表示

Point =CenterOfScreen + T(LightPos - CenterOfScreen)

T是个变量

这样我们只需要取T为0——1之间的值就可以设置光圈的位置，然后光圈的大小完全是2D上屏幕大小，大小和T你可以随意设置。

typedef struct FLARESPOT_TYPE

{

VS2DSurface m_FlareSurface; //用来渲染的2D表面类

float m_fSize; //大小

float m_fPos; //中心点位置，也就是上面方程//中变量T

VSCOLOR m_Color; //颜色

} FLARESPOT;

这个是我引擎中的光圈结构体

这里面有的m_Color，为了是让光圈可以任何颜色，渲染时用顶点漫反射颜色也参与ALPHA混合

m_pDevice->SetTextureStageState(0, D3DTSS_COLOROP,D3DTOP_MODULATE);

m_pDevice->SetTextureStageState(0,D3DTSS_ALPHAOP,D3DTOP_MODULATE);

现在我给出渲染的整个代码

//先求出Point =CenterOfScreen + T(LightPos - CenterOfScreen)方程里面的//LightPos – CenterOfScreen

int iCenterOfScreenX = iScreenWidth/2;

int iCenterOfScreenY = iScreenHeight/2;

int iDistanceX = iCenterOfScreenX - LightPos.x;

int iDistanceY = iCenterOfScreenY - LightPos.y;

//画光圈

for(UINT i = 0 ; i < m_uiNumIndex ; i++)

{

//用参数T求出真正屏幕位置

int iSpotCenterPosX = int(iCenterOfScreenX - (iDistanceX * m_pFlareSpot[i].m_fPos));

int iSpotCenterPosY = int(iCenterOfScreenY - (iDistanceY * m_pFlareSpot[i].m_fPos));

//求出画2D光圈左上角位置坐标（我引擎规定画2D表面用表面左上角//坐标）

int iSpotDrawPosX = iSpotCenterPosX - m_pFlareSpot[i].m_FlareSurface.GetWidth()/2;

int iSpotDrawPosY = iSpotCenterPosY - m_pFlareSpot[i].m_FlareSurface.GetHeight()/2;

//计算光圈强度

float fA = m_pFlareSpot[i].m_Color.fA * fRealIntensity;

if (fA > 1.0f) fA = 1.0f;

if (fA < 0.0f) fA = 0.0f;

//设置光圈颜色

m_pFlareSpot[i].

m_FlareSurface.SetColor(m_pFlareSpot[i].m_Color.fR,

m_pFlareSpot[i].m_Color.fG,

m_pFlareSpot[i].m_Color.fB,

fA);

//画光圈 m_pFlareSpot[i].m_FlareSurface.Draw(iSpotDrawPosX,iSpotDrawPosY);

}

//画太阳

m_Light.Draw(LightPos.x - m_Light.GetWidth()/2,LightPos.y - m_Light.GetHeight()/2);

这里我没有给出D3D中2D的实现过程，你可以用XYZRW顶点格式来渲染，我自己封装了一个2D表面类。这个很简单，我相信你也能实现的。

九．地形场景物体与BHV

不知道我讲的怎么样，我很尽力了，估计大家应该能看明白的，为了写这个，现在已经过了10天了，真希望我的努力没白费，大家帮我加加油。谈到这里，我很想说的是，中国游戏开发人员也应该有高手的，但为什么他们就不能写些书籍呢？介绍他们在游戏开发中，应用到技术和经验，毕竟中国人自己写的，而且还有项目经验，深刻理解了整个游戏开发过程，比没有开发经验，有些甚至根本就没有理解，生硬的翻译国外书籍的人要写好的多（对于那些翻译国外书的人，虽然有些书翻译的不好，但还是要谢谢他们，孜孜不倦的努力）。

继续讲了，这节的目的是在地形中添加物体，尽量多的物体。一但添加了物体，就要做至少2个工作，一个相机对物体的快速剪裁，另一个是碰撞测试。

这节我主要讲剪裁，碰撞我到后面和地形集中讲。

我先说静态物体剪裁，也是我地形里用的。对于成千上万的动态物体剪裁，我后面讲一个方法。

游戏中最大的好处是，大多数物体是静止的，对于静止的东西，我们能做很多预处理工作。

你想象下，地形中很多物体，如果每一个物体一个一个都要判断，是否在视线范围内，会花很多时间，游戏编程中有一个规则，如果处理它花费时间很多，还不如直接渲染它，不做任何处理。

我想介绍的就是用BHV（bounding hierarchical volumes）方法进行剪裁,BHV中文翻译为层次包围体。我在这里我想太详细介绍，其实很多空间划分技术都属于层次包围体，想要了解更多的，就看《3D 游戏编程大师技巧》里面介绍很详细。

我以前实现过物体上8叉树的BHV（剪裁单位为物体，做一个宇宙的飞机游戏，能用到的），多边形上的4叉树BHV（剪裁单位为多边形，准确说三角形，主要是地形剪裁三角形）。这两个都是为软件引擎做的，当时为了理解D3D流水线真正的原理，就做了个软件引擎，模拟真个D3D流水线。里面封装了可以剪裁三角形，我想D3D内部也有剪裁三角形这个功能。我们用D3D只能在物体级别上进行剪裁，很多三角形剪裁我们也可以控制，但相当麻烦，而且处理它很浪费时间，不如D3D帮我们处理（这里我指的是动态剪裁，不是象BSP那样可以剪裁三角形后，再渲染），如果你看过《3D游戏编程大师技巧》你就会知道，用相机剪裁三角形不是那么容易。

现在这个地形上要渲染的是物体，我们要剪裁的是物体，而且D3D中也只能剪裁物体，至于物体一部分在相机里面，一部分在相机外面，我们不做物体上剪裁，直接渲染它。物体上有些三角形不在相机里面，我们自己做三角形剪裁不如让D3D给我们剪裁方便。

图70

看图70，物体一部分在相机里面，一部分在相机外面。红色部分是D3D帮我们剪裁。如果我们不做任何剪裁算法，所有都直接渲染，D3D就会一个一个物体的三角形剪裁，速度很慢。

9．1 构造四叉树BHV

现在开始用四叉树BHV处理地形上物体。

图71

看图71，红色的是物体，地形上现在有些物体。

图72

计算当前所有物体最大包围盒（AABB）（这一步，要求所有物体的包围盒都知道，这个在你加载物体时，就要计算出来，我的引擎处理模型是。X文件，加载物体后计算包围盒，支持蒙皮骨骼动画，非蒙皮骨骼动画，非动画物体，而且骨骼动画支持骨骼包围盒，也就是骨骼包围盒碰撞，如果是多MESH的物体，还支持多MESH 包围盒，有时间我会结合代码和原理讲下，我的BOLG里面只讲了原理。）

图73

四叉树划分绿色包围盒，形成了四个包围盒，然后根据物体位置，划分物体，看物体属于哪个空间。这里可能物体和2包围盒个边界相交，我只根据物体位置来判断，物体位置就是一个点，点在2包围盒个边界上几率太小了，几乎可以忽略。

图74

重新计算每个分支物体的AABB。

图75

对每个AABB再进行划分。

图76

重新计算每个分支物体的AABB。

重复上面过程，直到分支物体小于某个数量时，我引擎规定如果分支物体数量小于5个就结束递归。

typedef struct PLANTMODEL_TYPE

{

VSModelD3D *m_pModel; //物体

VSVector m_Pos; //物体世界坐标

}PlantModel;

//节点结构

class QuatTree

{

public:

QuatTree();

~QuatTree();

vector<PlantModel> m_PlantModel; //物体列表

VSAabb m_Aabb; //节点AABB

QuatTree *Child[4]; //孩子

void Create(vector<PlantModel> &Plant,VSAabb & Aabb); //进行划分

};

void QuatTree::Create(vector<PlantModel> &Plant,VSAabb & Aabb)

{

//如果大于5 结束递归

if(Plant.size() > 5)

{

VSVector Max(-99999.0f,-99999.0f,-99999.0f);

VSVector Min(99999.0f,99999.0f,99999.0f);

//把物体加入到节点 m_PlantModel.insert(m_PlantModel.begin(),Plant.begin(),Plant.end());

//重新计算当前节点AABB

for(int i = 0 ; i< Plant.size(); i++)

{

VSAabb Aabb;

Plant[i].m_pModel->GetAABB(&Aabb);

if(Max.x < Aabb.vcMax.x)

Max.x = Aabb.vcMax.x;

if(Max.y < Aabb.vcMax.y)

Max.y = Aabb.vcMax.y;

if(Max.z < Aabb.vcMax.z)

Max.z = Aabb.vcMax.z;

if(Min.x > Aabb.vcMin.x)

Min.x = Aabb.vcMin.x;

if(Min.y > Aabb.vcMin.y)

Min.y = Aabb.vcMin.y;

if(Min.z > Aabb.vcMin.z)

Min.z = Aabb.vcMin.z;

}

m_Aabb.vcMin.x = Min.x;

m_Aabb.vcMin.y = Min.y;

m_Aabb.vcMin.z = Min.z;

m_Aabb.vcMax.x = Max.x;

m_Aabb.vcMax.y = Max.y;

m_Aabb.vcMax.z = Max.z;

m_Aabb.vcCenter.x = (Max.x - Min.x)/2;

m_Aabb.vcCenter.y = (Max.y - Min.y)/2;

m_Aabb.vcCenter.z = (Max.z - Min.z)/2;

//划分当前节点AABB，四等分

VSAabb AabbTemp[4];

int iNum[4]={0,0,0,0};

float HalfX ,HalfY,HalfZ;

HalfX = m_Aabb.vcMax.x - m_Aabb.vcMin.x;

HalfY = m_Aabb.vcMax.y - m_Aabb.vcMin.y;

HalfZ = m_Aabb.vcMax.z - m_Aabb.vcMin.z;

Min.x = m_Aabb.vcMin.x;

Min.y = m_Aabb.vcMin.y;

Min.z = m_Aabb.vcMin.z + HalfZ;

Max.x = m_Aabb.vcMax.x - HalfX;

Max.y = m_Aabb.vcMax.y;

Max.z = m_Aabb.vcMax.z;

AabbTemp[0].Set(Min,Max);

Min.x = m_Aabb.vcMin.x + HalfX;

Min.y = m_Aabb.vcMin.y;

Min.z = m_Aabb.vcMin.z + HalfZ;

Max.x = m_Aabb.vcMax.x;

Max.y = m_Aabb.vcMax.y;

Max.z = m_Aabb.vcMax.z;

AabbTemp[1].Set(Min,Max);

Min.x = m_Aabb.vcMin.x + HalfX;

Min.y = m_Aabb.vcMin.y;

Min.z = m_Aabb.vcMin.z;

Max.x = m_Aabb.vcMax.x;

Max.y = m_Aabb.vcMax.y;

Max.z = m_Aabb.vcMax.z - HalfZ;

AabbTemp[2].Set(Min,Max);

Min.x = m_Aabb.vcMin.x;

Min.y = m_Aabb.vcMin.y;

Min.z = m_Aabb.vcMin.z;

Max.x = m_Aabb.vcMax.x - HalfX;

Max.y = m_Aabb.vcMax.y;

Max.z = m_Aabb.vcMax.z - HalfZ;

AabbTemp[3].Set(Min,Max);

vector <PlantModel> PlantTemp[4];

//求出儿子节点

for(int j = 0 ; j < 4 ; j++)

{

for(int w = 0 ; w < Plant.size(); w++ )

{

//判断点是否在AABB里面（这个算法很简单，我不想介绍了）

if(AabbTemp[j].Intersects(Plant[w].m_Pos))

{

PlantTemp[j].push_back(Plant[w]);

iNum[j]++;

}

if(iNum[j])

{

Child[j] = new QuatTree();

Child[j]->Create(PlantTemp[j],AabbTemp[j]);

}

开始初始化时，这么写就可以了

VSAabb Aabb;

Aabb.Set(VSVector(-99999.0f,-99999.0f,-99999.0f),

VSVector(99999.0f,99999.0f,99999.0f));

m_pTreeRoot = new QuatTree();

m_pTreeRoot->Create(m_PlantModel,Aabb);

m_PlantModel 为所以物体的列表

对于动态物体剪裁，大家注意到没有，游戏任何动的物体都有一个活动范围，也就是说任何NPC不能象你控制的主角一样，到处走，它都有一个活动空间。所以游戏中你先对NPC活动空间剪裁，然后再处理这些动的NPC。如果你的NPC走动空间无限大，我想除了遍历没有别的方法。

9．2渲染四叉树BHV

如果我们已经构造完成了BHV，那么现在我们就要渲染它，渲染它没有什么特别的，就是用AABB和相机做剪裁，剪裁算法我前面介绍过了。

m_Visible是可见列表

void VSTerrainJungle::CullQuatNode(QuatTree *pNode)

{

if(!pNode)

return;

int flag = pNode->m_Aabb.Cull(m_pPlanes,6);

if( flag == VSCULLED)

return;

if( flag == VSVISIBLE)

m_Visible.insert(m_Visible.end(),pNode->m_PlantModel.begin(),

pNode->m_PlantModel.end());

int iEmptyChild = 0;

for(int i = 0 ; i < 4; i++)

{

if(!pNode->Child[i])

{

iEmptyChild++;

}

else

{

CullQuatNode(pNode->Child[i]);

}

//如果四个儿子节点都是空，物体和相机做剪裁判断

if(iEmptyChild == 4)

{

for(int j = 0 ; j < pNode->m_PlantModel.size() ; j++)

{

VSAabb Aabb ;

pNode->m_PlantModel[j].m_pModel->GetAABB(&Aabb);

if(Aabb.Cull(m_pPlanes,6) != VSCULLED)

m_Visible.push_back(pNode->m_PlantModel[j]);

}

我想代码已经描述的很清晰，不做太多解释。唯一要说的，如果你模型要用到ALPHA渲染，你还要把m_Visible列表里物体进行Z排序。要求出物体到相机的距离（用距离平方吧！不用开根号）。也可以用相机矩阵把所有物体变换到相机坐标下，再排序，效果一样，从效率来讲第一种好.

渲染ALPHA时，也可以用ALPHA测试，ALPHA测试和常用ALPHA有一个不同地方。ALPHA测试时，如果象素没有通过测试，颜色缓冲区（屏幕表面）和Z缓冲都不会被写入，而常用ALPHA测试颜色缓冲区（屏幕表面）和Z缓冲都都被写入，只不过颜色混合运算后还是原来的颜色，看起来颜色缓冲区（屏幕表面）还和以前一样。

十．阴影体

10．1介绍模板缓冲

今天再写最后一个，就是阴影体。要想了解阴影体，一定要了解D3D中模板缓冲区的工作原理。

D3D中有三个常用缓冲区，颜色缓冲区（屏幕表面），Z缓冲，模板缓冲，我希望大家能了解它们的用途，和对它们怎么操作。

我本来不想详细说模板，但为了让大家能更好了解阴影体还是说下吧，谁叫我这么善良了！嘿嘿。

当我们创建D3D设备时，要填写一个D3DPRESENT_PARAMETERS m_d3dpp这样的一个变量，然后用它来创建D3D设备。

我只说几个参数

后备缓冲个数，我设置1个，后备缓冲最后要换页，和前屏幕缓冲进行交换，这里的后备缓冲，也就是我们要渲染图形的缓冲，就是颜色缓冲。

m_d3dpp.BackBufferCount = 1;

设置后备缓冲格式，我设置成当前屏幕格式

m_d3dpp.BackBufferFormat = d3dDisplayMode.Format;

启动深度和模板缓冲

m_d3dpp.EnableAutoDepthStencil = TRUE;

这里是关键，它是设置深度缓冲和模板缓冲格式，一般情况下，它们一共占2个字，也就是4个字节。D表示深度缓冲，S表示模板缓冲，我这里设置的是深度占3个字节，24BIT，模板占一个字节，8BIT。

m_d3dpp.AutoDepthStencilFormat = D3DFMT_D24S8;

我现在介绍D3D模板操作基本流程。

图77

图77表示模板的使用流程，模板，深度，颜色，它们都是一个对应一个的。

这个图我一步一步介绍。

这个图简单描述就是，你给定一个值和当前颜色对应的模板值进行比较，如果通过比较就渲染这个颜色，如果没有通过就不渲染。通过比较或者没有通过比较都可以设置这个颜色对应的模板值。

1．你要给定一个用来比较的值，这个就叫模板参考值。

m_pDevice->SetRenderState(D3DRS_STENCILREF, 0x1);

D3D中这样设置，我设置的参考值为1。0x表示16进制。

2．图77还有一个叫模板掩码的东西，模板掩码要和参考值进行与操作，还要和当前颜色对应的模板值进行与操作。与操作目的就是取出参考值某几个位，然后再取出当前颜色对应的模板值某几个位，它们取出的这几个位都是同一的。

例如：我设定模板掩码为0xF0,2进制为11110000。现在参考值2进制为

1011 1100 0100，当前颜色对应的模板值为 1000 1101（开始创建时模板为8位）

然后它们与操作，就是把分别把对应在模板掩码中是1的位取出来。

1011 1100 0100

1111 0000

与操作，取出来为 1100 0000

1000 1101

1111 0000

与操作 取出来为 1000 0000

然后1100 0000和1000 0000比较

你仔细观察就是把对应模板掩码是1的取出来，然后比较。

设置模板掩码，这个设置的是所有位取出来，然后比较。

m_pDevice->SetRenderState(D3DRS_STENCILMASK, 0xffffffff);

3．设置比较函数

m_pDevice->SetRenderState(D3DRS_STENCILFUNC,D3DCMP_LESSEQUAL );

这里设置是小于等于参考值为通过测试。

然后你就要绘制，你要绘制的东西，如果象素通过测试它就会画到屏幕上。

4．最后是，无论通过还是没有通过都可以设置更改模板对应的值。

测试通过

m_pDevice->SetRenderState(D3DRS_STENCILPASS, D3DSTENCILOP_KEEP);

测试没有通过

m_pDevice->SetRenderState(D3DRS_STENCILFAIL, D3DSTENCILOP_KEEP);

D3D提供这些更改方式

typedef enum _D3DSTENCILOP {

D3DSTENCILOP_KEEP = 1,

D3DSTENCILOP_ZERO = 2,

D3DSTENCILOP_REPLACE = 3,

D3DSTENCILOP_INCRSAT = 4,

D3DSTENCILOP_DECRSAT = 5,

D3DSTENCILOP_INVERT = 6,

D3DSTENCILOP_INCR = 7,

D3DSTENCILOP_DECR = 8,

D3DSTENCILOP_FORCE_DWORD = 0x7fffffff, /* force 32-bit size enum */

} D3DSTENCILOP;

具体表示什么自己看D3D SDK吧！

5．最后要说的就是更改模板值，D3D中对于颜色缓冲，Z缓冲都没有提供相应内容操作，如果你想操作它们必须LOCK。这个速度很慢。但模板例外没，D3D中提供一些方式，让你可以很快的更改它。

基本上D3D提供了

D3DRS_STENCILFAIL //模板测试没有通过，Z缓冲通过

D3DRS_STENCILZFAIL //模板通过Z缓冲没通过

D3DRS_STENCILPASS //模板测试通过，Z缓冲通过

这三个是要配合模板比较函数来使用的（个人认为虽然这个三个操作和合理使用比较函数，可以达到任何操作效果，但还是感觉给的操作太少，比如模板没有通过测试Z没有通过测试等这样的操作）

10．2构造阴影体

好了，现在正式介绍阴影体。

图78

绿色区域就为阴影体，只要在这个范围的物体，都是在阴影区域，如果这个区域没有其他光可以干扰的话，只要有物体在这里面，则这个物体的表面就要被阴影覆盖。

这个方法更大的技巧借助了模版缓冲，把3D问题最后简化到2D问题的渲染，而且不受投影面的影响。

首先我们要构建阴影体。

阴影体由前面，侧面，下面组成。

1．我们先来计算前表面，这里所有求得的三角形都没有用索引方法来渲染。直接把所三角形顶点求出来。

前表面是那些自己法向量和光源方向反方向的（左手坐标系）。

因为D3D中默认顺时针可见，表面的法向量根据左手定规（左手坐标系）可以判断，也就是说物体表面法向量是朝向物体外部的。

所以前表面是那些自己法向量和光源方向反方向的。也就是它们点积与小于0。

2．求侧面首先要知道轮廓边，轮廓边就是光源正好照射物体的边界

对于轮廓边有两种求法

A．你仔细观察就会发现，相临的两个三角形的公用边，如果这两个三角形面法向量和光源的点积一个正，一个负那么这个公用边就是轮廓边。

B．还有一种求轮廓边的方法就是，所有上表面中，那些只被一个三角形使用的边，就是轮廓边。否则如果不是轮廓边至少2个三角形公用。

3．知道了轮廓边后，就知道了边的顶点。为了构成阴影体，你要把顶点按照光源方向延长L长度，然后形成了侧面。这里究竟延长多长，你一定要使阴影体和要被投影的面相交，这样被投影面上，才能形成阴影。

4．下表面，是根据正表面顶点延长L长度。

//阴影体顶点格式

typedef struct SHADOW_VERTEX_TYPE

{

D3DXVECTOR3 position;

}VSSHADOW_VERTEX, *PVSSHADOW_VERTEX;

//阴影体表面三角形结构

typedef struct TRIANGLE_TYPE

{

D3DXVECTOR3 * pV0;

D3DXVECTOR3 * pV1;

D3DXVECTOR3 * pV2;

VSVector vcN;

}TRIANGLE;

//为要渲染阴影体，添加顶点，顶点个数，顶点索引，索引个数，顶点大小

HRESULT VSShadowVolume::UpdateGeometry(void *pVerts, UINT NumV,

WORD *pIndis, UINT NumI,

UINT nSize, VSAabb aabb)

{

if (!pVerts || !pIndis || (NumV==0) || (NumI==0))

return VS_FAIL;

m_pVerts = (BYTE *) pVerts;

m_pIndis = pIndis;

m_NumV = m_NumV;

m_NumI = NumI;

m_nSize = nSize;

m_Aabb = aabb;

m_NumT = m_NumI/3;

m_pTris = new TRIANGLE[m_NumT];

//一个三角形的一条边用2个顶点索引存储,共3条边 m_NumT*6 最多m_NumT*3个临界边

m_pEdges = new WORD[m_NumT*6];

//不使用索引渲染阴影体

//模型一共m_NumT三角形，一个三角形3个顶点，阴影体顶面和底面最多

//m_NumT*3*2，最多m_NumT*3临界边，每个边都有可能是侧面，一个侧面

//2个三角形，每个三角形3个顶点共6个顶点。侧面最多

//为m_NumT*3*6，最后结果为m_NumT*3*2+m_NumT*3*6 = m_NumT*3*8;

m_pShadowVertex = new VSSHADOW_VERTEX[m_NumT*3*8];

int nFact = m_nSize/sizeof(BYTE);

//计算面法向量

for (UINT i=0; i<m_NumT; i++)

{

m_pTris[i].pV0 = (D3DXVECTOR3*)&m_pVerts[ m_pIndis[i*3+0] * nFact ];

m_pTris[i].pV1 = (D3DXVECTOR3*)&m_pVerts[ m_pIndis[i*3+1] * nFact ];

m_pTris[i].pV2 = (D3DXVECTOR3*)&m_pVerts[ m_pIndis[i*3+2] * nFact ];

VSVector vc0( m_pTris[i].pV0->x,

m_pTris[i].pV0->y,

m_pTris[i].pV0->z);

VSVector vc1( m_pTris[i].pV1->x,

m_pTris[i].pV1->y,

m_pTris[i].pV1->z);

VSVector vc2( m_pTris[i].pV2->x,

m_pTris[i].pV2->y,

m_pTris[i].pV2->z);

//法向量朝里面

m_pTris[i].vcN.Cross( (vc2 - vc1),(vc1 - vc0));

m_pTris[i].vcN.Normalize();

}

return VS_OK;

}//UpdateGeometry

构造阴影体

//光源LightOrient方向，最好单位化，我引擎里面单位化了

void VSShadowVolume::BuildShadowVolume(const VSVector& LightOrient)

{

VSVector vc;

VSVector wc;

VSSHADOW_VERTEX v1, v2, v3, v4;

//我这里延长了500个长度

vc = LightOrient * 500.0f;

m_NumShadowVertex = 0;

m_NumE = 0;

//计算轮廓边和上下面

for (UINT i=0; i<m_NumT; i++)

{

//使用物体顶点索引来计算

WORD wFace0 = m_pIndis[3*i+0];

WORD wFace1 = m_pIndis[3*i+1];

WORD wFace2 = m_pIndis[3*i+2];

//使用前表面，因为D3D顺时针可见，根据左手坐标系三角形法线方向，和光源方向相同相反

//当前三角形面法向量和光源方向做点积，三角形面法向量最开始模型//要形成阴影时，就要求出来

if ( (m_pTris[i].vcN * LightOrient) < 0.0f )

{

//添加边，为了找出轮廓边，具体内容，下面给出

AddEdge(wFace0, wFace1 );

AddEdge(wFace1, wFace2 );

AddEdge(wFace2, wFace0 );

memcpy(&v1, m_pTris[i].pV0, sizeof(D3DXVECTOR3));

memcpy(&v2, m_pTris[i].pV1, sizeof(D3DXVECTOR3));

memcpy(&v3, m_pTris[i].pV2, sizeof(D3DXVECTOR3));

//形成上面

m_pShadowVertex[m_NumShadowVertex++] = v2;

m_pShadowVertex[m_NumShadowVertex++] = v1;

m_pShadowVertex[m_NumShadowVertex++] = v3;

//形成下面

m_pShadowVertex[m_NumShadowVertex++] = Extrude(&v1,vc);

m_pShadowVertex[m_NumShadowVertex++] = Extrude(&v2,vc);

m_pShadowVertex[m_NumShadowVertex++] = Extrude(&v3,vc);

}

} // for

int nFact = m_nSize/sizeof(BYTE);

//侧面

for (UINT j=0; j<m_NumE; j++)

{

memcpy(&v1, &m_pVerts[ m_pEdges[2*j+0] * nFact ], sizeof(VSSHADOW_VERTEX));

memcpy(&v2, &m_pVerts[ m_pEdges[2*j+1] * nFact ], sizeof(VSSHADOW_VERTEX));

v3 = Extrude(&v1,vc);

v4 = Extrude(&v2,vc);

m_pShadowVertex[m_NumShadowVertex++] = v1;

m_pShadowVertex[m_NumShadowVertex++] = v2;

m_pShadowVertex[m_NumShadowVertex++] = v3;

m_pShadowVertex[m_NumShadowVertex++] = v2;

m_pShadowVertex[m_NumShadowVertex++] = v4;

m_pShadowVertex[m_NumShadowVertex++] = v3;

}

} // BuildShadowVolume

//找出轮廓边

void VSShadowVolume::AddEdge(WORD v0, WORD v1)

{

for( UINT i=0; i < m_NumE; i++ )

{

//如果有公用的，就删除掉

if( ( m_pEdges[2*i+0] == v0 && m_pEdges[2*i+1] == v1 ) ||

( m_pEdges[2*i+0] == v1 && m_pEdges[2*i+1] == v0 ) )

{

if( m_NumE > 1 ) {

m_pEdges[2*i+0] = m_pEdges[2*(m_NumE-1)+0];

m_pEdges[2*i+1] = m_pEdges[2*(m_NumE-1)+1];

}

m_NumE--;

return;

}

//没有公用，添加

m_pEdges[2*m_NumE+0] = v0;

m_pEdges[2*m_NumE+1] = v1;

m_NumE++;

}//AddEdge

渲染阴影算法介绍

10．3 渲染阴影体

10．3．1 Z测试通过算法

先渲染所有场景，然后打开模板缓冲，把Z缓冲变成只读，然后渲染阴影体的前表面多边形（法向量朝视点），如果Z测试通过，此象素的模板缓冲+1。接着渲染阴影体的后表面，如果Z测试通过，此象素模板缓冲-1。

图79

渲染前表面1，3，射线a 对应的象素摸板都通过Z测试加2次1，为2，射线b同理。渲染后表面2，4，射线a渲染2通过Z测试-1，b也通过Z测试-1，但渲染4时，对于a 没有通过z测试，而b 通过Z测试，所以屏幕上点a为阴影。

但这个方法同时存在问题。

图80

如果视点在阴影中，情况就不正常了，当然可以判断视点是否在阴影中，如果在阴影中的话，把模板值初始为1，就可以了。

我给出代码，代码是结合我引擎的，但我相信是能看明白的。

初始设置

//设置成小于才通过Z测试，因为阴影体上面和物体面向光源的表面是重叠的，为了防止上面形成阴影所以设置为小于

m_pDevice->SetRenderState(D3DRS_ZFUNC,D3DCMP_LESS);

//Z缓冲只读

m_pDevice->SetRenderState(D3DRS_ZWRITEENABLE, FALSE);

//启动模板

m_pDevice->SetRenderState(D3DRS_STENCILENABLE, TRUE);

//用FLAT着色

m_pDevice->SetRenderState(D3DRS_SHADEMODE, D3DSHADE_FLAT);

//因为没有正式渲染阴影，只是为修改模板操作做准备，模板所有操作都通过。

m_pDevice->SetRenderState(D3DRS_STENCILFUNC, D3DCMP_ALWAYS);

m_pDevice->SetRenderState(D3DRS_STENCILPASS, D3DSTENCILOP_KEEP);

m_pDevice->SetRenderState(D3DRS_STENCILFAIL, D3DSTENCILOP_KEEP);

//关闭颜色缓冲，我们现在不想让颜色渲染到屏幕上，只是为了往模板里面写值

SetUseColorBuffer(false);

//渲染前面

m_pDevice->SetBackfaceCulling(RS_CULL_CCW);

m_pDevice->SetStencilBufferMode(RS_STENCIL_PASS_INCR, 0);

if(VS_FAIL==m_pDevice->GetVertexManager()

->Render(VSSHADOW_VERTEX_FVF,

m_NumShadowVertex,0,m_pShadowVertex,NULL,m_SkinID))

return VS_FAIL;

//渲染后面

m_pDevice->SetBackfaceCulling(RS_CULL_CW);

m_pDevice->SetStencilBufferMode(RS_STENCIL_PASS_DECR,0);

if(VS_FAIL==m_pDevice->GetVertexManager()

->Render(VSSHADOW_VERTEX_FVF,

m_NumShadowVertex,0,m_pShadowVertex,NULL,m_SkinID))

return VS_FAIL;

m_pDevice->SetBackfaceCulling(RS_CULL_CCW);

这样完成了模板的，然后我们用黑色透明的，和屏幕大小相等的矩形渲染，通过模板测试的，就有黑色透明象素，也就形成了阴影。

//设置模板参考值

m_pDevice->SetRenderState( D3DRS_STENCILREF, 0x1 );

//设置模板比较函数

m_pDevice->SetRenderState( D3DRS_STENCILFUNC, D3DCMP_LESSEQUAL );

//设置通过后操作

m_pDevice->SetRenderState( D3DRS_STENCILPASS, D3DSTENCILOP_KEEP );

//画透明黑色矩形

FadeScreen(0.0f,0.0f,0.0f,0.6f);

//恢复所有原来模式

m_pDevice->SetRenderState(D3DRS_SHADEMODE, D3DSHADE_GOURAUD);

m_pDevice->SetRenderState(D3DRS_CULLMODE, D3DCULL_CCW);

m_pDevice->SetRenderState(D3DRS_ZWRITEENABLE, TRUE);

m_pDevice->SetRenderState(D3DRS_STENCILENABLE, FALSE);

m_pDevice->SetRenderState(D3DRS_ALPHABLENDENABLE, FALSE);

m_pDevice->SetRenderState(D3DRS_ZFUNC,D3DCMP_LESSEQUAL);

SetUseColorBuffer(true);

我给出了打开关闭颜色缓冲的函数，很简单的。

void VSGraphD3D::SetUseColorBuffer(bool b)

{

if (!b)

{

m_pDevice->SetRenderState(D3DRS_ALPHABLENDENABLE, TRUE);

m_pDevice->SetRenderState(D3DRS_SRCBLEND, D3DBLEND_ZERO);

m_pDevice->SetRenderState(D3DRS_DESTBLEND, D3DBLEND_ONE);

}

else

{

m_pDevice->SetRenderState(D3DRS_ALPHABLENDENABLE, FALSE);

m_pDevice->SetRenderState(D3DRS_SRCBLEND, D3DBLEND_ONE);

m_pDevice->SetRenderState(D3DRS_DESTBLEND, D3DBLEND_ZERO);

}

}//SetUseColorBuffer

10．3．2 Z测试失败算法

先渲染所有场景，然后打开模板缓冲，把Z缓冲变成只读，然后渲染阴影体的后表面多边形（法向量朝视点），如果Z测试没通过，此象素的模板缓冲+1。接着渲染阴影体的前表面，如果Z没测试通过，此象素模板缓冲-1。

图81

可以看出这种方法就不存在上面的问题。

代码入下

初始设置和Z测试通过算法一样

//渲染后面

m_pDevice->SetBackfaceCulling(RS_CULL_CW);

m_pDevice->SetStencilBufferMode(RS_STENCIL_ZFAIL_INCR,0);

if(VS_FAIL==m_pDevice->GetVertexManager()

->Render(VSSHADOW_VERTEX_FVF,

m_NumShadowVertex,0,m_pShadowVertex,NULL,m_SkinID))

return VS_FAIL;

//渲染前面

m_pDevice->SetStencilBufferMode(RS_STENCIL_ZFAIL_DECR, 0);

m_pDevice->SetBackfaceCulling(RS_CULL_CCW);

if(VS_FAIL==m_pDevice->GetVertexManager()

->Render(VSSHADOW_VERTEX_FVF,

m_NumShadowVertex,0,m_pShadowVertex,NULL,m_SkinID))/**/

return VS_FAIL;

m_pDevice->SetBackfaceCulling(RS_CULL_CCW);

渲染阴影设置和Z测试通过算法一样

还有一点我要说的是，如果你远剪裁面把阴影体剪裁了，你的渲染就有毛病了，这个你自己可以想象，或者自己画图看一下，根据上面的讲解，你会自己知道问题在那里的。所以你尽量设置下，物体靠近远剪裁面的，就不让它画阴影了。

十一．碰撞

讲到这个地方我很有成就感，可以说，我的地形引擎已经很完善了，基本想要有的功能我都添加到了里面。

对于引擎里面的一切，我改了很多遍。我知道自己的引擎根本不能和商业的相比，唯一另我欣慰的是，运行速度我比较满意。我的引擎现在还有一点小毛病，我实在不想改了，这个毛病并不影响速度，只不过是稍微有些不方便使用，我想很少有人去关心我的引擎究竟怎么实现，在过几年DX9就完全被淘汰，真正的渲染基本都要用SHADER，谁还会关心用DX9固定流水线实现的引擎（其实我引擎里面很少用DX9里面的函数，基本也都是自己写的）。

每次我都愿意发掉牢骚，因为自己编程太枯燥了，没有人合作，学校里想找个有共同目标的人很难，找到了吧，基本也是你在帮他，真郁闷。

仔细想想我们要处理碰撞，都要有那些碰撞需要处理呢？

如果你没有做过引擎，又想研究引擎，我个人建议就读《3D GAME ENGINE PROGRAMING》，其他的都不要看，这是一个唯一有讲解的书籍，其他引擎连个文档几乎都没有，更别说讲解，所以你很难看懂，还浪费时间。相信我，花半年研究这本书，你很值得。最好还要按照自己想法重写他的代码，你会更加提高。如果你想了解更多请看我的BLOG http://user.qzone.qq.com/79134054/blog/1214061242

11．1 三种碰撞基元算法

我们需要处理的碰撞，基本就3种。

1．AABB与射线碰撞

3D游戏中子弹碰撞判断基本都是射线碰撞，当然射线可以有很多用途。射线与物体碰撞，如果要简单处理的话，就是射线和物体AABB碰撞。

如果想要精度提高，一个模型就要每个部分有一个AABB，然后用射线分别和这些部分的AABB碰撞。我的骨骼动画类里面支持骨骼AABB，MESH AABB，所以对于多MESH 物体，或者骨骼物体，碰撞精度很高。

有时间我一定把我写的加载。X文件类的实现过程和代码写出来，这个类可以加载所有。X文件，有骨骼的，蒙皮骨骼，非蒙皮骨骼的，多MESH的，单MESH的，有动画信息的，没动画信息的，大小通吃。我没有用D3D接口，只用了个XFILE接口，帮我读文件内容，其余所有处理都自己做的，想要了解D3D 关于MESH 和骨骼动画的，你们可有福音了。

2．AABB与AABB碰撞

两个物体碰撞用这个，最好不过了。

3．射线与三角形

这个用来做地形和射线碰撞。

在把这些碰撞引入地形之前，我想先介绍这三种碰撞的算法。这些算法都来自《计算机图形学几何工具算法详解》，很好的书，不要吝啬钱，买下它，很值得。虽然这本书上有很详细的算法，但我还是详细介绍下。

我先介绍下，射线的定义吧！

图82

看图82，射线是用一个顶点p 和一个方向d（最好单位化）来定义。如果你对这个定义感到很迷糊，希望你数学要好好学学。想成3D高手，数学基础不好，那是不可能的。

射线上任意一点M = P + t*d (0< = t)

如果t<0，求出的点就在射线反方向上。

1．AABB与射线碰撞

前面我说过了，AABB的一种定义是用边界最大点，最小点组成。因为AABB是所有平面都和坐标轴对齐，所以可以用轴分离的方法，分别处理每个坐标轴方向的点碰撞。

图83

看图83，射线与AABB相交。我们要求出的点是t0点，也就是说求出最近相交的点，求的相交点以参数t的形式返回，然后代到射线方程，就求出这个点了。

轴分离的思想是，分别用X、Y、Z三个分量来进行处理。

图84

图84是在X轴上进行分离，所有分量都用X的进行计算，分别求出t0,t1

进行比较t后最大值给tFar ,最小值给tNear。然后分别在Y轴、Z轴进行分离计算，把最大，最小t和tFar 和tNear比较，再给tFar tNear。如果tNear>0，则返回tNear，如果tNear<0，说明射线在顶点在AABB里面，则返回tFar。

如果处理线段，也就是说射线有长度的，我们长度也要求用射线方程变量t给出，也就是说给一个fL来表示长度，把fL带到射线方程就能求出这个点来。当求出tNear后，和fL比较，如果小fL则相交，如果大于则没有相交。

bool VSAabb::Intersects(const VSRay &Ray, float fL, float *t)

{

bool bInside = true;

float t0, t1, tmp, tFinal;

float tNear = -999999.9f;

float tFar = 999999.9f;

float epsilon = 0.00001f;

VSVector MaxT;

//判断方向X分量是为0，为0，则X方向平

if (_fabs(Ray.m_vcDir.x) < epsilon)

{

//顶点X分量如果在边界盒X分量外，则直接返回不相交

if ( (Ray.m_vcOrig.x < vcMin.x) ||

(Ray.m_vcOrig.x > vcMax.x) )

return false;

}

//求出t0,t1

t0 = (vcMin.x - Ray.m_vcOrig.x) / Ray.m_vcDir.x;

t1 = (vcMax.x - Ray.m_vcOrig.x) / Ray.m_vcDir.x;

//找t0,t1中最大和最小给tFar tNear

if (t0 > t1) { tmp=t0; t0=t1; t1=tmp; }

if (t0 > tNear) tNear = t0;

if (t1 < tFar) tFar = t1;

if (tNear > tFar) return false;

if (tFar < 0) return false;

//Y分量

if (_fabs(Ray.m_vcDir.y) < epsilon)

{

if ( (Ray.m_vcOrig.y < vcMin.y) ||

(Ray.m_vcOrig.y > vcMax.y) )

return false;

}

t0 = (vcMin.y - Ray.m_vcOrig.y) / Ray.m_vcDir.y;

t1 = (vcMax.y - Ray.m_vcOrig.y) / Ray.m_vcDir.y;

if (t0 > t1) { tmp=t0; t0=t1; t1=tmp; }

if (t0 > tNear) tNear = t0;

if (t1 < tFar) tFar = t1;

if (tNear > tFar) return false;

if (tFar < 0) return false;

//Z分量

if (_fabs(Ray.m_vcDir.z) < epsilon)

{

if ( (Ray.m_vcOrig.z < vcMin.z) ||

(Ray.m_vcOrig.z > vcMax.z) )

return false;

}

t0 = (vcMin.z - Ray.m_vcOrig.z) / Ray.m_vcDir.z;

t1 = (vcMax.z - Ray.m_vcOrig.z) / Ray.m_vcDir.z;

if (t0 > t1) { tmp=t0; t0=t1; t1=tmp; }

if (t0 > tNear) tNear = t0;

if (t1 < tFar) tFar = t1;

if (tNear > tFar) return false;

if (tFar < 0) return false;

if (tNear > 0) tFinal = tNear;

else tFinal = tFar;

//和fL进行比较

if (tFinal > fL) return false;

if (t) *t = tFinal;

return true;

} // Intersects(Ray) at length

2．AABB与AABB碰撞

进行AABB相交测试也用这种轴分离的方法。

很简单，直接给代码你就能明白。

bool VSAabb::Intersects(const VSAabb &aabb)

{

if ((vcMin.x > aabb.vcMax.x) || (aabb.vcMin.x > vcMax.x))

return false;

if ((vcMin.y > aabb.vcMax.y) || (aabb.vcMin.y > vcMax.y))

return false;

if ((vcMin.z > aabb.vcMax.z) || (aabb.vcMin.z > vcMax.z))

return false;

return true;

} // Intersects(Aabb)

3．射线与三角形碰撞

三角形有一个重心方程，这个方程可以表示三角形任意点。

图85

三角形上任意一点Q = w*V0+u*V1+v*V2;其中u+v+w = 1.。当0 < u ,v,w<1时 Q点在三角形内，否则在三角形外的同平面上。

射线与三角形相交我们只需要满足下面方程就可以了。

P+t*d = w*V0+u*V1+v*V2…………………………………….. (11.1);

u+v+w = 1…………………………………………………………(11.2).

已经知道P+t*d = w*V0+u*V1+v*V2进行分量处理可以变成三个方程，再加上u+v+w = 1，四个方程，四个未知数，可以求得。

很多书上都用克莱母法则来解

(11.1与11.2)得出

[-d, V1-V0, V2-V0] [ u ] = [P – v0]

t |P – V0 V1- V0 V2 - V0|

[ u ] = 1 / | -d V1 – V0 V2 – V0 | [ |-d P - V0 V2 - V0| ]

v |-d V1-V0 P - V0|

= 1 / （(d 叉乘 V2 – V0)点乘V1 – V0 ）

（（P – V0叉乘 V1- V0）点乘 （V2 - V0））

[ （（d 叉乘 V2- V0）点乘 （P - V0）） ]

（（P – V0叉乘 V1- V0）点乘 d ）

其中|u v w|= u点乘 (v叉乘 w) = w点乘 (u叉乘 v)

x叉乘y= - y叉乘x

x点乘y = y点乘x

下面是代码，变量bCull表示是否背面剪裁，也就说，顶点逆时针排列的三角形

不进行处理。fL表示处理的是线段的长度。

bool VSRay::Intersects(const VSVector &vc0, const VSVector &vc1,

const VSVector &vc2, bool bCull, float fL, float *t)

{

VSVector pvec, tvec, qvec;

VSVector edge1 = vc1 - vc0;

VSVector edge2 = vc2 - vc0;

pvec.Cross(m_vcDir, edge2);

//计算（ (d 叉乘 V2 – V0)点乘V1 – V0 ）

//并且等于 -d点乘((V2 – V0) 叉乘(V1 – V0))，((V2 – V0) 叉乘(V1 – V0))

//为平面法向量，如果d*((V2 – V0) 叉乘(V1 – V0)) >0，则剪裁掉，也就是//说 - d*((V2 – V0) 叉乘(V1 – V0))< 0

float det = edge1 * pvec;

if ( (bCull) && (det < EPSILON_E5) )

return false;

else if ( (det < EPSILON_E5) && (det > -EPSILON_E5) )

return false;

//求u,我们没有必要求u，因为用t可以确定相交点，求u只不过是为了看

//点是否在三角形内，也就是u< 1,u+v < 1，

float f_det = 1.0f / det;

tvec = m_vcOrig - vc0;

float u = (tvec * pvec) * f_det;

if (u < 0.0f || u > 1)

return false;

qvec.Cross(tvec, edge1);

float v = (m_vcDir * qvec) * f_det;

if (v < 0.0f || u+v > 1)

return false;

float f = (edge2*qvec) * f_det;

if(f < 0)

return false;

if (t)

{

*t = f;

}

return true;

} // Intersects(Tri at length)

过程很烦琐，我希望没有读懂的再仔细读一遍，如果数学不过关，那我也没办法了。

11．2场景中的碰撞处理

1．场景中2个物体碰撞

对于场景中的2个物体碰撞，我采用AABB与AABB测试，精度还是可以的。我程序中给的例子是一个相机和场景中所有静态物体进行碰撞测试。动态物体之间的测试后面我再说。

对于静态物体，我们还用BVH四叉树算法来处理。因为前面BVH四叉树我们已经构造完成，现在只需要用AABB检测就可以了。检测算法是递归的，而且一遇到碰撞，也就是只有真正和叶子节点的物体发生碰撞才返回1，并且是遇到第一次就返回（和射线碰撞有些不一样，射线碰撞必须返回最小值，所以要和所有发生碰撞的物体都测试，然后返回最小的），其余情况都返回0。

bool VSTerrainJungle::TestCollisionQuatNode(VSAabb& Aabb,QuatTree *pNode)

{

//如果AABB和节点AABB相交

if(pNode->m_Aabb.Intersects(Aabb))

{

//分别处理所有孩子

int iEmptyChild = 0;

bool bResult = 0;

for(int i = 0 ; i< 4; i++)

{

if(pNode->Child[i])

{

if(TestCollisionQuatNode(Aabb,pNode->Child[i]))

{

bResult = 1;

break;

}

else

{

iEmptyChild++;

}

//如果孩子节点为空，证明是叶子节点，处理叶子节点的所有物体

if(iEmptyChild == 4)

{

int j;

for(j = 0 ; j < pNode->m_PlantModel.size() ; j++)

{

//如果物体要求AABB测试

if(pNode->m_PlantModel[j].m_bCollision)

{

VSAabb AabbModel ;

pNode->m_PlantModel[j].m_pModel->GetAABB(&AabbModel);

if(AabbModel.Intersects(Aabb))

{

bResult = 1;

break;

}

return bResult;

}

return bResult;

}

else

{

return 0;

}

对于动态物体，我们没有什么好办法，如果物体有活动区域，就先对活动区域剪裁，然后在对动态物体判断。后面我讲地形拼接，把一块地形重复，构成无限地形时，动态物体只能在一块地形上活动。所以我们可以剪裁地形块，然后在处理地形块的动态物体。

2．场景中射线与物体碰撞

只说静止的，动态和上面说的方法基本一样。还是用BVH四叉树进行处理。没办法，它速度快呀！哈哈。开始时，我让fL为99999.0f，因为我假设我的子弹射程是99999.0f。处理过程和处理2个AABB之间差不多，唯一不同就是要找出最小的相交点。

bool VSTerrainJungle::TestCollisionQuatNode(VSRay& Ray,float fL,

float *pfD,QuatTree *pNode)

{

if(!pNode->m_Aabb.Intersects(Ray,fL,pfD))

return 0;

else

{

int iEmptyChild = 0;

bool bResult = 0;

for(int i = 0 ; i< 4; i++)

{

if(pNode->Child[i])

{

if(TestCollisionQuatNode(Ray,fL,pfD,pNode->Child[i]))

bResult = 1;

if(!pfD)

break;

}

else

{

iEmptyChild++;

}

if(iEmptyChild == 4)

{

int j;

for(j = 0 ; j < pNode->m_PlantModel.size() ; j++)

{

if(pNode->m_PlantModel[j].m_bCollision)

{

VSAabb AabbModel ;

pNode->m_PlantModel[j].m_pModel->GetAABB(&AabbModel);

float _pfD = 0.0f;

if(AabbModel.Intersects(Ray,fL,&_pfD))

{

//找出最小相交点

bResult = 1;

if(pfD)

{

if(*pfD > _pfD)

*pfD = _pfD;

}

else

{

break;

}

return bResult;

}

return bResult;

}

return 1;

}

上面代码我写的说明很少，我认为大家可以看明白，其实也很简单，不是吗？

3．场景中射线与地形三角形碰撞

这个测试算法和射线与AABB差不多，只不多测试的三角形。这个是基于小地形小正方形的AABB的，一旦遍历到地形最小正方形（边长为2，边上顶点为3个），就开始处理这个正方形扇形的8个三角形。下面是代码很简单的。

bool VSTerrain::TestCollisionQuatNode(VSRay& Ray,float fL, float *pfD,

bool bCull,int iX, int iZ, int iEdgeLength)

{

bool bResult = 0;

if( iEdgeLength > 3 )

{

VSAabb *pAabb = GetAABBMatrix(iX,iZ);;

if(pAabb->Intersects(Ray,fL,NULL))

{

int iChildOffset = ( ( iEdgeLength-1 ) >> 2 );

int iChildEdgeLength= ( iEdgeLength+1 ) >> 1;

//lower left

if(TestCollisionQuatNode( Ray,fL,pfD,bCull,iX - iChildOffset, iZ - iChildOffset, iChildEdgeLength ))

bResult = 1;

//lower right

if(TestCollisionQuatNode( Ray,fL,pfD,bCull,iX + iChildOffset, iZ - iChildOffset, iChildEdgeLength ))

bResult = 1;

//upper left

if(TestCollisionQuatNode( Ray,fL,pfD,bCull,iX - iChildOffset, iZ + iChildOffset, iChildEdgeLength ))

bResult = 1;

//upper right

if(TestCollisionQuatNode( Ray,fL,pfD,bCull,iX + iChildOffset, iZ + iChildOffset, iChildEdgeLength ))

bResult = 1;

}

else

{

VSVector FanVer[10];

int iEdgeOffset= ( iEdgeLength-1 )>>1;

VSVERTEXTER *pVer;

int i = 0;

//Get Certer

pVer = GetRealDate(iX,iZ);