Ok, so I understand what a quadtree is, and what it’s used for, but here’s what I don’t know how to do.
If I draw two splitting planes in my scene to create a new node and there is an object that intersects a plane, (so that it would exist in two nodes) what do I do with it? I was thinking that I should just stick it in a linked list connected to the quadtree (so that it is a member of the larger node rather than a subdivision) but I realized that if I have terrain, like one huge height map, then none of that would be put into a tree.
If I try to break the object up, how would that be done? Say that I’m drawing a box with GL_QUADS or something… how do I store the individual planes in different children?
And what if an object is added to the scene? What’s the best way to sort it into an already-existing tree?
You have a couple of options for objects that span quad cells.
You can add the object to the leaf-most quad-cell that fully contains the object, in which case it may not be an actual leaf node (and all nodes can potentially contain objects as well as sub-nodes).
You can split the object along the dividing lines and then put each piece in a sub cell. Keep splitting if you choose to create more sub cells.
put the object in more than one leaf node – generally equivalent to #1 (not exactly, since the object may be in only 2/4 or 3/4, 2/16, etc… sub-nodes). But adds overhead in list processing and frame-reference counting.
For terrain, #2 is the only useful option and it makes sense since you want to cull out invisible portions anyway. Split once at load time, or pre-process the terrain into quad-tiles (also useful for LOD). The level of recursion is generally a function of the terrain density in a given area, so the amount of splitting is fairly predictable and consistent.
For moving objects, #1 make the most sense as you probably don’t want to split objects repeatedly or on the fly. I’d only use #3 in cases of large, irregular, hard-to-split objects that otherwise force themselves towards the top of the tree.