70 9. SCHLUSSBEMERKUNGEN

Umgebung platziert, dann erfüllen die Kontrollmöglichkeiten durch die Regeln sicher dieErwartungen eines Benutzers. Aber, wie oben schon erwähnt, zur Planung von realen Städteneignet sich die Strassennetzwerke nur in der ersten Entwurfsphase.

Das grösste Problem bei der Entwicklung von Regeln ist, dass auf dem Gebiet der Städtepla-nung wenig entsprechende Modelle existieren oder aber diese nicht allgemeingültig sind.Deshalb mussten die Modelle, die die Zusammenhänge zwischen Strasse und Umgebungabstrahieren, zuerst entwickelt werden. Da in der Literatur natürlich keine statistische Werte fürdie Parameter dieser Modelle existieren, mussten diese hergeleitet werden.

9.1.2 Gebäudegenerierung

Die Shape Grammar wurde so entworfen, dass Gebäudeformen unabhängig von der Form deszugehörigen Grundrisses beschrieben werden können. Es existiert ein guter Mix aus einge-schränkten (relativen) Befehlen und unabhängigen (absoluten) Befehlen. Das Vokabular derCityEngine Shape Grammar kann in drei Klassen aufgeteilt werden: Turtle-, Grundriss- undGeometrie-Befehle. Obwohl dieses Vokabular der Shape Grammar sehr einfach gehaltenwurde, können erstaunlich viele bestehende Gebäude mit ihr beschrieben werden. L-Systemewurden zur Generierung der Shape Strings benutzt, weil diese sehr flexibel sind, da nachBelieben Module hinzugefügt oder entfernt werden können.

Der Entscheid, Geometrien im Maya Ascii Format (.ma) abzuspeichern, erwies sich alsungünstig. Obwohl dieses Format gleich wie das .obj-Format aufgebaut ist, dauert in Maya dasLaden einer .ma-Datei viel länger als das Laden einer.obj-Datei mit dem gleichen Inhalt.

9.1.3 Implementation

Die Kombination von C++ und Tcl/Tk erwies sich als gute Lösung: Die Implementation derCityEngine Pipeline ist einfach organisiert, das resultierende Programm läuft stabil und schnell,und das User Interface ist übersichtlich und intuitiv. Die modulare Struktur, welche in Imple-mentation und User Interface verwendet wird, ermöglicht eine unkomplizierte Weiterentwick-lung des Programms.

Das User Interface könnte im Bezug auf das Editieren der Regeln verbessert werden(beispielsweise das Positionieren eines Gitters durch die Maus) und das Arbeiten mit der City-Engine Shape Grammar müsste graphisch besser unterstützt werden (beispielsweise mit einemShape Grammar Modeler). Da sich die CityEngine in der Entwicklung befindet, sind die Para-meter nicht fest im System implementiert und auch nicht allzu benutzerfreundlich im UserInterface angeordnet.

9.2 Ausblick

9.2.1 Strassenetzwerkerzeugung

Möchte man noch andere Arten von Städten erzeugen, müssten weitere Rules gefunden werden.Will man beispielsweise kleinere Städte oder Vororte erzeugen, müsste dem erweiterten L-System die Residential Rule hinzugefügt werden. Diese generiert Strassennetze mit einer ver-zweigenden Struktur (siehe Abbildung 4.2) und die Verhaltensweise gleicht dem der Wurzelnin Kapitel 2.7.

Anstatt die Resultate mehrerer Rules durch lineare Gewichtung zu vereinigen, könnte diedominierende Rule durch Verhaltensmodelle (Inhibition, Level-Of-Interest) aus dem “Virtual-Reality”-Bereich Action Selection bestimmt werden [2].

9.2 AUSBLICK 71

Methoden der Verkehrsplanung und -analyse wie Transportsimulation könnten im L-Systembzw. in den Rules implementiert werden. Auf diese Weise könnten realistischere Strassen-netzwerke erzeugt werden.

9.2.2 Gebäudegenerierung

Neben den schon erwähnten möglichen Erweiterungen der Shape Grammar (eine Extrusion mitmehr Parametern), könnte der Shape Grammar eine neue Klasse von Befehlen hinzugefügt wer-den: die Material-Befehle. Der Interpreter wüsste immer, ob es sich nun um eine Fassade, einDach, einen Eingang oder eine Antenne handelt.

Um die Gebäude realistischer und besser kontrolliert zu generieren, könnte ein umgebungs-sensitives L-System benutzt werden. Die dreidimensionale Umgebung beinhaltet beispiels-weise Baugesetze wie das New Yorker Zoning Law, welches ab einer gewissen Höhe einegewisse Verjüngung der Gebäude verlangt (in [8]).

Eine total andere Methode der Generierung von Strings wäre folgende: Man definiere einenString eines Gebäudes dessen Stil gefällt. Da die Shape Strings eine verzweigende Strukturhaben, könnte der String, der Genotyp, nun mutiert werden [28].

Da die Gebäudegeometrien mit Shape Grammar Elementen zusammengesetzt wurde, eignetsich die Geometrie auch zur Darstellung in verschiedenen Level of Details. Abbildung 9.1 zeigtverschiedene ‘Level of Detail’-Auflösungsstufen eines Gebäudes.

Sehr schwierig zu rendern sind verglaste Fassaden, die nicht verspiegelt sind (z.B. Abend-dämmerung und in den Büros sind die Lichter an), da man das Interieur des Gebäudes erkennenkann. Benutzt man frontal aufgenommene Fotos als Texturen, fehlt die Tiefenwirkung. Deshalbkönnte ein Shader implementiert werden, der wie in Abbildung 9.2 frontale Interieuraufnahmenzweidimensional verzerrt, indem der Mittelpunkt im Texturraum verschoben wird.

Abbildung 9.1: Level of Detail: Links die simpelste Darstellung (Bounding Box) fürGebäude in weiter Entfernung zur Kamera. Nach rechts nimmt dieKomplexität der Geometrie zu, bzw. der Abstand zur Kamera ab.

Abbildung 9.2: Warping Facades. Die Textur (linkes Bild) dieses ebenen Polygonswurde durch Verschieben des Mittelpunkt verzerrt.

72 9. SCHLUSSBEMERKUNGEN

