# Curvature Sampling

Importance Sampling theory is used in graphics and other fields to reduce variance when integrating a function such as evaluating the rendering equation. Here *important* samples are the ones that contribute most to the integral, so large values (e.g. a light source reflected on a glossy surface). By focusing samples at large values of , the variance of each contribution to the integral is reduced – i.e. the area of each bar is roughly the same:

The PDF is shown in red, and is a normalised version of the function itself, which happens to be (excuse the strange form, it was the result of tweaking to get a nice variation in curvatures).

Thinking about this from a numerical integration point of view, each of the bars is a good estimation of the area under its part of the curve if the function is roughly linear there – then the error in the left half of the bar is equal and opposite to the area in the right half of the bar, so they cancel each other out. An idea then is to sample according to a measure of the curvature of the function – in this case the absolute value of the second derivative. This gives the new PDF (red) and bar distribution (grey) shown below:

As expected, the bars are concentrated where the curvature of the function is high. When the curvature is low, the function is well approximated by a straight line, and a wide bar gives a good estimate of the area. A quick mathematical justification: if we do a Taylor expansion of around the center of a bar at , we want to minimize the even terms (error from the odd terms cancel out as mentioned). By focusing samples where is large, we reduce the width of bars and therefore in the error terms of order 2 and higher, therefore reducing the error.

For this simple scenario, the curvature sampling does better – its error is -0.00024, whereas the error for the importance sampling shown above is -0.01093. I don’t know that this is true of the general case. I tried to see if I could follow a similar analysis to this very useful resource from Art Owen to see if I could find some evidence that sampling proportional to the second derivative reduces variance more effectively but I quickly got stuck trying to integrate something like which didn’t go well.

It does seem intuitive though that curvature sampling should work. In practice obtaining the second derivative of a potentially unknown or complex function is likely to be difficult or impossible, but there might be particular situations where this is useful. Since I couldn’t find anything about this on the net, thought I’d write it up and park it here. I’m sure this is just a special case of some more general existing work – if anyone can identify this please let me know in the comments!

## Leave a Comment