Quadtrees... conceptual help

[sirSolarius]

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?

Thanks!

[Cyranose]

You have a couple of options for objects that span quad cells.

1) 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).

2) 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.

3) 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.

Avi

[gumby]

There is also the loose-octree option: http://www.tulrich.com/geekstuff/partitioning.html

[sirSolarius]

Ok, that sounds reasonable. My last question is: how do I add a new object to a scene and sort it into an existing quadtree efficiently?

[This message has been edited by sirSolarius (edited 01-31-2004).]