Portal Rendering

BSP algorithms are a very efficient way of computing visibility in occluded environments. But they are not the only way of achieving interactive frame rates with indoors data sets. A completely different approach, called portal rendering, has been evolving through the years, offering a similar performance with a different approach. A variant of this algorithm was used in the Unreal engine and has gained widespread acceptance since then. Like BSPs, it allows programmers to paint only what is effectively seen. Unlike BSPs, the world hierarchy is not automatically computed, and visibility is computed in real time, not preprocessed.

I will begin by describing the data structure used to perform the portal visibility checking, and then move on to the algorithms. Portal rendering is based on the concept that the game world is divided into cells or rooms connected by doors or portals. Thus, our game world is really a list of rooms; each one connected to other rooms by a number of portals. It is a very human and logical way of laying out the game level. If you think about it, you will see that the data structure that more closely resembles this one is the nondirected graph (see Figure 13.11). Each room is considered a graph node, and each portal is represented by an edge between two rooms or graph nodes. The only difference with regular graphs is that two rooms can be directly connected with more than one portal (imagine two rooms with two windows separating them). Thus, our graph must allow two connected nodes to have any number of edges between them.

Figure 13.11. Map and graph.

Each room will hold its geometrical data and a tight bounding volume (a convex hull is a good choice) to test whether the player is effectively inside the room. Some portal implementations, especially the older ones, need the rooms to be convex. Later versions of the technique remove this restriction and handle concave rooms as well. Whichever you choose, keep in mind you need a bounding volume that can perform a precise player-in-room test. Thus, concave rooms will require a more complex point inclusion test. Check out Chapter 22, "Geometrical Algorithms," for more information on geometric tests.

Once the room structure is defined, we need to specify a list of portals emanating from it. For each portal, we will need links to both rooms connected by it and the geometry of the polygon that describes the portal shape. Portal polygons can be concave or convex, although some implementations impose some restrictions on their shape. Some use four-sided portals only, others force them to be all convex, and so on. By using the portals along with the associated rooms, we need to be able to traverse the game level much like a walking character would do, moving through the rooms using the doors that connect them. This is the core of any portal rendering algorithm.

The data structures that support the portal rendering algorithm are usually created by hand in the content development phase. The world editing tool must allow designers to cut geometry into pieces, place portals, and so on. In this respect, portal rendering is a bit more complex than BSP handling, where the world hierarchy is created automatically. However, this complexity will result in many advantages in the long run.

It is now time to move on to the painting algorithm. Portal systems do not store precomputed visibility tables like some BSPs do. They resolve visibility queries at runtime using the portals to cull away unseen geometry. We begin by using the bounding volumes of the different rooms (either individually or using some hierarchy) to detect the room the camera is standing in. This room will be the starting point of the rendering algorithm. Then, we paint the room geometry, locate any visible portals, and move on to the rooms connected to them. For this second-level of rooms, we clip geometry through the portals, test whether there is any second-level portal that can still be seen, and so on. We will recursively explore the game level as long as new portals are still visible. When no more portals can be seen, the rendering routine will return (see Figure 13.12).

Figure 13.12. Recursive portal rendering.

The main difficulty in portal rendering is learning how to use portals as clipping volumes. We need to detect which triangles are seen through them, what part of a portal is visible through another portal, and so on. The main tool for the job will be a variant of the view frustum, which we will call the portal frustum a frustum that emanates at the camera position and passes through the portal's vertices. This type of frustum can be used to test for inclusion of triangles inside the portal and only paint those that are effectively inside. But wait, there's more. We can intersect two portal frustums to compute the part of a second-level portal that is visible through a first-level portal. Frustum-based computations are the meat of any good portal rendering system. They are the core routines that make the algorithm complex and also determine the final performance of the technique.

Now, let's take a look at different strategies regarding frustums that have been used throughout the years. I will start with a perfect, general-case frustum analyzer and then present optimized, more restrictive options.