9.3 Danksagungen

Ich möchte mich bei folgenden Personen bedanken: Mein Betreuer Yoav ‘Yogi’ Parish, derimmer an mich geglaubt hat und mir stets freundschaftlich mit Rat und Tat zur Seite stand; Pro-fessor Markus Gross, dass ich die Diplomarbeit in seinem Institut durchführen durfte; meinerPraktikumsfirma Eyetronics, dass ich mir dort das programmiertechnische Knowhow aneignenkonnte um ein gesamtes Framework aufzustellen; Daniel Von Büren für seine Tcl/Tk Tipps;und Hanspeter Brunner und Christian Iten für die Mithilfe am Siggraph-Paper.

73

AImplementation

A.1 Programm-Design

Nachdem der Aufbau der Pipeline festgelegt war, wurde ein der Pipeline entsprechendes mod-ulares Programmkonzept gewählt. Es entstanden fünf Module namens Base, LSystem, Streets,Allotments und UI (siehe Abbildung A.1).

Die ersten vier Module sind hauptsächlich in C++ programmiert und jedes bildet eineLibrary. Im UI-Modul, das hauptsächlich in Tcl/Tk programmiert ist, befindet sich unteranderem der Source-Code (Main.c++) für das Executable der CityEngine. Diese Routine ist ver-antwortlich für die Kommunikation zwischen C++ und Tcl, welche über Wrapper vonstattengeht und folgendermassen funktioniert: Jedes Modul hat eine Klasse namens Wrapper.c++, inder die Wrapper definiert sind. Als Wrapper kann man eine Routine bezeichnen, die zwar in C++definiert wurde, aber auch von Tcl aufgerufen werden kann. In Main.c++ wird nun ein Tcl/TkInterpreter gestartet, sämtliche Wrapper-Aufrufe beim neuen Interpreter registriert und Main.tclgestartet. Letzteres kontrolliert den Aufbau von dem User-Interface. Sind die Wrapper-Aufrufeerst einmal registriert, können sie in Tcl wie jeder andere Tcl-Befehl verwendet werden

Die Organisation der Entwicklungsumgebung (im Ordner dev/) ist in Abbildung A.2 darges-tellt. In diesem Ordner befindet sich die Datei Makefile, welche die Makefiles der einzelnenModule aufruft (Kommandos: make all, make allclean, make base etc.) und ein Makefile-Tem-plate das von den Makefiles der Module importiert wird. Im Ordner bin/ befindet sich das Exe-cutable. Die Libraries der Module Base, LSystem, Streets und Allotments sind in lib/ zu finden.

Abbildung A.1: Das Programmdesign der CityEngine.

74 A. IMPLEMENTATION

Die beispielsweise vom Base-Modul erzeugten .o-Files werden in obj/base/ abgespeichert.Jedes Modul hat eine eigene Verzeichnisstruktur, indem sich wiederum ein Makefile befindet.In diesen Makefiles werden nur Variablen bestimmt und anschliessend wird Makefile_templateaufgerufen, das die Kompilierung und das Linken ausführt.

Die folgenden Abschnitte beschreiben kurz die wichtigsten Eigenschaften der verschiedenenModule. Details zur Implementation findet man im dokumentierten Sourcecode.

A.2 Das Modul Base

Das Modul Base enthält Tools und Datenstrukturen, die jedes Modul benutzt: Die Graphen-klasse, die Parameterverwaltung und das Image-Handling. Jedes der anderen Module linkt diesediese Library (libbase.a) dazu.

Die Klasse Graph bestitzt Methoden zum Lesen und Speichern des Graphen (siehe B.3),sowie Einfüge- und Löschoperationen für Punkte und Kanten. Für Kanten existiert eine Inter-section-Abfrage und für Punkte ist eine Nearest-Neighbour-Abfrage implementiert. Die Punkteund Kanten werden in Listen verwaltet, wobei die Liste der Kanten ungeordnet und die Listeder Punkte nach x-Koordinate sortiert ist (d.h. Reduktion vom zweidimensionalen Raum in deneindimensionalen Raum). Zusätzlich zur Punkteliste wird ein Bucketarray verwaltet. EinBucket zeigt auf den ersten Punkt in dem entsprechenden Bereich (falls ein Punkt vorhandenist). Beispiel: Man sucht den Punkt mit Koordinate (5634,3012). Bei einer Bucketlänge vonbeispielsweise 200 muss nun die Punkteliste ab dem Eintrag in Bucket[28] sequentiell durch-sucht werden. Die Bucket-Methode ist in jeder Hinsicht ideal, da Punkte sowohl schnelleingefügt, wie auch schnell gesucht werden können. Vor allem Range-Queries können gleichschnell wie die einfache Suche durchgeführt werden, was nur bei sehr komplexen räumlichenDatenstrukturen wie MX-Quadtrees oder Bit-Interleaving möglich wäre [17]. Da Kanten aufihre beiden Endpunkte zeigen und Punkte wiederum auf ihre Kanten, können auch Kanten überdie Punktdatenstruktur gesucht werden.

Die Klasse Parameter liest und speichert ein Parameterfile (siehe B.1), stellt Methoden zumAbfragen und Ändern der Parameter zur Verfügung und liefert Tcl entsprechende Wrapper. InC++ wie auch in Tcl können die Parameter mit dem Parameternamen, der im Parameterfileangegeben ist, abgefragt werden. In Tcl sind die Parameter in einem eigenen Namespaceabgespeichert. Will ein Modul nun seine Parameter im User-Interface anzeigen, baut eine Rou-tine im Parameter-Namespace das entsprechende Widget auf. Verändert man einen Eintrag,

Abbildung A.2: Die Verzeichnisstruktur der Entwicklungsumgebung.

A.3 DAS MODUL LSYSTEM 75

werden Events aufgerufen, die wiederum die entsprechenden Wrapper aufrufen, welche dafürsorgen, dass die Parameterwerte in C++ und Tcl konsistent sind.

