回头用Xebra测试下，看3代这关卡中开启盖，会影响游戏否

若不影响就说明关卡和贴图文件压缩得很好，也可以说关卡构架简单、贴图单一

饮水思源 - 文章阅读　　
[讨论区: GameDesign]

发信人: huling (独立游戏制作人), 信区: GameDesign
标  题: culling技术的一些介绍
发信站: 饮水思源 (2002年08月10日16:02:41 星期六), 站内信件

对于realtime interactive 3d environment,
现实的速度是非常重要的，
虽然现在的硬件能力非常的快，
但是要想保持30FPS的同时处理数十万的三角形，
以现在的主流机器来说还是非常困难的。

为了解决这种问题，人们提出了很多方法，其中有LOD,
有Culling,对于LOD,它可以从2FPS提高到10FPS,但是很
难从4FPS提高到20FPS。这两种方法并不矛盾，而且我
们往往需要在culling的基础上再使用lod进一步解决
pipeline的负担。

这里我主要希望讨论一下culling方面的技术：
culling的意思是select from a flock,
就是“从一群里面选择一部分“。对于3d engine来说，
就是要从几十万的triangle之中选择出一小部分送给
pipeline进行渲染。

选择的方法总的来说有如下几种途径：

最简单的就是backface culling,这个已经很普通，我就不说废话了。

然后就是view frustum culling,只选择在view frustum中可见的部分
送入pipeline,通常人们会采用hierarchy的数据结构来有效的进行
view frustum culling,层次型的结构在各种图形学算法中普遍采用，
比如碰撞检测，光线追踪，radiosity等等。
我尝试过一种基于AABB Tree的view frustum culling,
加上frame coherency,plane masking等优化的方法之后，
我认为效率已经非常高了。

但是对于现在的游戏场景viewfrustum culling是远远不够用的，
因为view frustum实在是非常的大，现在的场景又非常的复杂，采用
view frustum culling对于场景漫游的视角来说,平均可以删除场景中
60%左右的数据，对于一个100,000triangle的场景来说，剩下的数据也
会有好几万多边形，对于pipeline来说依然是比较重的负担。

不过view frustum culling是最容易实现的算法了，非常的方便和有效，
对于一部分3d rpg来说，我认为是一个不错的选择，因为你可以要求camera
处于较高的位置，并且总是向下观察，这样用view frustum culling就可以
以非常低的代价筛选出很少的一部分场景数据了，对于《格兰蒂亚》,《星辰物语》，
还有最新的《绝冬城之夜》等,是足够了，他们对于镜头都有比较严的限制，
正好适用于viewfrustum culling.如果大家想做3d游戏，
还是先从这类游戏入手的好，因为可以直接集中精力于渲染技术和
其他有趣的部分。

但是对大部分第一人称射击游戏而言，view frustum culling是远远不够的，
事实上，在实际的环境中我们的视野总是被各种物品遮挡住，
所以我们往往只能看到整个场景中的一小部分，远远小于我们的view frustum
的范围。这些物品被称作occluder,所以有很多方法就是在考虑如何使用
occlusion culling来提高显示的性能。然而，occlusion culling比起view
frustum culling复杂度上升的太多，直径也很难找到一个很完美的解决方案，
下面我就将现有的一些途径简单的介绍一下：

这些方法都有需要将整个场景进行层次划分(用bsp tree,kd-tree)，分解成
一个个cell。可见性判别的力度往往就是到达cell的级别，你可以根据自己
需要决定cell的粒度来平衡效率。

先介绍run-time的一些方法：

