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 96f86e4c8dfdbdea1a468aa29130010be8f89e27 (commit) via 5534588fb5e3d02ee7504e01ce8b3f1045fba7fd (commit) from 2ebe2eeef4357ca15c5c0656973fffb1487d4b2d (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/96f86e4c8dfdbdea1a468aa29130010be8f89... commit 96f86e4c8dfdbdea1a468aa29130010be8f89e27 Merge: 5534588 2ebe2ee Author: Jiri BlueBear Dluhos <jiri.bluebear.dluhos@gmail.com> Date: Mon Dec 10 14:10:24 2012 +0100 Merge branch 'master' of ssh://repo.or.cz/srv/git/gfxprim http://repo.or.cz/w/gfxprim.git/commit/5534588fb5e3d02ee7504e01ce8b3f1045fba... commit 5534588fb5e3d02ee7504e01ce8b3f1045fba7fd Author: Jiri BlueBear Dluhos <jiri.bluebear.dluhos@gmail.com> Date: Mon Dec 10 14:09:58 2012 +0100 Rewrote FillPolygon() according to books. Still not correct though. diff --git a/libs/gfx/GP_Polygon.c b/libs/gfx/GP_Polygon.c index 2114006..b807d1c 100644 --- a/libs/gfx/GP_Polygon.c +++ b/libs/gfx/GP_Polygon.c @@ -26,6 +26,7 @@ #include <stdlib.h> #include <stdio.h> #include <math.h> +#include <limits.h> #include "core/GP_Transform.h" #include "core/GP_GetPutPixel.h" @@ -34,166 +35,214 @@ #include "GP_HLine.h" #include "GP_Polygon.h" -/* 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) */ -}; +/* "almost equality" for float coordinates */ +#define GP_COORDS_ALMOST_EQUAL(a,b) (fabsf(a-b) < 0.00001f) -/* Threshod value for delta y; edges with dy smaller than this are considered horizontal. */ -const float GP_HORIZ_DY_THRESHOLD = 0.00001f; +/* + * Edge state. Every edge proceeds from READY to ACTIVE and then FINISHED. + * Numeric values reflect sorting priority (ACTIVE < READY < FINISHED). + */ +#define EDGE_FINISHED 2 +#define EDGE_READY 1 +#define EDGE_ACTIVE 0 + +/* Working record about an edge. */ +struct GP_Edge { + int state; /* edge state */ + float x; /* X coordinate of the working point */ + int y; /* Y coordinate of the working point */ + int dy; /* vertical size */ + float dxy; /* dx/dy */ +}; -/* Initializes the polygon_edge structure. */ -static void GP_InitEdge(struct GP_PolygonEdge *edge, float x1, float y1, - float x2, float y2) +/* Initializes the edge structure. */ +static void GP_InitEdge(struct GP_Edge *e, GP_Coord x1, GP_Coord y1, + GP_Coord x2, GP_Coord y2) { - 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; + GP_ASSERT(y1 != y2, "horizontal edges not allowed here"); + + /* initialize the working point to the top point of the edge */ + if (y1 < y2) { + e->x = x1; + e->y = y1; + } else { + e->x = x2; + e->y = y2; } - float dx = (edge->x2 - edge->x1); - float dy = (edge->y2 - edge->y1); - edge->dx_by_dy = dx / dy; + e->dy = GP_ABS(y2 - y1); + e->dxy = (float)(x2 - x1)/(y2 - y1); + e->state = EDGE_READY; } -static int GP_IsEdgeHorizontal(struct GP_PolygonEdge *edge) -{ - return ((edge->ymax - edge->ymin) < GP_HORIZ_DY_THRESHOLD); -} +/* Type of a callback function to be passed to qsort(). */ +typedef int (*GP_SortCallback)(const void *, const void *); -/* 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 ignored at this point (result is always 0). +/* + * Compares two edges. Used for initial sorting of the edges. + * Edges are sorted by Y first, then by X, then by DXY. + * Returns -1 if e1<e2, +1 if e1>e2, 0 if e1==e2. */ -static int GP_ComputeIntersection(float *result_x, struct GP_PolygonEdge *edge, float y) +static int GP_CompareEdgesInitial(struct GP_Edge *e1, struct GP_Edge *e2) { - if (y<edge->ymin || y>edge->ymax) - return 0; /* outside the edge Y range */ + if (e1->y < e2->y) return -1; + if (e1->y > e2->y) return 1; - if (GP_IsEdgeHorizontal(edge)) - return 0; /* ignore horizontal edges */ + if (e1->x < e2->x) return -1; + if (e1->x > e2->x) return 1; - *result_x = edge->x1 + (y-edge->y1)*edge->dx_by_dy; + if (e1->dxy < e2->dxy) return -1; + if (e1->dxy > e2->dxy) return 1; - return 1; + return 0; } -/* Sorting callback. Compares two floats and returns -1 if A<B, - * +1 if A>B, 0 if they are equal. +/* + * Compares two edges. Used for in-run sorting. + * Edges are sorted by state (ACTIVE < READY < FINISHED), then by X, + * then by DXY. + * Returns -1 if e1<e2, +1 if e1>e2, 0 if e1==e2. */ -static int GP_CompareFloats(const void *ptr_a, const void *ptr_b) +static int GP_CompareEdgesRuntime(struct GP_Edge *e1, struct GP_Edge *e2) { - float a = ((float *) ptr_a)[0]; - float b = ((float *) ptr_b)[0]; + if (e1->state < e2->state) return -1; + if (e1->state > e2->state) return 1; + + if (e1->x < e2->x) return -1; + if (e1->x > e2->x) return 1; + + if (e1->dxy < e2->dxy) return -1; + if (e1->dxy > e2->dxy) return 1; - if (a < b) return -1; - if (a > b) return 1; return 0; } -/* 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) -{ - unsigned int edge_index = 0; - int result_index = 0; - - for (; edge_index<count; edge_index++) { +typedef struct { + GP_Coord x, y; +} GP_Point; - struct GP_PolygonEdge *edge = edges + edge_index; - float x; +void GP_FillPolygon_Raw(GP_Context *context, unsigned int nvert, + const GP_Coord *xy, GP_Pixel pixel) +{ + unsigned int i; + struct GP_Edge *e; + + if (nvert < 3) + return; /* not enough vertices */ + + GP_Point const *vert = (GP_Point const *) xy; + + /* find first and last scanline */ + GP_Coord ymin = INT_MAX, ymax = -INT_MAX; + for (i = 0; i < nvert; i++) { + ymax = GP_MAX(ymax, vert[i].y); + ymin = GP_MIN(ymin, vert[i].y); + } + + /* build a list of edges */ + struct GP_Edge edges[nvert]; + unsigned int nedges = 0; /* number of edges in list */ + for (i = 0; i < nvert; i++) { /* - * Horizontal edges match either as a whole (yielding two - * intersections), or not at all. + * next vertex index (wraps to 0 at end to connect + * the last vertex with the first one) */ - if (GP_IsEdgeHorizontal(edge)) { - if (fabsf(edge->ymin - y) < 0.00001f) { - results[result_index++] = GP_MIN(edge->x1, edge->x2); - results[result_index++] = GP_MAX(edge->x1, edge->x2); - } + unsigned int nexti = (i+1) % nvert; + + /* skip horizontal edges */ + if (vert[i].y == vert[nexti].y) { continue; } - if (GP_ComputeIntersection(&x, edge, y)) { - results[result_index++] = x; - } + GP_InitEdge(edges + nedges, + vert[i].x, vert[i].y, + vert[nexti].x, vert[nexti].y); + e = edges + nedges; + + nedges++; } - qsort(results, result_index, sizeof(float), GP_CompareFloats); - - return result_index; -} - -void GP_FillPolygon_Raw(GP_Context *context, unsigned int vertex_count, - const GP_Coord *xy, GP_Pixel pixel) -{ - float ymin = HUGE_VALF, ymax = -HUGE_VALF; - struct GP_PolygonEdge *edge; - struct GP_PolygonEdge edges[2*vertex_count]; - - - /* Build edge structures for each vertex-vertex connection. - * NOTE: Each vertex is in fact in the middle of the pixel, so - * add 0.5 to both coordinates. - */ - int i; - for (i = 0; i < (int)vertex_count - 1; i++) { - edge = edges + i; - GP_InitEdge(edge, - 0.5f + xy[2*i], 0.5f + xy[2*i + 1], - 0.5f + xy[2*i + 2], 0.5f + xy[2*i + 3]); - ymin = fminf(ymin, edge->ymin); - ymax = fmaxf(ymax, edge->ymax); + if (nedges < 2) + return; /* not really a polygon */ + + for (i = 1; i < nedges; i++) { + e = edges + i; + struct GP_Edge *prev_e = edges + i - 1; + if (GP_COORDS_ALMOST_EQUAL(prev_e->x + prev_e->dy*prev_e->dxy, e->x)) { + prev_e->dy--; + } + else if (GP_COORDS_ALMOST_EQUAL(e->x + e->dy*e->dxy, prev_e->x)) { + e->dy--; + } } - /* the last edge (from the last point to the first one) */ - edge = edges + vertex_count - 1; - GP_InitEdge(edge, - 0.5f + xy[2*i], 0.5f + xy[2*i + 1], - 0.5f + xy[0], 0.5f + xy[1]); + /* initially sort edges by Y, then X */ + qsort(edges, nedges, sizeof(struct GP_Edge), + (GP_SortCallback) GP_CompareEdgesInitial); - /* For each scanline, compute intersections with all edges + for (i = 0; i < nedges; i++) { + e = edges + i; + } + + /* + * for each scanline, compute intersections with all edges * and draw a horizontal line segment between the intersections. */ - 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); - - i = 0; - for (;;) { - if (i >= inter_count) break; - float start = intersections[i++]; - if (i >= inter_count) { - - /* a solo vertex or a single-point intersection */ - GP_PutPixel_Raw(context, start, y, pixel); - break; + float inter[nedges]; + unsigned int ninter; + int y = ymin; + for (y = ymin; y <= ymax; y++) { + + /* mark edges we have just reached as active */ + for (i = 0; i < nedges; i++) { + e = edges + i; + if (e->state == EDGE_READY && (y == e->y)) { + e->state = EDGE_ACTIVE; } - float end = intersections[i++]; - if (start == end) { - - /* two intersections - edge joint */ - if (i >= inter_count) break; - end = intersections[i++]; + } + qsort(edges, nedges, sizeof(struct GP_Edge), + (GP_SortCallback) GP_CompareEdgesRuntime); + + /* record intersections with active edges */ + ninter = 0; + for (i = 0; i < nedges; i++) { + e = edges + i; + if (e->state == EDGE_ACTIVE) { + inter[ninter++] = e->x; } + } + + /* draw each even range between intersections */ + for (i = 0; i < ninter; i += 2) { + float start = inter[i]; + + /* odd number of intersections - skip last */ + if (i+1 == ninter) + break; + + float end = inter[i+1]; GP_HLine_Raw(context, start, end, y, pixel); } + + /* check and mark edges we are done with */ + for (i = 0; i < nedges; i++) { + e = edges + i; + if (e->state == EDGE_ACTIVE && e->dy == 0) { + e->state = EDGE_FINISHED; + } + } + qsort(edges, nedges, sizeof(struct GP_Edge), + (GP_SortCallback) GP_CompareEdgesRuntime); + + /* update active edges for next step */ + for (i = 0; i < nedges; i++) { + e = edges + i; + if (e->state == EDGE_ACTIVE) { + e->x += e->dxy; + e->dy--; + } + } } } ----------------------------------------------------------------------- Summary of changes: libs/gfx/GP_Polygon.c | 291 ++++++++++++++++++++++++++++-------------------- 1 files changed, 170 insertions(+), 121 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.")