Sunday, September 01, 2013

Gradients 2: Diffusion

The main way of understanding gradients mathematically, is to view them as a 3d surface or 3d patch. The surface is bounded by the 2d shape you are filling, and the height of the surface corresponds to the colour of the gradient. So for a black and white image, the height of the surface function would refer to the grey-level of the gradient. For an RGB colour image, you might have three different surface functions for each of the red, green, and blue values of the gradient.

Finding a gradient then comes down to finding an appropriate surface function or height map that matches the properties that you want for the gradient. This is why many 2d vector drawing programs include support for gradient meshes. The gradient meshes map directly onto well-known mathematical shapes such as coons patches or bezier patches that can be used as a surface for the gradient. Unfortunately, when trying to build a gradient for an arbitrary polygon, gradient meshes are sometimes cumbersome to use because they might not fit into the shape of an arbitrary polygon and they have many control points that need to be adjusted to get the desired effect.

In the last few years, there has been a lot of talk of using diffusion curves for drawing images with lots of smooth shading. Diffusion curves can form a suitable basis for drawing gradients in arbitrary polygons. The main algorithm for actually determining the height map of the surface that forms the gradient is described in Sketch based coding of grey level images. The basic idea is that you specify that certain points have to be certain colours, and the algorithm then tries to interpolate the colours between the points. Since you want the shading to be "smooth," the algorithm should try to minimize how quickly the colour changes across the surface. Since this is a surface, the change in colour at any point can be expressed as ∂f/∂x and ∂f/∂y. Since you want to minimize the change in colour across the whole surface, you should integrate those changes over the surface and minimize that value: ∬(∂f/∂x)² + (∂f/∂y)². If you want to minimize that value, you just have to take the derivative, set it to zero, and try to solve. Solving it requires the use of discrete calculus, the Laplacian, and various numerical techniques.

It all sounds messy, but you can actually skip over all the math and jump right to the punchline. In the final algorithm, all you have to do is, first, set colours for certain points in your image that you want be fixed. Then you repeatedly go over the image, and for each pixel, you set it to the average value of the adjacent pixels. If you keep doing this, colours will eventually diffuse throughout the image, and you will get your gradient.

Below is a gradient I created for a concave polygon with different colours at each point:

Although the gradient is very smooth, the diffusion is too uncontrolled. For example, the colour from the white point at the center of the polygon diffuses to many of the edges of the polygons. This is problematic because it means that the colours along the edges of the polygon are dependent on colours used throughout the polygon. This makes it hard for users to create two polygons beside each other with the same colour along their edges.

The diffusion curves paper solves this by strictly defining what the colours along the edges of the polygon should be. Along the edge of the polygon, the colours should be a linear mix of the colours at the points on each end of the edge. So when doing the diffusion, not only do we set the colours along the ponts of the polygon but along the edges as well. Below is a picture of the result. Notice that the white colour of the point in the middle no longer influences the colours of polygon edges that it isn't adjacent to.

So that's how you can build gradients using diffusion. The main problem with this technique though is that it's slow. Diffusing colours throughout an image until you reach convergence can take a lot of iterations. You can use multigrid techniques to get reasonable speed, which basically means you start with a very low resolution image, and slowly up the resolution as you diffuse your colours. Unfortunately, it's still too slow for real-time graphics like what you would want in a game, for example.

No comments:

Post a Comment