Part of the Khronos Group
OpenGL.org

The Industry's Foundation for High Performance Graphics

from games to virtual reality, mobile phones to supercomputers

Results 1 to 4 of 4

Thread: Quadtrees... conceptual help

  1. #1
    Junior Member Newbie
    Join Date
    Jan 2004
    Posts
    6

    Quadtrees... conceptual help

    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!

  2. #2
    Junior Member Regular Contributor
    Join Date
    May 2003
    Location
    New York
    Posts
    194

    Re: Quadtrees... conceptual help

    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

  3. #3
    Junior Member Regular Contributor
    Join Date
    Mar 2002
    Posts
    103

    Re: Quadtrees... conceptual help

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

  4. #4
    Junior Member Newbie
    Join Date
    Jan 2004
    Posts
    6

    Re: Quadtrees... conceptual help

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

Posting Permissions

  • You may not post new threads
  • You may not post replies
  • You may not post attachments
  • You may not edit your posts
  •