Gradients 4: Precomputing Mean Value Coordinates and Diffusion

Although I have already shown two really good techniques for calculating gradients using diffusion or mean value coordinates, they don't quite do everything that I want them to do. One of the main benefits of vector drawings over raster drawings is that they are easier to animate, but mean value coordinates and diffusion aren't fast enough for real-time animation. Graphics hardware is optimized for displaying triangles on the screen, so the ideal gradient algorithm would be able to break down a gradient shaded polygon into a set of triangles that can be blasted to the screen quickly by the graphics hardware. We can use techniques similar to 3d animation where the animated geometry is precomputed: we'll try to break down the gradient polygons into triangles in advance, and those triangles can then be animated easily. This does mean that the gradients can't change during an animation, but hopefully allowing the geometry to change during an animation provides sufficient flexibility for artistic expression.

Precomputing a diffusion gradient is a little messy since it relies on a pixel grid instead of the triangles that we want in our final output. If I paid more attention in my classes on calculus and numerical methods, I might be able to rederive the diffusion equations for use on a triangle mesh instead of on a grid, but that's really beyond my mathematical ability at the moment. On the other hand, applying mean value coordinates to a triangle mesh is straight-forward, but mean value coordinates can potentially produce bad values when used on concave polygons. Instead, I've tried to combine both approaches. I'm precomputing a diffusion gradient by using the mean value coordinates as the basis for diffusing values through a triangle mesh. Basically, instead of finessing the problem, I'm going to bash this problem with a brute force hammer until I get something that seems to work. It may have no proper mathematical basis, but it should hopefully produce something good enough for real use.

The first step is to create a triangle mesh over which I can diffuse a gradient. The scientific computation community has all sorts of techniques for computing triangle meshes that are optimal for doing various things, but I don't know any of that work, so I'm just going to put together something hacky. The first step is to use some sort of bog standard polygon triangulation algorithm to create an initial triangulation.

The edges in a minimal triangulation of a polygon always go between corner points of the polygon (i.e. no new points or interior points are necessary). Since these points already have colours, we can build a gradient using barycentric coordinates for the triangles in the triangulation. The resulting overall gradient for the polygon has the correct colours along the exterior edges of the polygon but looks inconsistent and odd in its interior.

Since the main primitive in graphics hardware are triangles shaded using barycentric coordinates, if we want a different colouring at the interior of the polygon, we're going to have to add some new points to the interior of the polygon and change the triangulation. As a heuristic, I generate these new points in this way: I find triangle edges that join points that aren't adjacent in the original polygon, and I split that edge. This gives me extra point that I can use to control the colouring at the interior of a polygon.

From there, I calculate new colours for all the interior vertices I've created inside the polygon. I do this by diffusing colours inwards from the boundary of the polygon: I iterate over all the interior vertices, and I set the colour of each vertex by mixing together the colours of adjacent vertices using the ratio given by the mean value coordinates, and I keep doing that until I reach convergence. In actuality, the mean value coordinates of all the interior vertices actually form a linear system of equations that should be small enough to solve so that might be a better way of computing the final gradient than iteratively diffusing colours through the mesh (in fact, I'm not sure diffusing colours with mean value coordinates will actually converge to the correct values). But I already had code for diffusion but I didn't have code for solving a linear system of equations, so I went with the diffusion route.

If we remove the triangle mesh, we arrive at the final result.

The result is similar to the gradient created by diffusing colours, but it still needs more refinement. The area around the white vertex in the middle of the polygon has too much white because the triangles mesh is too coarse there.