Advanced gradient fills in SVG


Table of Contents

Vertices-based gradient fills
Contour based gradient fills
1. Raster to vector conversion
How to implement such vectors into SVG
Conclusion
References

The gradient fills inside some area require only a non-empty set of vertices. That's all. Therefore, the problem is how to interpolate color from the set of vertices to the whole area to be painted. There are some methods in the theory of elasticity that can be used here. Splines are optimal for 1D interpolation. The cubic spline actually is a thin flexible ruler, deformed under a set of point forces. Its direct analogue for 2D is a thin flexible sheet and the set of point forces. In both cases energy of a deformed object is to be minimized. Therefore, 2D interpolation, based on an analogue of the thin flexible plate, has some extremal properties. A shape of this sheet can be described by a biharmonic equation. And the solution of this equation is the optimal method for 2D interpolation. This method has a whole list of advantages. Without the mesh, corresponding file is significantly smaller. Both editing and creation of such a gradient is simpler compared with mesh-based methods. It is very easy to add any number of additional vertices, delete some of them, change their position etc. It does not matter where vertices are to be placed: inside the area to be painted, onto its border or outside (the last option hardly will be used, but it is possible). Of course, solving biharmonic equation is not such a simple task. If number of vertices is not very large (few hundreds), it is possible to construct solution as a sum of fundamental solutions of the biharmonic equation, multiplied by some unknown coefficient plus a linear function. To get these coefficients, one needs to solve linear system of equations. Dimension of this system equals to a number of vertices + 3. This is why this method becomes inefficient, when number of vertices is comparatively large. Alternatively another methods, based on direct solution of a biharmonic equation (sparse matrix and so on), can be used here. A program (SVSViewer), demonstrating which sort of images could be created using this approach, is available at (2). But, despite this method is able to convert raster image into vector format with nearly photorealistic quality, it has some disadvantages too. Vertices cannot be placed too close to each other, that limits color gradient inside a region to be painted. This is why raster to be converted to vector must be split to a set of pieces, something like mosaic or window. And inside these mosaic pieces, color gradient must be below some threshold. Not a problem, if contours, separating differently colored regions of a raster are loops. But many of these contours that are present in a raster image are open ones. Therefore, some additional contours are necessary as each region to be painted must be enclosed and separated from the others. But, there are other methods without this disadvantage.

One highly efficient method is described in (1). This method is named Diffusion Curves. This method does not need all contours to be enclosed lines; in fact contours can have any shape. Each contour is a double-sided line. Color of the left side of the contour differs from color of the right one. Interpolation to the whole image to be painted is based on Laplace equation (authors of (1) claim that they solve Poisson equation, but it is obviously a mistake). This is an efficient method, producing nice-looking vector images. Author, wanting to create contour based gradient fills, uses similar approach- the same equation, but another partial solution. Programs, intended to demonstrate this method (PaintingPen, PaintingPenDemo) are available for download at (2). However, the Diffusion Curves method has some disadvantages, too. Let's try to convert a raster to vector, using such approach. At the first stage one needs to convert a source raster image to a contour image. Later these contours will be used as a base to paint the whole image. But, it is quite clear, that it is hardly possible to keep color of a big region under control, using only information, distributed along its border. Thus, some additional invisible contours are necessary (any contour can be done invisible by applying an unsharp mask- it is obviously not the best method, if all what one needs is to place some vertices onto this region). This is why author believes, that the most efficient way to convert a raster to vector is the combination of both above described methods.

