# Stochastic Pruning for Real-Time LOD

Posted: January 12th, 2010 | Tags: , , , | 5 Comments »

Rendering plants efficiently has always been a challenge in computer graphics, a relatively new technique to address this is Pixar's stochastic pruning algorithm. Originally developed for rendering the desert scenes in Cars, Weta also claim to have used the same technique on Avatar.

Although designed with offline rendering in mind it maps very naturally to the GPU and real-time rendering. The basic algorithm is this:

1. Build your mesh of N elements (in the case of a tree the elements would be leaves, usually represented by quads)
2. Sort the elements in random order (a robust way of doing this is to use the Fisher-Yates shuffle)
3. Calculate the proportion U of elements to render based on distance to the object.
4. Draw N*U unpruned elements with area scaled by 1/U

So putting this onto the GPU is straightforward, pre-shuffle your index buffer (element wise), when you come to draw you can calculate the unpruned element count using something like:

[sourcecode language="cpp"]
// calculate scaled distance to viewer
float z = max(1.0f, Length(viewerPos-objectPos)/pruneStartDistance);
// distance at which half the leaves will be pruned
float h = 2.0f;
// proportion of elements unpruned
float u = powf(z, -Log(h, 2));
// actual element count
int m = ceil(numElements * u);
// scale factor
float s = 1.0f / u;
[/sourcecode]

Then just submit a modified draw call for m quads:

[sourcecode language="cpp"]
glDrawElements(GL_QUADS, m*4, GL_UNSIGNED_SHORT, 0);
[/sourcecode]

The scale factor computed above preserves the total global surface area of all elements, this ensures consistent pixel coverage at any distance. The scaling by area can be performed efficiently in the vertex shader meaning no CPU involvement is necessary (aside from setting up the parameters of course). In a basic implementation you would see elements pop in and out as you change distance but this can be helped by having a transition window that scales elements down before they become pruned (discussed in the original paper).

Tree unpruned

Tree pruned to 10% of original

Billboards still have their place but it seems like this kind of technique could have applications for many effects, grass and particle systems being obvious ones.

I've updated my previous tree demo with an implementation of stochastic pruning and a few other changes:

• Fixed some bugs with ATI driver compatability
• Preetham based sky-dome
• Optimised shadow map generation
• Some new example plants
• Tweaked leaf and branch shaders

I use the Self-organising tree models for image synthesis algorithm (from SIGGRAPH09) to generate the trees which I have posted about previously.

While I was researching I also came across Physically Guided Animation of Trees from Eurographics 2009, they have some great videos of real-time animated trees.

I've also posted my collection of plant modelling papers onto Mendeley (great tool for organising pdfs!).

Tree pruned to 70% of original

### 5 Comments on “Stochastic Pruning for Real-Time LOD”

1. 1 Graham Reeves said at 9:01 am on January 13th, 2010:

I used a similar technique (without realising it), when rendering the crowd in Beijing 2008. The crowd member [instances] were randomly indexed and used the camera distance to the group's "center" point to render 0..N of the instances with full alpha and then a second render of the same instances of N..X with 1-bit alpha. As well as varying X for a 0-100% amount of the crowd being rendered in general, I think we settled on 80%. You couldn't tell that 20% of the seats were empty. Sega or the IOC (I forget which) insisted there would never be empty seats in the olympics, so we had to tell them 100% of the seats were filled.

The further away from a stand (the group of instances) the more 1 bit alphas were rendered. I think I called it noisy LOD

The artifacts are visible (to me at least) in this screenshot...

2. 2 mmack said at 9:31 am on January 13th, 2010:

Thanks Graham, that's interesting - I also vaguely remember hearing that Colin McRae Rally used something similar for the long dust trails way back when.

The problem for trees is that this approach really only works for disconnected elements (leaves). Simplifying the branches is a bit more difficult but I think progressive meshing would work OK. At least it would be easy to assign edge weights based on tree depth..

3. 3 Graham Reeves said at 11:33 am on January 13th, 2010:

Yeah I doubt it would be that difficult, random shuffling is all well and good, why not do a weighted shuffle based on the branch volume. Little branches would be (sorry) pruned away.
It's all just simple LOD techniques, I guess the CG types are catching up to us RTR'ers

4. 4 Sander van Rossen said at 11:07 pm on May 26th, 2010:

Amazing work!
Thanks for sharing

5. 5 Dorian said at 2:22 pm on September 11th, 2011:

Thank you very much! As a Maya TD I spend time trying to understand how stochastic pruning work and the Pixar paper is a little technique! Your method is simple and the OpenGL tool you give really help me to understand "what that mean in the image".

Thank a lot!

EDIT: I just see there is no post anymore on your blog. That's a shame because it is very good! ðŸ˜‰