How to implement PVS calculation?

I'll explain to you how Quake does it.You can get the source code to QBSP and study it too. It is a bit complicated as it does alot more than just finding the visibility graph.

What QBSP does is find the portals between adjacent sectors/leafs, and it uses these portals to build a visibility graph. They aren't really portals like in a portal engine but they are the same idea. Then each leaf in the BSP has a cluster of visible bits and the clusters that are connected via the portals are set to 1, and everything else is set to 0. They are encoded as 1 leaf per bit, and consecutive 0's are RLE compressed. Now the engine will find the leaf the camera is in, and decompress the visbits for the leaf and than draw all the visibile leafs from it. The visbits are the PVS. The BSP is mostly there for collisions and finding what is visible to draw ( but Quake 1/2 use the map BSP to draw, but it rorders it internally. The file format leafs contain the list of faces that are drawn when it is visible.)

It isn't too hard to do it. The worst way probably would be to raycast out from the leaf and see if it hits into any other leafs. Or you draw it from 6 different camera angles, and than determine if any other leafs were visible. QBSP cuts the polys against the brush windings and it is left with empty polys that define potential portals to other cells. It uses this (I think) to also flood the graph to find out if there are any holes in the map (it must be sealed to meet some sort of 2-manifold requirements of a BSP tree or something).

I hope it helps. QBSP is your friend. Get Quake 1 utils, or Quake 2, they are much simpler than to follow Quake 3.

Actually i mostly knew what you said. From what i read on a site, Quake computes the portals by creating a large polygon for each intersection plane that goes out of the level's boundaries and then clips it with the planes of the children of the node that has the intersection plane. The "remaining" is a potential portal polygon.

Then it somehow figures out which of the potential portal polygons are actual portal polygons... and then somehow using these portals it computes which parts of the tree are visible to other parts...

[knowledge on the topic stops here]

The problem is that i can't find any page with clear information on how to calculate PVS (note that i don't require it to be the method that Quake used) or portals (or both if one requires the other).

Also i'm not sure what to do once i find the portals. I don't think that raycasting from one cell to others actually works; at the past i wrote a "2.5D" software rendering engine for which i was calculating a PVS by dividing the world in square cells and shooting rays to see which walls are visible from a cell. The problem is that from some points in the cell a wall was visible and from some other points, it wasn't (and shooting ALOT of rays wasn't a solution - there always was some cases where i was "between" points where a wall should be visible but it wasn't).

A solution would probably be to test each "out" cell (the cells that are outside the cell we make the PVS entry for) for being visible to the "in" cell by projecting all polygons it has on the portal polygon's plane, then clipping the projected polygons by the portal polygon and marking the cell as "visible" if any of the projected polygons is inside the portal polygon or "invisible" if all of the projected polygons falls outside the portal polygon.

However i have a great feeling that this is wrong...

Quote:

Original post by badsector Actually i mostly knew what you said. From what i read on a site, Quake computes the portals by creating a large polygon for each intersection plane that goes out of the level's boundaries and then clips it with the planes of the children of the node that has the intersection plane. The "remaining" is a potential portal polygon. Then it somehow figures out which of the potential portal polygons are actual portal polygons... and then somehow using these portals it computes which parts of the tree are visible to other parts... [knowledge on the topic stops here] The problem is that i can't find any page with clear information on how to calculate PVS (note that i don't require it to be the method that Quake used) or portals (or both if one requires the other). Also i'm not sure what to do once i find the portals. I don't think that raycasting from one cell to others actually works; at the past i wrote a "2.5D" software rendering engine for which i was calculating a PVS by dividing the world in square cells and shooting rays to see which walls are visible from a cell. The problem is that from some points in the cell a wall was visible and from some other points, it wasn't (and shooting ALOT of rays wasn't a solution - there always was some cases where i was "between" points where a wall should be visible but it wasn't). A solution would probably be to test each "out" cell (the cells that are outside the cell we make the PVS entry for) for being visible to the "in" cell by projecting all polygons it has on the portal polygon's plane, then clipping the projected polygons by the portal polygon and marking the cell as "visible" if any of the projected polygons is inside the portal polygon or "invisible" if all of the projected polygons falls outside the portal polygon. However i have a great feeling that this is wrong...

That *is* the PVS ;-) All the leafs who have portals to other sectors are it's PVS. You just mark them as being *potentially* visible.

