Quad-Tree

I've been searching around for the logic behind QuadTrees, and trying to implement my own QuadTree algorithm.  What's the basic logic behind QuadTrees?

smoke trees errday

It's like any tree, except instead of k number of children at non-leaf nodes, there are 4 children. So you use the same algorithms for traversing trees in general. In graphics or physics simulations, where it is used to partition space into a tree structure for logarithmic searches and culling, each non-leaf node in a tree represents the axis-aligned bounding volume of it's 4 children, in a recursive manner. That's all there is to it.

ya, ya just take your space and cut it into four pieces, and store each quadrant under your current node. One method is to pick an object on your map that is near the middle, and represent the object as a node. Doing this, you can quickly find objects that are close to each other, which will help for efficient collision detection when there are many objects on your map. If every object is stuck inside of every other object it'll still be n squared checks, but hopefully that doesn't happen. It isn't that difficult to create, but keeping it valid as the objects move around, and keeping it balanced could be something. I want to learn more about this myself.

first binary trees now quad trees?

what the fuck? what about ternary trees?

Interestingly, quad trees can be implemented as binary trees, just as octrees can

>>3
I'm not familiar with the current existing algorithms.  I'm most confused at deciding what needs to be rendered without processing my data each time to determine what's inside of the rectangle.

>>7
you can try http://en.wikipedia.org/wiki/Sparse_voxel_octree

You have your choice of depth-first or breadth-first searching. This isn't new stuff, Dijkstra was doing this shit back in the 50s. At each node, check to see if the bounding volume of the node (and thus all of its children) intersects with the camera's view frustrum. If it does not, you do not need to traverse any further on that branch of the tree and you do not need to render any of the geometry located within the leaf nodes of that branch.

oh no - not this old chestnut again
some twat will start harping on any minute now about how you can render infinite graphical complexity with sparse voxel trees

That's easy. A Quadtree is like an Octree but with only 2 dimensions.

