We use something similar to quad-trees. Here is a merged excerp from some of
my other e-mails.
We have a viewable range of, well anything up to 12800 meters with
pretty good results. I tried a LOT of different ways to go, including
adaptive quad-trees, but finally settled for static quad-trees for the
terrain. We import a GIS heightmap and generate geometry cells and
procedural texture cells for 200m, 400m, 800m, 1600m, etc up to 6400 meter
cells.
Each level is controlled by a LOD descriptor that defines the following:
1. The sparseness of the heightmap scan
2. the amount of polygon crunching to do in percentage of total polygons
3. The size of the texture
4. The density of the detail texture
5. The name of the detail texture
6. Whether or not to share the parent's texture
7. The number of children in one dimension (2 for right now for all levels)
We run a program that generates all the geometries and textures into files
(soon to a jar) and we are coming in at 35mb per 135 sq km, which is pretty
decent, although we have plans to reduce that further. We then define an
array of spherical bounds which define the
minimum LOD level in relation to the person. So everytime they move 40
meters or so we recusively drop down through the tree starting at the top
and check to see if the cell violates the layered bounds. When it does, it
builds n children and drops down inside of them, whereupon it continues. So
we can say we want the highest lod detail within a 400 meter radius, and we
never want the 3200 or up LOD version within 800 meters. If we don't do
this we can get too close to a low res version approaching major colinear
cell boundries (like in the very center of a 12k cell). During this pass a
list of nodes is built. This list is then passed to the renderer which
determines which cells have been removed from the last pass and which need
to be added. It then modifies the scenegraph accordingly and then prunes the
tree to remove children that arn't needed anymore.
The textures *can* be built on the fly, but there is a noticible
sluggishness. This will only grow worse as we refine the shaders. So we
pre-generate all of them for every cell at every level, except where the
levels share textures. So you can tell the engine that 800 meter cells
should use their portion of the 1600 meter cells. But by and large the vast
majority of the textures are the 200x200 meter cells stored in 128x128
textures, then blended with a detail texture to hide stretching.
The meshes are also pre-built, although they can be more easily built on
the fly without performance hits. Each mesh file has a corresponding
matching texture file. Each mesh file is stored with a pre-calculated LOD
reduction map, so we can dynamically control the quality of the landscape
based on user's machine. Each mesh file is quite small. There is a dynamic
(in memory) node tree which represents the currently active nodes. Its
recursive, so say there is a 12800 m x 12800 m node, with 4 children
representing the four 6400 m x 6400 m children, representing 4 quandrants of
the parent. When I check to see if we need to update the landscape, I drop
down through the parent and apply certain policies to see if we need to
recurse into the children, or if it is safe to render this cell level. So
the quad-tree is self maintaining. It builds a render list of nodes which
*should* exist to fulfill the policies. This is passed to a controller that
compares it to the list of existing nodes. It then builds a transaction
representing a series of attaches and detaches of the scene graph, and
requests the nodes to return their Shape3D's, the old branchgroups are
detached and get garbage collected, and the unused children are then culled
from the tree. So for for over a 120,000 square meter area I usually only
have from 20 to 45 nodes active at one time.
Feedback from the team is that there is no sense of paging or slowdowns or
hiccups at all. The LOD changes are noticible, but not really bad at all.
There is some popping, but not generally in outline of the mountains. The
textures appear to be seemless. The farther cells are being built with
fewer and fewer polygons.
----- Original Message -----
From: Corysia Taware <[EMAIL PROTECTED]>
To: <[EMAIL PROTECTED]>
Sent: Thursday, June 07, 2001 6:16 PM
Subject: [JAVA3D] Quadtrees and Scene Graphs
Do quadtrees work well for managing terrain data with scene graphs? Almost
every article I've read on them demonstrates the theory in immediate mode,
not in a retained mode architechture. It seems to me that it would be
necessary to continually tear down and rebuild those portions of the tree
that deal with the landscape.
_________________________________________________________
Do You Yahoo!?
Get your free @yahoo.com address at http://mail.yahoo.com
===========================================================================
To unsubscribe, send email to [EMAIL PROTECTED] and include in the body
of the message "signoff JAVA3D-INTEREST". For general help, send email to
[EMAIL PROTECTED] and include in the body of the message "help".
===========================================================================
To unsubscribe, send email to [EMAIL PROTECTED] and include in the body
of the message "signoff JAVA3D-INTEREST". For general help, send email to
[EMAIL PROTECTED] and include in the body of the message "help".
