Jump to content
  • Advertisement
Sign in to follow this  
bnadland

Are BSP trees the fastest?

This topic is 4696 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
Advertisement
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
Sign in to follow this  

  • Advertisement
×

Important Information

By using GameDev.net, you agree to our community Guidelines, Terms of Use, and Privacy Policy.

GameDev.net is your game development community. Create an account for your GameDev Portfolio and participate in the largest developer community in the games industry.

Sign me up!