Tuesday, December 09, 2008

some procedural cities and architectures

  • Several papers state that game creators take a long time creating city artwork, but no one can cite how long it takes to create the cityscapes in recent games.

The current approach to 3D modeling is to manually create 3D geometry using tools like Autodesk Maya or 3ds Max [interactive visual editing of grammars for procedural architecture]
It can take several years to model detailed 3D land and cityscapes[procedural design of urban open spaces]

  • Presentation really matters - chucking the results through a global illumination renderer with (Sity, Mueller's stuff) instantly gives additional credibility to the project.
  • Other procedural architecture round-ups by Citygen people.
  • The two commercial projects (gamr7 and cityEngine) are European. woo! This means either the Americans haven't noticed this niche yet, or they don't think it's viable. Both companies have academic backers.
  • The unix command "pdfimages pdf-file output-directory-and-stub" is a great way to rip the images from pdf files. Sorry if anyone takes offence from me using their work here - the images give a good impression of what each project is good at. Shout (or leave a comment) and I'll take them down.

Example-Based Model Synthesis (pdf | doi)
Paul Merrell

Texture synthesis is a common technique for extrapolating 2D textures by incrementally adding bits of image. By choosing sections of image that are close to one another in the input, convincing textures can be built up. This paper (and the following one "Continuous Model Synthesis") extend the technique to 3D models very successfully. While not particularly to do with cities, all the examples are architectural.

This technique could be invaluable to artists as it wouldn't require many changes to the art toolchain - the technique can accept any model as input.

The input geometry is subdivided to blocks. These are analyzed to find allowable neighbors along each axis. To evaluate the model a search is performed to find configurations of allowable blocks. As with texture synthesis the output can be constrained to volumes force the structure to grow in a specific location.

Style Grammars for Interactive Visualization of Architecture (pdf | doi)
Daniel G. Aliaga, Paul A. Rosen, Daniel R. Bekins

This paper takes a different approach and shows a technique for semi-automatic extraction of a building grammar from a set of photographs. This grammar can then be applied to a stylize another block house model.

Several photographs are taken of the desired building. Then a simple 3D model is manually constructed, and aligned to the photos using a semi-automatic process - it's guesses become become better as more elements are aligned.

The paper then makes it appear trivial to deconstruct the given model into a grammar - admittedly taking some architecture specific properties into account. After orthogonal subdivision the layout of each floor is represented by strings. Analysis on theses strings with a few simple rules can produce the necessary grammar.

Obscured area of the input photographs have their features extrapolated from similar un-obscured areas.

Taking a bit of a tangent the paper goes on to describe several different rendering techniques are given at the end of the paper. Equalization of the textures ensures a constant colour over a facade.

Continuous level-of-detail modeling of buildings in 3D city models (pdf | doi)
Jürgen Döllner, Henrik Buchholz

The CityGML standard defines some city-centric extensions to XML and this paper presents a continuous LOD (level of detail) method for the generation of city buildings. The primary target of the work are GIS (Geographic Information Systems). The paper details the class hierarchy used to define each building, this corresponds to the more formal (but less readable) grammars in other work.

While the paper mentions straight skeletons it is ambiguous as to whether they are actually used. The final level of detail is given by texturing using a photo of the real world building.

The level of detail in the paper's title refers to whether a simple block model, the block model with a roof or the model with a roof and facade elements is shown. This isn't the same continuous LOD terminology used in video games, where one LOD would be expected to seamlessly morph in the next before the meshes where switched over.

This is a technique for manually constructing buildings.

Procedural Modelling of Cities (pdf | roi)
Yoav I. H. Parish, Pascal Müller

I've waffled on about this paper in-depth here.

It presents some techniques that have become very popular for generating roads, and some (later to be refined) methods of creating buildings.

The input supplied by the user includes geographic properties, such as valid city area (eg: not under water), a height map and a population density map. First major arterial roads are created by allowing roads to grow between population centers. This produces natural looking roads between the built up areas. Next a parallel L-system fills in the gaps between major roads with minor ones, using one of several models and self-sensitivity to give a connectedness to the otherwise tree-shape result of the L-system.

A shape grammar continually divides the volume made from the extruded footprint of a building to create a model of the building. By rendering different levels of this model, a level-of-detail (LOD) system is easily achieved.

One of the cornerstone papers in procedural urban geometry.

Instant architecture ( pdf | video | doi )
Peter Wonka, Michael Wimmer, Francois Sillion William Ribarsky

This paper details a grammar for the construction of buildings. A large library of components and a split (continuous subdivision) grammar a large design space is possible. A control grammar runs in parallel and distributes attributes spatially.

This system of attributes is the main accomplishment of this paper - it allows the design space to be purposefully evaluated. For example every element may have a "simplicity" value, and if the user asks for a "simplistic" building, this can be used to guide the evaluation of the split grammar. Other elements have attributes that ensure they are only used if there is sufficent space.

When all attributes are taken into account, there may be a tie-break between several rules. When such an arbitrary choice has to be made, the choice is "baked in" until the end of the evaluation of that particular building. So if a window type is chosen in a particular building, it will be used in all identical situations in the same building.

Some really nice façade results. The other cornerstone paper in urban procedural geometry.

Procedural Modelling of Buildings (pdf | doi)
P Müller, P Wonka, S Haegler, A Ulmer, L Van Gool

This is one of the papers that pushed Müller & Wonka et al. to the head of the field. Really impressive stuff that I'm going to be chasing for a long time. It outlines CGA shape, a shape grammar for describing buildings. There seems to be continuing work in this area developing CGA shape and it seems to produce some of the most convincing results out there.

The grammar is a shape grammar - one that continually subdivides volumes. It uses rules that replace one shape with one or more others, rules to subdivide over over absolute, scaled or repeated parameters and rules to perform functions on geometric primitives that allow a change in dimensionality (working in 2d for example).

These rules are fairly declarative ("if you decide to make a courtyard then this is how to do it"). There must be a large library of rules, painstakingly created.

Once these rules have defined a basic mass (the crude structure of the building) visibility testing occurs to retrieve a set of polygon faces that can be further processed for details. These include roof tiles or eves, doors and windows, all still produced using the shape grammar. Using features called snap-lines these are aligned to predominant architectural features.

The end results depends on the quality of the rule library, but it does produce some impressive results. This is a fantastic paper, and one that I've already started a more in-depth post on.

The work in this paper is extended (by morphable terminals) in the paper Procedural 3D Reconstruction of Puuc Buildings in Xkipché. CGA shape is again used in Procedural Design of Outdoor spaces.

Citygen: An interactive system for procedural city generation
George Kelly, Hugh McCabe

This screenshot doesn't really do the system justice. It allows interactive modeling of cityscapes - you can go in and tweak parameters for a particular regions and get real-time feedback. They borrow some elements from CityEngine (which is becomming the defeacto standard) namely secondary road generation using parallel growth and lot subdivision techniques.

The hierarchy used is to first create primary road, then secondary roads and finally buildings. The primary roads are generated between user defined juntions. Again, similarly to cityEngine, the roads "grow" by looking ahead to find desirable features (eg: least height differential). Finally they are smoother using splines. Some effort was put into investigating different functions of the height hight map when guiding roads.

The secondary roads are grown using a "parallel l-system", and produce a pleasing range of results between organic and ordered. Again as with CityEngine, snapping occurs when two secondary roads get close to one another. Work has been done on optimizing these tests a bit, but not so far as to use a quad tree or similar.

Pavements are created by shrinking the plot boundtry, although how the shrink is implemented isn't documented (I should just go and look at the src code). Block subdivison to plots occurs by repeated splitting of the entire concave block on a line between the midpoint and the centre point of the longest side. Sometimes this is modulated to occur more often on street-side properties.

Country houses are moved back from the street, while town houses are built to abut the pavements.

The buildings are currently simple extrusions that use texture and bump maps.

Roll A City
Graham Whelan, George Kelly, Hugh McCabe

A short paper that builds on citygen. Strangely they say the thing that they do differently is to not use statistical data as an input, then they use statistical data in the form of a height map. The user lays the main roads (yellow above) and then the detail is generated. This can then be edited, by creating new house grammars, or modifying one from an existing library.

Image based Procedural Modelling of Facades
Pascal Mueller, Gang Zeng, Peter Wonka, Luc Van Gool

This paper using procedural and image processing techniques to reconstruct 3d facades from a single low-res 2d image. Image analysis breaks the image down into and removes all repeated components (above, left). These are sudivided and matched against a library of 3d components by comparing the image to a rendered image of the 3d component. From here a grammar can be constructed to give the entire facade.

Procedural Inc.

This is the accumulation of Pascal Mueller's research in the form a company. Their major selling points are
  • Rapid Digital Prototyping
  • Shorter Time-to-Market
  • Cost Reduction
  • High-Quality Content
  • Redefine Design
  • Flawless Integration
Cost is $4000, and they seem to be pitching to a wide range of companies, everything from video games, architecture, archeology, simulation, film & tv. I'll write more once I've had a play with it on my PC

Introversion games
Chris, Mark, Thomas and John

This is a continuing video games project that shows some real promise. These guys are the heros on the indie-games network, unfortunately they seem to have grown up and moved from their bedrooms into offices. They don't seem to publish anything about their algorithms, but some of their videos are very insightful and of a higher quality than lots of the academic tat. Senzee has talked to them and say they're working from Mueller et al's excellent CSG and shape grammar stuff.

Lionel Barret, Bernard Légaut

A French company using a consultancy model. Like Procedural Inc. they have academic roots, but they are concentrating on the gaming market. There selling points seem to be:
  • Automatic Geometric adaptation
  • Automatic HeightField adaptation
  • Automatic LOD removal of objects
  • Exports to Collada for easy mockups and visualisation
  • Exports to xml for easy integration into pipeline
  • Heightfield Import
  • Configurable Forbidden Zone : Water, gameplay constraint
  • Configurable Road Newtork : Spline, Bridges, Etc.
They don't specify a cost, but this is normal for a consultancy. No very impressive screenshots from them; their buildings all look a bit too similar.

Sity Generator

eves variety

Rather depressingly my old school project doesn't look too out of place among these candidates. It presents some novel-ish techniques that simplify the control of complex architecture geometry generation. The skeleton algorithm is so well suited to architecture generation, I'm quite surprised it isn't used elsewhere (despite being a biatch to implement nicely ;). The design of the system is more heterogeneous - relying on the same {plane -> subdivision using voronoi -> extrusion using straight skeleton -> planes} cycle for everything from the city layout (admitedly not as nice as the grown cities, but lower effort) to the generation of garden walls.

It also featured concepts such as Wonka's "baking in" of random values when evaluating a grammar. But the baking wasn't limited to one-level of the grammar (the building in Wonka's example), but occured at several depths. For example the probability distribution of the type of building was baked in once per block.


  1. Hi Tom. I just found your blog, you have some very interesting posts. I've had a casual interest in procedural city generation ever since I had a play around with the Greeble plugin for 3DSMax. I've added your blog to my list of feeds and look forward to reading more. Nice to see this sort of work coming out Glasgow too :)

  2. That's really a very interesting harvest and digestion of city generation articles, so much to learn!. Nice job. I have my self a distinctly profound interest at procedural geometry. Here are some procedural geometry images from my last renderer engine called Raydiant.