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?


- ØØ -

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).

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

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 -

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 -

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.

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 -

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

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 -