Jump to content
  • Advertisement

Archived

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

Dark

Visibility Determination (BSP/kD tree)

This topic is 6931 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

I want to create a 3D computer game/demo... but I need some information on BSP/kD trees... I understand almost everything, but I don''t understand how to determine when I got to stop rendering... Somebody: Please write a detailed description of how a BSP/kD tree works. I certainly would like it if you included some demo code (with explanation). Thank you in advance. Greetings from Dark Wizard

Share this post


Link to post
Share on other sites
Advertisement
Yes, you got the point. Every damn tutorial explains how to build the tree, how to check intersections with a tree, how to clip nodes to the frustrum....

but NO tutorial explains how to check which surfaces are hidden, so that we get a benefit from BSP & co. in HSR...

Share this post


Link to post
Share on other sites
Check out the q1 src and tools. Or check out the Void source. Both use BSPs which store PVS data in the leaves.

Share this post


Link to post
Share on other sites
In quake in each subspace of the BSP tree information is stored about which triangles are visible when you''re inside the subspace. Then the BSP tree can be drawn back to front. There are also other optimizations in quake, check http://www.bluesnews.com/abrash.

Visit our homepage: www.rarebyte.de.st

GA

Share this post


Link to post
Share on other sites
I read the Abrash stuff, pretty iteresting...
I know that BSPs use a PVS for each node, so you just have to cull the nodes that are not in your frustrum, hidden nodes aren''t listed anyway.

so my question: How to calculate which nodes are visible from another one ???

Tim

Share this post


Link to post
Share on other sites
I can''t tell you offhand, because I haven''t got to that point yet

The logic you are looking for can be found in the qvis programs of the quake series. Probably looking at qvis3 ( the Q2 version) is most helpful.

Share this post


Link to post
Share on other sites
Hi Dark,
I believe there is another way to check whether a BSP-Plane has to be drawn and whether you have to continue rendering with the front of back node.

You just have to calculate the signed distances form the 8 vertices that represent your viewing frustum, to the Plane. When all distances have the same sign (all vertices ly on the same side) the Plane is not hitting the view frustum and not visivble. Then you only have to proceed with one of the two following nodes, depending on which side of the plane the viewpoint is located.
When the distances have different signs you have to continue drawing both nodes.

I hope thats what you need.

Share this post


Link to post
Share on other sites
You are talking view frustum clipping, no? That may be what he was asking, not sure. But what happens if you have a long, narrow level, with alot of detail, and you look down the long end? You will end up drawing almost everything, as it will be in view. What a PVS system does it determine, from where you are standing, what you could *possibly* see, and what you could never see, and draws that. So I would think, first, based on the view frustum, determine what leaves are in view, then use the PVS data for each leaf to see if it needs to be drawn.

Share this post


Link to post
Share on other sites
Actually you should do it the other way around.

First get the Potential-Visible-Set (PVS) from the BSP leaf where your camera is, and then check each of the leaves in the PVS against the view frustum.

The PVS for a BSP leaf is basically a list of BSP leaves that is visible from some point in the leaf. The meaning with the PVS is that you don''t have to check each leaf in the BSP against view frustum. This effectively culls a lot of BSP leaves from visibility determination at once, in many cases the majority of the BSP tree is culled, thus making the rendering so much faster.

- WitchLord

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!