Sign in to follow this  

BSP tree for occlusion ++

This topic is 4491 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 know there is lots of threads here about BSP I even see one 7 threads furuther down here. But I just need a some simple hints here..:) I am writing a simple indoor 3D engine just for fun in C# and GDI+, and I need to first find out what walls not to draw, then to draw them back to forth. I know how to set up a BSP tree and traverse it to draw from the back to the front, but how do I find out what walls are outside my FOV? Behind me or to the left or what ever? Is that what they call painters algorithm (ftp://ftp.sgi.com/other/bspfaq/faq/bspfaq.html#9.txt)? Or is that something else? If it is, is it a good way to do it, or is there an other way you would recomend for me to take away walls from my rendering queue? Thanks BugSlayer

Share this post


Link to post
Share on other sites
Culling -- if all the vertexes of the view frustum are on one side of the plane of a node, then the other side of the node is not in the view frustum and does not need to be drawn.

Painter's Algorithm -- this is a method of drawing polygons (back-to-front) so that they are properly obscured. Using a Z-buffer makes this unnecessary (except for polygons with transparency). In fact, when using a Z-buffer on modern hardware, polygons should be drawn front-to-back to take advantage of special hardware that rejects obscured pixels early in the pipeline.

Share this post


Link to post
Share on other sites
Guest Anonymous Poster
Quote:
Original post by JohnBolton
Painter's Algorithm -- this is a method of drawing polygons (back-to-front) so that they are properly obscured. Using a Z-buffer makes this unnecessary (except for polygons with transparency). In fact, when using a Z-buffer on modern hardware, polygons should be drawn front-to-back to take advantage of special hardware that rejects obscured pixels early in the pipeline.



OK, thanks, don't think I will implement a Z-buffer right away, so will draw it back to front, and hope that it won't be too slow.


Quote:
Original post by JohnBolton
Culling -- if all the vertexes of the view frustum are on one side of the plane of a node, then the other side of the node is not in the view frustum and does not need to be drawn.


Can you elaborate a bit more on that? When you saw ALL the vertices of the view frustum, do you mean the 4 vertices for the near plane, and the 4 for the far plane, so in total all 8 of them?

And what do you mean by "plane of a node". A node is a wall? and the plane is the red line on this picture for the "node" C?

[img]http://maven.smith.edu/~mcharley/bsp/figure6.gif[/img]

And what do you mean by "then the other side of the node is not in the view frustum", do you talk about the "left" and "right" leaf in the binary tree. So if all the vertices is on the left side, then discard the right leaf and all its childs?


Thanks a bunch, really appreciate if you help me out with this.

- ØØ -

Share this post


Link to post
Share on other sites
Quote:
Original post by Anonymous Poster
And what do you mean by "then the other side of the node is not in the view frustum", do you talk about the "left" and "right" leaf in the binary tree. So if all the vertices is on the left side, then discard the right leaf and all its childs?


Yes. That's it. One comment about terminology -- a leaf is a node that has no children.

Share this post


Link to post
Share on other sites
I have one/two more questions about this, so sorry for bumping this thread.

But the Binary tree. Is it only constructed ONCE the first time when you load the level, and after that it will never get altered? Because walls never move? And we are talking world coordinates here right?

- BS -

Share this post


Link to post
Share on other sites
yes you build in world coordinates and yes the tree is built only once for stationary objects. the bsp tree arranges objects "realative" to one another, not to any specific world space point. thus if the relative position of the objects doesn't change, there is no need for the bsptree to change.

Tim

Share this post


Link to post
Share on other sites
Thanks, I kind of got what you ment by "relatively to each other". Because they are kind of dependent on each other. The world coordinates will tell you if one object is in front or back or left or right of an other object, hence also relatively.

Yeah, you know what I mean...hmm...so I think I got you. Will give it a shot and see what I can pull off.

Thanks
- BS -

Share this post


Link to post
Share on other sites
Ahha, good to know. Thanks for saving me a lot of time there. I guess it is more importent where you start the "slicing" then. I guess you can be very unlucky can't you? Is it just normal to start on the middle of the map? Or is there some algo for this too?


- ØØ -

Share this post


Link to post
Share on other sites
The traditional method is to look through the planes of all polygons in your list from which you're building your node and test each one by some metric too see how 'good' a splitter it is. Then you use the one with highest ranking. I usually base my metric on a combination of number of polygons split and tree balance (how many on each side).

Share this post


Link to post
Share on other sites
for straight z ordering it doesn't matter if the tree is balanced or not, what criteria would you use to balance? no matter how the tree is arranged you have about o(n) complexity for drawing even if you ordered it such that the furthest poly from the current viewpoint is first in the list, if you moved the viewpoint, this wouldn't be the case. if your using the bsp tree for intersection testing of some sort then you should probably balance it such that aproximatly the number of objects on one side of a poly is equal to the number of pbjects on the other side. but if your using it for visible surface determination, it doesn't matter. because the difference between the two problems is for z-determination you're making a traversial of the tree(ie visiting all the nodes in a certian order), while with intersection testing you're searching through the tree. no matter how ugly the tree is, making a traversal of the tree is roughly o(n).

Tim

Share this post


Link to post
Share on other sites
Quote:
Original post by timw
for straight z ordering it doesn't matter if the tree is balanced or not, what criteria would you use to balance? no matter how the tree is arranged you have about o(n) complexity for drawing even if you ordered it such that the furthest poly from the current viewpoint is first in the list, if you moved the viewpoint, this wouldn't be the case. if your using the bsp tree for intersection testing of some sort then you should probably balance it such that aproximatly the number of objects on one side of a poly is equal to the number of pbjects on the other side. but if your using it for visible surface determination, it doesn't matter. because the difference between the two problems is for z-determination you're making a traversial of the tree(ie visiting all the nodes in a certian order), while with intersection testing you're searching through the tree. no matter how ugly the tree is, making a traversal of the tree is roughly o(n).

