BSP trees [Resolved, now also with Quad, Oct, AABB, K-D, BV, OBB, BR, ABT, BS trees]

If you have a big map you can scale it to 0-256 (just arbitrary values, but it helps if they are in power of 2. Like 256 is representated in binary as

11111111

8 bits


http://www.vbforums.com/attachment.p...postid=1663675

Now the red thing on the drawing is an object. If we look at the X possition of the object the start of the object are in about:

X1 = 155,4

and the right side of it is about

X2 = 166.1

and lets say that the top is:

Y1 = 140.1

and bottom is:

Y2 = 150.2

Now since the map is 255 wide, we can use some nice XORing to find out in what level it is. If you look at the drawing you can see that the big black square is a representation of the whole map. We devide it in 4 new sqares that becomes level one in our quad tree

Old picture:
http://www.vbforums.com/


Then those sqares are again devided into 4 sqares that becomes level 2. And so on. We have 9 levels like that. I have only drawn drawn 4 levels, included the root level that is the whole square. You can see that it gets hit on the midle of level 4 in the drawing. So it belongs to level 3. That is included the root level. So we find it in code like this:

We XOR the integer values of the X coordinates of the object we get:

X1: 155=10011011
X2: 166=10100110
------------------------
XOR Res: 00111101

The first "1" bit is in posistion 6. So if we have 9 levels we can just take 9-6 and we get 3.

So we know it is in level three so we wil insert it there...

Look here....it's the green dot.
http://vbforums.com/attachment.php?s=&postid=1663660

But I have just inserted it in a node...but I now only know what level it is supposed to go in...Again, the power-of two dimensionality of our tree makes this a simple task. If all sectors of a given tree level are stored in a 2 dimensional array, the proper section can be found by taking the coordinates of the object being tested and converting them to the scale of the node grid at the tree level. Tree level 2 at the drawing contains 2X2 grid of nodes. Therefor, the coordinates of our object have to be scaled to into the range [0,1] on each axis to find the column and row.

A simple shift operation does the trick. Coordinates of our level are in the range [0,63] (Remeber the whole thing was [0,255])., 6 bits. To get them to range [0,1], we need to convert them to 1-bit values. Shifting the coordinate values to the right by 5 places will perform the conversion (8-bit value to 1-bit value is a right shift of 7). For our object, we take the coordinates (155,140) that is actually (27,12) on this level and shift them down 5 places....

what is the answer of this again.....ehhhh....[0,0]. And that is the up left sqare in the picture in level 3 (included the root)



Hope I didn't screw up the last part, I am not 100% sure of this...but it looks like it worked....tell me if you did fall off somewhere so I can explain that bit a bit better....

And remember that you should XOR the Y coordinates too, to see if the object maybe have to ho up an other level or two....

This is more or less a big tutorial now...:D


And I can see that I have got an answer in the PHP section...so then I can work more untill you post again...;)

Quote:

---

Originally posted by NoteMe
No it can be usfull for more then that....but it will be slower and slower. Untill you redo the whole thing. It's easier to implements then lots of other trees, thats why it is used that much. But if you have the time then you should use other trees for big amounts of data....

---

yeah you are right in that.. I just never got to implement the things myself just used the STL ;) and knowing just how the trees work theoretically is just fine enough for me, theres so much more you could do with trees, but I don't really have the need to go into all the details, i remember my teacher said there was a professor that was specilizing just on heaps, that must be a huge area and we only know the tip of an iceberg here hehe :D

yeah note, I think I've got it somehow now, thanks for taking so much time up to explain this for me (really very appreciated)

Still when you say that each level has their own 2d array, I was sortf of, ***, because whats the point in having the tree if you can have a 2d array at bottom level, even that would save space, and do searchign much simpler as well.

all the xoring and bitshifting is neat and efficient but this really put me off, i hope theres a catch somewhere because it sounded good at first, or I could be wrong here though..

Quote:

---

Originally posted by kedaman
yeah you are right in that.. I just never got to implement the things myself just used the STL ;) and knowing just how the trees work theoretically is just fine enough for me, theres so much more you could do with trees, but I don't really have the need to go into all the details, i remember my teacher said there was a professor that was specilizing just on heaps, that must be a huge area and we only know the tip of an iceberg here hehe :D

---

Hehe..yeah...as long as I know what it is...and how it works...and when to use what I am fine....Seldom implements stuff like this anyway....But I have been a teacher in Algoriths in Java for 5 months now....for beginners tho'...so I should probably know more about it....but I at least know enough to tell them what to do, and when to do it....

hehe.. cool teacher ;)

