Monday, March 14, 2011

Little Blue House on the Prairie

This post will introduce the L-System I used for the architecture generation. My system is still far from complete. While it is fairly good at producing the outside of many different types of buildings, it does very little about what is inside. That is the big next step for me.

If you remember an earlier post, an L-System was a set of rules that described how one thing could be replaced by other things, which in turn are replaced again and so on. This resulted in fairly complex structures which went beyond the apparent simplicity of the individual rules.

L-Systems are often associated with trees and botany, but they really apply to anything showing any sort of structure. For instance you may say any book is a series of chapters, each chapter is a series of paragraphs, each paragraph is a series of sentences, each sentence a series of words, each word a series of characters. If you were to write these as rules it could be something like:

Book = repeat(Chapter)
Chapter = repeat(Paragraph)
Paragraph = repeat(Sentence)
Sentence = repeat(Word)
Words = repeat(Character)

Then a Character would be just one instance of multiple choices:

Character = instance("A"..."Z")

Of course there are other rules at play. The structure of the sentence includes other symbols like spaces between words, there should be titles for chapters, etc. Our basic set of rules could be extended to:

Chapter = Title + BlankLine + repeat(Paragraph + BlankLine)

Sentence = repeat(Word + Space)
Title = Sentence
Space = instance(" ")
BlankLine = instance("\n")

You will see that these rules use two special commands: "repeat" and "instance". What they do should be evident by now. Repeat can be extended so it will include a minimum and maximum number of repetitions. That way you can hardwire some boundaries into the rules so for instance words and paragraphs will contain a natural number of elements.

What if we want to have a table of contents at the beginning? A new command could be helpful: "split". The book rule could be rewritten like this:

Book = split(TableOfContents, Contents)
Contents = repeat(Chapter)

In most books the words and sentences actually make sense. We will ignore that for now. Note that given enough time and processing power, even this simple system will inevitably produce Tolstoy's War and Peace. It deserves some respect already.

But this accomplishes only one half of the task. So far what we've got is the "definition" of a book. Somehow these rules need to be expressed into something you can read.

The expression algorithm would execute the "instance" commands and produce something tangible. It could be very simple: just output the character to screen.

Any L-System will show the same dichotomy. One side of it deals with the representation of the rules while the other side deals with their manifestation. It actually helps to keep both sides as independent as possible. In the book example, you may later devise very nice and ingenious ways to visualize the book, or maybe read it aloud. This would affect only they way the instances are expressed, but would have little to do on how books are represented or even generated.

Now let's say you want to adapt this system to produce architecture. Instinctively you may say that a building is a series of spaces, each space is delimited by a series of walls, a wall is a series of elements like doors, windows, ledges, ornaments. Will it work?

It may seem simplistic at first, the trick lays in the definition of "space". A very simple house can be defined by two main spaces: a box for the house and a prism for the roof:
So the simple house rule could be something like this:

SimpleHouse = split(Box, Prism)

Then for each space, we could target each one of its faces. We can choose to replace each face in the box by a new rule that we will call "WindowedWall":

Box = split_faces(WindowedWall)

Note there is a new command here: "split_faces". This is like split, but it will operate on the faces of the volume. This is a very powerful operation, it is what allows the rules to move from the generic spaces and start targeting the different facades of a building.

Then WindowedWall can be defined as a repetition of windows:

WindowedWall = repeat(Window)

The "repeat" command will fit as many windows as possible in this space. It will look like this:
The split_faces command could assign a different rule to different faces in the current volume. This way one of the faces could become the entrance of the house:

Box = split_faces(
  Entrance, 
  WindowedWall, 
  WindowedWall, 
  WindowedWall)

Entrance = split(WindowedWall, Door, WindowedWall)

So our little house would get a door:
What about a roof? For that we would need to select the faces in the top prism:

Prism = split_faces(Roof)

Actually by providing several rules to the prism split, we could add a chimney and a little attic window too:

Prism = split_faces(RoofWithChimney, Attic, Roof, Attic)
So far you may be thinking this can only produce the same house. Well, depending on the initial sizes of the box and prism you will get a different number of windows. The door may be placed at a different position on each case. Then you may have different angles in for the roof.

But you are right, there is little room for variation here. The L-System becomes very powerful when you add randomness to it. For instance, you could either choose to have a chimney, no chimney or a UFO landing pad:


This is probably enough for an introduction. The system I'm using is actually a lot more complex and I intend to cover it in future posts. Still it is based on the principles described here.

For additional reading, I really recommend: Procedural Modelling of Buildings 

9 comments:

  1. I've become highly interested in L-Systems and their applications. Enjoyed the post and look forward to future post on the subject.

    ReplyDelete
  2. Out of curiousity, is the top-down composition an aspect of your implementation, or just presented here for clarity?

    Conceptually, bottom-up seems to make more sense to me.

    ReplyDelete
  3. @Alex: Yes, it is Top-Down for me. I think this is the typical approach when it comes to architecture. It also ties very well into the generation of entire cities, which is also top-down. The city generation ends by defining lots for individual buildings. The architecture module takes the lot space as input and breaks it down.

    ReplyDelete
  4. Interesting. I wonder if it's indicative of how I code that I can't quite get my head around how that approach would work :)

    I'm looking forward to seeing how it all hangs together. Thanks for the response.

    ReplyDelete
  5. Hah sweet. The resources and references you link to are great because you already have proven that they work.

    ReplyDelete
  6. I've always been fascinated by procedural generation, and looking at your work I'm curious about something. You said you were planning to have interconnected networks of cities, and I assume you're designing your generators to create coherent architectural and city planning styles of some kind.

    Have you considered training the generators to create and maintain separate discrete styles? It would be very interesting to see each city/region/culture have a procedurally selected library of architectural components used in their structures. You could modify basic constants like roof height and various proportions to produce distinct cultural styles as well.

    ReplyDelete
  7. @NeoSonic: In theory, yes, I would like to cover different styles. I don't know how much time I will have to write the grammars for the first iteration of this world. And it is not only the grammars, I also need to create the individual elements like windows, doors, columns, etc. I'm stariting with western Classical (Greek and Roman), Romanesque and Gothic. Then if time allows I will go into North African for the desertic areas.

    It is not only possible to keep clear boundaries between buildings of different styles, the best part is they can be blended in the same building. For intance you can have a castle that has a style that is between Romanesque and Gothic. Or a Romanesque cathedral that shows North African influences.

    ReplyDelete
  8. Hi MCeperoG,
    just a hint: the link to the paper/website is broken.
    Keep up the good work!

    ReplyDelete
    Replies
    1. It can be accessed here http://web.archive.org/web/20090228081605/http://www.vision.ee.ethz.ch/~pmueller/wiki/CityEngine/PaperBuildings

      Delete