I'm going to talk about shape grammars (split grammars, place grammars), in particular their application to procedural 3D content generation as presented in the paper "Procedural Modeling of Buildings" by Müller, Wonka, et al. This was a landmark paper (along with the 2003 "Instant Architecture") that is still the state of the art in some ways. There might be some digression into general grammar-driven generation, especially for automatic test generation, since it's a broad and interesting topic.
The primary paper I'll be discussing is available at
The author's site,
is a great resource for papers related specifically to building and facade modelling, including a paper, "On-the-fly Generation and Rendering of Infinite Cities on the GPU", which refers to the paper Peter Zion presented last month on dynamic GPU memory allocation. Of special interest, too, is Inverse Procedural Modeling, on which much work has been done in the last few years and which builds upon the use of shape grammars.
I also considered presenting Stiny's original paper, which is available along with a bibliography of more general shape grammar papers (some of which I'll be mentioning) at
Finally, for some motivating examples, here is a 64k demo (i.e., the program which produces this output is only 64 kilobytes, and does it in realtime!) that has some characteristic shape grammar effects:
And here are some examples from someone's work-in-progress game involving procedurally-generated sprawl: