Home       About Me       Contact       Downloads	Part 25    Part 27

As I mentioned last part, I'm busy cleaning up and extending the framework code I've written so far. But I also found a bit of time to play with generating trees. Well, branches at this point. There's a lot to do for a convincing tree!

Fig 1: Project Frontier trees (click for full size)

Fig 2: Procedural World trees (click for full size)

Over at TwentySided, Shamus Young has recently done trees for his Project Frontier. He is keeping his trees simple (see Figure 1). From the writeup, it looks like he creates a trunk, recursively branches a time or two, and then slaps one of a number of crowns of leaves on top. Add some hanging moss and he's done. It looks nice and fits the style of his world.

At the other extreme, we have Miguel Cepero at Procedural World, who is generating trees like the one in Figure 2, which match his awesomely detailed world. He's using an algorithm called "space colonization" to generate the branch pattern. It looked interesting, so I decided to try implementing it.

The "Space Colonization" Algorithm

The algorithm is described in Modeling Trees with a Space Colonization Algorithm, by Adam Runions, Brendan Lane, and Przemyslaw Prusinkiewicz. It's very readable.

Older algorithms start from the bottom and branch the way Shamus is doing. When I tried generating floating island/trees for my "gas giant" world, I did the same thing. The problem you run into is that the branches start to hit one another fairly quickly. It's also hard to control the overall shape of the tree, since it's not clear how branch points, angles and lengths are really going to add up to a complete tree shape.

The colonization algorithm works the other way, by starting with a shape and then generating branches to fill it. After all, the "goal" of the tree is to put a bunch of leaves in the air where they can catch the sun. The branches are just the supporting structure for those leaves.

So we have a collection of "attraction points" that define the shape of the tree. I was thinking of these as leaves until I implemented the algorithm and realized that isn't really right. Still, call this list of points LEAVES. Each "leaf" has a location point and the index of the closest branch segment.

Then we have a collection of branch segments. Each has a location point, and the index of its parent. The first branch point has no parent. So working back from the end of the list, you could draw the entire set of branches, connecting each branch point to its parent branch point. A branch also has a point GROW_DIR, which is where new branches are created, and a count, GROW_COUNT. Call the list of segments BRANCHES.

Finally, we have three distances. GROW_DIST is the amount we are going to grow a branch on each iteration. This is "D" in the paper. MAX_DIST is the maximum "influence" distance between a branch point and a leaf point. This is "d_i" in the paper. And we have MIN_DIST. When a leaf is within this distance of a branch, it is removed from the set of leaves (it has been reached by a branch.) This is "d_k" in the paper.

Fig 3: Space Colonization in action

Here's the algorithm:

1. Generate a cloud of points at random in the shape you want to fill. A sphere will do for your first experiment. Put those in LEAVES. These are the green dots in Figure 3.

2. On the ground beneath your points, start the first branch segment. Stack a few segments on top of it to make a trunk for the tree. Each segment will point to the previous one as its parent. Make sure the top branch segment is within MAX_DIST of at least some leaves. These are the brown segments in Figure 3.

3. Now for each leaf in LEAVES, compare the leaf to all the BRANCHES and get the direction vector DIR (leaf pt - branch pt), and the distance DIST (length of DIR.) These are the lines in Figure 3.

   If DIST < MIN_DIST, remove the leaf from LEAVES. It has been reached. If DIST > MAX_DIST, skip comparing this leaf and branch. They are too far apart.

   As you compare a leaf to all the BRANCHES, track the closest branch segment and the DIR and DIST to that segment.

   After you have the closest, normalize the direction by dividing DIR by DIST. Then add it to GROW_DIR of the closest branch. Increment the GROW_COUNT of that branch.

4. After you've compared all the leaves to all the branches, go through the list of BRANCHES. The ones with GROW_COUNT > 0 are going to sprout a new branch. Divide GROW_DIR by GROW_COUNT to get the average direction, then normalize it (divide by length.) Take the position of the branch and add this new vector to get the position of the new branch. Initialize that new branch and add it to the list.

   Reset the GROW_DIR and GROW_COUNT of the existing branch.

5. Loop back to step 3 until you are not adding branches any more.

Fig 4: Failed colonization

