# Quirk in VertexColors interpolation when displaying Polygon

When using VertexColors the docs state:

The interior of the polygon is colored by interpolating between the colors specified by VertexColors.

It however doesn't say how this interpolation is carried out. I've seen at times that small quirks show up that I wouldn't expect, and I'm wondering if someone else has a clearer perspective on exactly why and when these show up.

 aim = {Cos[2 \[Pi] #], Sin[2 \[Pi] #]} &;
angles[n_] := Range[0, 0.5, 0.5/(n - 1)];
colors[n_] := Join[ConstantArray[Purple, n], ConstantArray[Orange, n]];

draw[n_, a_] :=
Graphics[{
Polygon[Join[aim /@ angles[n], a aim@# & /@ Reverse[angles[n]]],
VertexColors -> colors[n]
]}]


Using this definition and n->5, I don't see anything wrong when a->0.415 but when a->0.414 it looks like it's interpolating incorrectly, and when n is set larger two such quirks appear which seem to always be present. This can be seen in the three calls:

 GraphicsColumn[{draw[5, 0.415], draw[5, 0.414], draw[100, 0.415]}]


So the question is, why does this happen and is there a general way to avoid it, or test for when it's expected to happen?

I know that for this particular example I can avoid it simply by splitting my single polygon into many smaller 4 point polygons, I'm not asking for code that just draws a shaded arc. I'm interested in the underlying problem.

-
did you check if all the polygons are oriented counter clockwise? Perhaps that's an issue. –  user21 Dec 12 '12 at 12:37
@ruebenko There is only one polygon. It happens to be oriented counter clockwise, but the same behavior is present independent of orientation. –  jVincent Dec 12 '12 at 12:46
My guess is that the best general way to deal with this is to (1) triangulate your large polygon (2) assign vertex colors to the newly introduced vertices (could be tricky, in general) and (3) display the whole thing. –  Mark McClure Dec 12 '12 at 15:31
@MarkMcClure A triangulation shouldn't introduce new vertices, unless you mean to resolve self intersections simultaneously. In such cases I would suspect it would be trivial to just do a linear interpolation at the intersection point. –  jVincent Dec 12 '12 at 15:51
Depends on how you triangulate! :) I described one tool for triangulation in this answer: mathematica.stackexchange.com/questions/3646/… Of course, that's not necessary for this example but, perhaps, one would find themselves using that on another example. –  Mark McClure Dec 12 '12 at 16:02

The behavior you are seeing is, that OpenGL (which is most probably used) has to break your your polygon of many vertices into triangles. What you then see are artifacts of the linear interpolation of the colors. When you assign a random color to each vertex, you can observe the triangle structure

aim = {Cos[2 \[Pi] #], Sin[2 \[Pi] #]} &;
angles[n_] := Range[0, 0.5, 0.5/(n - 1)];
colors[n_] :=
Join[ConstantArray[Purple, n], ConstantArray[Orange, n]];

draw[n_, a_] :=
Graphics[{
Polygon[Join[aim /@ angles[n], a aim@# & /@ Reverse[angles[n]]],
VertexColors -> (RGBColor @@@ RandomReal[{0, 1}, {2 n, 3}])]}]
Manipulate[draw[n, a], {a, 0.4, 0.5}, {n, 5, 20, 1}]


To my knowledge, it is not possible to influence the process of breaking a polygon down to triangles and therefore ensure a satisfying colorization. What you can do of course is, give triangles as polygons and therefore ensure this manually.

In your case this would be something like

points[n_, a_] := {#1, #2, #4, #3} & @@@
Partition[Flatten[Transpose[{a #, #}], 1], 4, 2] &@
Table[{Cos[phi], Sin[phi]}, {phi, 0, Pi, Pi/(n - 1)}];
Manipulate[
Graphics[Polygon[points[n, a],
VertexColors ->
ConstantArray[{Orange, Purple, Purple, Orange}, n - 1]]], {a, 0.4,
0.5}, {n, 5, 20, 1}]


-
So really the problem is that it's doing a less then optimal triangulation which actually seems to result in zero area triangles at times. Is there any documentation or information about which method is used to break it down? Perhaps someone knowledgeable in triangulation algorithms would know, Afaik Delaunay triangulation avoids these effects. –  jVincent Dec 12 '12 at 13:16
Yes, I'm sure but not in Mathematica, because this is an OpenGL problem. Look for instance down this page. Looks familiar, right? If you want to know more, you could check the sources of the Mesa free OpenGL implementation. –  halirutan Dec 12 '12 at 13:25

As stated in my answer the problem for the arc was solved with just creating polygons such that they ended up without defects similar to how halirutan did it. Which is a method to avoid these problems in specific cases. But in the general case this doesn't work out, so I also found a solution by triangulating the polygon using the Delauyney triangulation. This seems to work, and my intuition tells me it should work for all non self intersecting polygons(* My intuition fails me, see update):

 Needs["ComputationalGeometry"]

trisFromDelaunay[o_,l_]:=Sequence@@({o,Sequence@@#}&/@Partition[l,2,1])
triangulate[points_]:=trisFromDelaunay@@@DelaunayTriangulation[points]
filter[indices_]:=Select[indices,Signature[#]==1&]

polygonColoredTris[points_,VertexColors->colors_]:=
Polygon[points[[#]]&/@#,VertexColors->colors[[#]]]&/@filter[triangulate[points]]


This seems to work nicely for my current uses.

n = 50;
l = 0.3; u = 1.9;
spiral = Join[#, Reverse[0.6 #]] &@(# aim[#] & /@ Range[l, u, (u - l)/(n - 1)]);
spiralColors = Blend[{Purple, Orange}, #] & /@ Range[0, 1, 1/(n - 1)];

GraphicsRow@Table[
Graphics[{
testing[spiral, VertexColors -> colors[n]]
}],
{testing, {Polygon, polygonColoredTris}}]


Update Whoops turns out this also only works under special conditions. Specifically you aren't guaranteed that the original edges are actually present in the triangulation, I got by because I was looking at cases where they did. So I'm back to the drawing board.

-

Here's a triangulation approach that might work easily and more generally. Let's start with on of your problematic examples:

drawing = draw[5,0.414]


Now, let's triangulate, after getting rid of 10^-17 type expressions.

GraphicsMeshMeshInit[];
pts = Chop[drawing[[1, 1, 1]]];
tri = PolygonTriangulate[pts]

(* Out: {{6, 4, 5}, {4, 2, 3}, {1, 9, 10}, {8, 2, 4}, {9, 2, 8},
{2, 9, 1}, {4, 7, 8}, {4, 6, 7}} *)


Finally, we'll assemble it into a GraphicsComplex.

colors = VertexColors /. drawing[[1, 1, 2]];
newcolors = colors[[#]] & /@ tri;
Graphics[GraphicsComplex[pts,
Polygon[tri, VertexColors -> newcolors]]]


We can see the triangulation using EdgeForm, which might be useful to understand the colorization.

 Graphics[GraphicsComplex[pts,
{EdgeForm[Black], Polygon[tri, VertexColors -> newcolors]}]]


Which explains why it doesn't work so well here with draw[100,0.414]:

On the other hand we could use the following triangulation of your draw[100,0.414] polygon (obtained from the triangle program as described in this answer):

We could then color the newly introduced vertices using linear interpolation between orange and purple. The result is:

Which is not too bad! I'd be glad to share more specific code, if you get the triangle` command working, as described in the globe answer.

-
@jVincent Just wondering if you had noticed the edits to this answer? –  Mark McClure Dec 12 '12 at 19:22
It would be nice to see some code pieces, you can always just reference your other answer with respect to interfacing triangle. –  jVincent Dec 13 '12 at 9:41
@jVincent Yes, it would be. I was working on a bunch of stuff yesterday and figured I'd only prioritize this if you had triangle working. I'll probably clean this up at some point in the next couple of days but don't have the time immediately. I am curious to try it on more complicated examples, anyway. –  Mark McClure Dec 13 '12 at 15:04