+ All Categories
Home > Documents > Master thesis pascal_mueller02

Master thesis pascal_mueller02

Date post: 05-Dec-2014
Category:
Upload: guest39ce4e
View: 570 times
Download: 0 times
Share this document with a friend
Description:
 
18
16 2. LINDENMAYER-SYSTEME wurden eindrückliche Szenarios geschaffen (Abbildung 2.9). Natürlich wurden in diesen Beispielen auch stochastische Verhaltensweisen in die Simulationen miteinbezogen. Dieses Beispiel führt vor, dass man zuerst intensiv die Eigenschaften eines Objektes studieren muss, bevor man es mit einem L-System simuliert. Die entsprechenden Regeln zu finden kann ziemlich anspruchsvoll und aufwendig sein, wie die vielen Beispiele unter- schiedlichster Pflanzenarten aus Lindenmayers und Prusinkiewicz’ Arbeiten zeigen. 2.7 Open L-Systems Interaktion mit der Umgebung ist ein wichtiger Aspekt in der Entwicklung von Pflanzen. Während in umgebungssensitiven L-Systemen nur die Reaktion der Pflanze auf ihre Umgebung simuliert wird, sind Open L-Systems in der Lage, beidseitige Kommunikation zu modellieren. Das bedeuted, die Pflanze kann nun auch Änderungen in der Umgebung bewirken. Deshalb wurden die Query-Module zu Kommunikations-Modulen der Form ?E(x 1 , x 2 , ... , x n ) erweitert. Die Parameter x 1 , x 2 , ... , x n senden und empfangen Information der Umgebung. Zusätzlich wird der Umgebung immer der Status der Turtle (Position und Orientierung) mitgeliefert, d.h. dies muss nun nicht mehr explizit angegeben werden. Je grösser das Gleichungssystem zur Definition eines L-Systems wird, desto unüber- sichtlicher wird dieses. Deshalb wurden weitere Konstrukte eingeführt: Produktionen können Zuweisungsstatements für lokale Variablen beinhalten. Diese Zuweisungen sind in geschweiften Klammern und durch Semikolons getrennt. Das L-System kann Arrays verarbeiten. Auf einzelne Felder kann auf die selbe Weise wie in der Programmiersprache C zugegriffen werden. Die Liste der Produktionen ist geordnet. Im deterministischen Fall wird die erste pas- sende Funktion ausgeführt. Dabei werden die Produktionen, wenn nicht anders ange- geben, von oben nach unten geprüft. Im stochastischen Fall bleibt alles beim Alten. Das folgende, umfassende Open L-System modelliert das Wachstum einer Wurzel. Haupt- aufgabe einer Wurzel ist das Beschaffen von Nährstoffen für die Pflanze. Durch das Aufsaugen von Wasser wird aber lokal die Wasserkonzentration im Boden vermindert, was Wasser- bewegungen im Boden verursachen kann (von wasserreichen zu entleerten Regionen). Währenddessen wachsen die Spitzen der Wurzel mehr oder weniger dem Gradienten der Abbildung 2.9: (3D-)Umgebungssensitives L-System. Links: Ein Skelett aus Linien und Ellipsoiden definiert eine implitzite Oberfläche. Rechts: Inner- halb dieser Oberfläche gewachsene Pflanzenstruktur.
Transcript
Page 1: Master thesis pascal_mueller02

16 2. LINDENMAYER-SYSTEME

wurden eindrückliche Szenarios geschaffen (Abbildung 2.9). Natürlich wurden in diesenBeispielen auch stochastische Verhaltensweisen in die Simulationen miteinbezogen.

Dieses Beispiel führt vor, dass man zuerst intensiv die Eigenschaften eines Objektesstudieren muss, bevor man es mit einem L-System simuliert. Die entsprechenden Regeln zufinden kann ziemlich anspruchsvoll und aufwendig sein, wie die vielen Beispiele unter-schiedlichster Pflanzenarten aus Lindenmayers und Prusinkiewicz’ Arbeiten zeigen.

2.7 Open L-Systems

Interaktion mit der Umgebung ist ein wichtiger Aspekt in der Entwicklung von Pflanzen.Während in umgebungssensitiven L-Systemen nur die Reaktion der Pflanze auf ihre Umgebungsimuliert wird, sind Open L-Systems in der Lage, beidseitige Kommunikation zu modellieren.Das bedeuted, die Pflanze kann nun auch Änderungen in der Umgebung bewirken. Deshalbwurden die Query-Module zu Kommunikations-Modulen der Form ?E(x1, x2, ... , xn) erweitert.Die Parameter x1, x2, ... , xn senden und empfangen Information der Umgebung. Zusätzlich wirdder Umgebung immer der Status der Turtle (Position und Orientierung) mitgeliefert, d.h. diesmuss nun nicht mehr explizit angegeben werden.

Je grösser das Gleichungssystem zur Definition eines L-Systems wird, desto unüber-sichtlicher wird dieses. Deshalb wurden weitere Konstrukte eingeführt:

• Produktionen können Zuweisungsstatements für lokale Variablen beinhalten. DieseZuweisungen sind in geschweiften Klammern und durch Semikolons getrennt.

• Das L-System kann Arrays verarbeiten. Auf einzelne Felder kann auf die selbe Weisewie in der Programmiersprache C zugegriffen werden.

• Die Liste der Produktionen ist geordnet. Im deterministischen Fall wird die erste pas-sende Funktion ausgeführt. Dabei werden die Produktionen, wenn nicht anders ange-geben, von oben nach unten geprüft. Im stochastischen Fall bleibt alles beim Alten.

Das folgende, umfassende Open L-System modelliert das Wachstum einer Wurzel. Haupt-aufgabe einer Wurzel ist das Beschaffen von Nährstoffen für die Pflanze. Durch das Aufsaugenvon Wasser wird aber lokal die Wasserkonzentration im Boden vermindert, was Wasser-bewegungen im Boden verursachen kann (von wasserreichen zu entleerten Regionen).Währenddessen wachsen die Spitzen der Wurzel mehr oder weniger dem Gradienten der

Abbildung 2.9: (3D-)Umgebungssensitives L-System. Links: Ein Skelett aus Linienund Ellipsoiden definiert eine implitzite Oberfläche. Rechts: Inner-halb dieser Oberfläche gewachsene Pflanzenstruktur.

Page 2: Master thesis pascal_mueller02

2.7 OPEN L-SYSTEMS 17

Wasserkonzentration entgegen, den sie durch ihre Aktivitäten verändert haben. Es finden alsokomplexe Interaktionen zwischen Wurzel und Boden statt. Das Modell beschränkt sich wiederauf 2D. Zuerst werden die Funktionen der Kommunikations-Module erklärt, dann das Umge-bungsmodell (der Boden) und anschliessend das Open L-System, das die Wurzel simuliert.

Kommunikations-Spezifikation: Die Pflanze interagiert mit der Umgebung mit Kommuni-kations-Modulen der Form ?E(c, θ), die in den Spitzen des Wurzelsystems zu finden sind. DerParameter c repräsentiert die gewünschte (optimale) Menge Wasser, die die Spitze aufnehmenmöchte, und der Wert θ gewichtet den Einfluss des Gradienten auf die Richtung, in der dieWurzelspitze wachsen soll. Hat die Umgebung die eingegangenen Daten verarbeitet, sendet siemit c die tatsächliche Wassermenge, die die Wurzelspitze erhalten kann, und θ ist nun einWinkel und beschreibt die Wachstumsrichtung.

Umgebungsmodell: Die Umgebung ist ein Feld C vonWasserkonzentrationen, repräsentiert durch ein Array mitjeweils der Menge Wasser pro Volumeneinheit. Die Wasser-bewegungen im Boden folgen den Gesetzen der Diffusionund werden mittels finiten Differenzen numerisch berechnet.Auf eine Anfrage einer Wurzelspitze mit Position (i, j) nachWasser reagiert die Umgebung folgendermassen: Der neueWert für c, also die Menge Wasser, die die Wurzelspitzeerhalten kann, wird bestimmt, indem man die gewünschte (cin)mit der an dieser Stelle verfügbare Menge Wasser vergleichtund den kleineren Wert auswählt. Anschliessend wird dieWasserkonzentration an der abgetasteten Position um diesenWert dekrementiert. Der zweite Parameter θ des Kommunikations-Moduls, die Richtung, inwelche die Wurzelspitze weiterwachsen soll, wird berechnet wie in Abildung 2.10 dargestellt:Der Vektor T ist eine lineare Kombination des Vektors H, welcher Position und Richtung derTurtle repräsentiert, und des mit θin gewichteten Vektors ∇C, des Gradienten derWasserkonzentrationen. θout ist dann der Winkel zwischen den Vektoren T und H.

Wurzelmodell: Das Open L-System benutzt Arrays, um so unterschiedliche Parameterwertefür die drei verschiedenen Verzweigungstiefen zu lesen. Diese Parameterwerte basieren aufBiologie-Arbeiten über Wurzeln.

#define N 3 /* max. branching order + 1 */Define: { arrayReq[N] = {0.1, 0.4, 0.05}, /* requested nutrient intake */MinReq[N] = {0.01, 0.06, 0.01}, /* minimum nutrient intake */ElRate[N] = {0.55, 0.25, 0.55}, /* maximum elongation rate */MaxLen[N] = {200, 5, 0.8}, /* maximum branch length */Sens[N] = {10, 0, 0}, /* sensitivity to gradient */Dev[N] = {30, 75, 75}, /* deviation in heading */Del[N-1] = {30, 60}, /* delay in branch growth */BrAngle[N-1] = {90, 90}, /* branching angle */BrSpace[N-1] = {1, 0.5}, /* distance between branches */}ω : A(0,0,0) ?E(Req[0],Sens[0])p1 : A(n,s,b) > ?E(c,θ) : (s > MaxLen[n]) || (c < MinReq[n]) → εp2 : A(n,s,b) > ?E(c,θ) :

(n ≥ N-1) || (b < BrSpace[n]) {h = c/Req[n]·ElRate[n];}→ +(nran(θ,Dev[n])) F(h) A(n,s+b,b+h) ?E(Req[n],Sens[n])

Abbildung 2.10:Definition von θout.

Page 3: Master thesis pascal_mueller02

18 2. LINDENMAYER-SYSTEME

p3 : A(n,s,b) > ?E(c,θ) :(n < N-1) && (b ≥ BrSpace[n]) {h = c/Req[n]·ElRate[n];}→ +(nran(θ,Dev[n])) B(n,0) F(h)

/(180) A(n,s+h,h) ?E(Req[n],Sens[n])p4 : B(n,t) : t < Del[n] → B(n,t+1)p5 : B(n,t) : t ≥ Del[n]

→ [ +(BrAngle[n]) A(n+1,0,0) ?E(Req[n+1],Sens[n+1]) ]p6 : ?E(c,θ) → ε

Die Entwicklung startet mit einem Apex A, gefolgt von einem Kommunikations-Modul ?E. DieParameter vom Apex repräsentieren die Verzweigungstiefe, die momentane Länge dieserAchse und die Distanz zum letzten Verzweigungspunkt. Im den folgenden Abschnitten werdendie Produktionen p1 bis p3 illustriert, die das mögliche Schicksal eines Apex’ beschreiben.

Überschreitet die Länge s einer Achse mit Verzweigungstiefe n den vordefiniertenMaximumwert MaxLen[n], oder reicht die erhaltene Menge Wasser c nicht mehr aus (d.h. liegtunter dem Minimum MinReq[n]), stirbt der Apex ab und die Wurzelspitze wächst nicht mehrweiter (Produktion p1).

