Procedural Modelling of Cities Y.I.H. Parish & P. Mller Presentation by Ian Eborn and Anton Burger Overview

CityEngine Introduction to L-systems The road generation algorithm The building generation algorithm Procedural texturing system CityEngine Uses maps of population density, land-water boundaries, etc. to create a road network using

Open L-systems Spaces between blocks subdivided into lots for individual buildings Buildings generated using parametric stochastic L-systems, detail with procedural texturing technique Introduction to L-systems

Parallel string rewriting systems Originally used to model plant growth Strings consist of symbols (modules) Uses production rules to rewrite modules The starting string is called the axiom, and is labelled

Intro to L-systems Each production rule requires at least a name, predecessor module and a string of modules, its successor Example: : A p1: A AB p2: B BA

Produces strings of the form ABBABAAB NB. Parallel rewrite system means that all possible rewrites are made to the old string before the next iteration begins Intro to L-systems Now associate commands with modules Imagine a Logo-like turtle with a position and orientation; commands executed sequentially after all rewrites in a derivation step

e.g. F = draw 1 unit in current direction, + = turn right 60, - = turn left 60 [ and ] are push and pop: remember current turtle state so we can return to it later Allows creation of branching structures An L-system turtle Assume turtle starts facing straight up : F p1: F F[-F][+F]

1 iteration 2 iterations More complex L-systems Introduce the notion of left- and right-context p1: A < S > B C

Replaces S with C only if it is preceded by A and followed by B Modules can have parameters : F(1) p1: F(x) F(x + 1) Parameters can be used to match modules for rewriting or to affect their associated commands Parameters and conditions

Conditions provide extra prerequisites for the application of a production : F(1) p1: F(x): x < 3 F(x + 1) p2: F(x): x 3 F(3)

Line stops growing at 3 units Stochastic L-systems Specifies the probability of a particular production being applied : A(5) p1: A(x) A(x + 1): 0.3 p2: A(x) A(x 1): 0.7 Parameter likelier to shrink than to grow in

this example Environmentally sensitive L-systems So far, L-systems have been more or less selfcontained Parameters provide global influences from the environment We can provide a way to have the environment affect the development of the system locally Query module: ?X(x, y, z) X represents some property of the turtle, i.e. X = P for

position, X = H, U or L for orientation vectors When the module is interpreted, the parameters are filled with the relevant quantities; can be used for subsequent matches or calculations Environmentally sensitive L-systems Example from Synthetic Topiary, by P. Prusinkiewicz, M. James & R. Mch Need some extra modules: % terminates a branch by deleting all the modules

from the current point to the end of this branch @o draws a circle at the current turtle position Environmentally sensitive L-systems : A

p1: A [+B][-B]F?P(x, y)A p2: B F?P(x, y)@oB p3: ?P(x, y): 4x2 + (y 10)2 > 102 [+(2y)F][-(2y)F]% Similar constructs used to represent effects of pruning, competition amongst branches for sunlight, etc. The eye-candy part of the presentation

Some results from the authors of Synthetic Topiary Open L-systems Generalisation of environmentally sensitive Lsystems Communication module ?E(x1, , xn) with no restriction on number/meaning of parameters When interpreted, control is passed to an external function representing some part of the environment Environment performs calculations, optionally passes

back modified parameter values to be used in the next derivation step Allows two-way communication between system and environment The road generation algorithm CityEngine uses Open L-systems for road generation Environment functions are the constraints imposed on the roads Two types of roads: highways & streets

Highways connect areas of high population density Streets connect the rest of the populace to the nearest highway The production rules for roads : R(0, initRuleAttr)?I(initRoadAttr, UNASSIGNED)R(0, R(0, initRuleAttr)?I(initRoadAttr, UNASSIGNED)initRuleAttr)?I(initRoadAttr, R(0, initRuleAttr)?I(initRoadAttr, UNASSIGNED)UNASSIGNED) p1: R(0, initRuleAttr)?I(initRoadAttr, UNASSIGNED)R(del, R(0, initRuleAttr)?I(initRoadAttr, UNASSIGNED)ruleAttr): R(0, initRuleAttr)?I(initRoadAttr, UNASSIGNED)del R(0, initRuleAttr)?I(initRoadAttr, UNASSIGNED)< R(0, initRuleAttr)?I(initRoadAttr, UNASSIGNED)0 R(0, initRuleAttr)?I(initRoadAttr, UNASSIGNED) R(0, initRuleAttr)?I(initRoadAttr, UNASSIGNED) p2: R(0, initRuleAttr)?I(initRoadAttr, UNASSIGNED)R(del, R(0, initRuleAttr)?I(initRoadAttr, UNASSIGNED)ruleAttr) R(0, initRuleAttr)?I(initRoadAttr, UNASSIGNED)> R(0, initRuleAttr)?I(initRoadAttr, UNASSIGNED)?I(roadAttr, R(0, initRuleAttr)?I(initRoadAttr, UNASSIGNED)state): R(0, initRuleAttr)?I(initRoadAttr, UNASSIGNED)state R(0, initRuleAttr)?I(initRoadAttr, UNASSIGNED)== R(0, initRuleAttr)?I(initRoadAttr, UNASSIGNED) SUCCEED R(0, initRuleAttr)?I(initRoadAttr, UNASSIGNED)+(roadAttr.angle)F(roadAttr.length)

