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 const struct ao_transform ao_identity = {
  26         .x_scale = 1.0f, .x_off = 0.0f,
  27         .y_scale = 1.0f, .y_off = 0.0f
  28 };
  29
  30 static float
  31 _x(const struct ao_coord        *coords,
  32    const struct ao_transform    *transform,
  33    uint16_t                     coord)
  34 {
  35         return ao_t_x_c(&coords[coord], transform);
  36 }
  37
  38 static float
  39 _y(const struct ao_coord        *coords,
  40    const struct ao_transform    *transform,
  41    uint16_t                     coord)
  42 {
  43         return ao_t_y_c(&coords[coord], transform);
  44 }
  45
  46 static uint16_t
  47 _next(uint16_t ncoords, uint16_t edge)
  48 {
  49         return edge == ncoords - 1 ? 0 : edge + 1;
  50 }
  51
  52 /*
  53  * Return if the given edge is 'live' at the specified y coordinate.
  54  * That means the edge spans the y value. Horizontal lines are never
  55  * live
  56  */
  57 static bool
  58 ao_edge_live(const struct ao_coord      *coords,
  59              uint16_t                   ncoords,
  60              const struct ao_transform  *transform,
  61              uint16_t                   edge,
  62              float                      y)
  63 {
  64         float y1 = _y(coords, transform, edge);
  65         float y2 = _y(coords, transform, _next(ncoords, edge));
  66
  67         if (y1 > y2)
  68                 return y2 <= y && y < y1;
  69         else
  70                 return y1 <= y && y < y2;
  71 }
  72
  73 /*
  74  * Compute the X coordinate for a given edge at a specified y value
  75  */
  76 static int16_t
  77 ao_edge_x(const struct ao_coord         *coords,
  78           uint16_t                      ncoords,
  79           const struct ao_transform     *transform,
  80           uint16_t                      edge,
  81           float                         y)
  82 {
  83         uint16_t next_edge = _next(ncoords, edge);
  84         float x1 = _x(coords, transform, edge);
  85         float x2 = _x(coords, transform, next_edge);
  86         float y1 = _y(coords, transform, edge);
  87         float y2 = _y(coords, transform, next_edge);
  88         float dx = x2 - x1;
  89         float dy = y2 - y1;
  90         float off_y = y - y1;
  91
  92         return (int16_t) (x1 + (off_y * dx) / dy + 0.5f);
  93 }
  94
  95 struct next_x {
  96         float           x;
  97         uint16_t        edge;
  98 };
  99
 100 /*
 101  * Find the next X/edge pair along the given scanline.  If two edges
 102  * have the same X value, return them in edge index order. Returns false
 103  * if there are no more edges.
 104  */
 105 static bool
 106 ao_next_x(const struct ao_coord         *coords,
 107           uint16_t                      ncoords,
 108           const struct ao_transform     *transform,
 109           struct next_x                 *this_x,
 110           float                         y)
 111 {
 112         uint16_t        edge;
 113         float           next_x = FLT_MAX;
 114         uint16_t        next_edge = UINT16_MAX;
 115         bool            ret = false;
 116
 117         for (edge = 0; edge < ncoords; edge++) {
 118                 if (ao_edge_live(coords, ncoords, transform, edge, y)) {
 119                         float   nx = ao_edge_x(coords, ncoords, transform, edge, y);
 120                         if (this_x->x < nx || (this_x->x == nx && this_x->edge < edge)) {
 121                                 if (nx < next_x) {
 122                                         next_x = nx;
 123                                         next_edge = edge;
 124                                         ret = true;
 125                                 }
 126                         }
 127                 }
 128         }
 129         this_x->x = next_x;
 130         this_x->edge = next_edge;
 131         return ret;
 132 }
 133
 134 /*
 135  * Fill a span at the specified y coordinate from x1 to x2
 136  */
 137 static void
 138 ao_span(const struct ao_bitmap  *dst,
 139         float                   x1,
 140         float                   x2,
 141         float                   y,
 142         uint32_t                fill,
 143         uint8_t                 rop)
 144 {
 145         int16_t ix1 = (int16_t) floorf(x1 + 0.5f);
 146         int16_t ix2 = (int16_t) floorf(x2 + 0.5f);
 147         int16_t iy = (int16_t) y;
 148
 149         ao_clip(ix1, 0, dst->width);
 150         ao_clip(ix2, 0, dst->width);
 151         ao_solid(ao_and(rop, fill),
 152                  ao_xor(rop, fill),
 153                  dst->base + iy * dst->stride,
 154                  dst->stride,
 155                  ix1,
 156                  ix2 - ix1,
 157                  1);
 158 }
 159
 160 /*
 161  * Compute the 'winding' for the specified edge. Winding is simply an
 162  * indication of whether the edge goes upwards or downwards
 163  */
 164 static int
 165 ao_wind(const struct ao_coord           *coords,
 166         uint16_t                        ncoords,
 167         const struct ao_transform       *transform,
 168         uint16_t                        edge)
 169 {
 170         uint16_t next_edge = _next(ncoords, edge);
 171         return _y(coords, transform, edge) > _y(coords, transform, next_edge) ? 1 : -1;
 172 }
 173
 174 /*
 175  * Fill the specified polygon with non-zero winding rule
 176  */
 177 void
 178 ao_poly(const struct ao_bitmap  *dst,
 179         const struct ao_coord           *coords,
 180         uint16_t                        ncoords,
 181         const struct ao_transform       *transform,
 182         uint32_t                        fill,
 183         uint8_t                 rop)
 184 {
 185         float           y_min, y_max;
 186         uint16_t        edge;
 187         float           y;
 188         float           x;
 189         struct next_x   next_x;
 190         int             wind;
 191
 192         if (!transform)
 193                 transform = &ao_identity;
 194
 195         /*
 196          * Find the y limits of the polygon
 197          */
 198         y_min = y_max = _y(coords, transform, 0);
 199         for (edge = 1; edge < ncoords; edge++) {
 200                 y = _y(coords, transform, edge);
 201                 if (y < y_min)
 202                         y_min = y;
 203                 else if (y > y_max)
 204                         y_max = y;
 205         }
 206
 207         y_min = floorf(y_min);
 208         y_max = ceilf(y_max);
 209
 210         ao_clip(y_min, 0, dst->height);
 211         ao_clip(y_max, 0, dst->height);
 212
 213         /*
 214          * Walk each scanline in the range and fill included spans
 215          */
 216         for (y = y_min; y < y_max; y++) {
 217                 x = INT16_MIN;
 218                 next_x.x = INT16_MIN;
 219                 next_x.edge = 0;
 220                 wind = 0;
 221                 while (ao_next_x(coords, ncoords, transform, &next_x, y)) {
 222
 223                         /*
 224                          * Fill the previous span if winding is
 225                          * non-zero
 226                          */
 227                         if (wind != 0)
 228                                 ao_span(dst, x, next_x.x, y, fill, rop);
 229
 230                         /* Adjust winding for the current span */
 231                         wind += ao_wind(coords, ncoords, transform, next_x.edge);
 232
 233                         /* Step to next span start x value */
 234                         x = next_x.x;
 235                 }
 236         }
 237 }