Tutorial 6: Rendering With Portals

This time we'll finally discuss the techniques used in a Portal Engine. You know from the name of this series that we will be building one of these. So we should really take a close look at its underlying principles: how it works, why it works, and why you'd want to use it. (Actually, a good game engine nowadays shouldn't use only one kind of technique. It should mix and match. So you will see later that our engine uses portal technique to draw rooms -- walls, windows, houses -- and other principles to draw things in rooms -- people, tables, columns. Still later you'll might want to use a landscape engine to draw what you see when you look outside a castle window, for example. The great thing about portal rendering techniques is that they are open to mixing with other techniques.)

Basic Idea:
In a portal engine, the world is divided into sectors. The central idea here is that these sectors are convex. That means that however you look at the sector from the inside, none of the polygons overlap each other. For example, a sphere is a convex sector. The great thing about convex sectors is that you don't have to sort the polygons or anything. You can draw them in any order, and they still won't overlap each other. You can probably already imagine how you could draw different types of rooms as convex sectors.
What happens when you want two rooms? Obviously, when taken together they don't form a convex sector. This is where you use a portal. Imagine a portal as being a window. You can see from one room to the next through the window, and of course you can't see anything not through the window. A portal has vertices like a polygon, but instead of a texture being mapped to it, the vertices are used to set up the planes to "cut" the next room so that only the portion you see through the portal is rendered.

In the room you're in, none of the polygons overlap each other. The polygon with the orange outline in the picture is the portal. It clips the room behind it, then that room is drawn.
And if in the process of drawing the second room you come upon a portal that hasn't been clipped away, you clip the room behind THAT portal and draw it, then return to drawing the second room. You keep recursively drawing rooms through visible portals until there are none left. Then you're done. Think about this process and understand it well.

Technical Details:
Okay, now... remember the viewing pyramid?

Well, clipping to the portal is exactly like that! Imagine that the polygon from which you make the planes isn't the screen, but the portal. And the planes only apply to the room(s) which are rendered THROUGH the portal. (In fact, in your engine you can have the screen be a portal, so the viewing pyramid is then the screen portal's frustrum plus the z=0 plane).

The way clipping to a portal works is: you set up a plane for each side of the portal. If a polygon [in the room being rendered through the portal] is made invisible by any of the planes, it is invisible, and you can discard it. Otherwise, it is at least partly visible. A polygon can be clipped by one or more planes, as clipping is performed first by one plane, then by another and another. Finally, you get only the polygons that are visible through the portal, and those polygons are clipped away so that only the part visible through the portal remains. You can now draw those visible, clipped polygons and be sure that you're exactly "filling in" the portal as you should.

A note on hardware acceleration: with hardware acceleration, it is enough to just see if a polygon is visible or not. You don't actually have to spend the extra time to clip the polygon to a portal frustrum. This is because of z-buffering, which automatically takes care of overlapping. Z-buffering on today's 3D accelerators is faster than your clipping algorithm, so you can avoid the extra optimization work when clipping polygons to portal frustrums and simply leave it to z-buffering. But this is only for portals. For clipping to the z-plane, for example, you will still need to actually CLIP polygons. The same normally goes for the entire viewing pyramid. [And for software rendering you still need to clip, because z-buffering in software is slow.]

Okay, so how do we set up the planes for a particular portal? Remember, the portal can have 3 sides, 4 sides, or 10 sides! Consider that, given a triangle, you can create a plane. That is, you can create a plane from 3 points. So let's set up the planes the straightforward way: consider pairs of vertices for the portal, and create a plane from the two vertices and the eye. Makes sense, right? The plane goes from the eye to the two points, and serves to clip the polygons in the room being rendered. (Think of the viewing pyramid.)

The only problem is, the normal vectors for these planes have to face into the portal, not out of it. This is the case because we are aiming to leave the polygons that are visible through the portal! When we create a plane from a triangle its normal vector can face either way, so we have to choose the normal vector that faces inside. How do we do this? Well, we can do the following:
when you consider each pair of vertices, for example vtx2 and vtx3,
take the average of the vectors (vtx1-vtx2) and (vtx3-vtx2),
and you obtain a vector that points well inside the portal.
If the angle between the plane's normal vector and the "average inside" vector is more than 90 degrees, negate the plane's normal vector to make it point the other way.