In a general case, a portal can have any number of vertices and be both convex and concave. Intersecting two such portals is thus a case of 2D shape intersection. We start by projecting both portals to 2D window coordinates. This way the test only needs to handle the X and Y coordinates, simplifying some math. Then, to compute the test, we start with the first vertex of portal P1 and follow the sequence of vertices used in the portal definition. For each vertex, we do a point-in polygon with P2. Clearly, those points that are part of P2 will be part of the intersection. But there's more: Imagine an edge composed by two subsequent vertices. The first vertex on the sequence is not in P2, but the second vertex is. This case represents an edge that crossed P2's boundaries. Thus, we need to compute the intersection between that segment and P2, and store the intersection point in the result as well. In addition, we need to test the opposite case. If a point is outside P2 but the previous point in sequence was inside, we need to compute the intersection again and store that point. If you do this until you have cycled P1, the resulting list will contain the new portal (or nothing if there was no intersection). Here is the pseudocode for the algorithm in full:

 portal intersect(portal p1, portal p2) { list<points> result; bool previnside=false; if p2.contains(p1.vertices[p1.numvertices-1])    {    previnside=true;    } for (i=0;i<p1.numvertices;i++)    {    curinside= p2.contains(p1.vertices[i]);    if (curinside)    result.push_back(p1.vertices[i]);    if ((previnside && !curinside) || (!previnside && curinside))       {       int aux=i-1;       if (aux<0) aux+=p1.numvertices;       point inter=compute_intersection(p1.vertices[aux], p1.vertices[i], p2);       result.push_back(inter);       }    previnside=curinside;    } portal presult(result); return presult; } 

Notice how we take special measures to guarantee that we cycle through the array. Thus, we begin by initializing the previous value to that of the last vertex to check the segment formed by the last and the first vertex.

However, this is not a fast routine. Each call is linear to the number of vertices in P2, and the intersection test is not much better. Remember that this must be recomputed per frame, so we might not reach the desired performance with such a complex test. Thus, faster alternatives must be devised.

A popular choice was proposed by Luebke and Georges. Using their method, we don't use the portal, but instead use the screen-aligned 2D bounding box of the portal, making the portal intersection routine very straightforward. Intersecting screen-aligned boxes is just a matter of selecting the right X and Y values through very simple tests, and thus the routine is significantly sped up. The downside is precision. The resulting bounding box will be bigger than the portal it contains; and some tests that should return a negative value will return a positive value, as if a fragment or triangle were actually visible.

However, in modern-day hardware, rendering some extra triangles comes at no additional cost, so we should not worry about this. Remember, most geometry data structures are usually grouped together (like all triangles in a room, for example). A vertex buffer or vertex arrays in OpenGL will be prebuilt for each room. So, the effort of classifying triangles one by one will clearly not pay off in the long run, and a gross visibility test such as the one we have just proposed will be perfect.

Optical Effects Using Portals

One of the main advantages of portal rendering is that optical effects such as reflections and translucency can be elegantly implemented on top of the core algorithm. This was first showcased in games such as Epic's Unreal. All you have to do is enrich the portal data structure, so a portal can be much more than a simple door. It can be a mirror, a glass surface, and many other surreal effects you can think of.

Take reflections, for example. Any optics manual will tell you that looking at a mirror is, in practical terms, equivalent to looking at the same room from a virtual position that is the specular reflection of your position through the mirror. That is, if you look at a mirror at a 45° angle from five meters away, the scene you will see in the mirror is exactly the same scene a viewer located five meters away inside the mirror would see. Feeling like Alice in Wonderland? Check out Figure 13.13 for a visual explanation.

Figure 13.13. Mirrors on portals.

So, implementing a reflection is only a matter of having a special kind of portal that connects a room with itself while inverting the viewing matrices in the process. A general portal structure that incorporates this optical phenomenon would be as follows:

 class portal    {    point *vertices;    int numvertices;    int type;    roomid room1,room2;    }; 

where type would store the type of portal that is, regular, reflective, or translucent. Remember that both room identifiers for reflective portals would be the same, because a mirror does not really connect two rooms. Then, the portal propagation code would be something like this:

 switch (type)    {    case REGULAR:       {       // Paint destination room of the portal       break;       }    case REFLECTIVE:       {       // calculate the virtual camera using the support plane of the portal       // invert viewing matrices       // Paint destination room of the portal       // paint portal using alpha blend if you need a "stained glass" effect       break;       }    case TRANSLUCENT:       {       // Paint destination room of the portal       // paint portal using alpha blend if you need a "stained glass" effect       break;       }    } 

The amount of code needed to implement these great looking effects is minimal, keeping the overall elegance of the portal approach.