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 - 2012 Jiri Dluhos <jiri.bluebear.dluhos@gmail.com>    *
  20  * Copyright (C) 2009 - 2012 Cyril Hrubis <metan@ucw.cz>                     *
  21  *                                                                           *
  22  *****************************************************************************/
  23
  24 #define _ISOC99_SOURCE
  25
  26 #include <stdlib.h>
  27 #include <stdio.h>
  28 #include <math.h>
  29 #include <limits.h>
  30
  31 #include "core/GP_Transform.h"
  32 #include "core/GP_GetPutPixel.h"
  33
  34 #include "GP_Line.h"
  35 #include "GP_HLine.h"
  36 #include "GP_Polygon.h"
  37
  38 /* A 2D point specified by GP_Coord coordinates. */
  39 typedef struct {
  40         GP_Coord x, y;
  41 } GP_Point;
  42
  43 /* "almost equality" for float coordinates */
  44 #define GP_COORDS_ALMOST_EQUAL(a,b)     (fabsf((a)-(b)) < 0.0001f)
  45
  46 /*
  47  * Edge state. Every edge proceeds from READY to ACTIVE and then FINISHED.
  48  * HORIZONTAL is special (horizontal edges are handled separately).
  49  * Numeric values reflect sorting priority (ACTIVE is foremost).
  50  */
  51 #define EDGE_HORIZONTAL 3
  52 #define EDGE_FINISHED   2
  53 #define EDGE_READY      1
  54 #define EDGE_ACTIVE     0
  55
  56 /* Working record about an edge. */
  57 struct GP_Edge {
  58         int state;      /* edge state */
  59         float x;                /* X coordinate of the working point */
  60         int y;          /* Y coordinate of the working point */
  61         int dy;         /* vertical size */
  62         float dxy;      /* dx/dy */
  63 };
  64
  65 /* Initializes the edge structure. */
  66 static void GP_InitEdge(struct GP_Edge *e, GP_Point start, GP_Point end)
  67 {
  68         /* horizontal edges are a special case */
  69         if (start.y == end.y) {
  70                 e->dy = 0;
  71                 e->x = start.x;
  72                 e->y = start.y;
  73                 e->dxy = end.x - start.x;
  74                 e->state = EDGE_HORIZONTAL;
  75                 return;
  76         }
  77
  78         /* initialize the working point to the top point of the edge */
  79         if (start.y < end.y) {
  80                 e->x = (float) start.x;
  81                 e->y = start.y;
  82         } else {
  83                 e->x = (float) end.x;
  84                 e->y = end.y;
  85         }
  86
  87         e->dy = GP_ABS(end.y - start.y);
  88
  89         e->dxy = (float)(end.x - start.x)/(end.y - start.y);
  90         e->state = EDGE_READY;
  91
  92         /* Shorten each edge by one pixel at the bottom. This prevents
  93          * every vertex point to be reported as two intersections.
  94          * This also means causes all horizontal edges cut by one pixel,
  95          * but we will fix this at the end by drawing them separately.
  96          */
  97         e->dy--;
  98 }
  99
 100 /* Type of a callback function to be passed to qsort(). */
 101 typedef int (*GP_SortCallback)(const void *, const void *);
 102
 103 /*
 104  * Compares two edges. Used for initial sorting of the edges.
 105  * Edges are sorted by Y first, then by X, then by DXY.
 106  * Returns -1 if e1<e2, +1 if e1>e2, 0 if e1==e2.
 107  */
 108 static int GP_CompareEdgesInitial(struct GP_Edge *e1, struct GP_Edge *e2)
 109 {
 110         if (e1->y < e2->y) return -1;
 111         if (e1->y > e2->y) return 1;
 112
 113         if (e1->x < e2->x) return -1;
 114         if (e1->x > e2->x) return 1;
 115
 116         if (e1->dxy < e2->dxy) return -1;
 117         if (e1->dxy > e2->dxy) return 1;
 118
 119         return 0;
 120 }
 121
 122 /*
 123  * Compares two edges. Used for in-run sorting.
 124  * Edges are sorted by state (ACTIVE < READY < FINISHED), then by X,
 125  * then by DXY.
 126  * Returns -1 if e1<e2, +1 if e1>e2, 0 if e1==e2.
 127  */
 128 static int GP_CompareEdgesRuntime(struct GP_Edge *e1, struct GP_Edge *e2)
 129 {
 130         if (e1->state < e2->state) return -1;
 131         if (e1->state > e2->state) return 1;
 132
 133         if (e1->x < e2->x) return -1;
 134         if (e1->x > e2->x) return 1;
 135
 136         if (e1->dxy < e2->dxy) return -1;
 137         if (e1->dxy > e2->dxy) return 1;
 138
 139         return 0;
 140 }
 141
 142 void GP_FillPolygon_Raw(GP_Pixmap *pixmap, unsigned int nvert,
 143                         const GP_Coord *xy, GP_Pixel pixel)
 144 {
 145         unsigned int i;
 146         struct GP_Edge *e;
 147
 148         if (nvert < 3)
 149                 return;         /* not enough vertices */
 150
 151         GP_Point const *vert = (GP_Point const *) xy;
 152
 153         /* find first and last scanline */
 154         GP_Coord ymin = INT_MAX, ymax = -INT_MAX;
 155         for (i = 0; i < nvert; i++) {
 156                 ymax = GP_MAX(ymax, vert[i].y);
 157                 ymin = GP_MIN(ymin, vert[i].y);
 158         }
 159
 160         /* build a list of edges */
 161         struct GP_Edge edges[nvert];
 162         unsigned int nedges = 0;                /* number of edges in list */
 163         for (i = 0; i < nvert; i++) {
 164
 165                 /*
 166                  * next vertex index (wraps to 0 at end to connect
 167                  * the last vertex with the first one)
 168                  */
 169                 unsigned int nexti = (i+1) % nvert;
 170
 171                 /* add new edge record */
 172                 e = edges + nedges++;
 173                 GP_InitEdge(e, vert[i], vert[nexti]);
 174         }
 175
 176         if (nedges < 2)
 177                 return;         /* not really a polygon */
 178
 179         /* initially sort edges by Y, then X */
 180         qsort(edges, nedges, sizeof(struct GP_Edge),
 181               (GP_SortCallback) GP_CompareEdgesInitial);
 182
 183         /*
 184          * for each scanline, compute intersections with all edges
 185          * and draw a horizontal line segment between the intersections.
 186          */
 187         float inter[nedges];
 188         unsigned int ninter;
 189         int y;
 190         for (y = ymin; y <= ymax; y++) {
 191
 192                 /* mark edges we have just reached as active */
 193                 for (i = 0; i < nedges; i++) {
 194                         e = edges + i;
 195                         if (e->state == EDGE_READY && (y == e->y)) {
 196                                 e->state = EDGE_ACTIVE;
 197                         }
 198                 }
 199                 qsort(edges, nedges, sizeof(struct GP_Edge),
 200                       (GP_SortCallback) GP_CompareEdgesRuntime);
 201
 202                 /* record intersections with active edges */
 203                 ninter = 0;
 204                 for (i = 0; i < nedges; i++) {
 205                         e = edges + i;
 206                         if (e->state == EDGE_ACTIVE) {
 207                                 inter[ninter++] = e->x;
 208                         }
 209                 }
 210
 211                 /* draw each even range between intersections */
 212                 for (i = 0; i < ninter; i += 2) {
 213                         float start = inter[i];
 214
 215                         /* odd number of intersections - skip last */
 216                         if (i+1 == ninter)
 217                                 break;
 218
 219                         float end = inter[i+1];
 220                         GP_HLine_Raw(pixmap, start, end, y, pixel);
 221                 }
 222
 223                 /* update active edges for next step */
 224                 for (i = 0; i < nedges; i++) {
 225                         e = edges + i;
 226                         if (e->state == EDGE_ACTIVE) {
 227                                 if (e->dy == 0) {
 228                                         e->state = EDGE_FINISHED;
 229                                 } else {
 230                                         e->x += e->dxy;
 231                                         e->dy--;
 232                                 }
 233                         }
 234                 }
 235         }
 236
 237         /* finishing touch: draw all horizontal edges that were skipped
 238          * in the main loop
 239          */
 240         for (i = 0; i < nedges; i++) {
 241                 e = edges + i;
 242                 if (e->state == EDGE_HORIZONTAL) {
 243                         GP_HLine_Raw(pixmap, e->x, e->x + e->dxy, e->y,
 244                                      pixel);
 245                 }
 246         }
 247 }
 248
 249 void GP_FillPolygon(GP_Pixmap *pixmap, unsigned int vertex_count,
 250                     const GP_Coord *xy, GP_Pixel pixel)
 251 {
 252         unsigned int i;
 253         GP_Coord xy_copy[2 * vertex_count];
 254
 255         for (i = 0; i < vertex_count; i++) {
 256                 unsigned int x = 2 * i;
 257                 unsigned int y = 2 * i + 1;
 258
 259                 xy_copy[x] = xy[x];
 260                 xy_copy[y] = xy[y];
 261                 GP_TRANSFORM_POINT(pixmap, xy_copy[x], xy_copy[y]);
 262         }
 263
 264         GP_FillPolygon_Raw(pixmap, vertex_count, xy_copy, pixel);
 265 }
 266
 267 void GP_Polygon_Raw(GP_Pixmap *pixmap, unsigned int vertex_count,
 268                     const GP_Coord *xy, GP_Pixel pixel)
 269 {
 270         unsigned int i;
 271
 272         GP_Coord prev_x = xy[2 * vertex_count - 2];
 273         GP_Coord prev_y = xy[2 * vertex_count - 1];
 274
 275         for (i = 0; i < vertex_count; i++) {
 276                 GP_Coord x = xy[2 * i];
 277                 GP_Coord y = xy[2 * i + 1];
 278
 279                 GP_Line_Raw(pixmap, prev_x, prev_y, x, y, pixel);
 280
 281                 prev_x = x;
 282                 prev_y = y;
 283         }
 284 }
 285
 286
 287 void GP_Polygon(GP_Pixmap *pixmap, unsigned int vertex_count,
 288                 const GP_Coord *xy, GP_Pixel pixel)
 289 {
 290         unsigned int i;
 291
 292         GP_Coord prev_x = xy[2 * vertex_count - 2];
 293         GP_Coord prev_y = xy[2 * vertex_count - 1];
 294
 295         GP_TRANSFORM_POINT(pixmap, prev_x, prev_y);
 296
 297         for (i = 0; i < vertex_count; i++) {
 298                 GP_Coord x = xy[2 * i];
 299                 GP_Coord y = xy[2 * i + 1];
 300
 301                 GP_TRANSFORM_POINT(pixmap, x, y);
 302
 303                 GP_Line_Raw(pixmap, prev_x, prev_y, x, y, pixel);
 304
 305                 prev_x = x;
 306                 prev_y = y;
 307         }
 308 }