1.基于portal的occlusion culling,
  这是一种基于object space的run-time method,
  这种方法特别适用于全封闭的建筑类场景，洞穴类场景，
  因为这些场景有一个特点，遮挡非常明显，比如一个大楼，
  每个房间（cell)的大部分都被墙壁所遮挡，只能透过少数的门，
  窗看到场景中的其他部分。对于这种场景，我们可以采用如下的方法
  进行有效的culling:
  首先，识别出场景中每个cell的portal(门，窗),
  渲染的时候，找到view point所在的cell,然后view frustum从当前cell开始，
  一次通过该cell的portal来遍历场景，每经过一个portal,  就对view frustum
  进行一些修正，因为这些portal与视点形成更多的限制，直到看不到任何portal
  位置。遍历过的cell就是可见的cell.

  这种方法对于这类场景非常有效，因为通常我们的遍历透过几扇门窗就停止了。
  portal需要事先人工设置，或者用算法自动识别。
  然而对于很多户外场景，很难存在这样的cell和portal,因此对于那些场景这个
  方法就不适用了。

2.single occluder culling
  在portal算法的基础上，这又是一种基于object space的run-time method,
  这种方法可以用于那些有很多高大的遮挡物的场景，比如大都市，高山环绕的场景。
  这些场景的特点是，存在很多单个的高大有效的遮挡物，比如大山，大楼，他们往往
  能够遮挡住viewfrustum中的很多部分。当然对于portal算法对应的室内场景该方
  法也同样适用。算法的过程如下：

  维护一个occluder列表，利用层次性的结构，从视点出发，以从前往后的顺序访问
  各个cell,判断是否被occluder列表中的某个occluder挡住，如果没有对于该cell
  中的物体，判断它是否是比较好的occluder(根据它在是平面上的投影面积等因素）
  ,如果是则加入occluder列表，继续遍历。

  这种方法有时也会采用一些与处理的过程，标记一些物体为好的occluder,或者生成一
些
  virtual occluder(外形更加简单，近似代替一些occluder）,这些都是为了减少运行
时
  选择occluder的时间，以及让occluder的选择更加有效。

  这种方法的缺陷是，无法考虑几个occluder共同的作用效果，有很多东西也许既不能
被
  occluder A挡住，也不能被occluder B挡住，但是有了occluder A和B,你确实看不见
这
  个东西了。所以对于没有非常大的occluder的但是仍然遮挡很密集的场景，比如丛林
  ，这个方法一点用也没有。然而要想在run-time的时候考虑多个occluder共同的影响
  （在object-space中)，是非常难以做到速度的保证（计算的代价太大）。


3.由上面两个例子，可以看出如果可以考虑多个occluder的作用影响，那么viewfrustum
  中的部分就可以限制得非常多，而且也可以处理更加复杂的场景。但是像在object-sp
ace
  中处理这种情况实在是很难以很低的计算代价来获得。因此一些基于image-space的方
法
  就诞生了。最普通的例子就是z-buffer.利用image-space来处理的好处就是image-spa
ce
  的可见性是由有限的元素（屏幕上的像素个数）来决定的，比起object-space有很大
的
  优势。但是依靠z-buffer已经到达了渲染阶段，是不够的。有一种hierarchy
z-buffer的
  做法，也称作z-pyramid,因为它生成一系列的不同精细度的z-buffer,比如，最大的
  z-buffer是32*32的一块suface,那么它生成16*16,4*4,2*2,1*1的另外4级z-buffer,
  每一级z-buffer对应上一级中的四个像素，并且取其中的最远深度。因此我们在绘制
场景
  的时候可以通过层次性结构，从前往后渲染，并且每次可以先拿层次结构中的结点的
  bounding box先进行比较（从最粗的那一级z-buffer开始），那么就可以非常有效的
绘制
  遮挡关系复杂的场景。这种方法我感觉非常有希望，但是唯一不足的是如果没有硬件
的支持，
  考软件的方法来实现这种z-pyramid以及相应的检测，速度还是非常慢的。
  因此我认为如果以后硬件开始很好的支持z-pyramid,那么这会是一个非常好的方法，
  说不定会成为一个标准方法，就像现在的z-buffer那样。

4.image-space确实是一个解决多个occluder共同影响可见性的好途径，但是没有硬件的
支持，
  使得他的效率降低。然而对于某些特殊的环境，可以采用一些特殊的方法，使得我们
也可以
  将objec-space和image-space的方法结合起来从而得到一个比较好的trade off.
  这种场景就是那些2.5d的场景，最常见的就是城市环境。基本上，绝大部分在城市场
景的游戏
  都可以看作是2.5d的环境，可见性的判断只要在2d的基础上考虑一下高度的因素就可
以了。
  因此这里有一个方法可以有效的处理城市的环境。算法如下：
  首先将cell的划分严格限制在平面上（比如水平的地面上），比如256*256个cell的方
格,
  大小和粒度可以根据具体的场景来决定。每个cell记录属于该cell的objects(需要绘
制的），
  以及该cell中最高object的高度。为了提高效率，也需要事先标记一些良好的occlude
r，
  比如各个楼房的正面，不过这里有一个限制，就是occluder必须是垂直于水平面的矩
形。
  有一个surface buffer,比如我们这里的是256*256的一块surface对应各个cell,一开
始该
  surface对应的z-buffer都是0，然后我们根据视点选择附近的一些occluder,可以选择
上百个，
  （这是比object-space方法好的一点，一般的object-space算法只能是用少量的occlu
der),
  将视点与occluder形成的shadow volume以正投影视角（从天空上往地面的方向正投影
）
  渲染在我们的surface上，这样surface对应的z-buffer上就留下了该shadow volume的
高度，
  多个shadow volume的影响只要将他们都渲染到该suface上就可以得到，而且这种渲染
可以使用
  硬件加速，所以可以使用许多occluder.最后对于每个cell的可见性判断，
  只要比较cell的高度和surface中对应的点的z-buffer的高度就可以判断出来了。
  这里还有一点需要改进的是，直接读取z-buffer是非常慢的，所以必须用个比较好的
办法，
  将这种信息转换到surface buffer上，将surface buffer的数据拷贝到系统内存中的
代价要低很多。
  具体做法如下：一开始surface buffer全部清0，对应的z-buffer设置为各个cell的高
度。
  然后关闭z-buffer check和write,现将view frustum以颜色1渲染到surface buffer上
，
  打开z-buffer check,用颜色0渲染shadow volume,最后将surface buffer拷贝到系统
内存，
  数据为1的地方就是可见的cell.
  
  这种方法对于2.5d的城市来说确实是个好办法，不过他也有很多限制，比如对occlude
r的限制，
  你可能不得不为此专门写一个编辑器。对于其他全3d的复杂场景，这种方法也不行了
。

介绍了这些run-time的方法，我们可以看一下很多preprocess的方法，在run-time的时
候计算可见性，
对于一个相当复杂的场景来说，代价确实非常高。而事先计算好可见性的一些方法却可
以取得非常好的效果。
这种方法放弃了计算point to cell的可见性，转而计算cell to cell的可见性，这样虽
然增加了可见部分，
把一些不可见的cell也送入pipeline处理，但是preprocess却不用占用run-time的时间
，这一节省大大提高了
效率，因为在很多最坏的情况下，特别是在处理复杂场景的时候比起run-time就非常具
有优势。

基本的做法是计算出在每个cell中任何一个视点可能看到的其他cell的集合,也叫做PVS
。
运行的时候只要将pvs中的cell同时又处于view frustum中的cell绘制出来就可以了。
然而如何计算出好的pvs却是一件非常复杂的事情。

每个人也有不同的方法，具些简单的例子如下:
1.在portal引擎适用的环境中，利用portal间形成的全影半影来计算pvs
2.在cell的附近，选择一些occluder，然后不断的与周围的某些occluder形成一些
  virtual occluder(可以这挡住一些比较大的范围）,然后再用这些virtual occluder
  去计算对其他cell的可见性。
3.有一种针对2.5d的城市环境的pvs算法，对occluder也仅限于垂直于地面的rectangle,

  基本计算都是在进行2d空间的visibility计算，只在需要的时候才进行高度的检测。

还有其他的一些算法，感觉都非常的复杂，我也还没有完全搞清楚，就不在这里乱说了
。
如果找到什么好办法，再和大家分享。





如果大家想了解各种算法的详细内容，可以通过下面的连接搜索相应的paper
http://citeseer.nj.nec.com/cs
推荐关键字：
visibility preprocess
occlusion culling