Przemyslaw Prusinkiewicz, Computergrafiker an der Universität von Calgary (Kanada), sah sich einem ungewöhnlichen Fälschungsvorwurf ausgesetzt. Seine Kollegen argwöhnten nicht etwa, er wolle etwas Nachgemachtes für echt ausgeben, sondern umgekehrt etwas Echtes für nachgemacht.

Jedes Jahr trifft sich der Unterausschuss für Computergrafik (special interest group on graphics, Siggraph) der amerikanischen Informatikervereinigung ACM zu einer Art Leistungsschau. Auf einem dieser Treffen Anfang der neunziger Jahre legte Prusinkiewicz ein Bild von einem Sonnenblumenfeld vor, das so echt aussah, dass selbst Fachkollegen es nicht für computererzeugt halten mochten.

Hinter dieser Misstrauen erregend guten Darstellungsleistung steckt ein ganzes Bündel von Ideen und Verfahren, die seit Prusinkiewicz’ ersten Pionierarbeiten noch beträchtlich weiterentwickelt wurden. Über sie soll in diesem Artikel berichtet werden.

Ein wichtiger Grundgedanke ist: Der Computer erzeugt nicht nur ein Bild von einer Pflanze oder einer ganzen Landschaft. Er erzeugt intern eine dreidimensionale geometrische Repräsentation und erst in einem zweiten Schritt aus dieser Repräsentation ein Bild. Durch Änderung des Betrachterstandpunkts ergeben sich aus derselben internen Darstellung immer wieder neue Bilder. Der Benutzer kann also in der imaginären Landschaft, die sich ihm am Computerbildschirm präsentiert, umherwandern.

Wie aber macht man die interne Darstellung einer Pflanze? Eine nahe liegende Idee ist, dass die virtuelle Pflanze so heranwachsen soll wie die echte. Aus einem kleinen Wachstumskegel sprießen eine Blattanlage und ein neuer Wachstumskegel; die Blattanlage wächst zu einem Blatt aus, das sich seinerseits in Stiel und Blattspreite differenziert. Dieses Prinzip hat der Biologe Aristid Lindenmayer 1968 in den so genannten L-Systemen formalisiert (Spektrum der Wissenschaft 9/1989, S. 52). Eigentlich wollte er in erster Linie das Zellwachstum modellieren; die L-Systeme wurden aber bald auch für Pflanzen verwendet.

Ein Buchstabe steht beispielsweise für eine Knospe. Zu diesem Buchstaben gibt es einerseits eine Anweisung, wie diese Knospe zu zeichnen ist, und aus dem Kontext ergibt sich, wohin; andererseits gibt es eine Ersetzungsregel, die beispielsweise aus "Knospe" so etwas wie "Blattanlage plus Knospe" macht. Oder aus einem Zweig wird ein Zweig mit zwei angesetzten kleineren Zweigen; diese verzweigen sich wieder durch Anwendung der Ersetzungsregel, bis schließlich die Zweige fünfter Ordnung Blätter ansetzen.

Indem man auf einen gewissen Buchstaben (eine "Keimzelle") die Ersetzungsregel anwendet, auf die dadurch entstehende Zeichenkette wiederum alle Ersetzungsregeln und so weiter, gewinnt man immer länger werdende Zeichenketten. Lässt man schließlich den Computer eine solche Zeichenkette als Folge grafischer Anweisungen interpretieren, gewinnt man ein Bild von einer ausdifferenzierten Pflanze – je länger die Zeichenkette, desto vielgestaltiger.

Auf diese Weise lassen sich allerdings sowohl natürlich wirkende als auch physikalisch unmögliche Bäume erzeugen. Die Menge der statisch stabilen und erst recht die Menge der natürlich vorkommenden Bäume ist ein winziger Teil der insgesamt herstellbaren Verzweigungsstrukturen. Es bleibt also die Frage, wie man die Menge der herstellbaren Bäume einschränkt auf im weitesten Sinne lebensfähige Exemplare, um aus dieser Menge im nächsten Schritt die tatsächlich existierenden zu extrahieren.

