1、引言（Introduction）
3D场景中的对象通常存储在一个场景图里，并由树结构负责划分它们的层次。最简单的场景渲染方法就是从照相机的视角出发，遍历整个树（从根处开始递归直到处理完所有的分支），然后绘制每个可见或者局部可见的对象。一个对象是否可见取决于它的包围盒（沿坐标轴的包围盒，是个球体或其它什么东西）是否由部分进入了相机的视锥体。
The objects of a 3D scene are generally stored in a scene graph, a tree structure intended to form them into a hierarchy. The most simple way to render the scene, like it is viewed from a camera, involves traversing the whole tree (= start from its root, go recursively down each branch, sub-branch, etc), and draw every object that is totally or partially visible. An object is considered 'visible' when its bounding volume (AABB, sphere or whatever) is at least partly contained in the view frustum of the camera.
这个（太）简单的方法有两个主要缺点：
This (too) simple method has two major drawbacks :
遍历整个图的花销很大（尤其当图很大以至于不能全部存入缓冲区的时候）。实际上，算法根本没有必要完全处理每个分枝：假如图的节点的包围体（包括节点的所有子节点以及它包含的对象）在视锥以外，因为子节点都不可见，就没有处理的必要。
the traversal of the whole graph takes a significant amount of time (especially since the graph probably can't entirely stay in the cache). Actually the algorithm doesn't need to explore every branch till its end : if the bounding volume of a graph's node (= volume that includes all children of this node as well as the objects it contains) is outside the view frustum, it is unnecessary to go down further as every child node is invisible.
重复的画工作量比较大。理想的话，屏幕上面的每个像素最好只画一次。重复的画就是指一些不同的对象互相重叠，因此一些完全被挡住的面也画了。重复的画的工作量是用被挡住的而且画了的像素（画的像素数目减去实际可见的像素数目得到得值）除以可见的像素。最优的值是0。如果每一帧一个像素平均画两次也是合理的。但是如果次数还要多就不行了。不考虑面的问题，一个明显的优化算法就是监测完全被其他物体挡住的物体，这些物体不需要着色。但是这种监测是很复杂的（因为物体又复杂的形状，不能用包围盒来代替，因为包围盒包括的范围比物体本身大）所以我们反其道而行之，监测可以看到别的物体的区域，例如在相邻的空间里面。
overdraw can be large. Ideally, each pixel of the screen should be drawn only once per rendering of the scene ; overdraw names the fact that things can be different, that some visible objects cover each other, that some completely masked faces are drawn for nothing. Overdraw is generally measured by dividing the number of pixels drawn 'for nothing' (= number of pixels drawn minus number of really visible pixels) by the number of visible pixels ; its optimal value is so zero, it is reasonable till 1 (= for each frame a pixel is drawn twice on average), and becomes problematic for bigger values. Without going down to the face level, an obvious optimization would consist in detecting the objects that are completely hidden by others, and not rendering them at all ; these occlusion tests are unfortunately quite complex (because objects have complex shapes, and can't be replaced by their bounding volumes that mask inevitably more things than they do themselves). This is why it is better to do the opposite : detect areas allowing to see 'somewhere else', for example in the neighbouring room, thanks to portals.
图1 模板深度的例程
该“模板深度”例程源于DirectX 8，其显示了重画：红色象素部分只画一次，绿色象素部分画两次，黄色象素部分画三次，蓝色象素部分画四次。
"stencil depth" sample from DirectX 8, showing overdraw : - in red the pixels drawn once - in green the pixels drawn twice - in yellow the pixels drawn 3 times - in blue the pixels drawn 4 times.
2、什么是入口？（What is a portal ?）
这里有两个不同的定义：
There are two different definitions :
一些人（我也这么看）认为入口是一个n个边的平面凸多边形，在渲染时进行特殊处理。它的目的不是被绘制，而是定义一个区域。穿过这个区域你可以从一个地方到达另外一个地方（例如：两个房子之间的门、窗口、及墙上的洞…）。这是一种特殊的视角：例如在一个房内的一架照相机正在“看着”房间入口处，也就意味着它可看到入口的另一面的区域。入口只是在两个图节点之间建立链接，而没有其它的必然关系。
for some people (and I belong to this group) a portal is a n-sided flat and convex polygon, handled in a special way at rendering time. Its goal is actually not to be drawn, but to define an area 'you' can cross to go from one place to another in the level (example : a door between two rooms, a window, a hole in a wall...). 'You' means vision in particular : if a camera in a room 'is seeing' a portal of this room, this means it can also see what is 'on the other side' of the portal. A portal establishes a link between two graph nodes, that don't necessarily have any other relation.
一些人则认为场景被划分为较小部分的多边形，所以叫其（这些块）做入口。他们的“入口”与我的“房间” 定义相符，他们不再是多边形而是有体积了，根据处理目的的不同它们可能是凹的或者凸的（凹多面体一般都可以细分为几个单独的凸多面体）。我会在后面详细分析凹凸多面体的概念因为这是很重要的。现在我们讨论入口的定义：这里入口表示一个平面的凸多边形，其他的文献中可能表示场景中间的一个基本的空间或者单元。
other people consider those polygons divide the scene in small parts, and they call these pieces portals. So their 'portals' correspond to my 'rooms', they are no more polygons but volumes, they can be convex or concave depending on the pursued aim (a concave volume can always be subdivided into several all convex volumes). I will precise this concept of convex / concave volumes later because it's very important, for the moment let's come back to our definition of the portal : in this whole document it means my n-sided flat and convex polygon, but be aware that in other texts it can represent an elementary volume of the scene (or 'cell').
让我们以一个房间为例：图的根节点代表这整个的房子，根节点下面的每个节点是一个房间，每个房间包含家具，在家具上有物体等等。演示程序中就是这么做的：首先是“初层”节点（假定根为0层）代表各房间或走廊，它的孩子是放置在房间里的对象（例如在中间的房子里有：四面墙、一面天花板、一面地板、一架楼梯、一座喷泉、二个粒子系统、一盏灯 ― 由于门是房子之间的边界所以有点特殊）。入门就是房间或走廊的毗邻处的“洞”，它们的形状和过道正好相符合的（简单的矩形）。
Let's take the example of a house : the graph root represents this whole house, each node under the root is a room, each room contains furniture, in pieces of furniture there are objects, etc. This is the same thing in the demo #3 of Fairy : the 'first level' nodes (if the root is the 0-level) each represent a room or a corridor, their children are the objects placed in this room (for example in the central room : 4 'wall' objects, 1 ceiling, 1 floor, 1 staircase, 1 fountain, 2 particle systems, 1 light - the doors' case is a bit special because they are at the borderline between two rooms). Portals are placed on each 'hole' allowing to go to the neighbouring room or corridor, their shapes fit exactly those of the passages (simple rectangles).
注意：因为门是多边形，它们可以用“标准”的面来保存，用一个标志表示是否需要进行不同的处理，如果把门都放在在一个单独的链表中会更加简单一些，特别是当它们包括了附加的信息，就像我们在后面会看到的。
Note : because portals are polygons, they could be stored with 'normal' faces, a flag indicating they have to be treated differently ; however it is simpler to keep them in a separate list, especially as they can contain additional informations as we are going to see later.
例如：我房间的平面草图。
example : rough plan of my flat (inaccurate scale)
图2 我房间的平面草图
A：卧室（bedroom）1 ― B：卧室（bedr
