Small Blender Things: space colonization algorithm

Showing posts with label space colonization algorithm. Show all posts

Space Tree Pro: new features

I have updated my Space Tree Pro add-on for Blender. Its latest version (201510041334) comes with additional skinning modes, and option to add some random bumps to the basic crown shape and and option to randomly drop some mature branches from a tree to add 'character'. The new update is of course free to download for people who have previously purchased the Space Tree Pro add-on.

Better skinning

The native skinning option in the add-on left something to be desired, especially for thinner, highly curved branches which may end up looking rather squashed. This new version therefore sports three additional skinning modes, each with it own pros and cons:

Native: The original modifier. An example of the flattened twigs is shown in the image:
Skin modifier: It is now possible to use Blenders built-in skin modifier. It looks better but is really slow:
Convert to curve: Another choice is converting the tree skeleton to a collection of bevelled curves:
Ball and pipe: The final option is to use the conventional ball and pipe approach:

The quality of the new methods is comparable but the time to generate the mesh and and the number of polygons in the mesh differs significantly: For a moderate tree (1000 markers, 400 new markers, branch segment length 0.25, kill distance 1.0) the four skinning methods give the following numbers (on a Intel i7, 4 cores, your mileage may vary)

Method	Time (seconds)	Tris
Native	1.5	73,886
Convert to curve	1.2	63,536
Skin modifier	35.8	415,092
Ball and pipe	1.6	141,376

A more random crown

It was already possible to vary the branch generation by choosing a different random seed but the overall shape of the crown stayed the same unless you used a crown group. Now with the added bumpiness and size variation for the basic crown shape it has become much simpler to generate unique trees. Compare the three different trees on the top row (diffent branching, same overall shape) with the three trees on the bottom row (which have random bumpiness and shape).

Dropping some mature branches

The final new addition to this version is the option to break away a random number of branch segments after the tree is fully generated. This may add some character to trees think storms etc.). The image below show the same trees where the one on the right has 50 segments removed:

Currently I am working on a next release of my Space Tree Pro addon. One of the things it will feature is randomization of the basic ellipsoid crown shape and some additional bundled tree examples. The one shown below is has photo realistic hazel leaves and has is crown slightly randomized.

I know of course that hazel trees or bushes normaly don't grow in a prairie like environment :-)

Features that will probably make it into the next release:

Randomized crown outline
Randomzied shape, offset and distortion of the crown shape, making it easier to create unique but similar trees
A better looking trunk mesh
The possibility to remove random branches, adding character to trees
Several new, ready to use example trees

This new revision will of course be free of charge for people who already bought the addon.

Space Tree Pro, a new way to create trees in Blender

I like to announce my new tree creation addon Space Tree Pro that will appear on Blender Market on June 25.

A teaser video is already on YouTube:

The add-on is a natural evolution of my free space tree addon, with a vastly improved user interface, the possibility to influence the shape of the trees with the grease pencil, better tree trunks that are uv-unwrapped and generated faster, and a nice starter set of ready to use trees (that can be used as is, but are even better suited as a starting point for your own trees). Combined with the tutorial videos and a comprehensive manual I hope it will help people create many trees quickly with minimal effort, without sacrificing the individual character of each generated tree and offering great flexibility in blending trees with their environment.

Of course the add-on still has all the features of its free counterpart as well, like the possibility to shape the crown with groups of objects, defines shadow groups and exclusion zones and create trees or hedgerows with multiple trunks. Another new feature is that all configuration parameters are stored with the generated tree, which means you can create libraries of trees in separate .blend files and those trees can be loaded and tweaked again with the add-on.

Check Blender Market soon and I hope you will find the offer worthwhile.

A new tree addon, Part VII: an all C implementation

As indicated in this BlenderArtists post I have started developing a version of the space tree addon with most of the core calculations performed by C code.

