Radial gradient

[kdschlosser]

Introduce the problem

I have been messing about with doing some testing to render radial gradients and I believe I may have come up with some code to handle this that isn't all too complicated.

The code written below is in Python. I ported the LVGL code to Python for faster testing purposes and it would be easy to port over to C.

It needs some work but the basic idea is there. This writes the data to a bmp file for viewing.

Proposal

Here is the code.

import math
import struct


# typedef struct {
#     uint8_t blue;
#     uint8_t green;
#     uint8_t red;
# } lv_color_t;
class lv_color_t:
    def __init__(self, red: int, green: int, blue: int):
        self.red = red
        self.green = green
        self.blue = blue

    def __str__(self):
        return f'lv_color_t(red={self.red}, green={self.green}, blue={self.blue})'


class lv_grad_color_t(lv_color_t):
    pass


# typedef struct {
#     lv_color_t color;   /**< The stop color */
#     lv_opa_t   opa;     /**< The opacity of the color*/
#     uint8_t    frac;    /**< The stop position in 1/255 unit */
# } lv_gradient_stop_t;
class lv_gradient_stop_t:
    def __init__(self, color: lv_color_t, opa: int, frac: int):
        self.color = color
        self.opa = opa
        self.frac = frac


# typedef struct _lv_gradient_cache_t {
#     lv_color_t   *  color_map;
#     lv_opa_t   *  opa_map;
#     uint32_t size;
# } lv_grad_t;
class lv_grad_t:
    def __init__(self):
        self.color_map: list[lv_color_t] = []
        self.opa_map: list[int] = []
        self.size: int = 0


# typedef struct {
#     lv_gradient_stop_t   stops[LV_GRADIENT_MAX_STOPS];
#     uint8_t              stops_count;
#     lv_grad_dir_t        dir : 3;
# } lv_grad_dsc_t;
class lv_grad_dsc_t:
    def __init__(self):
        self.stops: list[lv_gradient_stop_t] = []
        self.stops_count: int = 0
        self.dir: int = 0


def GRAD_CONV(t, x):
    t.red = x.red
    t.green = x.green
    t.blue = x.blue


def GRAD_CM(r, g, b):
    return lv_color_t(r, g, b)


def LV_UDIV255(x):
    return (x * 0x8081) >> 0x17


def lv_gradient_color_calculate(dsc: lv_grad_dsc_t, rnge: int, frac: int, color_out: lv_grad_color_t, opa_out: list[int]):
    # Clip out-of-bounds first
    mn = (dsc.stops[0].frac * rnge) >> 8

    if frac <= mn:
        GRAD_CONV(color_out, dsc.stops[0].color)
        opa_out.append(dsc.stops[0].opa)
        return

    mx = dsc.stops[dsc.stops_count - 1].frac / 255.0 * rnge
    print(mx, frac, rnge)

    if frac >= mx:
        GRAD_CONV(color_out, dsc.stops[dsc.stops_count - 1].color)
        opa_out.append(dsc.stops[dsc.stops_count - 1].opa)
        return

    # Find the 2 closest stop now
    found_i = 0
    for i in range(1, dsc.stops_count, 1):
        cur = (dsc.stops[i].frac * rnge) >> 8
        if frac <= cur:
            found_i = i
            break

    one = dsc.stops[found_i - 1].color
    two = dsc.stops[found_i].color
    mn = (dsc.stops[found_i - 1].frac * rnge) >> 8
    mx = (dsc.stops[found_i].frac * rnge) >> 8
    d = mx - mn

    # Then interpolate
    frac -= mn
    mix = int((frac * 255) / d)
    imix = 255 - mix

    GRAD_CONV(color_out, GRAD_CM(
        LV_UDIV255(two.red * mix + one.red * imix),
        LV_UDIV255(two.green * mix + one.green * imix),
        LV_UDIV255(two.blue * mix + one.blue * imix)
    ))

    opa_out.append(LV_UDIV255(dsc.stops[found_i].opa * mix + dsc.stops[found_i - 1].opa * imix))


