What's the best way to draw lots of trees

Question

I'm writing an app which renders a random island planted with trees. The trees are currently two quads, criss-crossed and drawn with textures. I plan to have more complex meshes that form different plant types, e.g. a palm tree, oak, grasses etc..

The problem I face is that because the textures are transparent I must draw them from back to front. Plan-b is to call of using discard in the frag shader, but z-order gives better results:

uniform float uTreeAlpha;
uniform sampler2D uTexture;

varying vec2 vTexCoordOut;

void main (void)
{
  vec4 colour = texture2D(uTexture, vTexCoordOut);
  if (colour.a < 0.1) {
    discard;
  }
  gl_FragColor = vec4(colour.rgb, colour.a * uTreeAlpha);   
}

The second problem is because the order changes depending on camera & lookat I do not know an efficient way to draw them in OpenGL in a single call.

At present my rendering code looks like this pseudocode:

if cameraChangedFromLastTime() then
  sortTreesBackToFront();
end
for i = 0 to trees.size() -1
  drawTree()
end

Where every drawTree() sets some uniforms, sets the texture, and then calls glDrawArrays(). I have some optimisations to skip setting a texture or updating texture coords if the last tree and the current are the same, and setting some common uniforms outside the loop, and of skipping trees which are too far away but basically if I have 3000 trees I go 3000 times around the loop.

Drawing each tree individually is the performance killer. If I could draw them in a single call, or batches (while preserving Z-order) I'd probably so in 1/10th the time.

So how would I do that. Bear in mind that my trees are placeholders and eventually I would have:

• Different meshes for different trees
• Different scales and angles for trees to give some more variety
• Different textures for different trees, potentially multiple textures applied to a mesh (e.g. leaves one texture, trunk another)
• Trees are all mixed together so no simple way to draw one kind and then another
• Some form of simple cyclical animation (branches bobbing in the wind)
• All textures would reside in a single atlas

So what's best approach here? Is it feasible to render in a single pass? If I used glDrawElements, rebuilding the indices but not the vertices, could I achieve this?

Answer 1

What you want is hardware instancing. Note: I've done this in XNA (i.e. DirectX), but I don't know much about OpenGL. I'm positive there is a comparable feature, though. Basically what it amounts to is binding together the vertexes of your tree model with another vertex stream that carries world coordinates for each instance.

Answer 2

The transparency only needs to be ordered if it uses non-additive blending. For a ton of distant billboards, the blending is unnecessary (you can't really see it). Render at least the further ones with cutout transparency (alpha of only 1 or 0) and you don't need to sort them.

You can use a sprite sheet of sorts to render different types of trees, with baked animations. Draw meshes for closer trees which you can animate with more fidelity based on winds or whatever you want.