B(del1, R(0, initRuleAttr)?I(initRoadAttr, UNASSIGNED)ruleAttr1, R(0, initRuleAttr)?I(initRoadAttr, UNASSIGNED)roadAttr1) B(del2, R(0, initRuleAttr)?I(initRoadAttr, UNASSIGNED)ruleAttr2, R(0, initRuleAttr)?I(initRoadAttr, UNASSIGNED)roadAttr2) R(del0, R(0, initRuleAttr)?I(initRoadAttr, UNASSIGNED)ruleAttr0)?I(roadAttr0, UNASSIGNED) The production rules for roads p3: R(0, initRuleAttr)?I(initRoadAttr, UNASSIGNED)R(del, R(0, initRuleAttr)?I(initRoadAttr, UNASSIGNED)ruleAttr) R(0, initRuleAttr)?I(initRoadAttr, UNASSIGNED)> R(0, initRuleAttr)?I(initRoadAttr, UNASSIGNED)?I(roadAttr, R(0, initRuleAttr)?I(initRoadAttr, UNASSIGNED)state): R(0, initRuleAttr)?I(initRoadAttr, UNASSIGNED)state R(0, initRuleAttr)?I(initRoadAttr, UNASSIGNED)== R(0, initRuleAttr)?I(initRoadAttr, UNASSIGNED) FAILED R(0, initRuleAttr)?I(initRoadAttr, UNASSIGNED) p4: R(0, initRuleAttr)?I(initRoadAttr, UNASSIGNED)B(del, R(0, initRuleAttr)?I(initRoadAttr, UNASSIGNED)ruleAttr, R(0, initRuleAttr)?I(initRoadAttr, UNASSIGNED)roadAttr): R(0, initRuleAttr)?I(initRoadAttr, UNASSIGNED)del R(0, initRuleAttr)?I(initRoadAttr, UNASSIGNED)> R(0, initRuleAttr)?I(initRoadAttr, UNASSIGNED)0

R(0, initRuleAttr)?I(initRoadAttr, UNASSIGNED)B(del R(0, initRuleAttr)?I(initRoadAttr, UNASSIGNED) R(0, initRuleAttr)?I(initRoadAttr, UNASSIGNED)1, R(0, initRuleAttr)?I(initRoadAttr, UNASSIGNED)ruleAttr, R(0, initRuleAttr)?I(initRoadAttr, UNASSIGNED)roadAttr) p5: R(0, initRuleAttr)?I(initRoadAttr, UNASSIGNED)B(del, R(0, initRuleAttr)?I(initRoadAttr, UNASSIGNED)ruleAttr, R(0, initRuleAttr)?I(initRoadAttr, UNASSIGNED)roadAttr): R(0, initRuleAttr)?I(initRoadAttr, UNASSIGNED)del R(0, initRuleAttr)?I(initRoadAttr, UNASSIGNED)== R(0, initRuleAttr)?I(initRoadAttr, UNASSIGNED)0 R(0, initRuleAttr)?I(initRoadAttr, UNASSIGNED)[R(del, R(0, initRuleAttr)?I(initRoadAttr, UNASSIGNED)ruleAttr)?I(roadAttr, R(0, initRuleAttr)?I(initRoadAttr, UNASSIGNED)UNASSIGNED)] p6: R(0, initRuleAttr)?I(initRoadAttr, UNASSIGNED)B(del, R(0, initRuleAttr)?I(initRoadAttr, UNASSIGNED)ruleAttr, R(0, initRuleAttr)?I(initRoadAttr, UNASSIGNED)roadAttr): R(0, initRuleAttr)?I(initRoadAttr, UNASSIGNED)del R(0, initRuleAttr)?I(initRoadAttr, UNASSIGNED)< R(0, initRuleAttr)?I(initRoadAttr, UNASSIGNED)0 R(0, initRuleAttr)?I(initRoadAttr, UNASSIGNED) R(0, initRuleAttr)?I(initRoadAttr, UNASSIGNED) p7: R(0, initRuleAttr)?I(initRoadAttr, UNASSIGNED)R(del, R(0, initRuleAttr)?I(initRoadAttr, UNASSIGNED)ruleAttr) R(0, initRuleAttr)?I(initRoadAttr, UNASSIGNED)< R(0, initRuleAttr)?I(initRoadAttr, UNASSIGNED)?I(roadAttr, R(0, initRuleAttr)?I(initRoadAttr, UNASSIGNED)state): R(0, initRuleAttr)?I(initRoadAttr, UNASSIGNED)del R(0, initRuleAttr)?I(initRoadAttr, UNASSIGNED)< R(0, initRuleAttr)?I(initRoadAttr, UNASSIGNED)0 R(0, initRuleAttr)?I(initRoadAttr, UNASSIGNED) The production rules for roads p8: R(0, initRuleAttr)?I(initRoadAttr, UNASSIGNED)?I(roadAttr, R(0, initRuleAttr)?I(initRoadAttr, UNASSIGNED)state): R(0, initRuleAttr)?I(initRoadAttr, UNASSIGNED)state R(0, initRuleAttr)?I(initRoadAttr, UNASSIGNED)== R(0, initRuleAttr)?I(initRoadAttr, UNASSIGNED)UNASSIGNED R(0, initRuleAttr)?I(initRoadAttr, UNASSIGNED)?I(roadAttr, R(0, initRuleAttr)?I(initRoadAttr, UNASSIGNED)state)

