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
Parish and Müller (2001)

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
Parish and Müller (2001)
Parish and Müller (2001)
  • 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):

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:

(Parish and Müller 2001)
(Parish and Müller 2001)

Street patterns — Examples

San Francisco
San Francisco
Sao Paolo
Sao Paolo
New Delhi
New Delhi
Tokyo
Tokyo

http://maps.stamen.com/

Implementation as parametric L-System

Original implementation by Parish and Müller (2001)

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 Sean Barrett (2008)

function generate() {
    let Q = new PriorityQueue<Segment>();
    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


Parish and Müller (2001)

  1. Recursively divide along the longest edges that are approximately parallel
  2. Discard all blocks that do not have street access

Architecture

Approaches:

  • L-systems (see Parish and Müller (2001))
  • Split grammars (see Wonka et al. (2003) “Instant Architecture.”)

Alternative Methods

Tensor fields

Chen, Guoning, Gregory Esch, Peter Wonka, Pascal Müller, and Eugene Zhang. 2008. Interactive Procedural Street Modeling. In ACM SIGGRAPH 2008 Papers, 103:1–103:10. SIGGRAPH ’08. New York, NY, USA: ACM. doi:http://doi.org/10.1145/1399504.1360702.
Chen, Guoning, Gregory Esch, Peter Wonka, Pascal Müller, and Eugene Zhang. 2008. “Interactive Procedural Street Modeling.” In ACM SIGGRAPH 2008 Papers, 103:1–103:10. SIGGRAPH ’08. New York, NY, USA: ACM. doi:http://doi.org/10.1145/1399504.1360702.

Time simulation

Weber, Basil, Pascal Müller, Peter Wonka, and Markus Gross. 2009. Interactive Geometric Simulation of 4D Cities. Computer Graphics Forum 28 (2): 481–92. doi:http://doi.org/10.1111/j.1467-8659.2009.01387.x.
Weber, Basil, Pascal Müller, Peter Wonka, and Markus Gross. 2009. “Interactive Geometric Simulation of 4D Cities.” Computer Graphics Forum 28 (2): 481–92. doi:http://doi.org/10.1111/j.1467-8659.2009.01387.x.

References

Slides including source code:

http://cities.studium.sexy

Parish, Yoav I. H., and Pascal Müller. 2001. “Procedural Modeling of Cities.” In Proceedings of the 28th Annual Conference on Computer Graphics and Interactive Techniques, 301–8. SIGGRAPH ’01. New York, NY, USA: ACM. doi:http://doi.org/10.1145/383259.383292.

“Procedural City Generation - Projects.” 2015. Accessed November 5. http://www.tmwhere.com/city_generation.html.

Sean Barrett. 2008. “L-Systems Considered Harmful.” http://nothings.org/gamedev/l_systems.html.