2 Comments

Algorithmic trees

This past week was “tree week”. I currently have a small number of tree and vegetation models in my game, but I want a lot more.

Nice models are expensive and/or hard to come by. Plus, in order to have them behave nicely with my wind, I have to tediously paint the vertex colors in a modelling app to identify which parts of the vegetation are stiff.

For algorithmic trees, I used the LTrees library before. It’s an impressive piece of code, but the look isn’t what I want for my game. The leaves are billboarded to face the camera – I want them in fixed positions that look good from an overhead view, plus I need them fixed so they work well with wind.

So I spent several days modifying the LTree library to do what I want. I’ve ended up with the following set of functionality:

  • Leaves are fixed to branches and have better options for orientation
  • Leaves can be further tessellated to an nXn grid
  • This leaf grid can be curved in many different ways to resemble the shape of a real leaf
  • The vertex colors for my wind implementation are automatically calculated
  • I can automatically calculate a per-vertex ambient occlusion term
  • The finished result is exported to a .obj file that can be loaded in XNA’s content pipeline

I’ll go through various parts of this and show the results I’ve gotten so far.

Leaf curves

In the vegetation models I’ve purchased, one thing that lends realism is the curvature of the leaves. This is especially noticeable for plants like the following:

So what kind of curves do leaves have?

I thought about it for a while, and identified a number of obvious ways in which leaves curve:

  • There is an overall lengthwise curve to the leaf
  • Sometimes this lengthwise curve is more sharp at one end or the other
  • There can be a curve across (widthwise) the leaf too

In the LTrees library, I start with a simple quad – or rather the 4 end points of the leaf. These also define the normal, binormal and tangent vectors for the leaf.

Then I further tessellate the leaf (say, making it a 4×8 grid instead of a 1×1), and then adjust the positions and normal vectors to match whatever curve I desired.

But how should I parametrize the curve?

I thought about mapping it to a circle/sphere, but that seemed a bit limited.

I researched bezier surface patches a bit, and that seemed promising. You can get a variety of shapes with them. However, there are 16 control points for a bezier patch. One of my goals was to provide as few knobs as possible for the designer (me) to adjust. I pictured how complex it would be to try to move around 16 points in 3d space to get the leaf curve I wanted. Not to mention the work of implementing such an editor! So this no longer seemed promising.

I thought about using two orthogonal Curve objects to define the leaf curve. XNA has a built-in curve class, and there is even a curve editor as one of the education samples on the Microsoft website. I could just drop that curve editor into a small app and go. I actually spent some time doing that, but the result seemed clumsy.

In the end I went back to mapping the curve to a circle. This is easy to understand, provides a small set of knobs, and generates (I think) fairly good results.

The knob is basically the radius of an imaginary circle onto which one axis of the leaf is wrapped. To add extra variety, I can provide a second radius – one for one end of the leaf, and a different one for the other. This allows me to strength or weaken the curve of the leaf over its length.

In addition, I supply a third radius for the imaginary circle that bends the leaf cross-wise. The end result looks fairly reasonable:

Additionally, I allow for a crease down the center of the leaf. This is implemented by rotating vertices around the binormal that runs down the crease (the binormal points down the length of the leaf). Vertices on either side of the rotation axis rotate in opposite directions. Here’s what it looks like, with normal-based shading applied:

It was a fair amount of work to implement all that. What kind of plants did I make from it? A simple one that is just leaves:

This is what it looks like in the editor. You can see the tessellation needed for the curve:

Here’s a weird one where the leaves curve in the opposite direction:

These are both algorithmic plants defined in XML, and generated from a random seed.

Ambient occlusion

When working with pre-made models, I used a script in Blender that calculates ambient occlusion. I want to remove Blender from the workflow here, so I implemented that functionality in my tree editor:

It’s basically the same implementation as the blender script I used to use. It iterates through all vertices. For each one, it casts a number of rays (I think I use 13 right now) of a certain length in a hemisphere centered around the normal of the vertex. It determines the ambient occlusion value by how many rays hit other triangles in the tree.

For an extra touch, I take into account the transparent parts of the leaves (this is something that the script in Blender couldn’t do).

While I’m at it, this seems like a good place to show how the vertex colors that define the wind behavior are done:

Other trees

It typically takes about one or two hours for me to make a tree now. Of course, the longer I spend, the better the results.

Here’s a devils club plant:

And I tried making a Joshua tree. This is difficult because of the nature of the leaves, but I managed to get something passable by placing several instances of the leaf quad in different orientations overlapping each other:

It would be more realistic if the leaf spikes were smaller, but really thin objects are problematic for rendering.

Challenges

Here are some trees that didn’t go so well.

First, an attempt at making a tropical rainforest tree (Kapok):

You can clearly see my curving leaf primitives here. This looks awful, I think, simply because of the texture I used. Achieving the right leaf scale is important. The textures are from an overhead view of tree canopies. So you’re looking at thousands of tiny leaves in each texture.

(Also, I think a normal mapping shader would help a lot here).

As for the importance of scale, here’s what happens when I use the wrong scale in the other direction:

It maylook somewhat “pretty”, but it looks wrong because of the leaf scale. If each texture were 6 or 7 smaller maple leaves, I think it would be an improvement.

Here’s something that I think has a better scale, but still looks awful:

I think I just need to spend some more time arranging the leaf textures in a better fashion. Defining the trees in XML is definitely an art, and it takes some time to get something reasonable.

Other improvements

One improvement I would like to make (if performance measurements suggest it is worth it) is to minimize the wasted space in the leaf primitives. Consider the following devils club leaf:

Probably over 50% of the pixels are transparent – this is time that the pixel shader has spent doing nothing useful. You incur a huge amount of overdraw when rendering clip-tested primitives like this. Eventually I would like to find a way to  adjust the vertices to eliminate much of the wasted space around the edges.

Conclusion

This is what the editor looks like so far:

Of course most of the actual tree definition is in the XML file.

There are still a number of things I would like to have support for: root structures to give a more realistic appearance near the base of the tree, “fruit” objects, stumps.

So what do you do to get nice-looking trees? My game uses an overhead view, so what works for me would probably not work for games with a more “on the ground” perspective. And how do you create good leaf textures?

 

Addendum

Here’s an attempt with smaller leaves on the maple (on the left). I think it looks a little better.

Advertisements

2 comments on “Algorithmic trees

  1. Good results 🙂 proper leaves are a great replacement to billboarded sprites – and your editor looks fun to use.

  2. Great work! I have been putting this off for a while.Thanks for the info!

Leave a Reply

Fill in your details below or click an icon to log in:

WordPress.com Logo

You are commenting using your WordPress.com account. Log Out / Change )

Twitter picture

You are commenting using your Twitter account. Log Out / Change )

Facebook photo

You are commenting using your Facebook account. Log Out / Change )

Google+ photo

You are commenting using your Google+ account. Log Out / Change )

Connecting to %s

The Space Quest Historian

Adventure game blogs, Let's Plays, live streams, and more

Harebrained Schemes

Developer's blog for IceFall Games

kosmonaut's blog

3d GFX and more

Halogenica

Turn up the rez!

bitsquid: development blog

Developer's blog for IceFall Games

Game Development by Sean

Developer's blog for IceFall Games

Lost Garden

Developer's blog for IceFall Games

Memories

Developer's blog for IceFall Games

Casey's Blog

Developer's blog for IceFall Games

Blog

Developer's blog for IceFall Games

Rendering Evolution

Developer's blog for IceFall Games

Simon schreibt.

Developer's blog for IceFall Games

Dev & Techno-phage

Do Computers Dream of Electric Developper?

- Woolfe -

Developer's blog for IceFall Games

Ferrara Fabio

Game & Application Developer, 3D Animator, Composer.

Clone of Duty: Stonehenge

First Person Shooter coming soon to the XBOX 360

Low Tide Productions

Games and other artsy stuff...

BadCorporateLogo

Just another WordPress.com site

Sipty's Writing

Take a look inside the mind of a game developer.

Jonas Kyratzes

Writer, game designer, filmmaker.

%d bloggers like this: