Sign in to follow this  

Are BSP trees the fastest?

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

Is the BSP tree technique the fastest for rendering? I just wonder, because most of the articles for game maps include BSP trees. I tried to understand how they work and how they were implemented, but wasn't succesful yet. Are there other possible ways for fast rendering?

Share this post


Link to post
Share on other sites
Quote:
Original post by cignox1
AKAIK kd-tree are considered the fastest for ray-tracing.
I was under the impression the octrees work the best, since they subdivide the space very quickly and result in a shallow tree and faster searches. I may be wrong, though.

Share this post


Link to post
Share on other sites
It really depends on your scene, but my opinion is that BSP trees are very rarely necessary any more.

They *used* to be necessary when it was really expensive to rendering more geometry than you could see, but in the modern day of primarily CPU-limitation, it's better to have a fast algorithm that creates a conservative set of "potentially visible" objects, and render them all. If a few thousand polygons don't end up being displayed, no big issue. If you have *really expensive* fragment shaders, you can always do a z-only pre-pass as well.

Anyways I'd recommend looking at something more like an octtree or similar bounding volume hierarchy. They are fairly simple to implement and although they have their own set of flaws, usually they can be made to work well.

Share this post


Link to post
Share on other sites
I might be wrong, but I think the OP is asking about conventional rendering techniques for real-time games, rather than raytracing.

@The OP: BSP trees have played various roles in 3D engines since the first Doom (and maybe before). In the original Quake, the tree was used to sort polygons from front to back for software rendering, but when hardware rendering became common that became less important. The BSP tree was still used for other purposes though up through Quake 3 and its derivatives. It's useful for collision detection, and is also used to construct the PVS (potentially visible set), which cuts down on unnecessary rendering by sending to the hardware only what could possibly be visible from the current camera position.

I know less about more recent engines such as Doom 3, but I think a manual portal system now compliments (or perhaps replaces) the PVS/BSP system. Whether a BSP tree will be useful or accelerate rendering really depends on the context; for a heavily occluded indoor environment with a relatively low poly count it may be ideal, but for an outdoor terrain-based environment it would probably be of little use.

Share this post


Link to post
Share on other sites
Quote:
Original post by Promit
Quote:
Original post by cignox1
AKAIK kd-tree are considered the fastest for ray-tracing.
I was under the impression the octrees work the best, since they subdivide the space very quickly and result in a shallow tree and faster searches. I may be wrong, though.


Octrees are faster to build, but kd-trees should be faster in the rendering. I cannot be completely sure, but there should be a paper somewhere that compares many schemes and kd-trees came out to be the fastest. The book 'physically based rendering' by pharr and humpreys uses kd-trees.
To the OP: if you're talking about traditional rasterization, then forgive what I said.

Share this post


Link to post
Share on other sites
kd-trees are great for raytracing, but they are hard to update, and introduce unnecessary overhead for simply doing some culling/collision detection, etc. Unless you're looking at a totally static scene (in which case you can generate the kd-tree ahead of time), I'd recommend against them for game usage.

Share this post


Link to post
Share on other sites
AFAIK all spatial subdivisions based on static spaces are terrible for dynamic scenes (unless you can interpolate between pre-generated "key frames" of spatial division), they tend to mix memory a lot. Bounding volumes are better for dynamic scenes (as any other "loose" technique). The point of space partitioning is to divide element accesses. So for example in an indoor game you would use BSP-trees or portals to determine in which "subparts" of the level the player or any other object is. On outdoor you would choose perhaps a quadtree or a 2D grid for example.

<rant>
The point for spatial subdivision is to separate what is viewable and what can be ignored. If elements start to move a lot and you try to adapt the Space Division to best fit it, you tend to get unoptimal. The thing is to adapt the elements to the Space Division and ONCE IN A WHILE, when it gets TOO CROWDED or inefficent you update the space division.
</rant>

Hope this helps,

JVFF

Share this post


Link to post
Share on other sites
If I cand find the PDF by nVidia I will, but it basically said that Octrees were preferable because, due to their shallowness, the less following of pointers there is. "Every time you follow a pointer, you can assume a cache miss," is a quote I remember well. It had something to do with something, this sort of thing I haven't looked at in great detail yet, but I do remember what I read.

Share this post


Link to post
Share on other sites
Quote:
Original post by _goat
If I cand find the PDF by nVidia I will, but it basically said that Octrees were preferable because, due to their shallowness.


Shallowness is a fake issue. If you want a shallowness tree, use a single-cell tee ;)

What kind of KD-Tree exactly is considered to be the best please ?

Share this post