Die abstrakte Klasse Heightfield dient zum Lesen von 2D-Daten jeglicher Art. Die Klasseist abstrakt, da vor allem Digital Elevation Maps in diversen Formaten existieren. Bisherkönnen jedoch nur TIFF-Bilder gelesen werden. Von diesem Typ existieren im Modul Basemehrere globale Variablen wie gPopulationDensityHF oder gElevationHF (diese werden injedem Modul immer wieder benötigt). Das Pendant in Tcl/Tk ist der Namespace ImageViewer,welcher verantwortlich für das Anzeigen der Bilder im User-Interface ist (vollständig in Tk).Da Tk keine TIFF-Bilder lesen kann, wurde das Img-Package von Jan Nijtmans benutzt.

A.3 Das Modul LSystem

Das Modul LSystem ist verantwortlich für die Strassennetzwerkgenerierung. Es beinhaltet denParser samt Wachstumsregeln und Diffusionssystem. Den Klassen dieses Moduls werdenLookuptables für trigonometrische Funktionen zur Verfügung gestellt, da effizienter Code hiersehr wichtig ist.

Die Klasse LSystem beinhaltet den Parser für das L-System, welcher die Wachstumsregelnaufruft und, falls mehrere Wachstumsregeln aktiv sind, die Vorschläge in einem vereinigt(Blending). Anschliessend wird der Environmentcheck (durch Klasse Environment) aus-geführt. Danach wird die (eventuell) resultierende Strasse im Graphen eingefügt und im Diffu-sionssystem findet ein Update statt. Die Ersetzungsregeln im L-System sind fest implementiert,d.h. es können keine neuen Ersetzungsregeln eingebaut werden wie im L-System, das dieGebäude erzeugt. Dies ist auch nicht nötig, da das Wachstumsverhalten komplett mit denWachstumsregeln kontrolliert werden kann.

Die abstrakte Klasse GrowingRule dient als Basisklasse für jede Wachstumsregel. Momen-tan sind vier Wachstumsregeln implementiert. Diese Klasse stellt einerseits den abgeleitetenKlassen relevante globale Parameter auf lokaler Basis zur Verfügung (schneller als überParameter-Klasse) und stellt andererseits sicher, dass neue Wachstumsregeln kompatibel sind.Eine Wachstumsregel muss zwei Funktionen implementieren: road(…) und highway(…). Diebeiden Funktionen erhalten als Übergabewerte den aktuellen Turtlestatus und die letzteeingefügte Strasse (Street resp. Highway). Dann erfolgt das eigentliche Wachstum, was in max-imal 3 neuen Strassen resultiert. Die Klasse GrowingRule besitzt nun 3 Highway- und 3 Street-Branches als Member. In diesen (public) Members werden die neuen Strassen abgespeichertund können bis zum nächsten Aufruf von road(…) resp. highway(…) gelesen werden. Weiterhat jede Wachstumsregel eine Parameter-Klasse und eine Heightfield-Klasse als Member.

In der Klasse Cells ist das Diffusionssystem implementiert. Das Diffusionssystem stelltFunktionen für das Abfragen (benutzt von Wachstumsregeln) und Absaugen (benutzt vomParser) von Zellen zur Verfügung, wobei diese Funktionen auf der Finiten-Differenzen-Methode basieren. Wenn Highways die Richtung der grössten Population suchen, tritt die radi-ale Abfragefunktion in Kraft. Diese wurde sehr effizient programmiert, indem im Konstruktorder Klasse angegeben werden kann, wieviele Strahlen zur Berechnung benutzt werden sollen,und wie lang diese sein sollen. Noch im Konstruktor werden nun sämtliche Indexoffsets derZellen mitsamt den Gewichten (je weiter weg, desto kleiner) berechnet. Wird die Funktion nunaufgerufen, findet bloss noch eine kleine Anzahl Multiplikationen und Additionen statt. AlsResultat liefert diese Funktion ein Array von Floats, welche eine 360°-Sicht repräsentieren (dieWerte zwischen den Strahlen werden linear interpoliert). Zusätzlich können TIFF-Bilderabgespeichert werden, welche den Zustand der Zellen visualisieren.

76 A. IMPLEMENTATION

Die Klasse LSystemGraph ist eine Subklasse der Klasse Graph aus dem Modul Base undbesteht nur aus einer Funktionendefinition. Diese Funktion namens insertModuleInGraph(…)(‘Module’ in L-System-Terminologie) stellt die Kommunikation zwischen L-System undGraph dar. Sie wird aufgerufen sobald das L-System ein Strasse definitiv einfügen will. Danachteilt der Graph (via Insertion-Module) dem L-System mit, ob das Einfügen erfolgreich war. DasZeichnen des Graphen führt ein Wrapper (in LSystemWrapper.c++) aus. Dazu wurde die X-Libbenutzt, welche Linien schneller als Tk zeichnet.

Der einzige Tcl-Code in diesem Modul ist der Namespace RuleParameter. Dieser ist eineleicht abgeänderte Version des Namespaces Parameter aus dem Modul Base. Letzterer konntenur ein Parameterfile verwalten, während RuleParameter mehrere Parametersets kontrollierenkann (pro Wachstumsregel ein Ruleparameterfile).

A.4 Das Modul Streets

Das Modul Streets ist das kleinste Modul. Da dieses Modul für die Funktionalität des Strassen-editors verantwortlich ist, besteht es bloss aus Wrapper-Definitionen und der KlasseStreetGraph, welche eine Subklasse von Graph aus dem Modul Base ist. Die Klasse Street-Graph erweitert die Graphenklasse um zwei Funktionen: smoothGraph(…) (siehe 4.4) undsaveAATIFF(…), welche den Graphen als TIFF-Bild abspeichert. Die Kanten der gezeichnetenStrassen werden dabei geglättet. Die Wrapper sind verantwortlich für Funktionsaufrufe wieselectEdge(…), moveVertex(…), deleteEdge(…) oder drawGraph(…). Das Zeichnen desGraphen erfolgt auf ähnliche Weise wie im Module LSystem, nur sind hier mehrere Darstellung-sarten möglich und Selektion wird unterstützt.

A.5 Das Modul Allotments

Das Modul Allotments ist verantwortlich für die Konvertierung des Graphen in Polygone(Blocks), deren Subdivision in kleinere Polygone (Grundstücke) und das Erzeugen und Ver-walten von Gebäudegeometrie. Allen Klassen in diesem Modul stehen Polygon-Datenstruk-turen (mit Funktionen) zur Verfügung. Die Punkte aller Polygone sind stets imGegenuhrzeigersinn angeordnet.

