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]

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

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.

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, skipthe 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 !

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

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 !