def allocate_item(g: lv_grad_dsc_t, w: int, h: int) -> lv_grad_t:
    if g.dir == LV_GRAD_DIR_HOR:
        size = w
    else:
        size = h

    item = lv_grad_t()

    for _ in range(size):
        item.color_map.append(lv_color_t(0, 0, 0))
        item.opa_map.append(0)

    item.size = size
    return item


def lv_gradient_get(g: lv_grad_dsc_t, w: int, h: int) -> lv_grad_t:
    # No gradient, no cache
    if g.dir == LV_GRAD_DIR_NONE:
        return None

    # Step 1: Search cache for the given key
    item = allocate_item(g, w, h)

    # Step 3: Fill it with the gradient, as expected
    for i in range(item.size):
        opa = []
        lv_gradient_color_calculate(g, item.size, i, item.color_map[i], opa)
        item.opa_map[i] = opa[0]

    return item


LV_GRAD_DIR_NONE = 0
LV_GRAD_DIR_VER = 1
LV_GRAD_DIR_HOR = 2
LV_GRAD_DIR_RADIAL = 3
LV_GRAD_DIR_CONICAL = 4


def bmp_header(o_file, fsize):
    o_file.write(bytes("BM", "ascii"))
    o_file.write(struct.pack("<I", fsize))
    o_file.write(b"\00\x00")
    o_file.write(b"\00\x00")
    o_file.write(struct.pack("<I", 54))


def bytes_per_row_with_pad(source_width):
    pixel_bytes = 3 * source_width
    padding_bytes = (4 - (pixel_bytes % 4)) % 4
    return pixel_bytes + padding_bytes


def dib_header(o_file, w, h):
    o_file.write(struct.pack("<I", 40))
    o_file.write(struct.pack("<I", w))
    o_file.write(struct.pack("<I", h))
    o_file.write(struct.pack("<H", 1))
    o_file.write(struct.pack("<H", 24))
    for _ in range(24):
        o_file.write(b"\x00")


def lv_radial_gradient(radius, dsc: lv_grad_dsc_t, o_file, background_color: lv_color_t = lv_color_t(0, 0, 0)):
    img_size_width = radius * 2
    img_size_height = radius * 2

    dsc.dir = LV_GRAD_DIR_HOR
    grad = lv_gradient_get(dsc, radius, 1)

    for c in grad.color_map:
        print(c)

    res = bytearray(img_size_height * bytes_per_row_with_pad(img_size_width))
    row_buffer = bytearray(bytes_per_row_with_pad(img_size_width))

    print(grad.size)

    for y in range(img_size_height, 0, -1):
        buffer_index = 0
        for x in range(img_size_width):
            dist = int(abs(math.sqrt((radius - x) ** 2 + (radius - y) ** 2)))

            if dist >= grad.size:
                color_rgb = background_color
            else:
                color_rgb = grad.color_map[~dist]

            row_buffer[buffer_index] = color_rgb.blue & 0xFF
            buffer_index += 1
            row_buffer[buffer_index] = color_rgb.green & 0xFF
            buffer_index += 1
            row_buffer[buffer_index] = color_rgb.red & 0xFF
            buffer_index += 1

        o_file.write(row_buffer)

        res.extend(row_buffer)

    return res


grad_dsc = lv_grad_dsc_t()
grad_dsc.stops.append(lv_gradient_stop_t(lv_color_t(255, 0, 0), 255, 10))
grad_dsc.stops.append(lv_gradient_stop_t(lv_color_t(0, 0, 0), 255, 100))
grad_dsc.stops_count = 2


print("saving starts")
output_file = open(r'radial.bmp', "wb")
filesize = 54 + 400 * bytes_per_row_with_pad(400)
bmp_header(output_file, filesize)
dib_header(output_file, 400, 400)

lv_radial_gradient(200, grad_dsc, output_file)
output_file.close()
print("saving done")

and the output looks like this.

[kdschlosser]

The cool thing is this same mechanism can also handle conical gradients as well with the addition of a little bit more code. It can also combine a conical gradient and a radial gradient together to produce this

[kdschlosser]

code execution time for the red gradient in the original post averages out to about 143 milliseconds in python which in C code should be close to 0.17 milliseconds. This is of course on a PC so the code execution time would be slower on an MCU. not sure exactly how much but even if it took 50 milliseconds it wouldn't be that bad. That is for rendering a 400 x 400 image.