p9: R(0, initRuleAttr)?I(initRoadAttr, UNASSIGNED)?I(roadAttr, R(0, initRuleAttr)?I(initRoadAttr, UNASSIGNED)state): R(0, initRuleAttr)?I(initRoadAttr, UNASSIGNED)state R(0, initRuleAttr)?I(initRoadAttr, UNASSIGNED)!= R(0, initRuleAttr)?I(initRoadAttr, UNASSIGNED)UNASSIGNED R(0, initRuleAttr)?I(initRoadAttr, UNASSIGNED) Global goals Population density Highways connect peaks on population density map End of segment shoots rays across map; each ray is sampled and sample points look up population value Fitness of ray is the sum of the population values along a ray multiplied by the inverse distance of the corresponding

point on the ray Highway generation continues in the direction of the fittest ray Global goals Street patterns Configurable using street pattern control maps New York: Streets form blocks by restricting the length of a block and the angles that streets follow

Paris Concentric rings around a central point, connected by short radial streets San Francisco Tries to reduce the length of non-contour streets; uses gradient of elevation map Local constraints

Modify attributes (length, angle) of road segments in response to surroundings Make sure roads do not cross water and any other places youd expect not to find them Creates intersections with other roads Local constraints - intersections Dont want more dead ends than intersections Dont want intersecting segments without creating an intersection (node in the road graph)

3 rules: 2 streets cross: generate an intersection Segment ends close to intersection: join it to the intersection Segment ends close to another segment: extend it and create an intersection Modelling of Buildings Once the roadmap has been generated...

Allotments generated Geometry generated Buildings assigned textures Textures are semi-procedural Lowers memory cost Division into Lots City divided into blocks

Blocks subdivided into allotments Blocks assumed to be convex and rectangular Concave allotments forbidden Simple recursive algorithm Divide longest edges that are approximately parallel Stop when size less than threshold value

Allotments without street access or too small discarded Maximum building height from image map Building Geometry Parametric, stochastic L-System One building per allotment Each building style has own set of production rules Manipulate arbitrary ground plan

L-System modules: Transformation modules Extrusion module Branching and Terminating modules Geometric templates Final shape is ground plan transformed by L-System Building functionality not represented

L-System output fed to another parser which produces final geometry Building Geometry Example: Textures Detailed texture maps Pictures scanned, modified and mapped High workload much more time than geometry generation

Memory problems Procedural textures Address many of the above problems Cannot always model all the details Semi-automatic texture generation Layered Grids technique Generic Style Textures

Model simplified by 3 assumptions: Facades show 1 or more overlayed grid structures, with most cells having the same function Grid cells are influenced by surrounding cells Irregularities mostly affect entire rows or columns Hierarchical system based on Interval Groups Non-overlapping, ordered intervals

Combination of 2 groups forms a 2-D layer Changing a single interval changes an entire row / column assumption 3 Individual cells can still be accessed Layer definition: 2 interval groups Evaluation function, eval, between the interval groups Colour evaluation function, col

For a point p(s, t) where eval(s, t) = 1, p(s, t) is said to be active in the current layer. All active points are the active area If this set is partitioned, the partitions are called active grid cells If a point p(s, t) is active, col(s, t) is called Returns colour (or other values, such as

reflectivity or bump) Non-rectangular areas can be formed by assigning functions to the intervals Layerstacks If a point p(s, t) on layer l is not active, the point p(s, t) on layer l-1 is evaluated instead This allows for the construction of different grid-like

structures Functions operating between layers can be defined Evaluation Functions can be: A procedural texture An image map Another nested layer or layerstack L-systems reference Synthetic Topiary, by P. Prusinkiewicz, M.

James & R. Mch Proceedings of SIGGRAPH 94, pp. 351-358