Tim




But I am going to use it for culling. Then I don't have to go through all the nodes do I? Isn't that why I use this tree in the first place. So I can discard whole "arms" in the tree? Or have I totaly missunderstood the use of BSP for culling?

- BS -

Share this post


Link to post
Share on other sites
Quote:
Original post by ZQJ
The traditional method is to look through the planes of all polygons in your list from which you're building your node and test each one by some metric too see how 'good' a splitter it is. Then you use the one with highest ranking. I usually base my metric on a combination of number of polygons split and tree balance (how many on each side).



So low split gives a high rank? Or the other way around?

And how are you able to check the balance of the tree without making it? Does that mean that you make just as many BSP trees as you have nodes, with a new node as root each time to test? I hope you ment something else..?..?


Thanks
- BS -

Share this post


Link to post
Share on other sites
The BSP tree for z ordering is differnt then the BSP tree for culling I'm sorry I thought you only wanted z-ordering. The z-ordering BSP tree cant be used to cull, however it does automatically eliminate all geometry that is behind the viewport, so it culls in this manner of speaking. there are bsp trees you can use for culling, they are not made in the same way as a bsp tree for z-ordering. the ones for culling are made by dividing space, by picking an arbitrary splitting plane and partitioning all objects above and below the plane. and continuing this process till the LEAF contain a small number of objects. for z-ordering, the actual object(triangle) in consideration is used for the splitting plane and is thus stored in a NODE, objects are ordered relative to eachother in this case. so the two structures are indeed BSP trees but they're made differntly. one is a spacial partitioning structure, and another is a object ordering structure.


I'm not really up on advanced culling techniques, I figured you wanted this for z ordering only. but it does cull stuff that is behind you so that's a plus. an easy way would be to subdivide space with all your stationary gemoetry. divide space into cells, a grid structure and only render cells that are within the viewport, within a cell, I would clip at the object level tho, not the triangle level, it's realtively expensive to see if a large number of triangles are within a view, I'd toss out entire objects using the bounding rectangle or something, for the objects that are not entirely onscreen I'd just pass the entire thing trough.

Share this post


Link to post
Share on other sites
OK, it might be time to put all the cards on the table, since it seems like my lack of knowledge here confuses you more then nessesary....:)


Me and a friend is making a small small 3D engine from scratch. Just to show off C# skills. It is not ment to be fancy or be fast or be used to anything else then make a small screensaver that will walk through a labyrinth.

Screeny from our app at the moment:
http://vbforums.com/attachment.php?attachmentid=39850&stc=1
Mapeditor:
http://vbforums.com/attachment.php?attachmentid=39875&stc=1


So since we are doing this from scratch no DX or OpenGL, we both need culling for speed and Z-Ordering. But I thought we could use the same tree. So sorry for confusing.

A grid could work. I was tempted to say Quad tree to, but I can't see how that will work out now...hmmm..I think I have to twist my mind some more.

Thanks again for your input.
- BS -

Share this post


Link to post
Share on other sites
I was searching for some information for you and I found some notes that might be helpfull for you.

www.cse.ohio-state.edu/~hwshen/781/newCulling.ppt

he's calling what I was talking about in regard to z ordering (polygon-aligned) bsp and he's calling the bsp tree I was talking about for culling (axis-aligned). look at them both to note the differences, however he didn't talk about it but the bsp tree need not use axis aligned splitting planes, usually this is called a k-d tree but whatever float his boat. I figure once you read this you should be set, if not feel free to inquire about specifics

Tim

Share this post


Link to post
Share on other sites
Well I have been googling a whole bit to try to find out more about this, and it seems like there might be a slight difference between a KD tree, and a Axis Aligned BSP.

Quote:

axis-aligned bsp-tree partions space using the xy, xz, and yz planes but it will not neccessarily alternate periodically between them the way a kd-tree does. Instead the aa bsp-tree chooses it's splitting plane depending on the geometrical density.


Not that I am fully understanding that part. So you think that using Axis Aligned is the way to go for culling? I must say that it is a bit dense looking for me on how to split up a room using Axis Aligne. But I guess I can find out that. But Polygon allign looks a bit simpler. At least to make the tree.

Thanks for the link. Think I need to find out more about AA now to get this workin. Unexpected turn...

- BS -

Share this post


Link to post
Share on other sites
Quote:
Original post by BugSlayer
Quote:
Original post by ZQJ
The traditional method is to look through the planes of all polygons in your list from which you're building your node and test each one by some metric too see how 'good' a splitter it is. Then you use the one with highest ranking. I usually base my metric on a combination of number of polygons split and tree balance (how many on each side).



So low split gives a high rank? Or the other way around?

And how are you able to check the balance of the tree without making it? Does that mean that you make just as many BSP trees as you have nodes, with a new node as root each time to test? I hope you ment something else..?..?


Thanks
- BS -


Usually I use rank = 8*number of splits + abs(number in front of splitter - number behind splitter), and looked for the one with the lowest rank. This may be a terrible method since I never tried to benchmark it (8 is a TOTAL guess on my part). I usually use leafy BSPs where all polygons are stored in leaves not nodes, and you can do frustum culling with those. If you want full visibility culling you'll need to go one better and compute the PVS or something.

Share this post


Link to post
Share on other sites

This topic is 4491 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.

Create an account or sign in to comment

You need to be a member in order to leave a comment

Create an account

Sign up for a new account in our community. It's easy!

Register a new account

Sign in

Already have an account? Sign in here.

Sign In Now

Sign in to follow this