Attribute grammars for incremental evaluation of scene graph semantics

Abstract

In CAD-Software und Videospielen finden häufig sogenannte Szenegraphen Anwendung, um die Relationen der Daten in einer Szene zu beschreiben. Durch die hierarchische Anordnung der Knoten eines solchen Szenegraphen können Attribute und deren Gültigkeitsbereiche, wie beispielsweise affine Transformationen oder Texturinformationen, einfach und konsistent modelliert werden. Szenegraphsysteme erlauben zwar durch ihre hohe Ausdrucksstärke die Modellierung von dynamischen Sachverhalten, wie etwa Animation und Simulation, die Programmierung davon gestaltet sich jedoch häufig als schwierig und ineffizient. In dieser Arbeit zeigen wir Probleme von bestehenden Systemen auf, synthetisieren Design Ziele und entwickeln ein Szenegraph Konzept, welches diese Probleme auf neuartige Art und Weise löst. Das hohe Abstraktionsniveau unseres Systems erlaubt eine effizientere Programmierung von interaktiven Rendering Applikationen. Die verbesserte Programmierbarkeit wurde anhand eines Anwendungsfall demonstriert. Dazu wurde der Programmieraufwand in unserem System mit dem von alternativen Implementierungstechniken verglichen. Anhand von synthetischen Testszenen zeigen wir, dass unser vorgestelltes System trotz des hohen Abstraktionsniveaus, auch in dynamischen Szenen bessere Performance erreicht als bestehende Systeme.

Three dimensional scenes are typically structured in a hierarchical way. This leads to scene graphs as a common central structure for the representation of virtual content. Although the concept of scene graphs is versatile and powerful, it has severe drawbacks. Firstly, due to its hierarchical nature the communication between related nodes is cumbersome. Secondly, changes in the virtual content make it necessary to traverse the whole scene graph at each frame. Although caching mechanisms for scene graphs have been proposed, none of them work for dynamic scenes with arbitrary changes. Thirdly, state-of-the-art scene graph systems are limited in terms of extensibility. Extending framework code with new node types usually requires the users to modify traversals and the implementations of other nodes. In this work, we use attribute grammars as underlying mechanism for specifying scene graph semantics. We propose an embedded domain specific language for specifying scene graph semantics, which elegantly solves the extensibility problem. Attribute grammars provide well-founded mechanisms for communication between related nodes and significantly reduce glue code for composing scene graph semantics. The declarative nature of attribute grammars allows for side-effect free formulation of scene graph semantics, which gives raise for incremental evaluation. In contrast to previous work we use an expressive computation model for attribute grammar evaluation which handles fully dynamic scene graph semantics while allowing for efficient incremental evaluation. We introduce all necessary mechanisms for integrating incremental scene graph semantics with traditional rendering backends. In our evaluation we show reduced development effort for standard scene graph nodes. In addition to optimality proofs we show that our system is indeed incremental and outperforms traditional scene graph systems in dynamic scenes.