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
  23 /*
  24  * Return if the given edge is 'live' at the specified y coordinate.
  25  * That means the edge spans the y value. Horizontal lines are never
  26  * live
  27  */
  28 static bool
  29 ao_edge_live(const struct ao_coord      *coords,
  30              uint16_t                   ncoords,
  31              uint16_t                   edge,
  32              int16_t                    y)
  33 {
  34         int next_edge = (edge == ncoords - 1) ? 0 : edge + 1;
  35         int16_t y1 = coords[edge].y;
  36         int16_t y2 = coords[next_edge].y;
  37
  38         if (y1 > y2)
  39                 return y2 <= y && y < y1;
  40         else
  41                 return y1 <= y && y < y2;
  42 }
  43
  44 /*
  45  * Compute the X coordinate for a given edge at a specified y value
  46  */
  47 static int16_t
  48 ao_edge_x(const struct ao_coord *coords,
  49           uint16_t              ncoords,
  50           uint16_t              edge,
  51           int16_t               y)
  52 {
  53         int     next_edge = (edge == ncoords - 1) ? 0 : edge + 1;
  54         int16_t x1 = coords[edge].x;
  55         int16_t x2 = coords[next_edge].x;
  56         int16_t y1 = coords[edge].y;
  57         int16_t y2 = coords[next_edge].y;
  58         int16_t dx = x2 - x1;
  59         int16_t dy = y2 - y1;
  60         int16_t off_y = y - y1;
  61
  62         return x1 + (off_y * dx) / dy;
  63 }
  64
  65 struct next_x {
  66         int16_t         x;
  67         uint16_t        edge;
  68 };
  69
  70 /*
  71  * Find the next X/edge pair along the given scanline.  If two edges
  72  * have the same X value, return them in edge index order. Returns false
  73  * if there are no more edges.
  74  */
  75 static bool
  76 ao_next_x(const struct ao_coord *coords,
  77           uint16_t              ncoords,
  78           struct next_x         *this_x,
  79           int16_t               y)
  80 {
  81         uint16_t        edge;
  82         int16_t         next_x = INT16_MAX;
  83         uint16_t        next_edge = UINT16_MAX;
  84         bool            ret = false;
  85
  86         for (edge = 0; edge < ncoords; edge++) {
  87                 if (ao_edge_live(coords, ncoords, edge, y)) {
  88                         int16_t nx = ao_edge_x(coords, ncoords, edge, y);
  89                         if (this_x->x < nx || (this_x->x == nx && this_x->edge < edge)) {
  90                                 if (nx < next_x) {
  91                                         next_x = nx;
  92                                         next_edge = edge;
  93                                         ret = true;
  94                                 }
  95                         }
  96                 }
  97         }
  98         this_x->x = next_x;
  99         this_x->edge = next_edge;
 100         return ret;
 101 }
 102
 103 /*
 104  * Fill a span at the specified y coordinate from x1 to x2
 105  */
 106 static void
 107 ao_span(const struct ao_bitmap  *dst,
 108         int16_t                 x1,
 109         int16_t                 x2,
 110         int16_t                 y,
 111         uint32_t                fill,
 112         uint8_t                 rop)
 113 {
 114         ao_rect(dst, x1, y, x2 - x1, 1, fill, rop);
 115 }
 116
 117 /*
 118  * Compute the 'winding' for the specified edge. Winding is simply an
 119  * indication of whether the edge goes upwards or downwards
 120  */
 121 static int
 122 ao_wind(const struct ao_coord   *coords,
 123         uint16_t                ncoords,
 124         uint16_t                edge)
 125 {
 126         uint16_t next_edge = (edge == ncoords - 1) ? 0 : edge + 1;
 127         return coords[edge].y > coords[next_edge].y ? 1 : -1;
 128 }
 129
 130 /*
 131  * Fill the specified polygon with non-zero winding rule
 132  */
 133 void
 134 ao_poly(const struct ao_bitmap  *dst,
 135         const struct ao_coord   *coords,
 136         uint16_t                ncoords,
 137         uint32_t                fill,
 138         uint8_t                 rop)
 139 {
 140         int16_t         y_min, y_max;
 141         uint16_t        edge;
 142         int16_t         y;
 143         int16_t         x;
 144         struct next_x   next_x;
 145         int             wind;
 146
 147         /*
 148          * Find the y limits of the polygon
 149          */
 150         y_min = y_max = coords[0].y;
 151         for (edge = 1; edge < ncoords; edge++) {
 152                 y = coords[edge].y;
 153                 if (y < y_min)
 154                         y_min = y;
 155                 else if (y > y_max)
 156                         y_max = y;
 157         }
 158
 159         /*
 160          * Walk each scanline in the range and fill included spans
 161          */
 162         for (y = y_min; y < y_max; y++) {
 163                 x = INT16_MIN;
 164                 next_x.x = INT16_MIN;
 165                 next_x.edge = 0;
 166                 wind = 0;
 167                 while (ao_next_x(coords, ncoords, &next_x, y)) {
 168
 169                         /*
 170                          * Fill the previous span if winding is
 171                          * non-zero
 172                          */
 173                         if (wind != 0)
 174                                 ao_span(dst, x, next_x.x, y, fill, rop);
 175
 176                         /* Adjust winding for the current span */
 177                         wind += ao_wind(coords, ncoords, next_x.edge);
 178
 179                         /* Step to next span start x value */
 180                         x = next_x.x;
 181                 }
 182         }
 183 }