Ist die Verzweigunstiefe n gleich der maximalen Verzweigungstiefe N-1, oder die Distanzb zur letzten Verzweigung kleiner als die Schwelle BrSpace[n], generiert der Apex ein neuesWurzelsegment F (Produktion p2). Die Länge h von F wird berechnet, indem man das Ver-längerungsinkrement ElRate[n] mit dem Verhältnis zwischen erhaltener (c) und gewünschter(Req[n]) Menge Wasser multipliziert. Zuvor wird die Turtle um den Winkel nran(q,Dev[n])gedreht, wobei nran ein Zufallszahlengenerator mit Normalverteilung ist. Die Standardab-weichung Dev[n] simuliert andere Einflüsse auf die Wachstumsrichtung der Wurzelspitze, diein diesem Modell nicht berücksichtigt wurden.

Ist die Verzweigunstiefe n kleiner als die maximalen Verzweigungstiefe N-1, und die Dis-tanz b zur letzten Verzweigung gleich oder grösser als der Schwellwert BrSpace[n], so trittProduktion p3 in Kraft, welche eine neue Verzweigung B generiert. Alles weitere läuft wie in p2

ab.

Produktion p4 modelliert die Verzögerung von Del[n] Ersetzungschritten. Danach wird eineneueVerzweigung mit Apex und Kommunikations-Modul eingefügt (p5). Die letzte Produktionp6 ist dafür zuständig, die (oben gebrauchten) Kommunikations-Module zu löschen.

Abbildung 2.11: 2D-Modell einer Wurzel, die mit dem Wasser im Boden interagiert.Die Hintergrundfarben illustrieren die Wasserkonzentrationen(Blau: hoch, Schwarz: tief).

Page 4: Master thesis pascal_mueller02

2.7 OPEN L-SYSTEMS 19

Das Resultat der Simulation ist in Bild 2.11 dargestellt. Die Spitze der Hauptachse (Ver-zweigungstiefe 0) folgt, mit kleinen, zufälligen Abweichungen, dem Gradienten derWasserkonzentrationen. Die Äste der höheren Verzweigungsebenen sind auf den Gradientennicht sensitiv und haben eine grössere Standardabweichung. Durch die Wasseraufnahme derWurzelspitzen werden lokale Regionen völlig entleert und können auch nicht mehr durch Dif-fusion (aus wasserreichen Regionen) aufgefüllt werden. Als Folge dieser tiefen Wasser-konzentrationen stoppt das Wachstum einiger Wurzelverzweigungen, noch bevor diese ihrevolle Länge erreicht haben. Bild 2.12 zeigt eine dreidimensionale Erweiterung des vorher-gehenden Modells. Das linke Bild illustriert den Kampf zweier Wurzel um Wasser, was auchder Grund ist, weshalb die beiden sich immer mehr von einander entfernen. Rechts wachsen dieWurzeln langsamer, der Einflussbereich von jedem Wurzelsystem ist kleiner und die Haupt-achsen sind näher zusammen. Diese 2 Wurzelsysteme interagieren miteinander und benützenzur Kommunikation die Umgebung bzw. den Boden als Medium.

Abbildung 2.12: Dreidimensionale Version des Wurzel-Modells. Wasserkonzentra-tionen werden durch halb-transparente Iso-Oberflächen dargestellt.

Page 5: Master thesis pascal_mueller02

20 2. LINDENMAYER-SYSTEME

Page 6: Master thesis pascal_mueller02

21

3System Architektur

Das CityEngine System ist die Implementation der in Abbildung 3.1 dargestellten Pipeline: Imersten Schritt werden die Eingabebilder in die CityEngine eingelesen, und ein für diese Zweckeerweitertes L-System generiert daraus ein Strassennetzwerk. Dieses kann mit dem Strassen-editor nachträglich verändert werden. Dann werden die Räume zwischen den Strassen inGrundrisse (Allotments) unterteilt, auf welchen die Gebäude platziert werden. Im viertenSchritt werden durch ein zweites L-System den Gebäudegrundrissen entsprechende ShapeGrammar Strings generiert. Im letzten Schritt werden die Strings, welche die Formen derGebäude beschreiben, interpretiert und als texturierte Geometrie ausgegeben. Die Geometrie-daten der virtuellen Stadt können schliesslich mit einem 3D-Renderer visualisiert werden.

Abbildung 3.1: Die Pipeline der CityEngine. Die eingerahmten Boxen repräsen-tieren die Daten, welche die Tools in den schwarzen Boxen als Inputrespektive Output haben.

Page 7: Master thesis pascal_mueller02

22 3. SYSTEM ARCHITEKTUR

Die Eingabedaten, welche aus Graustufenbildern und Parametern bestehen, sind verant-wortlich für das Verhalten des gesamten Systems, also für das Aussehen der resultierenden vir-tuellen Stadt. Die Eingabebilder können durch Zeichnen oder Scannen von topographischenund statistischen Karten (wie in [9]) erstellt werden. Die Inputs lassen sich in folgende Kate-gorien unterteilen:

• Topographische Karten: Wasser/Land, Vegetation (Parks), Elevation

• Soziostatistische Karten: Populationsdichte, Landnutzung, Alter

• Kontrollbilder: Strassenmuster

Die ersten beiden Eingabebilder, Wasser/Land und Vegetation, werden binär interpretiert. DieLandnutzungskarte unterscheidet zwischen Residential, Commercial oder Industrial. Den rest-lichen Bildern können Skalierungswerte und Offsets übergeben werden. Abbildung 3.2 (linksoben) zeigt von jeder Kategorie ein Eingabebild. Die Eingabeparameter können aus statis-tischen Datensammlungen entnommen oder abgeleitet werden. In [16] finden sich beispiels-weise Angaben zur Anzahl Kreuzungen pro Fläche, woraus die durchschnittliche Strassenlängeberechnet werden kann, welche ein Parameter der CityEngine ist. Die Parameter können jeder-zeit interaktiv verändert werden, wodurch das Verhalten des Systems beeinflusst werden kann.

