Anyone got any links to some articles/tutorails about BSP trees? I am thinking about using quad trees or oct trees for for my outdoor terrain engine in DX9. But I wan't to explore the possibilities before I head away with the coding.
Anyone?
Anyone got any links to some articles/tutorails about BSP trees? I am thinking about using quad trees or oct trees for for my outdoor terrain engine in DX9. But I wan't to explore the possibilities before I head away with the coding.
Anyone?
I used to have but seems like the links aren't working. anyways I can instruct you how to make a BSP tree ;)
What does BSP stand for..BTW...Binary Seach P????
Yeah if you could do that, it will at least be a start, and maybe I even understand how to implement it to use it in my terrain engine, to calculate the view frustum...
Binary Space Partitioning. If you know what a binary tree is then you're half the way there already. a BSP tree is a binary tree which splits up all objects in partitions, by dividing the space in two for each node. A quad tree does this in two dimension while an oct tree does it in three
ok this is probably the most ugliest pic i've ever drawn, but you get the idea ;)
http://www.vbforums.com/attachment.p...postid=1662071
I know what a quad tree and a oct tree is....but don't know what a BSP tree is,...can you show me a picture of an BSP tree in action...
Here is my quad tree in action...
http://www.vbforums.com/attachment.p...postid=1662074
Forget about me asking about a picture, I can see you have posted something now...not sure what it is but give me some time to dechiffer it...:D
Hehe...ok, I got the idea..even if it took more time to dechiffer the drawing then it took to understand the idea..:DQuote:
Originally posted by kedaman
ok this is probably the most ugliest pic i've ever drawn, but you get the idea ;)
http://www.vbforums.com/attachment.p...postid=1662071
hehe.. i told you it was ugly ;)
anyways I found a link here for you anyway, which is quite good i think ;)
http://cs.smith.edu/~mcharley/bsp/
Wow...thanks...thats much better then all the links I have found...thanks again..
You might find something here:
http://www.gametutorials.com/Tutoria...OpenGL_Pg5.htm
Thanks I knew about that. But I don't find the BSP tutorials very general. They are to stuck on the Quake format and OGL, I wanted it more in general. Like the Oct Tree tutorial they have there. The link Keda gave me was actually pretty good.Quote:
Originally posted by cyborg
You might find something here:
http://www.gametutorials.com/Tutoria...OpenGL_Pg5.htm
hehe always better in the more general form ;)
Not always, but first og all I am using DX second of all this as more or less nothing to do with the graphics API you are using....so it was the theory I was looking for. That was why I wrote Articel/Tutorial, and not just tutorial...;)
when i saw this first i thought you were writing norwegian :DQuote:
first og all
its always better with theory first, then implementation ;) think of how much work can be saved if people did this instead of writing tutorial for every language and api etc ;)
yeah well that doesn't say much, but you could trust me to find one that is theoretical ;)Quote:
Articel/Tutorial
Me too! :bigyello:Quote:
Originally posted by kedaman
when i saw this first i thought you were writing norwegian :D
Me too...:DQuote:
Originally posted by cyborg
Me too! :bigyello:
Yeah Keda...you are right (at least a little bit), but then you have to write one for the theory, and one for all the APIs, thats one more then not writing theory at all..:D
No note, you just refer to the theory page from the implementation page ;) and if you leave out the theory completely you have only one way of doing things, without understanding how and why it works ;)
Hehe....don't start to irritate me again...I don't have the time today to argue with you...:D
I see your point....But I won't admitt that I am wrong...:D...I never will...:D
I must admitt that most often when I deal with an advanced topics for the first time like when I started to learn Vertex Shaders, Pixel Shaders...then I didn't understand much of the theory before I jumped into the coding...but it was nice to refer back to later when I understood what the theory was all about...
Quote:
Originally posted by NoteMe
Hehe....don't start to irritate me again...I don't have the time today to argue with you...:D
gheeheheehe :D why else would I be posting here ;)
Yeah, part of learning theory must be seeing what its for, otherwise its nonsense metaphysics ;) So its no use to learn any theory if you don't set out and do something with it as well ;)Quote:
I must admitt that most often when I deal with an advanced topics for the first time like when I started to learn Vertex Shaders, Pixel Shaders...then I didn't understand much of the theory before I jumped into the coding...but it was nice to refer back to later when I understood what the theory was all about...
To teach others..and ask questions..:DQuote:
Originally posted by kedaman
gheeheheehe :D why else would I be posting here ;)
I often learn things in theory and find out that I don't need to try it in practice at all..like the BSP tree..I don't need that for my out door terain engine....an extended quad three will do the job....;)Quote:
Originally posted by kedaman
Yeah, part of learning theory must be seeing what its for, otherwise its nonsense metaphysics ;) So its no use to learn any theory if you don't set out and do something with it as well ;)
But I will try it for an indoor envirment once I have time....probably 10 years from now..:D
but a quad tree is a BSP tree ;)Quote:
Originally posted by NoteMe
To teach others..and ask questions..:D
I often learn things in theory and find out that I don't need to try it in practice at all..like the BSP tree..I don't need that for my out door terain engine....an extended quad three will do the job....;)
But I will try it for an indoor envirment once I have time....probably 10 years from now..:D
Hmmm...not the way I am using it....I am bending all rules here...:D...trying out some teories....:D
But do you mean it...I can't see that it is the same thing here...
so is oct tree a BSP tree too then?
yeah, thats what it does, binary space partititioning, oct and quad are just the amount of dimensions log2-ed
Are BSP's effective at drawing a top down perspective, or just a FPS?
Quote:
Originally posted by kedaman
yeah, thats what it does, binary space partititioning, oct and quad are just the amount of dimensions log2-ed
Heheh,.,..Then I didn't understand the theory at the page you showed me....:D...and wy did theis guy ask what games used oct trees and what games used BSP trees in this thread if it is the same....????
http://www.beyond3d.com/forum/viewtopic.php?t=11084
Just FPS or when you can see more then just top down...then you don't have to draw everything behind you and things like that....at least I can't see the big advantage of using it in a top down game....Quote:
Originally posted by bobthebobert
Are BSP's effective at drawing a top down perspective, or just a FPS?
no idea.. perhaps he was talking about BSP trees in general since oct trees are just a special case ;)Quote:
Originally posted by NoteMe
Heheh,.,..Then I didn't understand the theory at the page you showed me....:D...and wy did theis guy ask what games used oct trees and what games used BSP trees in this thread if it is the same....????
http://www.beyond3d.com/forum/viewtopic.php?t=11084
yeah sure, in a strategy game you would benefit too having units starting attack the enemy if they come close for instance.. and generally you would need to do collision detection anyway. Just use a quad tree.Quote:
Originally posted by bobthebobert
Are BSP's effective at drawing a top down perspective, or just a FPS?
Quote:
Originally posted by kedaman
yeah sure, in a strategy game you would benefit too having units starting attack the enemy if they come close for instance.. and generally you would need to do collision detection anyway. Just use a quad tree.
I can't see the point....if you have a top down game, you know all the coordinates, and you can only do ONE boundingBox check to see what is going to be drawn, the same with when they are going to start to attack. Fussy Logic is great for simple, "When does the enemy attack AI"....
its not about knowing the coordinates, its about reducing search time, and trees are good for just that. If you have one bounding box, then search time is n, if you have a tree, search time is logn
What the hell did I think of when I wrote those last two posts.....I also think it can be usefull in a 2D game, maybe even a solling 2D game.
But quad and oct trees are not that fast in a very dynamic environment. Then they use to much time to update a tree...I have heard that Sphere trees can be faster for that...
BTW, in one of the Gems in Game Programing Gems 2 there is a section about Compressed AABB, and a quote from the first section goes like this:
Quote:
This section covers quadtrees, k-d trees, BSP trees, bounding volume trees, and axis-aligned bounding boxes...
So I guess it is not the same anyway....let me draw you a picture Keda...
If you look at this, I am not sure if I got the BSP tree right, but for me it looks like the BSP tree always devide the part of the map in two. First you have the whole map, then devide it in two (hence the size of my nodes..:D) then devide those two parts in two, and so on...
In a quad tree you devide the the whole map (root) in four, then you devide those parts in 4 again...and so on...
So it is not the same tree.
If you look at my drawing, you will see the two trees the way I think they are...(I know my quad tree is right), and if you look at the first drawing I made you see the whole map and how it is devided into the other levels in the tree...
http://vbforums.com/attachment.php?s=&postid=1663381
technically its not the same tree no (i never said that ;)), but theoretically a quad tree classes as a BSP tree, basically the only thing you have more in quad trees is that two levels are unified in one, so each node consists of 3 bsp nodes.
here's a diagram, the yellow represents the theoretical binary tree, and the quad tree
http://www.vbforums.com/attachment.p...postid=1663387
You like to admitt that you where wrong just as much as me...don't you...:D:D:D:D
A BSP tree has a left and right (Java/C/C++)pointer, but a quad tree has a A, B, C, and D (Java/C/C++)pointer to the next nodes.
A mother leaf in a BSP tree has 2 child leafs, a mother leaf in a quad tree has 4 child leafs...thats the way it is...
are we going to discuss
- k-d trees
- bounding volume trees
- AABB trees
now???..::D
no way i'm going to admit i'm wrong, when i'm not ;)
yeah go ahead and discuss those because i have no idea what they are
Quote:
Originally posted by kedaman
here's a diagram, the yellow represents the theoretical binary tree, and the quad tree
http://www.vbforums.com/attachment.p...postid=1663387
HEhe....didn't think of it like this before...:D...you are some kind of smart I gues...;)....but if this is the case, then I can't see the advantage of BSP trees over Quad threes, they have to go through more levels in a BSP tree.
They have more tests in a QUAD tree, but the smart instruction set in a x86 prosessor has some nice way to make these tests really really fast...
Quote:
Originally posted by kedaman
no way i'm going to admit i'm wrong, when i'm not ;)
yeah go ahead and discuss those because i have no idea what they are
Not me either....but I found this discussion the most intresting since the Arie (Hue/Saturation) thread...so I am nearly intrested in reading about them right now...I have that Gem from my book...:D....I just wish that I didn't have this ****ing hang over...:D
hehehe.. thats what you get for drinking too much ;)
no use having a look at trees you're never going to use ;)
But if they are better suited for one job, you know ways around the problem if oyu know about them. Thats a better solution the trying to make a tree fit your needs when it don't...Quote:
Originally posted by kedaman
hehehe.. thats what you get for drinking too much ;)
no use having a look at trees you're never going to use ;)
yeah but then you go look for the tree when you need it, not learn all sorts of stuff and then don't need it. Thats like going out and buy loads of stuff just because its cheap, then you figure out you don't actually need them
No that is not the same thing....it's more like
You go out, see things....now you know about them (reads the thory), but you don't buy them (implement them/use them). When you get to a situation where you need them (if you didn't read the theory, you don't know this tool is great for the job), then you know where to look for them.
Quote:
Bounding volume trees approach the problem diffrently then Oct/BSP/K-D trees. Instead of dividing space, bounding volume trees recursively divide a set of triangles into two subsets and fin a bounding volume that enclosure each subset. This approach avoids having to split triangles or include them in multiple nodes, and building a tree simply stops when a subset has only one remaining triangle. For more information on bounding volume tree, see [vandenBergen99]
yeah i was thinking about that too.. it was actually in the link i posted, they picked a wall and split everything in what was in front of and behind it.. its still a BSP tree after all
After reading more here, I am not so sure if you are right anyway....you are trying to bend the rules here....don't call everything you see a BSP tree...:D
Alle these structures are binary trees, they are just diffrent versions of it....ahha...let me draw again....:D
Here is how they are related...;)
And remember that all quad tree, oct tree and so on has a lot of diffrent way to bi implemented too....so I guess that there should have been one more level in that tree too..:D
http://vbforums.com/attachment.php?s=&postid=1663403
BTW I guess Heap and BS tree are Binary trees too...arn't they?
Best web page about K-D trees in the whole world I guess..:D
http://www.rolemaker.dk/nonRoleMaker...gem/kdtree.htm
no way note, they all partition space, and they are all binary ;) Heaps and.. do you mean BR tree? are binary trees yeah but they don't partitition spaceQuote:
Originally posted by NoteMe
Here is how they are related...;)
And remember that all quad tree, oct tree and so on has a lot of diffrent way to bi implemented too....so I guess that there should have been one more level in that tree too..:D
http://www.vbforums.com/
BTW I guess Heap and BS tree are Binary trees too...arn't they?
btw quad and oct are sort of malnamed, they should be Bool^2 and Bool^3
Yeah, that is what my image shows...they are all binary trees..but non of them is more related then that...all of the trees are "derived" from the binary tree, but no one of the others you see here are "derived" from BSP tree.Quote:
Originally posted by kedaman
no way note, they all partition space, and they are all binary ;) Heaps and.. do you mean BR tree? are binary trees yeah but they don't partitition space
Heap and BS (I ment BS tree) are also binary trees, but I didn't add them to the picture becuase they are not partitioning space...;)...
Quote:
Originally posted by kedaman
btw quad and oct are sort of malnamed, they should be Bin^2 and Bin^3
They are called quad (4) becuase it devides into 4 elements rather then 2, and there is no way you are ever going to make me say Binary^2 or what ever...
Last link I am up for today...
AABB tree tutroail
http://www.flipcode.com/dp/dpcolumn_issue05.shtml
Quote:
Originally posted by NoteMe
Yeah, that is what my image shows...they are all binary trees..but non of them is more related then that...all of the trees are "derived" from the binary tree, but no one of the others you see here are "derived" from BSP tree.
which is what i disagreed with because they all partition space
[/quote]
Heap and BS (I ment BS tree) are also binary trees, but I didn't add them to the picture becuase they are not partitioning space...;)... [/QUOTE]
whats a BS tree`? bull**** treè? :D
of course there is, i'm here to correct the stupid programmers who have named those things out of their stupid heads ;)Quote:
Originally posted by NoteMe
They are called quad (4) becuase it devides into 4 elements rather then 2, and there is no way you are ever going to make me say Binary^2 or what ever...
BS != Binary Sh! tree
BS == Binary Search tree
what is a BR tree?
Binary "rumpe" tree?
I must admitt that I don't understand what you disagree with me on the drawing....can you draw it like you meen...
Quote:
Originally posted by kedaman
of course there is, i'm here to correct the stupid programmers who have named those things out of their stupid heads ;)
BTW why did you change it too bool^2..that is even worse..
that sounds relatively cool, although I think two triangles can be inseparable stillQuote:
Originally posted by NoteMe
Last link I am up for today...
AABB tree tutroail
http://www.flipcode.com/dp/dpcolumn_issue05.shtml
lol.. binary search trees hehe :D I think all binary trees are search trees, why would you use trees if not for searching ;)Quote:
Originally posted by NoteMe
BS != Binary Sh! tree
BS == Binary Search tree
what is a BR tree?
Binary "rumpe" tree?
I must admitt that I don't understand what you disagree with me on the drawing....can you draw it like you meen...
BR means Black Red trees let me find a link