Are BSP trees the fastest?
Author
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?
Quote:Original post by cignox1I 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.
AKAIK kd-tree are considered the fastest for ray-tracing.
Author
Why are there so much Articles & Tutorials on BSP trees then?
They are fairly complex, aren't they?
They are fairly complex, aren't they?
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.
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.
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.
@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.
Quote:Original post by PromitQuote:Original post by cignox1I 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.
AKAIK kd-tree are considered the fastest for ray-tracing.
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.
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.
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
<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
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.
This topic is closed to new replies.
Advertisement
Popular Topics
Advertisement
