From 60ac88e1ae2150b7ab5836fa882141324a642a4b Mon Sep 17 00:00:00 2001 From: Cyril Hrubis Date: Thu, 11 Jan 2018 18:44:03 +0100 Subject: [PATCH] gfx: Fix line drawing + symmetry tests The Bresenham's line does not draw symetric line by default, if you want line that is symmetrical when mirrored horizontally or vertically or when rotated by multiples of 90 degrees you have to draw only half of the line and draw second half symetrically to the line center. Signed-off-by: Cyril Hrubis --- libs/gfx/GP_Line.gen.c.t | 100 +++++++++++------- tests/gfx/.gitignore | 1 + tests/gfx/Line.c | 223 +++++++++++++++++++++++++++++++++++++++- tests/gfx/Makefile | 5 +- tests/gfx/gfx_benchmark.c | 4 +- tests/gfx/line_symmetry.gen.c.t | 173 +++++++++++++++++++++++++++++++ tests/gfx/test_list.txt | 1 + 7 files changed, 460 insertions(+), 47 deletions(-) create mode 100644 tests/gfx/line_symmetry.gen.c.t diff --git a/libs/gfx/GP_Line.gen.c.t b/libs/gfx/GP_Line.gen.c.t index 6e41be9f..bbccb583 100644 --- a/libs/gfx/GP_Line.gen.c.t +++ b/libs/gfx/GP_Line.gen.c.t @@ -4,7 +4,7 @@ * * Copyright (C) 2009-2012 Jiri "BlueBear" Dluhos * - * Copyright (C) 2009-2014 Cyril Hrubis + * Copyright (C) 2009-2018 Cyril Hrubis */ #include "core/GP_Common.h" @@ -23,6 +23,60 @@ */ @ for ps in pixelsizes: +static void line_dy_{{ ps.suffix }}(gp_pixmap *pixmap, int x0, int y0, int x1, int y1, gp_pixel pixval) +{ + if (y0 > y1) { + GP_SWAP(y0, y1); + GP_SWAP(x0, x1); + } + + int deltay = y1 - y0; + int deltax = GP_ABS(x1 - x0); + + int error = deltay / 2; + + int x = 0, y; + int xstep = (x0 < x1) ? 1 : -1; + + for (y = 0; y <= deltay/2; y++) { + gp_putpixel_raw_{{ ps.suffix }}(pixmap, x0+x, y0+y, pixval); + gp_putpixel_raw_{{ ps.suffix }}(pixmap, x1-x, y1-y, pixval); + + error -= deltax; + if (error < 0) { + x += xstep; + error += deltay; + } + } +} + +static void line_dx_{{ ps.suffix }}(gp_pixmap *pixmap, int x0, int y0, int x1, int y1, gp_pixel pixval) +{ + if (x0 > x1) { + GP_SWAP(x0, x1); + GP_SWAP(y0, y1); + } + + int deltax = x1 - x0; + int deltay = GP_ABS(y1 - y0); + + int error = deltax/2; + + int y = 0, x; + int ystep = (y0 < y1) ? 1 : -1; + + for (x = 0; x <= deltax/2; x++) { + gp_putpixel_raw_{{ ps.suffix }}(pixmap, x0+x, y0+y, pixval); + gp_putpixel_raw_{{ ps.suffix }}(pixmap, x1-x, y1-y, pixval); + + error -= deltay; + if (error < 0) { + y += ystep; + error += deltax; + } + } +} + void gp_line_raw_{{ ps.suffix }}(gp_pixmap *pixmap, int x0, int y0, int x1, int y1, gp_pixel pixval) { @@ -41,7 +95,7 @@ void gp_line_raw_{{ ps.suffix }}(gp_pixmap *pixmap, int x0, int y0, x0, y0, pixval); return; } - gp_vline_raw(pixmap, x0, y0, y1, pixval); + gp_vline_raw_{{ ps.suffix }}(pixmap, x0, y0, y1, pixval); return; } if (y0 == y1) { @@ -53,44 +107,10 @@ void gp_line_raw_{{ ps.suffix }}(gp_pixmap *pixmap, int x0, int y0, * Which axis is longer? Swap the coordinates if necessary so * that the X axis is always the longer one and Y is shorter. */ - int steep = abs(y1 - y0) / abs(x1 - x0); - if (steep) { - GP_SWAP(x0, y0); - GP_SWAP(x1, y1); - } - if (x0 > x1) { - GP_SWAP(x0, x1); - GP_SWAP(y0, y1); - } - - /* iterate over the longer axis, calculate values on the shorter */ - int deltax = x1 - x0; - int deltay = abs(y1 - y0); - - /* - * start with error of 0.5 (multiplied by deltax for integer-only math), - * this reflects the fact that ideally, the coordinate should be - * in the middle of the pixel - */ - int error = deltax / 2; - - int y = y0, x; - int ystep = (y0 < y1) ? 1 : -1; - for (x = x0; x <= x1; x++) { - - if (steep) - gp_putpixel_raw_{{ ps.suffix }}(pixmap, y, x, - pixval); - else - gp_putpixel_raw_{{ ps.suffix }}(pixmap, x, y, - pixval); - - error -= deltay; - if (error < 0) { - y += ystep; /* next step on the shorter axis */ - error += deltax; - } - } + if ((y1 - y0) / (x1 - x0)) + line_dy_{{ ps.suffix }}(pixmap, x0, y0, x1, y1, pixval); + else + line_dx_{{ ps.suffix }}(pixmap, x0, y0, x1, y1, pixval); } @ end diff --git a/tests/gfx/.gitignore b/tests/gfx/.gitignore index 92632603..191fe86f 100644 --- a/tests/gfx/.gitignore +++ b/tests/gfx/.gitignore @@ -13,3 +13,4 @@ /PutPixelAA /VLine /gfx_benchmark +line_symmetry.gen diff --git a/tests/gfx/Line.c b/tests/gfx/Line.c index 1e1b2d47..1b89e843 100644 --- a/tests/gfx/Line.c +++ b/tests/gfx/Line.c @@ -153,7 +153,7 @@ static struct testcase testcase_line_45 = { static struct testcase testcase_line_15 = { .x0 = 0, .y0 = 1, - .x1 = 11, + .x1 = 10, .y1 = 6, .w = 11, @@ -163,11 +163,11 @@ static struct testcase testcase_line_15 = { 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 1, 1, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 1, 1, 0, 0, 0, 0, 0, 0, 0, - 0, 0, 0, 0, 1, 1, 1, 0, 0, 0, 0, + 0, 0, 0, 0, 1, 1, 0, 0, 0, 0, 0, + 0, 0, 0, 0, 0, 1, 1, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 1, 1, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 1, 1, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, - 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, } }; @@ -205,6 +205,183 @@ static struct testcase testcase_line_large_xy = { } }; +static struct testcase line_nearly_vertical = { + .x0 = 0, + .y0 = 0, + .x1 = 1, + .y1 = 9, + + .w = 2, + .h = 10, + + .pixmap = { + 1, 0, + 1, 0, + 1, 0, + 1, 0, + 1, 0, + 0, 1, + 0, 1, + 0, 1, + 0, 1, + 0, 1, + } +}; + +static struct testcase line_nearly_horizontal = { + .x0 = 0, + .y0 = 0, + .x1 = 9, + .y1 = 1, + + .w = 10, + .h = 2, + + .pixmap = { + 1, 1, 1, 1, 1, 0, 0, 0, 0, 0, + 0, 0, 0, 0, 0, 1, 1, 1, 1, 1, + } +}; + +static struct testcase line_0_0_1_2 = { + .x0 = 0, + .y0 = 0, + .x1 = 1, + .y1 = 2, + + .w = 2, + .h = 3, + + .pixmap = { + 1, 0, + 1, 1, + 0, 1, + } +}; + +static struct testcase line_0_0_1_4 = { + .x0 = 0, + .y0 = 0, + .x1 = 1, + .y1 = 4, + + .w = 2, + .h = 5, + + .pixmap = { + 1, 0, + 1, 0, + 1, 1, + 0, 1, + 0, 1, + } +}; + +static struct testcase line_0_0_2_1 = { + .x0 = 0, + .y0 = 0, + .x1 = 2, + .y1 = 1, + + .w = 3, + .h = 2, + + .pixmap = { + 1, 1, 0, + 0, 1, 1, + } +}; + +static struct testcase line_0_0_4_1 = { + .x0 = 0, + .y0 = 0, + .x1 = 4, + .y1 = 1, + + .w = 5, + .h = 2, + + .pixmap = { + 1, 1, 1, 0, 0, + 0, 0, 1, 1, 1, + } +}; + +static struct testcase line_0_0_2_4 = { + .x0 = 0, + .y0 = 0, + .x1 = 2, + .y1 = 4, + + .w = 3, + .h = 5, + + .pixmap = { + 1, 0, 0, + 1, 0, 0, + 0, 1, 0, + 0, 0, 1, + 0, 0, 1, + } +}; + +static struct testcase line_0_0_4_2 = { + .x0 = 0, + .y0 = 0, + .x1 = 4, + .y1 = 2, + + .w = 5, + .h = 3, + + .pixmap = { + 1, 1, 0, 0, 0, + 0, 0, 1, 0, 0, + 0, 0, 0, 1, 1, + } +}; + +static struct testcase line_0_0_8_4 = { + .x0 = 0, + .y0 = 0, + .x1 = 8, + .y1 = 4, + + .w = 9, + .h = 5, + + .pixmap = { + 1, 1, 0, 0, 0, 0, 0, 0, 0, + 0, 0, 1, 1, 0, 0, 0, 0, 0, + 0, 0, 0, 0, 1, 0, 0, 0, 0, + 0, 0, 0, 0, 0, 1, 1, 0, 0, + 0, 0, 0, 0, 0, 0, 0, 1, 1, + } +}; + +static struct testcase line_0_0_4_8 = { + .x0 = 0, + .y0 = 0, + .x1 = 4, + .y1 = 8, + + .w = 5, + .h = 9, + + .pixmap = { + 1, 0, 0, 0, 0, + 1, 0, 0, 0, 0, + 0, 1, 0, 0, 0, + 0, 1, 0, 0, 0, + 0, 0, 1, 0, 0, + 0, 0, 0, 1, 0, + 0, 0, 0, 1, 0, + 0, 0, 0, 0, 1, + 0, 0, 0, 0, 1, + } +}; + + const struct tst_suite tst_suite = { .suite_name = "Line Testsuite", .tests = { @@ -228,6 +405,46 @@ const struct tst_suite tst_suite = { .tst_fn = test_line, .data = &testcase_line_15}, + {.name = "Line nearly vertical", + .tst_fn = test_line, + .data = &line_nearly_vertical}, + + {.name = "Line nearly horizontal", + .tst_fn = test_line, + .data = &line_nearly_horizontal}, + + {.name = "Line 0, 0, 1, 2", + .tst_fn = test_line, + .data = &line_0_0_1_2}, + + {.name = "line 0, 0, 1, 4", + .tst_fn = test_line, + .data = &line_0_0_1_4}, + + {.name = "Line 0, 0, 2, 1", + .tst_fn = test_line, + .data = &line_0_0_2_1}, + + {.name = "line 0, 0, 4, 1", + .tst_fn = test_line, + .data = &line_0_0_4_1}, + + {.name = "line 0, 0, 2, 4", + .tst_fn = test_line, + .data = &line_0_0_2_4}, + + {.name = "line 0, 0, 4, 2", + .tst_fn = test_line, + .data = &line_0_0_4_2}, + + {.name = "line 0, 0, 8, 4", + .tst_fn = test_line, + .data = &line_0_0_8_4}, + + {.name = "line 0, 0, 4, 8", + .tst_fn = test_line, + .data = &line_0_0_4_8}, + {.name = "Line clipping", .tst_fn = test_line, .data = &testcase_line_clip}, diff --git a/tests/gfx/Makefile b/tests/gfx/Makefile index 750d4553..4a5dc18b 100644 --- a/tests/gfx/Makefile +++ b/tests/gfx/Makefile @@ -2,10 +2,11 @@ TOPDIR=../.. include $(TOPDIR)/pre.mk CSOURCES=$(filter-out $(wildcard *.gen.c),$(wildcard *.c)) -GENSOURCES=APICoverage.gen.c +GENSOURCES=APICoverage.gen.c line_symmetry.gen.c APPS=gfx_benchmark Circle FillCircle Line CircleSeg Polygon Ellipse HLine\ - VLine PutPixelAA HLineAA LineAA FillEllipse FillRect APICoverage.gen + VLine PutPixelAA HLineAA LineAA FillEllipse FillRect APICoverage.gen\ + line_symmetry.gen Circle: common.o FillCircle: common.o diff --git a/tests/gfx/gfx_benchmark.c b/tests/gfx/gfx_benchmark.c index 282ed20e..66be751a 100644 --- a/tests/gfx/gfx_benchmark.c +++ b/tests/gfx/gfx_benchmark.c @@ -36,7 +36,7 @@ static int bench_line(gp_pixel_type type) unsigned int i; - for (i = 0; i < 100000; i++) { + for (i = 0; i < 20000; i++) { gp_line(img, 0 + i % 100, 0 - i % 100, 800 - i%200, 600 + i%200, i % 0xff); } @@ -80,7 +80,7 @@ static int bench_circle(gp_pixel_type type) unsigned int i; - for (i = 0; i < 100000; i++) { + for (i = 0; i < 5000; i++) { gp_circle(img, img->w/2, img->h/2, i % 1000, i%0xff); } diff --git a/tests/gfx/line_symmetry.gen.c.t b/tests/gfx/line_symmetry.gen.c.t new file mode 100644 index 00000000..8f1b5710 --- /dev/null +++ b/tests/gfx/line_symmetry.gen.c.t @@ -0,0 +1,173 @@ +@ include source.t +/* + * Tests that lines horizontally and vertically symetric lines are symetric. + * + * Copyright (C) 2018 Cyril Hrubis + */ + +#include + +#include +#include +#include + +#include "tst_test.h" + +@ max_x = 21 +@ max_y = 21 + +static void print_diff(gp_pixmap *p1, gp_pixmap *p2) +{ + gp_size x, y; + + printf(" "); + for (x = 0; x < p1->w; x++) + printf("-"); + printf("\n"); + + for (y = 0; y < p1->h; y++) { + printf("|"); + for (x = 0; x < p1->w; x++) { + gp_pixel px1 = gp_getpixel_raw_8BPP(p1, x, y); + gp_pixel px2 = gp_getpixel_raw_8BPP(p2, x, y); + + if (px1 == px2) { + if (px1) + printf("*"); + else + printf(" "); + } else { + if (px1) + printf("1"); + else + printf("2"); + } + } + printf("|\n"); + } + + printf(" "); + for (x = 0; x < p1->w; x++) + printf("-"); + printf("\n"); +} + +static void print(gp_pixmap *p) +{ + gp_size x, y; + + printf(" "); + for (x = 0; x < p->w; x++) + printf("-"); + printf("\n"); + + for (y = 0; y < p->h; y++) { + printf("|"); + for (x = 0; x < p->w; x++) { + gp_pixel px = gp_getpixel_raw_8BPP(p, x, y); + + if (px) + printf("*"); + else + printf(" "); + } + printf("|\n"); + } + + printf(" "); + for (x = 0; x < p->w; x++) + printf("-"); + printf("\n"); +} + +static int compare_pixmaps(gp_pixmap *p1, gp_pixmap *p2) +{ + gp_size x, y; + + for (x = 0; x < p1->w; x++) { + for (y = 0; y < p1->h; y++) { + gp_pixel px1 = gp_getpixel_raw_8BPP(p1, x, y); + gp_pixel px2 = gp_getpixel_raw_8BPP(p2, x, y); + + if (px1 != px2) { + print(p1); + print(p2); + print_diff(p1, p2); + return TST_FAILED; + } + } + } + + return TST_SUCCESS; +} + +static void prep(gp_pixmap **p1, gp_pixmap **p2, gp_size w, gp_size h) +{ + *p1 = gp_pixmap_alloc(w, h, GP_PIXEL_G8); + *p2 = gp_pixmap_alloc(w, h, GP_PIXEL_G8); + + gp_fill(*p1, 0); + gp_fill(*p2, 0); +} + +@ for x in range(1, max_x): +@ for y in range(1, max_y): +static int line_{{ x }}_{{ y }}_h(void) +{ + gp_pixmap *p1, *p2; + + prep(&p1, &p2, {{ x }}+1, {{ y }}+1); + + gp_line(p1, 0, 0, {{ x }}, {{ y }}, 1); + gp_line(p2, 0, {{ y }}, {{ x }}, 0, 1); + + gp_filter_mirror_h(p2, p2, NULL); + + return compare_pixmaps(p1, p2); +} + +static int line_{{ x }}_{{ y }}_v(void) +{ + gp_pixmap *p1, *p2; + + prep(&p1, &p2, {{ x }}+1, {{ y }}+1); + + gp_line(p1, 0, 0, {{ x }}, {{ y }}, 1); + gp_line(p2, {{ x }}, 0, 0, {{ y }}, 1); + + gp_filter_mirror_v(p2, p2, NULL); + + return compare_pixmaps(p1, p2); +} + +static int line_{{ x }}_{{ y }}_rot(void) +{ + gp_pixmap *p1, *p2; + gp_size w = GP_MAX({{ x }}, {{ y }}) + 1; + + prep(&p1, &p2, w, w); + + gp_line(p1, 0, 0, {{ x }}, {{ y }}, 1); + gp_line(p2, 0, w-1, {{ y }}, w - 1 - {{ x }}, 1); + p2 = gp_filter_rotate_90_alloc(p2, NULL); + + return compare_pixmaps(p1, p2); +} + +@ end +@ +const struct tst_suite tst_suite = { + .suite_name = "Line symmetry testsuite", + .tests = { +@ for x in range(1, max_x): +@ for y in range(1, max_y): + {.name = "line_h 0, 0, {{ x }}, {{ y }} vs 0, {{ y }}, {{ x }}, 0", + .tst_fn = line_{{ x }}_{{ y }}_h}, + {.name = "line_v 0, 0, {{ x }}, {{ y }} vs {{ x }}, 0, 0, {{ y }}", + .tst_fn = line_{{ x }}_{{ y }}_v}, + {.name = "line 0, 0, {{ x }}, {{ y }} rot 90", + .tst_fn = line_{{ x }}_{{ y }}_rot}, +@ end + {.name = NULL} + } +}; diff --git a/tests/gfx/test_list.txt b/tests/gfx/test_list.txt index b801c5ba..b8ee7ea7 100644 --- a/tests/gfx/test_list.txt +++ b/tests/gfx/test_list.txt @@ -5,6 +5,7 @@ APICoverage.gen HLine VLine Line +line_symmetry.gen Circle FillCircle Ellipse -- 2.11.4.GIT