git.gag.com Git - fw/altos/blob - src/draw/ao_poly.c

   1 /*
   2  * Copyright © 2023 Keith Packard <keithp@keithp.com>
   3  *
   4  * This program is free software; you can redistribute it and/or modify
   5  * it under the terms of the GNU General Public License as published by
   6  * the Free Software Foundation, either version 2 of the License, or
   7  * (at your option) any later version.
   8  *
   9  * This program is distributed in the hope that it will be useful, but
  10  * WITHOUT ANY WARRANTY; without even the implied warranty of
  11  * MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the GNU
  12  * General Public License for more details.
  13  *
  14  * You should have received a copy of the GNU General Public License along
  15  * with this program; if not, write to the Free Software Foundation, Inc.,
  16  * 59 Temple Place, Suite 330, Boston, MA 02111-1307 USA.
  17  */
  18
  19 #include "ao_draw.h"
  20 #include "ao_draw_int.h"
  21 #include <stdio.h>
  22 #include <math.h>
  23 #include <float.h>
  24
  25 /*
  26  * Return if the given edge is 'live' at the specified y coordinate.
  27  * That means the edge spans the y value. Horizontal lines are never
  28  * live
  29  */
  30 static bool
  31 ao_edge_live(const struct ao_coord      *coords,
  32              uint16_t                   ncoords,
  33              uint16_t                   edge,
  34              float                      y)
  35 {
  36         int next_edge = (edge == ncoords - 1) ? 0 : edge + 1;
  37         float y1 = coords[edge].y;
  38         float y2 = coords[next_edge].y;
  39
  40         if (y1 > y2)
  41                 return y2 <= y && y < y1;
  42         else
  43                 return y1 <= y && y < y2;
  44 }
  45
  46 /*
  47  * Compute the X coordinate for a given edge at a specified y value
  48  */
  49 static int16_t
  50 ao_edge_x(const struct ao_coord *coords,
  51           uint16_t              ncoords,
  52           uint16_t              edge,
  53           float                 y)
  54 {
  55         int     next_edge = (edge == ncoords - 1) ? 0 : edge + 1;
  56         float x1 = coords[edge].x;
  57         float x2 = coords[next_edge].x;
  58         float y1 = coords[edge].y;
  59         float y2 = coords[next_edge].y;
  60         float dx = x2 - x1;
  61         float dy = y2 - y1;
  62         float off_y = y - y1;
  63
  64         return x1 + (off_y * dx) / dy;
  65 }
  66
  67 struct next_x {
  68         float           x;
  69         uint16_t        edge;
  70 };
  71
  72 /*
  73  * Find the next X/edge pair along the given scanline.  If two edges
  74  * have the same X value, return them in edge index order. Returns false
  75  * if there are no more edges.
  76  */
  77 static bool
  78 ao_next_x(const struct ao_coord *coords,
  79           uint16_t              ncoords,
  80           struct next_x         *this_x,
  81           float         y)
  82 {
  83         uint16_t        edge;
  84         float           next_x = FLT_MAX;
  85         uint16_t        next_edge = UINT16_MAX;
  86         bool            ret = false;
  87
  88         for (edge = 0; edge < ncoords; edge++) {
  89                 if (ao_edge_live(coords, ncoords, edge, y)) {
  90                         float   nx = ao_edge_x(coords, ncoords, edge, y);
  91                         if (this_x->x < nx || (this_x->x == nx && this_x->edge < edge)) {
  92                                 if (nx < next_x) {
  93                                         next_x = nx;
  94                                         next_edge = edge;
  95                                         ret = true;
  96                                 }
  97                         }
  98                 }
  99         }
 100         this_x->x = next_x;
 101         this_x->edge = next_edge;
 102         return ret;
 103 }
 104
 105 /*
 106  * Fill a span at the specified y coordinate from x1 to x2
 107  */
 108 static void
 109 ao_span(const struct ao_bitmap  *dst,
 110         float                   x1,
 111         float                   x2,
 112         float                   y,
 113         uint32_t                fill,
 114         uint8_t                 rop)
 115 {
 116         int16_t ix1 = floorf(x1 + 0.5f);
 117         int16_t ix2 = floorf(x2 + 0.5f);
 118         int16_t iy = (int16_t) y;
 119         ao_rect(dst, ix1, iy, ix2 - ix1, 1, fill, rop);
 120 }
 121
 122 /*
 123  * Compute the 'winding' for the specified edge. Winding is simply an
 124  * indication of whether the edge goes upwards or downwards
 125  */
 126 static int
 127 ao_wind(const struct ao_coord   *coords,
 128         uint16_t                ncoords,
 129         uint16_t                edge)
 130 {
 131         uint16_t next_edge = (edge == ncoords - 1) ? 0 : edge + 1;
 132         return coords[edge].y > coords[next_edge].y ? 1 : -1;
 133 }
 134
 135 /*
 136  * Fill the specified polygon with non-zero winding rule
 137  */
 138 void
 139 ao_poly(const struct ao_bitmap  *dst,
 140         const struct ao_coord   *coords,
 141         uint16_t                ncoords,
 142         uint32_t                fill,
 143         uint8_t                 rop)
 144 {
 145         float           y_min, y_max;
 146         uint16_t        edge;
 147         float           y;
 148         float           x;
 149         struct next_x   next_x;
 150         int             wind;
 151
 152         /*
 153          * Find the y limits of the polygon
 154          */
 155         y_min = y_max = coords[0].y;
 156         for (edge = 1; edge < ncoords; edge++) {
 157                 y = coords[edge].y;
 158                 if (y < y_min)
 159                         y_min = y;
 160                 else if (y > y_max)
 161                         y_max = y;
 162         }
 163
 164         y_min = floorf(y_min);
 165         y_max = ceilf(y_max);
 166
 167         /*
 168          * Walk each scanline in the range and fill included spans
 169          */
 170         for (y = y_min; y < y_max; y++) {
 171                 x = INT16_MIN;
 172                 next_x.x = INT16_MIN;
 173                 next_x.edge = 0;
 174                 wind = 0;
 175                 while (ao_next_x(coords, ncoords, &next_x, y)) {
 176
 177                         /*
 178                          * Fill the previous span if winding is
 179                          * non-zero
 180                          */
 181                         if (wind != 0)
 182                                 ao_span(dst, x, next_x.x, y, fill, rop);
 183
 184                         /* Adjust winding for the current span */
 185                         wind += ao_wind(coords, ncoords, next_x.edge);
 186
 187                         /* Step to next span start x value */
 188                         x = next_x.x;
 189                 }
 190         }
 191 }