Die Klasse AllotmentGraph ist eine Subklasse der Graphenklasse aus dem Modul Base undextrahiert aus dem Graphen die der Suchtiefe entsprechenden Polygone. D.h. alle Zyklen imGraphen, die keinen anderen, kürzeren Zyklus enthalten, sind gesucht. Dazu wurde folgenderAlgorithmus verwendet: In jedem Knoten des Graphen wird nacheinander eine rekursive Suchenach Zyklen begrenzter Länge (Suchtiefe) durchgeführt. War die Suche erfolgreich, d.h. derletzte Knoten entspricht wieder dem Ausgangsknoten, indem die Suche gestartet wurde, mussder gefundene Zyklus überprüft werden:

• Wurde bereits ein kürzerer oder gleich langer Zyklus gefunden, der Teil des neuen Zyk-lus ist, ist der neue Zyklus überflüssig und kann verworfen werden.

• Ist der neue Zyklus Teil eines bereits gefundenen längeren Zyklus, kann der alte Zyklusverworfen werden.

• Befindet sich innerhalb des Zyklus ein Knoten, kann dieser verworfen werden.

Die Klasse PolygonContainer besteht aus einer Polygonliste und Funktionen zum Lesen undSchreiben von Polygonfiles (siehe B.4 und B.5). Weiter werden in dieser Klasse auch MEL-Dateien erzeugt (siehe B.8). Die Funktion cutEdges() verkleinert die Polygone, indem an jederKante die halbe Strassenbreite subtrahiert wird. Konkave Polygone werden durch diesen Proz-ess in konvexe Polygone verwandelt. Dies vereinfacht das Exportieren von Geometrie in 3D-

A.6 DAS MODUL UI 77

Programme (diese haben oft Mühe mit konkaven Polygonen). Das Subdividieren der Polygonewird wie in 5.1 beschrieben durchgeführt. Ist die Subdivision beendet und ein Grundstückgefunden, werden dessen sämtliche Eigenschaften bestimmt. D.h. alle Attribute eines Gebäudeswie Grundfläche, Höhe, Alter oder Funktion sind ab diesem Zeitpunkt festgelegt. Nur demShapestring-Attribut ist noch kein String zugeordnet. Das Pythonscript LSystemControl.pyruft nun für jedes Gebäude das L-System auf, das entsprechende Shapestrings generiert unddiese in einzelnen Dateien abspeichert. Mit Hilfe des Wrapperaufrufs attachStringToPoly-gon(…) werden diese Files eingelesen und in den Polygonen als Shapestring-Attribut abgespe-ichert. Ebenfalls in AllotmentsWrapper.c++ befindet sich ein Wrapper, der die Polygone imUser-Interface zeichnet. Auch hier wurde wieder die X-lib benutzt.

In der Klasse Geometry befindet sich der Parser, der die Shapestrings der Polygone interpre-tiert. Die daraus resultierende Geometrie wird in Objekten mit je einer Liste für Vertices, Tex-tures, Edges und Faces verwaltet. Der Zweck dieser Listen ist, dass die Geometrie in einbekanntes 3D-Format exportiert werden kann, weshalb auch die Beziehung zwischen denKomponenten mit Indexeinträgen abgebildet werden (zur Beschreibung eines Meshes listen diemeisten Formate zuerst die Vertices auf und anschliessend werden deren Indexe weiterverwen-det um Faces etc. zu definieren). Die Funktion exportGeometryToMaya(…) schreibt die Geom-etrie im Maya Ascii Format in eine Datei (siehe B.9).

A.6 Das Modul UI

Bis auf das oben erwähnte Main.c++ ist das Modul UI vollständig in Tcl/Tk programmiert.Main.tcl importiert zuerst das Img-Package und das BWidgets-Package. Letzteres stellt ver-besserte Widgets zur Verfügung, ist aber komplett in Tcl/Tk programmiert. Anschliessendwerden globale Variablen wie Modulnamen definiert und das User Interface mit den Menuein-trägen wird aufgebaut. Das User Interface selbst wurde ebenfalls modular entworfen, d.h. belie-big viele Module können dem User-Interface hinzugefügt werden. Entscheidend ist die Listeder Modulnamen. Jedem darin aufgeführten Modul wird ein Widget zur freien Verfügung bereitgestellt.

Die drei Module LSystem, Streets und Allotments benötigen im Gegensatz zum Modul Baseein User Interface. Die Definitionen dessen findet man in den Dateien LSystemUI.tcl, Street-sUI.tcl und AllotmentsUI.tcl in diesem Modul. Jeder Namespace muss eine Prozedur namensCreateMainFrame besitzen, die den Aufbau des von Main.tcl zur Verfügung gestellten Widgetsübernimmt. Jedes Modul kann Teile des Widgets dem ImageViewer zur Verfügung stellen.Falls das Modul dann eine eigene Zeichenroutine benützen will, kann es diese beim ImageV-iewer registrieren (drawStreetGraphWrapper ist beispielsweise die Zeichenroutine vom ModulStreets). Die Gestaltung der Widgets der Module kann sich unterscheiden: Das L-System-Modul hat beispielsweise einen multifunktionalen Timeslider, der im Allotments-Modul nichtvorkommt.

Der Namespace FileTransfer ist verantwortlich für das Laden und Speichern sämtlicherDaten. Je nach Dateityp führt er die entsprechenden Operationen aus. Wird ein Parameterfilegeladen, werden zuerst die Parameter in C++ gelesen, dann Tcl übergeben, welches darauf dieoffenen Parameterfenster neu zeichnet. Anschliessend werden die in Tcl/Tk mit dem ImageV-iewer-Namespace und in C++ mit der Heightfield-Klasse die Bilder geladen . Danach werdendie Ruleparameterfiles gelesen und wiederum ausgewertet (in Tcl/Tk Regel-Kontrollbild ladenund in C++ Instanz einer GrowingRule erzeugen). Die anderen Dateitransferoperationen bes-chränken sich meist auf einen Wrapper-Aufruf und ein ImageViewer-Update.

78 A. IMPLEMENTATION

79

BDateitypen

B.1 Parameterfile (.par)