Than in your engine, when you get the PVS you just frustum cull the leafs. PVS doesn't guarantee AVS (absolute visibility) only a good approximation of what is *potentially* visible.

It's really not hard, I remember when I first trying how confusing it is but it's actually mind boggingly simple when you finally get it.

Now raycasting would work sure, if you shot a bazillion rays and clip it against everything that it hits. If it hits a wall in some other leaf, it's potentially visible and Tag it. It's just god aweful slow.

The way Quake does it is rather complicated but it is much faster. The other way is to use a 'camera' view and detect visible leafs ( see Fly3D on how he implemented it ).

[EDIT]
Well I didn't want to completely confuse you.. calculating the PVS is hard mostly because you have to find all the portals. The portals are what is used to get the PVS. The PVS is just an array of flags for each leaf telling what other leafs might be visible from it, the portals are thrown away (on Quake anyways) There are other tricks but I don't think it's very good. But the PVS doesn't use the portals in a way like a portal engine would, because I think the BSP compiler makes so many of them that you don't have to really worry about the actual poly's. I never implemented a PVS calculation though.. I've only implemented level viewers for Quake and that is basically how the PVS is used after it's calculated: decompress vis, get potential vis leafs, frustum cull leafs that aren't visible and than just draw what is left. THe only thing GL quake did I can see is test if the poly is facing or not. But keep in mind that Quake maps can be rendered without budging most modern video cards without any visibilities at all.. most new games are using manual portals I think because they need a much higher level of occluding geometry than Quake maps did (I think). I'm not an expert, it's what I know, I wish you luck on your PVS compiler.


[Edited by - Name_Unknown on July 22, 2005 10:04:03 AM]

Well what you describe doesn't sound as PVS engine, but as a portal-based engine. PVS is like:

for each cell in the world (cell in my case could be the convex areas that the BSP leaves define) calculate which other cells are potentially visible. Then in the engine just pass only these cells to the lower level Hidden Surface Removal parts of the rendering pipeline (such as frustum culling and clipping) instead of passing everything in the world.

A portal-based engine works like this:

Figure out in which cell/sector the camera is and render the sector. Figure out which portal polygons are visible and clip the view frustum to them. Then render the cell/sector they point at with the new frustum. If the target cell/sector have any portal polygon, then clip the -already clipped- viewing frustum by this portal polygon and repeat this for the cell/sector the portal polygon points at. Repeat the same process for every portal polygon you'll find until no more portal polygons or until the frustum becomes extemelly small (1 pixel?).


Having said the above, i've heard that Unreal Engine is a portal-based engine, so things won't be that slow without PVS (if portals are used).

But a main problem is that i don't really know how to calculate the portals...

He was not saying that his idea was portal based. BSPs are in no way necessarily portal based. What he was saying is that portals are calculated for the BSP level and then used to find the PVS for each leaf. The portals themselves can then be discarded in the level editor, and all that is included in the final BSP is the BSP and the PVS flags. This is the way it is done in the BSP implementations we have in games. Its not a portal engine. Sorry if I can't point you to some helpful articles on the subject, but I was just hoping I could clarify what he said.

Quote:

Original post by NihilisticMystick He was not saying that his idea was portal based. BSPs are in no way necessarily portal based. What he was saying is that portals are calculated for the BSP level and then used to find the PVS for each leaf. The portals themselves can then be discarded in the level editor, and all that is included in the final BSP is the BSP and the PVS flags. This is the way it is done in the BSP implementations we have in games. Its not a portal engine. Sorry if I can't point you to some helpful articles on the subject, but I was just hoping I could clarify what he said.

Yes exactly.. the portals are used only to get the PVS. The PVS is just an array of flags telling the engine what BSP leafs are potentially visible from the leaf the camera is in.

