Tuesday, September 17, 2013

Gradients 5: Refinement of the Precomputed Gradient

One issue with the precomputed gradient was that the triangle mesh was too coarse to capture the details of the gradient. To solve this problem, I progressively refine the triangle mesh until it is detailed enough to show the gradient in the detail that I want. What I do is I first find all the edges of the triangle mesh. I then go over them and look for one that can be split, which creates a new vertex, which can be assigned a new colour, improving the detail in the gradient. When scanning over the edges, I arbitrarily go over them in order from longest edge to shortest edge. I was hoping that doing it that way would help prevent the creation of "skinny" triangles, but in pratice it didn't seem to help too much. For each edge, I split the edge, recompute the gradient, and then compare the new gradient with the old gradient at the vertex points. If the colours of the vertices change by above a certain amount, I keep the split. Otherwise, I revert the split. Then, I move on to the next edge and continue the process until I can't find any edges worth splitting.

Below, I have the triangle mesh generated when splitting an edge doesn't result in any colours changes above 0.1 in any one component (where colours range from 0 to 1).

And here is a triangle mesh when I only split edges that result in a colour change above 0.05. Because I never split exterior edges, there tend to be very long and skinny triangles along the exterior. I guess it would make sense to develop some sort of heuristic to figure out when it makes sense to make a split there.

And if we remove the triangle mesh and just look at the resulting gradient, here is the final result:

The result isn't too bad. The gradient is clearly there, but the colour transitions aren't completely smooth (due to the triangulation). The effect of gouraud shading between edges of the triangle are also visible. The white of the center vertex seems to extend deeper into the polygon that it really should.

But if you compare the generated gradient with that calculated by diffusion or by pure mean value coordinates, the results are decently. Below, the precomputed gradient is in the middle. The diffusion gradient is on the left. The mean value coordinates gradient is on the right.

One of the main reasons for not using mean value coordinates directly in the gradient was that for concave polygons, it could produce illegal colour values that aren't in the range of colours specified along the border of the gradient. As we can from the concave polygon below, we don't encounter any illegal colour values like when using pure mean value coordinates.

Although we still mean value coordinates, because of the way we set them up, it shouldn't be possible to get illegal values. Suppose we have an interior vertex that we're computing mean value coordinates for. Since the vertices adjacent to each interior vertex can all be arranged in a nice clockwise order, the interior vertex ends up with a nice mix of the adjacent colours with all the weights positive and adding to one. So the interior vertex can't have a colour outside the colour ranges of the vertices it is adjacent to. As such you shouldn't be able to get any colour values for an interior vertex that is outside the range of colours assigned to the boundary of the polygon. The problem with mean value coordinates on a concave polygon is that the vertices sometimes run clockwise or anti-clockwise, resulting in negative weights, which can result in the illegal values.

So that's my gradient. The resulting precomputed gradient can be rendered quickly on graphics hardware and has all the nice properties we want from a gradient. The only issue is that it's still a little slow to compute. It would be better if there were a better policy that could be used to create the triangulation of the polygon and its refinement. If I were better at the math, it might be cool trying to develop some sort of process for the diffusion or generating the weights that would result in only local changes to vertex colours when an edge is split, but I'm not sure if that's actually feasible (but it would make the mesh refinement process much faster!).

Wednesday, September 11, 2013

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.

Friday, September 06, 2013

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.

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.