Lean Trees

Trees with thin trunks are problematic for a voxel engine. The reason is aliasing. When the tree is far away you still see its crown, but the trunk may have disappeared entirely because of the voxel resolution cannot hold such a thin feature anymore.

I was not ready to give up on skinny trees. They are abundant in colder climates, definitively a must-have for the engine. After some kicking and screaming, I managed to get it done:

Let's see how.

This problem is linked to the sampling theorem and Nyquist frequencies. In a nutshell what this means is you can only reconstruct some information if your sampling frequency is at least twice of the information's frequency. If that sounds weird to you, you are not alone. As it turns out, we live in a freaky reality. Things, regardless of them being real or virtual, have frequencies sort of baked into them and their arrangements. In this particular case the virtual tree trunks had frequencies that were higher than the voxel frequency used to represent them. These trunks would just disappear.

As long as you use a discrete method, like pixels or voxels, to represent a continuous reality you are guaranteed to suffer from these aliasing issues. In the case of pixels, we solved this problem by just throwing lots of memory and processing power to it. With voxels, the hardware is still far from being there.

So this limitation will be there for a while. We better learn it well. Once you think about it, you see the limit is not really how thin a feature can be, but how close two thin features can be. If your voxel size is 1 meter, you can still do a golf ball with them. What you cannot do is have another golf ball next to it, unless you place it at 2 meters.

Maybe this image will help explain it better:

This image is a 2D representation of voxels, which are 3D, so you will need to extrapolate a little bit. The eight squares are voxels. The two red dots are two balls. Each voxel measures "d", which for the sake of argument we will make equal to one meter. We can engage voxels 1, 2, 3 and 4 to represent the first ball. This is how we can achieve a feature inside these voxels that is much smaller than "d". In fact, it could be really small, near zero.

So even huge voxels could encode a tiny feature. The real limit is how close the next feature can appear. In the image you see we cannot use voxels 2, 5, 4 and 7 to add another ball there. This is because voxels 2 and 4 area already engaged into expressing the first ball. So the closest ball can be placed two voxels away, using voxels 5, 6, 7 and 8. The distance between the two balls cannot be less than two meters, that is 2 times "d". This is the sampling theorem rearing its ugly head again.

But this was the key to my solution. Because of how forests are, I did not need two thin trees one immediately next to another after all. I just needed the thin trunks to align with the largest voxels that would still need to display the trunk. This involved shifting the tree a clever amount, which was never too much to disrupt the distribution of trees in the forest.

If you look at the forest screenshot again, you will see some fairly thin trunks in the distance. These trunks are an order of magnitude thinner than  the voxels used to represent them.

Voxel Studio Videos

Here are three videos I captured from Voxel Studio to help with the AiGameDev.com interview:

Fall colors

Here is a video showing the new skylight feature. Trees now can have different foliage. Adding fall colors was a nice way to test this. These trees share the same foliage texture, it is colorized on-the-fly by the shaders.

Realtime Shadows

I decided to give dynamic shadows a quick try. I used a shadow map with percentage-closer filtering to smooth shadow boundaries. The results are quite fast and smooth. The main trick was to run the shadow evaluation on the vertex shader. I realized I had enough vertex density for consistent results. The shadow interpolation between vertices would make the shadows even smoother.

Here are the results.

 

If you wait to the end of the video you will see there is some kind of mysterious object rising from the ground. This is unlike anything you have seen in my videos before. It certainly means something, a sign of things to come...

One quick session in Voxel Studio

As promised, here is a screen capture covering some other features in VoxelStudio. Here you will see terrain rendering happening on the Voxel Farm, also a glimpse of the tree and forest edition process.



I had only two nodes in the farm dedicated to rendering the terrain meshes shown here. A farm with four machines would have rendered twice as fast.

Trees in terrain preview

Here are some rendered trees. Keep in mind this is a preview to help the world designer choose the parameters for the procedural generation. The lighting is very poor. Also tree crowns appear as blobs in the preview, which is far from being realistic. These blob polygons are the base for instanced branches and leaves later in the client. This is similar to the grass I have posted in earlier screenshots.

Editing a Forest

My approach to forests is that they are emergent patterns. They appear out of the properties of the different tree classes. A tree class may use a density mask to tell the system where this type of tree does well. Altitude is one clear example. These masks, however, are a very broad brush. Several species may share the same mask values for very large areas, still their distribution within that area has to be realistic.

To achieve this, I use a simulation of the forest evolution over several centuries. This is something I described in an earlier post. There are two key parameters: tree maturity, which is the average age at which the tree starts producing seed, and average lifespan, which is for how long a tree is expected to live.

The whole world (12km x 12km in my tests) is covered by a single forest, which takes less than a minute to simulate. Even if it is a single forest to the simulation, it looks like different forests and types of biomes. By using the masks you can make sure trees gradually disappear in deserts, or that some species never crossed certain range of mountains.

You can choose to simulate much smaller areas while you are still tweaking the tree classes, the results are consistent with a wider simulation. It creates a very quick workflow.

In the following screenshots you can see a quick test I did with seven different types of trees. This can be improved a lot with more tree classes and more detailed masks, hopefully you get the idea:

Tree editor in Voxel Studio

Here is a screenshot of the tree editor in Voxel Studio:

