BSP trees [Resolved, now also with Quad, Oct, AABB, K-D, BV, OBB, BR, ABT, BS trees]
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.
I used to have but seems like the links aren't working. anyways I can instruct you how to make a BSP tree
Use
writing software in C++ is like driving rivets into steel beam with a toothpick.
writing haskell makes your life easier:
reverse (p (6*9)) where p x|x==0=""|True=chr (48+z): p y where (y,z)=divMod x 13
To throw away OOP for low level languages is myopia, to keep OOP is hyperopia. To throw away OOP for a high level language is insight.
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
Use
writing software in C++ is like driving rivets into steel beam with a toothpick.
writing haskell makes your life easier:
reverse (p (6*9)) where p x|x==0=""|True=chr (48+z): p y where (y,z)=divMod x 13
To throw away OOP for low level languages is myopia, to keep OOP is hyperopia. To throw away OOP for a high level language is insight.
ok this is probably the most ugliest pic i've ever drawn, but you get the idea
Use
writing software in C++ is like driving rivets into steel beam with a toothpick.
writing haskell makes your life easier:
reverse (p (6*9)) where p x|x==0=""|True=chr (48+z): p y where (y,z)=divMod x 13
To throw away OOP for low level languages is myopia, to keep OOP is hyperopia. To throw away OOP for a high level language is insight.
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/
Use
writing software in C++ is like driving rivets into steel beam with a toothpick.
writing haskell makes your life easier:
reverse (p (6*9)) where p x|x==0=""|True=chr (48+z): p y where (y,z)=divMod x 13
To throw away OOP for low level languages is myopia, to keep OOP is hyperopia. To throw away OOP for a high level language is insight.
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.
Use
writing software in C++ is like driving rivets into steel beam with a toothpick.
writing haskell makes your life easier:
reverse (p (6*9)) where p x|x==0=""|True=chr (48+z): p y where (y,z)=divMod x 13
To throw away OOP for low level languages is myopia, to keep OOP is hyperopia. To throw away OOP for a high level language is insight.
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
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
Articel/Tutorial
yeah well that doesn't say much, but you could trust me to find one that is theoretical
Use
writing software in C++ is like driving rivets into steel beam with a toothpick.
writing haskell makes your life easier:
reverse (p (6*9)) where p x|x==0=""|True=chr (48+z): p y where (y,z)=divMod x 13
To throw away OOP for low level languages is myopia, to keep OOP is hyperopia. To throw away OOP for a high level language is insight.
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..
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
Use
writing software in C++ is like driving rivets into steel beam with a toothpick.
writing haskell makes your life easier:
reverse (p (6*9)) where p x|x==0=""|True=chr (48+z): p y where (y,z)=divMod x 13
To throw away OOP for low level languages is myopia, to keep OOP is hyperopia. To throw away OOP for a high level language is insight.
Hehe....don't start to irritate me again...I don't have the time today to argue with you...
I see your point....But I won't admitt that I am wrong......I never will...
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...
Originally posted by NoteMe Hehe....don't start to irritate me again...I don't have the time today to argue with you...
gheeheheehe why else would I be posting here
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...
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
Use
writing software in C++ is like driving rivets into steel beam with a toothpick.
writing haskell makes your life easier:
reverse (p (6*9)) where p x|x==0=""|True=chr (48+z): p y where (y,z)=divMod x 13
To throw away OOP for low level languages is myopia, to keep OOP is hyperopia. To throw away OOP for a high level language is insight.
Originally posted by kedaman gheeheheehe why else would I be posting here
To teach others..and ask questions..
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
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..
Originally posted by NoteMe To teach others..and ask questions..
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..
but a quad tree is a BSP tree
Use
writing software in C++ is like driving rivets into steel beam with a toothpick.
writing haskell makes your life easier:
reverse (p (6*9)) where p x|x==0=""|True=chr (48+z): p y where (y,z)=divMod x 13
To throw away OOP for low level languages is myopia, to keep OOP is hyperopia. To throw away OOP for a high level language is insight.
yeah, thats what it does, binary space partititioning, oct and quad are just the amount of dimensions log2-ed
Use
writing software in C++ is like driving rivets into steel beam with a toothpick.
writing haskell makes your life easier:
reverse (p (6*9)) where p x|x==0=""|True=chr (48+z): p y where (y,z)=divMod x 13
To throw away OOP for low level languages is myopia, to keep OOP is hyperopia. To throw away OOP for a high level language is insight.
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.......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....????
Originally posted by bobthebobert Are BSP's effective at drawing a top down perspective, or just a FPS?
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....
Originally posted by NoteMe Heheh,.,..Then I didn't understand the theory at the page you showed me.......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....????
no idea.. perhaps he was talking about BSP trees in general since oct trees are just a special case
Use
writing software in C++ is like driving rivets into steel beam with a toothpick.
writing haskell makes your life easier:
reverse (p (6*9)) where p x|x==0=""|True=chr (48+z): p y where (y,z)=divMod x 13
To throw away OOP for low level languages is myopia, to keep OOP is hyperopia. To throw away OOP for a high level language is insight.
Originally posted by bobthebobert Are BSP's effective at drawing a top down perspective, or just a FPS?
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.
Use
writing software in C++ is like driving rivets into steel beam with a toothpick.
writing haskell makes your life easier:
reverse (p (6*9)) where p x|x==0=""|True=chr (48+z): p y where (y,z)=divMod x 13
To throw away OOP for low level languages is myopia, to keep OOP is hyperopia. To throw away OOP for a high level language is insight.
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
Use
writing software in C++ is like driving rivets into steel beam with a toothpick.
writing haskell makes your life easier:
reverse (p (6*9)) where p x|x==0=""|True=chr (48+z): p y where (y,z)=divMod x 13
To throw away OOP for low level languages is myopia, to keep OOP is hyperopia. To throw away OOP for a high level language is insight.
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...
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..) 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...
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.
Use
writing software in C++ is like driving rivets into steel beam with a toothpick.
writing haskell makes your life easier:
reverse (p (6*9)) where p x|x==0=""|True=chr (48+z): p y where (y,z)=divMod x 13
To throw away OOP for low level languages is myopia, to keep OOP is hyperopia. To throw away OOP for a high level language is insight.
here's a diagram, the yellow represents the theoretical binary tree, and the quad tree
Use
writing software in C++ is like driving rivets into steel beam with a toothpick.
writing haskell makes your life easier:
reverse (p (6*9)) where p x|x==0=""|True=chr (48+z): p y where (y,z)=divMod x 13
To throw away OOP for low level languages is myopia, to keep OOP is hyperopia. To throw away OOP for a high level language is insight.
yeah go ahead and discuss those because i have no idea what they are
Use
writing software in C++ is like driving rivets into steel beam with a toothpick.
writing haskell makes your life easier:
reverse (p (6*9)) where p x|x==0=""|True=chr (48+z): p y where (y,z)=divMod x 13
To throw away OOP for low level languages is myopia, to keep OOP is hyperopia. To throw away OOP for a high level language is insight.
Originally posted by kedaman here's a diagram, the yellow represents the theoretical binary tree, and the quad tree
HEhe....didn't think of it like this before......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...
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.......I just wish that I didn't have this ****ing hang over...
Reply With Quote
