• Advertisement
Sign in to follow this  

How to create a BSP tree?

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

1) If I want to split up the world (terrain) with an algorithm running everytime I load the game, what's the best/fastest way to do that? Shouldn't it be the best to make planes for the terrain, and somehow create planes for "curved" terrain? 2) Can someone refer me to some book/tutorial/source code which calculates some kind of BV tree (BSP or something) and explains how it actually works, in detail? 3) Is every leaf in such a tree just 1 single volume (plane, box, sphere)? If the object to check for collisions (the movable object) is in motion; is it a good way to create a bounding volume around the current position of the object and the "next" position and then check that volume for collisions? What if an object may collide with multiple leaves in the tree? [Edited by - Hannesnisula on January 23, 2009 11:20:01 AM]

Share this post


Link to post
Share on other sites
Advertisement
Quote:
Original post by Hannesnisula
1) If I want to split up the world (terrain) with an algorithm running everytime I load the game, what's the best/fastest way to do that? Shouldn't it be the best to make planes for the terrain, and somehow create planes for "curved" terrain?


Depends on how you are planning to use the BSP structure.

Quote:
2) Can someone refer me to some book/tutorial/source code which calculates some kind of BV tree (BSP or something) and explains how it actually works, in detail?


Do some research on your own first. It doesn't sound like you've spend 5 minutes on google yet...

Share this post


Link to post
Share on other sites
Why a bsp tree ? they come from an old age and are probably not the way to go anymore.
It's hard to compute, not suited for dynamic scenes, limited to indoor, requires that geometry is "closed", very sensilble to precision errors, etc...
If it's for a terrain, search for oc trees or quad trees, it should be a good start, and you'll find tons of infos.

Share this post


Link to post
Share on other sites
Quote:
It's hard to compute, not suited for dynamic scenes, limited to indoor, requires that geometry is "closed", very sensilble to precision errors, etc...


BSP trees are simple to produce, and can be well suited to dynamic scenes. It depends on the scene and what you want to do with it. They are NOT limited to indoor and do NOT require geometry to be closed. They are also not sensitive to precision. I don't know where you get all these ideas from.

Hannesnisula, I cannot give you any specific suggestions without knowing how you plan to use the structure.

Here is a general link, I suggest you read this page and all of the sub-references

http://en.wikipedia.org/wiki/Space_partitioning

Share this post


Link to post
Share on other sites
Oh man, bsp trees involve a lot of geometric and polygonal computations, wich are not fast and pretty sensible to numeric precision.

They are not easy to produce at all in the sense that some complex polygon spliting is involved, and a lot of corner cases are to be taken into account.
Plus, it's hard to control the tree creation.

Also you definitely can't use them for dynamic geometry, simply because bsp trees create very complex partitions, and a single moving triangle can require to rebuild the whole partition.

On the other hand, once the tree is built, they have the advantage to be pretty fast and accurate, but building the tree is the problem.

Definitely, you can't compare the complexity of a bsp tree and the complexity of an oc tree for exemple. An oc tree will be one hundred times easyer to implement, will be more stable, will give less headaches to his coder, and best of all, will be better suited than a bsp tree because the bsp comes with a lot of limtations that the coder will have to deal with one day.

Share this post


Link to post
Share on other sites
For colision detection, something like an oc tree can help you to quickly identify potentialy coliding nodes in the tree, and then greatly reduce the scope of the search.
So you can colide only the nodes of the world that need to be colided.

Share this post


Link to post
Share on other sites
Well, what I've read so far, a BSP tree doesn't seem to be limited or anything. A BSP tree doesn't seem more complex than any other tree, then again; from what I've read this far. Could you tell me what makes it so more harder to do than an octree or something?

Share this post


Link to post
Share on other sites
even though its old its still very useful but getting it right takes a bit of know how. Before going off and implementing the bsp tree go and research data structures i general. See what it is that make them so useful from there ask your self what do i really want it to do and which architecture is best suited for my application.

Bsp tree is a tree like data structure. Like all tree structure they connect data in a tree like manner through the use of nodes. In graphics this can be done dividing the scene up. This is where bsp is mainly used but it has many usages. it can orgranize a scene and do much more. look at wiki for more detail around bsp and look at papers for implementations of such datastructures

Share this post


Link to post
Share on other sites
kd-trees are a subset of BSP trees that are very good for doing efficient raytracing. You might want to do raytracing for a number of reasons.

a) you may be using raytraced rendering
b) you may be generating ambient occlusion maps
c) you may be shooting bullets or lasers
d) you may be trying to have one object follow along the surface of another object, requiring you to shoot rays at the object and find where they intersect (ie, for walking on a mountainous surface)

There are, of course, many other possible scenarios.

I haven't focused much on collision stuff, so I am not totally sure what is best to use for that. I do know that you typically form geometrically simplified versions of your models, and then may nest those in AABB's and such. You probably wouldn't use a BSP tree for object-object collision detection.

Share this post


Link to post
Share on other sites
point is that you dont want to check everything because that would be pointless and slow think of how you are partioning the scene and find whats near you and check them

Share this post


Link to post
Share on other sites
theres is a trade off in getting in fast but im sure you know that. Google quick collision response it should show up something. Maybe bounding sphere where you check the location in a certain range which is the radius.

Share this post


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

  • Advertisement