---
history: true
width: 1280
height: 960
margin: 0.05
theme: white
slideNumber: true
nocite: |
@subvimpl
bibliography: prosem.bib
header-includes: |
---
# Procedural Modeling of Cities
Press space to continue
##
**Goal**: _Automatic generation of a realistic-looking city
including road structure and buildings_
. . .
### Applications
- Entertainment (Movies, Games)
- Military training
- Land use planning
## Approach
1. Choose/Process input parameters
2. Generate street network
3. Evaluate building blocks
4. Generate building structure and architecture
Optional interaction between these steps
# Modeling of the street network
@cities2001
## Initialization
- begin with two opposite street segments
- greedily continue mostly straight from existing segments
## Branching
- branch with some probability at ≈ 90 degrees
## Street hierarchy
Primary, secondary, tertiary streets are used in urban planning
→ Simplified distinction between "highways" and normal streets
. . .
- highway segments are longer and branch less
- normal streets can only branch into normal streets
## Parallel growth
New potential segments are evaluated after existing ones
_red_ = current step
_green_ = next step
## Highway branching
Normal streets branching from highways have an additional delay (_blue_)
This prevents highways from being cut off by normal streets
## Conflict resolution
If a new segment
- is near an existing street: Adjust endpoint and create intersection
. . .

. . .
- ends in an obstacle (e.g. water, park): Shorten or rotate segment to fit
## Global goals (1)
Simplex noise
Population map (generated with layered simplex noise):
```javascript
function populationAt(x, y) {
value1 = simplex2(x / 10, y / 10) / 2 + 0.5;
value2 = simplex2(x / 20 + 0.5, y / 20 + 0.5) / 2 + 0.5;
value3 = simplex2(x / 20 + 1.0, y / 20 + 1.0) / 2 + 0.5;
return Math.pow((value1 * value2 + value3) / 2, 2);
}
```
## Global goals (2)
Highways try to connect population centers.
Possible new directions are sampled, the one with largest population is chosen

. . .
## Global goals (3)
Streets only branch if population is larger than some threshold:
## Global Goals (4) — Street patterns
Different patterns found in cities:
- Rectangular raster (≈ 90° angles)
- Radial
- Branching / random
![[@cities2001]](img/20151213214501.png)
## Street patterns — Examples




http://maps.stamen.com/
## Implementation as parametric L-System
Original implementation by @cities2001
```
w: R(0, initialRuleAttr) ?I(initRoadAttr, UNASSIGNED)
p1: R(del, ruleAttr) : del<0 -> e
p2: R(del, ruleAttr) > ?I(roadAttr,state) : state==SUCCEED
{ globalGoals(ruleAttr,roadAttr) creates the parameters for:
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)[i]
p3: R(del, ruleAttr) > ?I(roadAttr, state) : state==FAILED -> e
p4: B(del, ruleAttr, roadAttr) : del>0 -> B(del-1, ruleAttr, roadAttr)
p5: B(del, ruleAttr, roadAttr) : del==0 -> [R(del, ruleAttr)?I(roadAttr, UNASSIGNED)]
p6: B(del, ruleAttr, roadAttr) : del<0 -> e
p7: R(del, ruleAttr) < ?I(roadAttr,state) : del<0 -> e
p8: ?I(roadAttr,state) : state==UNASSIGNED
{ localConstraints(roadAttr) adjusts the parameters for:
state, roadAttr}
-> ?I(roadAttr, state)
p9: ?I(roadAttr,state) : state!=UNASSIGNED -> e
```
→ unnecessarily complicated
## Implementation with priority queue
originally from @harmful
```javascript
function generate() {
let Q = new PriorityQueue();
Q.enqueueAll(makeInitialSegments());
let segments = [];
while (!Q.empty() && segments.length < SEG_LIMIT) {
let minSegment = Q.dequeue();
// resolve conflicts
let accepted = applyLocalConstraints(minSegment, segments);
if (accepted) {
segments.push(minSegment);
// create new segments
Q.enqueueAll(globalGoalsGenerate(minSegment));
}
}
}
```
(+ a quadtree in _applyLocalConstraints_)
## Complete demo
(10000 segments, not full speed)
# Modeling of buildings blocks and architecture
## Input parameters
- Street network
- Building information (e.g. height / type / age)
## Lot subdivision
@cities2001
#. Recursively divide along the longest edges that are approximately parallel
#. Discard all blocks that do not have street access
## Architecture
Approaches:
- L-systems (see @cities2001)
- Split grammars (see Wonka et al. (2003) “Instant Architecture.”)
# Alternative Methods
## Tensor fields

## Time simulation

## References
Slides including source code: