Matrix Stack and the Visitor Pattern

Matrix Stack and the Visitor Pattern:

Scene Graphs and Scene Trees

When building a scene graph framework, such as the display list in ActionScript 3.0, two types of nodes are involved: internal nodes and leaf nodes. The transformation properties (x, y, rotation, etc.) are passed down from parents to children; that is, if the parent’s local coordinate is (10, 10), and a child’s local coordinate is (5, 5), then the global coordinate of the child is (15, 15).

ZedBox, my 2.5D billboard engine, internally manages objects in scene tree structure (a more specific type of scene graph where each child can only have one parent), just like the display list structure in ActoinScript 3.0. Each node holds a reference to an object containing its global transformation. When the scene tree is traversed in the render routine, the global transformation of each node is updated by its parents; in other words, the global transformation of each node is updated recursively from the root down.

Back then, this seemed to be a very reasonable approach to me. Later, however, I found out that this approach eventually made my code very messy and hard to maintain. Also, this approach does not apply to scene graphs; since in a graph each node can have more than one parents, it’s not right to have each node to hold reference to a single global transformation of its own. After a having a little chat with Jean-Marc Le Roux (the author of Minko 3D engine), I got to know that he used the Visitor Pattern in Minko to traverse the nodes managed in scene graph structure. Suddenly, it had struck me that this pattern is the key to calculate global transformation of the nodes in a scene graph. Instead of storing the global transformation of each node in the node itself, each node can have a chance to access the visitor when the visitor visits the node, where the visitor holds a reference to a matrix stack.

Matrix Stack

A matrix stack is essentially, well, a stack that contains matrices (here a matrix represents spatial transformation). The interface of a matrix stack may look like this [...]