Hello Worley

If you are into procedural things you probably heard about Perlin noise. This noise function can be used to recreate many of the patterns you find in nature, like clouds, large mountain ranges, marble. While it is not the only way to produce them, it is probably the most efficient way to achieve very good looking results.

There is another type of noise that is as useful as Perlin noise: Worley noise, which is also called cellular noise. Here you can see how it looks like, compared to Perlin:

Perlin is great for phenomena that originated from mixing different entities, like how moisture permeates a wall or mold grows on a tree. Worley is best for self-organizing patterns, things that break down into clear boundaries like cells, pebbles and even man-made objects like a stone wall.

The idea behind this noise function is simple. The function field is scattered with random points, then for any point in space the function determines how this point relates to the nearby random points.

Unlike Perlin's function, which you may take as a magical black box, it helps to learn the implementation details of the Worley function. Many interesting effects can be achieved by using different criteria. One example would be to return the distance to the closest random point. This is the used in the image before. As you can see it outputs the Voronoi diagram for the field.

I had delayed including Worley noise in my terrain generator for too long. All the screenshots and videos I had posted so far were produced using only some form of Perlin-like noise. It was a long weekend, so while the wife and twins were taking a nap I pulled out the holy book for procedural content and went straight to Worley's chapter.

It only took a few hours to have his noise ported to OpenCL. Here are screenshots of a large rock formation out of Worley noise:

Here it can be seen in more detail:

Worley's algorithm is perfectly suited for parallelization. I only changed the criteria on which neighbor cells are visited. For a CPU implementation, Worley goes into an elaborate scheme to avoid testing points inside a cell if it can be early discarded. My parallel superstitious instinct told me this type of optimization would not carry well into OpenCL. If at least one of the points in the current wavefront hits the worst case scenario, then it was as if all the points were worst case scenario too. So I removed all conditions and went with the brute force approach. I do not have any numbers to back this up, however. I could be wrong.

Now I have this new toy and I keep thinking of shiny things I could build. It is that warm feeling a new noise function will give you.

Radiosity Teaser

I went back to do some improvements in my radiosity solution. I added several bounces to the light and also translucency for some materials.

The following render shows the effects of the new algorithm:

This is the light-map generated by the radiosity solution for the same scene:

As you can see there is a lot of color bleeding from the tree leaves into the walls. The light in the tree crown actually comes from the other side, which is directly hit by sunlight.

Soon I will be posting more details about this method. It is a hybrid between GPU and CPU. It is not realtime. A scene 100 meters by 100 meters takes around four seconds in an ATI Radeon 4770, Intel Core 2 Quad CPU at 2.8 GHz.

The Forest

If a voxel tree falls down in a voxel forest, does it make a sound? What if it is voxel Hellen Keller the one who falls?

Now that I had different tree species I began considering how to assemble them in a forest. In earlier screenshots and videos you could see some trees around, but they were just scattered randomly. A forest is something more. Even if it is not apparent at a first glimpse, there is some order and rules.

This post is about how I did it. I will start with a render of my first forest ever. The following image shows two different species of trees, one tall, one short, interacting together. As you may notice, while there is some randomness to it, there is also some order. Often trees of the same type appear closer to each other, but not necessarily every time.

Again the folks at http://algorithmicbotany.org/ had a pretty good idea of how to do this. There is one article about forests that helped a lot.

The approach is to simulate the forest for a long period of time, a few centuries maybe. This does not take much, since it is possible to do it in increments of many years at once.

The terrain is seeded randomly, but according to the odds for each species to prosper on a given location. Some species do not do well in high slopes, or some may get a boost from one particular type of terrain. The seeds are spread very close one to another. I found that a two-meter size grid was enough to produce realistic results.

Then the simulation starts. Each tree grows at every iteration. When a tree touches a neighboring tree, one of the two will subside. Usually the large tree will kill the smaller one. A tree will grow until it reaches its mature size.

On each turn mature trees spread their seed. A parameter in the tree class determines how far the seed can go, and what are its odds of surviving. If the seed lands on a open point in the grid, a new tree starts there.

The previous image shows the results of this algorithm over a few square kilometers of terrain. To show the properties of the algorithm, the terrain properties have no effect in this particular simulation. This is the result of 10 iterations over 300 years.

