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!
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
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 "di" 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 "dk" in the paper.
Here's the algorithm:
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.
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.
A video of the algorithm at work is here.
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.
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.
I'm impressed with how simple the algorithm is and how well it works. On the other hand, there are a few problems:
More to Do
Trees are obviously more than branches. After I get a branch algorithm I like, I have several more steps:
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.
blog comments powered by Disqus