Alexander Förster

Graphische Darstellung von DOL-Systemen

Betreuer: Bernd Gärtner


DOL-Systeme sind formale Sprachen, deren Wörter sich als `Turtle-Grafik' interpretieren lassen. Schon sehr einfache Bildungsgesetze führen dabei zu komplexen und oft ästhetisch sehr ansprechenden Bildern. Eine typische Anwendung ist die Erzeugung von Pflanzen, wobei es die rekursive Struktur der DOL-Systeme erlaubt, die Pflanze in verschiedenen `Wachstumsstufen' zu betrachten. Jedes Bild enthält dabei mehrere Kopien des vorhergehenden Bildes. Bei Wachstumsstufe unendlich schließlich erhält man ein selbstähnliches Bild, ein Fraktal.

Wie an dieser kurzen Sequenz schon zu erkennen ist, nimmt die Anzahl der gezeichneten Linien mit der Wachstumsstufe exponentiell zu, und entsprechend lange dauert auch das Zeichnen. Bei der Diplomarbeit steht deshalb die Frage im Vordergrund, wie man diesen Zeichenvorgang beschleunigen kann. Ein Teilproblem besteht darin, die Größe der Zeichnung abzuschätzen. Ursprünglich werden nämlich auch die Bilder exponentiell groß und müssen - wie oben - skaliert werden, so daß sie auf den Bildschirm passen. Natürlich kann man die Größe der Zeichnung berechnen, indem man die Zeichnung selbst in exponentieller Zeit berechnet. Ein Ergebnis der Arbeit ist, daß man dieses Problem aber auch sehr elegant in linearer Zeit lösen kann (linear in der Wachstumsstufe).

Bleibt nur noch das Zeichnen selbst. Hier kann man Zeit sparen auf Kosten der Genauigkeit. Nutzt man die Tatsache aus, daß sich das nächste Bild aus Kopien des aktuellen Bildes zusammensetzt, so kann man das aktuelle Bild einfach als Rasterbild (`Bitmap') auffassen und Kopien davon erzeugen. Das nutzt aus, daß der Rechner Rasterbilder effizient verarbeiten kann, und geht wesentlich schneller, als die Kopien jeweils aufwendig noch einmal zu zeichnen. Beginnt man damit allerdings bei einer zu frühen Wachstumsstufe, so erhält man durch sogenannte `aliasing'-Effekte sehr ungenaue Ergebnisse.

Die theoretischen Überlegungen der Diplomarbeit haben Eingang gefunden in ein benutzerfreundliches Programm zur schnellen graphischen Anzeige von DOL-Systemen.