Unite 2010GDC ChinaAsia Game Show 2010GDC 2011
|
Cell-based occlusion cullingAs good as view frustum and back-face culling are, they still can't sufficiently reduce polygon counts in modern games. Thus, we turn our attention to occlusion culling, which, as the name suggests, attempts to identify the visible parts of the scene, thus reducing the number of primitives rendered. First of all we cover cell-based methods. All cell-based occlusion culling methods are based on the assumpion that the game world can be divided to cells which are connected to each other using portals. Clearly, if a portal is not seen from a given point of view, then none of the cells behind the portal can be seen and they can thus be culled away. There are two dominating forms of cell-based engines in use today: BSP and "portal" engines. BSP stands for Binary Space Partitioning. In Binary Space Partitioning, space is split with a plane to two halfspaces, which are again recursively split. This can be used to force a strict back-to-front drawing ordering (for more details, see [FDFH90]). Occlusion culling in BSP engines, such as Quake, is usually based on the Potentially Visible Set (PVS). This means that, for every cell in the world, the engine finds all the other cells that are potentially visible from the cell, from any point in the cell. [Tel92] details how to find this PVS analytically. Then, at rendering time, the cell where the viewer is located is found, view frustum culling is performed for the cells in the PVS, and finally those cells that reside in the PVS and inside the frustum are drawn. This introduces several major concepts. PVS-based culling is conservative: it always overestimates the set of visible cells, never underestimates it. This means that no artifacts due to objects that weren't drawn even though they should have been can occur. Further, as we know from Quake, calculating the PVS can take quite a bit of time. Thus, an expensive preprocessing step is traded for fast displaying speed. There is still overdraw, however, meaning that redundant polygons are drawn; this is due to the fact that PVS contains all the cells that can be seen from anywhere in the viewing cell. The overdraw typically ranges from 50% to 150%. A more recent form of cell-based occlusion culling is present in so-called "portal" engines. The world is again defined as cells and portals connecting them. At runtime, the cell where the viewer is in is found. Then, all portals in the viewing cell are tested against the view frustum planes and accepted, discarded, or clipped as necessary. Those that are either wholly or partially inside the frustum are recursively traversed, so that, mathematically speaking, the planes that define the portal polygon's boundaries are added as clipping planes, so that the new set of clipping planes define a smaller and smaller portion of the screen. This solution leads to exactly 0% overdraw for the world geometry thanks to the analytical clipping performed. It is thus well suited for software rendering. However, analytical clipping is expensive. Thus, the projected bounding rectangle of the portal polygons can be used instead, as detailed in [LG95], to provide an approximation for discarding portals. Portal engines have the advantage that no preprocessing step is required and that scenes can be very dynamic as no PVS is present. Also, "unnatural" space-warping effects are possible. The disadvantage is potentially larger CPU overhead for portal culling at runtime, especially in complex scenes. Recently portals have only been reserved for special effects in industry-strength engines, so that the eventual value of the dynamic portal approach is unclear. Clearly, cell engines are only suited for scenes where large occluders, such as walls, are present. Thus, they make excellent high-performance indoor engines for games. |
|||||||||||
|
|||||||||||
