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-2011 Jiri "BlueBear" Dluhos                            *
  20  *                         <jiri.bluebear.dluhos@gmail.com>                  *
  21  *                                                                           *
  22  * Copyright (C) 2009-2012 Cyril Hrubis <metan@ucw.cz>                       *
  23  *                                                                           *
  24  *****************************************************************************/
  25
  26 #include "gfx/GP_Polygon.h"
  27 #include "gfx/GP_HLine.h"
  28
  29 #include <limits.h>
  30 #include <stdlib.h>
  31
  32 struct GP_PolygonEdge {
  33         GP_Coord startx, starty;
  34         GP_Coord endx, endy;
  35         GP_Coord dx, dy;
  36 };
  37
  38 struct GP_Polygon {
  39         struct GP_PolygonEdge *edges;
  40         GP_Coord edge_count;
  41         GP_Coord ymin, ymax;
  42 };
  43
  44 #define GP_POLYGON_INITIALIZER { \
  45         .edges = NULL, \
  46         .edge_count = 0, \
  47         .ymin = INT_MAX, \
  48         .ymax = 0 \
  49 }
  50
  51 static void GP_InitEdge(struct GP_PolygonEdge *edge,
  52                 GP_Coord x1, GP_Coord y1, GP_Coord x2, GP_Coord y2)
  53 {
  54         if (y1 < y2) {                  /* coords are top-down, correct */
  55                 edge->startx = x1;
  56                 edge->starty = y1;
  57                 edge->endx = x2;
  58                 edge->endy = y2;
  59         } else {                        /* coords are bottom-up, flip them */
  60                 edge->startx = x2;
  61                 edge->starty = y2;
  62                 edge->endx = x1;
  63                 edge->endy = y1;
  64         }
  65
  66         edge->dx = edge->endx - edge->startx;
  67         edge->dy = edge->endy - edge->starty;
  68 }
  69
  70 static void GP_AddEdge(struct GP_Polygon *poly, GP_Coord x1, GP_Coord y1,
  71                        GP_Coord x2, GP_Coord y2)
  72 {
  73         struct GP_PolygonEdge *edge = poly->edges + poly->edge_count;
  74
  75         poly->edge_count++;
  76
  77         GP_InitEdge(edge, x1, y1, x2, y2);
  78
  79         poly->ymin = GP_MIN(poly->ymin, edge->starty);
  80         poly->ymax = GP_MAX(poly->ymax, edge->endy);
  81 }
  82
  83 static int GP_CompareEdges(const void *edge1, const void *edge2)
  84 {
  85         struct GP_PolygonEdge *e1 = (struct GP_PolygonEdge *) edge1;
  86         struct GP_PolygonEdge *e2 = (struct GP_PolygonEdge *) edge2;
  87
  88         if (e1->starty > e2->starty)
  89                 return 1;
  90         if (e1->starty > e2->starty)
  91                 return -1;
  92
  93         if (e1->startx > e2->startx)
  94                 return 1;
  95         if (e1->startx < e2->startx)
  96                 return -1;
  97
  98         return 0;
  99 }
 100
 101 static void GP_LoadPolygon(struct GP_Polygon *poly, GP_Coord vertex_count,
 102                 const GP_Coord *xy)
 103 {
 104         poly->edge_count = 0;
 105         poly->edges = calloc(sizeof(struct GP_PolygonEdge),
 106                         vertex_count);
 107
 108         GP_Coord i;
 109         GP_Coord coord_count = 2*vertex_count - 2;
 110         for (i = 0; i < coord_count; i+=2) {
 111
 112                 /* add the edge, unless it is horizontal */
 113                 if (xy[i+1] != xy[i+3]) {
 114                         GP_AddEdge(poly, xy[i], xy[i+1], xy[i+2], xy[i+3]);
 115                 }
 116         }
 117
 118         /* add the closing edge, unless it is horizontal */
 119         if (xy[1] != xy[i+1]) {
 120                 GP_AddEdge(poly, xy[i], xy[i+1], xy[0], xy[1]);
 121         }
 122
 123         /* sort edges */
 124         qsort(poly->edges, poly->edge_count, sizeof(struct GP_PolygonEdge),
 125                 GP_CompareEdges);
 126 }
 127
 128 static void GP_ResetPolygon(struct GP_Polygon *poly)
 129 {
 130         free(poly->edges);
 131         poly->edges = NULL;
 132         poly->edge_count = 0;
 133         poly->ymin = INT_MAX;
 134         poly->ymax = 0;
 135 }
 136
 137 /*
 138  * Finds an X coordinate of an GP_Coordersection of the edge
 139  * with the given Y line.
 140  */
 141 static inline GP_Coord GP_FindIntersection(GP_Coord y, const struct GP_PolygonEdge *edge)
 142 {
 143         GP_Coord edge_y = y - edge->starty;             /* Y relative to the edge */
 144         GP_Coord x = edge->startx;
 145
 146         if (edge->dx > 0) {
 147                 while (edge->startx*edge->dy + edge_y*edge->dx > x*edge->dy)
 148                         x++;
 149         } else {
 150                 while (edge->startx*edge->dy + edge_y*edge->dx < x*edge->dy)
 151                         x--;
 152         }
 153
 154         return x;
 155 }
 156
 157 void GP_FillPolygon_Raw(GP_Context *context, GP_Coord vertex_count,
 158                         const GP_Coord *xy, GP_Pixel pixel)
 159 {
 160         struct GP_Polygon poly = GP_POLYGON_INITIALIZER;
 161
 162         GP_LoadPolygon(&poly, vertex_count, xy);
 163
 164         GP_Coord y, startx, endx;
 165
 166         for (y = poly.ymin; y <= poly.ymax; y++) {
 167                 startx = INT_MAX;
 168                 endx = 0;
 169
 170                 GP_Coord 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                         GP_Coord GP_Coorder = GP_FindIntersection(y, edge);
 178
 179                         startx = GP_MIN(startx, GP_Coorder);
 180                         endx = GP_MAX(endx, GP_Coorder);
 181
 182                         if (y != edge->endy) {
 183                                 GP_Coorder = GP_FindIntersection(y + 1, edge);
 184                                 startx = GP_MIN(startx, GP_Coorder);
 185                                 endx = GP_MAX(endx, GP_Coorder);
 186                         }
 187                 }
 188
 189                 GP_HLine_Raw(context, startx, endx, y, pixel);
 190         }
 191
 192         GP_ResetPolygon(&poly);
 193 }