Gradients 3: Mean Value Coordinates

Although building gradients through diffusion produces nice results, the actual computation of these gradients is slow and cumbersome. Ideally, we want something like triangle barycentric coordinates but for arbitrary polygons: we want a nice simple equation that can be computed at arbitrary points inside a polygon that provides a nice gradient for us.

Fortunately, such an equation exists. It is called Mean Value Coordinates, and it was constructed/discovered by Michael Floater a few years ago. If you want to calculate the colour of any point in a polygon, you just take the colours of all the corners of the polygon, feed them into the equation described in the paper, and it will tell you how to mix the colours together to get the final result. The equation generates nice smooth gradients with practically all the properties you could want from a gradient such as linear transitions of colours along edges etc. What this means is that instead of having to iterate over the pixels of a polygon repeatedly to diffuse colours over it, you can just compute the gradient in a single pass over the pixels. Below is a picture of how a gradient computed using Mean Value Coordinates looks like. Notice that it is almost identical to the gradient produced using diffusion.

Mean value coordinates seem like the perfect solution for solving all gradient problems. In most cases, they are, but there are still a few tiny issues. One is that the gradients are supposedly not bilinear for rectangles. This means that if you map an image onto a rectangle using mean value coordinates, the image will be warped and won't perfectly reproduce the original image. Although this may be true, my tests with mean value coordinates seemed to indicate that this effect is hardly noticeable.

Another problems arises with concave polygons. When dealing with concave polygons, the colours of the gradients might not stay within the range of colours given to the corners of the polygon. In the image below, a gradient is constructed over a polygon where all the corners of the polygon have a grey value of 0.1 except for the two middle points, which are assigned a white value of 1.0. Although the gradient looks quite nice, some parts of the polygon end up being coloured with grey values less than 0.1. In the right image, pixels with grey values less than 0.09 are coloured in red, showing the region where the gradient is outside the range of colours given at the corners. This is worrisome. For concave polygons, the gradient might contain illegal colour values (like colour values less than zero). This effect also prevents you from creating a gradient of texture coordinates because the coordinates might be mapped outside the range of the texture.

Lastly, although mean value coordinates are much faster than diffusion, you still can't use them directly in real-time animation because they are too slow. Calculating mean value coordinates for a pixel requires merging in all the colours of a polygon's corner points, but there could potentially be a lot of points, especially when trying to recreate a curve using polygons. Trying to do these calculations in graphics hardware would be difficult for polygons with large numbers of points. So some sort of precomputation is needed to use mean value coordinates in an animation.