Quadtree and Frustum in OpenGL

sarah22 · 05-13-2009, 06:17 AM

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?

MK27 · 05-13-2009, 07:54 AM

Quote:

Originally Posted by sarah22

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

**Bubba** · 05-13-2009, 10:51 PM

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.

05-13-2009, 06:17 AM	#1
sarah22 Registered User Join Date: May 2009 Posts: 28	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?
sarah22 is offline

05-13-2009, 10:51 PM	#3
Bubba Super Moderator Join Date: Aug 2001 Posts: 7,819	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. __________________ If you aim at everything you will hit something but you won't know what it is. Last edited by Bubba; 05-13-2009 at 10:54 PM.
Bubba is offline

Thread Tools
Show Printable Version Email this Page
Display Modes
Linear Mode Switch to Hybrid Mode Switch to Threaded Mode