Ein erweitertes L-System, dessen Verhalten hierarchisch kontrolliert werden kann, generiertdie Strassennetzwerke. Auf einer globalen Ebene des L-Systems, kann das Strassenmusterbestimmt werden (durch die Rules und deren Kontrollbilder), und auf einer lokalen Ebene kannbeispielsweise bestimmt werden, wieviele Strassen maximal in einer Kreuzung münden. DerL-System Mechanismus wurde so erweitert, dass das Einbinden beliebig vieler Strassenmusteroder das Ändern von Parametern keine Modifikation der Produktionsregeln erfordert. Einezusätzliche Erweiterung zu bestehenden L-Systemen wurde entwickelt, um Zyklen undIntersektionen im generierten Strassennetzwerk zu erkennen (selbstsensitive L-Systeme).

Die Populationsdichte einer Stadt wird beeinflusst durch den Bau von Strassen [10]. Dieinverse Interpretation dieser Tatsache benutzt das L-System um die Strassen zu kreieren. Nach[10], ändern aber nicht alle Strassen die Population in ihrer lokalen Umgebung (Beispiel: eineStrasse die zwei Städte miteinander verbindet). Deshalb verwendet das L-System zwei Artenvon Strassen: Highways und Streets. Diese unterscheiden sich durch Funktion und Verhalten.Die Highways verbinden Regionen mit hoher Populationsdichte global, indem sie das Eingabe-bild absuchen. Die Streets bedecken, abhängig von der Populationsdichte, die Flächen zwischenden Highways, so dass der Zugang zu den Highways stets sichergestellt ist. Diese beiden Stras-sentypen zusammen bilden das Strassennetzwerk der virutellen Stadt (Abbildung 3.2 linksunten).

Ist das Strassennetzwerk kreiert, werden die Zwischenräume mit einem geometrischen Par-zellierungsalgorithmus in Allotments unterteilt. Auf den Grundrissen werden stochastische,parametrische L-Systeme ausgeführt, die die entsprechenden Shape Grammar Strings gene-rieren. Mit der CityEngine Shape Grammar kann die Form der Gebäude beschrieben werden.Der Benutzer programmiert diese L-Systeme und überwacht deren Verteilung. Dadurch kann erden Stil der Bauten in der virtuellen Stadt spezifizieren. Die Programmierung der L-Systemefällt leicht, da die CityEngine Shape Grammar für derartige L-Systeme entworfen wurde.

Der 3D-Interpreter, welcher die Strings parst, erzeugt Polygon-Geometrien mit Textur-kooridnaten, welche sich entweder für prozedurale Shader eignen oder planares Mappingerlauben. Die Geometriedaten können anschliessend in Alias¦Wavefronts Maya eingelesen wer-den. In Maya können den Geometrien Shader zugewiesen, eine Umgebung kann integriert unddie Stadt kann visualisiert werden (siehe Abbildung 3.2 rechts).

Page 8: Master thesis pascal_mueller02

23

Abbildung 3.2: Mit der CityEngine generierte virtuelle Stadt. Links oben: Drei derEingabebilder (Elevation, Populationsdichte und Rule Kontrollbild).Links unten: Generiertes Strassennetz. Rechts: Gerenderte Geometrie.

Page 9: Master thesis pascal_mueller02

24 3. SYSTEM ARCHITEKTUR

Page 10: Master thesis pascal_mueller02

25

4Erzeugung derStrassennetzwerke

4.1 Das erweiterte L-System

Um ein Strassennetzwerk zu generieren, wird ein kompliziertes L-System Regelwerk mit einergrossen Zahl von Parametern und Konditionen benötigt. Die Anzahl der Produktionen steigtrasch, und falls man neue Regeln implementieren will, müssen viele der bestehenden Produ-ktionen neu angepasst werden. Je grösser das L-System wird, desto unübersichtlicher undunflexibler wird es. Das L-System der CityEngine hat deshalb bloss noch eine ausführendeRolle, das heisst, es übernimmt nur noch die Produktion der Module. Das Bestimmen derParameter wird von externen Funktionen kontrolliert. Das L-System ist ideal geeignet, um dieseexternen Funktionen hierarchisch zu ordnen.

Da das L-System nur ein Template generiert und die Parameter nicht durch das L-Systembestimmt werden, sind fast keine konditionalen Produktionen nötig. Dadurch wiederum wirdinnerhalb der Module die Anzahl der Parameter, die für das L-System sichtbar sein müssen,reduziert. Es resultiert ein sehr übersichtliches L-System, das nur noch die für die Wachstums-steuerung nötigen Komponenten beinhaltet (im Sinne von Datenstrukturen). Das generischeTemplate, welches immer drei Strassenverzweigungen erzeugt, wird Ideal Successor genannt.Die Erzeugung einer Strasse in diesem L-System durchläuft folgende Phasen (siehe auchAbbildung 4.1):

1. Initiert werden neue Strassen durch den Ideal Successor. Dessen drei Verzweigungenbestehen aus Modulen, die je eine Strasse symbolisieren. Den Parametern dieserModule werden keine Werte zugewiesen.

2. Die externe Funktion globalGoals wird aufgerufen. Diese bestimmt die Parameter-werte der in Punkt 1 erwähnten Module. Mit dieser Funktion kann das Verhalten einerStrasse bezüglich ihres Wachstums auf einer globalen Ebene kontrolliert werden.

