Prozeduale Bäume

Prozeduale Bäume sind eine tolle Sache für eine größere Umgebung, wenn man dem Spieler nicht immer die selben - von Grafikern erstellten - Bäume vorsetzen möchte. Denn es wäre sehr Aufwändig für einen Wald aus > 10 Bäumen niemals den selben Baum doppelt in einem Bild zu verwenden und somit für den Betrachter die Welt glaubhaft(er) zu gestalten.

Allgemeine Vorgehensweise

Im Unterschied zur Landschaft oder ähnlichen Prozedualen Grafiken sind hier die unterschiedlichen Stufen der Generierung meist auch unterschiedliche Objekttypen. Ausgehend von einem Stamm werden die Äste berechnet, über die Äste die Zweige und schlussendlich werden die Blätter veteilt.

Bäume mit L-Systems

L-Systems basieren darauf, aus einem vorgegebenem, primitiven Muster durch rekursives einsetzen dieses Musters in sich selbst ein beliebig komplexes Modell zu erstellen.

Mehrere Detailstufen eines Baumes mit L-Systems, generiert mit Fractint

L-Systems wären nur mit stärkeren Modifikationen auch für 3D-Bäume einsetzbar, denn das Verhältnis von Blättern (höchste Stufe) zu Stamm und Ästen (die ersten paar Stufen) lässt sich nur schwer regulieren. Zum generieren von 2D-Texturen eignen sie sich hingegen sehr gut. Für die höchste Stufen werden die Linien durch Blatttexturen ersetzt, für die unteren Stufen eine Holztextur mit entsprechender Dicke. Natürlich sollte der Algorithmus auch noch mit Informationen zur Dicke und ähnlichem gefüttert werden.

Speedtree Bäume

Dies ist nicht der Name eines Algorithmus, sondern eines Produktes. Ich nenne sie deshalb so, da die Idee Bäume auf diese Art zu Generieren meines Wissens nach erstmals in der Middleware Speedtree von Interactive Data Visualization (IDV), Inc. umgesetzt wurde. Dieser Text bezieht sich auch sehr stark auf diese Software, jedoch natürlich mehr auf den technischen Aspekt um selbst Bäume dieser Art generieren zu können.

mehrere generierte Bäumen des selben Typs mit einem derartigen Algorithmus

Generelle Vorgehensweise

Bei Speedtree wird der Baum in bis zu 4 unterschiedliche Stufen unterteilt:

• Stamm
• beliebige viele Aststufen
• Zweige
• Blätter

Jede Stufe baut auf der vorigen Stufe auf:

• Äste werden für den Stamm oder für jeden Ast der vorigen Stufe generiert
• Zweige werden für jeden Ast generiert
• Blätter werden für jeden Zweig generiert

Stamm, Äste und Zweige werden grundlegend gleich generiert, jedoch sind bei einem mehr bei einem weniger Informationen nötig.
Die unterschiedlichen Bäume, die jedoch dennoch ähnlich aussehen und vom selben Baumtyp sind, werden durch Pseudozufallszahlen für nahezu jeden einstellbaren Wert erzeugt. Somit hat nahezu jeder Wert auch eine maximale Abweichung.

Stamm

Stamm gibt es natürlich nur einen. Er wird durch einen Zylinder mit beliebig vielen Unterteilungen in der Höhe und auch im Grundriss (also dem Kreis) definiert. Jeder Punkt dieses Zylinders wird durch verschiedenste Parameter berechnet. Einmalig sind für den Stamm folgende Werte wichtig:

• Radius
• Größe
• Startwinkel
• Unterteilungen in der Höhe
• Unterteilungen des Grundrisses
• Wiederholungen der Textur in der Höhe
• Wiederholungen der Textur am Grundriss
• ggf. Gravitation (dient als Multiplikator für alle Neigungen nach unten oder oben)

Abhängig von der Höhe werden zusätzlich noch folgende Parameter wichtig:

• Profileinwirkung
• Radiusmultiplikator (die Dicke des Stammes abhängig von der Höhe, ein Multiplikator für Radius)
• Neigungswinkel
• Abweichung

