Research : Spatial : Scene Graphs

Scene graphs have an interesting history. Modern engines seem to recognize that trying to create a single scene graph that can handle all needed organization is a pipe-dream.

Resources

  • Scene Graphs: Past, Present, and Future An excellent overview of the technical challenges with scene graphs. In particular, the article notes that creating a single scene graph is insufficient to handle the number of possible uses a developer might need. Scene graphs are typically used to find a set of elements in a scene based upon similarity. Unfortunately, many of the queries against that scene graph require sorting or searching on data that’s orthogonal (e.g. spatial similarity vs. common geometry or textures). To get around this, the suggested approach is to start maintaining separate graph structures specific to each type of query you’ll be making against the scene. This will likely negatively affect cache hit rates due to the fact that it becomes nigh-impossible to group like objects together in memory (for the same reason we’re maintaining separate graph structures in the first place.)

    I read through an interesting presentation about how to address the cache locality issues via the GDC archives not too long ago, but I can’t seem to find it now. I’ll post it later if I track it down.

    For another (supporting) perspective on this, take a gander at: Tom Forsyth’s Scene Graphs: Just Say No.