Game Development Conversations
On Transcending the Scene Graph
I’ve been having a number of refactoring conversations with my friend and colleague, Rob. The scene graph had become a mess, and integrating with third party physics, 3D sound, and other systems was beginning to expose redundancies in our code.
After a lot of discussion and some influence from the recent surge of articles on Data-Oriented Design, we found some interesting ways to re-think the scene. One of last week’s big examples had to due with transforms. As a standard, many objects are thought of as having world and local transform data. This way the spacial hierarchy suggested by your node relationships is respected when it’s time to draw. This just makes sense….
But think about the data for second. How are the local and world transforms used? They are used specifically to offset a child node’s orientation from its parent. The next question that entered my mind was “How many objects with hierarchical relationship are going to exist in our game?” The answer here will obviously vary game-to-game. But for us, very few nodes have a parent. For this majority case, the world and local transforms are the same, effectively wasting memory and processing for all such objects.
Solutions, as in any production environment, are potentially limited by time and the how-much-stuff-does-this-break factor. Creating a different object for each case wasn’t viable. We needed to preserve some aspects of our current design, and fragmenting our loading process was not an option. The solution ended up being that our World transform became a pointer. Whenever the node is parentless, it points to the Local Transform. Whenever a parent exists, the node gets a World Transform allocated for it, such that it can be maintained separately. Parents do not appear and abandon their children frequently in our game, so this will likely be a one-time setup operation for our nodes. Also, this gives us an opportunity to skip all transform update/synchronization code that applies only to parented nodes. The optimization-minded among you might say “You are clearly introducing branches here, friend.” And you would be right. However, given the predictability of these branches (based on the consistency of our game data), and type of processing being skipped, this has resulted in an increase in performance and reliability within our engine, and a substantial reduction in memory consumption, which is crucial for our target system.
Also, not described here are the ways our Transform model got consolidated, and the amount of duplicate code reduced that way. But all in all, this turned out to be a positive move for the codebase, and I’m pleased with it. But the story doesn’t end here.
This is basically where refactoring stopped for the current engine, due to schedule concerns. But our minds continue to imagine other improvements. Rob continued to ponder the consequences of a data-focused decision making. Moving beyond the scene graph as a concept could offer ways to improve both performance and parallel processing opportunities. Stripping down the idea of a “node” to its core property… the transform… one can imagine a linear array of these objects, which still maintain parent relationships where needed, by ID with a pool of available handles for new nodes. Organizing collections of data into linear arrays is fast becoming one of the simplest ways to design objects that perform well. And, against some of my previous assumptions, you can put just about any collection of data into a consecutive, linear array if you want to- and design accordingly.
A scene graph is essentially a fancy linked-list. Jumping around by pointer (to non-consecutive randomly allocated memory) is one of the red-flags when aiming for cache-friendliness. But there are lots of well-practiced methods that abandon this idea (or don’t consider it?). Before this engine really took shape, I was referencing a lot of David H. Eberly’s work, such as 3D Game Engine Design. One of the trickier aspects of modern game engines that he addresses is maintaining a global render state, such that you can tell your graphics API how each object is to be rendered, regardless of its place in spacial hierarchy. I derived a solution from his suggestions and examples which essentially maintains a stack for each type of state that can be altered through the engine, pushing and popping states objects for each node. I only mentioned this, because when you try to tie this into the scene graph in an Object-Oriented fashion, you can get a rather stark tradeoff for the functionality. One the one hand, there is the elegance of “attaching” a render state object to a node, and having the back end magically maintain this, updating the API for you, and so on. But if you’re concerned about limiting the memory jumps and being cache friendly, this only exacerbates an already memory-tangled system.
While I have no specific solution dreamt up for this, it’s an important discovery for me as a programmer to realize (again) that no tried-and-true method is beyond improvement. I look forward to seeing more data-oriented progress in technical articles on the internet, as well as whatever new paradigm rocks our world after that has had its day in the sun. From this standpoint, it’s easy to acknowledge that I’m not the best programmer out there. But it’s also encouraging to know that I’m my way to becoming the best programmer I can be.
Please comment! If you’ve run into any similar programming situations, if you have feedback on the current and future solutions that Rob and I have been dreaming up, or anything else. I’d love to hear what you think.
P.S. Some other recent-read articles are here.