Eine Möglichkeit besteht darin, von dem hohen Abstraktionsniveau der L-Systeme abzugehen und den im Computer wachsenden Baum realitätsnäher zu modellieren. Das läuft auf eine klassische Simulation von Wachstumsvorgängen hinaus. Gewisse zahlenmäßige Parameter ("Metrikdaten") wie etwa der typische Winkel einer Verzweigung oder das Ausmaß, in welchem sich ein wachsender Stängel zum Licht hin krümmt, lassen sich an realen Bäumen messen und in die Simulation einbringen.

So gibt es eine Methode zur Erzeugung von Bäumen, bei der das Programm entsprechend den Metrikdaten der Baumart Knospen auf der Oberfläche einer "Urzelle" verteilt und wachsen lässt. (Natürlich erzeugen wir oder die Computer keine Bäume, sondern nur interne Darstellungen von Bäumen; aber der verkürzende Sprachgebrauch hat sich unter den Computergrafikern eingebürgert.) Ein anderes Verfahren setzt einen Baum algorithmisch aus vielen unsichtbaren Einzelsträngen zusammen, die von der Wurzel bis zu jeweils einem Blatt oder einer Blüte reichen. Der Querschnitt eines Astes oder Stamms ist charakterisiert durch die Anzahl der in ihm verlaufenden Stränge. Auf diese Weise ergeben sich natürliche Proportionen, ein Ansatz, den schon Leonardo da Vinci im 16. Jahrhundert formuliert hat.

Vereinigung von regelbasierten und prozeduralen Prinzipien

Obwohl dieses Verfahren eine Reihe natürlich wirkender Bäume erzeugt, ist es nicht so systematisch, wie man es sich wünschen würde. Die Vermessung realer Bäume liefert zwar eine Vielzahl beschreibender zahlenmäßiger Daten. Diese lassen sich jedoch im Allgemeinen nicht oder nur teilweise in Parameter einer Simulation umsetzen. Auf der anderen Seite bleibt die Abgrenzung unklar, mit welchen Parameterwerten ein Algorithmus natürlich wirkende Bäume liefert und mit welchen nicht. Es bleibt also ein erhebliches Maß an Probieren.

Neuere Ansätze – darunter der un-sere – sind bestrebt, aus dieser Not eine Tugend zu machen: Wenn man schon probieren muss, dann mit möglichst unmittelbarer Rückmeldung. Der Benutzer wählt das Bild- und Datenmaterial, aus dem er einen Baum machen will, und die Software führt ihm, dank der hohen Rechenleistung moderner Grafikrechner, auf der Stelle vor Augen, wie die zugehörige Pflanze aussieht. Insbesondere in der Gebrauchsgrafik ist dies von Vorteil, weil hier neben der botanischen Korrektheit weitere Anforderungen an die Modelle gestellt werden. Oftmals werden für Filmsequenzen Bäume ganz bestimmter Form angefordert, oder bewusst irreale Pflanzen für Spezialeffekte.

In unserem Ansatz wird eine Pflanze aus Bausteinen zusammengesetzt, die jeweils Pflanzenteile wie etwa Blätter oder Blüten erzeugen. Der Benutzer verbindet die Bausteine interaktiv zu einem Graphen, der die gesamte Pflanze beschreibt. Das Neuartige an diesem Verfahren ist die Kombination von regelbasierten und prozeduralen Elementen zu einer Modelliermethode. In den einzelnen Komponenten berechnen Algorithmen die geometrischen Details; das Regelsystem wird durch den Graphen beschrieben, kann aber nunmehr einfacher Natur sein, da viele Aspekte der Pflanze durch die geometrischen Algorithmen abgedeckt werden.

