From b6a3261c28e0809d19fdfc68787148f0dea46ff2 Mon Sep 17 00:00:00 2001 From: Stefan Wildemann Date: Tue, 3 Sep 2019 00:38:35 +0200 Subject: Add:graphics/sdl:Add polygon with holes --- navit/graphics/sdl/graphics_sdl.c | 36 +++++++ navit/graphics/sdl/raster.c | 199 +++++++++++++++++++++++++++++++++++++- navit/graphics/sdl/raster.h | 6 ++ 3 files changed, 240 insertions(+), 1 deletion(-) diff --git a/navit/graphics/sdl/graphics_sdl.c b/navit/graphics/sdl/graphics_sdl.c index 4187d4ed6..bffe65a18 100644 --- a/navit/graphics/sdl/graphics_sdl.c +++ b/navit/graphics/sdl/graphics_sdl.c @@ -284,6 +284,40 @@ static void image_free(struct graphics_priv *gr, struct graphics_image_priv * gi g_free(gi); } +static void draw_polygon_with_holes (struct graphics_priv *gr, struct graphics_gc_priv *gc, struct point *p, int count, + int hole_count, int* ccount, struct point **holes) { + + dbg(lvl_debug, "draw_polygon_with_holes: %p ", gc); + if ((gr->overlay_parent && !gr->overlay_parent->overlay_enable) || (gr->overlay_parent + && gr->overlay_parent->overlay_enable && !gr->overlay_enable) ) { + return; + } + + /* SDL library (SDL_gfx) uses array of X and array of Y instead of array of points + * as the rest of navit does. This requires translating the coordinates from one struct + * into another. As we have our own version of SDL_gfx anyway, I step aside from this + * mechanic and continue using points. This breaks (pseudo= compatibility with stock + * sdl_graphics. Since we need to raytrace the polygons anyway, we can prepare the + * coordinates for SDL primitives there. + */ + + if(gr->aa) { + raster_aapolygon_with_holes(gr->screen, p, count, hole_count, ccount, holes, + SDL_MapRGBA(gr->screen->format, + gc->fore_r, + gc->fore_g, + gc->fore_b, + gc->fore_a)); + } else { + raster_polygon_with_holes(gr->screen, p, count, hole_count, ccount, holes, + SDL_MapRGBA(gr->screen->format, + gc->fore_r, + gc->fore_g, + gc->fore_b, + gc->fore_a)); + } +} + static void draw_polygon(struct graphics_priv *gr, struct graphics_gc_priv *gc, struct point *p, int count) { if ((gr->overlay_parent && !gr->overlay_parent->overlay_enable) || (gr->overlay_parent && gr->overlay_parent->overlay_enable && !gr->overlay_enable) ) { @@ -819,6 +853,8 @@ static struct graphics_methods graphics_methods = { NULL, /* set_attr */ NULL, /* show_native_keyboard */ NULL, /* hide_native_keyboard */ + NULL, /* get_dpi */ + draw_polygon_with_holes }; static struct graphics_priv *overlay_new(struct graphics_priv *gr, struct graphics_methods *meth, struct point *p, diff --git a/navit/graphics/sdl/raster.c b/navit/graphics/sdl/raster.c index 6c713844b..8da7cd9a1 100644 --- a/navit/graphics/sdl/raster.c +++ b/navit/graphics/sdl/raster.c @@ -16,6 +16,7 @@ #include +#include #include "raster.h" @@ -1953,8 +1954,8 @@ void raster_aapolygon(SDL_Surface *dst, int16_t n, int16_t *vx, int16_t *vy, uin o = p = -1; } #else - raster_hline(dst, xa+1, xb, y, color); + #endif // raster_rect_inline(dst, xa, y, xb - xa, 1, color); @@ -1962,3 +1963,199 @@ void raster_aapolygon(SDL_Surface *dst, int16_t n, int16_t *vx, int16_t *vy, uin } } +/** + * @brief render filled polygon with holes by raycasting along the y axis + * + * This function renders a filled polygon that can have holes by SDL primitive + * graphic functions by raycasting along the y axis. This works basically the same + * as for complex polygons. Only difference is the "holes" are individual + * polygon loops not connected to the outer loop. + * FIXME: This draws well as long as the "hole" does not intersect with the + * outer polygon. However such multipolygons are seen a mapping error in OSM + * and therefore the rendering err may even help in detecting them. + * But this could be fixed by never starting a line on a vertex that came from a + * hole intersection. + * + * @param s SDL surface to draw on + * @param p Array of points containing the outer polygon + * @param count Number of points in outer polygon + * @param hole_count Number of hole polygons + * @param ccount number of points per hole polygon + * @oaram holes array of point arrays. One for each "hole" + * @param col Color to draw this. + */ +void raster_aapolygon_with_holes (SDL_Surface *s, struct point *p, int count, int hole_count, int* ccount, + struct point **holes, uint32_t col) { + int i; + struct point * p1; + struct point * p2; + /* Check visibility of clipping rectangle */ + if ((s->clip_rect.w==0) || (s->clip_rect.h==0)) { + return; + } + + /* Sanity check number of edges */ + if (count < 3) { + return; + } + /* + * Draw antialiased outline + */ + p1 = p2 = p; + p2++; + for (i = 1; i < count; i++) { + raster_aalineColorInt(s, p1->x, p1->y, p2->x, p2->y, col, 0); + p1 = p2; + p2++; + } + raster_aalineColorInt(s, p1->x, p1->y, p->x, p->y, col, 0); + raster_polygon_with_holes(s, p, count, hole_count, ccount, holes, col); +} + +/** + * @brief render filled polygon with holes by raycasting along the y axis + * + * This function renders a filled polygon that can have holes by SDL primitive + * graphic functions by raycasting along the y axis. This works basically the same + * as for complex polygons. Only difference is the "holes" are individual + * polygon loops not connected to the outer loop. + * FIXME: This draws well as long as the "hole" does not intersect with the + * outer polygon. However such multipolygons are seen a mapping error in OSM + * and therefore the rendering err may even help in detecting them. + * But this could be fixed by never starting a line on a vertex that came from a + * hole intersection. + * + * @param s SDL surface to draw on + * @param p Array of points containing the outer polygon + * @param count Number of points in outer polygon + * @param hole_count Number of hole polygons + * @param ccount number of points per hole polygon + * @oaram holes array of point arrays. One for each "hole" + * @param col Color to draw this. + */ +void raster_polygon_with_holes (SDL_Surface *s, struct point *p, int count, int hole_count, int* ccount, + struct point **holes, uint32_t col) { + int vertex_max; + int vertex_count; + int * vertexes; + int miny, maxy; + int i; + int y; + + /* Check visibility of clipping rectangle */ + if ((s->clip_rect.w==0) || (s->clip_rect.h==0)) { + return; + } + + /* Sanity check number of edges */ + if (count < 3) { + return; + } + + /* + * Prepare a buffer for vertexes. Maximum number of vertexes is the number of points + * of polygon and holes + */ + vertex_max = count; + for(i =0; i < hole_count; i ++) { + vertex_max += ccount[i]; + } + vertexes = g_malloc(sizeof(int) * vertex_max); + if(vertexes == NULL) { + return; + } + + /* calculate y min and max coordinate. We can ignore the holes, as we won't render hole + * parts "bigger" than the surrounding polygon.*/ + miny = p[0].y; + maxy = p[0].y; + for (i = 1; (i < count); i++) { + if (p[i].y < miny) { + miny = p[i].y; + } else if (p[i].y > maxy) { + maxy = p[i].y; + } + } + + /* scan y coordinates from miny to maxy */ + for(y = miny; y <= maxy ; y ++) { + int h; + vertex_count=0; + /* calculate the intersecting points of the polygon with current y and add to vertexes array*/ + for (i = 0; (i < count); i++) { + int ind1; + int ind2; + struct point p1; + struct point p2; + + if (!i) { + ind1 = count - 1; + ind2 = 0; + } else { + ind1 = i - 1; + ind2 = i; + } + p1.y = p[ind1].y; + p2.y = p[ind2].y; + if (p1.y < p2.y) { + p1.x = p[ind1].x; + p2.x = p[ind2].x; + } else if (p1.y > p2.y) { + p2.y = p[ind1].y; + p1.y = p[ind2].y; + p2.x = p[ind1].x; + p1.x = p[ind2].x; + } else { + continue; + } + if ( ((y >= p1.y) && (y < p2.y)) || ((y == maxy) && (y > p1.y) && (y <= p2.y)) ) { + vertexes[vertex_count++] = ((65536 * (y - p1.y)) / (p2.y - p1.y)) * (p2.x - p1.x) + (65536 * p1.x); + } + } + for(h= 0; h < hole_count; h ++) { + /* add the intersecting points from the holes as well */ + for (i = 0; (i < ccount[h]); i++) { + int ind1; + int ind2; + struct point p1; + struct point p2; + + if (!i) { + ind1 = ccount[h] - 1; + ind2 = 0; + } else { + ind1 = i - 1; + ind2 = i; + } + p1.y = holes[h][ind1].y; + p2.y = holes[h][ind2].y; + if (p1.y < p2.y) { + p1.x = holes[h][ind1].x; + p2.x = holes[h][ind2].x; + } else if (p1.y > p2.y) { + p2.y = holes[h][ind1].y; + p1.y = holes[h][ind2].y; + p2.x = holes[h][ind1].x; + p1.x = holes[h][ind2].x; + } else { + continue; + } + if ( ((y >= p1.y) && (y < p2.y)) || ((y == maxy) && (y > p1.y) && (y <= p2.y)) ) { + vertexes[vertex_count++] = ((65536 * (y - p1.y)) / (p2.y - p1.y)) * (p2.x - p1.x) + (65536 * p1.x); + } + } + } + + /* sort the vertexes */ + qsort(vertexes, vertex_count, sizeof(int), gfxPrimitivesCompareInt); + /* draw the lines between every second vertex */ + for (i = 0; (i < vertex_count); i +=2) { + Sint16 xa; + Sint16 xb; + xa = (vertexes[i] >> 16); + xb = (vertexes[i+1] >> 16); + raster_hline(s, xa+1, xb, y, col); + } + } + g_free(vertexes); +} diff --git a/navit/graphics/sdl/raster.h b/navit/graphics/sdl/raster.h index 2e68ea05f..e295f23fb 100644 --- a/navit/graphics/sdl/raster.h +++ b/navit/graphics/sdl/raster.h @@ -10,15 +10,21 @@ #include #include "SDL.h" +#include "point.h" void raster_rect(SDL_Surface *s, int16_t x, int16_t y, int16_t w, int16_t h, uint32_t col); void raster_line(SDL_Surface *s, int16_t x1, int16_t y1, int16_t x2, int16_t y2, uint32_t col); void raster_circle(SDL_Surface *s, int16_t x, int16_t y, int16_t r, uint32_t col); void raster_polygon(SDL_Surface *s, int16_t n, int16_t *vx, int16_t *vy, uint32_t col); +void raster_polygon_with_holes (SDL_Surface *s, struct point *p, int count, int hole_count, int* ccount, + struct point **holes, uint32_t col); void raster_aaline(SDL_Surface *s, int16_t x1, int16_t y1, int16_t x2, int16_t y2, uint32_t col); void raster_aacircle(SDL_Surface *s, int16_t x, int16_t y, int16_t r, uint32_t col); void raster_aapolygon(SDL_Surface *s, int16_t n, int16_t *vx, int16_t *vy, uint32_t col); +void raster_aapolygon_with_holes (SDL_Surface *s, struct point *p, int count, int hole_count, int* ccount, + struct point **holes, uint32_t col); + #endif /* __RASTER_H */ -- cgit v1.2.1 From 3935ada407de4b84ef511b1206467cd23c711f29 Mon Sep 17 00:00:00 2001 From: Wildemann Stefan Date: Tue, 3 Sep 2019 09:31:36 +0200 Subject: Fix:graphics/sdl Always use new polygon with holes primitive Always use polygon with holes primitive for drawing polygons, as this should be faster than older SDL_gfx like drawing primitives because we do not copy the coordinates into different style buffer before raycasting. --- navit/graphics/sdl/graphics_sdl.c | 40 ++++----------------------------------- 1 file changed, 4 insertions(+), 36 deletions(-) diff --git a/navit/graphics/sdl/graphics_sdl.c b/navit/graphics/sdl/graphics_sdl.c index bffe65a18..d92699307 100644 --- a/navit/graphics/sdl/graphics_sdl.c +++ b/navit/graphics/sdl/graphics_sdl.c @@ -319,42 +319,10 @@ static void draw_polygon_with_holes (struct graphics_priv *gr, struct graphics_g } static void draw_polygon(struct graphics_priv *gr, struct graphics_gc_priv *gc, struct point *p, int count) { - if ((gr->overlay_parent && !gr->overlay_parent->overlay_enable) || (gr->overlay_parent - && gr->overlay_parent->overlay_enable && !gr->overlay_enable) ) { - return; - } - - Sint16 *vx, *vy; - Sint16 x, y; - int i; - - vx = alloca(count * sizeof(Sint16)); - vy = alloca(count * sizeof(Sint16)); - - for(i = 0; i < count; i++) { - x = (Sint16)p[i].x; - y = (Sint16)p[i].y; - vx[i] = x; - vy[i] = y; - - dbg(lvl_debug, "draw_polygon: %p %i %d,%d", gc, i, p[i].x, p[i].y); - } - - if(gr->aa) { - raster_aapolygon(gr->screen, count, vx, vy, - SDL_MapRGBA(gr->screen->format, - gc->fore_r, - gc->fore_g, - gc->fore_b, - gc->fore_a)); - } else { - raster_polygon(gr->screen, count, vx, vy, - SDL_MapRGBA(gr->screen->format, - gc->fore_r, - gc->fore_g, - gc->fore_b, - gc->fore_a)); - } + dbg(lvl_debug, "draw_polygon: %p ", gc); + /* Use polygon with holes primitive as this seems to be better performing than the + * traditional SDL_gfx like ones */ + draw_polygon_with_holes(gr, gc, p, count, 0, NULL, NULL); } static void draw_rectangle(struct graphics_priv *gr, struct graphics_gc_priv *gc, struct point *p, int w, int h) { -- cgit v1.2.1