Currently most functionality is available except for apical control and pruning but a 4x speed up (approximately, your mileage may vary) is worth it. This version is at the moment only available for 64bit Windows platforms (because it was difficult enough already to get that running with Visual Studio 2012) and unlike the previous C enhancements there will be no fallback on pure Python.

Code availability

This version is developed in its own branch, 'all_c' and the installation follows the exact same pattern as for other addons (don't forget to remove any older version). The zipfile is located here. As of May 2, 2014, this is linked against the 3.4 Python library as shipped with the Blender dailt build. If you use a slightly older version of Blender you might want to use the previous commit that was linked against 3.3.

The (almost) pure Python version stays available in the master branch, the zip file for this version is located here.

Future developments

I am thinking about making a Linux version available but that's not high on my priorities. If someone is willing to compile the module however I can include it with the addon. I think it is entirely possible to have a csca.pyd and a csca.so side-by-side. Having different .so files for Linux and OSX is something else, that would require tweaking the Python imports based on the OS type.

The current speed improvements only apply to the generation of the tree skeleton. I think the same improvement should be possible for native skinning algorithm. Also, there is yet no optimization of the C code and no multithreading, so we might improve the speed even more.

Another area of interest that I am currently spending time on is creating good leaf textures. Even with a decent flatbed scanner this is not trivial, yet now that spring is in full gear in my hemisphere I have started on cherry, apple and oak leaves.

References

The space tree addon itself is introduced in a few articles on this blog and is available on GitHub. Relevant links are listed below:

A new tree addon, part VI: continuing development

The latest version (0.2.14) includes a module written in C that implements some of the most time consuming functions. The result is a 20 - 30 % speedup for the generation of the branch skeleton. For now this is only available for 64 bit windows but on a different platform the addon will fall back on pure python implementations of these functions so cross platform portability is still guaranteed.

This is a quite noticable speedup: on my machine the generation of a tree consisting of 3000 branch segments went from 3.7s to 2.7s.

Implementation notes

The C extension module was compiled with Visual Studio 2013 and seems to work fine both with the official 2.70 distribution (compiled with MSVC 2008) and with the daily builds (compiled with MSVC 2013) but will only work with 64 versions of Blender. The Visual Studion solution is part of the spacetree repository so if people are interested in porting the module to other platforms they can have a go. Detailed notes on how to compile a native Python extension with Visual Studio 2013 were published in a separate article.

Undocumented stuff

This version of the addon also contains a first try at the implementation of branch shedding.

References

The space tree addon itself is introduced in a few articles on this blog and is available on GitHub. Relevant links are listed below:

A new tree addon, part V: bug fixes and user contributions

The latest version (0.2.11) fixes several bugs and adds a a very nice collection of fruit objects to the bundled library.

Vitamins are good for you

BlenderArtists member Piet not only contributed a new bark material that adds the impression of snow lying on the branches but also provided a collection of several fruits: Apples, pears, plums, peaches, cherries as well as mistletoe and a birds nest. Thank you Piet! Now all we need is leaf materials to go with these fruits. I'll try to source some Creative Commons leaf textures but now that spring is getting underway (at least here in the Netherlands) I might create some of my own.

Bug fixes

This release also features some bug fixes: If you were using groups of objects to shape a crown and an object within this group wasn't a mesh object, the addon would throw an exception. Likewise, if you had an object selected before creating a tree, an exception was thrown if this object didn't have an edit mode (like the camera or an empty).

Observations

The bundled library is getting quite big, I am thinking about zipping it and uncompressing it on the fly.
The fruit objects (and the leaves as well) are not positioned perfectly (Most of the time they do not quite connect to a branch). I'll have to check if there origins are set correctly or if we need something else (fruit tree for example grow their fruits generally on small protrusion called spurs)
It might be sensible to add more than one object group from the library (for example acorns and mistletoe)

References

The space tree addon itself is introduced in a few articles on this blog and is available on GitHub. Relevant links are listed below:

A new tree addon, Part IV: volume rendering experiments with OSL

With the new volume shading options offered by Blenders OSL implementation it is tempting to try this on the trees generated by the space tree addon. Without adding any extra geometry or particles apart form a basic ahape a volume shader might give the impression of a much denser crown as shown in the image below:

This effect was achieved by inserting a scaled icosphere that covers about 90% of the crown interior (see below) and adding a volume shader to this icosphere that scatters and absorbs light in a non-uniform manner, i.e. the shader mimics a bunch of small scattered disks, which when seen from the distance add to the illusion of leaves. Note that we cannot do without all the leaves because volume scattering adds no specular reflections as real leaves might do.

If you would like to know more about programming OSL you might be interested in my book "Open Shading Language for Blender". More on the availability of this book and a sample can be found on this page.

Shader code and example node setup

The code for this shader consists of the shader proper, which merely checks which randomly scattered point we are closest to and then calls the indisk function with the position of this closest point and a random direction. indisk checks whether we are inside a disk with its axis in some direction and returns 1 if this is indeed so. Note that the include at the start of the code refers to a file that is distriubted with Blender and contains a number of useful functions, including a number of Voronoi/Worley related ones.

#include "node_texture.h"

int indisk(
  point p,
  point c, float r, float h, vector d
){
  vector v = p - c;
  float a = dot(v,d);
  float lh = abs(length(a * d));
  if(lh > h){ return 0;}
  float lv = length(v);
  float lp = sqrt(lv*lv - lh*lh);
  if(lp > r){ return 0;}
  return 1;
}

vector randomdirection(point p){
  float t = M_2PI*noise("cell",p,1);  
  float u = 2*noise("cell",p,2)-1;  
  float s,c,a;  
  sincos(t,s,c);  
  a = sqrt(1-u*u);  
  float x = a*c;  
  float y = a*s;  
  float z = u;  
  return vector(x,y,z);
}

shader bits(
  point Pos = P,
  float Scale = 1,
  float Size = 1,
  float Height = 0.05,

  output float Fac = 0
){
  point p = Pos * Scale;
  point centers[4];
  float distances[4];
  voronoi(p, "Distance Squared", 0, distances, centers);
  if(indisk(p,centers[0],Size,Height,randomdirection(p))){
    Fac = 1;
  }
}

The node setup to use this shader as seen in the opening image of this article looks like this:

Discussion

Whether using a volume shader this way is really useful remains to be seen: rendering this way is still rather slow. Of course, getting a comparable dense crown with extra particles also slows down rendering: in my tests doubling the number of particles from 1000 to 2000 resulted in a render time that was actually slower than adding the volume shader. In other words, your mileage may vary but it might be worth to experiment.

References

The space tree addon itself is introduced in a few articles on this blog and is available on GitHub. Relevant links are listed below:

A new tree addon, Part III: development continues

The latest version (0.2.10) adds a particle system with acorns to the library (not because it is briliantly modelled but to show an example usage) and adds a shadow density option if you use a shadow group (because no shadow is absolute). I also added an option to change the size of the faces of the emitter mesh. That way leaves and other objects can be made to sit closer to the branches.

Version (0.2.9) of the spacetree addon features cleaner code, the posibility to add two particle systems and an update to the bundled library: it now features a particle system of chestnut leaves as well as an additional bark material. I have also reordered the options in the UI to a somewhat more logical groouping and I am working on an update to the user manual (old version is still available, concepts discussed there are still valid)

Sample image of a tree with the chestnut leaf particle system. The crown was shaped with a crown group consisting of just a couple of icospheres.

References

Future work

Several suggestions have been done to improve the addon (and a few items from the roadmap are still open) but these are the most interesting ones in my opinion, although I am the first to admit that most serve more an academical interest than an artistical one:

Apical control

The suppression of side shoots lower down the branch by the growing tip. Is in place but functions unsatisfactorily. Should give straighter branches.

Branch angle control

The angle of a side branch is usually more or less fixed for a given species of tree. Having this could add to the believability of the generated tree.

Branch sheding

Some trees (e.g. conifers) drop old branches that don't receive enough light, resulting in bare lower trunks.

Shadow group density

Currently the shadow group will receive no endpoint markers at all. This should be modulated by some density factor to emulate half shadow (done, see version 0.2.10)

Tree roots

Fairly easy to add I think as it is mainly a not so comples upside down tree (at least as an approximation :-). The trick is to match the diameter of the trunk to the top of the root system.

Of course, adding to the bundled library of particle systems and brak materials is very desirable as well, but hopefully the community has something to contribute here (some already have and I you have any good procedural bark material to constribute or maybe good leaf materials (procedural or alphamapped) please post the in the Blender Artist thread. The should be completely your own and have either a Public Domain, CC-0 or GPL license but of course I will credit you in the library notes)

If you really like my addon you might consider having a look at my Amazon wish list :-)

