最近一直在考虑farcry在outdoor环境中所使用的HSR算法，使用过crytek的sandbox的朋友都可以看出来，
在使用线框模式情况下可以清楚的发现cry engine可以对大部分的无效的渲染图元进行干净的剔除，基本
上有两种情况，一种是backface culling，就是对背面的地形face进行干净的剔除，另一种是OC，就是对
地形所遮挡的地形face和model(就是地面上的树木,建筑物等等)进行大部分的剔除.基本上backface culling
部分比较简单,估计使用的算法就是法线锥,如果对这种算法不熟悉的可以参考一书
相关部分有比较详细的介绍.比较困难的是第二种情况就是OC的算法,由于OC算法非常多因此并不能非常肯定
crytek所使用的算法,根据我这一段的研究,简单介绍一下自己对其算法的考虑,希望高手讨论一下.
通常OC算法有非常重要的两个步骤,一个是获得场景中非常精确的occluder信息,另一个是使用occluder
信息来对场景的occludee进行剔除.对于第一步来说有两种方法,一个是预先计算好,另一个是运行时实时计算
获得,观察sandbox我们可以发现cry engine使用的是实时计算获得occluder信息,这是非常重要的一步,由于
是运行时进行计算,因此获得occluder的算法必须非常高效,否则是得不偿失的.对于第二步需要根据获得的
具体occluder信息来使用相应的算法,因此最后再谈.先看看第一步.
一 通过观察地形的线框信息可以看到farcry的地形是分块的,每一块地形由(32+1)*(32+1)个顶点组成,而且
需要注意相临地形块之间地形变化是连续的.根据这些信息基本上可以肯定获得occluder的算法使用轮廓线
算法是比较合适的,下面我们看一下如何来获得轮廓线,先以一个地形块开始,
1 对每一个顶点建立一个edge数组,这个数组保存了所有和当前顶点构成edge的顶点索引,根据farcry使用
的LOD算法,这个数组最大可以保存6个顶点索引.
2 将地形块中所有的顶点变换到投影空间,这样做地目的是为了方便处理,投影空间是一个齐次空间,这里
frustum的形状已经变换为立方体,而且所有位于frustum内的顶点都被限制在指定的范围(-1.0 -- 1.0),
注意由于DX和OGL的差异,为了方便这里以OGL的为准.
3 对变换后的顶点进行排序,排序需要按照从小到大的顺序记录顶点索引,排序规则如下:首先比较顶点的x
值,如果x值相同比较y值.
4 从排序后第一个顶点a出发,选择其edge数组中y值最大的顶点b(b的x值必须大于a),然后将这条edge记录
下来.
5 接下来检查在ab之间的顶点(x值大于a而小于b)是否存在y值比ab的y值都大的顶点,如果存在说明在这个
范围内有edge和当前的edge发生交叉,说明一下通过比较y值来确定是否存在edge发生交叉得出的结果并不
能保证将所有存在交叉的edge都找出来,但是为了保证算法的速度必须这样做,如果计算edge的斜率的话
需要做除法运算,效率太差.如果不存在交叉edge那么从顶点b开始重复过程4.
6 接下来需要找到存在交叉的edge,假设找到的顶点为c,那么在c的edge数组中查找位于ab之间的顶点,如果
找到那么这条edge就是交叉edge(具体编程时需要考虑没有找到和找到多个顶点的情况),然后简单的计算
出两条edge之间的交点d,剔除edge ab,将edge ad和dc记录下来.从顶点c开始重复过程4.
7 当遍历到排序数组的最后一个顶点后,就可以获得地形块的轮廓线.必须注意在遍历到最后时并不能保证
一定是在最后一个顶点上终止,这是因为步骤5只是检查了位于ab之间顶点构成的edge是否存在交叉并没有
考虑这样的edge(一个顶点位于ab之间而另一个大于b的edge),因此需要在最后如果出现这种情况从尾部的
顶点出发逆向遍历到交叉edge即可.
这是一个最基本的获得一个地形块轮廓线的算法,这里没有考虑通过frustum对顶点进行剔除,也没有考虑存在
相临地形块的情况,不过也很简单只需要进行稍微的修改就可以完成,下面就要考虑如何使用获得的轮廓线来对
occludee进行剔除的问题.这里我们首先肯定的是不可能求出所有的地形块的轮廓线，因为这没有什么用，我们
求轮廓线的目的是为了对遮挡的地形块和model进行剔除，因此第一个问题是求出哪部分轮廓线来剔除被遮挡
的物体，首先可以肯定不可见的地形块是不需要计算，这些地形块包括位于frustum之外和backface的地形块。
接着看看还能剔除哪些地形块，如果地形非常平坦计算轮廓线是没有价值，因为它不可能遮挡任何物体，而
只有在地形起伏比较大的地方才可能遮挡住物体，因此高度起伏比较小的地形块需要我们进一步剔除，可以
为每一个地形块建立一个值记录地形块内高度最大和高度最小的顶点的高度差，如果小于某一个值我们可以
认为它是平坦的不需要计算轮廓线，但是并不是所有平坦的地形块都不需要计算，考虑这样的情况如果平坦的
地形块恰好位于山峰的顶部怎么办，或许此时不计算这个地形块的轮廓线也可以，不过我考虑最好还是计算，
此时可以考虑记录地形块的平均高度，如果相临地形块高度差大于临界值(这样做是考虑如果地形块为backface
的情况,此时地形块虽然达到要求但还是被剔除了)而平坦的地形块的平均高度大于相临地形块时需要计算轮廓
线.恩,实际编程的时候还有考虑各种各样的特殊情况,这里就不多说了.最后还要剔除那些距离camera位置一定
距离的地形块,这是因为距离camera非常远的地形块只能遮挡距离camera位置更远的地形块,而这些地形块可能
已经位于far clip plane之外,而且毕竟计算轮廓线还是需要非常大的代价,因此计算远处的轮廓线性价比不高,
具体的距离值设定多少需要程序运行时才能决定.
接着考虑如何对occludee进行剔除,由于轮廓线是按照地形块计算的,因此很自然的想到,如果camera所在的
地形块为A而其正前方的下一个地形块为B,B是否被遮挡只能通过检查A的轮廓线来决定,接着假设B的下一个地形
块为C,而C是否被遮挡这需要同时检查A和B的轮廓线,依次类推D需要检查A,B,C的轮廓线,这个过程称为occluder
的融合.由于地形块是严格按照行列进行排列的因此我们可以很容易的计算出哪些occluder需要融合,在计算每个
地形块的轮廓线时需要严格分层将这些轮廓线组合到一起,如何分层是非常值得考虑的问题,其实做起来也非常
简单,首先我们把camera所在的地形块作为0层,它不需要和其它轮廓线组合,将完整包围0层的8个地形块作为1层,
包围1层的16个地形块作为2层,依次类推.位于同一层中的地形块如果存在轮廓线的话需要组合到一起,同时计算
遮挡关系时也非常简单了,计算1层是否被遮挡只需要检查0层,计算2层时检查0,1层等等.好了,剩下的问题简单了
一个是occluder的融合,一个是检查是否被遮挡.
先看occluder的融合,由于轮廓线是在投影空间计算的,因此融合起来也非常方便,假设现在是0层和1层融合,
1 从0层的第一条edge ab开始,对1层中所有x值位于a,b之间的顶点检查是否有y值大于ab之间最大的y值,这
样做还是防止计算斜率,
2 如果不存在检查下一条edge,如果存在计算两条edge的交点c,记录两条边ac和cd,此时ab暂时不剔除
3 检查顶点d的下一条edge的顶点是否位于ab之间,如果不位于剔除ab,如果位于则
A 检查其y值是否大于b,如果大于将这条edge记录下来,接着重复步骤3检查下一条edge,直到顶点大于b的
范围后剔除ab.然后停止查找当前顶点的下一条edge,由于此时顶点已经进入0层的下一条edge的范围,
需要检查其y值是否大于下一条edge的y值,如果大于那么继续遍历当前(1层)顶点的下一条edge,如果
小于那么edge之间存在交点,继续步骤2.
B 如果y值小于b,好重新计算这条edge与ab之间的交点,并将新产生的edge记录下来.(此时就发现不计算
斜率带来的麻烦了,由于误差比较大,此时可能会出现错误的求交,是否必须计算斜率呢?)重复步骤1.
4 重复步骤1直到遍历完所有的edge.
其实occluder的融合应当放在计算轮廓线的时候就应该计算,这样效率应该高一些的,而且除了0层外其他层需要
的本来就是融合后的轮廓线.
当所有的轮廓线计算完成后检查occludee是否被occluder所遮挡就非常简单了,通常我们使用的occludee
就是物体的aabb,因此只需要将aabb的8个顶点变换到投影空间,然后简单的计算是否位于轮廓线之下就可以了,
算法如下: 遍历8个顶点,获得顶点的x位于轮廓线哪个edge范围内,然后比较是否位于edge的下方,如果所有的顶
点都位于轮廓线的下方那么occludee必然被遮挡.
好,终于将自己的想法写完了,毕竟这个算法不是太成熟.希望各位高手多多拍砖指正,本人不胜感激.
|
|手机版|小黑屋|九艺游戏动画论坛
( 津ICP备2022000452号-1 )