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