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.

Realtime global illumination, sort of

I just added skylight to the realtime renderer. I am very happy with the results. In my opinion it adds a lot of depth, and it is quite fast to compute. You can see it here in two series of screenshots I took for a forest setting.

In each series, the first image is the final results, the second image is the contribution from the skylight and the third is the direct sunlight illumination:

Second series:

This is already looking good, and it runs in realtime. If there was some large character moving around in the scene, you would see its contribution to the shadowing.

The skylight is a standard shadow map, but it is sampled taking a lot of neighbors into consideration. This creates nice soft transitions between areas of light and penumbra.

There are no light bounces here, however. I have been toying with the idea of a screen-space radiosity solution. I think it is possible. If you know of any papers on the subject, please drop a link in the comments section.

As usual I look forward to your comments and criticism.

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...

Voxels in the wind

Fall is here and it is getting windy. It is a good time to finally add some animation to grass blades and tree branches.

 Here you can see some results:

   

There is nothing fancy going on here. The post title is deceiving since no voxels were animated, just traditional polygonal billboards. The motion is a few sine waves overlapping at different frequencies. The next step is to feed wind vectors to the vertex shader. This will create turbulence near cliffs and some other nice effects.

And then some leaves and other particles flying around for increased realism.

One last visit to the forest

Here is a slightly old video I took from the voxel forest. This one has a radiosity solution. It is still not there for me, it may be too dark, also it also has some bugs in the lighting of grass and canopies that I fixed after doing the video. Anyway I thought it could be entertaining to some of you.

More radiosity shots

Here is the rest of the radiosity screenshots I took over the long weekend. Keep in mind this only shows ambient light, this is why they are darker than what they should. Still a long way to go!

Radiosity Screenshot

Here is a quick update on the radiosity. In this image there is only ambient light. Sunlight will make it more interesting for sure.

20 Light Bounces

I rewrote the radiosity solution over the weekend, this time for the Voxel Farm. Here you can see some results for the same forest scene of the earlier video:

It is a bit tricky to understand the light in these pictures. Primary light sources like the sun and the sky are not shown here. You can only see the light that has bounced off the surfaces or went through the tree crowns, which are translucent.

There are no materials or any texturing. The green hue comes from the crowns and parts of the ground that are covered by grass. But don't pay too much attention to the colors. This was to see if the algorithm was working properly. Also keep in mind the crown polygons are there only to collect, scatter and reflect illumination. They are replaced by the instanced leaves.

I found I needed to get up to 20 bounces to get enough illumination down to the forest ground. Otherwise it was too dark.

The Faraway Forest

One recurring question about the trees and forests I am doing is how they will show in the distance, from how far you could see them. It is a real issue.

I chose a different approach for trees than most engines I know. In traditional engines, trees are done by instancing the same tree models many times over the landscape. Each tree instance is known by the scene management and rendering engine. If a tree is sufficiently distant it can be represented by a simpler instance. This works nicely even for distant forests, but it imposes a very homogeneous look for your trees. If you want very large trees with unique branches this becomes a problem. At some level of detail the unique tree needs to be replaced by an instance. The more unique the tree, the bigger the visual jump will be.

I wanted to take a different approach to instancing. I still use it, but for much smaller elements like grass, flowers, tree leaves and small branches. This means each tree has unique geometry. Trees are fairly complex objects, a distant forest could have thousands of them. How to overcome this?

Many years ago I was flying over the Amazon rain-forest. I could see a thick layer of tree canopies below and a thick layer of clouds above me. I was amused by how similar they were. I began wondering if a forest could be rendered as a volumetric object, more like clouds.

I also wondered if I could make tree canopies opaque. After all they are often so dense you cannot really see inside them. It would really cut the number of polygons. All the branches inside the canopy could be removed, only the larger branches supporting the canopy puffs would remain. Here is one example taken form a Voxel Studio mesh render preview:

When looking at this, keep in mind there is a missing layer of instancing that goes on the crown volumes. This is rendered pretty much like grass and flowers over the ground (which you also won't see in this picture). You will be able to see a lot of detail coming out of the tree crowns. The green blobs in the picture before are the base for this instancing. This basic geometry is from where leaves and small branches get their position and -very important- their illumination.

I liked the fact that tree identities would be lost in this gigantic cloud. The geometry of several trees could be merged and simplified together, there was no need to think of tree instances beyond the generation stage. Also it would be rather easy to perform light scattering in the canopy cloud. To me proper lighting was essential to convey the scale of the trees and how it feels to be under them.

This approach had some big issues too. It does not work very well unless trees have fairly thick crowns. You can have a lot of small crown puffs to represent sparse crowns, but this could hurt your polygon budgets.

Now comes the initial question: How does it look when trees are far away? This is where this approach can shine. Since there are no individual tree instances anymore, the volume can be simplified down to the levels we know will look fine on screen. Then the instancing of leaves and branches continues to provide detail on top of the simplified clouds.

The following images show how much the trees can be simplified. You need to remember that each consecutive level appears further away. When these meshes are rendered in their proper positions, you cannot really tell the coarse level is just a weird soup of polygons.

This is LOD 1, which is shown pretty close to the camera:

This is LOD 6, which shows a few hundred meters away from the camera:

And this is LOD 10, which appears at more than one kilometer away. As you can see, the forest has entirely blended with the terrain. This means the grown polygons are not rendered anymore, only the canopy layer remains visible:

Here you can see the same progression from a different point of view. The LOD levels are the same: 1, 6 and 10.

Hopefully I have answered that forest-in-the-distance question. This looks really nice when properly illuminated and adorned with instances. In the short future I will post about that.

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.

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.

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.

A Voxel Tree

This is just a teaser of a future post about procedurally generated trees. Here you can see an example of the trees I'm currently able to generate. I would have liked it to be a Christmas tree, but I cannot make evergreens right now.

You can click on the image to get a higher resolution view.

It is all voxels, which explains why the tree's crown looks a bit like a cloud. That can be improved at lot, this is something I will discuss later.

I am not using L-systems to generate trees. I did try it, but I was not happy with the amount of input that was required. When it comes to trees apparently there are bigger forces at work than just self-similarity and subdivision.

This is using a technique called Space Colonization. Although I modified this method to make it more efficient, you can find the basics here.