3. Die externe Funktion localConstraints wird aufgerufen. Die in Punkt 2 vorge-schlagenen Parameter werden von dieser Funktion überprüft. Falls die Strasse nicht indie lokale Umgebungssituation passt, wird versucht, deren Parameter entsprechend zujustieren. Ist es aus umgebungsbedingten Gründen unmöglich eine Strasse im Systemeinzufügen, wird sie von dieser Funktion verworfen.

Page 11: Master thesis pascal_mueller02

26 4. ERZEUGUNG DER STRASSENNETZWERKE

Die Funktion globalGoals bewirkt, dass die Strassen einem globalen Muster folgen, und dieFunktion localConstraints implementiert den umgebungssensitiven Teil eines L-Systems.Durch diese beiden Funktionen wird das Verhalten des L-Systems vollständig kontrolliert.Deshalb kann die Funktionalität des L-Systems erweitert werden, ohne dass die Produktionenverändert werden müssen. Das Regelwerk des L-Systems, das die Strassennetzwerke erzeugt,sieht folgendermassen aus:

ω : R(0,initialRuleAttr) ?I(initRoadAttr,UNASSIGNED)

p1 : R(del,ruleAttr) < ?I(roadAttr,state) : del < 0 → εp2 : ?I(roadAttr,state) : state == UNASSIGNED

{localConstraints(roadAttr) adjusts the parameters for: state, roadAttr}→ ?I(roadAttr, state)

p3 : ?I(roadAttr,state) : state != UNASSIGNED → ε

p4 : R(del, ruleAttr) : del < 0 → εp5 : R(del, ruleAttr) > ?I(roadAttr,state) : state == SUCCEED

{globalGoals(ruleAttr,roadAttr) creates the parametersfor: pDel[0-2], pRuleAttr[0-2], pRoadAttr[0-2]}

→ +(roadAttr.angle) F(roadAttr.length) B(pDel[1],pRuleAttr[1],pRoadAttr[1]) B(pDel[2],pRuleAttr[2],pRoadAttr[2]) R(pDel[0],pRuleAttr[0]) ?I(pRoadAttr[0],UNASSIGNED)

p6 : R(del, ruleAttr) > ?I(roadAttr, state) : state == FAILED → ε

p7 : B(del, ruleAttr, roadAttr) : del > 0 → B(del-1,ruleAttr,roadAttr)p8 : B(del, ruleAttr, roadAttr) : del == 0

→ [ R(del, ruleAttr) ?I(roadAttr,UNASSIGNED) ]p9 : B(del,ruleAttr,roadAttr) : del < 0 → ε

Das Axiom ω initialisiert das System mit einem Rule Modul R, gefolgt von einem InsertionQuery Modul ?I. Diese beiden Module treten im L-System immer zusammen auf und repräsen-tieren eine Strasse. Der Parameter del des Rule Moduls bestimmt, ob eine Strasse exisitiert(del ≥ 0) und ruleAttr ist eine Sammlung von Parametern, die den Rules zum Übergeben vonWerten dienen. Reichen also für die Programmierung einer Rule die lokalen Informationen unddie Strassenparameter nicht, kann ruleAttr ein neues Element hinzugefügt werden. Mit demInsertion Modul können, unabhängig vom Rule Modul, die Local Constraints überprüft werden.Der Eintrag roadAttr, welcher wie ruleAttr eine Sammlung von Parameter ist, beschreibt eine

Abbildung 4.1: Die Erzeugung einer Strasse. Die Bestimmung der Parameterwertefolgt hierarchischen Funktionen.

Page 12: Master thesis pascal_mueller02

4.2 GLOBAL GOALS 27

Strasse mit Parametern wie Winkel, Länge, Typ etc. Der Parameter state dient als Kontroll-element.

Die ersten drei Produktionen kontrollieren das Insertion Modul. Falls eine Strasse gar nichtexistiert (Parameter del des im Kontext stehenden R Moduls kleiner als Null), tritt Produktionp1 in Kraft, und das zugehörige Insertion Module wird gelöscht. Produktion p2 ruft die local-Constraints Überprüfung auf. Diese benötigt als Eingabewert die Strassenparameter (roadAttr),welche überprüft, und falls nötig, geändert werden. Als Rückgabewert erhält man neben den(evtl. angepassten) Strassenparametern die Variable state. Wenn die Strasse erfolgreich in derUmgebung eingefügt werden konnte, wird state auf SUCCESS gestetzt, andernfalls auf-FAILED. Produktion p3 sorgt aus folgendem Grund dafür, dass ein Insertion Modul nur zweiErsetzungsschritte lang existiert: wurde die localConstraints Überprüfung durchgeführt (d.h.state != UNASSIGNED), werden die Werte in Produktion p5 aus dem Kontext gelesen, und dasInsertion Modul wird nicht mehr benötigt.

Die Produktionen p4 - p6 behandeln das Rule Modul. Existiert eine Strasse nicht (del < 0),wird diese durch die Produktion p4 gelöscht. Produktion p5 repräsentiert das Template desL-Systems, das für das Wachstum verantwortlich ist. Das Template fügt die von den Local Con-straints überprüfte Strasse ein (da state den Wert SUCCESS hat) und erzeugt drei neue Strassen:zwei Verzweigungen und eine Strasse “geradeaus”. Die Parameter der neuen Strassen werdenvon globalGoals (also den Rules) bestimmt: Als Eingabewert werden die Parameter dererzeugten Strasse (roadAttr) und ruleAttr benötigt. Als Rückgabewert erhält man drei neueStrassen in Form von Arrays (pDel[0-2], pRuleAttr[0-2] und pRoadAttr[0-2]). Durch das Tem-plate werden diese drei Strassen (respektive deren Module) in jedem Fall eingefügt. Dies erklärtauch den Sinn der Produktionen p1 und p4, welche die Module löschen, falls die Funktion glo-balGoals gar keine Strasse vorgeschlagen hat (pDel[0] < 0). Produktion p6 löscht das R Modul,falls die localConstraints Überprüfung negativ ausfiel.