>>10
If you want infinite graphical complexity you have to generate the data procedurally, and voxels store the most data(they're basically 3D bitmaps) compared to polygons(geometry defined with filled vectors) which require much more than raw vectors(used in old games like Elite).
i.e. using voxels is the worst choice for complexity, meshes and polygons also require a fair bit of memory,
but procedurally generated objects can be as complex as design of an algorithm creating them, and they can be discarded and regenerated as often as desired(typically they're cached for reuse).

>>9
Doesn't that only work if you were searching from the origin of the octree?

If you're looking towards the origin from the outside alone one of the major axes, it would render 1/2 the entire tree until you got to the final leaf nodes, then it would discard all of it.

Rendering with voxels is always going to be worse than polies, for the simple fact that voxels must be converted to surfaces before attempting to collision detect, and polies don't.

I'm saging because you're a retarded trolling faggot, but fuck, at least try next time.

>>13
Doesn't that only work if you were searching from the origin of the octree?

No. And this is a quad tree we're talking about. For a 2D game, or a 3D game where the world is mostly flat on the XZ axes.

If you're looking towards the origin from the outside alone one of the major axes, it would render 1/2 the entire tree until you got to the final leaf nodes, then it would discard all of it.

No. The bounding volumes of the nodes are hierarchical. Everything behind you and outside of your field of vision would be culled, often without needing to traverse all of the way down to the leaf nodes. That's why a tree structure is used in the first place, it provides O(log n) time complexity for spatial lookups.

I'll assume the rest of your response was for >>12

The cool thing about octrees and quadtrees is if you keep the size of your leaf-nodes the exact same so that they form a uniform grid, you don't need to store the tree structure at all, you can generate array indices and bounding volumes into the leaf node grid on the fly as you traverse your tree hierarchically.

Quality->Voxels
Speed->Polygons
Speed&Quality->Meshes
Scaling->Vectors
Scaling&Quality->NURBS
Autism->Procedurally generating everything

>>16
You can generate Meshes/Voxels/Polygons/Vectors procedurally too.

this thread is [b][i][o]ENTERPRISE WIKIPEDIA QUALITY[/b][/i][/o]

>>16
Autism->Procedurally generating everything

http://www.youtube.com/watch?v=2NBG-sKFaB0&feature=related

AVTISMVS MAXIMVS

>5

You will love 2-3-4 trees.

>>19
Everything in this is procedurally generated:

http://www.youtube.com/watch?v=h7eREddMjt4

>>22
http://en.wikipedia.org/wiki/Vaporware

>>22
Really? Even the ships? That's quite a feat.

>>10
http://www.pcper.com/reviews/Editorial/John-Carmack-Interview-GPU-Race-Intel-Graphics-Ray-Tracing-Voxels-and-more/Transcr
John Carmack: Okay, for one thing, I think it’s important to separate the notion of infinite detail and Voxels. You can have Voxels [that are not infinitely detailed] because many of the Voxel engines that I’ve written have been at finite coarse levels of detail. The fact that you can instance detail in [Voxels]... in may ways it sounds awesomely cool: “infinite detail,” but if we look at all of the trends that we’ve been doing and Rage epitomizes in many ways, procedurally generated detail is usually not what you want. This has been an argument going back decades: “now is the year of procedurally generated textures and geometry.” We’ve heard that for a decade and it never has come true. What has won is being able to manage the real data that we want. Procedural-ism is really just a truly crappy form of data compression. You know, you have the data that you really want, and procedural-ism makes you something that might resemble what you really want, but it’s a form of extraordinarily lossy data compression that lets you produce something there.

>>25
Twat!

>>25

Video games will never realize their true potential until they allow you to throw julia sets at people.

>>27
set theory is pseudoscience.
julia was jewish.

>>25
Procedural-ism is really just a truly crappy form of data compression.
Carmack is as retarded as always. Procedural generation is good when you want to eleminate bias: for example, one could randomize chess pieces or randomly generate map for an online game. It has nothing to do with curve fitting math pseudoscience.

>>28
You will call anything you don't understand pseudoscience. You do realize that you could limit your sets to finite and computable objects right? Even if a fractal could be described by a non-halting (by definition infinite) process, you only need to compute a part of it for most practical uses.

>>30
Then there will be no "infinite detail". Your filthy marketing buzz fails you, jew.

>>27
I'd love to trap somebody within a julia set then search the set to find that person.

>>29
In the days when Sussman was a novice, Minsky once came to him as he sat hacking at the PDP-6.
"What are you doing?", asked Minsky.
"I am training a randomly wired neural net to play Tic-tac-toe", Sussman replied.
"Why is the net wired randomly?", asked Minsky.
"I do not want it to have any preconceptions of how to play", Sussman said.
Minsky then shut his eyes.
"Why do you close your eyes?" Sussman asked his teacher.
"So that the room will be empty."
At that moment, Sussman was enlightened.

>>31
Why is non-halting recursive patterns not infinite detail?

>>31
I haven't read this thread, so I don't know what this 'infinite detail' is, but I do think non-halting processes are fine, our universe may very well be one (and if not, by induction, an universe with a next state will always exist).
Given some fractal computing process, you can render it up to detail 'k' (some particular resolution). Given more time, you can render it up to k+1, and so on. I refuse to accept that the next step cannot exist when one models the process abstractly. (I also refuse to accept that there is such a time t which is the final state and no states follow after it. Of course, no conscious artifact (such as ourselves) will ever be able to say that a time t is final, or that t+1 doesn't exist, as our own illusion of continuity of consciousness requires us to assume t+1 always exist - and since I think living for this illusion is perfectly fine(no reason to live if you don't care about your own conscious state), I will always assume t+1 exists for any t and also the existence of a mathematical or computational multiverse, but that's a discussion for another day).

>>33
Because the Universe will eventually halt once all protons have decayed and entropy has reached maximum, and thus no more work can be performed. Thus, any computational process being simulated inside of the Universe will also be forcibly stopped.

>>32

Could you imagine the pain of getting cut by a knife with a serrated koche snowflake at the end? The knife would have finite area, and an edge with infinite length, yielding INFINITE PAIN

>>33

0xFFFFFFFF+1 = 0;

>>35
Why do you so fervently believe that this particular universe is unique and is the only computational process that can exist? It's a baseless assumption. Most people assuming the physical church turing thesis also assume a computational multiverse at minimum (see: http://arxiv.org/abs/quant-ph/0011122 for one view, although fairly incomplete. the one I personally subscribe to actually shows that quantum mechanics results very naturally from observing such a computational multiverse from the inside and getting away from it is very difficult).

>>34
an universe with a next state will always exist
Yes, that may be true, perhaps the Universe can restart/reset itself (Penrose's Conformal Cyclic Cosmology), or maybe the holographic membrane of the universe evaporates and is recycled by external/adjacent universes in some sort of Multiverse theory.

But here's the thing, it doesn't matter. All prior information is lost at the point when maximal entropy is achieved, including any macroscopic computational processes.

>>39 here, just want to clarify one thing. I shouldn't say information is lost, as that's not true (conservation of energy). Rather, what happens at maximum entropy is that all information is sufficiently randomized.