Quote:

---

Originally posted by kedaman
yeah note, I think I've got it somehow now, thanks for taking so much time up to explain this for me (really very appreciated)

Still when you say that each level has their own 2d array, I was sort of, ***, because whats the point in having the tree if you can have a 2d array at bottom level, even that would save space, and do searchign much simpler as well.

all the xoring and bitshifting is neat and efficient but this really put me off, i hope theres a catch somewhere because it sounded good at first, or I could be wrong here though..

---

It is really fast...it fell in love with it first time I did read abou it....


I think I explained a bit bad at the end, because I have never implemented it my self. I will in a couple of weeks, but right now I just know the theory. It is not a 2D array in the end. There is 4 leafs on every level. But to calculate what leaf to put the object in. You look at it like an 2D array.

So when you have shifted the bits you will get a 0-1 range X and Y coordinate. So you know what leaf to put it in.


Here is a drawing of what I mean. Look at the pic sqare as Level 1 (root) and the 4 smaller sqares as Level 2

http://www.vbforums.com/attachment.p...postid=1663749


The other array part I was talking about, that I also might have explained a bit bad is that if you make the whole tree with on alloc. You get all the memory you need for the rest of the game. And the leafs will lie down after each other in memory. That way you won't get that much cach misses when you seach the tree. And if you want to alter one node, you can calculate your way to that node rather then go through the tree becuase it is laied down as an array in memory.

The other advantage of this is that you don't have to make new objects or destroy them when you are in the game. Just alter them and run thrue them.

The draw back is that it takes up a bit of memory. But It is worth it for the speed.

Quote:

---

Originally posted by kedaman
hehe.. cool teacher ;)

---

What do you mean by that...:D

Quote:

---

It is really fast...it fell in love with it first time I did read abou it....


I think I explained a bit bad at the end, because I have never implemented it my self. I will in a couple of weeks, but right now I just know the theory. It is not a 2D array in the end. There is 4 leafs on every level. But to calculate what leaf to put the object in. You look at it like an 2D array.

So when you have shifted the bits you will get a 0-1 range X and Y coordinate. So you know what leaf to put it in.


Here is a drawing of what I mean. Look at the pic sqare as Level 1 (root) and the 4 smaller sqares as Level 2

---

Things still remain unclear to me, where does the arrays reside in memory, are they all the size of 2x2 or what..

thanks for your time.. teacher ;)

Quote:

---

Originally posted by kedaman
Things still remain unclear to me, where does the arrays reside in memory, are they all the size of 2x2 or what..

thanks for your time.. teacher ;)

---

I was going to explain this for you with showing you a Binary Tree. But when I had finished the drawing I realised that I was sligthly wrong about what I said in the last part. It was a bad example in the book I did read abou the oct treee. So I must have missunderstood one part.

But anyway. I guess you know that a binary tree can be written either using nodes, or an array. This picture represent the array. People often use nodes, becuase it makes it dynamical. But using an array to represent it is much faster due to less cach misses, and that you can calculate the level with taking:

(root is level1)

level * 2

and then you have

2^(level - 1) nodes in that level. And they lie right after each other in the array...Then you can directly access the index.

The explenation of the rest have to waith untill an other day. Time is now 23 here, and I have been working 13 hours, and tomorrow I am going to work 15 hours. So I have to get my rest now....


But short explenation of what was wrong in my explenation. I said it had to be mapped to a [0,1] value. That is not true....or that is true if it was in Level 2. There you have 2*2 squares. But in our level we have 8*8 squares. So it has to be mapped to [0,8][0,8]...;)....I first realised that when I was drawing the picture....:(...sorry for that fault...I feel like an idiot....

Sorry...forgot to add the picture...here it is...:D

http://vbforums.com/attachment.php?s=&postid=1664468

Shifting wouldn't still work if only a few nodes were splitted up, would it?

What do you mean....all the parts are splitted up en qual parts. So you get a perfectly balanced quad tree. And to make it optimised, you make it stay perfectly balanced and don't add or delete nodes during the game...

Honestly I didn't read the whole discussion so I might have the wrong idea but this looks quite memory-expensive to me. In a 3d world for example you surely wouldn't need to expand every node down to level n.

If you have 9 levels...with 4 nodes that becomes 87000 nodes...and all of them contain more or less little to no data...so this is not that memory expecive, you can for smaller maps reduce it to 8 levels and get away with 22000 nodes...so it is a bit of memory But you have to tune the game to get the number of nodes that you need. But memory is better to use becuase you will use the screen cards memory for most of the vertex and texture etc data, and then you want to free the CPU for the calcultaions. So having a static tree is much faster then making it dynamicaly...and it is WAY faster to have some kind of tree then not havning any tree at all..then you will send ALL the objects to the rendering pipeline every time...and that will take a LOT of time to render...and you can only see small parts of it anyway....

Okay this makes sense, so we just waste memory to gain more speed :) Well, why not ^^

