Seriously, Google, seriously

I apologize for going off-topic, but I find this rather amusing.

It seems Google's AdSense cannot figure out what this blog is about. For a long time now it has been showing ads about real-life construction, churches, Christmas trees, family trees, prune your trees. I just took this screenshot:

The funny thing is Google has all the information it needs to discover what the people who read this page care about. It seems they are just matching words and hoping for the best. If they were paying attention to the comments, all the posts, the links, they could figure it out. This blog is also hosted by Blogger, which is owned by Google. They could make sure there is good metadata for their engine to discover. There are even tags to associated to each post.

They say their algorithm is intelligent. I agree, only it is same level of intelligence that allows a dog chase its own tail for hours.

Writing Architecture

If you were the last person in the world, would you build a parser?

It is only me using this engine at this point. There is no UI for any of the things you can define for the virtual world. Not even configuration files, XML, INI, etc. It is all a  big soup of C++ code. To me it is the same to change a value in a C++ file than to edit a configuration file.

Then I started working on the architecture L-System. Soon I realized that writing grammars in C++ was not very good. They were extremely verbose and hard to read. It would be better if the grammar was written in a language designed just for that. For the first time in this project, I started considering parsing from an external file.

Luckily I remembered an old trick. I saw it long time it in ancient UI systems to define menu structures. The trick is to define functions that always return the state you are building, so you can chain their calls.

For instance, you can have a construct like:

begin("house").
divide_y("80% 20%", "living_area roof").
end();

It is really three functions being chained one after the other, but it looks like an structured construct. The "begin" function returns a new rule object with the specified name, in this case "house". Then the "divide_y" function is called in the rule to specify a house will be divided in two spaces, the living area and the roof. The function also returns the rule, so if we wanted to add more instructions we could do it right there. Then the "end" function returns the grammar object so a new rule can begin.

It is quite simple to use, the grammars are easy to read and you get all the help from the C++ compiler. Even the intellisense kicks in and gives you hints about function signatures. Also it allows to move into a different format in the future, even a dynamic UI. What changes is how the grammar objects are created, nothing more.

Just so you get a feeling of the written grammars, I leave you with the rules that define the church of my earlier screenshots. This is just the main module for the church. It references other modules that I did not include here. In a future post I will explain what these functions actually do.


begin("church").


// main space
push().
occludes().
center().
scale("90%", "100%", "70%").
box().
select("face_x", "nave_walls").
select("face_z", "nave_facade").
push().
move("0", "100%", "0").
loft_box("80%", "100%", "0%").
select("face_x", "thin_wall").
pop().
pop().


// transept
push().
move("10%", "0", "0").
push().
occludes().
center().
rotate_y("90").
scale("70%", "100%", "50%").
box().
select("face_x", "transept_walls").
select("face_z", "transept_facade").
push().
move("0", "100%", "0").
loft_box("80%", "100%", "0%").
select("sides", "thin_wall").
select("prism_sides", "prism_cap").
pop().
pop().
pop().


// towers
push().
move("0", "0", "100%").
push().
scale("tower_width", "300%", "tower_depth").
move("0", "0", "-50%").
module("tower").
pop().
pop().


push().
push().
scale("tower_width", "300%", "tower_depth").
module("left_tower").
move("0", "0", "-50%").
pop().
pop().


// apse
push().
move("20%", "0", "0").
push().
occludes().
center().
scale("130%", "100%", "130%").
ngon("18").
select("sides", "nave_wall").
push().
occludes().
move("0", "100%", "0").
move("0", "0.5", "0").
loft_ngon("18", "100%", "0%").
select("sides", "thin_wall").
select("prism_sides", "prism_cap").
pop().
pop().
pop().
end().

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 

Space Colonization

This is not about moving to Mars or terraforming. It is mostly about procedural trees.

Many things in nature are governed by one simple goal: Take as much space as economically possible. Before cities were intelligently designed, they would just grow following this principle. Streets wandered around  the terrain  forming a network that covered all available space. Similar networks are found in living things like blood vessels, nervous systems.