Eine Parameterdatei beinhaltet alle Daten eines CityEngine-Projektes, wie UI-Einstellungen,Dateipfade zu den entsprechenden Bildern, Dateipfade zu den Parameterdateien der L-SystemRegeln (siehe nächsten Abschnitt) und Parameter jeglicher Art. Im Unterschied zu den anderenDateitypen beinhaltet eine Parameterdatei nicht nur die Werte der Parameter sondern auchderen Definition und UI-Informationen. Das Format einer Zeile (entspricht einer Parameter-definition) sieht folgendermassen aus, wobei in Klammern immer der Typ des jeweiligen Ein-trags angegeben ist (B für Boolean, I für Integer, F für Float, C für Char und S für String):

Typ(C) Name(S) Wert(Typ) Standardwert(Typ) UI-Info(C)

Der erste Eintrag einer Zeile definiert den Typ des Parameters (B, I, F oder S). Das Zeichen ‘_’im Parameternamen wird zur Anzeige im User Interface mit einem Leerzeichen ersetzt. Derletzte Eintrag einer Zeile kontrolliert den Ort der Anzeige im User Interface: P für das Fenstermit den Einstellungen; L, S oder A für den Parameterteil des jeweiligen Moduls oder H um denParameter nicht anzuzeigen (angewendet bei On/Off-Buttons, die über Menüs wesentlichbesser zu kontrollieren sind). Die Reihenfolge der Darstellung der Parameter im jeweiligenFenster entspricht der Reihenfolge ihrer Definition in der Parameterdatei. Ein Ausrufezeichenzu Beginn der Zeile nach der letzten Parameterdefinition markiert das Ende der Datei.

B.2 Ruleparameterfile (.rp)

Die Parameterdatei einer Regel für das Strassennetzwerk generierende L-System hat dasselbeFormat wie eine Parameterdatei. Der Unterschied liegt einzig im Inhalt: Wie der Name schonverrät, beinhaltet sie sämtliche Parameter zur individuellen Steuerung einer L-System-Regel.Der Typ der Regel (Western, Grid, Radial, Topological) wird durch den Prefix im Dateinamenbestimmt (zum Beispiel: Western.version2.rp). Die UI-Information wird hier nicht verwendet.

B.3 Graphfile (.gra)

Eine Graphendatei beschreibt ein (generiertes) Strassennetzwerk samt Strasseninformationen.Eine Datei sieht folgendermassen aus:

80 B. DATEITYPEN

#VERTICES: nbrOfVertices(I)valence(I) x(F) y(F)… #EDGES: nbrOfEdges(I)index1(I) index2(I) creationStep(I) nbrOfTracks(I) streetType(S)…

Die Kopfzeile beschreibt die Anzahl der Punkte (respektive Kreuzungen) und auf den darauffolgenden nbrOfVertices Zeilen sind die Daten der Punkte aufgelistet. Der Eintrag valencebeschreibt die Anzahl der sich in diesem Punkt treffenden Kanten (entspricht Strassen). Danachfolgt die Definition der Kanten (Anzahl: nbrOfEdges). Die ersten beiden Indexeinträge ver-weisen auf die beiden Endpunkte der Kante und die letzten drei Einträge repräsentieren dieAttribute einer Strasse: creationStep beschreibt den Zeitpunkt der Generierung durch dasL-System, nbrOfTracks die Anzahl Spuren und streetType den Typ der Strasse (H für Highway,S für Street und falls die Strasse eine Brücke ist: BH respektive BS).

B.4 Blockfile (.p)

Dieser Dateityp wird verwendet, um Blockdaten (Polygone) abzuspeichern und zu lesen. EineDatei dieses Typs beinhaltet die eigentliche Definition der Polygone und für jede Kante dieStrassenattribute (siehe Graphfile). Jede Zeile beschreibt ein Polygon und eine Null am Anfangder letzten Zeile markiert das Ende der Datei. Das Format einer Zeile sieht folgendermassenaus:

valence x1 y1 … xvalence yvalence streetAttr1 … streetAttrvalence

B.5 Lotfile (.p+)

Dieser Dateityp wird verwendet um Gebäudegrundstücke (Polygone) abzuspeichern und zulesen. Auch das gebäudegenerierende L-System liest diese Polygondatei um die Shapestringszu generieren. Die ersten Einträge einer Zeile sind dieselben wie im Blockfile und die restlichenEinträge sind Parameter für das auf diesem Grundstück zu bauende Gebäude. Eine Null amAnfang der letzten Zeile markiert das Ende der Datei. Eine Zeile hat folgende Einträge:

valence,x1,y1,…,xvalence ,yvalence ,streetAttr1,…,streetAttrvalence ,elevation(F),height(F),length(F),width(F),shapeType(C),creationStep(I),zoneID(I),blockID(I),houseID(I),buildingType(C),objectID(I),age(I),floorHeight(F),windowWidth(F)

Der Eintrag elevation entspricht der Höhe über Meer (minimale Y-Koordinate aller Punkte), dienächsten drei Einträge stellen die Bounding Box dar und shapeType den Typ des Polygons (Rfür Rechtecke und I für alle anderen Formen). Die weiteren Attribute und ihre Bedeutung:

• creationStep: maximaler creationStep aller Kanten von dem Polygon.• zoneID: Identifikationsnummer der rechteckigen Zone, in der sich das Polygon befindet.• blockID: Identifikationsnummer des Blockes, in dem sich das Polygon befindet.• houseID: eindeutige Hausnummer.• buildingType: R für Residential, C für Commercial und I für Industrial (dieser Wert wird

für das Gebäude-L-System und die prozeduralen Shader benötigt). • objectID: Identifikationsnummer für das Geometrieobjekt, zu dem dieses Gebäude hin-

zugefügt werden soll (werden prozedurale Shader verwendet, so ist diese Identifikations-nummer irrelevant, da nur je ein Objekt erzeugt wird).

B.6 BUILDINGRULEFILE (.LSYS) 81

• age: Erbauungsjahr des Gebäudes. • floorHeight: Stockwerkhöhe (für L-System und nicht-prozeduralen Shader); • windowWidth: Fensterabschnittsbreite (für L-System und nicht-prozeduralen Shader).

B.6 Buildingrulefile (.lsys)

