Portal rendering

In the previous issue of this column, I introduced a few visibility determination algorithms. This issue will discuss the portal rendering algorithm, as I will use it in Untitled-3D, in more detail.

I'll start by giving a more detailed explanation of the basic portal rendering algorithm. Afterwards, I will discuss the variation that I intend to use in Untitled-3D.

• Basic portal rendering

To do portal rendering, you must first subdivide your world into convex subsectors. These sectors should then be connected by portals. When you want to render your world, you start in the sector where the viewer is located. If this sector has any portals in it, and these portals are visible to the viewer, than the sectors behind the portals are processed first. When moving from one sector to the next, the portal that led you to the next sector should be used to clip other portals against. The following figure may help:

The black outline is the room you are in. The blue lines are portals. I've numbered them in the first figure for convenience. The red dot is the viewpoint and the arrow indicates the viewing direction. Finally, the green lines indicate the field of view. This will be used for the clipping only - after step 1 it is not the "real" field of view anymore. Now, in the first step the viewer is facing a wall and he sees portal 1 on the left. This means the engine processes the sector behind that portal. To do so, the field of view is adjusted. Anything that is not visible through portal 1 is clipped.

Using the new field of view, portals 2 and 3 both become visible. Suppose you start at the top and process the sector behind portal 3. There are no other portals visible, so the sector is just rendered, and processing can continue with portal 2. Again, there are no visible portals behind portal 2, so the sector is rendered. Having processed all the portals behind portal 1, that sector is also rendered and you're back where you started: the sector that has the viewer. There was only one portal in it, so now it can be rendered, too.

Note that this was not a very good example, because you still ended up drawing all the sectors. The following example can eliminate some sectors:

If you follow the algorithm as described above, you'll see that the most distant sector will never be drawn, regardless of the viewing direction. Note that you can still clip polygons and portals against the original field of view as well, to further reduce the polygon counts and eliminate a lot more sectors.

• Sector subdivision

One of the biggest problems when doing portal rendering, is the placement of portals. The need for convex sectors can create a lot of portals. That's why you'll need a way to place portals automatically. Failing that, you might want to consider using concave sectors. Convex sectors are really only useful because they can be drawn without polygon sorting. Hardware rasterizers can just as easily cope with concave sectors, though, so your portal counts can be reduced drastically. In Untitled-3D, I intend to use the concave sector approach. Of course, if you use concave sectors and transparent surfaces, you need to sort polygons back-to-front before drawing them. That's why Untitled-3D will build a BSP tree for each sector. It may sound complicated, but this solution makes it more feasible to place portals manually.

If you absolutely have to place portals automatically, you can use a number of approaches. The most common approach seems to be the use of a leafy BSP tree, where the nodes of the tree don't store polygon information (just splitting planes), and the leaves store convex groups of polygons. Portals can then be found by creating polygons on the splitting planes. If you are interested, there are some worthwhile discussions on the subject on flipCode (check Harmless' column), and I think there's also some useful stuff over at gameprog.com.

• Polygon sorting

If you're going to use concave sectors in your portal renderer, you'll need some polygon sorting algorithm to draw your sectors. If you don't sort, translucent surfaces can and will be rendered incorrectly. Untitled-3D will use a BSP tree for each sector. Special care has to be taken when working with moving objects, though. Ideally, these objects' polygons should be included in the BSP tree, but this would require the BSP to be rebuilt at run-time. Due to the time complexity of the BSP algorithm, this isn't really an option. If you're using a hardware rasterizer, such as OpenGL, you can let the Z-buffer handle moving objects. You still have to watch your step with those translucent surfaces though. You'd have to render using the following steps:

  - traverse the BSP tree drawing only opaque polygons
  - render any moving objects
  - mark the Z-buffer read-only (glDepthMask() in OpenGL)
  - traverse the BSP again, but this time rendering only translucent surfaces
  - re-enable the Z-buffer for the next time around

This way, everything should render correctly. There's one tiny little problem left: your moving objects can't be transparent. This is generally not an issue, though. If you want to use sprites for weapon effects, for example, this problem doesn't arise because a sprite is only a single polygon, and so it can't suffer from polygon sorting issues.

• Conclusion

The basic portal rendering algorithm is far from perfect. Using concave sectors can eliminate some of the biggest problems, though: you don't need as many portals anymore, and as such you don't need to find ways to place them automatically. Concave sectors do bring up the need for polygon sorting, but I've covered that as well.

Delphi3d.net was written and maintained by Tom Nuydens.
Best viewed in 800x600 @ 16 bpp or better.