Month: January 2012

Tensor Meshes Revisited

When I first proposed adding meshes to the SVG standard the SVG working group looked at the question of Coons patch vs tensor patch meshes. A tensor patch adds four additional control points to a Coons patch. These control points influence how the color is spread inside the patch. The group decided that the added complexity of the tensor patch was not worth the benefit gain. I am now revisiting this decision. In a previous blog I discussed the problems caused by a lack of smoothness across patch boundaries. At first it didn’t seem like having tensor control points would help but now I realize that in some limited cases they can be of great benefit. Consider the following four patch mesh:
A 2x2 patch mesh showing effect of lack of smoothness across boundaries.

A 2×2 Coons Patch mesh. The outer corner colors are black. The center corner is white.

The first thing that one sees is a cross pattern. This is due to a lack of smoothness across the patch boundaries. In the following figure one can see the color profile for two of the patches that clearly illustrates the sharp change in the color derivative at the patch boundary.
A diagram of the color profile for two of the patches in the above mesh.

The color profile for two of the patches in the previous figure. The height of the surface is proportional to the white level. The red line illustrates the profile along a diagonal line in one of the patches. The blue line shows the required profile if the profile is to be rotationally symmetric around the center point.

By moving the tensor mesh points it is possible to better approximate a rotationally symmetric profile around the center point, reducing the “cross” artifact.
A 2x2 patch mesh where tensor control points are used to smooth the color profile across patch boundaries.

Tensor control points have been used to smooth the color profile.

It is not possible to completely remove the cross using tensor control points. One also still has a bright spot at the center point which is not what one wants when trying to illustrate a diffuse reflection of light off a curved surface. To get a smoother profile one needs to add more patches.
A 4x4 patch mesh with a smoother color profile.

A 4×4 Coons patch mesh is used to produce a smoother color profile.

So adding tensor control points is useful but is not a complete solution to smoothness. I still haven’t made up my mind about their cost/benefit value. Feedback would be appreciated.

Mesh Gradients in SVG

I’ve been working on adding Mesh Gradients to the SVG standard and in principle they have been accepted as part of SVG 2. In particular, the SVG working group has approved the addition of Coons Patch mesh gradients. This type of mesh is powerful enough to handle the requirements for most advanced gradients use cases and at the same time is a convenient form for use in content creation. Coons Patch meshes are included in the PostScript and PDF standards (Type 6 Shading) and the Cairo rendering library supports them in trunk. I’ve added support for meshes to a my own branch of Inkscape for testing purposes. The SVG working group has identified one problem with the meshes: It is not always possible to have smooth color transitions across mesh boundaries. To understand why this can be a problem, one must understand how the meshes work. A Coons Patch mesh is composed of an array of Coons Patches. A Coons Patch consists of four Bézier curves along the sides with colors defined at each corner. The color of any point inside the patch is determined by a two-dimension bi-linear interpolation of the corner colors followed by a geometric mapping defined by the Bézier patch sides.
Left: square showing color interpolation. Right: patch showing result of mapping.

Left: Color defined by a two-dimension bi-linear interpolation of the corner colors. Right: the color interpolation mapped to the patch region. The Bézier end points (corners) and handles are shown as diamonds and circles respectively.

The key word in the above description is “linear”. Working in one dimension, linear interpolation between two colors works exactly the same as in the linear gradient of SVG 1. A patch corresponds to the interval between two color “stops”. The linear gradient in the following figure consists of three stops or two “patches”. The color transition between the two patches is continuous but not smooth.
Top: a three stop linear gradient. Bottom: the RGB color profile of the gradient.

Top: A three stop gradient with stop colors blue, purple, and yellow. Bottom: Plots of the red, green, and blue profiles of the gradient.

Lack of smoothness in some cases can lead to visual artifacts as illustrated in the following figure:
Six linear gradients with the second and fourth stops in different places.

Linear gradients consisting of five stops. The outer two are black, the center one is white, and the remaining two are set to 90% white. The position of the 90% white stops are different for each gradient. The red line shows the black to white profile for each gradient.

As one can see in the above linear gradients, the eye is fooled into thinking that the location of the 90% white stop is whiter than the areas immediate right and left of the stop. This is due to the Mach Banding effect. With meshes, one can move the Bézier “handles” to alter the color profile. This is equivalent to stretching or shrinking a section of the patch. If the side is linear, moving the handles will not change the shape of the patch but will change the “speed” of the curve’s parameterization. The following figure shows how moving the handles can yield a smooth transition and eliminate the Mach Banding:
Three gradients illustrating how to smooth a color transition.

The top gradient is a linear gradient. The middle gradient is a Coons Patch mesh gradient that duplicates the linear gradient. The location of the Bézier handles (circles) are shown in blue. They are at their default positions spaces one-third of the way between the corner points (squares), corresponding to a linear interpolation. The bottom gradient is a Coons Patch mesh gradient where the top and bottom handles have been moved to smooth out the transition across the patch boundaries. The 90% stop has been changed to 80%. The purple line on the bottom gradient shows the new color profile.

As illustrated above, it is possible in some cases to obtain smooth transitions with Coons Patch mesh gradients across patch boundaries. However there are cases where it is not possible. Consider the center “stop” in the above figure. No matter how you manipulate the handles you can not achieve a smooth transition at this point. The derivative of the color profile cannot be made to be zero. The following figure shows some of the profiles available for one patch:
Three gradients showing the range of allowed color profiles when moving Bézier handles.

Three Coons patch meshes are shown where the left corners are black and the right corners are white. Overlaid each gradient is the color profile determined by the handle placements of the top and bottom Bézier curves. The top gradient shows the color profile with the default handle placement (i.e. when a curve is defined by a “lineto”). The Bézier handles of top and bottom of the mesh are shown in blue while the color profile with the profile’s effective Bézier handles are shown in red. The middle gradient shows the the color profile when the handle “lengths” are zero (i.e. when the handles are placed on top of the corners. The bottom gradient shows the color profile when the handles are placed over the opposite corners.

Note that in the above figure the handles of the effective Bézier curve color profile are constrained to horizontal lines one-third of the distance between the top and bottom range of the color profile. As a result, one can never have a profile where the derivative of the color change at a boundary is zero. Also note, that while the handles can be moved outside the patch region to the left or right, a discontinuity in the color profile will result as the effective profile Bézier will overlap itself. Another case where it is impossible to obtain a smooth transition is when the different primary colors (red, green, blue) have different profiles. In general, only the profile of one color can be made smooth. So how do Adobe Illustator and Corel Draw get smooth transitions? I don’t have either one so I can’t check personally but from a paper by Sun, Liang, Wen, and Shum it appears that Adobe Illustrator and Corel Draw use a monotonic cubic spline interpolation instead of a linear interpolation. Then, when exporting to PostScript or PDF, a single Illustrator or Corel Draw patch gets exported as multiple Coons patches inorder to approximate the smooth transitions. The question then is: should the SVG standard support the Coons Patch meshes with bi-linear interpolation or should it specidfy a more complex interpolation. My inclination is to leave the interpolation as bi-linear and follow Adobe’s and Corel’s lead and let the authoring software handle smoothing out transitions when necessary. This keeps compatability with existing standards and keeps the definition of the patches simpler. More details about meshes in SVG can be found at my Coons Patche Meshes page.