Here's an illustration of this:

Alright, now... where should we put portals? Generally you should have in mind large convex sectors for rooms and such. The portals would link these rooms. Think about rooms in Quake... where would you, roughly, put the portals? Don't worry about things in the rooms. We will use another method to render those. The beauty of a portal engine is that you can combine it with other techniques!

Here's a screenshot of a portal engine that I created a while ago. Could this scene be one convex sector? Where would you put portals? (Hint: between the edges of walls?)

We can make much more of our portal engine, but that's enough for this tutorial. We will continue making our engine more interesting in the next tutorial. But I will stop here, because I want you to get a good understanding of exactly how a portal engine works. Remember,
what are convex sectors?
what are portals and how can we use them?
how do we clip rooms to portals?
You should be comfortable with these concepts.

Preview: In the next tutorials we will explore interesting possibilities. We'll discuss things such as: Being less strict about convex sectors. Mixing portal techniques with other stuff. What 'sector' is the player/camera in? Keeping track of sectors and polygons. After you get the hang of that kind of stuff, it gets very interesting. Because using your knowledge you can implement lighting, reflective surfaces, transparent effects like water, halos, and much more!

The Code

Ah, finally you get to see how to get this stuff working. The suspense is over. You missed The Code section, didn't you? Admit it! Well, you're in luck, because this time the code section is large! And important...

First, how can we define a portal structure? Since it contains vertices like a polygon, plus some other stuff, maybe we should make a portal structure contain two pointers to the sectors it links together, and one pointer to the polygon which defines its vertices -- its position. You can have other stuff (a later tutorial talks about engine organization) but this seems like a pretty good definition. Hey, look -- there it is below! ;-)

typedef struct Portal
{
   SECTOR *Sec1, *Sec2;
   POLYGON *Poly;
   int Reserved; // we'll see what this one's for
} PORTAL;

Okay. Now we have a room, and it contains polygons and portals. When we render the room, we will render portals first then the polygons (for reasons covered in later tutorials). So it's good to keep the portals as separate objects in a separate array, since we're going to draw them before polygons. Here is what a sector (synonymous with room) structure contains:

typedef struct Sector
{
   PORTAL *Portals; // Pointer to array of Portals
   POLYGON *Polygons; // Pointer to array of Polygons
   int PortalCount, PolygonCount;
} SECTOR;

(In the engine organization tutorial, we'll find better ways of storing arbitrary numbers of polygons, portals, sectors, rooms, etc... but for now, an array of, say, 100 elements, will be enough.)

Alright, so a sector contains a portal pointer, and a portal contains a sector pointer. How can this be possible? Well, typedef the sector and pointer structures beforehand, without elements. Something like this:
typedef struct Portal PORTAL;
typedef struct Sector SECTOR;
struct Portal { ... };
struct Sector { ... };

If that doesn't work (it is not suported by some older compilers) you can store the index of the sector in an array rather than a pointer to it. The array of sectors will be in the world structure.

Alright, now we have the two structures. How do we implement the drawing of sectors and portals? Well...

int DrawSector(SECTOR *, CAMERA *);
int DrawPortal(PORTAL *, SECTOR *);
int DrawPolygon(POLYGON *); // implemented in previous tutorial :)
PLANE *NewPlane(POINT pt1, POINT pt2, POINT pt3);
PLANE *Planes[100]; // an array of clipping planes
int PlaneCount = 0;
int ClipPolygon(POLYGON *, PLANE *);
int ClipPolygon(POLYGON *);

We have these five functions. DrawPolygon has been implemented in a previous tutorial. So was the first ClipPolygon version. NewPlane has been implemented, but this version takes three points rather than a point and a vector. DrawSector will draw all portals and polygons in the sector. We will maintain a "stack" of planes which will be used for clipping polygons (and portals) before drawing them. DrawPortal will add planes to the stack, call DrawSector, and then remove the planes and return. The second version of the ClipPolygon function will clip a polygon by all the planes in the Planes array.

Portals have an integer member called Reserved, which keeps track of whether the portal has already been drawn. A portal cannot be drawn through itself, because that would lead to an infinite loop. (The case is a bit different with mirrors, in a later tutorial.) So in the beginning we test to see if the portal is already being rendered, by checking if its Reserved value is TRUE. If it's not TRUE, then we make it TRUE, call DrawSector, then make the value FALSE at the end and return. A portal can be rendered twice (the same window rendered through two doors) but it cannot be rendered because of itself (seeing the window in the window). Take a moment to understand that. Anyway, that means that when portals are created, their Reserved variables must be set to FALSE at the beginning.
Here's how we could implement the functions ClipPolygon, DrawSector and DrawPortal:

int ClipPolygon(POLYGON *Poly)
{
   int i;
   for (i=PlaneCount-1; i>=0; i--)
   { // go backwards... from most imposing planes to least, to save work
      ret = ClipPolygon(Poly, Planes[i]);
      if (ret == 0) break;
   }
   return ret;
}

#define CompareCameras(Cam1, Cam2) \
   ((Cam1).x == (Cam2).x) && \
   ((Cam1).y == (Cam2).y) && \
   ((Cam1).z == (Cam2).z) && \
   ((Cam1).yaw == (Cam2).yaw) && \
   ((Cam1).roll == (Cam2).roll) && \
   ((Cam1).pitch == (Cam2).pitch))