[kisvegabor]

Cool!

dist = int(abs(math.sqrt((radius - x) ** 2 + (radius - y) ** 2)))

Only this sqrt worries me. We can save 7/8 of the calculations by mirroring the circle octals. Can we cache or fake the remaining 1/8 sqrts?

[kdschlosser]

Yes it can be mirrored ad you have said and that would without a doubt save some time in rendering, BUT.... you would loose the ability to handle conical gradients. This is made with a modification of the code I posted.

This is the joining of a conical gradient and a radial gradient.

[kdschlosser]

The first "color wheel" image I posted was something that I copied from the web. The second one seen above is rendered using a variation of the code I originally posted. Notice how the second one looks better? It doesn't have any moire`

[kdschlosser]

what is nice is that both the radial and the conical gradients use the existing gradient generator that exists in LVGL. If I could only figure out hot the frac thing works because it behaves oddly when rendering.

If I set the frack to zero for say red and the frack to255 for black there should be a really nice transition from red to black across the provided length/width that is given. Unfortunately it doesn't do this.

Ideally the gradient generation code in LVGL would need to be pulled apart so the portion of the code that generates the gradient would only require a length parameter and not have to deal with the orientation aspects. that should be taken care of in a different function. The other thing is the enumerations for specifying which gradient to be use should be able to be or'ed together so a user could combine a horizontal gradient and a vertical or combine a radial and a conical.

This is where you guys would come in, that is above my knowledge on how to make that kind of thing possible. I am also unsure of how to get the data to write to a pixel buffer correctly instead of outputting in a bitmap format.

[kdschlosser]

@kisvegabor

I have another pretty kick ass one for ya. you are going to love this one I think. This is a dithering algorithm but isn't crazy math intensive so it's fast.

from PIL import Image

# typedef struct {
#     uint8_t blue;
#     uint8_t green;
#     uint8_t red;
# } lv_color_t;
class lv_color_t:
    def __init__(self, red: int, green: int, blue: int):
        self.red = red
        self.green = green
        self.blue = blue

    def __str__(self):
        return f'lv_color_t(red={self.red}, green={self.green}, blue={self.blue})'


red_thresh = [
  1, 7, 3, 5, 0, 8, 2, 6,
  7, 1, 5, 3, 8, 0, 6, 2,
  3, 5, 0, 8, 2, 6, 1, 7,
  5, 3, 8, 0, 6, 2, 7, 1,
  0, 8, 2, 6, 1, 7, 3, 5,
  8, 0, 6, 2, 7, 1, 5, 3,
  2, 6, 1, 7, 3, 5, 0, 8,
  6, 2, 7, 1, 5, 3, 8, 0
]

green_thresh = [
  1, 3, 2, 2, 3, 1, 2, 2,
  2, 2, 0, 4, 2, 2, 4, 0,
  3, 1, 2, 2, 1, 3, 2, 2,
  2, 2, 4, 0, 2, 2, 0, 4,
  1, 3, 2, 2, 3, 1, 2, 2,
  2, 2, 0, 4, 2, 2, 4, 0,
  3, 1, 2, 2, 1, 3, 2, 2,
  2, 2, 4, 0, 2, 2, 0, 4
]

blue_thresh = [
  5, 3, 8, 0, 6, 2, 7, 1,
  3, 5, 0, 8, 2, 6, 1, 7,
  8, 0, 6, 2, 7, 1, 5, 3,
  0, 8, 2, 6, 1, 7, 3, 5,
  6, 2, 7, 1, 5, 3, 8, 0,
  2, 6, 1, 7, 3, 5, 0, 8,
  7, 1, 5, 3, 8, 0, 6, 2,
  1, 7, 3, 5, 0, 8, 2, 6
]


# Get 16bit closest color
def closest_rb(c):
    return c >> 3 << 3


def closest_g(c):
    return c >> 2 << 2


