[subheading]Regular Joe says:[/subheading]

[font="Arial"]Now we've done all our pre-processing, it's time to talk about the runtime stuff - actually rendering with this cell and portal graph.
We know that the cells in our world graph are convex, so we can safely assume that all surface geometry in the same cell as the camera is 'potentially visible'.
It's hardly even worth testing them against the view frustum - we can just go ahead and draw these polygons. More technically challenging are the portals.
The cell our camera is in contains one or more portals to other cells - if none of them are currently visible, then our job is done.
However, if a portal is visible, then some of the surfaces of the cell it leads to are visible as well...
The portal rendering algorithm involves recursively visiting the cells which are connected to visible portals.
Basically, the idea is to refine our view frustum, traditionally done by clipping it to the shape of visible portals, essentially 'shattering' the view frustum into 'frustlets'.
We recurse each connected cell, with the clipped 'frustlet' as input frustum.
I have included some 'programmer art' conveying this concept, sorry if it's crap.

[subheading]Let's redefine the problem[/subheading]
Unless your portals are all regular rectangles, it can be expensive to clip the 3D geometry repeatedly against portal silhouettes.. However we can go some way to reduce the pain by avoiding all the clipping operations entirely.

Let's look at what we are really trying to do.
We are trying to find the extruded intersection of each portal with the current cell's 'input frustlet'.
This is the same as the projection of the portal's geometry from its current location, onto the view frustum's near and far planes.
This tapered extrusion is the 'frustlet' we are looking for - all we need is a cheap way of projecting the portal from its current position onto the near/far planes, and then find the planes of the tapered surfaces (cost of one crossproduct per portal edge).
So the only remaining problem seems to be how to project an arbitrary point inside the view frustum onto its near/far planes.
We already have a matrix that can transform a WorldSpace point into ScreenSpace, which effectively projects world points onto the Near frustum plane.
That's ALMOST what we want! We could probably find a way to use it. Instead, we'll directly use the stuff it contains.

Wouldn't it be nice if we could find some way of Scaling the portal vertices up and down for a given frustum 'depth' ?
We can borrow some stuff normally used for 'screen ray picking'.
First, we will calculate the 2D coefficients of the input point with respect to the camera view:
[/font][font="Arial"]

dx=tanf(FOV*0.5f)*(x/WIDTH_DIV_2-1.0f)/ASPECT;
dy=tanf(FOV*0.5f)*(1.0f-y/HEIGHT_DIV_2);

Note that the tangents here can be pre-calculated if your projection matrix is not changing (which would be the normal case).

Now we can easily find the projection of the input point on the near and far planes as:

nearPoint=D3DVECTOR(dx*NEAR,dy*NEAR,NEAR);
farPoint =D3DVECTOR(dx*FAR,dy*FAR,FAR);

Hmm, wait, that will give us the Point relative to a camera with identity transform - we still need to transform the point into camera view space, unless we're happy to do our calculations relative to the camera view

We can construct a geometric primitive from the portal vertices' near and far plane projections, and from them, we can find the 'unknown planes' formed between the near and far projections of the portal vertices... we now have created one 'frustlet', which extends from the near plane to the far plane, and is the shape of the portal.


I know, it still sounds like a lot of work! However I believe it will end up being much cheaper than the traditional 'subtractive solid geometry' method of slicing up the original frustum, and discarding the occluded portions.




[subheading]Rendering Algorithm:[/subheading]


So, given the current cell (which contains the camera) and the current view frustum as input 'frustlet A', for each visible portal, construct a 'frustlet B' from the input 'frustlet A' and the portal, then recurse the cell which is behind that portal, passing in 'frustlet B'.

Since all our 'frustlets' share the same near and far planes (ie, those of the camera view frustum), this recursion is automatically bounded by the view depth - it will stop when we get far enough away from the camera.

Now, in order to ensure correct drawing order for our polygons, we simply defer the rendering of the polygons until the recursion is 'returning' as follows:




-For each Portal in this cell
--If Portal is Visible, Calculate Frustlet and recurse adjacent cell

-EndFor


-Draw polygons in this cell

-Return from recursion



This ensures that polygons are drawn on the 'way back', ie deepest recursed cells are drawn first, and the current cell is drawn last.




As mentioned, there will be some MINOR overdraw, which could be virtually eliminated if we add the step of testing polygons against the frustlets before drawing them, however I see this as prohibitively expensive (we shouldn't be culling at the polygon level on the cpu), and find the amount of expected overdraw acceptable.










[/font]