Scenegraph Stuff
Entry posted by Josh ·
1,757 views
Discussing scene graphs in a game development or programming forum can be difficult, because I feel many people are very short-sighted about all the exceptions and complications that can arise in a flexible environment. In fact, there are many situations that will make rendering with a scene graph much slower than without. Many programmers have a tendency to ignore anticipated problems and assume it will work itself out somehow. It's also very hard to predict how bottlenecks will form and what "typical" behavior in a game will turn out to be. Thus, in the past I have never gotten much out of all the discussions and theories that exist on this subject.
The primary complication arises from the fact that some objects are typically static, while others may move around. Static objects are infrequently added to or removed from the scene graph, so quad trees or octrees work great. Dynamic objects do not work well with these approaches because of the amount of data that has to be recalculated.
Another problem appears when an object crosses over the bounds of two "cells" or areas. If an object lies on an edge where it overlaps two areas, what should you do? Recalculating the bounding box of the area is one solution. Consider a quad tree with three branches. If a car in one leaf moves, the branches two levels up have to have their AABB recalculated. If the leaf contains a large number of objects, it may require iterating through all of them to recalculate the AABB. So this solution isn't very good for a scene with a lot of moving objects. This approach, incidentally, is the one used internally by the vegetation system.
Another approach is to list the object in both areas. However, if you have a large building that may occupy dozens of separate areas at once, this approach can create a lot of unnecessary overhead.
Before I discuss my solution, let's consider the fundamental differences between static and dynamic objects in a scene. Static objects are usually used for trees, grass, plants, buildings, fences, and other repetitive objects. They tend to be very high in density and quantity. Dynamics objects have an overall tendency to be more spread out and fewer. An area might be littered with a lot of physically interactive debris, but that's still less than the tens or even hundreds of thousands of trees that might exist. This means the two kinds of objects have fundamental differences in distribution that makes different scenegraph systems more optimal for either.
For static objects, the quad tree approach with adjusting bounding boxes is fantastic. For dynamic objects, it makes more sense in practice to have a nonrecursive grid with adjusting bounding boxes. It's pointless to have recursive levels of bounding box adjustment and culling when the quantity of dynamic objects is nowhere near that of the vegetation system, which benefits from a heavy optimization system. The renderer can just grab a square of sectors within the camera range, in the same way the terrain renderer does, as this pseudo code shows:
for x=camera.position.x - camera.range to camera.position.x + camera.range {
for z=camera.position.z - camera.range to camera.position.z + camera.range {
if !sector:Culled(camera) {
sector[x,z]:Draw(camera)
}
}
}
This also is optimal for AI and other updating. The S.T.A.L.K.E.R. engine has a setting for AI range. This is how they are able to have so many characters in the world, and only have to worry about updating the ones in the near vicinity. I might add an "update range" setting so that only models within a certain distance have their Update callbacks and script functions run. The code to do this would look something like this:
for x=camera.position.x - camera.range to camera.position.x + camera.range {
for z=camera.position.z - camera.range to camera.position.z + camera.range {
sector[x,z]:Update()
}
}
These are some small improvements I plan to make. The effects won't be immediately apparent to most people, but they will ensure your project will stay fast as your work becomes more advanced.
4 Comments
Recommended Comments