libs/gfx/GP_Polygon.c

   1 /*****************************************************************************
   2  * This file is part of gfxprim library.                                     *
   3  *                                                                           *
   4  * Gfxprim is free software; you can redistribute it and/or                  *
   5  * modify it under the terms of the GNU Lesser General Public                *
   6  * License as published by the Free Software Foundation; either              *
   7  * version 2.1 of the License, or (at your option) any later version.        *
   8  *                                                                           *
   9  * Gfxprim is distributed in the hope that it will be useful,                *
  10  * but WITHOUT ANY WARRANTY; without even the implied warranty of            *
  11  * MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the GNU         *
  12  * Lesser General Public License for more details.                           *
  13  *                                                                           *
  14  * You should have received a copy of the GNU Lesser General Public          *
  15  * License along with gfxprim; if not, write to the Free Software            *
  16  * Foundation, Inc., 51 Franklin Street, Fifth Floor,                        *
  17  * Boston, MA  02110-1301  USA                                               *
  18  *                                                                           *
  19  * Copyright (C) 2009-2010 Jiri "BlueBear" Dluhos                            *
  20  *                         <jiri.bluebear.dluhos@gmail.com>                  *
  21  *                                                                           *
  22  * Copyright (C) 2009-2010 Cyril Hrubis <metan@ucw.cz>                       *
  23  *                                                                           *
  24  *****************************************************************************/
  25
  26 #include "GP_Gfx.h"
  27
  28 #include <limits.h>
  29 #include <stdlib.h>
  30
  31 struct GP_PolygonEdge {
  32         int startx, starty;
  33         int endx, endy;
  34         int dx, dy;
  35 };
  36
  37 struct GP_Polygon {
  38         struct GP_PolygonEdge *edges;
  39         int edge_count;
  40         int ymin, ymax;
  41 };
  42
  43 #define GP_POLYGON_INITIALIZER { \
  44         .edges = NULL, \
  45         .edge_count = 0, \
  46         .ymin = INT_MAX, \
  47         .ymax = 0 \
  48 }
  49
  50 static void GP_InitEdge(struct GP_PolygonEdge *edge,
  51                 int x1, int y1, int x2, int y2)
  52 {
  53         if (y1 < y2) {                  /* coords are top-down, correct */
  54                 edge->startx = x1;
  55                 edge->starty = y1;
  56                 edge->endx = x2;
  57                 edge->endy = y2;
  58         } else {                        /* coords are bottom-up, flip them */
  59                 edge->startx = x2;
  60                 edge->starty = y2;
  61                 edge->endx = x1;
  62                 edge->endy = y1;
  63         }
  64
  65         edge->dx = edge->endx - edge->startx;
  66         edge->dy = edge->endy - edge->starty;
  67 }
  68
  69 static void GP_AddEdge(struct GP_Polygon *poly, int x1, int y1, int x2, int y2)
  70 {
  71         struct GP_PolygonEdge *edge = poly->edges + poly->edge_count;
  72
  73         poly->edge_count++;
  74
  75         GP_InitEdge(edge, x1, y1, x2, y2);
  76
  77         poly->ymin = GP_MIN(poly->ymin, edge->starty);
  78         poly->ymax = GP_MAX(poly->ymax, edge->endy);
  79 }
  80
  81 static int GP_CompareEdges(const void *edge1, const void *edge2)
  82 {
  83         struct GP_PolygonEdge *e1 = (struct GP_PolygonEdge *) edge1;
  84         struct GP_PolygonEdge *e2 = (struct GP_PolygonEdge *) edge2;
  85
  86         if (e1->starty > e2->starty)
  87                 return 1;
  88         if (e1->starty > e2->starty)
  89                 return -1;
  90
  91         if (e1->startx > e2->startx)
  92                 return 1;
  93         if (e1->startx < e2->startx)
  94                 return -1;
  95
  96         return 0;
  97 }
  98
  99 static void GP_LoadPolygon(struct GP_Polygon *poly, int vertex_count,
 100                 const int *xy)
 101 {
 102         poly->edge_count = 0;
 103         poly->edges = calloc(sizeof(struct GP_PolygonEdge),
 104                         vertex_count);
 105
 106         int i;
 107         int coord_count = 2*vertex_count - 2;
 108         for (i = 0; i < coord_count; i+=2) {
 109
 110                 /* add the edge, unless it is horizontal */
 111                 if (xy[i+1] != xy[i+3]) {
 112                         GP_AddEdge(poly, xy[i], xy[i+1], xy[i+2], xy[i+3]);
 113                 }
 114         }
 115
 116         /* add the closing edge, unless it is horizontal */
 117         if (xy[1] != xy[i+1]) {
 118                 GP_AddEdge(poly, xy[i], xy[i+1], xy[0], xy[1]);
 119         }
 120
 121         /* sort edges */
 122         qsort(poly->edges, poly->edge_count, sizeof(struct GP_PolygonEdge),
 123                 GP_CompareEdges);
 124 }
 125
 126 static void GP_ResetPolygon(struct GP_Polygon *poly)
 127 {
 128         free(poly->edges);
 129         poly->edges = NULL;
 130         poly->edge_count = 0;
 131         poly->ymin = INT_MAX;
 132         poly->ymax = 0;
 133 }
 134
 135 /*
 136  * Finds an X coordinate of an intersection of the edge
 137  * with the given Y line.
 138  */
 139 static inline int GP_FindIntersection(int y, const struct GP_PolygonEdge *edge)
 140 {
 141         int edge_y = y - edge->starty;          /* Y relative to the edge */
 142         int x = edge->startx;
 143
 144         if (edge->dx > 0) {
 145                 while (edge->startx*edge->dy + edge_y*edge->dx > x*edge->dy)
 146                         x++;
 147         } else {
 148                 while (edge->startx*edge->dy + edge_y*edge->dx < x*edge->dy)
 149                         x--;
 150         }
 151
 152         return x;
 153 }
 154
 155 void GP_FillPolygon(GP_Context *context, int vertex_count, const int *xy,
 156                 GP_Pixel pixel)
 157 {
 158         struct GP_Polygon poly = GP_POLYGON_INITIALIZER;
 159
 160         GP_LoadPolygon(&poly, vertex_count, xy);
 161
 162         int y, startx, endx;
 163         int startx_prev = -INT_MAX;
 164         int endx_prev = INT_MAX;
 165
 166         for (y = poly.ymin; y <= poly.ymax; y++) {
 167                 startx = INT_MAX;
 168                 endx = 0;
 169
 170                 int i;
 171                 for (i = 0; i < poly.edge_count; i++) {
 172                         struct GP_PolygonEdge *edge = poly.edges + i;
 173
 174                         if (y < edge->starty || y > edge->endy)
 175                                 continue;
 176
 177                         int inter = GP_FindIntersection(y, edge);
 178
 179                         startx = GP_MIN(startx, inter);
 180                         endx = GP_MAX(endx, inter);
 181
 182                         if (y != edge->endy) {
 183                                 inter = GP_FindIntersection(y + 1, edge);
 184                                 startx = GP_MIN(startx, inter);
 185                                 endx = GP_MAX(endx, inter);
 186                         }
 187                 }
 188
 189                 GP_HLine(context, startx, endx, y, pixel);
 190
 191                 startx_prev = startx;
 192                 endx_prev = endx;
 193         }
 194
 195         GP_ResetPolygon(&poly);
 196 }