This is an automated email from the git hooks/post-receive script. It was generated because a ref change was pushed to the repository containing the project gfxprim.git. The branch, master has been updated via e34e0ac5d46c12c6e2a3e7f14bb27138fb005e1f (commit) via c438a7976238a10cd9562cbf28580f0c05b1529f (commit) from 4128a845f099a7902414cfe3314a61bcff9b60c8 (commit) Those revisions listed above that are new to this repository have not appeared on any other notification email; so we list those revisions in full, below. - Log ----------------------------------------------------------------- http://repo.or.cz/w/gfxprim.git/commit/e34e0ac5d46c12c6e2a3e7f14bb27138fb005... commit e34e0ac5d46c12c6e2a3e7f14bb27138fb005e1f Merge: c438a79 4128a84 Author: Jiri BlueBear Dluhos <jiri.bluebear.dluhos@gmail.com> Date: Sun Nov 25 23:03:22 2012 +0100 Merge branch 'master' of git://repo.or.cz/gfxprim http://repo.or.cz/w/gfxprim.git/commit/c438a7976238a10cd9562cbf28580f0c05b15... commit c438a7976238a10cd9562cbf28580f0c05b1529f Author: Jiri BlueBear Dluhos <jiri.bluebear.dluhos@gmail.com> Date: Sun Nov 25 22:59:33 2012 +0100 Finished initial implementation of generic polygon. diff --git a/demos/c_simple/randomshapetest.c b/demos/c_simple/randomshapetest.c index b699348..19fcae4 100644 --- a/demos/c_simple/randomshapetest.c +++ b/demos/c_simple/randomshapetest.c @@ -42,9 +42,10 @@ static int pause_flag = 0; #define SHAPE_ELLIPSE 2 #define SHAPE_TRIANGLE 3 #define SHAPE_RECTANGLE 4 -#define SHAPE_TETRAGON 5 -#define SHAPE_RECTANGLE_AA 6 -#define SHAPE_LAST 6 +#define SHAPE_TETRAGON 5 +#define SHAPE_POLYGON 6 +#define SHAPE_RECTANGLE_AA 7 +#define SHAPE_LAST 7 static int shape = SHAPE_FIRST; /* Draw outlines? */ @@ -142,6 +143,18 @@ void draw_random_tetragon(GP_Pixel pixel) GP_Tetragon(win->context, x0, y0, x1, y1, x2, y2, x3, y3, pixel); } +void draw_random_polygon(GP_Pixel pixel) +{ + GP_Coord xy[10]; + int i; + + for (i = 0; i < 5; i++) { + random_point(win->context, xy + 2*i, xy + 2*i + 1); + } + + GP_FillPolygon_Raw(win->context, 5, xy, pixel); +} + void draw_random_rectangle_AA(GP_Pixel pixel) { int x0, y0, x1, y1; @@ -188,6 +201,9 @@ void redraw_screen(void) case SHAPE_TETRAGON: draw_random_tetragon(pixel); break; + case SHAPE_POLYGON: + draw_random_polygon(pixel); + break; case SHAPE_RECTANGLE_AA: draw_random_rectangle_AA(pixel); break; @@ -203,7 +219,7 @@ void event_loop(void) case GP_EV_KEY: if (ev.code != GP_EV_KEY_DOWN) continue; - + switch (ev.val.key.key) { case GP_KEY_SPACE: shape++; @@ -243,7 +259,7 @@ void event_loop(void) int main(void) { const char *backend_opts = "X11"; - + win = GP_BackendInit(backend_opts, "Random Shape Test", stderr); if (win == NULL) { @@ -251,14 +267,14 @@ int main(void) backend_opts); return 1; } - + white = GP_ColorToContextPixel(GP_COL_WHITE, win->context); black = GP_ColorToContextPixel(GP_COL_BLACK, win->context); - + for (;;) { GP_BackendPoll(win); event_loop(); - + usleep(20000); if (pause_flag) diff --git a/libs/gfx/GP_Polygon.c b/libs/gfx/GP_Polygon.c index 328e7fa..c1d2288 100644 --- a/libs/gfx/GP_Polygon.c +++ b/libs/gfx/GP_Polygon.c @@ -1,193 +1,124 @@ -/***************************************************************************** - * This file is part of gfxprim library. * - * * - * Gfxprim is free software; you can redistribute it and/or * - * modify it under the terms of the GNU Lesser General Public * - * License as published by the Free Software Foundation; either * - * version 2.1 of the License, or (at your option) any later version. * - * * - * Gfxprim is distributed in the hope that it will be useful, * - * but WITHOUT ANY WARRANTY; without even the implied warranty of * - * MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the GNU * - * Lesser General Public License for more details. * - * * - * You should have received a copy of the GNU Lesser General Public * - * License along with gfxprim; if not, write to the Free Software * - * Foundation, Inc., 51 Franklin Street, Fifth Floor, * - * Boston, MA 02110-1301 USA * - * * - * Copyright (C) 2009-2011 Jiri "BlueBear" Dluhos * - * <jiri.bluebear.dluhos@gmail.com> * - * * - * Copyright (C) 2009-2012 Cyril Hrubis <metan@ucw.cz> * - * * - *****************************************************************************/ - -#include "gfx/GP_Polygon.h" -#include "gfx/GP_HLine.h" - -#include <limits.h> #include <stdlib.h> +#include <stdio.h> +#include <math.h> -struct GP_PolygonEdge { - GP_Coord startx, starty; - GP_Coord endx, endy; - GP_Coord dx, dy; -}; +#include "GP_HLine.h" +#include "GP_Polygon.h" -struct GP_Polygon { - struct GP_PolygonEdge *edges; - GP_Coord edge_count; - GP_Coord ymin, ymax; +/* A single edge of the polygon. */ +struct GP_PolygonEdge { + float x1, y1, x2, y2; + float ymin, ymax; + float dx_by_dy; /* dx/dy (0 for horizontal edges) */ }; -#define GP_POLYGON_INITIALIZER { - .edges = NULL, - .edge_count = 0, - .ymin = INT_MAX, - .ymax = 0 -} +/* Threshod value for delta y; edges with dy smaller than this are considered horizontal. */ +const float GP_HORIZ_DY_THRESHOLD = 0.00001f; -static void GP_InitEdge(struct GP_PolygonEdge *edge, - GP_Coord x1, GP_Coord y1, GP_Coord x2, GP_Coord y2) +/* Initializes the polygon_edge structure. */ +static void GP_InitEdge(struct GP_PolygonEdge *edge, float x1, float y1, + float x2, float y2) { - if (y1 < y2) { /* coords are top-down, correct */ - edge->startx = x1; - edge->starty = y1; - edge->endx = x2; - edge->endy = y2; - } else { /* coords are bottom-up, flip them */ - edge->startx = x2; - edge->starty = y2; - edge->endx = x1; - edge->endy = y1; + edge->x1 = x1; + edge->y1 = y1; + edge->x2 = x2; + edge->y2 = y2; + edge->ymin = fminf(edge->y1, edge->y2); + edge->ymax = fmaxf(edge->y1, edge->y2); + + /* horizontal (or almost horizontal) edges are a special case */ + if ((edge->ymax - edge->ymin) < GP_HORIZ_DY_THRESHOLD) { + edge->dx_by_dy = 0.0; /* not meaningful */ + return; } - edge->dx = edge->endx - edge->startx; - edge->dy = edge->endy - edge->starty; + float dx = (edge->x2 - edge->x1); + float dy = (edge->y2 - edge->y1); + edge->dx_by_dy = dx / dy; } -static void GP_AddEdge(struct GP_Polygon *poly, GP_Coord x1, GP_Coord y1, - GP_Coord x2, GP_Coord y2) +/* Computes an intersection of the specified scanline with the given edge. + * If successful, returns 1 and stores the resulting X coordinate into result_x. + * If failed (the edge does not intersect), 0 is returned. + * Horizontal edges are considered to never intersect. + */ +static int GP_ComputeIntersection(float *result_x, struct GP_PolygonEdge *edge, float y) { - struct GP_PolygonEdge *edge = poly->edges + poly->edge_count; - - poly->edge_count++; + if (y<edge->ymin || y>edge->ymax) + return 0; /* outside the edge Y range */ + + if (edge->ymax - edge->ymin < GP_HORIZ_DY_THRESHOLD) + return 0; /* ignore horizontal edges */ - GP_InitEdge(edge, x1, y1, x2, y2); + *result_x = edge->x1 + (y-edge->y1)*edge->dx_by_dy; - poly->ymin = GP_MIN(poly->ymin, edge->starty); - poly->ymax = GP_MAX(poly->ymax, edge->endy); + return 1; } -static int GP_CompareEdges(const void *edge1, const void *edge2) +/* Sorting callback. Compares two floats and returns -1 if A<B, + * +1 if A>B, 0 if they are equal. + */ +static int GP_CompareFloats(const void *ptr_a, const void *ptr_b) { - struct GP_PolygonEdge *e1 = (struct GP_PolygonEdge *) edge1; - struct GP_PolygonEdge *e2 = (struct GP_PolygonEdge *) edge2; - - if (e1->starty > e2->starty) - return 1; - if (e1->starty > e2->starty) - return -1; - - if (e1->startx > e2->startx) - return 1; - if (e1->startx < e2->startx) - return -1; + float a = ((float *) ptr_a)[0]; + float b = ((float *) ptr_b)[0]; + if (a < b) return -1; + if (a > b) return 1; return 0; } -static void GP_LoadPolygon(struct GP_Polygon *poly, GP_Coord vertex_count, - const GP_Coord *xy) +/* Computes intersections of the y coordinate with all edges, + * writing the X coordinates of the intersections, sorted by X coordinate, + * into 'results'. + */ +static int GP_ComputeScanline(float *results, struct GP_PolygonEdge *edges, + size_t count, float y) { - poly->edge_count = 0; - poly->edges = calloc(sizeof(struct GP_PolygonEdge), - vertex_count); + unsigned int edge_index = 0; + int result_index = 0; - GP_Coord i; - GP_Coord coord_count = 2*vertex_count - 2; - for (i = 0; i < coord_count; i+=2) { + for (; edge_index<count; edge_index++) { - /* add the edge, unless it is horizontal */ - if (xy[i+1] != xy[i+3]) { - GP_AddEdge(poly, xy[i], xy[i+1], xy[i+2], xy[i+3]); + struct GP_PolygonEdge *edge = edges + edge_index; + float x; + + if (GP_ComputeIntersection(&x, edge, y)) { + results[result_index++] = x; } } - /* add the closing edge, unless it is horizontal */ - if (xy[1] != xy[i+1]) { - GP_AddEdge(poly, xy[i], xy[i+1], xy[0], xy[1]); - } + qsort(results, result_index, sizeof(float), GP_CompareFloats); - /* sort edges */ - qsort(poly->edges, poly->edge_count, sizeof(struct GP_PolygonEdge), - GP_CompareEdges); + return result_index; } -static void GP_ResetPolygon(struct GP_Polygon *poly) +void GP_FillPolygon_Raw(GP_Context *context, int vertex_count, + const GP_Coord *xy, GP_Pixel pixel) { - free(poly->edges); - poly->edges = NULL; - poly->edge_count = 0; - poly->ymin = INT_MAX; - poly->ymax = 0; -} - -/* - * Finds an X coordinate of an GP_Coordersection of the edge - * with the given Y line. - */ -static inline GP_Coord GP_FindIntersection(GP_Coord y, const struct GP_PolygonEdge *edge) -{ - GP_Coord edge_y = y - edge->starty; /* Y relative to the edge */ - GP_Coord x = edge->startx; - - if (edge->dx > 0) { - while (edge->startx*edge->dy + edge_y*edge->dx > x*edge->dy) - x++; - } else { - while (edge->startx*edge->dy + edge_y*edge->dx < x*edge->dy) - x--; + float ymin = HUGE_VALF, ymax = -HUGE_VALF; + struct GP_PolygonEdge *edge; + struct GP_PolygonEdge edges[vertex_count]; + + int i; + for (i = 0; i < vertex_count - 1; i++) { + edge = edges + i; + GP_InitEdge(edge, xy[2*i], xy[2*i + 1], + xy[2*i + 2], xy[2*i + 3]); + ymin = fminf(ymin, edge->ymin); + ymax = fmaxf(ymax, edge->ymax); } - return x; -} - -void GP_FillPolygon_Raw(GP_Context *context, GP_Coord vertex_count, - const GP_Coord *xy, GP_Pixel pixel) -{ - struct GP_Polygon poly = GP_POLYGON_INITIALIZER; - - GP_LoadPolygon(&poly, vertex_count, xy); - - GP_Coord y, startx, endx; - - for (y = poly.ymin; y <= poly.ymax; y++) { - startx = INT_MAX; - endx = 0; + /* the last edge (from the last point to the first one) */ + edge = edges + vertex_count - 1; + GP_InitEdge(edge, xy[2*i], xy[2*i + 1], xy[0], xy[1]); - GP_Coord i; - for (i = 0; i < poly.edge_count; i++) { - struct GP_PolygonEdge *edge = poly.edges + i; - - if (y < edge->starty || y > edge->endy) - continue; - - GP_Coord GP_Coorder = GP_FindIntersection(y, edge); - - startx = GP_MIN(startx, GP_Coorder); - endx = GP_MAX(endx, GP_Coorder); - - if (y != edge->endy) { - GP_Coorder = GP_FindIntersection(y + 1, edge); - startx = GP_MIN(startx, GP_Coorder); - endx = GP_MAX(endx, GP_Coorder); - } + float intersections[vertex_count]; + int y; + for (y = (int) ymin; y < (int) ymax; y++) { + int inter_count = GP_ComputeScanline(intersections, edges, vertex_count, y + 0.5f); + for (i = 0; i < inter_count; i+=2) { + GP_HLine_Raw(context, intersections[i], intersections[i + 1], y, pixel); } - - GP_HLine_Raw(context, startx, endx, y, pixel); } - - GP_ResetPolygon(&poly); -} +} No newline at end of file ----------------------------------------------------------------------- Summary of changes: demos/c_simple/randomshapetest.c | 32 ++++-- libs/gfx/GP_Polygon.c | 245 ++++++++++++++------------------------ 2 files changed, 112 insertions(+), 165 deletions(-) repo.or.cz automatic notification. Contact project admin jiri.bluebear.dluhos@gmail.com if you want to unsubscribe, or site admin admin@repo.or.cz if you receive no reply. -- gfxprim.git ("A simple 2D graphics library with emphasis on correctness and well-defined operation.")