Polygonal Gradients

Question

I am working on a project that uses the Juce library to display graphics. So far I have been using the library's API functions to generate linear and radial gradients, however that's the only two types of gradients that this library supports. I am now in need of generating a different type of gradient, one that follows the shape of a regular convex polygon. The key word here is REGULAR, meaning a polygon with all edges of the same length and with all vertices lying on a single circle.

For the case of a pentagon, here is a picture to better show the result I would like to get: http://www.filterforge.com/wiki/index.php/Polygonal_Gradient

For my application, I want to be able to specify a polygonal gradient with any number of edges. (pentagon, hexagon, octagon, etc...)

Given the limitations of the API, the only way I can produce the desired result is to fill a surface matrix pixel by pixel, mathematically calculating the values of the R, G, B, A components for each pixel.

Here is the code I have so far:

void render_surface(unsigned char *surface_data,
                    int width, int height, int linestride,
                    int num_vertices, t_rgba *color1, t_rgba *color2)
{
    const double center_x = 0.5 * width;
    const double center_y = 0.5 * height;
    const double radius = 0.5 * MIN(width, height);
    int x, y;

    for (y = height; --y >= 0;) {

        uint32_t *line = (uint32_t *)data;
        data += linestride;

        const double dy = y - center_y;

        for (x = width; --x >= 0;) {

            const double dx = x - center_x;

            double rho = hypot(dx, dy);
            rho /= radius;    // normalize radius 

            // constrain
            rho = CLIP(rho, 0.0, 1.0);

            // interpolate
            double a = color2->alpha + (color1->alpha - color2->alpha) * rho;
            double r = color2->red   + (color1->red   - color2->red  ) * rho;
            double g = color2->green + (color1->green - color2->green) * rho;
            double b = color2->blue  + (color1->blue  - color2->blue ) * rho;

            // premultiply alpha
            r *= a;
            g *= a;
            b *= a;

#if LITTLE_ENDIAN
            *line++ = ((unsigned int)((256.0 * (1.0 - DBL_EPSILON)) * a) << 24) // alpha
                    | ((unsigned int)((256.0 * (1.0 - DBL_EPSILON)) * r) << 16) // red
                    | ((unsigned int)((256.0 * (1.0 - DBL_EPSILON)) * g) <<  8) // green
                    |  (unsigned int)((256.0 * (1.0 - DBL_EPSILON)) * b);       // blue
#else
            *line++ = ((unsigned int)((256.0 * (1.0 - DBL_EPSILON)) * b) << 24) // blue
                    | ((unsigned int)((256.0 * (1.0 - DBL_EPSILON)) * g) << 16) // green
                    | ((unsigned int)((256.0 * (1.0 - DBL_EPSILON)) * r) <<  8) // red
                    |  (unsigned int)((256.0 * (1.0 - DBL_EPSILON)) * a);       // alpha
#endif
        }
    }
}

The above code produces a radial gradient, the same type of gradient I could produce using one API function. However it seems to be a good starting point to tackle the problem.

surface_data - is a matrix of 8 bit values representing the pixel intensities of the Red, Green, Blue and Alpha components.

num_vertices - is the number of vertices (equally spaced on a single circle) that we want our polygonal gradient to have.

color1 - starting color of the gradient.

color2 - ending color of the gradient.

I would like to know how I can fill a surface in the same fashion, creating a polygonal gradient as opposed to radial.

Thanks for any help.

• Luigi

Rethinking about this problem a little bit... if we consider the origin of our coordinate system the center of the polygon, it boils down to finding an equation such that for any input point in cartesian coordinates, the output is the distance from the closest side of the polygon.

My intuition tells me that there must be some kind of closed form solution because:

for a circle,

rho = sqrt(dx*dx + dy*dy);

gives us the radial distance from the center of the circle, which could be considered as a polygon with infinite sides.

For a square,

fmax(fabs(dx), fabs(dy));

gives us the Chebyshev distance from the closest side of the square, which could be considered as a polygon with 4 sides.

So, I am thinking that some kind of combination of the two formulas should give the intermediary cases, which would solve the initial problem.

Am I totally off thinking along these lines?

• Luigi

Answer 1

My intuition tells me that there must be some kind of closed form solution

There is...

Anaylsis

For this I've taken the formula for the distance from the center to the edge of a hexagon (here) and noticed it can be generalised to any polygon. In that particular formula, the constant sqrt(3) is used (which I'll now call z). This number is equivalent to twice the ratio of the distance between the polygon midpoint and the midpoint of one of its edges compared to the distance between the midpoint and one of its vertices (this distance is 1 in a unit length polygon).

So, this constant (which is sqrt(3) for hexagons) is given by:

This ratio, which I described before, is given by:

Notice the 2s cancel out, so the general function to derive this constant for any polygon is:

SIDES is the number polygon sides (e.g. 6 for hexagon)