Die Regelwerke für das L-System, das die CityEngine Shape Grammar Strings erzeugt, werdenin diesem Dateityp verfasst. Da dieser auf XML basiert und sich streng an die L-System-Syntaxhält, ist dessen Anwendung leicht nachvollziehbar und bedarf keiner weiteren Erklärung.

B.7 Shapestringfile (.str)

Diese Dateien werden vom Gebäudegenerierenden L-System erzeugt und jede Datei beinhalteteinen CityEngine Shape Grammar String, der die Form eines Gebäudes beschreibt. Der Datein-ame beinhaltet die eindeutige Gebäudenummer (houseID), wodurch jedem Gebäude dieentsprechende Shapestringdatei zugeordnet werden kann. Die Shape Grammar ist in Kapitel 6beschrieben.

B.8 MEL Code (.mel)

Dieser einfache MEL (Maya Embedded Language) Code ist vor allem zu Testzweckengeeignet, um Polygone in Maya zu betrachten. Der Code liest Polygone (MEL-Befehl: create-Facet) jeglicher Art (Blocks und Lots) und anschliessend werden diese Polygone extrudiert(MEL-Befehl: extrude), wobei keine Texturinformationen hinzugefügt werden.

B.9 Maya Ascii (.ma)

Maya Szenen können als Binary oder Ascii Files abgespeichert werden. Letztere bestehen auseinem reduzierten Set von MEL-Kommandos, mit denen Geometrie direkt in Maya eingelesenwerden kann (ähnlich wie zum Beispiel das .obj Format). Die CityEngine kann drei Arten vonMaya Ascii Dateien schreiben:

1. Untexturierte Extrusionen: Der Unterschied zum erzeugten MEL-Code ist, dassdieses Format wesentlich schneller in Maya eingelesen ist und nur ein Objekt erzeugt,was viele Transform-Nodes erspart und die resultiernde Maya-Szene um einigesschneller macht.

2. Gebäude für prozedurale Shader: Es wird pro Shader (Residential, Commercial undIndustrial) ein Objekt generiert. Jedem Face werden Attribute wie Gebäudenummer,Alter oder Fassadengrösse zugeordnet, welche von den prozeduralen Shadern gelesenwerden können. Die Texturkoordinaten der Faces können in Maya normalisiert wer-den.

3. Gebäude für nicht-prozedurale Shader: Für jeden Gebäudetyp (objectID) existierenzwei Shader: ein Fassadenshader und ein Dachshader. Es wird also pro Fassaden-Shader ein Objekt und pro Dachshader ein Objekt generiert. Fassadenshader sind fol-gendermassen aufgebaut: Ein Fensterabschnitt mit Höhe floorHeight und Breite win-dowWidth entspricht im Texturraum U von 0 bis 1 und V von 0 bis 1. In Mayabedeutet dies nun nicht, dass alle Fenster gleich aussehen müssen, denn es gibt dieMöglichkeit Shader über mehrere Fensterabschnitte zu definieren (Coverage-Para-meter von 2DTexturePlacement). Die Texturkoordinaten der Dachobjekte können inMaya normalisiert werden.

82 B. DATEITYPEN

83

CReferenzen

[1] C. Alexander, S. Ishikawa, M. Silverstein, M. Jacobson, I. Fiksdahl-King and S. Angel.A Pattern Language. Oxford University Press, New York, 1977.

[2] B. M. Blumberg and T. A. Galyean. Multi-Level Direction of Autonomous Creatures forReal-Time Virtual Environments. In SIGGRAPH Conference Proceedings, pages 47-54,August 1995.

[3] E. Catmull and J. Clark. Recursively generated B-spline surfaces on arbitrary topologicalmeshes. Computer Aided Design, 10(6):350-355, 1978.

[4] D. Davis, W. Ribarsky, T.Y. Jiang, N. Faust and S. Ho. Real-Time Visualization of scal-ably large collections of heterogeneous objects. IEEE Visualization ‘99, pp. 437-440,October 1999.

[5] X. Decoret, G. Schauffler, F. Sillion and J. Dorsey. Multi-layered impostors for acceler-ated rendering. Eurographics 18(3), 1999.

[6] O. Deussen, P. Hanrahan, B. Lintermann, R. Mêch, M. Pharr and P. Prusinkiewicz. Real-istic modeling and rendering of plant ecosystems. In SIGGRAPH 98 Conference Proceed-ings, pages 275-286, August 1998.

[7] K. Dietrich, M. Rotach, E. Boppart. Strassenprojektierung. Zurich 1993.

[8] H. Ferris. The Metropolis of Tomorrow. I.Washburn, New York, 1929.

[9] C. Focas (ed.) The Four World Cities Transport Study. London Research Centre, The Sta-tionery Office, London 1998.

[10] K. Fuesser. Stadt, Strasse & Verkehr (City, Roads and Traffic), Vieweg Verlag, 1997.

[11] T. Fujii, K. Imamura, T. Yasuda, S. Yokoi and J. Torikawi. A virtual scene simulationsystem for city planning. Computer Graphics International, 1995.

[12] D. Zorin, P. Schröder. Subdivision for Modeling and Animation. Siggraph Course Notes,ACM SIGGRAPH, Course 36, 1998.

[13] O. Henricsson, A. Streilein and A. Gruen. Automated 3-D reconstruction of buildings andvisualization of city models. Bonn. Oct. 1996.

84 C. REFERENZEN

[14] B. Hillier. Space is the Machine: A Configurational Theory of Architecture. CambridgeUniversity Press, Cambridge, UK, 1997.

[15] B. Hillier, A. Penn, J. Hanson, Grajewski and J. Xu. Natural Movement: or, Configura-tion and Attraction in Urban Pedestrian Movement. Environment and Planning B, Vol.20, pp. 29-66, 1993.

[16] A.B. Jacobs. Great Streets.The MIT Press, Cambridge Massachusetts. 1993.

[17] H. Samet. The Design and Analysis of Spatial Data Structure. Addison-Wesley, Reading,MA, 1990.

[18] R. Mêch and P. Prusinkiewicz. Visual models of plants interacting with their environ-ment. In SIGGRAPH 96 Conference Proceedings, pages 397-410, August 1996.