Off topic questions: Wasn't there a option to set custom titles when reaching 2048 postings? Was it raised to 4096?

Yaeh it is 4096...;)....

It's not about waisting memory, it is about moving the strain to the places it can be handeled the best. Like not make the CPU render, but letting the GPU render as much as it can...

Quote:

---

Originally posted by NoteMe
Sorry...forgot to add the picture...here it is...:D

http://www.vbforums.com/

---

damned.. it was as I thought :D Note, where is that link where you got this, if I'm right this oct tree is sort of totally worthless, because it does consume more memory than a 2d array at the bottom level :D (to be precise twice-1)

Quote:

---

Originally posted by kedaman
damned.. it was as I thought :D Note, where is that link where you got this, if I'm right this oct tree is sort of totally worthless, because it does consume more memory than a 2d array at the bottom level :D (to be precise twice-1)

---

But how fast can you search in a 2D array....;)...ann remmeber that oyu need all the nodes in level 1, level 2 and level 3 in your 2D array too...;)

no you don't, the access time is O(1) for an array

Yes you need the other nodes in the array too. Because they represent the one sqare that holds the 4 inner sqares. If an object spans two or more of those inner squares, you have to draw the whole "big" sqare. And that is the mother node...;)...so you need that one too...
¨
And I was not talking about the access time. I was talking about the search time....and remember what I said. The oct tree can be laied down like an array in memory...so you can't beat it in any way....with my representation o the oct tree, you have the advantages from both an array and a binary tree, but you have the disadvantage of using a lot of memory...

Quote:

---

Originally posted by NoteMe
Yes you need the other nodes in the array too. Because they represent the one sqare that holds the 4 inner sqares. If an object spans two or more of those inner squares, you have to draw the whole "big" sqare. And that is the mother node...;)...so you need that one too...
¨
And I was not talking about the access time. I was talking about the search time....and remember what I said. The oct tree can be laied down like an array in memory...so you can't beat it in any way....with my representation o the oct tree, you have the advantages from both an array and a binary tree, but you have the disadvantage of using a lot of memory...

---

Access time is search time for the array. And now you are not making any sense note, why would you have to draw the entire map if a small object is lying in the middle of the level1 nodes, when you could just check the nodes in the area of visibility

Look here at this picture. If the object spans more then one node in that level, you will put it in the mother node. That way you don't have to go throug all the child nodes, and you don't have to check them either.....

In this case, it will be saved in the Root (Level1) and you don't have to check the rest at all....

so how are you going to draw an object that is on level 4 lying next to that object?

I am not 100% sure about this, but I guess you just lie it down in the root too, becuase it is no use to put it in a lover level, as long as that whole level has to be drawn anyway....

No of course..I have thought it true...you will put it in the node where it belongs. It will be drawn anyway.

That also fixes the problem if an other object all ready was in level 4....:D

well in that case I think a 2d array is better anyway ;)

Well in that case I give up arguing with you...:D...


Lets both make a outdoor terrain engine. And ship it in late june, and lets see who manage to do it best...:D....my engine will at least try to use a quad tree for now...:D

hehe.. I wish I had the time ;) Maybe later on summer when I have time ;)

I will make my own anyway...that is why I first looked into the subject...but I have no idea when it is going to be finished.

I am thinking about using DX9 and VC++.NET. Never used either. But I have heard that .NET supports SSE, and VC++6 doesn't. So we will have to see how fast this will run...

don't worry about how fast it will run, if you want I could compile it for you as I have the .NET 2003 compiler

When we are on the topic....I don't have .NET 2003 yet....but do you know what the major changes is.

I read somewhere that they have changed the syntax for Templates. Anything else that you can add to my list...:D


BTW saw a nice article about how to derive all objects in a scene from a template and then add them to a render que. Sort them so you don't have to change the render method in DX for every object and then render. Pretty smart. And should be much faster then just rendering and changing the awsom slow render method for every object...

eh.. syntax on templates? no way note now you are talking crap :D
the templates are now handled more standard compliant than ever, if thats what you meant, but other than that AFAIK the optimation is better than any other compiler

Quote:

---

BTW saw a nice article about how to derive all objects in a scene from a template and then add them to a render que. Sort them so you don't have to change the render method in DX for every object and then render. Pretty smart. And should be much faster then just rendering and changing the awsom slow render method for every object...

