Chris Oliver's Weblog

Instancing

To conserve memory and minimize processor cache misses and GPU state changes, we need reasonable ways of "instancing" scene graph elements, meaning reusing the same objects in cases where the same element conceptually appears multiple times in the same scene.

It's possible to implement a transform and bounding volume hierarchy which supports instancing, however the overhead is significant, both in terms of its impact on processing costs and memory-use, as well as on ease-of-use for many use cases. If you introduce instancing at this level, every node potentially has many parents (and further ancestors) - which implies a node also has as many world space transforms and world space bounding volumes as the product of all its ancestors.

To avoid these costs but still retain some of the benefits of instancing, one approach is to make the instancing purely visual. In this case, a Node which appears multiple times in the same scene still may have at most one actual parent, and thus only a single world transform and bounding volume. A special auxiliary node type is provided which itself is part of the transform hierarchy and bounding volume hierarchy of the scene, however any nodes it contains remain disconnected from that, i.e it is not their parent. When this auxiliary node is rendered, it cancels the world transform of the actual parent (if any) of its child nodes and substitutes its own in place of that. In addition, it arranges for its children to derive their render states from its own rather than those of their parents.

In our system, this auxiliary node is called a "Lens" and has the following partial definition:

public class Lens extends Node {

    public var view: Node;
   
     ...

}

Example - Bubblemark

It's not a very interesting example, but it is (hopefully) somewhat familiar. In "Bubblemark" the same vector "bubble" graphic appears N times, each with a different translation. It would be extraordinarily wasteful to actually create N duplicate Bubble objects (which are quite heavyweight). Instead, we can use N Lens objects (which are lightweight by comparison) each viewing a single Bubble, and translate the lenses instead of the bubble. Here's the relevant code:

Stage {
    scene: Scene {
       def bubble = Bubble {}
       content:
       Group {
            content: bind lazy
                for (ball in model.balls)
                    Lens {
                        x: bind lazy ball.x;
                        y: bind lazy ball.y;
                        view: bubble;
                    }
	}
    }
}

With this formulation of instancing I no longer have transform and bounding volume information about the "instanced" bubbles, however in this case I didn't need that since it's already present in the Bubblemark application's "model".

Performance of "Bubblemark" in our system seems good compared to others:

By comparison, the vector Flex example on bubblemark.com has roughly half the frame-rate, and more than double the CPU usage, even while rendering far fewer pixels. Of course, these discrepancies aren't just about instancing, but more so about using the GPU rather than the CPU for rasterization.

As a second example, here's a quickly thrown together example of a 3D chart, which was produced using one cylinder instance and one rectangle instance:

Posted at 03:49PM Jul 23, 2009 by Christopher Oliver in Research  |  Comments[18]