PDA

View Full Version : Quadtree and Frustum in OpenGL



Sarah22
05-13-2009, 06:56 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?

Dark Photon
05-13-2009, 08:56 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?

I can only guess what your assignment is. My guess is you need to use view-frustum culling to draw only entities in the scene which are potentially visible (as opposed to the entire DB). So google that for details.

As to what you cull, obviously you don't want to cull at the finest resolution of the DB (O(n)). Typically you want to do a hierarchy of culls on courser groupings of the DB. How do you get those? Google for spatial subdivision and bounding volume hierarchies. Those are the two main classes of methods.

Within those methods you will find quadtrees (a spatial subdivision technique). As to what a scene graph is, conventionally it is a bounding volume hierarchy, but it can be anything you want.

Sarah22
05-13-2009, 06:00 PM
I found a topic about what you have said in a book, Focus on 3D Terrain Programming. But my problem is, do I really need to render it like the steps below?

1) Get data (1 or 0)
2) if true
3) is this the smallest node? do 3 - 8
3) upper right vertex
4) upper mid, skip if the adjacent node is of a lower detail level
5) upper left
6) left mid, skip if the adjacent node is of a lower detail level
7) lower left vertex.
8) return;
9) else and a bunch more of recursive codes.

It has 500 lines just for the rendering function! My whole MD2 Model loader.cpp has the same number of lines. I want to make use vertex buffer object (glDrawElements) but I think this will take some time.

Dark Photon
05-13-2009, 06:56 PM
I found a topic about what you have said in a book, Focus on 3D Terrain Programming. But my problem is, do I really need to render it like the steps below?
Probably should ask the instructor. (Also BTW, this thread probably should have been posted in the beginners forum.) The steps you post are apparently for a very specific regular grid terrain rendering algorithm supporting LOD, which they call quadtree. Haven't read that book, but bunches of such algorithms are possible.

Not that I see it in those steps you posted, but just from the name my guess the terrain tessellation alg (i.e. how they bust up the terrain into triangles) they're describing mimics quadtree subdivision. That is, you take a big grid of heightposts, bust it up 2X2. The vertices touched by those cuts form your lowest LOD. Bust each of those 4 squares up 2x2 and that forms your next lowest LOD. etc. on down to the resolution of the grid.

Please don't quote me though; read the book. And if they don't explain it well, toss it and get a better book. :)

Since it sounds like you're just starting out with graphics programming, forget the terrain for starters. Start by drawing a single triangle using immediate mode (glBegin/glVertex/glEnd) with no lighting (glDisable( GL_LIGHTING )). Once you get it rendering on screen, draw another triangle. using the same technique right beside it sharing an edge. Then switch to drawing these same two triangles using one glDrawElements call for both.

Once you're to that point, then plug in the terrain alg. All it's probably going to give you is a new set of triangles to render, besides the two you have been.