Unfortunately, there is one pathological case in this algorithm. If you have two leaves on opposite sides of a branch point, the average direction will be not be towards either leaf (see Figure 4). Then the branch grows away from the leaves. On the next iteration, the two leaves will still be closer to the original point and generate the same segment again, producing an infinite loop.

This problem isn't mentioned in the paper, but seems to be fundamental to the algorithm. With lots of leaf points (thousands), it doesn't happen often, since a new branch segment eliminates many points at once. When testing it with a handful of points, it happens a lot. I'm not sure what the easiest way to detect this condition would be.

Rendering

Obviously,we don't want the stick figure branches of my 2D example. To get a realistic looking branch size, you can pass over the branch segments and increase their size as they join.

The "pipe" model of tree branch sizes says that when a branch splits, the cross section of the pieces equals the cross section of the original. If you think of the branch as a pipe, the smaller branches have to carry the same amount of water, so they will add up to the same area as the original branch.

To compute the size of all your branch segments, keep the radius squared (call it AREA) in each segment. Initially, these are all zero.

Loop through the BRANCHES list from the end. If AREA is zero, make it the minimum size you've picked (a tiny branch.) Then add the AREA of the branch to the AREA of the parent (which will be earlier in the list and not yet seen.) Continue in reverse order to the start of the list. When drawing, set the radius of the branch to the square root of the AREA value.

Done in three dimensions, it looks like Figure 5.

Fig 5: Colonization in 3D

A video of the algorithm at work is here.

Variations

This algorithm is very flexible because of your nearly complete freedom in initializing both the cloud of "leaf" points, and the initial set of branch segments. For example, you could have multiple trunks. The algorithm is just going to grow the segments nearest the leaves, and so multiple trees will grow into the same cloud. See Figure 6.

Fig 6: Multiple trunks

Unlike placing multiple trees in one area, here the branches will not interfere, since they competed for a single set of leaf points. With the right set of points and initial branches, you should even be able to do topiary figures. You should also be able to create tree roots, with a second point cloud below ground. This would be useful for trees with partially exposed roots.

This algorithm should work as well for other kinds of plants with branching stems, so shrubs and even ivy should be possible. You could do other branching structures such a leaf veins (the original inspiration for this algorithm) and blood vessels.

On Procedural World, Miguel Cepero complains that it doesn't do pine trees. I think if you grew the central trunk, adding a layer of leaf points and radial branches at the bottom as it grows, you might get the right look. I haven't tried it.

Problems

Fig 7: Seems reasonable

Fig 8: What kind of point cloud to use?

I'm impressed with how simple the algorithm is and how well it works. On the other hand, there are a few problems:

• I really want to be able to generate points, then just run the algorithm until no more branches are generated. I have to come up with a fix for the infinite loop described above.

• To get a nice branch, you want to use a lot of points and very fine steps (small GROW_DIST). But since you are comparing every leaf to every branch for hundreds of iterations, this is a lot of computation. I need to use a fancier data structure to cut down on the number of leaf/branch segment comparisons.

• There's no control on how often a branch can split. That seems to produce a lot of little twigs.

• Some trees branch very low in the trunk, away from all leaves. To get this effect, you'd have to create a cone-shaped volume of "leaf" points, different from where you are actually placing the leaves. I have yet to try that.

• Looking at real trees in my neighborhood, it would be a challenge to produce some of them. Figures 7 and 8 show the variation.

More to Do

Trees are obviously more than branches. After I get a branch algorithm I like, I have several more steps:

• Leaves are going to be a challenge. So much of the look of a tree depends on the shadowing of leaves on one another. At a distance, all kinds of tricks would work, but if the player can walk up to the tree, it gets a lot harder.

• I need to come up with some bark textures I like. I'd like to generate them procedurally, since there's a lot of variation even on a single tree.

• I need to render this all efficiently, both up close and at a distance. Shamus just reduces the polygon count on his branches, while still rendering every branch. Eventually, he flattens them to billboards. Miguel seems to rebuild the entire structure as a lower polygon count shape and texture map, here.

• Trees need to be placed in forests, or at least groups. I'm not sure if I should try to render small groups of trees together using the algorithm, or worry about overlapping trees.

I'll release this as a demo once I solve some of these problems. I'd like a small forest you can walk through as a test case.

Home       About Me       Contact       Downloads	Part 25    Part 27