Jump to content
  • Advertisement
Sign in to follow this  
Hannesnisula

How to create a BSP tree?

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

  • Advertisement
×

Important Information

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

We are the game development community.

Whether you are an indie, hobbyist, AAA developer, or just trying to learn, GameDev.net is the place for you to learn, share, and connect with the games industry. Learn more About Us or sign up!

Sign me up!