Die von uns praktizierte Zerlegung in algorithmische und regelbasierte Anteile hat einen weiteren Vorteil: Ohne großen Zusatzaufwand kann man – zum Beispiel – vom Wachstum einer Pflanze eine Art Kurzfilm erzeugen. Das Regelsystem bleibt unverändert; nur die Parameter der Algorithmen in den Komponenten ändern sich mit der "Zeit", in der das fiktive Wachstum stattfindet. Der Benutzer kann sich damit begnügen, die Parameterwerte für einige markante Zeitpunkte zu bestimmen. Der Computer berechnet dann für jedes Filmbild durch Interpolation die gültigen Parameter, aus diesen eine Pflanzengeometrie und aus dieser das fertige Bild.

Eine derart kontinuierliche Veränderung einer Pflanze wäre mit einem L-System nur über umständliche Zusätze zu modellieren, da dort Wachstum nur in diskreten, ziemlich großen Schritten stattfindet.

Hat man auf diese Weise verschiedene Pflanzen erzeugt, möchte man diese zu ganzen Landschaften kombinieren. Aus einer Reihe von Gründen ist es hier aber mit dem einfachen Nebeneinanderstellen der Modelle nicht getan:

- Geometrische Komplexität: Die Geometrie einer Pflanze wird üblicherweise über Dreiecke im Raum beschrieben. Ein einzelner Baum benötigt bis zu einer Million Dreiecke, ein Quadratmeter Wiese eine ähnliche Anzahl. Für größere Szenen oder gar ganze Landschaften wären daher viele Milliarden Dreiecke notwendig, was selbst moderne Rechner vor große Schwierigkeiten stellen würde. Abhilfe schafft eine gezielte Vergröberung, ein so genannter Level-of-Detail-Algorithmus: Je weiter entfernt ein Baum vom Betrachter steht, desto weniger geometrische Details werden zu seiner Beschreibung verwendet. Ein guter Algorithmus verändert die Beschreibung der Pflanze so unmerklich, dass dem Betrachter, der sich virtuell auf sie zu bewegt, nichts auffällt.

- Natürliche Variabilität: Keine zwei Pflanzen gleichen einander völlig. Würde man eine einmal erzeugte Pflanze vielfach in einer Szene wiederholen, würde es dem Betrachter sofort auffallen. Daher muss eine Anzahl verschiedener Repräsentanten für jede Spezies erzeugt werden, die – gedreht und geringfügig vergrößert oder verkleinert – über die Szene verteilt werden. Interessanterweise reichen einige wenige Repräsentanten aus, um einen Eindruck natürlicher Variabilität zu erzeugen. Nur die Daten dieser Exemplare werden gespeichert und eine Liste der Positionen angelegt, an denen sich Kopien eines Exemplars befinden sollen.

- Interaktion zwischen Pflanzen: Das Aussehen einer Pflanze wird maßgeblich durch ihre Umgebung beeinflusst. Ein Baum neben einer Mauer oder innerhalb einer Baumgruppe hat eine andere Form als ein allein stehender Baum. Dies muss schon bei der Herstellung der Einzelpflanzen berücksichtigt werden. Hier finden geometrische Randbedingungen Anwendung, die schon während der Herstellung einer Pflanze deren Gesamtvolumen beschränken.

Sind die geometrischen Daten für eine Szene erzeugt, wird im nächsten Schritt eine gedachte Kamera mit Blickrichtung, Öffnungswinkel und Bildauflösung definiert. Für jedes Pixel des herzustellenden Bildes sind nun Farbe und Helligkeit zu bestimmen. Dies geschieht üblicherweise durch Strahlrückverfolgung (Raytracing, Spektrum der Wissenschaft 4/2000, S. 74, und 12/1991, S. 128): Man schickt vom Projektionszentrum der gedachten Kamera durch jedes Pixel der Bildebene einen Strahl in die Szene und bestimmt, welche Objekte er trifft.

Bei mehreren Millionen Strahlen und einigen Milliarden Dreiecken entsteht hierbei ein erheblicher Rechenaufwand. Für spiegelnde Oberflächen wie Wasser oder durchscheinende Gegenstände wie dünne Blätter ist der Strahl noch über das erste getroffene Objekt hinaus zu verfolgen, was den Aufwand weiter erhöht. Erstaunlicherweise lassen sich die Algorithmen mit allerlei Tricks aber so effizient gestalten, dass die Erzeugung der Bilder oftmals schneller vonstatten geht als die Herstellung und Verwaltung der geometrischen Daten.

