Jump to content
  • Advertisement

Archived

This topic is now archived and is closed to further replies.

Taulin

Building a PVS for a BSP tree?

This topic is 6925 days old which is more than the 365 day threshold we allow for new replies. Please post a new topic.

If you intended to correct an error in the post then please contact us.

Recommended Posts

Abrash talks about building a precalculated viewable set at each node in a BSP tree. Does anyone know of an easy, or even a way to do this? I saw a thesis one time that described finding the portals of each convex room in a BSP tree, and test every possible angle to other room portals. Is this the same way that the Quake utilities produces its sets? Thanks -------------- My opinions do not reflect the porn industry in any way.

Share this post


Link to post
Share on other sites
Advertisement
i remember that''s how doom editors did it (testing all possible locations along each sector). there is a series of articles by michael abrash on the quake engine visibility stuff right here on gamedev.
also, check out the bspfaq, which is located here somewhere (i think) and many other programming sites.



crazy166
some people think i'm crazy, some people know it

Share this post


Link to post
Share on other sites
The way Quake has structured its BSP tree each leaf can be seen as a convex cell of walls. Since they are convex you can easily construct portals where you can see out from the leaf and into another. To compute the PVS through one of these portals place the hypothetical camera in the plane of the portal, here it can see out from the cell with a FOV of 180 degrees. Then you take this visible area and checks which portals are visible. Each time you find that a portal is visible you add the leaf to the PVS and recursively checks which portals are visible through that one. The visible area will also narrow as you go through each portal.
You of course need to do this for each cell and portal to compute the complete PVS.

I think that this is similar to the technique called beam tree, but I''m not sure.

(I know the above explanation might be confusing, so if you don''t understand it just ask again.)

- WitchLord

Share this post


Link to post
Share on other sites
By the nature of the BSP tree, a leaf
of the tree would consitute a position
that is enclosed in a Convex chamger.
The question is now how to find the planes
that make up the portals into the chamber
(empty spaces). To do this, I would
think you would have to find which polygons make
up the walls of the ''chamber'' and construct
the portals from the empty spaces. To do this,
I would think would be very difficult. Am
I missing something?

My only guess right now is to find which polygons
are closer, then test if the polygon shares
vertices with a polygon already determined if
it was close....this is already getting messy.
There has to be an easier way.

So the final question is: How do you come up
with the list of polygons that make up the portals
into a given leaf''s convex chamber?

-Phil

Share this post


Link to post
Share on other sites
I''m sorry but I don''t know the algorithm to do this by heart so I can''t give it to you, but I can tell you that you should try to find some papers on ''Convex Hull'' algorithms that computes the convex hull from a set of vertices. The convex hull would then be the sum of the cell walls and portals.

- WitchLord

Share this post


Link to post
Share on other sites
Here is how I calculate the portals in my compiler.

I first calculate a BSP tree using the polygons in the scene as the splitting planes. Then I go through the BSP tree and for each node which has both a front and a back child, I create a polygon which lies on the splitting plane for that node and that is the size of the bounding box of that node. I then clip this new polygon to all of the polygons in the leaves which are children of this node. I pass all of the pieces I get down the BSP tree (if the piece lies on a plane, pass it down both front and back) and every piece which ends up in two leaves is a portal between those two leaves.

I wrote a program which does this, so it does work.

Share this post


Link to post
Share on other sites
Icarus,
First, Thanks.
Second, I was going through this, and had one question.
"Create a polygon the size of the bounding box of that node". Do mean the model? If you did, that would sound logical having a polygon that stretched across all the polygons that it split.
I worked through it and it looks like it will work. Most excellent. I wonder if it is possible to build this as the tree is being built? Hmmm.

Phil

Share this post


Link to post
Share on other sites
I believe he meant the bounding box of the BSP leaf that you are currently computing the portals for. Still I''m not sure as I haven''t done much work with BSP trees.

- WitchLord

Share this post


Link to post
Share on other sites
Taulin,

Here is how I do it. Each node in the BSP tree has a bounding box which is the size of all of the polygons which are children of that node. When I say node I do not mean leaf. So lets say that you have a huge world containing many polygons. Lets say a splitting plane split them in half. The head node would have a bounding box which was the size of all of the polygons in the world. The left node(front) would have a bounding box the size of all of the polygons in front of the splitting plane, and the right node(back) would have a bounding box the size of all of the polygons behind the splitting plane. If you need more help, you can post on the board or email me at NeoIcarus@mail.com.

-Icarus

Share this post


Link to post
Share on other sites
Dong! (Sound of me hitting myself in the head)
Ok, that makes sense. Thanks!

Phil

Share this post


Link to post
Share on other sites

  • Advertisement
×

Important Information

By using GameDev.net, you agree to our community Guidelines, Terms of Use, and Privacy Policy.

GameDev.net is your game development community. Create an account for your GameDev Portfolio and participate in the largest developer community in the games industry.

Sign me up!