def dither(x, y, col):
    tresshold_id = ((y & 7) << 3) + (x & 7)

    return lv_color_t(
        closest_rb(min(col.red + red_thresh[tresshold_id], 0xff)) & 0b11111000,
        closest_g(min(col.green + green_thresh[tresshold_id], 0xff)) & 0b11111100,
        closest_rb(min(col.blue + blue_thresh[tresshold_id], 0xff)) & 0b11111000
    )


import os

base_path = os.path.dirname(__file__)
img_path = os.path.join(base_path, 'test.png')

src_img = Image.open(img_path).convert('RGB')


width, height = src_img.size

dst_img = Image.new('RGB', src_img.size, (0, 0, 0))

color_1_set = set()
color_2_set = set()

for y in range(height):
    for x in range(width):
        r, g, b = src_img.getpixel((x, y))
        c = dither(x, y, lv_color_t(r, g, b))
        color_1_set.add((r, g, b))
        color_2_set.add((c.red, c.green, c.blue))
        dst_img.putpixel((x, y), (c.red, c.green, c.blue))

src_img.show()
dst_img.show()

print(len(color_1_set))
print(len(color_2_set))

You would need to supply your own image file to test with. put the image file in the same directory as the file you put this code and name the image "test.png". so make sure the image is a png file...

Then run the code and it will open the source file and the dithered one in the same file

Here is an example of an RGB888 converted to RGB565 and dithered

RGB888

RGB565 dithered

the RGB888 has a total of 115316 colors and the dithered RGB565 has a total of 10620 colors.

Here is the test using a gradient.

RGB888 (3595 colors)

RGB565 (1662 colors)

RGB565 dithered (1825 colors)

pretty good don't ya think? mostly super fast bit operations, there is only one addition and that is still fast. no floats or division nothing complicated. The lookup tables are small in size too. 3 uint8_t arrays that use only 192 bytes of memory. possibly something that would be worth adding especially with gradients. Those usually look choppy when converted from RGB888 to RGB565. maybe have it set up so it will get used when the RGB565 color mode gets set. maybe the arrays could be created dynamically or using macros to put them on the stack so they aren't resident all the time. They aren't that large to begin with. I am not a math super freak but there is a pattern to them that might be able to be used to make them smaller and use a math equation to get the value that is needed.

[kdschlosser]

Here is another.

RGB888

RGB565

RGB565 dithered

[kisvegabor]

1/8 circle
Optimizing for speed is important, so we can

• have 1/8 circles mirrored for radial gradient
• mirror at least the result of sqrt in case of conic gradient.

So even if it's a code duplication I think these can be handled separately for better optimization.

Dithering
Very impressive! Is based on some standard algorithms?

@XuNeo Typically RGB565(A8) dithering is not supported in image editors so wonder if we can add it to the image converter.

[XuNeo]

Thanks for the share, nice work!

@XuNeo Typically RGB565(A8) dithering is not supported in image editors so wonder if we can add it to the image converter.

@W-Mai has developed a whole new image converter from scratch using rust. It supports dither.
https://github.com/W-Mai/icu

We can also see how it can be integerated to the python tool. It should be straightforward.

[kdschlosser]

I know the code examples I provided are written in Python. They should be able to be converted into C code pretty easily.

The dithering example is based on the code found

https://github.com/amarullz/AROMA-Installer/blob/master/src/libs/aroma_graph.c

To my knowledge it is not any known way of dithering. It works really well tho and it's pretty fast at doing it too. Small memory footprint as well.

[kdschlosser]

The dither is something that is able to be used at runtime specifically for things like gradients and PNG files when using an RGB565 display. PNG format doesn't support 16 bit color and a user would need to save the image to a file format that supports 16 bit color and then load it and dither the image and then save it as a PNG file. That would only work for PNG files and image formats that do not support 16 bit color. With gradients they are generated at runtime and this would correct a gradient when being displayed on an RGB565 display. I think that it would be an important thing to use. Especially if radial and conical gradients get added.

[kdschlosser]

Here is code for a conical gradient. The gradients made are using a bezier function and a polylinear function

import math
from PIL import Image


TWO_PI = 6.28318530717958647693
INV_TWO_PI = 1.0 / TWO_PI


