culling:一种高效的基于大规模地形场景的OCCLUSION CULLING算法

　　对于通用场景来说我以前介绍区间扫描线Z缓冲器算法可以剔除大部分不可见物体但是在基于heightmap大规模地形场景下会发现作用不是太大区间扫描线Z缓冲器算法需要在场景中手工指定occluderoccluder必须为规则物体而在地形场景中这种occluder非常少也就是场景中建筑物的类物体实际上地形场景中最适合作为occluder是连绵起伏丘陵、山脉它遮挡住了场景中大部分物体但是区间扫描线Z缓冲器算法对这种情况下OC就无能为力了需要使用其它算法进行OC计算现在网上完全公开适用于地形场景OC技术主要有以下几种:

Voxelcolumnculling、Hierarchicalvisibility、incrementalhorizon这些算法都需要进行些预处理其中最流行是incrementalhorizon(增量地平线)技术这种技术要求在渲染前对每个地形块计算个潜在轮廓线在渲染时将这些潜在轮廓线合并为地平线进行OC处理由于这种算法需要进行预处理因此也不太适用游戏开发此后我自己又开发了个realtime计算incrementalhorizon算法但是发现开销太大根本无法用于realtimerendering(和PascalJunod在论文ImplementationofaO(na(n)log(n))PoVisibilityAlgorithmonDigitalTerrainModels中使用算法相同这篇论文我也是后来才发现有兴趣可以翻看下我以前在gameres发表文章)

下面列出是网上相关论文有兴趣可以自己看下

LloydB,EgbertP.Horizonocclusioncullingforreal-timerenderingofhierarchicalterrains.In:GrossM,JoyKI,MoorheadRJ,eds.Proc.oftheIEEEVisualization.Boston:IEEEComputerSocietyPress,2002.403-410.
StewartJ.Hierarchicalvisibilityerrains.In:DorseyJ,SlusallekP,eds.EurographicsWorkshoponRendering.Vienna:Springer-Verlag,1997.217-228.

ZauggB,EgbertP.Voxelcolumnculling:Occlusioncullingforlargeterrainmodels.In:EbertD,FavreJM,PeikertR,eds.Proc.oftheJoEurographics-IEEETCVGSymp.onVisualization.Vienna:Springer-Verlag,2001.85-93.StewartJ.Fasthorizoncomputationatallposofaterrainwithvisibilityandshadingapplication.IEEETrans.onVisualizationandComputerGraphics,1998,4(1):82-93.

DanielArchambault.AlltheDistantHorizonEdgesofaTerrain.B.Sc.(Hons.)inComputingScience,Queen’sUniversity(Kingston),2001PascalJunod.ImplementationofaO(na(n)log(n))PoVisibilityAlgorithmonDigitalTerrainModels.October1999

　　后来我仔细观察farcryeditorsandbox经过差不多两个多月试验终于开发出个可以realtime运行用于地形环境OC算法这个算法开销非常小经过我在OGRE平台上试验此算法可以做到非常精确剔除FPS提升明显由于这个算法核心是线段求交因此我暂时称其为线段求交OC算法

在介绍这个算法前先明确下坐标系张heightmap行为X列为Y高度方向为Z
先考虑单点OC情况如下图所示:
P
|
|C
A-------------------B
|
|
O
假设planeAB为个occluderO为camera位置如果要判断点P是否被AB遮挡只需要简单判断线段OP是否和occluderAB相交即可如果存在相交点C则点P即被遮挡问题被简化为线段和平面求交下面继续考虑在地形环境下如何简化这个问题在地形环境下heightmap每行和列都可以看作个occluder这里假设AB为行或列相临两个顶点组成线段如果要判断点P是否被AB遮挡可以通过比较交点C在线段OP和线段AB上z值来确定:

Zc_op>Zc_ab点P没有被线段AB遮挡

Zc_op<=Zc_ab点P被线段AB遮挡

现在检查点P是否被遮挡在地形环境下简化为个简单2D线段求交问题这也是本算法的所以高效原因

下面继续来看下如何将算法由个点推广到整个地形在基于heightmap地形系统中通常将地形分成块块小tile根据LOD算法区别tile大小可以为17*17或者33*33不等这里假设使用17*17tile

首先来看如何剔除场景中被遮挡tile对于tile来说如果所有顶点都位于其前方行和列下方那么它定被遮挡换句更精确定义对于tile每个顶点如果和camera所在位置所形成线段全部和位于tile和camera的间行或列中任意条线段相交那么可以确认tile被完全遮挡

按照上面定义个tile如果被检查到完全遮挡需要检查17*17=289次虽然2D线段求交运算开销非常小但是个tile就需要进行289次运算仍然是不可接受需要更简化算法考虑下区间扫描线Z缓冲器算法occludee使用都是物体AABB是否可以使用tileAABB进行运算呢？由于地形环境性质可以不用考虑AABB最下面 4个顶点但是直接使用AABB最上面 4个顶点进行运算绝对不行如图所示:




screen.width-333) {this.width=screen.width-333;this.title=\'open window\';}\" _disibledevent=>
4个顶点虽然被完全遮挡但是occludee并没有被完全遮挡如果解决这个问题需

要将AABBup表面分割成16*16格子这样话运算次数并没有发生变化
这里可以使用个取巧思路方法如下图所示:
screen.width-333) {this.width=screen.width-333;this.title=\'open window\';}\" _disibledevent=>

将AABB投影到camera空间直接获得线段AB将AB线段16等分获得17个新顶点注意这些顶点z值全部相等现在ocludee是否可见只需要检查17次就可以了

下面看下算法复杂度对于个完全遮挡tile只需要进行17个顶点计算完全未遮挡tile只需要计算个顶点部分遮挡tile大约是2-16个顶点左右由于tile在进行OC运算的前首先要做frustumculling剔除被frustumcullingtile然后剔除那些没有被遮挡tile实际上运算量非常少

注意这里每个顶点计算不是指简单17次线段求教运算,根据tile距离camera位置远近每个顶点求交数量是不样,例如下图所示:

screen.width-333) {this.width=screen.width-333;this.title=\'open window\';}\" _disibledevent=>
图中线段OA需要检查 3条行和列,共是 6个交点,需要进行 6次线段求交运算.

对于场景中模型进行OC运算时也需要按照上面思路方法将模型AABB变换到camera空间获取条occludee线段然后根据地形相临顶点的间距离确定顶点数

使用这个算法和区间扫描线Z缓冲器算法相配合可以获得在室外场景中最大限度剔除被遮挡物体先用线段相交OC算法剔除被地表遮挡tile和模型然后用区间扫描线Z缓冲器算法剔除被建筑物遮挡tile和模型完美室外场景OC解决方案verynice！！！！

原创文章,转载请注明出处!!!!!!!

线段相交OC算法演示下载(使用OGRE平台运行前先看readme文件):

http://www.cnblogs.com/dreams/archive/2007/03/26/688650.html
这是我新blog,呵呵.

延伸阅读

• 2009-2-12-- occlusion:Occlusion Cull