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-2011 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         GP_Coord startx, starty;
  33         GP_Coord endx, endy;
  34         GP_Coord dx, dy;
  35 };
  36
  37 struct GP_Polygon {
  38         struct GP_PolygonEdge *edges;
  39         GP_Coord edge_count;
  40         GP_Coord 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                 GP_Coord x1, GP_Coord y1, GP_Coord x2, GP_Coord 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, GP_Coord x1, GP_Coord y1,
  70                        GP_Coord x2, GP_Coord y2)
  71 {
  72         struct GP_PolygonEdge *edge = poly->edges + poly->edge_count;
  73
  74         poly->edge_count++;
  75
  76         GP_InitEdge(edge, x1, y1, x2, y2);
  77
  78         poly->ymin = GP_MIN(poly->ymin, edge->starty);
  79         poly->ymax = GP_MAX(poly->ymax, edge->endy);
  80 }
  81
  82 static int GP_CompareEdges(const void *edge1, const void *edge2)
  83 {
  84         struct GP_PolygonEdge *e1 = (struct GP_PolygonEdge *) edge1;
  85         struct GP_PolygonEdge *e2 = (struct GP_PolygonEdge *) edge2;
  86
  87         if (e1->starty > e2->starty)
  88                 return 1;
  89         if (e1->starty > e2->starty)
  90                 return -1;
  91
  92         if (e1->startx > e2->startx)
  93                 return 1;
  94         if (e1->startx < e2->startx)
  95                 return -1;
  96
  97         return 0;
  98 }
  99
 100 static void GP_LoadPolygon(struct GP_Polygon *poly, GP_Coord vertex_count,
 101                 const GP_Coord *xy)
 102 {
 103         poly->edge_count = 0;
 104         poly->edges = calloc(sizeof(struct GP_PolygonEdge),
 105                         vertex_count);
 106
 107         GP_Coord i;
 108         GP_Coord coord_count = 2*vertex_count - 2;
 109         for (i = 0; i < coord_count; i+=2) {
 110
 111                 /* add the edge, unless it is horizontal */
 112                 if (xy[i+1] != xy[i+3]) {
 113                         GP_AddEdge(poly, xy[i], xy[i+1], xy[i+2], xy[i+3]);
 114                 }
 115         }
 116
 117         /* add the closing edge, unless it is horizontal */
 118         if (xy[1] != xy[i+1]) {
 119                 GP_AddEdge(poly, xy[i], xy[i+1], xy[0], xy[1]);
 120         }
 121
 122         /* sort edges */
 123         qsort(poly->edges, poly->edge_count, sizeof(struct GP_PolygonEdge),
 124                 GP_CompareEdges);
 125 }
 126
 127 static void GP_ResetPolygon(struct GP_Polygon *poly)
 128 {
 129         free(poly->edges);
 130         poly->edges = NULL;
 131         poly->edge_count = 0;
 132         poly->ymin = INT_MAX;
 133         poly->ymax = 0;
 134 }
 135
 136 /*
 137  * Finds an X coordinate of an GP_Coordersection of the edge
 138  * with the given Y line.
 139  */
 140 static inline GP_Coord GP_FindIntersection(GP_Coord y, const struct GP_PolygonEdge *edge)
 141 {
 142         GP_Coord edge_y = y - edge->starty;             /* Y relative to the edge */
 143         GP_Coord x = edge->startx;
 144
 145         if (edge->dx > 0) {
 146                 while (edge->startx*edge->dy + edge_y*edge->dx > x*edge->dy)
 147                         x++;
 148         } else {
 149                 while (edge->startx*edge->dy + edge_y*edge->dx < x*edge->dy)
 150                         x--;
 151         }
 152
 153         return x;
 154 }
 155
 156 void GP_FillPolygon_Raw(GP_Context *context, GP_Coord vertex_count,
 157                         const GP_Coord *xy, GP_Pixel pixel)
 158 {
 159         struct GP_Polygon poly = GP_POLYGON_INITIALIZER;
 160
 161         GP_LoadPolygon(&poly, vertex_count, xy);
 162
 163         GP_Coord y, startx, endx;
 164         GP_Coord startx_prev = -INT_MAX;
 165         GP_Coord endx_prev = INT_MAX;
 166
 167         for (y = poly.ymin; y <= poly.ymax; y++) {
 168                 startx = INT_MAX;
 169                 endx = 0;
 170
 171                 GP_Coord i;
 172                 for (i = 0; i < poly.edge_count; i++) {
 173                         struct GP_PolygonEdge *edge = poly.edges + i;
 174
 175                         if (y < edge->starty || y > edge->endy)
 176                                 continue;
 177
 178                         GP_Coord GP_Coorder = GP_FindIntersection(y, edge);
 179
 180                         startx = GP_MIN(startx, GP_Coorder);
 181                         endx = GP_MAX(endx, GP_Coorder);
 182
 183                         if (y != edge->endy) {
 184                                 GP_Coorder = GP_FindIntersection(y + 1, edge);
 185                                 startx = GP_MIN(startx, GP_Coorder);
 186                                 endx = GP_MAX(endx, GP_Coorder);
 187                         }
 188                 }
 189
 190                 GP_HLine_Raw(context, startx, endx, y, pixel);
 191
 192                 startx_prev = startx;
 193                 endx_prev = endx;
 194         }
 195
 196         GP_ResetPolygon(&poly);
 197 }