Procedural Architecture

I thought it'd be interesting to go back and review a bit of work I did for fun a few years ago. I'd been reading Shamus Young's excellent series of articles about building a procedural city. It fascinated me and I set out to make my own, but with a more realistic and less grid-like road network, inspired by Müller and Parish's paper on building cities. I documented it a bit in an earlier post.

Müller and Parish's work went on to be the foundation for Procedural's CityEngine, a product that included both procedural road grid and building generation. Procedural was later bought by ESRI and they're still actively developing CityEngine. We used it at Slant Six Games for an unreleased project set in a massive city in the post-apocalyptic future. CityEngine worked well for us.

But prior to that project at Slant, I was still messing about with my city generator, and road networks were only part of it. I wanted interesting buildings. Shamus Young came up with some interesting randomized building design algorithms, but I was fascinated by the "CGA Shape Grammar" language built into CityEngine. (CGA stands for "Computer Generated Architecture".) I wanted to make my own CGA Shape Grammar parser.

Implementation

I used standard flex and bison to parse CGA. There are certainly newer and fancier frameworks for language parsing, but I already knew how to use flex and bison quite well, and the CGA Shape Grammar language didn't have any particular complications that would have prevented me from using them. Also, flex and bison have the advantage that they generate C code and don't require linking with any external libraries, so the end result is easily maintainable and fairly future-proof.

A CGA program defines a series of rules to transform shapes into other shapes. So, for example, in my editor, we start with a "Lot" shape, as defined by the lot editor.

To transform it into a box, we'd do something like:

Lot --> extrude(20) Box

The CGA language defines a series of operators and functions, of which I implemented just a small subset of. But I tried to focus on the most commonly used ones:

• transformations: scale, rotate, translate, center, alignScopeToGeometry, alignScopeToAxes
• basic math functions (sin, cos, abs, sqrt, etc.)
• shape modification: extrude, split, setback, comp
• visual: color, texture, projectUV, setupProjection
• import OBJ files

With those basic functions and operators, you can actually create a huge variety of buildings. House shapes are problematic, because I didn't implement a gabled roofs operator, but office buildings are trivial.

Here's an example of a simple CGA program using some of those functions and operators. It uses recursion to create an interesting geometric shape:

attr ErkerFact = 0.8
attr ErkerDepth = 0.8
attr ErkerStop = 2

Lot-->
   extrude(10)
   X
   comp(f) { all : Erker }

Erker-->
   case(scope.sx > ErkerStop) :
      s('ErkerFact, 'ErkerFact, 0)
      center(xy)
      extrude(ErkerDepth)
      X
      comp(f){top : Erker}
   else:
      NIL

The resultant shape looks like this:

Editor

I wrote the editor UI side of things in C#. This was written a while ago, and these days I'd probably use Qt and C++11 to keep it all in one language (the core geometry manipulation code is all C++), but back when I originally wrote it C++ and Qt weren't nearly as elegant as C# .NET.

I broke the UI up into three windows:

• The editor window. This is where you'd edit your CGA Shape Grammar program.
• The Lot window. This is a 2D representation of the building lot that your building will grow out of. Changing the shape of the lot will change the shape of the building.
• The preview window. This shows the results of the CGA program applied to the Lot.

When I wrote this, I was incredibly inspired by [Bret Victor's video "Inventing on Principle". It's a fantastic demonstration of his vision for the future of programming (and more). Many others have since copied aspects of it (Khan Academy, for example), and I too wanted to see if I could use some of those ideas in my own editor. To that end, I implemented the following two features:

• The CGA Shape Grammar program in the editor window is compiled with every keystroke. If the resulting program compiles successfully, the result is displayed in the editor window. If not, an inline error message is displayed at the point of the error.
• Placing your cursor on a value in the program and holding down Ctrl will allow you to scrub the value to tune it in real time and see the results.

The above changes feel great in practice, and they really differentiate it from CityEngine itself, where you have to press a "compile" button to see the results.

Here's demo of the editor in action, where I show off a bit of what it can do: