Page 1 of 2

Herb's Tree Studio - Procedural Trees

Posted: Mon Oct 27, 2014 6:30 pm
by Herb
[UPDATE] Feb 2016 - New video showing editor progress and entity system working for object properties. Have multiple "scenes" now so each tab is a tree with independent settings. Think I'm far enough to get back to the algorithm work now. :)

[youtube]7wYOdg4jZIk[/youtube]

[UPDATE] March 10th - Update later in the thread, but adding the new video here as well for painting of attraction points.

[youtube]H2IbdwyYI1s[/youtube]


Hey Everyone!

Thought I'd share a little side project I was working on generating procedural trees with Ogre. Don't have leaf placement yet, just branches, but it's coming along. It uses a space colonization algorithm for the tree, so NOT the same as the other ogre tree generators of old like cadune, etc...

If you've never heard of this algorithm, here's a white paper on it.

So, instead of what Arbaro does which grows the tree from the ground up with LOTS of parameters (and it's a bit complicated), I draw the tree by starting with the leaves. :)

Basically, you define a shape for your "leaves" to be in. Then you fill the shape with "attration points", which are random points that fall within the shape. The algorithm then starts at a point and interates generating another segment of the tree as it reaches for the attraction points. Certain parameters cause the branch to split and attraction points are deactivated when a tree segment gets within the configurable kill distance.

Below is a quick video showing a little bit of what I can do at the moment. It's pretty alpha stage at the moment.

[youtube]vtqB5FQuUU4[/youtube]

Libraries Used:
- Qt
- Ogre 1.9
- DirectX on Windows, OpenGL on Linux (Ubuntu)
- OgreProcedural

If I get time, I'd love to not only get leaves, but get some wind shaders going. :)

Hope you like it. Let me know if you find interest in this too. I'd be more interesting in working on it if others would have use for it. Feel free to ask any questions about it.

Re: Herb's Tree Studio - Procedural Trees

Posted: Tue Oct 28, 2014 9:27 am
by tod
Looks good. Too bad I don't use trees in my project. :(

Re: Herb's Tree Studio - Procedural Trees

Posted: Tue Oct 28, 2014 10:09 am
by Zonder
It looks really good.

Are the branches always up due to the algorithm or just happened to be the way you made them? (I was thinking of willow trees where the branches get weighed down http://i1013.photobucket.com/albums/af2 ... w-tree.jpg)

Re: Herb's Tree Studio - Procedural Trees

Posted: Tue Oct 28, 2014 1:42 pm
by Zonder
Had a chance to read through some of that article I have to say it is rather interesting it would be a nice way of getting realistic growth when developing a forest for instance. Have you tried simultaneous growth yet? or maybe seeding trees randomly in an area overtime?

I defiantly think you should continue this work! :)

Re: Herb's Tree Studio - Procedural Trees

Posted: Tue Oct 28, 2014 1:43 pm
by Herb
Yes, this is all through post process steps, which I don't have many in there yet. The key is how simple the algorithm is, so you can add modifiers easily for things like that. The white paper I reference has some details about this in there. The best example is the group behind the article who wrote an awesome iOS app using this algorithm. Below is the video of their iOS implementation. I show it as it captures what this type of algorithm could do if you wanted to expand it. Originally my goal was to mimic this adding wind shaders, but my team dwindled down to just me, so progress has been limited. There is also a post process step in my app for how you decided how "thick" each tree segment is. I run this periodically during the algorithm to make it appear like the trunk is growing with the branches.

Again, this video is the TreeSketch iOS application from Algorithmic Botany, so not Ogre, but uses the same algorithm I'm using in my Ogre app.

[vimeo]68195050[/vimeo]

Re: Herb's Tree Studio - Procedural Trees

Posted: Tue Oct 28, 2014 1:46 pm
by Herb
@Zonder - I haven't, but you nailed a sweet idea. If you have multiple start points, you can simulate things like growing a tree canopy together, or even generating a perfectly integrated hedge together.

The triangle count can be higher for these tree models, but if I keep the attraction points down (keeping the branches sparser) and then get leaves on there (which adds more detail), I think it would still be usable in the game world.

Re: Herb's Tree Studio - Procedural Trees

Posted: Tue Oct 28, 2014 7:35 pm
by dark_sylinc
Looking good!!

Is this project of yours going to be available for download?
Will it also handle leaves?

Keep it up! :)

Re: Herb's Tree Studio - Procedural Trees

Posted: Wed Oct 29, 2014 1:45 pm
by drwbns
Looks awesome so far, it might give speedtree a run for it money if you can develop it as much as the iOS app you posted there. Add simple .mesh exporting and you've already got something content creators will use. A few leaf shaders on top of an awesome branch structure is already a great start. Kudos to you. :)

Re: Herb's Tree Studio - Procedural Trees

Posted: Wed Oct 29, 2014 2:43 pm
by Herb
@dark_sylinc - Sounds like there's enough interest for me to work on leaves :) I think once I have leaf placement, a download would be valuable to folks.

@drwbns - Yes, have an export feature already for the mesh. Turns the ManualObject to a Mesh and saves it out.

The biggest issue with the algorithm is it's n squared efficiency...I've found some way to thread pieces of it, but until I try those ideas it can be slow if you have too many attraction points, which would happen if you made a forest all together (might turn more into a batch job at that point). If you get 3K or more attraction points the algorithm slows quite a bit for for the last few iterations (as it's slow and single threaded). It does speed up if you don't render it while it's generating, but that's the cool part. 8)

I guess the thing to decide is what to do for leaves... I'm thinking a two-sided quad for lighting on both sides and to keep the triangle count down. The big decision is how realistic to make it... If I put a lot of leaves on there, the branches really need to be thinned down for most tree types or the triangle count is going to be too high for game use. I think having balance of realistic trees that don't eat too much of the GPU is important for the library to be of use.

Thanks everyone for the feedback! :)

Re: Herb's Tree Studio - Procedural Trees

Posted: Wed Oct 29, 2014 4:23 pm
by Zonder
For the leaves don't go for performance go for looks, then see how to optimize.

I am presuming at the moment branches are all cylinders? If so maybe use an X style quad when they are small instead.

Re: Herb's Tree Studio - Procedural Trees

Posted: Wed Oct 29, 2014 4:49 pm
by dark_sylinc
Herb wrote: The biggest issue with the algorithm is it's n squared efficiency...I've found some way to thread pieces of it, but until I try those ideas it can be slow if you have too many attraction points, which would happen if you made a forest all together (might turn more into a batch job at that point).
Aw! Don't worry so much about forest.
We cheat all the time. We often generate around 4-10 trees, then repeat them but randomizing size, orientation and colour (and sometimes leaf's billboard texture).
Also generating two trees should be easy to thread (i.e. 2 trees = 2 threads; as compared to threading the generation of a single tree)
Herb wrote: I guess the thing to decide is what to do for leaves... I'm thinking a two-sided quad for lighting on both sides and to keep the triangle count down. The big decision is how realistic to make it... If I put a lot of leaves on there, the branches really need to be thinned down for most tree types or the triangle count is going to be too high for game use. I think having balance of realistic trees that don't eat too much of the GPU is important for the library to be of use.
Agreed!

Re: Herb's Tree Studio - Procedural Trees

Posted: Wed Oct 29, 2014 5:06 pm
by Herb
@Zonder - Yes, they are cylinders. But, I could extrude a different shape or something when the radius of the branch got to a small enough value. Back when the Woody3d tree library was alive (I ported it to Ogre3D few years back), I like what they did for branches with trees full of leaves. See image below.

Image

Basically, they either didn't draw branches or something at least more primitive then cylinders on the outer branches.

@dark_sylinc - Agree. I think I'll worry more about leaves right now before optimizing any more on the algorithm. When I get to wind shaders, I'll probably be tapping you for some tips FYI. :wink:

Re: Herb's Tree Studio - Procedural Trees

Posted: Thu Oct 30, 2014 9:00 am
by Zonder
Herb wrote:@Zonder - Yes, they are cylinders. But, I could extrude a different shape or something when the radius of the branch got to a small enough value. Back when the Woody3d tree library was alive (I ported it to Ogre3D few years back), I like what they did for branches with trees full of leaves. See image below.
Yes I didn't consider that you could extrude something else or like you say when they are small don't extrude anything like in woody (I had completely forgotten about that conversion!). But I think leaves are the thing which will make this shine 8)

