第二节 隐藏面剔除
对不可见物体进行剔除是游戏行业为了满足提高画面渲染速度的要求而产生的一项技术，就是在硬件加速技术飞跃发展的今天，虽然现在已经可以完成许多在过去被认为是不可能实现的工作，但是对于隐藏面进行剔除仍是加速图形渲染的一项重要技术。通常当一个游戏运行的时候，它最少需要以每秒30帧的速度运行。在几年前这意味着如果每一帧你渲染的带纹理的多边形数量超过5000个就被认为是不可接受的，而现在几乎所有的商业显卡每一秒都可以渲染几千万个多边形。可是现在仍然需要使用隐藏面剔除这项技术，这是为什么呢？显而易见，对不可见物体渲染以后将会被可见物体遮挡住，这样做无谓的浪费了显卡的带宽，但是同时它也增加了场景的细节，使游戏画面看起来更加吸引人。现在的问题是多大程度上来剔除隐藏的多边形，象view frustum culling和portal渲染这样的技术来剔除一个不可见多边形是非常耗费时间的，用来去做这些计算的CPU时间可以用来完成其它诸如AI或碰撞检测这样的工作，因此开发一个隐藏面剔除算法必须注意到这一点。对于现在的游戏来说几乎没有一个是将每一个隐藏的多边形都进行剔除，而是剔除一个多边形的集合如一个节点或一个物体等等。对于一个单独的多边形它并不进行剔除，因此一个正确的隐藏面剔除方案是允许一定的重复渲染来适当的减少计算量。
当建立一个FPS游戏时进行隐藏面剔除最通常的方法是使用portal渲染。这项技术可以非常充分的利用BSP的优点，但是请注意portal技术并不仅仅只能用于BSP中。Portal技术还可以用来产生一些特效如镜子和监视器等等。
Portal渲染
在这里我将介绍一下portal技术的原理，通常对于一个室内场景来说它可以被描述为由一个个“洞口”相互连接的“房间”组成，这里“洞口”被称为portal而“房间”被称为sector，通常sector被定义为一个“凸”的“闭合”的多边形集合，定义中的“凸”阅读过前面的内容你应当已经能很好的理解了，而“闭合”是什么意思呢？它意味着在sector内部任意连接两个顶点做一条线段，这条线段不会和其它的多边形相交。换句话说如果你想在sector内部任意画一条线段通到sector的外部必定与组成sector的多边形相交。这也意味着连接每一个sector的“洞口”必须被一个组成portal的多边形所填充，而对于放置portal多边形来说你既可以手工放置也可以由程序自动产生，在我讲解这项技术之前我必须提醒一下，由于硬件加速Z缓冲的出现对sector必须为“凸”的限制已经消除，因此有许多游戏引擎已经不再遵守这个标准，但是在这里我还是要对过去的方法进行一下介绍。
一个portal引擎的基本方法是当你通过一个指定观察位置的可视平截体（view frustum）进行渲染时，如果一个portal出现在可视范围内，那么portal将对可视平截体进行剪切，这样与其相连的sector将会通过一个观察位置相同但已经改变过的可视平截体进行渲染。这是一个非常简单而且非常适合进行递归调用的方法，由于可视平截体被portal进行了精确的限制，因此被隐藏的物体可以很简单进行剔除。下面的例图显示了一个portal引擎中的可视平截体是如何被剪切的。
在图中观察者的位置位于V，而初始的可视平截体为F1，当它通过一个portal多边形P1后被P1剪切产生新的可视平截体F2，接着当它通过portal多边形P2、P3后F2被剪切为F3、F4，而F3通过P4后被剪切为F5而F4被剪切为F6。观察这个过程我们可以发现portal技术非常适合进行递归调用。
接着需要考虑的是如何对物体进行拣选剔除，通常对于所有的3D引擎来说都需要通过一系列步骤来加速这个处理过程，回忆一下前面讲解的内容，这个过程首先要计算出物体的“最大包围球”或是“最大包围盒”，它是包含了物体所有顶点的最小包围体，接着用包围体来和“可视平截体”每一个剪切面进行碰撞检测，如果包围体位于每一个剪切面的“反面”那么物体将不会进行渲染，下图显示了这个过程：
图中物体1位于右剪切面的“正面”但位于左剪切面的“反面”因此它将不会被渲染，而物体2不仅位于左剪切面的“正面”而且有一部分位于右剪切面的“正面”因此将会被渲染出来。
Portal技术最初的想法是通过剪切多边形来保证只有物体可见的部分被渲染出来，也就是无效渲染的多边形数量为0。但是现在这种想法被认为不是很理想，因为它无谓的浪费了处理时间。但是由于一个多边形在递归循环过程中将被遍历多次因此我们需要知道在渲染场景时它是否已经被渲染过，一个较好的方法是使用一个帧数来标识这个多边形，这样可以很容易的来描述这个多边形在上一帧是否被渲染过。再看一下图中最右边的墙，它同时通过F5和F6来进行渲染，通过对它进行标识我们可以知道它是否被渲染过，否则就会产生Z缓冲错误。
为了便于在portal引擎中进行渲染我们需要对“可视平截体”进行一下定义，一个“可视平截体”是一个保存了多个剪切面的结构，每一个剪切面的法线都将指向“可视平截体”的内部，因此在它内部将产生一个闭合的锥体。下面的算法显示了如何计算一个多边形是否包含在“可视平截体”的内部。在这个算法中我们使用了一个函数CLASSIFY-POINT，它使用一个剪切面和一个点作为输入参数。
l 函数INSIDE-FRUSTUM
l 参数:
l Frustum ? 用于检测多边形是否位于其中的“可视平截体”。
l Polygon ? 用于检测的多边形。
l 返回值:
l 多边形是否位于“可视平截体”的内部。
l 功能:
l 使用“可视平截体”的每一个剪切面来对多边形的每一个顶点进行检测，如果所有的顶点都位于所有剪切面的“正面”，那么多边形处于“可视平截体”的内部。
INSIDE-FRUSTUM (Frustum, Polygon)
1 for each point Pt in Polygon
2 Inside = true
3 for each plane Pl in Frustum
4 if (CLASSIFY-POINT (Pl, Pt) INFRONT)
5 Inside f false
6 if (Inside)
7 return true
8 return false
在一个portal引擎中它的主渲染函数可以简单的用下面的方法来实现。
函数RENDER-PORTAL-ENGINE
参数:
Sector ? 观察者所处的sector。
ViewFrustum ? 当前的“可视平截体”。
返回值:
None
功能:
渲染portal引擎中的多边形，场景被描述为由多个portal连接的sectors所组成。
RENDER-PORTAL-ENGINE (Sector, ViewFrustum)
1 for each polygon P1 in Sector
2 if (P1是一个portal and INSIDE-FRUSTUM (ViewFrustum, P1))
3 NewFrustum = CLIP-FRUSTUM (ViewFrustum, P1)
4 NewSector = 获得由当前sector通过portal P1相连接的sector
5 RENDER-PORTAL-ENGINE (NewSector, NewFrustum)
6 else if (P1任然没有被渲染)
7 draw P1
8 return
如何放置portal
正如我前面提到的在一个portal引擎中最大的问题就是如何放置portal，如果手工来放置它的话非常花费时间，同时要求地图的设计者有熟练的技巧。因此一个良好的自动放置portal的算法非常有必要，在这里我将要介绍一下关于这方面的几个解决方案，这些方案都使用了BSP。
我介绍的第一个解决方案是由瑞典DICE公司的Andreas Brinck提出的，它的原理非常简单，观察一下一个完整的BSP层次树，可以发现这样一个现象，对于每一个portal来说它必定与BSP层次树中由分割多边形定义的分割面位置相同，因此在相同的位置上我们可以在分割面之外建立一个portal多边形，portal多边形被初始化为一个矩形，这个矩形的大小将超过portal所处的BSP节点的“最大包围盒”的大小，接着将portal多边形放入包含它的节点所位于的子树中，当节点不是叶节点时，那么portal将继续被传送到节点的子树中，这样子节点中的分割面将对它进行分割，而当包含它的节点为叶节点时，它也会被节点中的多边形进行剪切，因为portal初始化的大小超过了节点的范围。当portal被分割后，被分割的两个部分会继续传送到最顶层的节点重复这个过程，而当portal不需要进行分割时，根据它所处于分割面的位置来放置到相应的子节点中，如果位于分割面的“正面”它将被放置在右子树中，而当它位于分割面的“反面”将被放置于左子树中。如果portal正好位于分割面之上它将同时放在左右子树中。
为了方便方便将所有的portal放置到BSP中我们需要定义如何对一个多边形进行分割，为了方便使用我们假设完成这个功能的函数为INTERSECTION-POINT，它将返回一个面与一个线段的交点。
l 函数CLIP-POLYGON
l 参数:
l Clipper ? 去分割其它多边形的多边形或面。
l Polygon ? 被分割的多边形。
l 返回值:
l 被分割后的两个部分。
l 功能:
l 由指定的分割面来分割多边形。如果多边形没有被分割将会返回一个空的多边形。
CLIP-POLYGON (Clipper, Polygon)
1 RightPart = {}
2 LeftPart = {}
3 for each point edge E in Polygon
4 Side1 = CLASSIFY-POINT (Clipper, E.Point1)
5 Side2 = CLASSIFY-POINT (Clipper, E.Point2)
6 if (Side1 Side2 and
Side1 COINCIDING and
Side2 COINCIDING)
7 Ip = INTERSECTION-POINT (Clipper, E)
8 if (Side1 = INFRONT)
9 RightPart = RightPart U E.Point1
10 RightPart = RightPart U Ip
11 LeftPart = LeftPart U Ip
12 LeftPart = Le