[19] V. Meier. Realistic Visualization of Abdominal Organs and its Application in Laparo-scopic Surgery Simulation. Disseration, ETH Zurich, 1999.

[20] W.J. Mitchell. Computer-Aided Architectural Design. Van Nostrand Reinhold, NewYork, 1977.

[21] F.K. Musgrave, C.E. Kolb and R.S. Mace. The Synthesis and Rendering of Eroded FractalTerrains, In SIGGRAPH 89 Proceedings, pp. 41-50, July 1990.

[22] Peponis J., Zimring C. and Choi Y. K. Finding the Building in Wayfinding. In Environ-ment and Behavior, Vol. 22, pp. 555-590., 1990.

[23] K. Perlin. An Image Synthesizer. Computer Graphics (SIGGRAPH 85 Proceedings),19(3): 287-296, 1985.

[24] P. Prusinkiewicz and A. Lindenmayer. The algorithmic beauty of plants, Springer, 1990.

[25] P. Prusinkiewicz, M. James and R. Mêch. Synthetic Topiary. In SIGGRAPH 94 Confer-ence Proceedings, pages 351-358, July 1994.

[26] W.T.Reeves and R.Blau. Approximate and probabilistic algorithms for shading and ren-dering structured particle systems. Computer Graphics (SIGGRAPH 85 Proceedings),19(3): 313-322, 1985.

[27] S. M. Rubin and T. Whitted. A 3-dimensional representation for fast rendering of complexscenes. Computer Graphics 14(3), pages 110-116, 1980.

[28] K. Sims. Evolving Virtual Creatures. Computer Graphics (SIGGRAPH 94 Proceedings),1994.

[29] G. Stiny. Pictorial and Formal Aspects of Shapes and Shape Grammars. Birkhauser,Basel, Switzerland, 1975.

[30] M. Wegener. Operational Urban Models: State of the Art. In Dortmunder Beitrage zurRaumplanung No. 84, University of Dortmund, 1998.

[31] G. Schmitt. Architectura et Machina. Vieweg Verlag, Wiesbaden, 1993.

[32] R. Woodbury. Layouts, Solids, Grammar Interpreters and Fire Stations. In: CAADFutures ‘93, Pittsburgh, 1993.

[33] I. Sutherland. Sketchpad, A Man-Machine Graphical Communication System. In: Pro-ceedings 1963 Spring Joint Computer Conference AFIPS, Vol. 23, 1963.

85

DSiggraph 2001 Paper

ABSTRACT

Modeling a city poses a number of problems to computer graph-ics. Every urban area has a transportation network that followspopulation and environmental influences, and often a superim-posed pattern plan. The buildings appearances follow historical,aesthetic and statutory rules. To create a virtual city, a roadmaphas to be designed and a large number of buildings need to begenerated. We propose a system using a procedural approachbased on L-systems to model cities. From various image mapsgiven as input, such as land-water boundaries and populationdensity, our system generates a system of highways and streets,divides the land into lots, and creates the appropriate geometryfor the buildings on the respective allotments. For the creation ofa city street map, L-systems have been extended with methodsthat allow the consideration of global goals and local constraintsand reduce the complexity of the production rules. An L-systemthat generates geometry and a texturing system based on textureelements and procedural methods compose the buildings.

CR categories:

F.4.2 [Mathematical Logic and Formal Lan-guages]: Grammars and Other Rewriting Systems: ParallelRewriting Systems, I.3.7 [Computer Graphics]: Three-Dimen-sional Graphics and Realism, I.6.3 [Simulation and Modeling]:Applications

Keywords:

L-system, software design, developmental mod-els, modeling, urban development, architecture

1 INTRODUCTION

Modeling and visualization of man-made systems such as largecities is a great challenge for computer graphics. Cities are sys-tems of high functional and visual complexity. They reflect thehistorical, cultural, economic and social changes over time inevery aspect in which they are seen. Examining pictures of alarge-scale city such as New York reveals a fantastic diversity ofstreet patterns, buildings, forms and textures. The modeling andvisualization of large-area cities using computers has becomefeasible with the large memory, processing and graphics powerof todays hardware. The potential applications for a proceduralcreation range from research and educational purposes such asurban planning and creation of virtual environments to simula-tion. Especially the entertainment market such as the movie andgame industry have a high demand for the quick creation ofcomplex environments in their applications.Visual modeling of large, complex systems has a long traditionin computer graphics. Most of these approaches address theappearance of natural phenomena. Much of the appeal of suchrenderings lies in the possibility to depict the complexity oflarge-scale systems, which are composed of simpler elements.

Some of these systems include: the simulation of erosion [23],particle based forests [28] and cloud modeling [25].Grammar-based generation of models (especially L-systems) areemployed in computer graphics mainly to create plant geometry[26]. L-systems have evolved into very sophisticated and power-ful tools [20, 27] and have been extensively used in the modelingof plant ecosystems described in [8].

1.1 Related Work in Urban Modeling

One approach to modeling existing cities is the use of aerialimagery to extract the buildings and streets thereof, using com-puter vision methods. There are various research projects thatrely on this approach, e.g. [15]. This method can be used torebuild cities, but is not designed to create new models withoutphotographic input data.The existing research work concerning the visualization of cities[6, 7, 13, 29] focuses on techniques for data management, fastreal-time visualization and memory-usage optimization.In [1], Alexander et al. describe a pattern language, which con-sists of over 250 relevant patterns for the successful constructionof cities, buildings and houses. They range from very generalpatterns like “Ring Roads” to very specific ones like “Pavingwith cracks between the stones”. Since these patterns are notformalized, they cannot be used in the automatic creation pro-cess of an urban environment.

Space Syntax

has been developed by Hillier [16]. Space syntaxcan be viewed as a set of theories analyzing the complexity oflarge-scale spaces, such as cities. It tries to explain humanbehaviors and activities from a spatial point of view and hasbeen used in the analysis of city pedestrian flows [17] or way-finding processes [24]. This approach is analytical and relies onthe availability of city-maps. In the field of architectural interac-tive design one approach might be mentioned: the

shape

gram-mar

developed by Stiny [31]. This method uses production rules,but instead of operating on strings, a shape grammar definesrules directly on shapes. Shape grammars have been used to gen-erate two-dimensional patterns and in interactive design applica-tions.

1.2 Our approach