Wandern durch virtuelle Landschaften

Zur Beschreibung einer großen Szene verstreuen wir zunächst gleichsam viele Exemplare einer Pflanze über den gedachten Boden. Die Standorte der einzelnen Pflanzen sowie ihre individuellen Eigenschaften (beschrieben durch geometrische Parameter) hängen sowohl vom Zufall ab als auch von vorgebbaren globalen Größen wie Bodenfeuchtigkeit, Sonneneinstrahlung und Hindernissen in der Landschaft. Im nächsten Schritt vereinfachen wir das Sortiment, indem wir – mit einer Variante der Clusteranalyse aus der Statistik – Repräsentanten bestimmen, möglichst wenige Musterexemplare, welche die Vielfalt der soeben erzeugten Pflanzen möglichst gut ausschöpfen. Jede Pflanze wird dann durch das ihr ähnlichste Musterexemplar ersetzt. Diese Instanzenbildung sorgt bei geeigneter Implementierung für eine dramatische Reduzierung der Daten. Für übliche Szenen müssen statt 500 Gigabyte Daten nur noch einige hundert Megabyte verarbeitet werden, was eine Bilderzeugung auch auf PCs möglich macht.

Eine Instanzenbildung kann auch auf Teilen der Einzelpflanzen geschehen. Ein kleiner Ast kann an vielen Stellen innerhalb eines Baumes wiederholt werden, ohne dass es visuell auffällt. Größere Teile eines Baumes können analog in einer Ansammlung von ähnlich aussehenden Bäumen wiederholt werden. Mit der Ausnutzung aller dieser Möglichkeiten lässt sich eine weitere dramatische Datenreduktion erzielen.

Die erzeugten Computergrafiken sind mehr als nur schöne Bilder. Mit ihnen eröffnen sich neue Möglichkeiten beispielsweise in der Visualisierung ökologischer Daten. Oftmals scheitert die Realisierung von Landschaftsplanungen an der mangelnden Transparenz der ausgearbeiteten Pläne. Synthetisch erzeugte Landschaften können in neuer Weise Folgen von Eingriffen in Ökosysteme darstellen, Entscheidungsträger werden in der Lage sein, sich in einer geplanten virtuellen Landschaft umher zu bewegen, Planungsalternativen können visuell abgewogen werden. Mit speziellen Verfahren der Computergrafik kann man die Darstellung auch gezielt so schematisch und nicht-realistisch gestalten, wie das in den Präsentationsskizzen der Landschaftsplaner üblich ist – mit dem Unterschied, dass der Benutzer durch diese "Skizze" hindurchwandern kann.

Ein Naturkundemuseum der Zukunft könnte den Besucher in virtuelle Welten entführen, etwa in einen urzeitlichen Wald oder auch in eine einfache Wiese, die aber aus der Ameisenperspektive betrachtet wird. So könnte Natur auf didaktisch neue und auch für junge Menschen attraktive Weise vermittelt werden.

Auch Fahr- und Flugsimulatoren profitieren von realistischen Landschaften. Neben anderen Faktoren ist die Realitätstreue naher Objekte entscheidend für das Bewegungsgefühl des Benutzers. Die Probleme mit der großen Menge an geometrischen Daten lassen sich durch image-based rendering vermindern. Unter diesem Begriff vereinigen sich Techniken zur schnellen und Speicherplatz schonenden Berechnung neuer Objektansichten aus vorab berechneten Bildern und Datenstrukturen. Anstelle von Millionen Dreiecken zur Darstellung eines Baumes benötigt man hier nur mehr einige vorab berechnete Bilder mit wenigen Zusatzdaten.