I told you 3 ways to calculate the PVS now, all of them are documented and have been used (although I never heard of anyone actually using raycasting, I know it can be done). The big developers used portals because it is apparently the best way to do it. Quake is not a portal engine. It is a visibility graph driven engine (which is the PVS, and that is connected to the leafs and every leaf potentially visible from the camera leaf). That's it. You don't have to use portals at all.. but all new engines are using them now. Unreal uses both PVS and manual portals. Manual portals give you much finer control over visibility and also the artist can place them strategically. PVS really has nothing to do with Portals.. it is mentioned by Seth Teller as a way to calculate the PVS. The BSP tree is used because it provides a simple way to split the world up and order it, and it can be used to help the rendering to software (but is not good for hardware really). You don't have to use BSP, you can make a bunch of sectors and portals, and than make a PVS for it just like that by setting flags for each sector to what sectors are connected by the portals. You can do it with any spatial structure, BSP was used because it was simple and it was better for software rendering ( as I remember it told).

In quake the PVS is what does the visibility. The BSP is used for collision, for finding where the camera is at, and also it stores the faces to be drawn from the PVS. No portals in it anywhere. The portals are just polygons that the QBSP compiler clips against the leafs geometry and than tests it to see if there is a another leaf connected, once it has that it marks the entire leaf visible for drawing in it's PVS bits. You than use frustum culling to remove any possible non-visible leafs, the PVS ensures that you don't draw much more than you have to.

I'd say forget about BSP/PVS it's not favored as much because it is not as good for hardware. In the old days every poly drawn was super expensive and BSP magically made it easier or something. You can do PVS with Octrees, or anything. All it is is a graph that connects nodes marked potentially visible from one another.

take a look at this http://www.delphi3d.net/articles/printarticle.php?article=pvs.htm

I implemented this method a couple of years ago. It is easy to program and works just fine. the hard part is actually to extract the portals from the BSP tree.

Quote:

Original post by badsector I've found a paper by Teller which is supposed to provide what i need, but... well... i can't say i understand much of it (it could be that it's very long -more than 60 pages i think- and i'm easyly getting tired when reading text from the screen...).

That'd be "Visibility Precomputation in Densely Occluded Polyhedral Environments", I'd assume. Print it out and spend a lot of time on it; while it's rather dense (as most academic prose is), it is substantially worth the time invested in understanding it.

Umm, guys i know all this stuff you're talking about, i tried to implement a PVS in a grid-based partitioning, remember? :-). I know that portals are just one of the available methods to compute a PVS and BSP is just a method to get the portals. But anyway, thanks for your replies :-).

Btw, as i said i'm using BSP for other things, so i don't think that there is a reason to use another space partitioning structure (such as octrees, quadtrees, or whatever else).

Again thanks for the replies (and if anyone else has any idea please tell me about).

@toe99001:
well, yes... that's my major problem :-D

@Sneftel:
yes, that's it. And i'll probably do just that :-)

Quote:

Original post by badsector Umm, guys i know all this stuff you're talking about, i tried to implement a PVS in a grid-based partitioning, remember? :-). I know that portals are just one of the available methods to compute a PVS and BSP is just a method to get the portals. But anyway, thanks for your replies :-). Btw, as i said i'm using BSP for other things, so i don't think that there is a reason to use another space partitioning structure (such as octrees, quadtrees, or whatever else). Again thanks for the replies (and if anyone else has any idea please tell me about). @toe99001: well, yes... that's my major problem :-D @Sneftel: yes, that's it. And i'll probably do just that :-)

Than why did you say you don't know how to calculate the PVS? When you say that I assume you don't know what it is at all.

It's a connectivity graph of the leaf nodes in your BSP, whatever way you can dream of to find that you can implement. There are other PVS algorithms than Seth Teller's method... his way describes how to use portals in particular kinds of settings (densely occluded like Quake and Unreal maps...). If you don't like portals look at other methods. Look for a site called dPVS they have a paper that lists alternative algorithms they use.

I am assuming you are using a leafy bsp.. a node based BSP has the graph connecting nodes than.


Sorry but you were asking it like you had no clue what it means.

No, i know what PVS is - if i gave the wrong impression, then my fault :-)

My problem is that i don't know how to calculate it :-). Now i'm reading Teller's paper. It's big... actually huge, but seems good. What it describes seems to be exactly what i'm looking for (computing a PVS for interior scenes).

Anyway... thanks for the replies and i'll see what i'll come up with :-P