Only four tree classes appear here, but it is enough to perceive there is some character to how they spread over the land. The black dots are from a very aggressive species and will take any space they can. The cyan dots have still survived this and they have arranged themselves in some sort of vein-like pattern. The red dots belong to a species that is very large and grows fairly fast. Red dots also live longer. And you can see some yellow dots, this is a species that is doesn't compete that well so it depends on mostly on luck.

This is a fairly simple and fast method. It is somewhat reminiscent of cellular automata in the sense a tree will only interact with the neighboring space. Any order that may appear out of this is just emergent behavior. While the approach is local, it is possible to control global features by feeding different maps and having the tree classes react to it.

Once tree classes become aware of global parameters like terrain height, slope, abundance of water, shade, type of ground, even proximity to architecture, it is possible to have a single forest simulation cover the entire world. The global parameters would make a thick jungle develop in moist low grounds, while high altitudes will be covered mainly by pine trees (no, I still cannot do pine trees).

This is what I like the most about this approach. It produces a single organic layer. Even when there is a transition between different zones, it is still governed by the same rules. 

Is this the silver bullet method for forest generation? So far it looks like that.

Alter Ages

A friend is developing an interesting project. It is some kind of persistent, multi-player Civilization game. It is named "Alter Ages". You can sign up for the beta right now:

http://www.alterages.com

Depending on the size of the map, a single game could take up to a few hundred players. It can be played from your web-browser, but don't be mistaken, it is not like those old web-based strategy games. It feels more like a desktop game.

Beta will probably start in the summer. They are still working on it, mainly the graphics, but already looks quite interesting.

Mango, Sequoia, Baobab

At some point I was wondering if Space Colonization was all I needed for creating trees. Since the method was so simple, I always had my doubts. Could it be used to produce trees beyond the classic examples you see in the method's description?

I set out to define different tree classes, all using the same algorithm, just different parameters. Here are the results (click on the image to get a higher resolution):

In this post I will introduce the main parameters I used. As you will see, most of them control how the initial points for the colonization are seeded in space, the rest is colonization magic.

First there is the crown's envelope. The envelope starts from an ellipsoid. The class defines vertical and horizontal radii for the ellipsoid. In the next image you can see this large ellipsoid noted as (a):

A portion of this ellipsoid may be empty. This is noted as (c). This section may be quite large for some classes  like the baobab. The class also determines a proportion between the height of the trunk (b) and the size of the ellipsoid (a).

As points are randomly created inside the crown volume, the odds for a point to be added depend on another parameter: the "crown density". This parameter goes from zero to one. If it is close to zero, most points end up in the surface of the ellipsoid. If it is close to one, they are distributed evenly inside the ellipsoid.

The following image illustrates this effect:

Not all trees have this kind of elliptical crown. Many appear to have a number of smaller crowns, often showing some gaps in-between.

I wanted to have a simple definition for the class so I immediately ruled out any verbose approach. I realized that if I inserted the colonization tree points in an R-Tree and the clump the points on each node, it would naturally compact some areas of the crown. The clumps could also be shifted vertically to mimic the stratification you see in some trees.

I added two main parameters to control the clumping of the crown. One for the radius of the clumps, the second for how strongly the points will be pulled towards each other within the same clump. Then I added a third parameter: a probability that an entire clump may be removed. When an entire clump goes away it creates a natural gap in the crown.

The baobab class uses this to achieve the distinct look of its crown. The clumps appear as ellipsoids, noted as (d):

You probably remember Leonardo's observation about tree branching. For two branches splitting from one main branch, it stated that the cross-section areas of the two branches would add up to the area of the main branch. Something like:

Where a, b and c are the branch diameters as noted in the image.

Well, maybe Leo never went to Africa. The pipe model holds for trees that only care about moving stuff up and down. In some dryer places, trees also store water. This makes the trunks and some of the branches fatter. To account for this I added another parameter that controls the exponent of this equation. By default it is 2 which applies to most trees, but it opens many interesting possibilities as the fat baobad model above shows.

And that's it. There are some other parameters controlling the roots and venation, but they are quite similar to the ones I described above. One interesting addition to the algorithm is that now it produces very visible large veins along the trunk and main branches. I will cover this in a future post.

If you can think of a tree that cannot be represented by these parameters, just drop a comment here and point to the tree. I will try to reproduce it.