Trees develop in the same way. Their growth is determined by how much sunlight they can get. The better they expand in space, the bigger they become. You can argue that once you encounter an adult tree, it is there thanks to its successful colonization of the space around it. So somehow this principle is built into the tree.

But hold this thought for a moment. There is another approach to modeling things that grow. If you are into procedural things you surely heard of it: L-Systems. At their heart, they are just a way to describe how one thing can become a series of things over time.

For instance, a L-System may have a single rule that says a dot will become a dot and a line. If you start with one dot:

After one unit of time has passed, this dot is replaced by a dot and a line:

After another unit of time:

If we let this thing run for ten iterations, we will end up with nine lines and one dot. Even this very simple replacement rule has the ability to grow over time.

You could easily have a rule that produces branching, pretty much like a tree. If you say a stick will be replaced by three sticks:

It is not hard to imagine that with richer rules and better end elements that just lines and dots, you could grow something that is very close to a real-life tree. This is how many commercial-grade products generate vegetation, and they are very good at it.

The problem with L-systems is that it is their nature to blindly replace things. If you want them to become aware of external factors, like sunlight, presence of other objects or even be aware of themselves so a branch will not intersect other branches, you need to start tweaking them. Then they stop being so fun.

An algorithm that will use L-Systems to create a realistic looking tree is not trivial. While the basic branching idea of the tree is easily conveyed by the L-System, the system is not aware of the main forces that make a tree look like a tree.

Some folks at the University of Calgary saw this. They asked, what if you do it the opposite way. Instead of growing the tree from scratch and making sure it will grow the way you want, what if we start from the space we know the tree is going to take and just fill that volume.

The problem becomes about space colonization. This can be solved by an algorithm that is much simpler than extended L-Systems. You can see their paper here, but I will describe briefly how it works.

It starts by defining the volume the crown of the tree will take. The simplest volume is a sphere, just a point and a radius. The volume is then filled with random points. You can think of these points like targets the colonization algorithm will try to reach.

Then we add one segment at the base of the tree. From this point the tree will grow.

A segment has two ends and some length. Soon you will find that the average segment length will be in part responsible of the overall appearance of the tree. Smaller segments will result in curvaceous and intricate trees while larger segments will make for straight trunks and branches.

The two ends of the segment are of great importance too. For each segment end the algorithm will compute an attraction vector towards the cloud of target points. If there are target points close enough to the segment end, a new segment is added. The new segment will follow the same direction as the attraction vector at that point.

Whenever a segment end is too close to a target point, the target point is removed. As new segments are added in the direction of the target points, they end up eating all the points. Once there are no more points left, or they are too few of them, the algorithm is finished.

The results are very realistic. Branches naturally avoid each other, each one appears to have developed as the result of seeking sunlight. The same method can be used to create roots. Roots also expand in some form of space colonization.

The following image shows a tree generated with this technique. The ground is removed so the roots can be seen.

How many different trees can be achieved with this technique? Well there are many factors you can play with, like the size of the segments, the attractor vector cut-off zone and the distance where segments remove target points. On top of that you can introduce space warps that will mess up with attraction vectors. This can be used to simulate gravity for some heavy branches.

As you can see, the algorithm is pretty simple, still the results are quite good. I think this beats L-Systems for large trees. Next, I plan to use it for generating the chaotic layouts of old cities. When I get there I will surely post about that.

Open Hobby

Why not making  this project Open Source? I have received this question several times, either in comments, tweets or email. It is probably better if I address it in one post.

I could give a list of reasons why I'm not opening the code:

• Need to refactor and document what I have
• My OpenCL code is not good for every card out there
• Many features still in early stage (architecture, vegetation, city generation)
• My wife won't let me do it

The honest answer is I don't know. I have a very demanding job, whatever little time I have to spare, I use it in this project. I only do it because it relaxes me. Some people count sheep, I think about voxels.

If I made it Open Source, I would need to start thinking about other things. It won't be relaxing anymore, and I will probably find a different hobby.

Anyway there is a chance something will come out of this. Maybe a game and an engine, which I would have no problem licensing.