Tuesday, February 22, 2011

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.

Wednesday, February 9, 2011

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.

Sunday, February 6, 2011

Another Church Screenshot

Here is another shot of the same church:



This time seen from a distance.


Recombining rules

This is the polygonal ouput of the L-system:


The same church rules, but combined in a different ways can produce different buildings, like the one below:




Saturday, February 5, 2011

The Missionaries Arrived

I have done my first render of some architecture. Here you can see the results:


It is some kind of Romanesque church. It is all made of voxels, so it is pretty much the same as the terrain and the trees I have shown before.

This church is entirely procedural. It was created by an L-System based on a series of grammar rules. The rules can be evaluated in many different ways, producing churches with many different layouts and sizes. Many of the rules can be used for other things than churches. For instance, the same towers could appear in a castle as well.

Artistic input is still required, but at a very generic level. The artist creates the basic building blocks like doors, windows and ornaments. Then they are procedurally recombined by the grammar. This way a few assets can spawn a large number of very different looking buildings.

The base assets are in polygonal form. This is so it is easier for the artist to create them. For this reason the architecture L-System outputs polygonal meshes. The meshes are then voxelized and blended with the rest of the terrain so it benefits from all the advantages of the voxel engine.

I have still a very long way to go regarding architecture. First I need to improve the grammars so I can also represent interior spaces. The interior of this church is not very good for instance. It has practically nothing inside. I also need to port the voxelization to OpenCL. I'm still running a CPU-bound prototype.

And one building is just the beginning. I want a complex network of interconnected cities. These doodles illustrate what I'm going for:




At this point I feel like the man who was carrying a brick so other people could imagine how his house was. But hopefully you will get the idea.

I will post soon about the L-System and architecture grammars. It was very interesting for me and it was one of the tasks in this project I enjoyed the most.