A flexible and extensible traversal framework for scenegraph systems. Technischer Bericht

Graph traversal is a very basic concept in computer science, as graphs are needed and used in lots of places. As scenegraphs are graphs too, the standard graph traversal methods should suffice to cover scenegraph traversals. In practice, scenegraphs are a little different. They are heterogeneous, i. e. there are a number of different node types, which need to be treated differently. They are also used by a number of different types of traversals. Furthermore new node types as well as traversal types are added routinely to a scenegraph, often application-specific ones. This can be a problem when the source code of the library is not available. This work describes a framework for scenegraph traversals that is flexible as well as extensible to allow adding node types as well as traversal types without having to change existing code. The concept is based on three classes: Actors, Iterators and Actions. The Actors are the primitive active part and are used to be easily combinable to make up complex traversals. Actors are categorised according to different criteria to allow optimised traversals. Iterators are used to select the next node to traverse from the list of available nodes, allowing simple depth-first traversals as well as ordered traversals. The Action keeps all the parts together.