Handling large indoor levels is part of creating a good game engine. There is a difference between the types of optimizations for indoor and outdoor levels. For indoor levels occlusion culling is incredibly important. For outdoor levels, level-of-detail type optimizations are more important. Of course it's best to always use both. In this article I present an overview of portal occlusion culling. I considered describing details and alternative methods, but this article already ended up longer than I expected.

When using portal-based occlusion, you first divide a level into separate sectors ( I call them sectors here, although you could call them zones, sectors, chunks, segments, or anything else. ) Then you create portals linking together two different sectors. The portals themselves might be represented by rectangular plane segments. Any view between sectors that isn't linked together by a portal is considered occluded.

When writing a 3d program, view frustum culling would be the first optimization on my list, and it's important everywhere. I'm assuming readers will have some familiarity with this one. If an object is beyond a plane of the view frustum, it won't be visible, and we can safely discard it. For example, if there's a chair object behind you, it will be behind the near plane, and quickly discarded.

Every object in the world should use the same bounding class. In fact, what I use is similar to the class in my bounding box article, only with some more optimizations, and a few more functions. We can loop through all the objects in our world, and mark any within the view frustum as visible, then render visible objects.

With portals, instead of having just having a list of all the objects in the world, we use separate sectors, and have a list of objects in each sector. One way to decide which objects are in a sector is by using one or more bounding boxes to define the area of a sector, then testing the bound box of an object against the sector bound box. This can be calculated very quickly, and only needs to be recalculated if an object( or sector ) moves.

There are some issues at sector boundaries to be aware of. An object needs to be in at least one sector for portal based calculations to be meaningful. We can allow sectors to overlap, and objects to be in multiple sectors at the same time. At a sector boundary an object will be in multiple sectors, but since we're just setting a visible flag, it's okay for it to be marked as visible by either or both sectors.

When rendering a frame, we start by finding which sector the camera is in, and loop through each object in that sector checking if it's in the view frustum. Once we're done with that, we need to check if any portals leading from this sector are within the view frustum (note: we can use the same test for portals that we do for objects.) For any visible portals, we can calculate another frustum for the view through that portal from the camera position. We then render the sector that the portal leads to, repeating the process recursively.

It's important to minimize the number of lights affecting an object. The first thing to do is set a light influence radius for each light, but in a crowded indoor level if that's all you do, your lights will hit a lot of objects that they shouldn't hit because they're on the opposite side of a wall.

In the first phase we'll want to quickly discard any lights that can't contribute to the rendered scene. In the view frustum culling phase, we've marked all the sectors that are in the view. For each light, we can mark which sectors it hits. If it doesn't hit any sectors that are visible, we can discard this light completely.

If the light isn't discarded, we need to mark which objects are in the light. This process is similar to the visibility process described under the portal occlusion culling heading. The main difference is that instead of starting out with a view frustum, we start with no frustums. ( At least for omni-directional lights, projector spotlights will have a frustum. ) Portals can still create frustums. Additionally, with lights we need to remember to test objects and portals against the light radius.

There are 2 cases where you don't need to calculate shadow visibility. The first is that if the light doesn't hit the object, then it won't have shadow at all; ie. we just need to loop through the objects in the light. The second is that if an object itself is visible, then we know that the shadow is also visible. If neither of these 2 conditions are met, we'll need to do some calculation.

The shadows themselves create a frustum. First, if an object's shadow frustum is not within the view frustum, then we can skip shadow calculations on this object. Second, we can find which sectors a shadow is in by testing to see if the shadow frustum intersects any portals leading to new sectors, and skip the shadow if it doesn't hit any visible sectors.

The main thing to remember is that we don't want to do any needless work. If an object isn't visible, we don't want to render it or do any rendering related work. The main reasons an object won't be visible are either occlusion, or that it's outside the view frustum. We also want to check for occlusion and use influence radius to avoid any needless light-object interactions. An object's shadow might be visible even if the object isn't, but occlusion testing for shadows is equally important. One way to perform occlusion testing is using sectors and portals. I've found a large indoor level that runs between 50-250 frames per second with portal-based occlusion testing, might in some places run below 5 frames per second without it.

Category: Topic Overview
Articles in this category: Optimizing Code, The Hard Part, Coding Style, Using C++, Writing Tutorials, Villager's Tale, Engine Architecture #1