• entries
    26
  • comments
    42
  • views
    22707

Optimized portal rendering

Sign in to follow this  
__Homer__

491 views

[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]
Sign in to follow this  


4 Comments


Recommended Comments

Hello,

First of all, congrats on the excellent posts on Portals & Co. I've done some work on this topic myself, but ended up not implementing any of my notes (the notes are still kept, though, as I intend to get back to this someday).

Here's for something I'm not quite sure about:

[quote]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.[/quote]

Then you explain how to do the "frustlet" extrusion thing and all, cool. But won't this only work if a given portal fits entirely inside a given "frustlet"? In this case, I agree that the intersection is the extrusion you talk about.

But what if a given "frustlet" is small enough that it could "pass through" a portal? (Like a tunnel). The intersection is the current "frustlet" itself, no clipping! What about partial intersections, where you (should) clip some of the "frustlet" and the rest of the planes come from the portal?

Of course, I'm not sure I understand perfectly what you were trying to say here, so I'm just trying to clarify that :).

Also, as I mentioned, I've done some past work on this, and at the time I considered a good idea to force all portals to be rectangular, to simplify things a bit. Even if a doorway is modeled like a circle, for instance, make the portal geometry be the minimal rectangle that contains it, and use that. In practice, the "shape precision" you loose might not be very significant. Also, this would optimize some cases like a set of lots of small windows, grouped together - instead of lots of tiny portals, group them all and make one big one. Unless your objects on the other side are really small, you're not going to change the visible set that much, no?

Anyway, my humble thoughts for your work there, keep it up!

Share this comment


Link to comment
Hi, thanks for the feedback.
Frustlets are actually generated from the geometry of each visible portal, they describe the part of the frustum which is poking through a portal, and so are exactly the same shape as the portal's outline (noting that portals are 2D polygons built apon 3D planes). The only tricky part is that the input frustum changes at each recursion level: for the local cell, we use the full camera view frustum as the input frustum.. if we can see a portal, we use it to create a small frustum that is the shape of the portal and which represents a clipped-down version of the input frustum, and then we recurse the connected leaf node (subspace), using that small frustum (frustlet) as the input frustum.
Clipping 3D objects is expensive, so trimming down the frustum to fit a portal costs a lot, I have simply recognized that we already have the portal geometry, and can use this to create the part of the frustum that would fit through it.

Share this comment


Link to comment
My point exactly:

[quote]Frustlets are actually generated from the geometry of each visible portal, they describe the part of the frustum which is poking through a portal, and so are exactly the same shape as the portal's outline (noting that portals are 2D polygons built apon 3D planes).[/quote]

and

[quote]if we can see a portal, we use it to create a small frustum that is the shape of the portal and which represents a clipped-down version of the input frustum, and then we recurse the connected leaf node (subspace), using that small frustum (frustlet) as the input frustum.[/quote]

I can see this working perfectly if, at any given recursion level, a portal is completely "in view" of the current frustlet. The part I'm not sure I understand is when a portal is only partially in view of the current frustlet. The correct extrusion would take into account the visible part of the portal *and* a part that should be clipped. The other case I mentioned is when a portal is big enough (and the frustlet small enough) that it cannot "fit" in full view "inside" the frustlet, so the extrusion would be the current frustlet itself and not the portal extrusion, no?

I imagine you're talking about saving some of the clipping work by using the "already extruded" visible portal parts, right? But what about a part of it that might be out of view? How do you identify that?

Cheers!

Share this comment


Link to comment
Well, the answer to that is not quite straightforward unless we can say with certainty what the maximum dimensions of a portal can be... if we can determine a nice value for that (through empirical observation of the typical portal bounds as we discovered them), then one solution is to extend the upper, lower and side walls (ie offset the planes) of the original input (camera's view) frustum by that value in each planar direction, and finally, to ignore portals which are only partly visible in this expanded frustum (since they are not even partly visible in the genuine frustum until they are completely visible in this expanded frustum).
The 'hungry volume' approach is used in some physics engines in their collision detection, sometimes known as a 'margin' or 'expanded boundary'.
The idea is to add some stability to simulations by adding a 'grey area' or 'fuzzy logic' or 'uncertainty' to the equation.
It's the method I've considered using, however I am sure it's not the only way to fly.
The alternative method which I will implementing first though, is to simply handle partly visible portals as if they were fully visible - generate the frustlet even though it somewhat extends beyond the bounds of the frustum (note - 'just a bit') - and continue as usual, noting that we will now be throwing a few redundant (ie, offscreen) triangles at the gpu (it's a small number, and probably acceptable).

Share this comment


Link to comment

Create an account or sign in to comment

You need to be a member in order to leave a comment

Create an account

Sign up for a new account in our community. It's easy!

Register a new account

Sign in

Already have an account? Sign in here.

Sign In Now