We present a system called

CityEngine

which is capable ofmodeling a complete city using a comparatively small set of sta-tistical and geographical input data and is highly controllable bythe user. To our knowledge, there is no such system available,although one very similar project outline is presented under [34].In [5], a method for generating urban models is presented byrefinement of existing geometry. However, in this approach abasic model of the city buildings has to be created manually.Other systems [4, 32] rely on aerial pictures as the main inputfor building and road placement. Our

CityEngine

createsurban environments from scratch, based on a hierarchical set ofcomprehensible rules that can be extended depending on theusers needs.In [33], Wegener splits the urban model into subsystems. Hestates that the subsystems

networks

,

land use

and

housing

areamong the slowest changing elements in an urban environment.Therefore, in our system

CityEngine

, the creation of the cityis reduced to generating a traffic network and buildings. Landuse data is provided by the user in form of image-maps. Whenstudying maps and aerial photographs of large cities, it is obvi-ous that the streets follow some sort of pattern on different

Procedural Modeling of Cities

Yoav I H Parish Pascal Müller

parish@imes.mavt.ethz.ch pascal@centralpictures.com

ETH Zürich, Switzerland Central Pictures, Switzerland

Permission to make digital or hard copies of all or part of this work forpersonal or classroom use is granted without fee provided that copiesare not made or distributed for profit or commercial advantage and thatcopies bear this notice and the full citation on the first page. To copyotherwise, to republish, to post on servers or to redistribute to lists,requires prior specific permission and/or a fee.

ACM SIGGRAPH 2001, 12-17 August 2001, Los Angeles, CA, USA© 2001 ACM 1-58113-374-X/01/08...$5.00

301

scales. Roads are the transportation medium for the urban popu-lation distributed over the area. L-systems have been used in asimilar application [20], support branching very well and havethe advantage of database amplification [30]; this suggests theirpotential use to generate convincing large-scale road patterns.We have adapted the model of L-systems to enable the creationof large cities, based on the data that has been collected in [11]on four huge cities around the world, i.e. New York, Paris, Tokyoand London.Although we simplified the underlying model of the virtual city,the main design goal for the system is easy extensibility. Wewant to be able to add new subsystems, such as different trans-portation networks (underground, train) and alternative landuses. To achieve this, we extended the L-system with a higher-level mechanism that makes the addition of new rules very easy.

1.3 Overview

In Chapter 2 we describe the concept and the pipeline of the

CityEngine

system, and the methods used therein. In Chapter3 the idea of extended L-systems, which allow the implementa-tion of global goals and local constraints is introduced. We dem-onstrate the use of this extended concept on the creation of theroadmap. Chapter 4 gives a brief overview of the generation ofallotments and buildings and explains our proposed mechanismto simplify the texturing of facades. Finally, the results weachieved are shown and discussed in Chapter 5.

2 SYSTEM ARCHITECTURE

The

CityEngine

system consists of several different toolswhich form the pipeline that is shown in figure 1. In a first step,the input data is fed to the road-generation system, using anextended L-system described in 3.4. The areas between the roadsare then subdivided to define the allotments the buildings areplaced on. In a third step, by applying another L-system, thebuildings are generated as a string representation of booleanoperations on simple solid shapes. Finally, a parser interprets allthe results for the visualization software. The visualization soft-ware should be able to process polygonal geometry and texturemaps. This is the case for practically any 3D renderer. Addition-ally, most scanline renderers support procedural textures, so theproposed mechanism to generate facades of buildings can beincorporated into the pipeline.

Most of the input data to build up the virtual city is representedby 2D image maps which control the behavior of the system.Those images can be easily generated either by drawing them orby scanning from statistical and geographical maps, as found in[11]. The data can be categorized into two general classes:

• Geographical Maps- Elevation maps- Land/water/vegetation maps

• Sociostatistical maps- Population density- Zone maps (residential, commercial or mixed zones)- Street patterns (control behavior of streets)- Height maps (maximal house height)

Control of the various parameters within the particular tools canbe changed by the user interactively or by providing parameterfiles. For example, statistical measures such as the approximatearea size of a block or the average number of intersections persquare mile, such as in [18] can be used to change the resultingstreet map. In figure 2 the top pictures are examples of a geo-graphical image showing land-water boundaries and anotherimage depicting the distribution of the population over the area.

Two different L-systems are invoked for the creation of the com-plete city, one for street, the other for building generation. Thepopulation density of a city is influenced by the creation ofstreets. Through streets, people are transported by the system tothe next highway [12]. We reflect this by using an approach sim-ilar to the Open L-system model [20] when creating streets. TheL-system mechanism has been modified in such a way that vari-ous different road patterns can be visualized using the same pro-duction rules. According to [12], not all roads change the population density oftheir immediate local surroundings, e.g. roads connecting twocities. We therefore chose to consider two types of roads:

high-ways

and

streets

. They differ in their purpose and behavior:Highways connect areas with highly concentrated populationglobally, by scanning the population density input map forpeaks. Streets cover the areas between highways according tolocal population density, giving all neighborhoods transportationaccess to the nearest highway. Together, these two classes formthe road map of the virtual city.Once the road map is generated, the land is divided into smallerareas surrounded by streets. These areas can be geometricallysubdivided to define the allotments for the individual buildings.The buildings themselves are generated by a stochastic, paramet-ric L-system. In our system the buildings are composed byextruding and transforming an arbitrary outline.For the final visualization in the renderer facade textures are gen-erated using a semi-procedural approach. Every facade is tiledinto superimposed and nested grid structures. The grid cellsresulting from this subdivision can then be assigned textures orprocedural textures.

GeographicalSociostatistical

Image Maps

Roadmap creationExtended L-System

Division into lotsSubdivision

Building generationL-System

GeometryParser

RoadmapGraph

AllotmentsPolygons

BuildingsStrings

GeometryPolygons

Texture EngineGrid creation

ShadersProcedural

Facade elementsImage Maps

Renderer

OutputImages

Figure 1: The pipeline of the city creation tool. The dark boxeslist the results and data structures of the indiviual tools in thewhite rectangles.

Figure 2: Left column: Water, elevation and population densitymaps of an imaginary virtual city of 20 miles diameter. Right:One possible roadmap generated from this input data.

302