Quadtree and Frustum in OpenGL

This is a discussion on Quadtree and Frustum in OpenGL within the Game Programming forums, part of the General Programming Boards category; I can't find any good tutorial out there that teaches this topic. Is there any 3D guru that will teach ...

  1. #1
    Registered User
    Join Date
    May 2009
    Posts
    64

    Quadtree and Frustum in OpenGL

    I can't find any good tutorial out there that teaches this topic. Is there any 3D guru that will teach or give me a link on how to create a Quadtree and Frustum? I want to load a 512x512 heightmap then use quadtree and frustum on it. Does player's model will also be included on it to save rendering time?

    By the way, this is a bit different topic but what is scene graph in short and how can I implement it here?

  2. #2
    spurious conceit MK27's Avatar
    Join Date
    Jul 2008
    Location
    segmentation fault
    Posts
    8,300
    Quote Originally Posted by sarah22 View Post
    I can't find any good tutorial out there that teaches this topic. Is there any 3D guru that will teach or give me a link on how to create a Quadtree and Frustum?
    You could try
    OpenGL.org Discussion and Help Forums - Powered by UBB.threads™
    it is, of course, chock full of 3D gurus...
    C programming resources:
    GNU C Function and Macro Index -- glibc reference manual
    The C Book -- nice online learner guide
    Current ISO draft standard
    CCAN -- new CPAN like open source library repository
    3 (different) GNU debugger tutorials: #1 -- #2 -- #3
    cpwiki -- our wiki on sourceforge

  3. #3
    Super Moderator VirtualAce's Avatar
    Join Date
    Aug 2001
    Posts
    9,590
    First why do you need a quad-tree and second why do you need a scene graph and a quad tree in the same system?

    I could possibly see using a scene graph or possibly an octree for some lighting effects such as multiple point lights. Usually a quad tree is best suited for terrain rendering and not well suited for indoor rendering. For indoor rendering you will want to use BSP trees combined with portals to get good performance.

    Now on to your questions:

    I have created several types of quad-trees and my past threads are all over this forum so if you do a search you will find plenty of info. Quad-trees are essentially:

    Code:
    struct QuadNode
    {
       QuadNode *pNW;
       QuadNode *pNE;
       QuadNode *pSW;
       QuadNode *pSE;
    
       AABB bounds;
    };
    The AABB is the min and max points of the volume that the quad tree node comprises.

    1. If a node is completely in the frustum so are all of it's children and the frustum check need not be performed on any of them.
    2. If a node is partially in you need to continue the frustum check down to its children until 1 or 3 occurs.
    3. If a node is out so are all of it's children and the entire node and it's children can be rejected.

    There are many articles about how to create a frustum both for D3D and OpenGL. Just google for it and you should find info aplenty.

    In order to accomodate moving objects in your system you will have to have some neighbor information for each node. As an object passes a certain boundary of a node it now belongs to whichever node it is in. For half in and half out you can just select one or the other neighbor. The rendering still procedes as normal with each node being rendered (and all of it's objects) if it is in or partially in the frustum.
    Last edited by VirtualAce; 05-13-2009 at 10:54 PM.

Popular pages Recent additions subscribe to a feed

1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21