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.
Thanks for the write-up, very interesting stuff, and nice pictures to boot!
ReplyDeleteFor added realism, perhaps you could also add a low frequency 'disturbance' factor, to simulate broken twines early in the growth of the tree, bark diseases, lightning strikes, bird nests, etc.
Also, a shadow-volume could influence areas that recieve less light, and thus are less favorable in the space colonization algorithm.
The thing is, with algorithms like the one you've described, running it a few thousand times will generate a world in which everything still looks uniform somehow.
Getting a realistic picture requires small variations (some not even immediately recognizeable to the human eye) to not only give each entity a unique look, but also to form a characteristic 'feeling' about a group of entities - a forest in Greenland will have a different look from a forest even from the same type in of Brazil (and I'm not just talking about snow here ;-)). But the same principle applies to other procedurally generated entities too - continents, mountains, canyons/ravines, landmass, beaches, rivers, smaller vegetation, animal flocks, roads, cities, planetary systems, etc.
Good luck with your experiments - what's going to become of it btw?
@Patrick: How about squirrel nests? I can see one from my window.
ReplyDeleteThanks for the insight! Procedurally generated content interests me a loot and it's always great to learn about new ideas.
ReplyDeleteI'm going to have some demo videos of my work soon like you asked about a while ago.
ReplyDeleteOh and a little bit of what you touched on in this article reminded me of a flash project I made a while ago. Its a 2D gravity simulator. So each object exerts a force on every other object. It reminds me of your "attraction vector".
http://coreyfleming.com/Portfolio/WebDev/GravityBall/GravityBall_14_Mod_A
The same algorithm also works for simple enemy AI
Hi there, I found you through Rock Paper Shotgun. Your posts are very interesting, although I struggle to understand some of the detail!
ReplyDeleteWould it be not-fun to introduce cut-rules (like Prolog) to L-systems? EG:
A -> AB => A...AB
A -> AB; AAAAAB -> ! => AAAAAB
That looks pretty dull, how about:
A -> ABAB => ABABBABABBBABABBABABBBBABABBABABBBABABBABABBBB
A -> ABAB; BB -> ! => ABABBABABBABABBABABBABABBABABBABABBABABB
I think you could use this to 'switch system' part way, making better leaves. I suppose this has been thought of decades ago - maybe you're already doing it.
L-systems are deterministic, what techniques do you use to introduce variation?
Could the space colonization approach be improved by making the random points less random? Maybe generating the points from a mutated L-system, or using less initial points but generating secondary points outlining a pattern at each primary point?
@Alexis: There has been a lot of research around L-systems. Your ideas about switching and termination have been developed already. They are actually needed if you want to get something half-decent out of the system.
ReplyDeleteYou can build a lot of randomness in the system. First you can make rule replacement random. You can add a probability value to each rule, for instance:
A -> AABB 70%
A -> B 30%
This means the second rule will be used approximately one third of the time.
You can also add randomness to the way the system is expressed, that is converted into something you can see. For instance, some of the symbols in the system are for rotating and translating. You could add some degree of randomness to the amounts involved in these operations.
The no-fun side of them I was trying to point out was that they by definition lack awareness of their environment. Let's say you create the rules to generate a tree. Even if you cover from roots to leaf venation, nothing in the rules will prevent one branch from intersecting another. This is because rules are about replacing one entity by a series of others. So you need a parallel mechanism that will kill branches as soon as it realizes they are growing in an inconvenient direction. This is the no-fun part.
I use L-Systems extensively for architecture. I had to build-in many of these artificial constraints, otherwise you would get very crazy architecture, like a window that is partially crossed by a wall. For mature trees, I found the
Space Colonization approach a lot simpler. You do not need to worry about any of this.
As you noted, Space Colonization is a technique that is orthogonal to L-Systems, meaning you can combine both approaches and have very interesting results.
One of the things I'm working on is to have the architecture L-System produce the input for the space colonization. So for instance the L-System will produce the volume for a cathedral, but then instead of having any walls, I could have vines grow in this space using Space Colonization. You would end up with a building that appears to be entirely made of vegetation.
Or you can have some sections of a building represented by the space colonization. Imagine a factory, you could have a lot of pipes covering entire areas. The space colonization will make sure they look intelligent, you would only need to tweak the algorithm so the pipes always turn 90 degrees.
That's fascinating, thank you for your response. I hope you will post some screenshots of those examples :)
ReplyDeleteHave you thought about damaged models? Ruined churches, pockmarked landscapes, water erosion, tree struck by lightning etc. Would you implement that kind of thing as a second stage or different generational rules?
This tree-growing algorithm looks like a close relative of "rapidly exploring random trees". It's also very similar to leaf venation algorithms, e.g.:
ReplyDeletehttp://algorithmicbotany.org/papers/venation.sig2005.pdf
James, actually it's not surprising since (venation) both papers were written at the same lab ...
ReplyDelete@Alexis: I'm definitively going for ruins. I will use some sort of noise and subtract it from the voxelized architecture. This same value can be used to add rubble on the ground. I'll post on this as soon as I have something to show.
ReplyDeleteSearching for the closest branch in the space colonization algorithm can take a lot of time without using any type of space partitioning.
ReplyDeleteWhat method do you use to accelerate this step?
Well it is the opposite, a growing branch looks for seed points in a "kill" neighborhood. Anyway you need some spatial index to accelerate this. I use RTrees.
DeleteYes sorry, you're right. Thanks for the fast answer!
DeleteI have a working implementation of space colonization, but would you mind posting a brief pseudo-code or the steps necessary to include RTrees in the algorithm? I also have a working RTree class with all the needed functions.
DeleteFor example, how should I assign the rectangles, index, etc?
Each point goes into the RTree with a little epsilon margin around it. They are tiny rectangles.
DeleteThen the RTree can be searched from the rectangle defined by the segment. Segments are usually short, so this is not large. But then you need to grow this rectangle by the point "kill" ratio.
Once you get an overlap between a point's rectangle and the search rectangle, you can do a geometric distance test from the point to the actual segment.
Awesome, thanks!
DeleteSorry to bother again, but I have some questions regarding the steps you described.
DeleteFirst, if I understand correctly, you grow the segment's rectangle by the kill distance to remove the points that are too close?
After that, do you grow each point's rectangle by its radius of influence to find the closest segment to each point?
The problem I see with growing "rectangles" is that the distance between a rectangle corner and the center is greater than the distance between one face and the center. So an intersection between two corners is not representative of the desired distance.
Sorry if I sound ignorant, I'm just trying to understand the best I can.
I grow the segment's rectangle and use it to query the RTree. This returns a list of points.
DeleteThis list may contain false positives, since a point may be in the expanded segment's rectangle, but still the actual distance to the segment may be greater than the kill distance.
So for each point in the list returned by the RTree I compute the actual distance to the segment. If it is within the kill ratio, I remove the point. That's pretty much it.
This is why the RTree helps. Computing the point to segment distance is expensive. The RTree narrows the set of points that need to be tested.