Now we simply plug this constant into the formula for the ratio of a where a point lies on a given unit length polygon compared to where it would lie on a unit length circle:

Example

How this works out is show below for a hexagon (so SIDES=6 and z=sqrt(3)). We get d as 0.866 for a θ=30° and d as 0.897 for θ=45° (also equivalent to θ=15°).

Note that d is only defined properly for 0 <= θ <= segmentAngle (which is given by 2PI/SIDES in radians).

Implementation

Now we have all we need to code a solution.

The following function maps a 2D (pixel) coordinate to a number between 0 and 1; this number specifies at which point (the step) in the colour gradient each pixel occurs.

Ultimately, this is fairly similar to a radial gradient, where the euclidean distance between the pixel and circle midpoint is used to define the step of the pixel. With polygonal gradients however, we want to scale the euclidean distance between a pixel (x,y) and the midpoint of the polygon by d, such that colours are "pushed" towards the edges of the polygon (a.k.a chord of the circle).

When it comes to rendering, the only thing is multiplying d by a denominator so that the polygon renders at an appropriate scale.

Code

public void polygonGradient(colour[][] pixels, Gradient gradient, Vector2 midPoint, float angle, float zoom, int sides) {

    final double z = Math.tan(HALF_PI - (PI / sides)); // z, as derived in answer
    final double SEGMENT_ANGLE = (2 * PI) / sides; // max angle of polygon segment in radians

    angle %= SEGMENT_ANGLE; // mod angle to minimise difference between theta and SEGMENT_ANGLE in loop (less while calls)

    final double denominator = 1 / ((Math.max(pixels.height, pixels.width)) * zoom); // calc here once, not in loop

    double yDist; // y distance between midpoint and a given pixel
    double xDist; // x distance between midpoint and a given pixel

    for (int y = 0, x; y < pixels.height; ++y) {
        yDist = (midPoint.y - y) * (midPoint.y - y);
        
        for (x = 0; x < pixels.width; ++x) {
            xDist = (midPoint.x - x) * (midPoint.x - x);
            
            double theta = Math.atan2((midPoint.y - y), (midPoint.x - x));
            theta += (TWO_PI - angle); // TWO_PI - angle, so we rotate clockwise
            theta = Math.abs(theta); // abs() here to simplify while loop 

            // polygon is split into N segments; restrict theta to angle of one segment
            while (theta > SEGMENT_ANGLE) { // effectively modulo (faster than using % operator)
                theta -= SEGMENT_ANGLE;
            }

            final double pointDistance = Math.sqrt(yDist + xDist); // euclidean dist between (x,y) and midpoint

            double d = z * (z * Math.cos(theta) + Math.sin(theta)); // d, as derived in answer

            // now calculate the position of the pixel on the gradient
            double step = d  * denominator * pointDistance; // multiply euclidean distance by d

            if (step > 1) { // clamp to 1
                step = 1;
            }
            
            pixels[x][y] = gradient.colourAt(step); // get the colour of the gradient at the step given by dist
        }
    }
}

Output

Sides = 6

Sides = 9

Sides = 3; zoomed a bit; midpoint off centre

Sides = 5; non-linear colour interpolation

Answer 2

This is roughly how I'd approach it ...

• Place the center of the polygon at the origin 'O'.
• For a given point 'P' within a given segment of a regular polygon, let the line through 'O' & 'P' be 'Line1' and
• let the line through the outer edge of the containing polygon segment be 'Line2'
• Find the intesection point 'IP' of these 2 lines.

Now the color fraction at P is defined by the distance of P to the origin relative to the distance of IP to the origin.

Edit: I've implemented the algorithm above and this is the output ...

Edit2: Here's the (Delphi) code

const
  vertical: TFloat = 3.4e38;

function Slope(const pt1, pt2: TFloatPoint): single;
begin
  if (pt1.X = pt2.X) then result := vertical
  else result := (pt2.Y - pt1.Y)/(pt2.X - pt1.X);
end;
//---------------------------------------------------------------------------

procedure GetLine(const pt1, pt2: TFloatPoint; out m, b: TFloat);
begin
  m := Slope(pt1, pt2);
  if m = vertical then
    b := pt1.X else
    b := pt1.Y - m * pt1.X;
end;
//---------------------------------------------------------------------------

function GradientColor(const clr1, clr2: TColor32; fraction: TFloat): TColor32;
begin
  if fraction <= 0 then result := clr1
  else if fraction >= 1 then result := clr2
  else
  begin
    TColor32Entry(result).B :=
      trunc(TColor32Entry(clr2).B * fraction + TColor32Entry(clr1).B * (1-fraction));
    TColor32Entry(result).G :=
      trunc(TColor32Entry(clr2).G * fraction + TColor32Entry(clr1).G * (1-fraction));
    TColor32Entry(result).R :=
      trunc(TColor32Entry(clr2).R * fraction + TColor32Entry(clr1).R * (1-fraction));
    TColor32Entry(result).A :=
      trunc(TColor32Entry(clr2).A * fraction + TColor32Entry(clr1).A * (1-fraction));
  end;