A new Tree addon, adding functionality

Compoared to the previously documented features this new version (0.2.5) adds a preliminary version of apical control and a 'Leaves' vertex group.

Code availability

Downloaf the installable .zip file from GitHub and read the installation instructions carefully, especially if you have installed an earlier version.

Apical control

Apical control (or apical dominance) is the phenomenon where buds on the end of a branch supppres the developments of bufs lower doen the branch. Often this will lead to trees with straighter branches and less side shoots. This versions contains a preliminary version but because I'm not quite satisfied with it yet I won't elaborate on it.

Vertex weights

The generated tree now has a vertex group called Leaves. It has more weight near the end of the branches and the clustering can be controlled with the leaf clustering option. (As shown in the image below for a value of 1.0, 4.0 and 8.0 respectively). In the future we will add a ;eaves particle system as an alternative to the mesh leaves and the density of this particle system will be controlled by this vertex group. Of course you can now use this group yourself if you configure a particle system by hand. Note that without a skin the tree mesh consists only of vertices and edges (no faces) so the weights are not visible in weight paint mode although they are there. With a skin (either our custome skin or one generated with Blenders skin modifier there will be faces and the weights will be clearly visible (the skin 'inherits'the weights from the tree skeleton in both scenarios).

A new tree addon, revisited

It has been a while since I worked on the new tree addon so I thought some attention was due.

Over the last six months or so my thoughts did keep coming back to the speed of the space tree addon. We already got quite some speedup from introducing kd-trees to store the branchpoints but still it felt kinda slow.

A time complexity analysis is difficult because the number of branch segments grows while the number of endpoints either falls (when branches come within kill distance) or rises (when they are added at random while generating new branch segments) but what was clear that we calculated all branchpoint/endpoint interactions for each iteration anew. And with the number of branchpoints easily rising to hundreds if not thousands and the number of endpoints initialy amounting to several hundreds this adds up quickly, especially because calculating a branchpoint/endpoint interaction is computationally expensive.

This new version takes care to recalculate such interactions only when necessary: when adding or removing an endpoint it recalculates things only for the branchpoint to which it is closest and when adding a branchpoint it checks which if any of the endpoints is now closest to this new branchpoint and does the necessary calculations only for those endpoints.

The resulting speedup is tremendous: A moderately sized tree with the settings shown below takes 76 seconds to generate the branch skeleton on my machine, while in the new version it takes just 0.6 seconds! These two order of magnitude mean that I am tempted to remove the update button and return to truly interactive modelling, however, skinning such a tree takes still considerable time: almost 5 seconds with Blenders skin modifier, way too slow for interactive modelling (I didn't yet compare my own skinning method).

Parameter	Value
max. iterations	2000
no. of endpoints	500
internode length	0.35
kill distance	0.51

Code availability

I have not commited this new version to the addons-contrib repository yet because I want to test it some more (the changes in the code are quite big) and because I discovered a bug in Blenders skin modifier that this addon can trigger (edit: wow, that is fast, fixed almost immediately!). Nevertheless, this version is available for the adventurous on GitHub, just make sure you read the installation instruction posted there (important if you use a Blender daily build because then the old version of the addon comes bundled and needs to be removed).

Roadmap

A roadmap might not be the correct term as it implies some form of commitment I cannot possible pledge to a hobby project but nevertheless i'd like to present a list of things I have in mind for the spacetree addon.

None of those items might see the light of day and the order in which I might tackle them is not certain at all but it might give end users some indication of thr direction I'd like to take the addon. It also functions as a worklist that I can use for myself to tick items off.

[done] correct radius (and positioning) for native skinning
interactive/manual update switching based on elapsed time
twigs
final extra branchpoints not controlled by endpoints
[done] implement 'influence' option
restrict the range within endpoints can exert their influence
branch angle control
better leaves
- [done]better geometry (a small group of low poly leaves)
- [done]vertex group w. weights based on connectivity (or its reverse, tips have more leaves)
- [done]a default particle system (as an alternative to placing leave objects)
- [wip]some default leaf shapes (alpha masked textures, freely distributable, so I'll need to make my own once it is springtime again)
[done] experiment with blended box mapping material for branches, include seamless bark texture). Blended box mapping didn't work out that well but a material based on a normalxtangent based coordinate system works quite well (see BlenerArtists thread). Code and library are in place, but with a placeholder material for now.
[wip] apical control
control the suppression of side shoots lower down branches. (I have a rudimentary implemenation in place but it's not quite what I want yet)
branch shedding
control automatic pruning of branches that receive little light
endpoint distribution based on rudimentary mesh
distribute endpoints within some radius around the edges of a mesh to 'draw' a basic shape of a tree
better display of timings
[done]uv subdivision

A new tree addon part VII: tweaking leaf UVs

Now that the addon is in Blender's Contrib repository I thought it was time to start acting on some of the feedback from the BlenderArtists thread.

This release contains two minor improvements:

rotated UV-maps for the leaves and
an option to set the offset of the leaves from the twigs

Previously the UV-maps that were generated for the leaves were rotated. Because most alpha mapped leaf image textures feature leaves with the tip at the top and the stem at the bottom this rotated arrangement was often counter intuitive.

Depending on the image that you use as a leaf texture it might be useful to be able to control the point where the leaves are joined to the twig. This offset is now provided as an option slider in the leaves section. Note that even if this offset is zero the leaf plane might still be intersected by a twig. This happens when the branches are skinned with Blender's skin modifier (instead of the native skinning method).Before this skin modifier the addon adds a subsurface modifier which has the effect of cutting corners. Choosing a smaller internode distance and removing this subsurface modifier will prevent this unwanted intersection but in most cases (I.e. with enough leaves) this probably won't be noticeable anyway.

A new tree add-on part VI: speed improvements for complex trees

Trees that contain many branchpoints take a progressively longer time to generate as they become more complex. This is due to the time it takes to determine which branch segment is closest to any endpoint. The code up to version 0.0.7 did a linear scan through all the branch segments for each endpoint and while this was still fast enough for moderately sized trees (the time it takes doesn't explode exponentially because each iteration removes endpoints within kill distance of a branch) it took many seconds for a tree with thousand endpoints, short internode lengths and a short kill distance. In other words it got slow when the trees became interesting.

Version 0.0.8 (available on Github, click view raw to download) adds a significant speed up for larger trees (3-6 times depending on parameter settings). Quite complex tree skeletons can now be generated in a few seconds instead of half a minute or more (depending on the power of your pc of course. And remember, this is a pure python implementation so having multiple cores makes no difference, it's the raw speed of a single core that counts). Please note that because endpoints within kill distance are removed in a different order, trees generated in version 0.0.8 are not identical to trees generated in previous versions but their general appearance stays the same.

For the technically inclined: this speed up is realized by storing all branch segments in a kd-tree, so looking for a nearest neighbor now scales as the log of the number of branch segments instead of taking linear time. This is a very noticeable difference once your tree grows to hundreds or even thousands of branch segments. The kd-tree is a pure python implementation in its own, separate module kdtree.py that might be interesting for other applications as well.

A new tree add-on part V: speeding up skinning of the tree skeleton

one of the issues that bothered me about my new tree add-on was that applying the skin modifier to flesh out the branch skeleton was incredibly slow, especially for larger trees. I therefore decided i'd try writing my own skinning routine and the results are quite promising: a factor 10 or more for moderately sized trees.

The new version (0.0.7) is as usual available on GitHub. How to use and install this add-on is documented in previous articles: I II III IV.

The new skinning method is the default if you uncheck the no modifiers checkbox but if you like you can still select Blenders skin modifier from the drop down as shown on the right. (This can also be done later because we leave the skeleton itself intact; as it only consists of edges it won't show up in renders but you could use it to add any modifier later on).

Timings

The table below lists some timings for my computer, all values were left to their defaults except for the number of endpoints:

Timings in seconds for generating a tree skeleton
Endpoints	No modifier	Own skinning	Blenders skinmod
100	0.02	0.04	0.46
200	0.04	0.07	0.74
400	0.08	0.16	1.51
400	0.56	0.87	14.43

The last line shows the results for a fair sized, bushy tree (400 endpoints, but with the internode length and kill distances reduced to 0.5 and 2.5 respectively and with 3000 extra endpoints per 1000 iterations). The difference between less than a second and more than 14 seconds is the difference between comfortable modelling and frustration, and there is still some room for improvement because the code is still riddled with print statements.
There are three factors that help to speed up the skinning operation compared to blenders built-in skin modifier:

unlike the modifier we do not have to make a copy of the mesh,
we also generate a lot less geometry it seems and
we don't have to deal with special cases: the skin modifier can handle any geometry while our skinning just has to deal with straight edges or simple forks.

Results

When we apply a subsurface modifier to our skinned branches the result is already quite acceptable although I see room for improvement, specifically in the shape of the forks. As you can see there is some bulging were the branches join and this is especially noticeable when there is either a very sharp anngle between the branches or when both branches bend out of plane. Fortunately the highlighted 5-gon lends itself to all kinds of angle dependant adaptations so I expect I can tweak this further to get smoother results.
The focus for the next minor release will be on bug fixing and code cleanup to prepare for a full 1.0.0 release. This will be accompanied by better (hopefully: -) docs as well.

A new tree add-on part III: multiple trunks

Version 0.0.5 of my new tree add-on adds functionality to specify a group of starting points facilitating the creation of hedgerows or twinned trees.

multiple trunks

When you want to create a hedgerow or a small copse of trees combining multiple trees might not lead to an acceptable result because branches might cross and the shape is not quite the way you want it to be. Also the amount of work needed to create a hedge of thirty plants can add up. I therefore added the possibility to define any number of starting points by refering to the locations of objects in a group.

Part of the scene setup used the create the example image is shown on the left.

The empties (represented by the green cone shapes) are all in the same group and their locations are used as starting points.

The parameter settings were as shown on the right. As usual the code is available as a zip-file on GitHub. More info on how to use the tree add-on can be found in two previous posts: A new tree add-on and A new tree add-on part II: better workflow

Future directions

I noticed that the mesh created by the skin and subsurface modifiers contains not only a huge amount of faces but also contains quite a precentage of vertices (20% or so) that are so close together that they practically overlap. Generating such a mesh takes a considerable amount of time so I think I will try to come up with a skinning method that is suitable for our tree trunks but hopefully somewhat faster.

New tree addon part II: a better workflow

Version 0.0.4 of my new tree add-on is focused on defining the crown shape with groups of objects

usability enhancements

In the previous version of the add-on the markers or endpoints that represent the resources that the growing branches compete for were distributed inside an invisible ellipsoid. The resulting distribution could me made visible with the show markers option but from a usability point of view that was not ideal. likewise the su bstraction of markers from the distribution for those markers that were in the set of currently selected objects was less than intuitive, the more so since producing a tree would deselectsll objects forcing the user to select them again when trying for a different tree shape.

In this new version we allow for different way to define a crown shape using groups. If you select the use groups option you can choose three different groups:

the Crown group

any markers generated will lie inside the objects that are part of this group.

the Shadow group

any markers generated will not lie in any objects in this group. This group is optional.

the Exclusion group

growing branches will not penetrate into any objects in this group but stop. This group is also optional.

The shape of the marker cloud is determined by the combined shapes of the objects in the crown group minus those in the shadow group. If you use a shadow group it must be different from the crown group otherwise no markers would be produced at all (although there is a safeguard in the add-on to prevent this). If you use an exclusion group this should differ from the crown group as well although it might be the same as the shadow group.

workflow

The workflow now becomes pretty straight forward:

create a crowngroup, for example a bunch of different icospheres,
assign anything casting a shadow to a shadow group (here a box),
optional: assign anything impenetrable to an exclusion group (or reuse the shadow group),
position the 3d cursor at the place where the bole of the tree should start,
click update tree (here shown with the parameter settings that produce the tree in the screenshot),

Of course you can alter the other options as well. Don't forget to disable any objects for rendering that you used just to define a group otherwise you won't see much of your tree.

Code availability

This release is version 0.0.4 and avaible as a zipfile on GitHub

A new tree add-on

Blender already has a few add-ons to generate plant or tree objects, notably IvyGen and Sapling and recently I added a general L-system add-on into the mix. In this post I present a new add-on that creates trees based on the space colonization algorithm by Adam Runions.

A new kind of tree

This add-on now has a professional cousin available on Blender Market. It offers new functionality like controlling crown shapes with the grease pencil and is bundled with quite a few ready to use trees that can be used as is or function as a starting point. A YouTube playlist with examples/tutorials is available as well.

Documentation for this add-on now has its own page.

The GitHub repository now serves version 0.0.4 which makes it possible to define the shape of the crown with groups of objects. Details can be found in this follow-up article.

The GitHub repository now serves version 0.0.3 which allows more than one leaf per internode and has a control to determine how much these leaves are clumped. Note that the oft maximum of leaves is still 1.0, if you want more, click and alter the value by hand.

The GitHub repository now serves version 0.0.2 which adds the ability the enable the generation of new endpoint markers while the tree is generated. This will allow for bushier trees with extra small twigs on the main branches

[Some additional sample trees are near the end of this article] Because IvyGen is limited to climbing shrubs and Sapling requires a fair amount of user interaction to get nice results, I thought it would be interesting to explore the possibilities of generating trees with the space colonization algorithm as described by Adam Runions.
This algorithm models the growth of a tree by letting branches compete for resources (think light) as they grow. The distribution and density of these resources control the final shape and the algorithm lends itself easily to adapt to environmental influences like walls blocking light etc. a feature that comes in handy when doing architectural modelling for example.
In the first version of this add-on many features are already available but it is not yet a finished tool. Any remsrks and criticisms are welcome of course. This article describes how to install and use the add-on but does not give an in depth account of its design or underlying principles, that is left for a later article. I do present some example images with their parameter settings to get you started.
The code is available on github. Just download the latest zip from the release directory and install the add-on with File->user preferences->addons install from file by pointing it to the zip file. You can then toggle the checkbox to use it (It is in the Add Mesh category as SCA Tree Generator). Remebr to uninstall the add-on first if you installed an earlier version by clicking the remove button.

Creating a tree

To add a tree, position your 3d cursor where you would like the tree to grow and select Add->Mesh->Add Tree to Scene. A small tree skeleton will appear and in the toolbar on the left of the 3d view will be a number of options. (Press T if the tool bar isn't visible) User interaction is copied from IvyGen so changing the values of options doesn't have an immediate effect but new values are applied when you click update tree. This is necessary because generating larger trees can take quite some time and if that was attempted on each value change the add-on would become unusably slow.
An overview of all the options is available with the source, here we just highlight the more important ones.(tip: before you start experimenting it might be a good idea to check the no modifiers checkbox because the tree trunk is given substance by the skin modifier and will take many seconds on larger trees}
The whole idea of the space colonization algorithm is to populate a volume (an ellipsoid in our case) with markers and let a growth point (at the the 3d cursor) start growing in the direction of the nearest markers. As a growth point (called internode or branchpoint in the add-on in a not entirely botanically correct fashion) approaches a marker close enough, this marker is removed and subsequent growth is in the direction of a slightly different set of nearest markers. A branchpoint can have any number of markers in its sphere of influence but conversely a marker has only a single closest branchpoint. Because of that branches may develop sideshoots (read more on this in the original article)
This means that the number of markers and their distribution are the crucial parameters in determining the shape of the final tree,(tip if you check the show markers option in the debug panel, the markers that were generated at the start of the tree generation will be visualized as small tetrahedrons. That way you get a clear picture of their distribution. This feature is used in most images that follow.)

Some example trees and their marker distributions

Note that only the parameters that differ from their defaults are shown in the picture.

Few endpoints vs. many endpoints

Near central axis vs. near surface

More endpoints near the top

Mix and match

Even shrubs are possible as shown on the right.

adding leaves

When you click the add leaves button a new panel with options will appear with controls for the leaves. The number of leaves controls the probability that an internode (branch segment) carries a leaf. The size and size variation of these leaves can be controlled, as well as the variation in orientation of the leaves. The number of connections option controls how much 'old wood' carries leaves. If you set this to 1 only new twigs will carry leaves.

Shaping the branches

When you click on the add modifiers option, three modifiers are added to the trunk skeleton (shown in the opening image of this article):

a subsurface modifier to smooth the branches,
a skin modifier to give volume to the branches and
another subsurface modifier to smooth this skin.

Note that calculating these last two modifiers may take many seconds or even minutes if the tree is complex!
The thickness of the trunk and branches and the way the thickness of forking branches is combined is controlled by the Scale and Power options respectively.

Environmental influence

A final feature of this add-on that almost comes naturally with the space colonization algorithm is the ability to factor in environmental influences. For example if one side of the growing tree receives more shadow than the other side due to a wall or building, that side will grow less. We can easily mimick this by not placing any markers in a shadowed area. To accomplish this the add-on checks whether any of the markers is generates is inside any of the selected mesh objects in the scene and discards them if they are. The workflow is then:

select one or more objects (first image below)
position the 3d cursor where you want the tree to start
tweak any options
update the tree

The result (with markers) is shown in the second image below.

Note that we did not select the actual wall, but a larger duplicate (that we will not render), because the shadow influence normally extends beyond the wall and because a new branch might still pass through this exclusion zone towards markers that are above it. By chosing a wider volume we prevent those branches to pass through the actual wall.

Limitations

In this first version there will undoubtably be any number of bugs. One of the most annoying issues is that when the kill distance is chosen too small, a developing branch may terminate in a myriad of tiny segments. This will not only take an enormous amount of time when adding the skin modifier but will also cause a strange clump of hundreds of leaves at that point.
Another thing is that even when not actually generating new geometry, the user interface is sometimes slow when modifiers are selected. I have a hunch this might be related to Blender keeping track of this complicated geometry in its undo cache but I am not sure.
Of course there is also plenty of room for functional improvements: it would be nice if you could select more than one starting point for example to create hedgerows etc. and also have arbitrary objects instead of square leaves, but those are nice to haves for the future.

Some more examples

The following images show the same type of tree as the opening image of this article, but at more mature stages:

The masked leaf texture as well as the concrete and brick textures are from cgtextures.com, the latter two converted to various types of specular and bump maps with the free shadermap commandline tool. The hdri-background is Alex Hart's 'Arboretrum in Bloom'.
The most mature tree was generated with the settings shown below: