Polygon edge gradient algorithm

Question

I'm trying to create an application that uses an uncommon polygon gradient fill. The idea is that each edge of the polygon has a single colour, and these edge colours are used to fill the rest of the polygon's pixels in a smooth gradient.

I have a working program that performs this gradient by determining, for each pixel, how far it is from all the polygon's edges and doing a weighted average of all the edges' colours based on the distances to them. Here's a sample output:

Polygon edge gradient sample (click link to view)

The problem is that the algorithm is horribly slow when the polygon has a lot of edges, namely because for every single pixel, it has to calculate distances to every edge. Any ideas for how this could be sped up?

Current algorithm:

for pixel in polygon: # predetermined using a basic scan-line polygon-fill algorithm
    edge_distances = {}
    for edge in polygon:
        distance = calc_point_to_line_distance(pixel, edge) # simple formula, constant time            
        edge_distances[edge] = distance
    colour = calc_pixel_colour(edge_distances)  # runs in O(num_edges) time
    set_pixel_colour(pixel, colour)

I've left out the details because I'm looking for big picture ideas of how to do this better (i.e. better than O(num_pixels*num_edges)). All ideas welcome.

Thanks!

It's hard to optimize an algorithm we can't see. If you want help, you will have to share some code. — Bradley Uffner
Do you need to support concave polygons, or only convex ones? — Bradley Uffner

colinjstewart colinjstewart · Accepted Answer · 2017-10-30T03:23:14

Thanks to @SirRaffleBuffle for pointing me towards the answer (sorry, I don't have enough "reputation points" to upvote you).

What I went with in the end was a colour diffusion algorithm, combined with a multi-grid solver for massive performance gains (described mathematically here, here, and here; warning, lots of opaque math jargon and Greek letters).

The diffusion algorithm is fairly straightforward. You start with a canvas of pixels where some of them have specified colours (e.g. specified by you). Then, you start spreading the colours throughout the rest of the canvas by, for each pixel, averaging the four adjacent (non-diagonal) pixels. You then repeat this process over and over until all the pixels are filled and their colours stabilize.

This process is pretty slow in itself, but can be dramatically sped up with a "multi-grid solver." Here, you initially run the diffusion on a very small canvas (i.e. low resolution), then map the output colours to a second canvas with double the resolution, and run the diffusion on this canvas. This process can be repeated at higher and higher resolutions until you get what you want. The idea is to initialize the diffusion process with pixel colours that are close to the final output, thus cutting through most of the algorithm's work.

This is a pretty crude explanation; let me know if you want more detail.

Polygon edge gradient algorithm

2 Answers