Eine Reihe von vollständig synthetisch erzeugten Kinofilmen demonstrierte in den letzten Jahren die Möglichkeiten moderner Computergrafik. In vielen weiteren Filmen findet Computergrafik auch in einzelnen Szenen ihren Einsatz, ohne dass der Zuschauer etwas davon bemerkt. Hier wie auch bei der Herstellung von Computerspielen liegt weiteres großes Potenzial für den Einsatz synthetischer Pflanzen und Landschaften.

Literaturhinweise


Interactive Modeling of Plants. Von Bernd Lintermann und Oliver Deussen in: IEEE Computer Graphics and Applications, Bd. 19, Nr. 1, Januar–Februar 1999, S. 56.

Realistic Modeling and Rendering of Plant Ecosystems. Von Oliver Deussen et al. in: Computer Graphics, Bd. 32, Nr. 4, August 1998, S. 275.

Sprunghaftes Wachstum einer Computerpflanze


Man stelle sich eine Art künstliches Krabbeltier vor, das sich im dreidimensionalen Raum in diskreten Schritten bewegen kann. Zu jedem Zeitpunkt hat es eine Position und eine Orientierung, das heißt, eine bestimmte Lage im Raum, sodass man von vorne, hinten, links, rechts, oben und unten in Bezug auf die gegenwärtige Lage des Krabbeltiers sprechen kann. Wenn es sich bewegt, dann nach vorn; es kann auch zuvor seine Orientierung verändern. (Es handelt sich um eine dreidimensionale Version der "Schildkröten", mit denen Seymour Papert eine diskrete Geometrie der Ebene definierte.) Man kann das Krabbeltier durch Signale fernsteuern, die nur aus jeweils einem Zeichen bestehen:

F wandere eine gewisse Strecke d in der aktuellen Ori entierung, zeichne eine Linie

f wie F, aber ohne eine Linie zu zeichnen

+ – wende dich um einen gewissen Winkel a nach rechts bzw. links gegenüber der Laufrichtung

& ^ kippe um den Winkel a nach oben bzw. unten

\ / rotiere die eigene Körperachse um den Winkel a nach rechts bzw. links

| "mach auf dem Absatz kehrt": ersetze die bisherige Orientierung durch ihr Negatives

[ merke dir den gegenwärtigen grafischen Zustand (Po sition, Richtung, Malfarbe und so weiter)

] kehre zum zuletzt gemerkten grafischen Zustand zu rück

{ } fasse den Weg, den der Zeiger zwischen den ge schweiften Klammern zurücklegt, als Rand einer Fläche auf und fülle diese Fläche aus

! ’ Diese Zeichen ändern die Dicke und die Farbe der im Folgenden zu zeichnenden Linien.

Zu diesen "elementaren Zeichen" werden nun weitere definiert. Man hat die Freiheit, sich unter diesen Zeichen konkrete Dinge (in unserem Fall Pflanzenteile) vorzustellen: A wie Abzweigung, B wie Blatt, S wie Stiel. Maßgeblich ist jedoch nur eine Regel, die ein neu zu definierendes Zeichen durch eine Folge von (elementaren und neuen) Zeichen ersetzt. Ein System solcher Regeln könnte zum Beispiel wie folgt aussehen:

(1) A -> [&FB!A]////’[&FB!A]//////’[&FB!A]

(2) F -> S////F

(3) S -> FB

(4) B -> [’’’^^{-f+f+f-|-f+f+f }]

Aus einer gegebenen Zeichenfolge wird in einem Lindenmayer-System eine neue, indem für jedes Zeichen der Folge seine "Bedeutung", sprich die es definierende Zeichenfolge, eingesetzt wird. So entstehen aus der "Ur-Zeichenfolge", die nur aus dem Buchstaben A besteht, nacheinander die Folgen

[&FB!A]////’[&FB!A]//////’[&FB!A]

