Constructing a PVS

You only need to trace rays out at a 180^o angle from each portal. Also, instead of tracing individual rays, use a beam-tree. This will be more accurate. Or, as an alternative, you could give each cluster a unique color, and then use hardware acceleration to render the scene with a 180^o FOV from each portal, and then see which colors are in the image. The hardware accelerated technique should be done at a relatively high resolution so as not to miss any visible nodes. Using RGB color values to label each of your clusters allows you 16777216 individual clusters .

'The real problem is to find a point in the node to trace from. I think you have to do several traces from each node into each other one. For instance, node A may not be visible from node B's midpoint, but nearly all the other points in node B. '

I beg to differ...

The technique Quake uses is to form "anti-penumbra" clipping planes to determine what is visible through the portals of one convex leaf into another. An anti-penumbra is like the reverse of a shadow. Imagine standing in a pitch black room (with no light) and opening a door to a room that's filled with light. If you open the door by just a crack, the light that shines through will cover an area of space inside the dark room that represents an anti-penumbra, or anti-shadow. This is the area inside the dark room that's "potentially visible" from the lit room. Anything inside the dark room that isn't hit by the light can't be seen by someone standing in the lit room. (Pretty intuitive if you think about it.) More importantly, if the light shines on any portals inside the dark room, then the leafs on the other side of those portals are also "potentially visible" by the lit room, since the light shines into them as well.

The concept of light shining through doorways into rooms and through doorways into other rooms is just a way to conceptualize what's involved in calculating a PVS. The technique itself is relatively simple, but is dependent up creating portals during the BSP process. To create an anti-penumbra, you select a portal in one leaf, a portal in the neighboring leaf that the first portal leads into, create planes that completely separate the two portals, then step through the second portal into its neighboring leaf and see if any portals in that leaf are fully or partially inside all of the planes. If any are, then the leafs on the other side of these third portals are also potentially visible from the portal of the first leaf. The process repeats recursively for each portal in each leaf.

It's hard to fully explain. I recommend taking the Advanced 3D: BSP, CSG, PVS class at the GameInstitute (http://www.gameinstitute.com) or looking through the VIS.C file from the Quake and Half-life source code, which is the technique GameInstitute teaches. Also, Dan Royer has a tutorial on his site, http://aggrav8d.cfxweb.net/, but the GI course is the way to go.


PigVomit

Edited by - PigVomit on October 14, 2001 2:41:53 PM

Edited by - PigVomit on October 14, 2001 4:58:02 PM

Edited by - PigVomit on October 14, 2001 4:59:31 PM