int DrawSector(SECTOR *Sec, CAMERA *Cam)
{
   register int i;
   static CAMERA LastCam;

   if (CompareCameras(*Cam, LastCam) == FALSE)
   {  // Camera position changed, translate polygons
      LastCam = Cam;
      for (i=0; i<Sec->PortalCount; i++)
         Wor2Cam(Sec->Portals[i]->Poly);
      for (i=0; i<Sec->PortalCount; i++)
         Wor2Cam(Sec->Polygons + i);
   }

   for (i=0; i<Sec->PortalCount; i++)      // process portals
      if (ClipPolygon(Sec->Portals->Poly))
         if (Sec->Portals[i]->Sec1 == Sec)
            DrawPortal(Sec->Portals + i, Sec->Portals[i].Sec2);
         else
            DrawPortal(Sec->Portals + i, Sec->Portals[i].Sec1);

   for (i=0; i<Sec->PolygonCount; i++)     // draw polygons
      if (ClipPolygon(Sec->Polygons + i))
         DrawPolygon(Sec->Polygons + i);
}

int DrawPortal(PORTAL *Por, SECTOR *Sec)
{
   int i;
   int a, b, c, d;
   VECTOR in;
   PLANE temp;

   if (Por->Reserved) return;
   Por->Reserved = 1;

   for (j=1; j<=Por->Poly->Count; i++)
   {
      a = (j-1) % Por->Poly->Count;
      b = j % Por->Poly->Count;
      c = (j+1) % Por->Poly->Count;
      d = (j+2) % Por->Poly->Count;
      temp = NewPlane(eye, Por->Poly->c[a], Por->Poly->c[b]);
      in.x = (Por->Poly->c[a].x - Por->Poly->c[b].x +
              Por->Poly->c[d].x - Por->Poly->c[c].x) / 2;
      in.y = (Por->Poly->c[a].y - Por->Poly->c[b].y +
              Por->Poly->c[d].y - Por->Poly->c[c].y) / 2;
      in.z = (Por->Poly->c[a].z - Por->Poly->c[b].z +
              Por->Poly->c[d].z - Por->Poly->c[c].z) / 2;
      if (in.x * temp->a + in.y * temp->b + in.z * temp->c < 0)
      {
         temp->a = -temp->a; // reverse the direction of
         temp->b = -temp->b; // the plane's normal vector
         temp->c = -temp->c; // so it points inside the portal
      }
      Planes[PlaneCount++] = temp; // Add the clipping plane
   }

   DrawSector(Sec); // Draw the sector with the extra planes set up

   PlaneCount -= Por->Poly->Count; // Remove the clipping planes
   Por->Reserved = 0; // Allow drawing this portal again
}

You can see the recursion in the above code. DrawSector calls DrawPortal, DrawPortal calls DrawSector, until there are no more portals left to draw. Then the scene is done! :)