Sign in to follow this  
jfdegbo

PVS : Portal Culling and Recursion

Recommended Posts

Hello, i've been working on portal culling ; very standard method : I draw the room where the player is. For each drawed rooms, i check all the portals this room has and if a portal is visible across a 2D rectangle, i render the room on the other side of this portal passing the passed rectangle clipped with the portal's rectangle. The rectangle is initially the entire screen. The first problem is obvious : we have to check for loops. Thus we introduce a flag, telling if a room has already been considered, if it is the case, we skip it. The real problem is described by this simple example : ... As you can see there are some loops possible. Here is what happens with the above method :
Player is in A -> A is drawed
A's portals : [ 1, 2 ]
  portal 1 is visible, so let's draw B
    B's portals : [ 1, 3 ]
      portal 1 is visible, so let's draw A
        A has already been seen, skip it
      portal 3 is visible, let's draw C
        C's portals : [ 2, 3, 4 ]
          portal 2 is not visible through 3, skip
          portal 3 is visible, let's draw B
            B has already been seen, skip
          portal 4 is not visible through 3, skip
  portal 2 is visible, let's draw C
    C has already been seen, skip

the end
Fact is that we missed the draw of room D wich is visible !!! I'm looking for a very simple solution, if there's one. This is realtime culling... How does (for example DOOM3) handle this ? Thanks for your time ! [Edited by - jfdegbo on September 19, 2008 7:06:15 AM]

Share this post


Link to post
Share on other sites
Instead flagging a room, you could flag a portal. Rooms can be visible through multiple portals, eventually via multiple sectors as well.

Loop through your portals and flag them. Now it can happen that you add a sector twice or more. Therefore you use another flag to tell if the sector already has been added. If you encounter a room that has already been inserted, just proceed like normal, except don't add it twice.

So, as for your picture:

1.- Add Room A
< check all portals in room A >
2.- Portal (1)AB has not been checked yet, look into room B
3.- room B has not been added yet, add room B to the PVS
4.- Portal (3)BC has not been checked yet, look into room C
5.- room C has not been added yet, add room C to the PVS
6.- You can't see anymore portals via portal AB > BC in room C
>> Back to room A, next portal (2) AC
7.- room C has already been added. DONT add it again. However, you didn't check
all the portals there yet, so proceed.
8.- Portal (4) CD has not been checked yet, look into room D
9.- room D has not been added yet, add room D
10.- No more portals in room D, back to room C

11.- Don't know exactly how you check if a portal is inside your frustum, but it could be possible that portal (3) CB will be checked. This one has already been flagged before in step 4 though, so you can skip it.

greetings,
Rick

Share this post


Link to post
Share on other sites
It's been ages since I did portal stuff, but IIRC I built a list of visible rooms and their transformation and stopped when duplicates are found. You do your usual traversal of the portals (probably depth-first since that's easiest), and find the cumulative transformation applied by the current path of portals. Then you check to see if that particular room/transformation pair is already in your "to draw" list, and if it's not then add it. If it's already present then you've done with this room and return to the parent.

You need to store the transformation/room pair as otherwise you can't do neat rendering tricks like recursive rooms and other "impossible" room layouts.

Edit: I missed the bit where you're doing proper clipping of portals to each other. In that case I think you should always keep traversing the graph until you find no portals are currently visible. In your example that means you'll visit C twice, and the second time you'll correctly add D.

Share this post


Link to post
Share on other sites
Thank you Rick, this works... in a way.

OrangyTang : i'm not sure i understand what you mean by "transformation"...

But i have another problem.
When considering a portal p2 through a portal p1, i do the following : (very standard stuff, too :))
* project p1 vertices according to camera
* create the bounding rectangle of the projected 2D vertices
* do the same for p2
* clip p2's 2D rectangle inside p1's 2D rectangle

if the resulting clip is not a line or a point, then p2 is visible through p1.


Now, here's the problem :
If room A and B have two adjacent portals 1 & 2 leading to each other, ie A -1-> B -2-> A and B has a single portal 3 to room C


A
-1- -2-
B
-3-
C


If we are in A, we could have the following situation scenario :


add A
portal 1 not checked
add B
portal 1 checked, skip
portal 2 can be seen through 1 (because 2d overlap), not checked
room A already seen, all portals checked, skip
portal 3 not visible from 1 (could be like that)
portal 2 checked, skip

the end


we missed portal 3 that was possible to be seen through 2

Is it very wrong to do 2D clipping for portals ? I am missing anything ?
Thanks again !

Share this post


Link to post
Share on other sites
I believe my solution won't have that problem, as you'll just visit B twice, and C will be added correctly. Then you trim your list of duplicates so you don't draw B twice.

When I say transformations, it's usual to attach a matrix transform to each portal so you can do spatial tricks like infinite corridors or mirrors. If you're not up to that yet then you can ignore it (for a regular map like your examples all transformations would be the identity matrix).

Share this post


Link to post
Share on other sites
Well, I think you are right.
I've tested this and it works. I finally did some sort of (very optimized) stack of traversal with state restoration, and this seems to work perfectly.

thank you both for your advices and time !

Share this post


Link to post
Share on other sites

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

Sign in to follow this