Link to post
Share on other sites
Quote:
Original post by Woodchuck
What kind of KD-Tree exactly is considered to be the best please ?


I think it depends on the ray tracer implementation and the scene. In some cases you want to isolate the objects by surface area (to guarantee the number of tests is similiar between rays), in others you want to isolate empty spaces (to guarantee you are testing as few objects as possible). Hope this helps,

JVFF

Share this post


Link to post
Share on other sites
Quote:
Original post by jvff
Quote:
Original post by Woodchuck
What kind of KD-Tree exactly is considered to be the best please ?


I think it depends on the ray tracer implementation and the scene. In some cases you want to isolate the objects by surface area (to guarantee the number of tests is similiar between rays), in others you want to isolate empty spaces (to guarantee you are testing as few objects as possible). Hope this helps,

JVFF


Yes thanx.

Share this post


Link to post
Share on other sites
Agreed: adaptive bounding volume hierarchies are the way to go for dynamic scenes.

Quote:
Original post by jvff
The point for spatial subdivision is to separate what is viewable and what can be ignored.

Well they are also useful in finding spatially neighboring regions for things like collision detection, etc. Thus it's nice to have a BVH that supports neighbor access without too much traversal (ex. octtrees can be bad for this as neighboring cells can require one to traverse ALL the way up and ALL the way down the whole tree...).

Share this post


Link to post
Share on other sites
Kd-trees are considered the fastest ray casting structure for static geometry.

This link provides a PhD thesis with information on multiple structures for ray shooting with the different characteristics of the algorithms implemented.
http://www.cgg.cvut.cz/~havran/phdthesis.html
Like everything in Computer Science you might disagree with some of this results, but in reality the best way to deal with this is to implement different spatial partitioning algorithms yourself and get performance results.

There is very little literature on kd-trees, and it is hard to find good papers on them.

The main reasons why kd-trees are faster are because:
1. If built correctly they maximize the empty spaced traversed which reduces traversal time.
2. If designed correctly they can be VERY hardware friendly (The books "Graphics Programming Methods" and "Real-Time Collision Detection") have some details on how to do so.

Kd-trees can be very expensive to build but very cheap to traverse. The Siggraph 2005 notes on Real Time Ray Tracing have a good presentation on Kd-trees.

Note that Kd-trees can be succesfully used on games for ray casting on static geometry (not for rendering), and IMHO there is not a single spatial structure that works well with dynamic and static geometry.

Share this post


Link to post
Share on other sites
It depends on so many factors that saying "the fastest" is pointless.

For a system where you can to trivial comparisons, AND can build an optimal BSP outside of your performance constratints, AND your lookups fit the BSP search model, then they can be optimal for search time.

For a system where you are examining zones or are working with dynamic data inside zones, AND you can generate kd trees outside your performance constraints, AND you can trivially compute the zone(s) that an object lies in with a simple formula, then a kd-tree can be optimal for search time.

kd tree has a benefit that you can directly compute the zone, no lookups required. There is a tradeoff of space, and some search operations are extremely difficult.

bsp trees have the benefit that they match binary trees and will give search results very quickly, consume relatively little memory, and work very well with static data.

The two trees can be searched in roughly the same way; the performance from each depends on how you use them.

Share this post


Link to post
Share on other sites
Just to be clear:

Kd-trees ARE BSP-trees with partitioning constraints on axis aligned planes.

And the conditions in which kd-trees perform faster than other data structures are:
- Static geometry (Geometry does not move or change shape)
- Queries used are for ray shooting only
- Implemented on some modern computer architectures with some kind of processor cache

This also assumes that:
- You can build the tree offline
- You are going to be spending lots of time casting rays against static geometry which makes the time spent building trees negligible

Like most spatial data structures you can come up with a scene that generates a horrible kd-tree and makes traversal very expensive. But this is true for every single spatial partitioning data structure.

I would not use Kd-trees (Or BSPs in general) for dynamic geometry, or for broad phase collision detection. For games I would use it as a paritioning data structure for the static geometry. More common is to use kd-trees on global illumination renderers that are based on ray shooting algorithms.

Share this post


Link to post
Share on other sites
Just a side note really, but:

I have not seen a single cosmological simulation that used BSP trees.

Cosmological simulations use methods of approximating the result of N-Body integration on a system.. and generally with *extremely* large N.

As such they do not concern themselves at all with rendering issues, but instead with the much broader stroke of interactions and transitions between (in the case of tree's) volumes that are dynamically changing.

Only two notable cosmological algorithms use tree structures, and those two structures are KD-tree's and Oct-tree's.

Food for thought anyways.


Share this post


Link to post
Share on other sites

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