You saw several trees taken from here a while ago. Now you can see some of the parameters that define a single Tree class. A lot of things to worry about, but most combinations result in believable trees.

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.

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.

Tree Bits

In an earlier post I mentioned that I was using a Space Colonization algorithm to grow trees. This was more about producing an internal representation of the tree, for instance a list of line segments describing the tree trunk and branches. Still somehow the tree needs to materialize into voxels. In this post I will describe how I have done it so far.

If you remember another post, at some point I had decided to go into a full isosurface representation of the world. This means that for any point of the 3D space a density value is defined. If the value is positive, the point is inside a solid. If it is negative, it is outside. And if it is zero, it means this point is in the surface and should be visualized.

The question is, how to create a density function that will result in a tree?

You will find two different entities in your typical tree: the leaves and the branches --which include the trunk as some sort of over-sized branch. It made sense that the tree density function was the sum of two different density functions, one for the leaves and one for the branches.

For the trunk and branches, the colonization algorithm was producing a series of connected segments. This was just a collection of start and end points. First I needed to compute the girth of each branch.


Long time ago Leonardo DaVinci noticed a rule about tree branches. It seems that when a branch splits into two or more branches, the cross-section areas of the new branches add up to the area of the original branch.

At the right you can see a doodle I took from his handbook that illustrates this point.

This is also called the pipe model. It kind of makes sense when you think most trees just need to move their juices up and down.


With this in mind, it is possible to back-track the hierarchy of connected segments starting from the thinnest and adding up the areas down to the trunk. A the end of this process each segment will have its starting and end diameters defined.

That was the easy part, but this is still far from a real density function.

If you remember yet another post, I was computing all the density functions using OpenCL kernels. Each instance of the kernel would take a point in 3D space and compute the density function.

I wrote a new kernel for a density function based on a list of segments. It is fairly straightforward to compute the value, as the following image shows:

Here the large dot is the point in 3D space we need to compute. The line coming out of this point is the shortest distance from the point to the segment. If you subtract the radius of the cone at that position from the length of this line you will end up with the distance from the point to the surface of the cone. This distance is the value of the density function for the field.

The tricky part is making this fast. In theory each point should be tested against each segment. For a high density grids and large number of segments the naive approach is just too slow.

The first obvious optimization is to avoid testing all segments. If only segments that are reasonably close are  tested it would make a big difference. So I stored  the segments in an octree and tested only those segments that were in the neighbor cells to the point.

To speed up access to the octree in OpenCL, I made sure I was moving the octree data into local memory before going over the list of segments. You can see this trick in the ATI Stream OpenCL examples, specifically the one about solving the N-body problem. This case is similar to the N-body, only that some bodies are points are some other are segments.

Now, this produced segments that were far too smooth. For pipes or columns they would be great. Tree trunks and branches are not that regular. I realized I needed to add some noise to the segment surfaces.

This was a rather small change. Instead of using the regular segment radius (noted as "r" in the image before), we can affect this radius by a 3D noise. For this to work, you need to pick the right coordinates to evaluate the noise function. A good approach is to use the point where the shortest line intersects the smooth cone volume, that is, the same point we were using  before to compute the density field. Using these coordinates we evaluate the noise function. This returns a value we can use to offset the radius of the cone and produce a new distance to the volume.

In the following image you can see the effect this produces. By playing with the noise type and properties you can achieve different effects. Instead of a noise function you could also use cellular fields like the ones described by Worley.

This works for branches, roots and trunks. What about the other half of the problem, the leaves?

I chose to address this in a peculiar way. Maybe my eyesight is not alright, but when looked from a distance, a forest looks more like a field of clouds than a massive collection of individual leaves. You can see the leaves as some sort of noise in the profile of the crowns. One of my goals is to have individual objects that are too distant still blend properly in the background, instead of just disappearing from the view.

Now this works only if the trees are healthy and full of leaves. It is a limitation of my approach. I will see how far I can go with this before considering an alternative. It becomes very apparent when you are really close to the leaves that they are just a really noisy volume.

I have an idea to address this, which is to render additional billboards on the client based on the crown polygons. This is similar to what most games do when rendering grass. I would render tree leaves instead.

With that out of the way, we can start thinking about the tree crown as a cloud. Its definition is quite simple, just a list of ellipsoids. When a branch ends, the colonization algorithm inserts a point in the cloud. The diameter of the ellipsoid at that point is a function of the size of the tree and how distant this point is from the main branches.

If enough ellipsoids are created they eventually blend into some sort of cloud. The density function of this cloud is computed in a kernel very similar to the one used for the segments.

Adding a lot of noise helps making the crown more interesting. This noise needs large low frequency amplitudes but also a lot of high frequency detail too. The low frequencies break the appearance of the base ellipsoids while the high frequency resemble the look of the individual leaves.

The following image shows the results:

I know there is a lot of room for improvement. I still plan to revisit the generation of trees. I want more realistic trunks and roots, and also create new types of trees.

As I said before, individual leaves will be rendered by instancing on the client. This should improve a lot the realism of this method. What you have seen here is rather the content generation side of it. I also plan to revisit the global illumination solution to add light scattering in the tree crowns.

Until then, I hope this will inspire you to make some voxel trees of your own.