Aus diesen Parametern lässt sich nahezu jede beliebige, aber dennoch natürlich wirkende Stammform erzeugen. Das Profil gibt hierbei eine zufällige Abweichung für jeden Punkt des Grundrisses an, der jedoch für jeden Punkt des Grundrisses in der Höhe gleich sein sollte. Das Profil eignet sich sehr gut zur Simulation von Wurzeln am unteren Ende des Stammes.
Die Abweichung gibt eine zufällige Neigung an die zum Neigungswinkel addiert wird. Die Punkte des Baumes werden nun wie folgt berechnet (Neigungen vorerst außer Acht gelassen)

G = die (2D-)Punkte des Grundrisses (ein Kreis mit Radius 1 und den angegebenen Unterteilungen)
Pg = Profileinwirkung in Abhängigkeit der Höhe des Punktes
Punkt = ( Pg + Radius * Radiusmultiplikator(Höhe) ) * G

Dieser Vorgang muss natürliche für jede Höhe durchgeführt werden. In der Höhe wird der Stamm linear unterteilt, demnach ist

Höhe von Schicht X = X * (Größe / (Unterteilungen der Höhe - 1) )

sofern bei den Unterteilungen auch die oberste und die unterste Schicht mit gezählt wird. Die Neigung des Stammes lässt sich sehr gut über Matrizen berechnen. Für jede Höhenschicht wird dabei die Matrix berechnet, in Pseudocode:

M = Identitätsmatrix
Rotiere M um Z-Achse nach belieben (die Neigung sollte nicht immer in die gleiche Richtung gehen)
Für jede Höhenschicht
 Multipliziere Punkte dieser Höhenschicht mit M
 Rotiere M um X-Achse um ( Abweichung(Höhe) + Neigungswinkel(Höhe) ) * Gravitation
 wenn unterste Höhenschicht
  Rotiere M um X-Achse um Startwinkel
 Verschiebe M nach oben (Z-Achse) entsprechend der Höhe eines Höhensegmentes

Rotiere um Z-Achse nach belieben bedeutet hier einen Zufallswert zwischen 0 und 360 Grad.
In diesem Pseudocode ist zu beachten, das die unterste Schicht keine Neigung erhält. Dies hat den Nachteil dass es bei stärkeren Rotationen nicht ganz so gut aussieht, jedoch den Vorteil, dass jeder Punkt der Grundfläche immer am Boden steht (Höhe 0 hat). Wenn der Untergrund nicht halbwegs eben sein muss, so ist dies jedoch eher egal.

Äste

Äste werden vom Stamm ausgehend generiert. Für die Generierung der Äste werden beim Stamm nun noch weitere Parameter benötigt:

• Von wo weg (Prozent der Höhe)
• Bis wo (Prozent der Höhe)
• Anzahl (Abhängig von der Höhe)

Die Abhängigkeit der Höhe hat den Vorteil, dass es ein extrem kleiner Baum nicht gleich viele Äste wie ein großer erhält.
Gleiches gilt jedoch auch für jedes Ast-Level, da es ja mehrere Level geben kann, also benötigt auch jedes Astlevel die selben Informationen zur Generierung der nächsten Ast-Level.

Die Anzahl der Äste ist beispielsweise je 10 Meter in der Länge der Vorgänger-Stufe angegeben. Dadurch kann man die Anzahl sehr leicht bestimmten (Tatsächliche Anzahl = Anzahl * 10 / Länge). Die Generierung der Äste kann nun folgendermaßen erfolgen:

Höhe = Random im Bereich [Von wo Weg|Bis wo]
M = Matrix der entsprechenden Höhensegmentes zu <Höhe> (des Stammes oder des Astes)
HSeg = Höhe des entsprechenden Höhensegmentes (aktuelle Höhe von M)
Verschiebe M nach oben um <Höhe> - <HSeg>
Rotiere M um Z-Achse nach belieben (damit die Äste in unterschiedliche Richtungen zeigen)
Rotiere M um X-Achse entsprechend <Startwinkel(Höhe)>

Rotiere um Z-Achse nach belieben bedeutet hier einen Zufallswert zwischen 0 und 360 Grad.
Startwinkel(Höhe) ist hierbei ein Wert der in Abhängigkeit der Höhe/Länge der vorigen Stufe angegeben wird. Abhängig von der Höhe/Länge der vorigen Stufe benötigt man in der zu generierenden Aststufe folgende Informationen:

• Länge
• Radius (ein Multiplikator für den Radius der Vorgängerstufe an der entsprechenden Höhe)
• Startwinkel
• Graviation (Wiederum ein Multiplikator für Neigungen welcher jedoch bei Ästen sehr viel ausmacht)

Durch diese Parameter sind die Anfangsparameter die wir auch beim Stamm hatten gegeben, zur Erinnerung:

• Radius
• Größe
• Startwinkel
• Gravitation

Auch die anderen Parameter, diese waren:

• Profil in Abhängigkeit der Höhe
• Radius in Abhängigkeit der Höhe
• Winkel in Abhängigkeit der Höhe
• Abweichung in Abhängigkeit der Höhe
• Unterteilungen in der Höhe
• Unterteilungen des Grundrisses
• Wiederholungen der Textur in der Höhe
• Wiederholungen der Textur am Grundriss

werden genau so für jede Aststufe benötigt. Nur das Profil ist für Äste kaum noch relevant, kann aber bei Bedarf ebenfalls verwendet werden.

Die Generierung der Astgeometrie erfolgt genau gleich wie bei einem Stamm, mit sehr geringen Modifikationen:

• Profil muss nicht mit einberechnet werden
• Die Anfangsmatrix wird durch die Vorgängerstufe definiert (nicht durch die Identitätsmatrix)
• Bei den Ästen ist es (im Gegensatz zum Stamm) meist sinnvoll wenn auch das unterste (erste) Längensegment rotiert wird, da dieses im Stamm ist und somit nicht sichtbar sein sollte.

Zweige

Zweige sollen sehr detailiertes, feines Geäst darstellen. Dazu werden teilweise durchsichtige Texturen (Opacity Maps, also mit Alpha 0 oder 255) verwendet.

Zweige werden genau gleich erzeugt wie Äste. Auch die Geometrie wird sehr ähnlich generiert obwohl sie ganz anders aussieht. Hier möchte ich mich also auf die Unterschiede konzentrieren.

Die Geometrie eines Zweiges ist eine beidseitig sichtbare (siehe Backface Culling), 2D Geometrie, und zwar eine Ebene welche jedoch mehrere Unterteilungen entlang der Länge und auch Krümmungen enthalten kann. Somit werden anstatt eines Kreises als Grundfläche einfach 2 Punkte zur Berechnung verwendet. Für die Breite sind keine Unterteilungen nötig.

Da es sich um eine 2D Geometrie mit einer 2D Textur handelt, sollte das Verhältnis von Länge zu Breite immer gleich sein. Aus diesem Grund fallen alle Berechnungen für den Radius weg, es kommt jedoch ein zusätzlicher Faktor zur Angabe dieses Verhältnisses hinzu (oder er wird aus dem Seitenverhältnis der Textur entnommen).

Dies waren auch schon die beiden wichtigsten Unterschiede und somit sollte das Generieren von Zweigen kein Problem sein wenn man bereits einen Stamm und Äste hat.

Blätter

Eine gute Möglichkeit Blätter zu einem Baum hinzu zu fügen sind spherische Billboards. Dabei wird ebenfalls eine teilweise Transparente Textur verwendet welche eine Ansammlung von Blätter dar stellt. Zur Erzeugung können wiederum die Von wo weg- und Bis wo hin Werte der vorigen Stufe verwendet werden. Auch die Anzahl im Verhältnis zur Länge wird in der Vorgängerstufe angegeben. Im Unterschied zu den vorigen Baumteilen werden die Blätter ganz anders, jedoch um einiges einfacher generiert. Es sind nur 2 Parameter notwendig:

• Größe eines Blattes (da es sich um spherische Billboards handelt sind sie üblicherweise quadratisch)
• Abstand zum Vorgänger in Abhängigkeit der Länge

Die Position eines Blattes kann nun gleich wie bei Ästen durch die Matrix des Vorgängers bestimmt werden, mit dem Unterschied das nur 1 Punkt mit dieser Matrix multipliziert werden muss.

Texturen

Die Texturcoordinaten-Berechnung sollte keine Probleme bereiten. Beim Stamm und bei den Ästen werden diese einfach linear entlang der Höhe und um den Grundriss verteilt. Folgende Texturen werden benötigt:

• Stamm und Äste: eine Kachelbare Rindentextur
• Zweige: Geäst, natürlich auch mit einem "Stamm" von dem dieses Geäst entspringt
• Blätter: eine Ansammlung von Blättern.