[&S////F[’’’^^{-f+f+f-|-f+f+f}]![&FB!A]////’[&FB!A]//////’[&FB!A]]////’[&S////F[ ’’’^^{-f+f+f-|-f+f+f}]![&FB!A]////’[&FB! A]//////’[&FB!A]]//////’[&S////F[’’’^^{-f+f+f-|-f+f+f}]![&FB!A]////’[&FB!A]//////’[&FB!A]]

Nach einer vorher festgelegten Anzahl von Ersetzungsschritten wird das Ergebnis gezeichnet, das heißt das gedachte Krabbeltier folgt den Bewegungs- und Zeichenanweisungen der so entstandenen Zeichenfolge (und ignoriert die neu definierten Zeichen).

---

Ein Baukasten für Pflanzen


Die Vorstellung von zusammensteckbaren Einzelteilen, wie in einem Baukasten für Kinder, kommt der Sache schon recht nahe: Will man einen Zweig mit Blättern modellieren, so nimmt man einen Blatt-Baustein, steckt ihn auf einen zugehörigen Stiel-Baustein und diesen auf einen Zweig-Baustein.

In der Tat kann in unserem Programm der Benutzer Symbole solcher Bausteine auf dem Bildschirm bewegen und zu einem Graphen verknüpfen. Die Bausteine sind jedoch weit mehr als nur passive Klötzchen. Hinter ihnen stecken ganze Unterprogramme; sie erzeugen nicht nur einfach vorgegebene Strukturen, sondern verändern sie in Abhängigkeit von Parametern, die der Benutzer angibt. So kann ein Blatt auf Anweisung des Benutzers in Sekundenbruchteilen breiter, gewölbter oder gezackter werden. Andere Anweisungen machen einen Baum schlanker oder gedrungener oder ändern den Winkel seiner Verzweigungen.

Weitere Bausteine vervielfältigen alles, was in dem Graphen an ihnen hängt, oder wirken global auf alle anderen Bestandteile des Graphen. Da die Algorithmen in den Bausteinen botanische Gesetzmäßigkeiten wiedergeben, stellen sich fast automatisch biologisch korrekte Modelle ein.

Ein kleines Sortiment von Bausteinen genügt, um fast jede Art von Pflanzen zu erzeugen. Unter den elf Typen, die wir momentan verwenden, sind:

Blatt: Komponente zur Konstruktion von Blättern. Der Benutzer kann verschiedene Blattformen einstellen. Zur Steigerung des realistischen Eindrucks wird diese Form mit Bildern echter Blätter überzogen (texture mapping, vergleiche Spektrum der Wissenschaft 12/1998, S. 98).

Horn: Erzeugt einen verallgemeinerten Zylinder, der seinerseits aus lauter kleinen Zylinderstücken zusammengesetzt wird (Spektrum der Wissenschaft 6/1997 S. 10). Hörner werden für alle Arten von Blattstielen, Gräsern und Zweigen verwendet.

Baum: Erzeugt einen Baumstamm und vervielfältigt alle an ihm in der Strukturbeschreibung hängenden Komponenten als Verzweigungen. Sind weitere Baumkomponenten angehängt, entsteht das Grundgerüst für einen Baum.

Phiball: Vervielfältigt alle Nachfolgekomponenten und setzt die verschiedenen Exemplare auf eine Kugeloberfläche, und zwar so, wie in echten Pflanzen die Anlagen einzelner Blütenblätter, Schuppen bei einem Tannenzapfen oder Sonnenblumenkerne sich anordnen (Spektrum der Wissenschaft 5/1996, S. 14). Dabei spielt das Verhältnis f (phi) des Goldenen Schnitts eine entscheidende Rolle.

Freiformdeformation: Dieser Baustein verändert die geometrische Gestalt einzelner Teile oder der gesamten Pflanze, die dadurch zum Beispiel um ein Hindernis herumwachsen kann.

Tropismus: Dieser Baustein dient zur Definition von Licht- und Gravitationsfeldern. Viele Pflanzen richten ihre Blätter und Zweige entsprechend diesen Feldern aus (Photo- bzw. Gravitropismus). Zusätzliche Effekte wie etwa der Einfluss von Wind auf die Wuchsform lassen sich als Tropismen modellieren.

Aus: Spektrum der Wissenschaft 2 / 2001, Seite 58
© Spektrum der Wissenschaft Verlagsgesellschaft mbH