BSP tree ?

could anybody explain me exactly, what the joke behind bsp trees is ?

as far as i understand, it is some way to store a static 3d scene, and you can draw your polygons always back to front (or vice-versa) without z-sorting them every frame.

but how do you do that ?

Go here http://reality.sgi.com/bspfaq/ and search www.google.com for “BSP tree” and you will find tons of information.

Nate Miller http://nate.scuzzy.net

I have found 4 pages that have good documentation about BSP’s. A page containing all the links is available here:
http://www.fatech.com/tech/opengl/index.shtml?seccao=opengl&tipo=Any&subtipo=Any&palavras=BSP

Antonio: vc é brasileiro ???
conhece OpenGL ???

talvez possa me ajudar…

The Cutting Edge site says

What we do with frustrum culling is check the bounding box, and if it isn’t visible, neither are its children, thus eliminating huge amounts of unnecessary polygons
but it doesn’t explain how. Can anyone clarify, as it would be very useful be able to cull polygons as quickly as it implies.

It seems as though you check to see if a polygon is outside the frustum. If so, do not process the children of it that are facing in the opposite direction to you. As in you don’t recurse any further down the tree

Actually now that I think about it, I’m not sure if this would work…because the planes on the frustum are at a different angle than a polygon usually so if it’s outside the frustum, it does not necessarily mean that it’s children are also outside the frustum

Okay, it seems as though I ran a circle there
If anyone can answer this I’ll be happy TOO

Wow. look what i found here

http://www.tasteofhoney.freeserve.co.uk/vsd/bsp/bsppart1.html

This tutorial is VERY HUGE!!!

[This message has been edited by drakaza (edited 07-20-2000).]

Basically it works like this:
As a plane divides space it also works as a divider for other planes. If a child plane exists on two sides of the parenting plane it is divided into two seperate planes. The child plane’s front half will be located in the front leaf of the parent and the child’s back half will be located in the back leaf. Because of this rule you know that all other children in the front leaf will be contain polys that are also all in front of the parents plane and vice versa. Now if you determine that the front or back of a plane is outside of the viewing volume, then you can also conlude that all its children are also.

Hope this helps. It is kinda hard to explain without diagrams.

Right, so you are saying that you test all the vertices of a polygon against the frustum’s planes, and if it is outside, then you ignore all of it’s children that are facing away from the camera, whether it is it’s front children, or just the back ones, is that correct?

To clarify one thing:
If you want to do really fast VFrustum culling you´ll need to use bounding boxes…
In nearly EVERY bsp-app this techique is used:You store a bounding box at each node which encompasses all the faces of the node AND it´s children…Now you can ignore all children of a node(and the node itself) if the node´s BBox is outside the Frustum.

HTH,XBTC!

XBCT i thought a BSP tree did that anyways without using bounding boxes, or are you saying that using bound boxes + bsp tree is faster?

Chris

For fast polygon/frustum culling or whatever
you want to name it it would be wise to read
up on “loose” octrees as well. It may not
be as correct as a more strict bsp but its
fast.

good luck,

Marcus “Cruxis” Lenngren - Nopp

Originally posted by XBCT:
[b]To clarify one thing:
If you want to do really fast VFrustum culling you´ll need to use bounding boxes…
In nearly EVERY bsp-app this techique is used:You store a bounding box at each node which encompasses all the faces of the node AND it´s children…Now you can ignore all children of a node(and the node itself) if the node´s BBox is outside the Frustum.

HTH,XBTC![/b]

EXCELLENT!!! That is what I have wanted to know for ages!! It’s just that all of the tutorials I read either explain one thing or something else but they don’t mention how to mix them all

Thanks for the info!!!

Thanks for that uk BSP link, drakaza.

Why not just use octrees right away and skip all that hard-to-understand bsp-stuff? Octrees are really easy, and from what I know, there’s really no performance difference. I’m I correct?

“Why not just use octrees right away and skip all that hard-to-understand bsp-stuff? Octrees are really easy, and from what I know, there’s really no performance difference. I’m I correct?”

´Cause it really depends on what you want to do.For large outdoor-scenes a octree\lod based approach is much faster than a bsp-tree approach,but for occluded quake-like dungeons and indoor environements a bsp\pvs approach is THE way to go…

I would say to use a portal engine instead. PVS is pretty much dead; even John Carmack is probably moving away from it with his next-gen stuff.

A portal engine is simply this: You have sectors and portals. Each portal is looking into a sector. Each sector has a pointer to all its portals. You clip your view frustrum against all the portals in the current sector (the one you’re standing in). If a portal is completly clipped away, you ignore it. If a portal is clipped you send the CLIPPED FRUSTRUM to the sector that the portal leads to (upon which that sector will check the frustrum against all of its portals, except the one it came from). Each sector you enter is added to a list. Then you just pass through this list and sort the polys by texture. Then render it all as usual.
The portals are placed at logical (doorways etc.) places by the level-designer.

This is pretty fast because a hair-thin cylinder in the middle of a room won’t cause 1000 new portals to be generated. And ONLY the portals which are truly visible will be drawn (unlike PVS which will draw all the portals which could be visible from your current sector).

I like portal-engines better than PVS-engines because there is no need for VIS. VIS-algorithms are so… Brute… I just don’t think it’s an elegant way to do it =)
Also, a human will be able to determine where to place portals a lot better than a BSP-algorithm will. Sure it’s extra work but most level-designers have to play with hint-brushes for hours anyway.

I’d even have a bsp tree or oct-tree per sector, as that can improve the speed of the portal engine even further, particularly in large rooms with lots of structural brushes, but few logical places to put a portal brush to subdivide the room. And it is a great aid in collision detection. Otherwise collision detection is quite cumbersome in a portal engine.

[This message has been edited by DFrey (edited 07-25-2000).]

Hey Tom,

If you are looking for some code on this subject there is some on flipcode in the code of the day archives and also there is some code over on nate miller’s page on this subject also(havent checked out the stuff on flipcode but nate’s is really easy to understand).

Chris

P.S.: the Link is in his post the first reply to this thread.

http://www.inside3d.com/articles/bsptree.shtml

The simplest and best I have seen… Doesn’t explain coding but in general…