Die letzten drei Produktionen kontrollieren das Branch Modul B. Dieses Modul verzögertden Start des Wachstums einer Verzweigung, indem der Parameter del heruntergezählt wird(Produktion p7). Ist del gleich Null, tritt Produktion p8 in Kraft. Diese Produktion initiert eineneue Verzweigung mit den im Branch Modul gespeicherten Parametern ruleAttr und roadAttr.Wie beim Rule Modul, wird auch hier der Parameter del (zusätzlich) zur Überprüfung der Exis-tenz einer Strasse verwendet (Produktion p9): falls del < 0 ist, wird die Verzweigung nicht ini-tiert.

4.2 Global Goals

Die Funktion globalGoals setzt die Initialwerte der Strassenmodule, indem alle aktiven Rulesaufgerufen werden. Die Vorschläge jeder Rule werden entsprechend den Gewichten der Rulesin einem einzelnen Vorschlag vereinigt. Das Gewicht bzw. der Einfluss einer Rule wird über ihrKontrollbild bestimmt. Mit einer Rule kann das Erscheinungsbild eines Strassennetzwerkeskontrolliert werden, indem sich die Strassen dem von der Rule implementierten Strassenmusteranpassen. Abbildung 4.2 zeigt mögliche Strassenmuster (aus [7]). Eine Rule schlägt maximaldrei neue Strassen für das Template vor: Eine Strasse ungefähr geradeaus, eine Strasse ungefährnach links und eine Strasse ungefähr nach rechts.

4.2.1 Western Rule

In [10], kategorisiert Füsser Strassen in zwei Klassen: Hauptstrassen (Highways) und siedlungs-orientierte Nebenstrassen (Streets). Ausserdem vergleicht er das Auftreten von rasterartigenMustern mit dem von radialen Mustern: Erstere treten vor allem in polyzentrischen Städten auf

Page 13: Master thesis pascal_mueller02

28 4. ERZEUGUNG DER STRASSENNETZWERKE

und radiale Muster findet man eher in monozentrischen Städten. Highways können beide Artenvon Mustern repräsentieren, Streets hingegen treten nur in raster- bzw. schachbrettförmigenStrassenmustern auf. Deshalb bestehen die Strassennetze solcher Städte aus verschiedensten,beliebig zueinander angeordneten Schachbrettmustern mit unterschiedlichen Häuserblock-flächen. Die Grenzen zwischen diesen Mustern bilden Highways, die die Gleichförmigkeit derMuster unterbrechen [16]. Die Western Rule erzeugt derartige Strassenmuster.

Wie weiter oben bereits erwähnt, verbinden die Highways Zentren hoher Populationsdichtemiteinander. Die Western Rule korrigiert den Winkel eines Highway so, dass dieser der gröss-ten Populationsdichte folgt. Die Western Rule bestimmt diese Richtung, indem innerhalb desbenutzerdefinierten Bereiches Strahlen mit zufällig geänderten Winkeln die ideale Routesuchen. Entlang dieser Strahlen wird die Populationsdichte abgetastet. Jeder Wert wird mit derinversen Distanz gewichtet und aufsummiert. Die Richtung mit der grössten Summe wirdschlussendlich vom Highway eingeschlagen. Abbildung 4.3 illustriert den Vorgang. Findet einereine Highway-Verzweigung statt, wird dieser ein Wert mitgegeben (ruleAttr.branchDistance),der die Distanz bis zur nächsten Verzweigungen darstellt (gleich wie im L-System für die Wur-zeln in 2.7). Der Benutzer definiert sämtliche Parameter wie Längen, Winkel oder Wahrschein-lichkeiten (alle mit Standardabweichung).

Im Gegensatz zu den Highways folgen Streets nicht der grössten Populationsdichte, sonderneinem Schachbrettmuster. Dieses wird durch Highways initiert, die nach links oder rechts eineStreet-Verzweigung produziert haben. Dabei wird die Länge der Street und die Blockfläche desSchachbrettmusters (ruleAttr.area) bestimmt und für das L-System wird eine Verzögerungbestimmt, damit die Highways zuerst ihre Gebiete erschliessen können. Durch eine Länge unddie Fläche ist das Aussehen des Schachbrettmusters festgelegt, und, nachdem der Delay runt-ergezählt wurde, beginnt das Schachbrettmuster zu wachsen. Der Benutzer kann bestimmen,wie regelmässig dieses aussehen soll. Wird eine Street eingefügt, dekrementiert sie an dieserStelle die Population in einem Diffusionssystem mittels finiten Differenzen (gleich wie imL-System für die Wurzeln in 2.7). Sobald Streets auf Zonen ohne Population stossen, stoppt das

Abbildung 4.2: Eine Auswahl von möglichen Strassenmustern.

Abbildung 4.3: Links: Ein Strahl sucht die Richtung der höchsten Population.Rechts: Ein generiertes Highwaynetzwerk, das die Populations-zentren miteinander verbindet.

Page 14: Master thesis pascal_mueller02

4.2 GLOBAL GOALS 29

Wachstum. Alle oben erwähnten Parameter kann der User kontrollieren. Abbildung 4.4 zeigtlinks den Strassenplan von San Francisco, auf dem zwei aufeinandertreffende Schachbrett-muster dargestellt sind. Rechts in der Abbildung wird ein mit der Western Rule generiertesStrassennetz gezeigt.

4.2.2 Grid Rule

