The scene graph you want to use will be based on your type of engine.
Is your game engine mainly doing indoor scenes?
If yes, then you know your draw distances will be very manageable and thus you can cram a ton of objects into one room and get as detailed as the video card allows.
Good scene graphs for indoor environments:
1. BSP trees
2. Portal culling systems
3. A combination of 1 and 2.
We all know what BSP's are so I will talk about portal culling. Portals are extremely powerful and extremely good at clipping and culling geometry.
It works like this. Find a room in your house and go stand in it. Now the only way you will see any other part of the house is if the door in your room is open and leads to another portion of the house. That door is your portal. So if the portal (a simple quad) for the door is inside the frustum then you must draw the adjoining room. The key is then you compute a new frustum based on the door portal and cull everything in the next room according to that frustum. Now if the next room has a door or window that leads into another area then you check to see if it's in the frustum of the door since this is your new frustum. If it is, then you render the geometry for that room and clip and cull according to that new portal.
As you can see this will eliminate a lot of triangles extremely fast.
To build this system you need a couple of important items.
1. Every portal has 2 sides. This means you must place 2 quads or polygons representing the portal back to back in the doorway.
2. Don't draw the actual portal geometry, it's only used for culling and clipping.
3. In order to clip to the portal, a simple frustum cull would suffice which leads to another type of scene graph.
The type of scene graph you use in the room is up to you but if the geometry is static, I would say either a BSP tree or quadtree would suffice. An octree would be best but only if it sped rendering up. Checking more nodes may actuall hamper performance rather than help it.
The second thing you must learn is how to extract the planes from small portals to create the frustum. It's easy to extract them for the main viewing frustum but it does become a bit more to extract them from another piece of geometry. There are several tuts on the web and several books on amazon.com that discuss this type of system.
The only thing I can come up with as far as updating is a range-based system. Using anything else may result in objects not updating correctly due to the culling/clipping process. We still want the bad guy in the hallway to blow the crapola out of our buds in the hallway, if we are in the room adjacent to the hallway. If we use the portal scene graph system, they will only update when they are visible which is great for FPS, but not good for the feel of the game. Update using a bounding sphere. If an object is within range of the sphere, update the beast. You will have to account for objects that may move in and out of the sphere. You would still want to update these guys. You don't update when the object is and will be completely out of the sphere.
I think you may find that you can update the entire level in memory and not run into problems. Updating is extremely easy and extremely fast, especially if your rendering is optimized to the max. You could forego big time physics calcs for objects that are out of the sphere and only use the physics stuff on objects that are in proximity of the player.
For updating you could use a quad tree but then you must check each object to see if it has left a node and is entering another one.
There are tons of ways to do this, and you may even come up with another way in your pursuits. No one really cares how you do it, just as long as it works.
Outdoor scenes
Outdoor scenes are actually my specialty and area of interest. There are several good papers on www.vterrain.org about how to go about this.
The main scene graph for all outdoor scenes is the quad-tree. A quad tree is very fast and very east to implement.
My structure is this:
Code:
struct TerrainPatchInfo
{
int iNumVertsPerRow;
int iNumVertsPerCol;
int iNumCellsPerRow;
int iNumCellsPerCol;
int iNumVerts;
int iNumTris;
int iNumTrisPerRow;
int iNumTrisPerCol;
int iMapWidth;
int iMapDepth;
int iResType;
int iTreeType;
};
class CTerrainNode
{
CTerrainNode *m_pUL;
CTerrainNode *m_pUR;
CTerrainNode *m_pLL;
CTerrainNode *m_pLR;
TerrainPatchInfo m_PatchInfo;
....
};
class CTerrain
{
CTerrainNode *m_pRoot;
....
};
The code to create it looks basically like this. I have removed the terrain patch resolution code because it's complex and hard to explain here. I've also removed the u,v texture calculation per vertex for the same reason.
Code:
void CTerrain::CreateVertices(CTerrainNode *pNode,int x,int z,int x2,int z2,int iDesiredSize)
{
if ((x2-x)<=iDesiredSize)
{
//Compute how many vertices
...
//Compute cellsize for this patch
...
//Create vertices for x,z,x2,z2
...
//Create indices for vertices
...
pNode->iTreeType=QUAD_LEAF;
return;
}
//Compute midx and midz for split
pNode->iTreeType=QUAD_NODE;
int midx=(x2+x)>>1;
int midz=(z2+z)>>1;
midz+=z;
midx+=x;
//Create upper left child
pNode->m_pUL=new CTerrainNode;
CreateVertices(pNode->m_pUL,x,z,midx,midz);
//Create upper right child
pNode->m_pUR=new CTerrainNode;
CreateVertices(pNode->m_pUR,midx,z,x2,midz);
//Create lower left child
pNode->m_pLL=new CTerrainNode;
CreateVertices(pNode->m_pLL,x,midz,midx,z2);
//Create lower right child
pNode->m_pLR=new CTerrainNode;
CreateVertices(pNode->m_pLR,midx,midz,x2,z2);
}
My actual code creates 3 resolutions of the terrain. The resolution used is chosen at run-time based on distance from the camera. I line up differing resolutions by using a border for each new resolution that consists of one triangle. This way low to med lines up and med to high lines up. Low to High will not line up, but this also will never occur.
This is just an example of how complex these things can get.
..
.
