*1. What is portal-culling?
*2. Recursive function to get visible sectors
*3. Checking if portals are in your view with a 2D overlap check
*4. View-frustum narrowing
*5. Optimizing with Scissoring
*6. Portals that are partially in front, partially behind the camera
*7. Preventing infinite loops
1. I see what you don't see
The best part about programming is doing the stuff you like, with quick results. Adding the last straws on the other hand... Don't know about you, but in my case it often leads to 90% finished parts. The other 10% is... well, for another day.
Of course, with limited time you can't fine-tune everything till perfection. At the time it's perfect, it's probably also outdated, in this insane fast evolving software world. But sometimes you forget about important missing parts. Now that all Radar Station maps are imported, I noticed a relative low framerate on my laptop (~20 to 24 FPS). Now my laptop isn't the fastest anymore, but suddenly I remembered I didn't finish the portal-culling engine... This particular map has quite a lot of rooms and walls between them, resulting in a lot of overdraw.
For those unfamiliar with (portal)culling, or rendering performance in general, this technique helps preventing stuff from getting rendered for nothing. Unless you are spying or wearing X-Ray goggles, "rendering" the interior of your neighbor’s house is useless, cause you can't see it anyway. Walls and stuff. If we don't cull, invisible parts of the map will be called for nothing, and pixels will be drawn on the screen, and then get overdrawn by something else in front = a waste of time. In an ideal 3D world, each pixel will be drawn only once (asides overlapping pixels with alpha blending enabled).
A deferred-rendering engine already helps reducing the lighting complexity, but when rendering the contents for your deferred pipeline (data textures), shadow/depth Maps or other passes, you still want to exclude rooms you can't see. Or how about rooms you can only see partially? Behind a door or window, there could be st.Paul’s Cathedral. Yet you only see the bits behind the opened doors/windows ("portals").
With portal-culling, you divide your world into rooms, hallways, terrain chunks, or as I would like to call them: “Sectors”. The openings between them (open space, doors, windows, holes, ...) are called "Portals". In a perfect definition of a sector, for each corner(vertex) of a “room”, you can see all other corners of the same room without obstacles between them. But you can cheat a bit of course. Since rendering works best with bigger batches of data, try to prevent ending up with hundreds of tiny sectors. Because you will render sector by sector.
2. Portal Culling recursive function
Before you render your scene, you first have to determine what sectors are visible for the camera. Making such a list isn't that difficult, but it has some tricky (math) catches. Don't worry, my math doesn't go much further than counting potatoes, yet it succeeded. Here a pic, and some pseudo code:
// Make a list of visible sectors
1- Start in the sector your camera(player) is standing. Add to the list
2- FOR EACH portal IN currentSector.portalList
......3- Check if the portal(quad?) is inside/intersecting the camera view-frustum
............4- Add the sector behind the portal to the list, IF not done before.
............ Be aware that the same sector can be visible through multiple portals.
............5- For each sector, manage a list of portals that made it visible. Add ............ this portal to the sectors list.
............6- repeat step 2 for the sector behind the portal
Now when you go rendering your world, just loop through that sector-list. Eventually do it backwards to help with the depth-sorting for alpha-blended/transparent surfaces. The furthest sectors will be rendered first, your current sector last. Oh, and did I mention this "visible sector list" is also handy for other stuff like updating lamps, A.I., and vegetarian cooking? Having a list of visible sectors helps you to exclude unnecessary checks.
Now that's easy, just a recursive function, some looping, little list... done. But wait, as said, there are some catches. Circular references may occur, and how the hell do you know whether a portal is (partially) visible or not? If you are like me, you Googled "triangle sphere collision" and the likes quite some times. But "portal(or quad) versus frustum test" didn't gave me a lot useful results. Mostly you'll need combinations of functions, as collision-test routines are often incomplete. In case your portals are quads, they can be fully inside your camera frustum, intersect it, or completely overlap it (when standing nearby a big portal).
And that's where I didn't finish the code. Just made a cheap check to make sure portals would be visible. But due the margins, invisible sectors still became visible according to the checks. Time for a revision.
3. 3D to 2D
Checking if 3D stuff collides, intersects or overlaps isn't so easy. Narrowing the view-frustum when it travels through a portal neither. Checking if 2D rectangles overlap on the other hand... So why not do the math in 2D? It still has a few flaws, but at least it's an easy way. And a solution that actually works is also worth something right?
So, instead of doing 3D math, we convert the view-frustum and portals to simple 2D rectangles first. Initially, your view covers the entire screen, which means it’s rectangle would have the following coordinates: {-1,-1,+1,+1}. Where -1 is the left or top of the screen, 0,0 the center, and +1 the right or bottom. This conversion still requires a little bit matrix-math though. There are multiple ways to convert a 3D point to 2D, but what I did is using the camera ModelViewProjection (MVP) matrix. Wha? The same matrix you use in vertex shaders to convert 3D points to projection space(ehm... am I saying that right)? You can get this matrix in OpenGL as follow:
// 1. First, make sure your camera is set. For example:
glutLookat( ... ); // Point the camera at a target somewhere
gluPerspective( ratio, fov, near, far );
// 2. Now buy your matrices for only 99 cents
glGetFloatv( GL_MODELVIEW_MATRIX , @modelViewMatrix );
glGetFloatv(GL_PROJECTION_MATRIX , @projectionMatrix );
// Construct the MVP (matrix x matrix)
MVP := matrixMultiply( modelViewMatrix, projectionMatrix );
// 3. Convert a 3D point to 2D with the MVP (matrix * vector)
p2D.xyzw = vectorTransform( MVP, worldPos3D );
p2D.x := p2D.x / p2D.z;
p2D.y := p2D.y / p2D.z;
With this MVP matrix, you can convert 3D points to 2D space, in the range[-1..+1]. If you like, you can multiply further with the screen-resolution to get real screen pixel coordinates, but we don't need that here. Oh, AND your 2D point should also carry a Z. You can use the Z to check whether a point is in front or behind the camera-view frustum.
Testing, testing
PointInsideViewFrustum := (p2D.x >= -1) and (p2D.x <= +1) and
(p2D.y >= -1) and (p2D.y <= +1) and
(p2D.z >= 0);
The -1, +1 are the screen bounds, the Z tells if a point is in front or not. That's how you can check a single point. But, Portals aren't just points right? Portals can be seen as quad (since doors and windows are rectangular). But if you really like, you could also make complex shapes such as... circles, or... kangaroos.
What I do is simplifying the calculation by making simple rectangles out of whatever shape you want to check. First of all, your own view-frustum happens to be a rect; the entire screen. But hold on, your frustum may get narrowed as it passes through portals! (See Scissor chapter below). Next is the portal. Simply loop through all its (vertex) points, convert each one to 2D, and determine the most left/right/top/bottom ones. That makes a rectangle, or 2D “bounding box”.
Sure, rectangles fill more space than, say, a circle. So your portal might become visible even when you can't really look through it yet. But who needs complex portals anyway. Quads, or sets of quads, will do in almost any situation, and keeps the amount of point conversions limited. Asides, it’s wise to have some margin anyway. On top, the usage of rectangles gives an extremely nice bonus-track... but more about that later. Let's show how to do the overlap-check first:
rect1 := viewFrustumRect; // "screen"
rect2 := portalRect;
overlap := (rect1.left < rect2.right) and (rect.right > rect2.left) and
(rect1.bottom < rect2.top) and (rect1.top > rect2.bottom);
Still alive? Bon, because you're almost through the math-part. There is still one nasty bug at this point though, don't raise the flags yet.
* Always expand your portal 2D bounds a little bit to prevent leaky edges.
4. Portal Narrow
We know how to determine whether a portal is visible or not now. But usually a portal is a lot smaller than the sector behind it. Imagine you have a wall with a little Alice-in-Wonderland hole. Although you can fade-out and block the portal after a few meters (use this trick to keep distant sectors hidden), you will still have to render the entire sector behind that hole at some point. And how about the portals in that background sector? Maybe you can't even see them, yet they are in the view-
frustum:
This was one of the reasons why the Radar Station maps went slower and slower. Pretty much all rooms had an opening to another sector somewhere, so at some camera angles, the entire map would be rendered. While you only saw ~35% of it. A waste of precious horsepower.
What we should do, is "narrowing" the view frustum after each portal. That sounds like awful 3D vector math, and, it is. But wait, we worked with 2D rects right? Narrowing the view-frustum is just as easy as using an AND-operator on 2 rects. Well, that still sounds difficult. Look:
narrowFrustum.left := max( previousFrustum.left, portalBounds2D.left );
narrowFrustum.right := min( previousFrustum.right, portalBounds2D.right );
narrowFrustum.bottom := max( previousFrustum.bottom, portalBounds2D.bottom );
narrowFrustum.top := min( previousFrustum.top, portalBounds2D.top );
Just adapt to the portal rect. That's it. In the recursive "PortalCulling" function, narrow the frustum each time it passes through a portal. And don't forget your view might enter the same sector via multiple portals, resulting in different results.
5. Scissor sisters
Narrowing the view prevents portals that are in the view, but occluded by foreground geometry to be evaluated. But it still doesn't fix the huge overdraw when rendering a gigantic sector behind a tiny portal. Call in the Scissor Sisters.
Yet another great feature of 2D rectangles, is... 2D rectangles. In OpenGL, you can tell where to draw by giving up a rectangle, and enabling "scissor testing". Pixels inside the rect will be drawn, others outside will go to the pixel hell.
glScissor( portalBounds2D.left, portalBounds2D.bottom, portalBounds2D.width, portalBounds2D.height );
glEnable( GL_SCISSOR_TEST );
glDisable( GL_SCISSOR_TEST );
This is why I added the portals to a list(per sector) as well in the Portal Culling function. So later on, when looping through that list, just BEFORE rendering the sector, you can setup a scissor. In case you found multiple portals you might activate multiple scissor rects (not sure if this is possible), or just combine the portals to make 1 bigger rect. Don't always hurt yourself with math, enjoy life. With a scissor enabled on the portal, only the visible part of a sector will be drawn, no matter how !#@$ big it was.
However, it does not prevent the render-calls. All triangles / objects inside that sector will be pushed, the scissor just discards pixels that didn't fall inside the rectangle. If you have massive amounts of objects / vertex-data, you may want to split up the sector in smaller chunks. And don't forget about LOD systems. Portal Culling can help a lot, but still doesn't make your game fly of course. Games like Crysis or GTA use lower-poly meshes or even sprite billboards for distant objects.
6. The exceptionals; portals partial behind / in front of the camera
So far, so good. I would almost throw the portal-culling code asides again, leaving it "95% done". If it wasn't there is a not-to-ignore bug still present. How to handle with portals that are (partially) behind the camera? Take this scenario:
Two or only one point of the (quad) portal are in front of the camera, and will produce normal 2D coordinates. The other points are somewhere behind the camera. Math wouldn't be math if there wasn't always an annoying exception on the rule. If all points still had a positive Z value, there is nothing to worry about. The portal rectangle will be partially outside the screen-bounds, but that doesn't give any problems. But in this case, the rear-portal points have a negative Z value. So, when doing the division with Z, the X and Y coordinates will get mirrored too.
This makes a wrong rectangle. Luckily, there is an easy fix. I’m not 100% sure if this is the best way, but I did it anyway. And so far it works:
p2D.x /= p2D.z;
p2D.y /= p2D.z;
if (p2D.z < 0) then begin
if (p2D.x > 0) then p2D.x := -1.0 - p2D.x else // Put it left from the left side of the screen
p2D.x := +1.0 - p2D.x;
if (p2D.y > 0) then p2D.y := -1.0 - p2D.y else // Put it below the bottom of the screen
p2D.y := +1.0 - p2D.y;
end;
Now just make a rect out of all portal points and test it with the view frustum rect as usual, but be prepared for one exception:
if ALL points were negative, the test failed. At least 1 point has to be in the foreground. If you forget this, portals behind you can get visible as well.
7. Loop-back / Circular referencing
A problem with checking visible portals/sectors, especially with the 2D overlap check, is that we may get stuck in infinite loops, or lack info about which portals made a sector visible. Take this scenario:
In this particular case, first the room behind the 3 windows will be checked. This room has a door that leads to a toilet on the right. This toilet has another door that leads back into the big-room we started from. Although the toilet exit door is in front of the background room door, all their 2D rects will overlap (one shortcomings of doing 2D checks). In other words, after our toilet visit in the recursive functions, we get back to the main-room.
This isn't so bad, but we have to be careful not to add the room twice. But neither should we stop as soon as we detect an already-inserted room. Since we entered the room via a different route, it may show other portals that weren't visible before. This gives yet another problems: infinite loops.
To prevent walking circles, you can block portals. Once checked, they can't be checked again. But… this leads to wrong scissor-rects though, or even missing sectors. In complex situations, the same portal might be visible through multiple foreground portals. Each "route" can lead to different results, and will also produce a different scissor-rectangle. Crikey, how to deal with that? Not blocking means infinite loops. Blocking means incomplete data.
So instead of just blocking a sector or portal right away, I look if the sector was already made visible by a(nother) portal with equal or a bigger overlapping rectangle than the current one. Ifso, no need to check. Because it can't produce new results anyway.
Well, enough Portal Culling. The 2D approach has some flaws and still can evaluate portals that aren't really visible for the camera. Yet it's a relative simple (and fast) way to do culling. Just make sure your loop really checks all scenario's, in case parts of the scene are missing.