---

Templates concern optimations over abstraction layers, you would never get if you did it the OOP way, so you could of course do this regularly with procedural code, but templates just abstracts theoretical reusability from technical reusability (function calls, unneceesary indirection, DMA etc... that are all result of typology)

So if they have standardised the template structure...does that mean that the syntax is changed from earlier releases of VC++

the syntax is the same, but it compiles the damned templates too.. i've had way too many headaches from trying to make it compile them ;) (and ask Alex stepanov that made the STL, he got gray hair from trying to make the compilers compile STL :D) big reason why I hate C++

Quote:

---

Originally posted by kedaman
Templates concern optimations over abstraction layers, you would never get if you did it the OOP way, so you could of course do this regularly with procedural code, but templates just abstracts theoretical reusability from technical reusability (function calls, unneceesary indirection, DMA etc... that are all result of typology)

---

Didn't quite understand what you where talking about now...but isn't templating just copy paste done by the compiler....BTW I also saw now that he used function call back to actually render the object..never heard about that before...D:

in fact you still encounter problems trying to compile it sometimes, and if you look at the errors MSVC++.NET 2003 produces (of course that goes with all the earlier compilers too), you're going to have headaches for sure

Quote:

---

Originally posted by NoteMe
Didn't quite understand what you where talking about now...but isn't templating just copy paste done by the compiler....BTW I also saw now that he used function call back to actually render the object..never heard about that before...D:

---

hehe.. if it only were that easy, C++ does allow much more complicated stuff with the templates, I don't blame micrsoft its the langauge's fault

Quote:

---

Originally posted by kedaman
the syntax is the same, but it compiles the damned templates too.. i've had way too many headaches from trying to make it compile them ;) (and ask Alex stepanov that made the STL, he got gray hair from trying to make the compilers compile STL :D) big reason why I hate C++

---

AHha...I think I got the idea....so you could be more sloppy with the code earlier...hence this update on this guys code from a book...??

http://mightystudios.com/modules.php...nd+DirectX+9#2

theres something called type lists, which are lists of types you can use as if the compiler was list operating programming language, but man it would kill any compiler..

I haven't read this book, but if you really want to get your brain turned into jelly you can read it:
http://www.bookpool.com/.x/4a37eht3gr/sm/0201704315

Quote:

---

Originally posted by kedaman
hehe.. if it only were that easy, C++ does allow much more complicated stuff with the templates, I don't blame micrsoft its the langauge's fault

---

I am not going to start with you on that one again...:D....I like C++. But they never though us anything about Templates in our C++/QT class. So I just read in a book that the compiler did some copy pasting...and I belived it..:D

Quote:

---

Originally posted by kedaman
theres something called type lists, which are lists of types you can use as if the compiler was list operating programming language, but man it would kill any compiler..

I haven't read this book, but if you really want to get your brain turned into jelly you can read it:
http://www.bookpool.com/.x/4a37eht3gr/sm/0201704315

---

What is "generic components"...

BTW when you press build in VC++, does it comiple all the cpp files or does it just link them?...havn't used VC++ much...they made us use GCC at school...:D

Quote:

---

Originally posted by NoteMe
AHha...I think I got the idea....so you could be more sloppy with the code earlier...hence this update on this guys code from a book...??

http://mightystudios.com/modules.php...nd+DirectX+9#2

---

yeah I think so, but mostly what was annoying that things that should compile didn't. So there were either some workaraounds or you had to bang your head in the wall. I invented one for partial specialisation for VC++6 which should be posted in the C++ forum here

Quote:

---

Originally posted by NoteMe
I am not going to start with you on that one again...:D....I like C++. But they never though us anything about Templates in our C++/QT class. So I just read in a book that the compiler did some copy pasting...and I belived it..:D

---

the most simplest compilers would do that, and those are far from standard compliant ;)

Quote:

---

Originally posted by kedaman
yeah I think so, but mostly what was annoying that things that should compile didn't. So there were either some workaraounds or you had to bang your head in the wall. I invented one for partial specialisation for VC++6 which should be posted in the C++ forum here

---

partial specialisation?? and now are you talking about...?

BTW Was that the project you never finished?

Quote:

---

Originally posted by kedaman
the most simplest compilers would do that, and those are far from standard compliant ;)

---

Maybe you should make a compiler...:D...then you can have everything as you want..:D...BTW can I optimize the sqare root..:D

Quote:

---

Originally posted by NoteMe
What is "generic components"...