Über die mit der Western Rule erzeugten Schachbrettmuster der Streets hat der Benutzer wenigKontrolle, zumindest was deren Orientierung betrifft. Deshalb wurde die Grid Rule implemen-tiert. Highways und Streets verhalten sich hier nur noch nach geometrischen Regeln. DerBenutzer hat Kontrolle über das Schachbrett, indem er Position, Orientierung und Strassen-längen mit Standardabweichungen eingeben kann. Sind diesen Parametern Werte zugewiesen,wird das Gitter vollständig initialisiert. Die Strassen wachsen auf ähnliche Weise wie in derWestern Rule, nur gibt es keine Winkelabweichungen und die Strassenenden schnappen auf dieGitterpunkte ein. Abbildung 4.5 zeigt links das berühmte Strassennetz von Manhattan. Rechtsin der Abbildung sieht man eine mit der Grid Rule generierte Rekonstruktion dieses Strassen-netzwerkes.

4.2.3 Radial Rule

Neben der Grid Rule existiert noch eine zweite geometrische Rule: die Radial Rule. Diese Ruleerzeugt die in Abbildung 4.2 illustrierten radialen bzw. konzentrischen Strassenmuster. Solche

Abbildung 4.4: Western Rule. Links: Ein Strassennetzausschnitt von San Francisco.Rechts: Ein generiertes Strassennetz.

Abbildung 4.5: Grid Rule. Links: Ein Strassennetzauschnitt von Manhattan (NYC).Rechts: Ein generiertes Strassennetz (auch von Manhattan).

Page 15: Master thesis pascal_mueller02

30 4. ERZEUGUNG DER STRASSENNETZWERKE

Strassenmuster sind vor allem in europäischen Städten zu finden (Paris, Brüssel). Dieses Stras-senmuster hat ähnliche Charakteristika wie das der Western Rule. Auch hier werden die schach-brettartigen verteilten Streets von den Highways unterbrochen [10]. Aus diesem Grundverhalten sich die Streets in dieser Rule gleich wie diejenigen der Western Rule. Die Highwayswerden, je nachdem wie ihr Winkel zum Zentrum ist, entweder in tangentiale oder radiale Rich-tung gelenkt. Das Zentrum der Ringstrassen wird vom Benutzer definiert. Abbildung 4.6 zeigtlinks einen Strassenplan des Zentrums von Paris, rechts ein mit der Radial Rule erzeugtesStrassennetzwerk.

4.2.4 Topographical Rule

Die Strassenmuster von europäischen Städten reflektieren oft deren Topographie, indem diegrösseren Strassen den Höhenlinien folgen [16]. Diese Eigenschaft wird mit der TopographicalRule simuliert, die wie die beiden geometrischen Rules auf der Western Rule basiert. Die High-ways und die längeren Streets eines Schachbrettmusters folgen der geringsten Steigung. Kür-zere Streets eines Schachbrettmusters folgen der grössten Steigung, falls diese nicht zu steil ist.Ein weiterer Unterschied zu Western Rule besteht darin, dass Highways, wenn sie sich ver-zweigen, meistens nur eine anstatt zwei Verzweigungen generieren. Das topographische Ver-halten wird an einer Position erst aktiviert, wenn eine minimale Steigung im Gelände vorhandenist (und das Kontrollbild aktiv ist). Ist die Steigung in diesem Punkt kleiner als der vomBenutzer definierte Schellwert, verhält sich die Topographical Rule gleich wie die WesternRule. Abbildung 4.7 zeigt links das Strassennetzwerk von Zürich (aus [16]), indem anhand derStrassen erkennt werden kann, wie das Gelände rechts neben dem Fluss aufsteigt. Rechts inAbbildung 4.7 ist Strassennetzwerk abgebildet, das nur mit der Topographical Rule erzeugtwurde. Man kann deutlich erkennen wie in den flacheren Regionen das Western Rule Verhaltenaktiv war.

4.2.5 Blending

Falls an einer Position mehrere Rules aktiv sind (Kontrollbildwert > 0), werden zuerst alleaktiven Rules einzeln ausgewertet. Die vorgeschlagenen Parameter der Rules werden anschlies-send entsprechend ihrem Kontrollbildwert gewichtet und aufsummiert. Der folgendePseudocode illustriert das Blending der Rules:

Abbildung 4.6: Radial Rule. Links: Ein Strassennetzausschnitt von Paris. Rechts:Ein generiertes Strassennetz.

Page 16: Master thesis pascal_mueller02

4.2 GLOBAL GOALS 31

// 1. Which branches in template exist?foreach Branch

w = 0foreach Rule

if rule.branch existsw += rule.w

elsew -= rule.w

if w > 0branch exists

// 2. Is it a Highway or a Street?foreach Branch which exists

wHighway = wStreet = 0foreach Rule

if rule.branch existsif rule.branch.type == “HIGHWAY”

wHighway += rule.welse

wStreet += rule.wif wHighway > wStreet

branch.wSum = wHighwaybranch.type = “HIGHWAY”

elsebranch.wSum = wStreetbranch.type = “STREET”

// 3. Blend the rulesforeach Branch which exists

branch.par = {0,..,0}foreach Rule

if rule.branch exists && rule.branch.type == branch.typebranch.par += rule.branch.par * rule.w / branch.wSum

Im ersten Teil des Codes wird überprüft, welche der drei Branches, die das L-System Tem-plate zur Verfügung stellt, existieren (da eine Rule nicht immer alle drei Branches vorschlägt).Dies wird für jeden der drei Branches einzeln entschieden, indem das Gewicht (Kontrollbild-

Abbildung 4.7: Topographical Rule. Links: Ein Strassennetzausschnitt von Zürich.Rechts: Ein auf das Gelände projiziertes generiertes Strassennetz.

Page 17: Master thesis pascal_mueller02

32 4. ERZEUGUNG DER STRASSENNETZWERKE

wert) jeder aktiven Rule aufsummiert resp. subtrahiert wird. Ist der resultierende Wert grösserals Null, existiert der Branch.