Wertabhängige Parameter

Es wurden in diesem Artikel sehr häufig Parameter verwendet die von einem anderen Wert abhängig sind (der Höhe oder Länge einer Stufe oder der vorgänger Stufe). Dies ist natürlich ein idealer Anwendungsfall für 2D-Splines. Um den selben Kurveneditor für alle Parameter verwenden zu können, sollten natürlich alle Abfragen in einem Definierten Bereich sein. Im Endeffekt wird jedoch nur eine Funktion benötigt die einen durch den Grafiker festgelegten Wert X für eine Höhe/Länge Y liefert.

Schlussworte

Halbwegs realistisch aussehende, prozedual erstellte Bäume sind eine nicht triviale Angelegenheit, da vor allem schlecht gewählte Zufallswerte sehr viel Auswirkungen auf die Realitätsnähe haben können. Vor allem bei der Erzeugung von Ästen und Zweigen und auch Blättern kann eine weitere Einschränkung des Zufalls äusserst hilfreich sein, da ansonnsten nur etwa 1 von 10 generierten Bäumen brauchbar ist. Die Verteilung der Äste und Zweige ist sehr häufig etwas ungut da sie alle etwa die selbe Höhe besitzen, oder alle etwa in die selbe Richtung zeigen können (was auch sehr häufig der Fall ist). Um dies zu umgehen könnten Beispielsweise hier die Rotation (welche im oberen Code immer durch die Z-Achse ausgedrückt wird) gleichmäßig auf alle erzeugten Äste verteilt werden, was jedoch natürlich wiederum den Zufall und somit die Unterschiede von einem Baum zum anderen einschränkt. Gleiches gilt für die Höhe.

Die Verteilung der Blätter ist ungut, da man bei einer rein zufälligen Verteilung fast 5 mal so viele Blätter für einen schönen Baum benötigt wie wenn man verhindert das 2 Blätter sehr nah beieinander liegen können, dies kann auch im (frei downloadbaren) Editor von Speedtree gut getestet werden. Vor allem bei den Blättern ist es jedoch natürlich eine Frage der Performance bei der Generierung und bei der Darstellung (Kollisionsabfragen bei der Erzeugung oder Brute force bei der Erzeugung wodurch unnötig viele Blätter immer gezeichnet werden müssen).

Bei derartigen Algorithmen muss also ein gutes Mittelmaß zwischen Zufall und Realismus (bzw. Prozentsatz der realistisch wirkenden Bäume) gefunden werden.

Hier möchte ich auch noch kurz auf die hier nicht behandelten Probleme eingehen:

Level of Detail
Bei den Blättern hat man hier 3 Möglichkeiten:

1. Blätter entfernen indem man sie verkleinert
2. Blätter entfernen indem man sie langsam transparenter macht
3. Blätter einfach entfernen (was jedoch zu Popping führt)

Natürlich müssen die restlichen Blätter vergrößert werden wenn Blätter entfernt werden.

Bei den Zweigen und Ästen sieht es ähnlich aus, hier kämen jedoch eventuell noch VIPMs in Frage.

Normalvektor-Berechnung
Die Normalvektor-Berechnung für den Stamm, Äste und für die Zweige dürfte nicht allzu Problematisch sein. Entweder man verwendet die Position des Punktes am Kreis für die Berechnung, oder man berechnet sich die Normalvektoren aus den 3eck-Daten.

Für die Blätter hingegen eignet sich wohl am Besten der Vektor vom Baumzentrum zur Blattposition.

Wind
Für die Blätter ist eine Windsimulation sehr einfach zu machen, indem man die Spherischen Billboards ein bisschen hin und her dreht. Für Äste und Zweige hingegen benötigt man wohl Vertexprogramme für eine effiziente Implementierung.

Kollisionsabfrage
Die Generierung der Kollisionsobjekte kann auf unterschiedliche Weise erfolgen. Man könnte vordefinierte Kollisionsobjekte für jeden Baumtyp verwenden, was jedoch nicht sehr genau ist. Für eine detailiertere Kollisonsabfrage werden natürlich die Bounding Volumen von Stamm, Ästen, Zweigen und evntl. auch von den Blättern benötigt. Die Berechnung von diesen fällt jedoch nicht in den Bereich der Baum-Generierung.