From 0804bb7e067e66d4b05a6c45f9736b1e20505b96 Mon Sep 17 00:00:00 2001 From: Michael Drake Date: Fri, 28 Sep 2012 11:19:34 +0100 Subject: Add error diffusion to palette based rendering. Only used for bitmap and scaled bitmap plots. Doesn't do serpentine path, since that would need changes to the common bitmap rendering code. --- include/palette.h | 130 +++++++++++++++++++++++++++++++++++++++++++++++++++--- src/palette.c | 32 +++++++++++++- src/plot/8bpp.c | 2 +- src/plot/common.c | 69 ++++++++++++++++++++--------- src/surface/sdl.c | 2 +- 5 files changed, 206 insertions(+), 29 deletions(-) diff --git a/include/palette.h b/include/palette.h index 845c1bc..f975ef2 100644 --- a/include/palette.h +++ b/include/palette.h @@ -27,21 +27,35 @@ struct nsfb_palette_s { enum nsfb_palette_type_e type; /**< Palette type */ uint8_t last; /**< Last used palette index */ nsfb_colour_t data[256]; /**< Palette for index modes */ + + bool dither; /**< Whether to use error diffusion */ + struct { + int width; /**< Length of error value buffer ring*/ + int current; /**< Current pos in ring buffer*/ + int *data; /**< Ring buffer error values */ + int data_len; /**< Max size of ring */ + } dither_ctx; }; + /** Create an empty palette object. */ -bool nsfb_palette_new(struct nsfb_palette_s **palette); +bool nsfb_palette_new(struct nsfb_palette_s **palette, int width); /** Free a palette object. */ void nsfb_palette_free(struct nsfb_palette_s *palette); +/** Init error diffusion for a plot. */ +void nsfb_palette_dither_init(struct nsfb_palette_s *palette, int width); + +/** Finalise error diffusion after a plot. */ +void nsfb_palette_dither_fini(struct nsfb_palette_s *palette); + /** Generate libnsfb 8bpp default palette. */ void nsfb_palette_generate_nsfb_8bpp(struct nsfb_palette_s *palette); - -static inline uint8_t nsfb_palette_best_match( - const struct nsfb_palette_s *palette, - nsfb_colour_t c) +/** Find best palette match for given colour. */ +static inline uint8_t nsfb_palette_best_match(struct nsfb_palette_s *palette, + nsfb_colour_t c, int *r_error, int *g_error, int *b_error) { uint8_t best_col = 0; @@ -68,6 +82,9 @@ static inline uint8_t nsfb_palette_best_match( best_col = col; best_distance = cur_distance; + *r_error = dr; + *g_error = dg; + *b_error = db; /* Index into grayscale part */ col = (( c & 0xFF) + @@ -82,6 +99,9 @@ static inline uint8_t nsfb_palette_best_match( if (cur_distance < best_distance) { best_distance = cur_distance; best_col = col; + *r_error = dr; + *g_error = dg; + *b_error = db; } break; @@ -97,6 +117,9 @@ static inline uint8_t nsfb_palette_best_match( if (cur_distance < best_distance) { best_distance = cur_distance; best_col = col; + *r_error = dr; + *g_error = dg; + *b_error = db; } } break; @@ -108,4 +131,101 @@ static inline uint8_t nsfb_palette_best_match( return best_col; } +/** Find best palette match for given colour, with error diffusion. */ +static inline uint8_t nsfb_palette_best_match_dither( + struct nsfb_palette_s *palette, nsfb_colour_t c) +{ + int r, g, b; + int current; + int error; + int width = palette->dither_ctx.width; + uint8_t best_col_index; + + if (palette == NULL) + return 0; + + if (palette->dither == false) + return nsfb_palette_best_match(palette, c, &r, &g, &b); + + current = palette->dither_ctx.current; + + /* Get RGB components of colour, and apply error */ + r = ( c & 0xFF) + palette->dither_ctx.data[current ]; + g = ((c >> 8) & 0xFF) + palette->dither_ctx.data[current + 1]; + b = ((c >> 16) & 0xFF) + palette->dither_ctx.data[current + 2]; + + /* Clamp new RGB components to range */ + if (r < 0) r = 0; + if (r > 255) r = 255; + if (g < 0) g = 0; + if (g > 255) g = 255; + if (b < 0) b = 0; + if (b > 255) b = 255; + + /* Reset error diffusion slots to 0 */ + palette->dither_ctx.data[current ] = 0; + palette->dither_ctx.data[current + 1] = 0; + palette->dither_ctx.data[current + 2] = 0; + + /* Rebuild colour from modified components */ + c = r + (g << 8) + (b << 16); + + /* Get best match for pixel, and find errors for each component */ + best_col_index = nsfb_palette_best_match(palette, c, &r, &g, &b); + + /* Advance one set of error diffusion slots */ + current += 3; + if (current >= width) + current = 0; + palette->dither_ctx.current = current; + + /* Save errors + * + * [*]-[N] + * / | \ + * [l]-[m]-[r] + */ + error = current; + + /* Error for [N] (next) */ + if (error != 0) { + /* The pixel exists */ + palette->dither_ctx.data[error ] += r * 7 / 16; + palette->dither_ctx.data[error + 1] += g * 7 / 16; + palette->dither_ctx.data[error + 2] += b * 7 / 16; + } + + error += width - 2 * 3; + if (error >= width) + error -= width; + /* Error for [l] (below, left) */ + if (error >= 0 && error != 3) { + /* The pixel exists */ + palette->dither_ctx.data[error ] += r * 3 / 16; + palette->dither_ctx.data[error + 1] += g * 3 / 16; + palette->dither_ctx.data[error + 2] += b * 3 / 16; + } + + error += 3; + if (error >= width) + error -= width; + /* Error for [m] (below, middle) */ + palette->dither_ctx.data[error ] += r * 5 / 16; + palette->dither_ctx.data[error + 1] += g * 5 / 16; + palette->dither_ctx.data[error + 2] += b * 5 / 16; + + error += 3; + if (error >= width) + error -= width; + /* Error for [r] (below, right) */ + if (error != 0) { + /* The pixel exists */ + palette->dither_ctx.data[error ] += r / 16; + palette->dither_ctx.data[error + 1] += g / 16; + palette->dither_ctx.data[error + 2] += b / 16; + } + + return best_col_index; +} + #endif /* PALETTE_H */ diff --git a/src/palette.c b/src/palette.c index eba95cd..d600001 100644 --- a/src/palette.c +++ b/src/palette.c @@ -13,12 +13,13 @@ #include #include #include +#include #include "palette.h" /** Create an empty palette object. */ -bool nsfb_palette_new(struct nsfb_palette_s **palette) +bool nsfb_palette_new(struct nsfb_palette_s **palette, int width) { *palette = malloc(sizeof(struct nsfb_palette_s)); if (*palette == NULL) { @@ -28,14 +29,41 @@ bool nsfb_palette_new(struct nsfb_palette_s **palette) (*palette)->type = NSFB_PALETTE_EMPTY; (*palette)->last = 0; + (*palette)->dither = false; + (*palette)->dither_ctx.data_len = width * 3; + (*palette)->dither_ctx.data = malloc(width * 3 * sizeof(int)); + if ((*palette)->dither_ctx.data == NULL) { + nsfb_palette_free(*palette); + return false; + } + return true; } /** Free a palette object. */ void nsfb_palette_free(struct nsfb_palette_s *palette) { - if (palette != NULL) + if (palette != NULL) { + if (palette->dither_ctx.data != NULL) { + free(palette->dither_ctx.data); + } free(palette); + } +} + +/** Init error diffusion for a plot. */ +void nsfb_palette_dither_init(struct nsfb_palette_s *palette, int width) +{ + palette->dither = true; + memset(palette->dither_ctx.data, 0, palette->dither_ctx.data_len); + palette->dither_ctx.width = width * 3; + palette->dither_ctx.current = 0; +} + +/** Finalise error diffusion after a plot. */ +void nsfb_palette_dither_fini(struct nsfb_palette_s *palette) +{ + palette->dither = false; } /** Generate libnsfb 8bpp default palette. */ diff --git a/src/plot/8bpp.c b/src/plot/8bpp.c index 05574d8..0245542 100644 --- a/src/plot/8bpp.c +++ b/src/plot/8bpp.c @@ -39,7 +39,7 @@ static uint8_t colour_to_pixel(nsfb_t *nsfb, nsfb_colour_t c) if (nsfb->palette == NULL) return 0; - return nsfb_palette_best_match(nsfb->palette, c); + return nsfb_palette_best_match_dither(nsfb->palette, c); } #define PLOT_TYPE uint8_t diff --git a/src/plot/common.c b/src/plot/common.c index 185e323..c9f9dc1 100644 --- a/src/plot/common.c +++ b/src/plot/common.c @@ -16,6 +16,8 @@ #error PLOT_LINELEN must be a macro to increment a line length #endif +#include "palette.h" + #define SIGN(x) ((x<0) ? -1 : ((x>0) ? 1 : 0)) static bool @@ -249,8 +251,7 @@ static bool bitmap_scaled(nsfb_t *nsfb, const nsfb_bbox_t *loc, nsfb_bbox_t clipped; /* clipped display */ /* The part of the scaled image actually displayed is cropped to the - * current context. - */ + * current context. */ clipped.x0 = x; clipped.y0 = y; clipped.x1 = x + width; @@ -271,6 +272,10 @@ static bool bitmap_scaled(nsfb_t *nsfb, const nsfb_bbox_t *loc, else rwidth = width; + if (nsfb->palette != NULL) { + nsfb_palette_dither_init(nsfb->palette, rwidth); + } + /* get veritcal (y) and horizontal (x) scale factors; both integer * part and remainder */ dx = bmp_width / width; @@ -299,7 +304,8 @@ static bool bitmap_scaled(nsfb_t *nsfb, const nsfb_bbox_t *loc, pvideo = get_xy_loc(nsfb, clipped.x0, clipped.y0); pvideo_limit = pvideo + PLOT_LINELEN(nsfb->linelen) * rheight; if (alpha) { - for (; pvideo < pvideo_limit; pvideo += PLOT_LINELEN(nsfb->linelen)) { + for (; pvideo < pvideo_limit; + pvideo += PLOT_LINELEN(nsfb->linelen)) { /* looping through render area vertically */ xoff = xoffs; rx = rxs; @@ -322,7 +328,8 @@ static bool bitmap_scaled(nsfb_t *nsfb, const nsfb_bbox_t *loc, xloop))); } /* plot pixel */ - *(pvideo + xloop) = colour_to_pixel(nsfb, abpixel); + *(pvideo + xloop) = colour_to_pixel( + nsfb, abpixel); } /* handle horizontal interpolation */ xoff += dx; @@ -341,7 +348,8 @@ static bool bitmap_scaled(nsfb_t *nsfb, const nsfb_bbox_t *loc, } } } else { - for (; pvideo < pvideo_limit; pvideo += PLOT_LINELEN(nsfb->linelen)) { + for (; pvideo < pvideo_limit; + pvideo += PLOT_LINELEN(nsfb->linelen)) { /* looping through render area vertically */ xoff = xoffs; rx = rxs; @@ -350,7 +358,8 @@ static bool bitmap_scaled(nsfb_t *nsfb, const nsfb_bbox_t *loc, /* get value of source pixel in question */ abpixel = pixel[yoff + xoff]; /* plot pixel */ - *(pvideo + xloop) = colour_to_pixel(nsfb, abpixel); + *(pvideo + xloop) = colour_to_pixel( + nsfb, abpixel); /* handle horizontal interpolation */ xoff += dx; @@ -369,6 +378,11 @@ static bool bitmap_scaled(nsfb_t *nsfb, const nsfb_bbox_t *loc, } } } + + if (nsfb->palette != NULL) { + nsfb_palette_dither_fini(nsfb->palette); + } + return true; } @@ -391,17 +405,16 @@ bitmap(nsfb_t *nsfb, int height = loc->y1 - loc->y0; nsfb_bbox_t clipped; /* clipped display */ - if (width == 0 || height == 0) - return true; + if (width == 0 || height == 0) + return true; /* Scaled bitmaps are handled by a separate function */ if (width != bmp_width || height != bmp_height) return bitmap_scaled(nsfb, loc, pixel, bmp_width, bmp_height, bmp_stride, alpha); - /* The part of the scaled image actually displayed is cropped to the - * current context. - */ + /* The part of the image actually displayed is cropped to the + * current context. */ clipped.x0 = x; clipped.y0 = y; clipped.x1 = x + width; @@ -416,6 +429,10 @@ bitmap(nsfb_t *nsfb, if (width > (clipped.x1 - clipped.x0)) width = (clipped.x1 - clipped.x0); + if (nsfb->palette != NULL) { + nsfb_palette_dither_init(nsfb->palette, width); + } + xoff = clipped.x0 - x; yoff = (clipped.y0 - y) * bmp_stride; height = height * bmp_stride + yoff; @@ -428,16 +445,22 @@ bitmap(nsfb_t *nsfb, for (xloop = 0; xloop < width; xloop++) { abpixel = pixel[yloop + xloop + xoff]; if ((abpixel & 0xFF000000) != 0) { - /* pixel is not transparent; have to - * plot something */ - if ((abpixel & 0xFF000000) != 0xFF000000) { - /* pixel is not opaque; need to - * blend */ - abpixel = nsfb_plot_ablend(abpixel, - pixel_to_colour(nsfb, *(pvideo + xloop))); + /* pixel is not transparent; have to + * plot something */ + if ((abpixel & 0xFF000000) != + 0xFF000000) { + /* pixel is not opaque; need to + * blend */ + abpixel = nsfb_plot_ablend( + abpixel, + pixel_to_colour( + nsfb, + *(pvideo + + xloop))); } - *(pvideo + xloop) = colour_to_pixel(nsfb, abpixel); + *(pvideo + xloop) = colour_to_pixel( + nsfb, abpixel); } } pvideo += PLOT_LINELEN(nsfb->linelen); @@ -446,11 +469,17 @@ bitmap(nsfb_t *nsfb, for (yloop = yoff; yloop < height; yloop += bmp_stride) { for (xloop = 0; xloop < width; xloop++) { abpixel = pixel[yloop + xloop + xoff]; - *(pvideo + xloop) = colour_to_pixel(nsfb, abpixel); + *(pvideo + xloop) = colour_to_pixel( + nsfb, abpixel); } pvideo += PLOT_LINELEN(nsfb->linelen); } } + + if (nsfb->palette != NULL) { + nsfb_palette_dither_fini(nsfb->palette); + } + return true; } diff --git a/src/surface/sdl.c b/src/surface/sdl.c index 7a86dc1..0554e26 100644 --- a/src/surface/sdl.c +++ b/src/surface/sdl.c @@ -458,7 +458,7 @@ static int sdl_initialise(nsfb_t *nsfb) nsfb->surface_priv = sdl_screen; if (nsfb->bpp == 8) { - nsfb_palette_new(&nsfb->palette); + nsfb_palette_new(&nsfb->palette, nsfb->width); set_palette(nsfb); } -- cgit v1.2.1