end;
//---------------------------------------------------------------------------

function PointInTriangle(const pt, tr1, tr2, tr3: TFloatPoint): boolean;
begin
  result := false;
  if ((((tr1.Y <= pt.Y) and (pt.Y < tr3.Y)) or
    ((tr3.Y <= pt.Y) and (pt.Y < tr1.Y))) and
    (pt.X < (tr3.X - tr1.X) * (pt.Y - tr1.Y) /
    (tr3.Y - tr1.Y) + tr1.X)) then result := not result;
  if ((((tr2.Y <= pt.Y) and (pt.Y < tr1.Y)) or
    ((tr1.Y <= pt.Y) and (pt.Y < tr2.Y))) and
    (pt.X < (tr1.X - tr2.X) * (pt.Y - tr2.Y) /
    (tr1.Y - tr2.Y) + tr2.X)) then result := not result;
  if ((((tr3.Y <= pt.Y) and (pt.Y < tr2.Y)) or
    ((tr2.Y <= pt.Y) and (pt.Y < tr3.Y))) and
    (pt.X < (tr2.X - tr3.X) * (pt.Y - tr3.Y) /
    (tr2.Y - tr3.Y) + tr3.X)) then result := not result;
end;
//---------------------------------------------------------------------------

function GetSegmentIndex(vertex: TFloatPoint; vertices: TArrayOfFloatPoint): integer;
var
  i, highI: integer;
  prev: TFloatPoint;
const
  origin: TFloatPoint = (X: 0; Y: 0);
begin
  highI := high(vertices);
  prev := vertices[highI];
  result := -1;
  for i := 0 to highI do
  begin
    if PointInTriangle(vertex, origin, prev, vertices[i]) then
    begin
      result := i;
      break;
    end;
    prev := vertices[i];
  end;
end;
//---------------------------------------------------------------------------

procedure RegularPolygonFill(bmp: TBitmap32; const origin: TPoint;
  radius: TFloat; vertexCount: integer; InnerColor, OuterColor: TColor32);
var
  i,j,d,q: integer;
  dist1,dist2: TFloat;
  vert, intersetPt: TFloatPoint;
  verts: TArrayOfFloatPoint;
  edgeMs, edgeBs: TArrayOfFloat;
  angle, angleDiff, m, b: TFloat;
  sinAngle, cosAngle: extended;
const
  orig: TFloatPoint = (X: 0; Y: 0);
begin
  if vertexCount < 3 then exit;
  setlength(verts, vertexCount);
  setlength(edgeMs, vertexCount); //edge slopes  (ie y = M*x +b)
  setlength(edgeBs, vertexCount); //edge offsets (ie y = m*x +B)
  angleDiff := pi *2 / vertexCount;
  angle := angleDiff;
  vert.X := radius; //vert used here as prev vertex
  vert.Y := 0;
  for i := 0 to vertexCount -1 do
  begin
    SinCos(angle, sinAngle, cosAngle);
    verts[i].X := cosAngle * radius;
    verts[i].Y := sinAngle * radius;
    GetLine(vert, verts[i], edgeMs[i], edgeBs[i]);
    angle := angle + angleDiff;
    vert := verts[i];
  end;

  d := floor(radius);
  for i := -d to d do
    for j := -d to d do
    begin
      vert := FloatPoint(i,j);
      GetLine(orig, vert, m, b);
      q := GetSegmentIndex(vert, verts);
      if q < 0 then continue;
      //simultaneous equations to find intersection ...
      //y = m * x + b; y = edgeMs[q]* x + edgeBs[q];
      //edgeMs[q]* x + edgeBs[q] = m * x + b;
      //(edgeMs[q] - m) * x = b - edgeBs[q]
      //x = (b - edgeBs[q])/(edgeMs[q] - m)
      if m = vertical then
      begin
        intersetPt.X := b;
        intersetPt.Y := edgeMs[q]* intersetPt.X + edgeBs[q];
      end
      else if edgeMs[q] = vertical then
      begin
        intersetPt.X := edgeBs[q];
        intersetPt.Y := m* intersetPt.X + b;
      end else
      begin
        intersetPt.X := (b - edgeBs[q])/(edgeMs[q] - m);
        intersetPt.Y := m * intersetPt.X + b;
      end;

      //get distances from origin of vert and intersetPt ...
      dist1 := sqrt(vert.X*vert.X + vert.Y*vert.Y);
      dist2 := sqrt(intersetPt.X*intersetPt.X + intersetPt.Y*intersetPt.Y);

      bmp.Pixel[i + origin.X, j + origin.Y] :=
        GradientColor(InnerColor, OuterColor, dist1/dist2);
    end;
end;