Anschliessend wird für alle existierenden Branches überprüft, ob es sich um einen Highwayoder um eine Street handelt. Dies funktioniert ähnlich wie oben, nur werden hier zwei Gesamt-gewichte mitgeführt, da diese im dritten Teil, dem Blending, wiederverwendet werden.

Nachdem für jeden Branch bestimmt wurde, ob er existiert und welchen Strassentyp er hat,findet das Blending für jeden Branch statt (falls dieser existiert). Dabei haben nur noch die-jenigen Rules Einfluss, die einen Branch vorgeschlagen haben (rule.branch exists) und denentsprechenden Strassentyp unterstützen. Mit den im zweiten Teil berechneten Gesamtgewichtwerden (pro Branch) die vorgeschlagenen Parameter einer Strasse wie Winkel, Länge, etc.linear geblendet. Abbildung 4.8 zeigt ein Blending der beiden geometrischen Regeln.

4.3 Local Constraints

Die Strassenparameter, die die Funktion globalGoals vorgeschlagen hat, werden von der Funk-tion localConstraints entsprechend der lokalen Umgebung justiert. Wenn immer ein Spezialfallauftaucht, wenn beispielsweise eine Strasse auf Wasser trifft, wird dies durch den umgebungs-sensitiven Teil der Funktion erkannt, und falls möglich, werden die Parameter geändert.Anschliessend muss überprüft werden, ob die (evtl. justierte) Strasse auf eine Andere trifft undeine Kreuzung gebildet werden muss. Dazu wurden L-Systeme um die Fähigkeit erweitert,Intersektionen mit schon bestehenden Ästen zu erkennen. Es entstanden die selbstsensitivenL-Systeme. Die selbstsensitive Überprüfung, die immer nach der Umgebungssensitiven stat-tfindet, bestimmt die definitiven Parameter einer Strasse. Konnte die Strasse in die Umgebungeingefügt werden, wird dies via Parameter state des Insertion Moduls dem L-System mitgeteilt.

4.3.1 Umgebungssensitivität

Nachdem von den Rules eine Strasse vorgeschlagen wurde, passt die umgebungssensitive Über-prüfung die Strasse der lokalen Umgebung an. Bei einer einzufügenden Strasse liegt der Stras-senbeginn immer auf Land. Liegt das Strassenende im Wasser, in einem Park oder einer anderenillegalen Zone, wird versucht, die Strasse, bzw. deren Parameter, zu justieren:

• Die Länge der Strasse wird solange bis zu einem gewissen Faktor gekürzt, bis das Stras-senende in einer legalen Zone liegt.

Abbildung 4.8: Blending von Rules. Links oben das Kontrollbild der Grid-Rule,links unten das der Radial-Rule und rechts das resultierende Stras-sennetzwerk.

Page 18: Master thesis pascal_mueller02

4.3 LOCAL CONSTRAINTS 33

• Misslingt dies, wird versucht, den Winkel der Strasse (mit ihrer vorgeschlagenen Länge)solange bis zu einem Maximalwinkel zu verändern, bis das Strassenende in einer legalenZone liegt.

Diese Überprüfungen werden für Streets und Highways gleichermassen durchgeführt. Schlagenaber beide Versuche der Justierung fehl, werden die beiden Strassenarten unterschiedlichbehandelt: Streets werden verworfen, indem der Parameter state des Insertion Moduls aufFAILED gesetzt wird, womit die localConstraints Überprüfung beendet ist. Highways ist eshingegen erlaubt, Wasser zu überqueren und so Brücken zu bauen, indem durch Längen- undWinkeländerungen das andere Ufer gesucht wird. Falls dies gelingt, wird der Highway mar-kiert. Für Streets ist die umgebungssensitve Adjustierung nun abgeschlossen und die Strassemuss nur noch im selbstsensitiven Teil auf Kreuzungen untersucht werden. Die ersten beidenSpalten von Abbildung 4.9 illustrieren die Überprüfung

Da ein Highway oft einer Küste entlang verläuft [16], wird dieser, falls bisher keine Para-meteränderungen stattgefunden haben, zusätzlich überprüft:

• Befindet sich vor dem Strassenende Wasser, wird der Winkel des Highways in RichtungKüste geändert (obwohl sich der Highway auf legalem Gebiet befindet).

• War dies nicht der Fall und befindet sich neben dem Highway Wasser, wird der Winkelleicht in Richtung Wasser geändert (obwohl sich der Highway auf legalem Gebiet befin-det).

Die erste Überprüfung verhindert oft, dass Highways in Sackgassen enden. Jetzt können auchdie (evtl. justierten) Parameter eines Highways der selbstsensitiven Überprüfung übergebenwerden. Die beiden rechten Spalten von Abbildung 4.9 zeigen die Adjustierung der Highways.

4.3.2 Selbstsensitive L-Systeme

Da L-Systeme ursprünglich zur Generierung von Pflanzen entwickelt wurden, können mit denbestehenden L-Systemen nur verzweigende Strukturen erzeugt werden. Transport- oder Kom-munikationssysteme haben aber die Eigenschaft, dass sie zusammenwachsen und geschlosseneZyklen bilden (in einem Verkehrssystem beispielsweise sind Sackgassen die Ausnahme [7]).Deshalb wurden die selbstsensitiven L-Systeme entwickelt (ein ähnlicher Lösungsansatz wurdefür die prozedurale Generierung von Blutbahnen verwendet [19]): Eine neue Verzweigung kannauf ein Segment des schon bestehenden L-Systems treffen, die Kollision erkennen, sich“verbinden” und so einen Zyklus bilden. Dadurch ändert sich die Topologie von einer baum-artigen zu einer netzwerkartigen Struktur. Weil der Erzeugung vom Strassennetzwerk kein

Abbildung 4.9: Umgebungssensitives Einfügen von Strassen. Oberen Reihe: Vonden Rules vorgeschlagene Strassen. Untere Reihe: Nach der Adjus-tierung.


Recommended