Sunday, December 14, 2008

Portals

hi, this time i had to recreate my portals visibility system, why? well i had some nasty bug that pop out when doing my pvs (possible visibility set) on complicated levels with lots of portals crossing each other.
i will try to explain the problem so when you see one you could attack it :)
little info about portals for some of you who don't familiar with it.
portals is related to visibility system because they help to cull scene areas, how?
think for a moment on a door that connecting two rooms room A and room B, if you stand in room A and looking through the door you only can a portion of room B.
now if you doesn't look through the door, you probably wont see room B (if you cant see the door, you cant see the room/s it leads to)
so portals basically hand placed (can be places automatically) in few places (not just corridors) as convex polygons (usually quads).
now, when you want to know which areas are visible, you start from camera area and check which portals inside this area, for each portal you clip your current frustum planes (the camera planes) against the portal and check again with the new clipped planes as the new frustum (yes its recursive function) and so on and on for each portal until there is nothing to see/visit.
now each portal you enter lead you to a new area so you flag this area so you know it is visible.
after you quit this function you end up with a list of areas that are potentially visible from camera area. this is the basic idea but few trick here and there could do this faster!
now that you know whats portals, i try to explain why i think recursive function for portals visibility are not so good in complicating levels with lots of portals!
the thing is that every portal you pass, the current frustum get clipped and pass for the next check, for every area you visit you also flag it so you wont check it again (this also helps to break the recursion, if not you can get stack overflow) because other portals can also leads to it.
because of this you can have few routes (in the recursion tree) that can lead to the same area! but not all of them will result in a visible area at the end! this is because we flag all the visited areas so the other routes that start like the first one but ends different (in terms of areas) wont even ends! meaning the area at the end of their route wont even visit because the first ones was flagged as visited - resulting in a none visible area that needs to be visible!!
i hope you didn't get lost in this long explanation and get the idea, so here is my solution to this problem:
the way i solve it is to look at the problem as a tree where the camera eye placed at the root, each portal is node, each branch is an area. (this is just how it help me to solve the problem).
i scan this tree by levels!, this way the areas are visited in a sorted order relative to eye pos (the root) and all the routes advance one step at a time and not allowing one route to get to the end (leaf) and others stay at the beginning.
here is few screenshots that shows portals in action:

visible portals in green, none visible in red

visible portals in green, none visible in red
yellow lines are current frustum planes
NOTE: portals are clipped against current frustum thats why part of the portal is red and the other part is green

2 comments:

KD said...

What do you think about HOM based occlusion culling ? I think it is better than portal , it can handle outdoor scene also..

orenk2k said...

hi
well, as far as i can see its a pixel based occlusion culling using hierarchical textures/maps which contains the objects, then we need to perform a per pixel operations to get info about who is visible or not, my problem with all those pixel based methods is how to get back the result fast enough so the cpu wont wait for the gpu.
it looks like nice method, but i dont think it is good for game app where the gpu work a lot.
maybe i'm wrong, but still right now my problem is not the visibility, my engine preform very good culling with the old portals.
anyway thanks.