BTW when you press build in VC++, does it comiple all the cpp files or does it just link them?...havn't used VC++ much...they made us use GCC at school...:D

---

well.. i think it should compile all the files that need to be compiled, those that you haven't changed are just linked the old obj files to the exe

generic components are fun, sort of polymorphic types, that you can use without making an abstraction layer like polymorphism in OOP to bridge different types, but this of course is only something you can do at compile time.

Quote:

---

Originally posted by kedaman
well.. i think it should compile all the files that need to be compiled, those that you haven't changed are just linked the old obj files to the exe

generic components are fun, sort of polymorphic types, that you can use without making an abstraction layer like polymorphism in OOP to bridge different types, but this of course is only something you can do at compile time.

---

Sounds like nice things to know,...but gets seldom implemented. But as long as it is done at compile time, it's probably fast enough. I hate things that are done at runtime. Typecasting and stuff are not for me..:D

Quote:

---

Originally posted by NoteMe
partial specialisation?? and now are you talking about...?

BTW Was that the project you never finished?

---

http://www.vbforums.com/showthread.p...specialisation

partial specialisation allows you to use specify only some of the typenames or constants in an implementation of a template, look at the link, you see how I use it to calculate powers with both exponent and base specified, but its a workaround for a much easier way if partial specialisation worked in MSVC++6.

The project was codenamed bork templates library, I think it worked but its a pain to use.

Quote:

---

Originally posted by NoteMe
Maybe you should make a compiler...:D...then you can have everything as you want..:D...BTW can I optimize the sqare root..:D

---

yeah sure you could, but it would kill the compiler ;)

and no i'm not going to make a compiler, at least not for C++ ;)

Quote:

---

Originally posted by NoteMe
Sounds like nice things to know,...but gets seldom implemented. But as long as it is done at compile time, it's probably fast enough. I hate things that are done at runtime. Typecasting and stuff are not for me..:D

---

hehe.. maybe you should learn more about using templates then ;)

Quote:

---

Originally posted by kedaman
http://www.vbforums.com/showthread.p...specialisation

partial specialisation allows you to use specify only some of the typenames or constants in an implementation of a template, look at the link, you see how I use it to calculate powers with both exponent and base specified, but its a workaround for a much easier way if partial specialisation worked in MSVC++6.

The project was codenamed bork templates library, I think it worked but its a pain to use.

---

ANything you touch is a pain to use...;)...looked pretty advanced for a rooky C++ guy like me

Quote:

---

Originally posted by kedaman
yeah sure you could, but it would kill the compiler ;)

and no i'm not going to make a compiler, at least not for C++ ;)

---

Then we have to waith untill your language is finished...give me a call if oyu ever want some tutorials in that language...;)...I can make it happen...;)

Quote:

---

Originally posted by NoteMe
ANything you touch is a pain to use...;)...looked pretty advanced for a rooky C++ guy like me

---

hehe.. that was before the time i started to really hate the things i touched ;)

Quote:

---

Originally posted by kedaman
hehe.. maybe you should learn more about using templates then ;)

---

At some occasions I get my DataStructures in C++ book down from my shelf, and there they use it all the time. But that was the book that told me that templates was just copy/paste, so now I am not so sure if I want to read it anyway...:D

Quote:

---

Originally posted by NoteMe
Then we have to waith untill your language is finished...give me a call if oyu ever want some tutorials in that language...;)...I can make it happen...;)

---

yeah maybe, I can finish it some point, but god knows who is going to implement it ;)

Quote:

---

Originally posted by kedaman
hehe.. that was before the time i started to really hate the things i touched ;)

---

Don't touch me....;)


BTW in that same page as the code I posted a link to he sais this:

Quote:

---

This is not a stand-alone download, CD-ROM included with the book must be installed prior to using this update. Binary files are not included. Once this file is unzipped over the original code, recompile all binaries.

---

What does he mean by binarys....he can't mean the cpp files, does he?

Quote:

---

Originally posted by NoteMe
At some occasions I get my DataStructures in C++ book down from my shelf, and there they use it all the time. But that was the book that told me that templates was just copy/paste, so now I am not so sure if I want to read it anyway...:D

---

hehe.. there are loads of applications of templates.. if you just look around on the net, one thing though, you're probably getting information overload.. so if you don't want that you could always ask me ;)

Quote:

---

Originally posted by kedaman
yeah maybe, I can finish it some point, but god knows who is going to implement it ;)

---

I don't understand this about making a langauge....if you make a language, isn't that just theory, and then you have to make a conpiler to make it run on a platform? Isn't that the implementation...are you just doing the theory part?