def linear_gradient(s, f=(255, 255, 255), n=10):
    RGB_list = [s]

    for t in range(1, n):
        curr_vector = [
            int(s[j] + (float(t) / (n - 1)) * (f[j] - s[j]))
            for j in range(3)
        ]
        RGB_list.append(tuple(curr_vector))

    return RGB_list


def polylinear_gradient(colors, n):
    n_out = int(float(n) / (len(colors) - 1))

    gradient_list = linear_gradient(colors[0], colors[1], n_out)

    for col in range(1, len(colors) - 1):
        nxt = linear_gradient(colors[col], colors[col + 1], n_out)
        gradient_list.extend(nxt[1:])

    return gradient_list


fact_cache = {}


def fact(n):
    try:
        return fact_cache[n]
    except KeyError:
        if n == 1 or n == 0:
            result = 1
        else:
            result = n * fact(n - 1)
        fact_cache[n] = result

        return result


def bernstein(t, n, i):
    binom = fact(n) / float(fact(i) * fact(n - i))
    return binom * ((1 - t) ** (n - i)) * (t ** i)


def bezier_gradient(colors, n_out=100):
    RGB_list = colors
    n = len(RGB_list) - 1

    def bezier_interp(t):
        summands = [
            list(map(lambda x: int(bernstein(t, n, i) * x), c))
            for i, c in enumerate(RGB_list)
        ]
        out = [0, 0, 0]
        for vector in summands:
            for c in range(3):
                out[c] += vector[c]

        return tuple(out)

    gradient = [
        bezier_interp(float(t) / (n_out-1))
        for t in range(n_out)
    ]
    return gradient


def floormod(x, y):
    x %= y
    if x < 0:
        x += y

    return x


def conicGradient(gradient, radius, angle, swirl=False):
    diameter = int(radius * 2)
    gradient_len = len(gradient)
    img_size = diameter * diameter

    pixels = [None] * (diameter * diameter)

    for y in range(diameter):
        rise = radius - y
        run = radius
        
        for x in range(diameter):
            t = math.atan2(rise, run) + math.pi - angle
            if swirl:
                t += TWO_PI * math.sqrt((rise * rise + run * run) / (img_size + img_size))
            t = floormod(t, TWO_PI)
            t *= INV_TWO_PI

            step = int(t * gradient_len)
            pixels[diameter * y + x] = gradient[step]
            run -= 1

    return pixels


grad_colors = polylinear_gradient(((255, 0, 0), (255, 255, 0), (0, 255, 0), (0, 255, 255), (0, 0, 255), (255, 0, 255), (255, 0, 0)), 500)

img = Image.new('RGB', (200, 200))
colors = conicGradient(grad_colors, 100, 245)
for y in range(200):
    for x in range(200):
        color = colors[200 * y + x]
        img.putpixel((x, y), color)

img.show()

colors = conicGradient(grad_colors, 100, 245, True)
for y in range(200):
    for x in range(200):
        color = colors[200 * y + x]
        img.putpixel((x, y), color)

img.show()


grad_colors = bezier_gradient(((255, 0, 0), (255, 255, 0), (0, 255, 0), (0, 255, 255), (0, 0, 255), (255, 0, 255), (255, 0, 0)), 500)

colors = conicGradient(grad_colors, 100, 245)
for y in range(200):
    for x in range(200):
        color = colors[200 * y + x]
        img.putpixel((x, y), color)

img.show()

colors = conicGradient(grad_colors, 100, 245, True)
for y in range(200):
    for x in range(200):
        color = colors[200 * y + x]
        img.putpixel((x, y), color)

img.show()

And this is the output
polylinear

bezier

And there they are with a literal twist
polylinear

bezier

[kdschlosser]

Here is the code with an adjustable "twist"/"swirl" value.

import math
from PIL import Image


TWO_PI = 6.28318530717958647693
INV_TWO_PI = 1.0 / TWO_PI


def linear_gradient(s, f=(255, 255, 255), n=10):
    RGB_list = [s]

    for t in range(1, n):
        curr_vector = [
            int(s[j] + (float(t) / (n - 1)) * (f[j] - s[j]))
            for j in range(3)
        ]
        RGB_list.append(tuple(curr_vector))

    return RGB_list


def polylinear_gradient(colors, n):
    n_out = int(float(n) / (len(colors) - 1))

    gradient_list = linear_gradient(colors[0], colors[1], n_out)

    for col in range(1, len(colors) - 1):
        nxt = linear_gradient(colors[col], colors[col + 1], n_out)
        gradient_list.extend(nxt[1:])

    return gradient_list


fact_cache = {}


def fact(n):
    try:
        return fact_cache[n]
    except KeyError:
        if n == 1 or n == 0:
            result = 1
        else:
            result = n * fact(n - 1)
        fact_cache[n] = result

        return result


def bernstein(t, n, i):
    binom = fact(n) / float(fact(i) * fact(n - i))
    return binom * ((1 - t) ** (n - i)) * (t ** i)


def bezier_gradient(colors, n_out=100):
    RGB_list = colors
    n = len(RGB_list) - 1

    def bezier_interp(t):
        summands = [
            list(map(lambda x: int(bernstein(t, n, i) * x), c))
            for i, c in enumerate(RGB_list)
        ]
        out = [0, 0, 0]
        for vector in summands:
            for c in range(3):
                out[c] += vector[c]

        return tuple(out)

    gradient = [
        bezier_interp(float(t) / (n_out-1))
        for t in range(n_out)
    ]
    return gradient


def floormod(x, y):
    x %= y
    if x < 0:
        x += y

    return x


def conicGradient(gradient, radius, angle, swirl=None):
    diameter = int(radius * 2)
    gradient_len = len(gradient)

    pixels = [None] * (diameter * diameter)

    if swirl is not None:
        swirl = int((diameter ** 4) / (255 * swirl))

    print(swirl)

    for y in range(diameter):
        rise = radius - y
        run = radius
        
        for x in range(diameter):
            t = math.atan2(rise, run) + math.pi - angle
            if swirl is not None:
                t += TWO_PI * math.sqrt((rise * rise + run * run) / swirl)
            t = floormod(t, TWO_PI)
            t *= INV_TWO_PI

            step = int(t * gradient_len)
            pixels[diameter * y + x] = gradient[step]
            run -= 1

    return pixels


grad_colors = polylinear_gradient(((255, 0, 0), (255, 255, 0), (0, 255, 0), (0, 255, 255), (0, 0, 255), (255, 0, 255), (255, 0, 0)), 500)

img = Image.new('RGB', (200, 200))
colors = conicGradient(grad_colors, 100, 245)
for y in range(200):
    for x in range(200):
        color = colors[200 * y + x]
        img.putpixel((x, y), color)

img.show()

colors = conicGradient(grad_colors, 100, 245, 1000)
for y in range(200):
    for x in range(200):
        color = colors[200 * y + x]
        img.putpixel((x, y), color)

img.show()


grad_colors = bezier_gradient(((255, 0, 0), (255, 255, 0), (0, 255, 0), (0, 255, 255), (0, 0, 255), (255, 0, 255), (255, 0, 0)), 500)

colors = conicGradient(grad_colors, 100, 245)
for y in range(200):
    for x in range(200):
        color = colors[200 * y + x]
        img.putpixel((x, y), color)

img.show()

colors = conicGradient(grad_colors, 100, 245, 1000)
for y in range(200):
    for x in range(200):
        color = colors[200 * y + x]
        img.putpixel((x, y), color)

img.show()

[kdschlosser]

I have written an extension that adds the different gradients and also the dithering. I have not tested it beyond compiling. If someone wants to give it a go and see how the performance is I have attached a zip file for it.

lvgl_addons.zip

@kisvegabor

[kisvegabor]

@kdschlosser Could you create a Pull request from zip? This way anyone can see and comment on it.

[kdschlosser]

Yeah I can do that. I know it can be improved upon. What I did was only for the purpose of rendering to a raw pixel buffer that can be loaded using lv_image.

[planevina]

I want this!

[lvgl-bot]

We need some feedback on this issue.

Now we mark this as "stale" because there was no activity here for 14 days.

Remove the "stale" label or comment else this will be closed in 7 days.

[kdschlosser]

not stale

[kisvegabor]

Let's continue in #6013.