Re: Herb's Tree Studio - Procedural Trees

Posted: Fri Oct 31, 2014 6:31 am
by frostbyte
Let me know if you find interest in this too. I'd be more interesting in working on it if others would have use for it
:shock: :D :oops: :mrgreen: :lol:

Re: Herb's Tree Studio - Procedural Trees

Posted: Tue Nov 04, 2014 10:50 am
by nevarim
great work!! :D

Re: Herb's Tree Studio - Procedural Trees

Posted: Sat Dec 06, 2014 3:22 am
by Herb
Alright, got the first pass at adding leaves to the trees. :D It was a bit tricky to work out... Here's a screenshot of a few variation of trees (different amounts of attraction points and random seeds). I have a simple maple leaf I'm adding. Leafs are a quad (to keep triangle count down) and the leaf graphic uses alpha transparency. More tweaking is needed on placement and the angle (and amount) of the leaves, but happy with the initial attempt.

Re: Herb's Tree Studio - Procedural Trees

Posted: Sat Dec 06, 2014 6:12 pm
by mrmclovin
Nice project !!!

I'd love to include this into my planet/space world, if you decide to release an SDK in the future. I'm gonna follow your development! :D

Re: Herb's Tree Studio - Procedural Trees

Posted: Sun Dec 07, 2014 10:12 pm
by Nauk
Good work - Seems pretty useful already, looking forward to watch you progressing :)

Re: Herb's Tree Studio - Procedural Trees

Posted: Mon Dec 08, 2014 9:22 am
by Zonder
Yeah they are defiantly looking good.

Might be worth making it so you can have several different ones, I was thinking of trees in autumn.

Re: Herb's Tree Studio - Procedural Trees

Posted: Wed Dec 10, 2014 12:02 am
by frostbyte
looking good...
i think you should give some love to the tree stump( why does it always have to look like a straight pole? )
on other related notes...
an intersting approach for photo-realistic trees http://www.theastronauts.com/2014/02/ap ... an-carter/
it's very different to procesdural methods...but maybe you can get some insperation and embrace some of their ideas...( go out to the forest and talk to the leaves... :D )

Re: Herb's Tree Studio - Procedural Trees

Posted: Wed Dec 10, 2014 2:17 am
by Herb
@Zonder - Autumn shouldn't be too hard. Different leaf texture, and could have a parameter to cull a certain percentage of leaves to make it appear that the tree has lot some already.

@frostbyte - Thanks for the article link. It was an interesting read. The stump (or roots of the tree) can be produced in a similar fashion as the top, with putting attraction points and growing roots (like branches downward). It's on the list. :)

Really, next step is to spend some time on the UI to get a lot of the render options and such exposed. Then, people could start playing with a demo, which I'd like to make available to folks for feedback. I switched my UI lib to MyGui, as I just got too frustrated with Qt and it I'm very happy with the switch.

Re: Herb's Tree Studio - Procedural Trees

Posted: Wed Dec 10, 2014 9:13 am
by Zonder
I was thinking of season transitions in a game so the leaves going from green -> amber -> red depends on tree I know but you would have a mix of different leaf textures.

Re: Herb's Tree Studio - Procedural Trees

Posted: Tue Mar 10, 2015 8:51 pm
by Herb
Ok, have the first way to "paint" attraction points for the space colonization to use. You can get a little creative now. :wink:

Still need to get a "brush" control to see. I need to do some revamping on the UI next too. Need a toolbox for painting, erasing, etc... It's slowly coming, but still progressing!

And of course a short video to show it off. :D

[youtube]H2IbdwyYI1s[/youtube]

Re: Herb's Tree Studio - Procedural Trees

Posted: Tue Mar 10, 2015 11:02 pm
by frostbyte
wow, this looks like a real fun and fast way to produce trees...
leaves first...nature should consider adopting this method :wink:

Re: Herb's Tree Studio - Procedural Trees

Posted: Sun Mar 15, 2015 11:49 am
by Crashy
Hi,

I've discussed about your project with 3D modellers friends, and they are really interested in such a tool.

We've talked about the foliage lighting problem, and they gave me this link, which might interest you:
http://wiki.polycount.com/wiki/VertexNormal