Procedural tree generation

I read a paper regarding fractal generated trees like this one some time ago. Unfortunately I haven't found it using Google. Maybe the URL can be a starting-point for you.

With best regards,
Kimmi

The terms you might want to try and google are "IFS" (integrated fractal systems), "L-Systems" (Lindemeyer systems) and "procedural" - although you'll most likely want to look at IFS rather than L-Systems. These should get you started.

Quote:

Original post by irreversible The terms you might want to try and google are "IFS" (integrated fractal systems), "L-Systems" (Lindemeyer systems) and "procedural" - although you'll most likely want to look at IFS rather than L-Systems. These should get you started.

s/integrated fractal system/iterated function system/
s/Lindemeyer/Lindenmayer/

Why should IFS better than L-Systems? Last time I checked, IFS were great for creating fluffy fractals (excerpt), and L-Systems where just great stuff for creating artificial flora, and if you look at Aristid Lindenmayer's job, it's specifically biologist.


About L-Systems: Algorithmic Botany: Publications (at the bottom, you'll also find the free book "The Algorithmic Beauty of Plants", it's the reference on how to use L-Systems for flora).

L-Systems can even be used to create Architecture or whole cities.

One problem of L-Systems is that there is yet no known analytical method of transforming a given shape into an l-system (there exists a genetic one for parametric L-Systems: click; haven't checked the paper yet). Btw, for some motivation, have a look at xfrog, especially those collections.

For more techniques, have a look at vterrain's plant page.

Sidenote: Every programmer who is only slightly interested in terrain scenery should bookmark vterrain.org.

---

edit: While I am smashing urls, their newest paper looks damn sexy.

Thank you all (and especially the last poster!), you've all been very helpful with resources.


Now that I have enough for possibly a year of not more of just reading, I shall get started with L-systems, and paticularily "The Algorithmic Beauty of Plants". I wasn't expecting so many resources and research in this field. I think it may be a long time before I complete this, but at least the journey will be interesting.

Quote:

Original post by phresnel L-Systems can even be used to create Architecture or whole cities.

To be fair, the guys who did the best work with L-systems in architecture found that pure L-systems by themselves weren't enough for realistic city modeling, due to the difficulty of reconciling distantly related but spatially associated features. (Of course, the OP didn't want to make buildings, so I'm just being Mr. Pedantic here.)

Much better solution:
http://www.cs.duke.edu/courses/fall02/cps124/resources/p119-weber.pdf

Generates trees that actually look real, which L-systems etc doesn't.

Edit: changed link to downloadable pdf.

[Edited by - _swx_ on August 20, 2009 4:32:23 PM]

Quote:

Original post by _swx_ Much better solution: http://portal.acm.org/citation.cfm?id=218427 Generates trees that actually look real, which L-systems etc doesn't.

I don't have access to acm, nor am I willing to pay. I'll be going to university in a couple weeks, maybe they will grant me access?

And what specifically is bad about L-systems? I've read a bit of that paper already now.


The problem I'm dealing with is that they seem to be creating lines of which they have 3d representations of. How do they generate the 3d representation? Are they single meshes or just a bunch? (this was more of my question earlier, actually).

Okay, I've looked at it and it seems that they need a 3d representation of each "node". Do they just pile these on top of each other, or are they connected via the vertices somehow?

[html]http://blendernewbies.blogspot.com/2007/08/tree-making-tool-gen3.html[\html]

Coincidentally, I was doing tree generation too. This is the paper I am going to try to implement (the link to the original pdf is midway down the page)

Quote:

Original post by gpu_fem [html]http://blendernewbies.blogspot.com/2007/08/tree-making-tool-gen3.html[\html] Coincidentally, I was doing tree generation too. This is the paper I am going to try to implement (the link to the original pdf is midway down the page)

Excellent! I think I will implement this also, it looks very convincing.

I'll still read some of the other papers as they are all quite interesting.

Quote:

_swx_ http://www.cs.duke.edu/courses/fall02/cps124/resources/p119-weber.pdf

Their system is actually limited to trees, flowers and other flora supported by l-systems are not possible as is. Further: How do their trees interact with the environment? L-Systems have been extended to let them interact with the rest of the world (see also Illumination Driven Plant Growth):



The good thing, yes those trees are easier to construct for end users, once the system is implemented, but compared to L-Systems, they have only a fraction of their powerfulness.

Quote:

Original post by _swx_ Generates trees that actually look real, which L-systems etc doesn't.

Then below images are gimped or photoshopped?




And a real world scene (showing terragen+xfrog plants, image from xfrog):


[Edited by - phresnel on August 21, 2009 3:20:35 AM]

Quote:

Original post by gpu_fem [html]http://blendernewbies.blogspot.com/2007/08/tree-making-tool-gen3.html[\html]

Small nitpick: Even if the html tag would be enabled here, that wouldn't be valid html, in case you want a link be emitted. It would look like that:

[html]<font color="red"></font>[<font color="red">/</font>html]

Luckily, gd.net allows you to use the a-tag directly:
http://blendernewbies.blogspot.com/2007/08/tree-making-tool-gen3.html

I used the Weber paper for my trees and it works well, you can see a small video of some of the results

">Here. I've since added pruning volumes and obstructions to growth as well as grow along splines.

Maybe also check out GroIMP/XL:
https://sourceforge.net/projects/groimp/

It's an open source tool that allows to model trees and more. XL is a programming language that combines Java and L-systems and allows global interaction as well.

Quote:

Original post by spookycat I used the Weber paper for my trees and it works well, you can see a small video of some of the results ">Here. I've since added pruning volumes and obstructions to growth as well as grow along splines.

Mighty results. You write on that youtube page that it's for your game engine. Which one would that be?

Thankyou :) It's for our own in house game engine that is still being worked on. There is still a bit of work to do on the tree front better blending of branches to the trunk for example, working on the wind and deforming stuff at the moment. Some pics of the growing along a path and growing around objects. Still got some way to go to match SpeedTree 5.0 but cant afford that one, mind you price has come down a little but still more fun doing it oneself :)

Incredible!

Okay, just a single simple question.

In the paper, he says "a random rotation of magnitude (nCurveV/nCurveRes)". I am just wondering whether he means what he said (then its not random), or he means a random rotation of magnitude *up to* (nCurveV/nCurveRes).

I'll go with the second, but maybe I'm misunderstanding something.

In my version I have it as RandomValueBetween(-nCurveV, nCurveV) / nCurveRes

Quote:

Original post by spookycat In my version I have it as RandomValueBetween(-nCurveV, nCurveV) / nCurveRes

Okay, thats what I thought. I think it's an error in the paper.

I have a question regardin Weber's paper (http://www.cs.duke.edu/courses/fall02/cps124/resources/p119-weber.pdf) as well. In section 4.2, there is a passage which says: "If there are any clonsed, then the z-axis of the stem and its clones rotate away from the z-axis of the previous segment by angleSplit=(nSplitAngle+-nSplitAngleV)-declination, limited to a minimum of 0, where the "declination" angle ... can be found by taking the inverse cosine of the z component of a unit z vector passed through the current matrix tansformation of the relative coordinate system."

Here is what I do not get: suppose we got a two-way split after the first segment, so that the current transformation is a simple translation upwards, then the z component of a unit z vector passed through it would be 1, right? acos(1)=90, thus angleSplit will be negative except from exteme cases of nSplitAngle and nSplitAngleV which leads to angleSplit = 0 very often and the clones wont rotate away from the main branch.

If you look at the top center image, there is a tree which has a split right after the first segment, but here the angle seems to be 45 degrees from the segments z-axis, so why is that?

Where am I taking the wrong turn?