Let's run through process of a raster to vector conversion. We will speak for simplicity about grayscale images. This process consists of four stages. Two complex matrices with the same size as the source raster are to be created. The first matrix is filled with gradients of the source raster: real component with a gradient along x-axis, imaginary component with a gradient along y-axis. The second matrix is initially filled with zeros. If a module of the gradient at some point of the first matrix is above some predefined threshold, this complex gradient is exchanged with the gradient of the same point of the second matrix (gradient is moved to the second matrix, zero to the first one). After this operation, the first matrix contains only gradients below the threshold noticed above, therefore corresponding color distribution will be smooth. This color distribution can be restored, using relatively small number of vertices. The second matrix contains gradients above the predefined threshold and these gradients are distributed along edges, what really are present in a source raster. No additional contours are required at all. Corresponding color distribution can be obtained as a convolution with the derivation of the fundamental solution of the Poisson equation- K(z)=1/z. This color distribution is similar to a set of slices, made by scissors: one side of such a slice is lighter, the opposite darker. The difference between author's approach and the one used in (1) is that author does not fix color of both sides of contours but only their difference. This is why the proposed method is much faster and has no need in powerful video accelerators like Nvidia GeForce 8800. Convolution can be performed, using FFT. Due to the nature of hi-gradient matrix, the way to convert it to a vector object is obvious. This matrix is filled with zeros, except some contours. It looks like a set of walls with variable height. The set of these contours can be converted to the set of vector objects, using traditional technology. Each contour can be converted to the Bezier polyline. Let's assign to a link number N a real parameter s, what changes from N-1 to N inside this link. Then the gradient, distributed along a curve, may be converted to a spline, depending on that parameter. The first (low-gradient) matrix should be converted to a vector object, using vertices-based method. Color distribution, corresponding to the first matrix, can be obtained in the same way as a convolution with the same kernel. This color distribution must be reproduced with the predefined accuracy with the aid of interpolation from a set of vertices, placed onto the first (low-gradient) matrix. There are in fact two problems: where (and how many) vertices have to be placed and what colors have to be assigned to them. The first problem is non-linear, but some practical approaches are possible here. This process is shown on Fig. 1- Fig. 2.



There are some additional kinds of records to be included into SVG specification to make it able to support advanced gradient fills. They could be something like this:

      
  <fills>
    <path d="M147 4 C151 1 152 2 154 4 C157 6 166 9 169 11 C171 13 174 15 177 16 C186 21 199 28 203 30 C205 32 208 33 147 4"/>
    <vertex> "V26 10 #484d4e V42 16 #44464f V6 16 #363b36 V34 14 #313a35 "</vertex>
    <slice>
      <path d="M145.3 329.8 C149.5 326.2 151.3 334.0 154.9 328.0 C156.7 325.0 156.7 316.6 160.9 320.8 "/>
      <sf:parameter d="s0.0 p18.1 s0.3 p12.7 s0.9 p-7.7 s1.7 p-8.9 s2.0 p-13.0"/>
    </slice>
  </fills>

    

The second tag (path) describes a path, bounding region to be painted. If it is not exist, the whole image has to be painted. The third tag (vertex) describes the set of vertices. They consist from coordinates and RGB triplets. The fourth tag (slice) describes a contour line namely its shape and a parameter, distributed along this line. This parameter is the difference in color between the left and the right sides of a contour line. Currently author does not know, how to modify this record for true color images. Of course, instead of one scalar parameter there should be RGB triplets. Problem is that original RGB triplet consists of three positive values. But their difference may adopt negative values as well.

Author believes, that advanced gradient fills, described here, will allow this format to produce such vectors images, which could be hardly obtained by any other vector format. It is quite clear, that the current state of vector graphic is not an ultimate achievement of humankind. There is no great problem to incorporate such functionality into SVG format. More difficult task is to include support of above described gradients into some of common programs (browsers, editors, raster to vector converters etc). But it is a worthwhile thing due to the fact, that advanced gradients have the whole list of advantages. Smaller size and better quality of vectors, produced by above described technology, compared with vectors, produced by another converters (Rave Grid, Vector Eye, Live Trace and so on) is crucial, when one wants to edit such vectors manually. Intel will be happy, because rasterisation of such vectors requires lots of computations.

1. Alexandrina Orzan, Adrien Bousseau, Holger Winnemцller, Pascal Barla, Joлlle Thollot, David Salesin. Diffusion Curves: A Vector Representation for Smooth-Shaded Images. diffusion_curves.pdf[12.8Mo]

2. Andrey Matseevskiy. Advanced gradient fills in vector graphic. Soft, based on above described technology, is available here