Table of Contents

3D
Creating a cutting-edge engine
  01 - Design document
  02 - Overall structure

  03 - Binary Space Partitioning
  04 - Constrctive Solid Geometry
  05 - Portals
  06 - Possible Visible Set
  07 - Radiosity lighting
  08 - Mirrors

Dictionary of 3D terms

OTHER
A Genetic Algorithm
Line drawing
Line clipping
Line antialiasing
Line thickening
Line curving

Resources in print
Resources on the web
Resources to download

Excellent, dude.
Keanu Reves at his finest.
We need to go back - to the future!
Time travel 101: Be born in an 80's scifi movie.
05 - Portals
A lot of people like writing 3D engines in C and they're really proud of the fact. I think the reasons are two fold:
  1. They're stubborn conservatives who like "the old way" of doing things.
  2. They've never worked with portals.
For OOP programers, portals can be coded in a remarkably small ammount of time. For the rest of you, Ha ha! Why does OOP give such an advantage? Portals reuse all the basic polygon code. Can you say "derived class?" When I realized that fact I went one step further and made a class for polygons and two derived classes, one for texture mapped polygons and one for portals.


As I mentioned at the end of Constructive Solid Geometry it is possible to write an entire engine using nothing more than portals, but that's an excercise for another day. We're going to use portals to reduce rasterizer overdraw to zero and in the following sections we'll recycle them to do a whole bunch of other EXCELLENT things.


But what exactly are portals? Consider this simple BSP model:

a simple BSP


Each red line is on a BSP node plane. However, each red line is also the location of a portal. The portals are transparent polygons that describe the area in a model where each node touches another. Every portal contains information on the leaf nodes it is sandwiched between and so for the remainder of these pages I will reffer to portals by the nodes they touch. So portal (1,2) touches both node 1 and node 2 however there is no guarantee that node 1 is in front of the portal.

Using portals is really easy, it's the building of portals that can stump a lot of people. The most important thing to note is that every portal in on a node plane. This suggests that we'd want a recursive function. The second thing to note is that the shape of the portals can be described by the polygons in the model, which means it can be described by the nodes in the model. Since every node that has a portal must have both a front and a back it can be shown that the nodes required to clip a portal are the front and back child nodes of the node that shares the plane of the portal. In english that means we're looking at a recursive function inside a recursive function.

node::BuildPortal() {
  // leaf nodes can't have polygons
  if( this node is missing front and back children )
    return;
  // Nodes with no back child can't pass between
  // two interior convex sections.  Since all
  // node planes come from a polygon, the case of
  // a node with no front child will never happen.
  if( this node has a back child ) {
    Build an initial portal on the plane of this polygon
    Recursively clip the portal against the front tree
      (CSG-style).  When a portal fragment gets to a
      leaf store a refrence to that leaf in the fragment.
    Recursively clip the portal against the back tree
      (CSG-style).  When a portal fragment gets to a
      leaf store a refrence that leaf in the fragment.
    Delete all fragments that end on the back side of
      a node.
    Add the remaining fragments to the master portal list.
  }
  if( inside ) inside->BuildPortal();
  if( outside ) outside->BuildPortal();
}

Note: I find it also helps (for speed reasons) to store in each node a list of all the portals touching that node.

This leaves us with one really important part, building the initial portal. We'll NEED an initial portal that is big enough to encompass all the areas where interior nodes touch. Fortunately we've got the node plane and the node boundings.

The plane in the bounding box.



We have a plane P and a box of dimensions maxP and minP. What we want to find are the four points where the plane meets the corners of the box (P0, P1, P2 and P3). Really the next steps are very easy.

// We're assuming Pn is the plane normal.
// Find point Cp in the portal boundaries on the plane.
Cb = ( maxP + minP ) / 2.
dist = Cb dot product with Pn
Cp = Pn * -dist;

// Find vectors U and V orthogonal to Pn.
A.x = A.y = A.z = 0;
if( Pn.y > Pn.z ) {
  if( Pn.z > Pn.x ) A.x = 1;
  else A.z = 1;
} else if( Pn.y > Pn.x ) A.x = 1;
else A.y = 1;

U = A cross product with Pn.
normalize U.
V = U cross product with Pn.

// scale the U and V.  This is the cheap 'n' easy way.
U *= boundingSphere.radius;
V *= boundingSphere.radius;

// now calculate the corners.
P0 = Cp + U + V;
P1 = Cp + U + V;
P2 = Cp - U - V;
P3 = Cp - U + V;
Ta da! All done.

I promised I'd show you how to reduce overdraw to zero. Geeze, I bring it on myself. I should say near zero because even with this system there are still a few tiny slivers. It's the old addage "build an idiot proof machine and someone will notice the polygons overlap", you know what I mean? Since it's 0330 where I live, I'll be brief: Start each frame with a 2D portal the size of the renering area and store it in, say, pClipPortals. At each step in the BSP tree walk-to-render, transform the polygons to screen coordinates and clip them to the portals in pClipPortals. Then transform any portals touching the current node and clip pClipPortals to the new portals if and only if they overlap.

Valid 2D Portal/Portal clipping
A remains untouched, B is clipped by the new portal C to produce D.




Unfortunately, Portal generation is one of those things that are annoyingly hard to debug. If you've written CSG operations you might have a bit of a better feel for what kinds of problems you'll encounter. Me myself personally, I wrote my CSG code to use node-based trees and my Portal generation used leaf-based trees. So there wasn't much crossover. As long as you have a good poly/poly clipping system set up, you can reuse that to save yourself a ton of work and potential debugging. Remember: the error cannot be in the code you've proven works, so recycled code is your friend for more reasons that just saving you time.


The difference between this system and a portal engine is that a portal engine dosen't have a BSP tree. Yes, it has more flexible levels that you can modify on-the-fly. No, it probably won't run as fast and it will be a very different story when it comes to portal generation.

Yaay, that's all done and over with. *phew*. We've seen how to generate the initial portal on each plane and how to reduce those initial portals to the absolutely smallest size possible. Next we're going to take those portals and do a really great speed enhancement that'll impress all your friends.

Back to the top
PREV: Constructive Solid Geometry
NEXT: Possible Visible Set



All photos copyright of their respective owners. All other content of this website is © 1997-1999 Dan Royer.
Designed for IE 5.0+, 800x600x16 or greater. Some pages use style sheets.
http://members.home.com/droyer/index.html