• Advertisement
Sign in to follow this  

BSP and Octrees Wee bit confused :S

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

Hello there! From what I gather all an octree does (in terms of rendering) is that it will quickly cull out polygon that are outside the frustum. A BSP tree on the other hand (from what I gather from reading around) sorts out your polygons and puts them in a since binary tree, which you can use later on to do fast and efficient depth-testing. But from old topics here say things that are completely different. Topics like this: suggest that one is better for indoor setting while the other is better for outdoor settings. This doesn't make sense since octrees are used for frustum cull, and BSP trees are used for depth-testing (that's what I think). If I'm wrong, then what is the real application of octrees and BSP trees (in terms of rendering)? [Edited by - CodeMonkey2000 on July 14, 2008 11:22:02 AM]

Share this post


Link to post
Share on other sites
Advertisement
Both of them are just spatial partitioning algorithms that help you sort stuff by position, what you use them for is up to you. For example I'm using quad-tree(Octree with only 2 axis instead of 3) to speed up collision detection checks by placing what I need to check collision for into various regions, and then test an object against the tree and go down the tree and only do collision checks on the objects that are within the general area of my test object.

In terms of rendering, you kinda have to really look at what you're trying to organize to determine the best culling method. Octrees tend to be better suited for outdoor areas that have quite a bit of height elevation and are pretty easy to get up and running. Indoor areas tend to be very linear in most games and BSP is usually used to help generate things like Potential Visibility Sets for culling. However octrees can be still be used and if you're level is more of a real world area such as an office building, octrees may even be better for such an environment.

One of the original uses as you've said, was for depth sorting for the Painter's Algorithm which was required before depth buffers became widely used. The only game I can really remember that used BSP directly for culling was the original Doom, and I'm not even completely sure about that. Again, it's just a way to organize stuff by space.

Share this post


Link to post
Share on other sites
To use an octree for depth-testing, would I need to keep sorting the child nodes relative to the camera so they get drawn in the right order (I'm not really sure how to do depth-testing with octrees)? Or should I put all the visible polygons into a BSP tree every frame (it seems to be almost as efficient as a quick sort so it sounds plausible)?

Also my setting is a building with floors. I think an octree would better for this.

Share this post


Link to post
Share on other sites
Quote:
Original post by CodeMonkey2000
To use an octree for depth-testing,


You wouldn't bother. Draw solid stuff first, transparent stuff second. Use the z-buffer for the actual depth testing, and possibly depth peeling if you have a lot of transparent surfaces.

Quote:
Or should I put all the visible polygons into a BSP tree every frame (it seems to be almost as efficient as a quick sort so it sounds plausible)?


Dont bother with BSP.

Quote:
I think an octree would better for this.


An oct-tree is almost always better than a BSP tree. BSP tree's are a pita to work with imho. You can get depth sorting for (almost) free with a BSP tree, but the dis-advantages you get when using BSP tree's are substantial enough to not want to use them...

Share this post


Link to post
Share on other sites
For Rendering culling BSPs are no longer relevant, the comparison there should be between Octrees and Portals, in that case, yes, Octrees are better for open spaces and Portals for indoor levels.

BSPs Still have their use for Collision culling though.

Share this post


Link to post
Share on other sites
Quote:
Original post by RobTheBloke
Use the z-buffer for the actual depth testing, and possibly depth peeling if you have a lot of transparent surfaces.


How does z-buffering work? I look around and I'm still not sure how to do it. I think you just take the polygons that are on screen and just sort them out then draw them. Could I just assign each polygon the distance from the camera to that polygon, and quick sort them that way?

Share this post


Link to post
Share on other sites
Quote:
Original post by CodeMonkey2000
Quote:
Original post by RobTheBloke
Use the z-buffer for the actual depth testing, and possibly depth peeling if you have a lot of transparent surfaces.


How does z-buffering work? I look around and I'm still not sure how to do it. I think you just take the polygons that are on screen and just sort them out then draw them.


You don't have to, nowadays depth buffering is handled by hardware, all you have to do is define the precision of your depth buffer (16,24,32) and enable it.

Take a look at the page on Wikipedia

So, as Rob said, don't worry so much about what gets drawn first (just draw solid then transparent), but do worry about rendering only the objects that are inside the camera frustum.

Share this post


Link to post
Share on other sites
After Setting the depth size (resolution), which in SDL is done with:

SDL_GL_SetAttribute( SDL_GL_DEPTH_SIZE, 24 );

And maybe setting the depth clear value with glClearDepth, yes, that's all it takes.

Share this post


Link to post
Share on other sites
Quote:
Original post by Kwizatz
BSPs Still have their use for Collision culling though.


I don't doubt that, though if you've ever attempted to set up a collision mesh that's gets converted into a BSP tree, you might start to see my point about not bothering ;)

Share this post


Link to post
Share on other sites
Quote:
Original post by RobTheBloke
Quote:
Original post by Kwizatz
BSPs Still have their use for Collision culling though.


I don't doubt that, though if you've ever attempted to set up a collision mesh that's gets converted into a BSP tree, you might start to see my point about not bothering ;)


Oh, I definitely agree with you there, I went through that pain already, not only of the conversion, but also generating a properly balanced BSP [bawling].

In my opinion it is worth to at least keep your collision geometry convex and somewhat sorted, dynamic collision detection against polygon soups is way too unstable and prone to glitches, just another source of rear pain [lol].

Share this post


Link to post
Share on other sites
Sign in to follow this  

  • Advertisement