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!).