The Render Process

The rendering speed depends on how many entities, polygons, and pixels are actually drawn on the screen. This can be influenced by the user through reducing the number of entities in the level, and the number of their poygons. And it can be affected by the engine through removing as many objects as possible before drawing the rest. This process is called Scene Management, Visibility Determination, Hidden Surface Removal, or briefly Culling. Whatever the name, the goal is always the same: Prevent as many pixels as possible from reaching the screen.

There are several scene management methods. One of the oldest scene managers was the Octree system. An Octree splits the world in 8 rectangular regions, each of which contains 8 smaller regions. This process is repeated until the final regions are so small that they only contain a single object. The renderer then only renders the regions that are in the view area of the camera. The octree algorithm can not cull hidden objects, but is simple to implement and doesn't require a level compilation process. Due to their simplicity, octrees are still used by many 3D engines today. However, octrees don't care about which parts of the level were hidden behind walls or other objects. Thus better scene managers were developed.

The BSP tree system splits the level into irregular regions defined by the level geometry, and only renders the parts that are really visible. This is the fastest and most effective system, especially for indoor levels. With a BSP tree system, the indoor rendering speed is independent of the level size, which allows decent frame rates even on old PCs. But BSP trees have the disadvantage that they must be precalculated by a map compiler in the level editor.

Most high-end engines today use a BSP tree scene management with a PVS visibility set. This kind of tree algorithm, BSP/PVS in short, is the most effective way today for detecting whether an object is hidden or not. It's explained in more detail in the next section. Simple engines usually contain an Octree or another geometry-independent tree system. For outdoor levels, where a BSP tree offers little advantage over an Octree, a LOD (Level-Of-Detail - see Entities) system is used for keeping the frame rate high. It automatically switches to 'simpler' shapes of objects when they are far away from the camera, thus reducing the overall number of polygons drawn per frame.

The BSP tree

A Binary Space Partition tree, or BSP tree for short, is basically a method of splitting the world up into manageable chunks which can then be dealt with individually. Chunks not visible on the screen are early removed from the rendering process. Thus a BSP tree is vital in speeding up rendering, but can also support lighting calculations and collision detection, and performs a pre-sorting of objects due to their distance to the screen.

Beginning with the center of the level, the map is first split into two regions along a wall. One side is called the front region, the other the back region. Then the process happens again, except this time it is done on each of the front and back regions, treating each region like a different map. This keeps happening until the world is split up enough (determined by the compiler). We now end up with a hierarchical list of regions - that's our BSP tree. The engine keeps a track of what was split up from what, thus every region in the tree knows by which regions it is enclosed. As only level blocks are used for splitting, entities placed in the map have no influence on the BSP tree.

The connection between two regions is called a portal. They are the mysterious portals indicated by the map compiling process. But we are not finished yet. Once we've split up the world in regions, the map compiler visits all regions of the tree and determines which regions are visible from that region. For every region it generates a list of every other potentially visible region in the world. This list is called the Potentially Visible Set, or PVS. As you can appreciate, this is a complex process, which is why the map compiler takes a long time for calculate the PVS with complicated maps.

A8 The A8 engine supports special portals that are controlled by script. For this, rectangular portal regions can be placed in WED. Such a region, when activated with a script command, culls all its objects from the PVS. This can be used for disabling the rendering of objects inside a room or building as long as the camera is outside or the doors are closed.

When rendering a frame, the engine loops through the BSP regions to find out which region the camera is currently in. Once it's found it, it uses the PVS to find out what regions might be seen from there, and tosses out the regions that can't be seen under any circumstance - including all objects in those regions. This is a very effective form of visibility determination and can remove up to 90% of all objects, depending on the level architecture.

The Adaptive Binary Tree

An Adaptive Binary Tree, or ABT in short, is the most effective way for a scene management without a precalculated tree. It works similar to an Octree, but adapts the region sizes to the geometry and entity distribution of the level. An ABT is calculated in real time, thus level compilation is a lot faster due to omission of the BSP/PVS process. Although less effective than a BSP tree, it can offer almost the same performance in outdoor levels. The engine automatically uses an ABT for levels that don't contain a precalculated BSP tree. Engine versions below  P  don't support BSP and always use an ABT even when the level is compiled in BSP mode.

Further hazards in a pixel's way

After sorting the objects in the scene, and removing the hidden objects through the BSP/PVS algorithm, the engine next determines which of the potentially visible objects are within the view frustum. The view frustum is the area in front of the camera which the player can see. Anything completely outside of this area cannot be seen by the player. For normal views, the view frustum looks like a pyramid with the top chopped off; for isometric views it looks like a rectangular prism.

Any entity outside the frustum is marked with the CLIPPED flag that can be used in the script for preventing time consuming actions. Any object remaining in the view frustum is really rendered by the engine. This includes objects that are only partially inside the frustum (otherwise you would see them 'pop' at the far clipping range), and even polygons facing away from the camera (backface culling). Old engines, like A4 and A5, had extra clipping stages for removing non-visible polygons. Because today polygon clipping is done by the 3D hardware, those extra steps would slow down the rendering remarkably (up to 40%). Modern engines like A6 render objects as a whole polygon mesh, and don't care about clipping single polygons.

If an object has LOD stages, they are now selected due to its distance. The rendering then occurs in several passes. First the solid objects are drawn, then shadow volumes, then transparent objects, then stencil shadows, and finally the sky. Before rendering, solid objects are sorted front-to-back, transparent objects back-to-front. This has the advantage that pixels of solid objects early fill the z buffer - see below - and prevent costly shader operations of hidden objects.

The 3D hardware takes care of last culling stages. The hardware determines which polygons are outside the frustum or facing away from the camera (they are ignored), and which are partially or fully inside the frustum (they are clipped and then rendered). Finally, every single pixel of every polygon is compared with the distance of the pixel that's already drawn on the screen. If the distance is greater, the pixel is not drawn. This process is called z-buffer clipping. It can save a lot of rendering time especially when pixel shaders are used and thus every pixel requires a small program for drawing.

'Transparency' is not what you think

Translucent or transparent objects (see Transparency) rendered by a 3D engine behave slightly different than in real life. The main reason for this is that they aren't z-buffer clipped, otherwise you wouldn't be able to see through them. So this step is omitted on the transparent pass, causing the typical sorting errors within polygons of non-convex transparent objects, and the typical frustration of newbies who are not yet familiar with 3D engines.

The two sorted entity lists of the solid and the transparent passes are available through the ent_pvs function. Transparent entities can be forced in the solid pass through the PASS_SOLID flag. Entities with transparent and intransparent skin parts are rendered in both passes (transparent and intransparent). This allows to have an entity with transparent parts without sorting errors on its intransparent parts.

Objects
ABT or BSP/PVS
Frustum (Engine)
LOD
Solid Pass

Transparent Pass

Front-to-Back Sorting
Back-to-Front Sorting
Frustum (Hardware)
Frustum (Hardware)
Backface
Backface

Z Buffer
Screen
Screen

In the above diagram everything that the engine (software) does is marked blue, and the processes occurring in hardware are marked red. The engine acts on the objects level, and the hardware acts on the mesh, polygon, and pixel level.

► latest version online