Hello.
I have a question considering aabb’s in quad trees, which should actually
be in multiple quads.
What is best practise here? Should i check, if an object should be in 2 (or all 4) sub-quads and
put it in them, same while removing? Or are there other ways to do that?
Thank you!
Hi - sorry I don’t know much about quad trees, but I like talking about data structures so I’ll ask the question anyway :)… Under what circumstances would a value fall in more than one subdivision?
Quad-trees are hard in a language like java.
There isn’t really a best practices kind of thing for this. It depends on what you need. Generally you’d either check neighboring cells or have the objects that fit inside two or more cells pushed up to a top level cell.
Skimmed through the first links on google:
http://www.kyleschouviller.com/wsuxna/quadtree-source-included/
This is a complete tutorial that helped me implement a QuadTree.
Hope this helps.
Okay… in this tutorial there are sayint to put it into the parent node, too…
Thank you all 
painful i did’nt strike on this idea myself ^^
Java isn’t well suited to the problem without a lot of pita. No structures or arrays of.
Quadtrees in general are only well suited if you have (sub)space which is large compared to things to be contained.
For reference I’ve implemented probably over a dozen different flavors of quad-trees for various statistical properties. I understand java, compilers and how CPUs work. Writing a quad-tree worth using in java is hard. The vast majority of people will end up with a something much more complicated and less efficient than sweep-and-prune on a uniform grid.
Moreover if the distribution of object is closer to uniform than Gaussian, then the grid is a better idea anyway.
Understand sweep-and-prune on a uniform grid. Search the forum I’ve done a verbal write-up. Quad-tree’s are the same. The key notion is to be edge based instead of child based.
So, what Roquen was hinting at is that Java might not be a very good language in which to implement a quadtree structure. Of course if you have a box of nails and the only tool you have handy is a hammer, well, there you are. But why did he say this?
Two aspects of most things in comp sci are the physical structure of things in memory and the algorithms to access them efficiently. Sometimes a thing works really well because the precise way it is laid out in memory makes it extremely efficient to work with, and quadtrees is one of these things. In C, quadtrees are densely packed structures using pointers to bits of itself, all stored in a contiguous block of memory. It’s as efficient as it can possibly be.
In Java, the best you can do is a great big sprawling heap of instances scattered all over memory. Each instance itself has a whole load of extra guff associated with it somewhere else in memory, too. So though on the surface of it, it looks like you’ve got a neat looking data structure and perfectly simple algorithms, like a swan paddling on a lake it’s all serene on top but there’s a lot of furious thrashing going on underneath where you can’t see it. Then you wonder why it’s slower and takes up vast amounts of RAM.
Cas
You “can” get a good memory layout in java…just it’s a ton of work. Using something like Riven’s library would make the attempt partially sane. Like I said…this is hard in java. Actually it’s pretty hard in C as well, but at least you’re given the tools you need to do the job. And making the attempt is only ever worthwhile if its a good match to your data and the set of queries you’re going to perform.
[quote]In C, quadtrees are densely packed structures using pointers to bits of itself, all stored in a contiguous block of memory. It’s as efficient as it can possibly be.
[/quote]
are we talking of C or C++, too?
Im learning C++ in the moment… so i cannot argumentate on this side.
But if i understood you correctly, you mean in c (++?) quadtrees would be
more efficient because of pinters, and a better memory information structure?
Then, i would say, every program would be “better” in c, because why this point
should only be a plus in quadtrees? Data Structures in General should be better in C then,
if implemented correctly…
But why, i don’t understand… if the data is spread over the ram or not, at the and
there are just pointers pointing to the correct position, or not?..
I think the point was that in C (and in C++) you have more control how your data will be stored in the heap.
But this doesn’t mean that each and every C (or C++) program is better than Java, frankly, because in many cases this sort of control is not needed.
To optimize for performance, the key is to have data stored in the order that is the most frequent reading (or writing), particularly that the next accessed data is directly stored after the currently accessed data. Then it is cache friendly. Scattered data/scattered accesses are cache unfriendly, the more the smaller the data chunks and the more they are scattered.
In Java the only way to be sure of memory layout is to use Arrays as emulation of a heap, and provide a struct-like API into the (hidden) array data. This way you can have an OO-like API on top of an access-optimized structure, but it is not nice to code.
Spasi did a nice optimisation and benchmark of a Java quadtree using a structs library in LWJGL.
I pushed it back to the sane realm. :point: