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:
- They're stubborn conservatives who like "the old way" of doing things.
- 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:

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.
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.

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
|