This is a super short post about something I want to be able to reference again in the future (:
Let’s say that you need to average N things, where you don’t know what the final N will be, but you want to keep an average as you go.
For instance, let’s say you are doing monte carlo path tracing rendering, where the pixel you are showing is the average of however many samples you’ve had so far, but you are continuing to get new samples and want to show the updated average as you get new samples.
The formula for doing this is super simple.
NewAverage = OldAverage + (NewValue - OldAverage) / NewSampleCount; // Or: Average += (NewValue - Average) / NewSampleCount;
One way of thinking of the above equations is that you are adjusting the average by how much the new value would adjust the average.
Another way of thinking of the above two equations is this:
First figure out how far the new sample is from the average, then move towards that new amount by an ever decreasing amount, as the number of samples grow.
Because of this, if you are in a language such as glsl or hlsl which has linear interpolation built in (mix in glsl, lerp in hlsl), you can use linear interpolation as well:
Average = mix(Average, NewValue, 1.0 / NewSampleCount);
To see how this works out, check out the formula for lerp:
Substituting Average for a, NewValue for b, and 1/NewSampleCount for t, we get this:
Which is the exact same formula as above. So, using lerp in that way is mathematically equivalent.
Here’s a link with more discussion on this:
Math Stack Exchange: Incremental averageing
Here’s an awesome post on this same subject, with a different resulting formula, by Christer Ericson (@ChristerEricson), author of the famous “Real Time Collision Detection” book, and VP of technology at Activision. His solution looks like it might be more numerically robust, but I haven’t analyzed it well enough yet to know for sure:
Robustly computing the centroid for a point set
When you are actually doing this incremental average in a graphics setting, you might find yourself storing the average so far in the RGB channels of a float4, and storing 1/sampleCount in the A channel. You could alternately store SampleCount in the A channel, but if you are storing 1/sampleCount, there is an easy way to update that A value to be the next value:
If you try it out, you will see that 1 becomes 1/2, becomes 1/3, becomes 1/4, becomes 1/5 etc. That formula is less cumbersome than doing 1/A to get the sample count, adding 1 to it, and then doing 1 divided by that value to get the new value.
A somewhat related topic, here’s a method for keeping a sum with floating point numbers, that is more accurate than normal summation. Useful when you need to sum numbers of different magnitudes, which would normally be a problem in floating point.
Wikipedia: Kahan Summation
Here’s an incremental (aka online) algorithm that gives you the average as well as the variance, which you can square root to get the standard deviation. This is useful for when you need to know how volatile data samples are – like if reporting results from profiling code, or maybe useful for path tracing for finding how much variance is in a pixel, so you know whether you need more samples or can get away with fewer.
Wikipedia: Standard deviation – Online algorithm