How to create a BSP tree?
Author
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]
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...
Author
I've been searching around for about 3 months now but still can't find anything. If it's so easy, can you please give me 1 useful link?
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.
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.
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
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.
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.
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.
So you can colide only the nodes of the world that need to be colided.
Author
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?
This topic is closed to new replies.
Advertisement
Popular Topics
Advertisement