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

   1 /*
   2  * Copyright © 2016 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
  15 #include "ao_draw.h"
  16 #include "ao_draw_int.h"
  17
  18 #define ao_mask(x,w)    (ao_right(AO_ALLONES,(x) & AO_MASK) & \
  19                          ao_left(AO_ALLONES,(FB_UNIT - ((x)+(w))) & AO_MASK))
  20
  21
  22 /* out of clip region codes */
  23 #define OUT_LEFT 0x08
  24 #define OUT_RIGHT 0x04
  25 #define OUT_ABOVE 0x02
  26 #define OUT_BELOW 0x01
  27
  28 /* major axis for bresenham's line */
  29 #define X_AXIS  0
  30 #define Y_AXIS  1
  31
  32 /*
  33  * Line clipping. Clip to the box, bringing the coordinates forward while
  34  * preserving the actual slope and error
  35  *
  36  *
  37  *      X major line, clip X:
  38  *
  39  *      adjust_x = -x;
  40  *
  41  *      e += adjust_x * e1;
  42  *
  43  *      adjust_y = (e + -e3-1) / -e3;
  44  *
  45  *      e -= adjust_y / -e3;
  46  *
  47  *      X major line, clip Y:
  48  *
  49  *      adjust_y = -y;
  50
  51  *
  52  *      e -= adjust_y / -e3;
  53  *
  54  *      adjust_x = e / e1;
  55  */
  56
  57
  58
  59
  60 static void
  61 ao_bres(const struct ao_bitmap  *dst_bitmap,
  62         int16_t         signdx,
  63         int16_t         signdy,
  64         int16_t         axis,
  65         int16_t         x1,
  66         int16_t         y1,
  67         int16_t         e,
  68         int16_t         e1,
  69         int16_t         e3,
  70         int16_t         len,
  71         uint32_t        and,
  72         uint32_t        xor)
  73 {
  74         int16_t         stride = dst_bitmap->stride;
  75         uint32_t        *dst = dst_bitmap->base;
  76         uint32_t        mask0, mask;
  77
  78         mask0 = 1;
  79         if (signdx < 0)
  80                 mask0 = ao_right(1, AO_UNIT - 1);
  81
  82         dst = dst + y1 * stride + (x1 >> AO_SHIFT);
  83         mask = ao_right(1, x1 & AO_MASK);
  84
  85         if (signdy < 0)
  86                 stride = -stride;
  87
  88         while (len--) {
  89                 /* clip each point */
  90
  91                 *dst = ao_do_mask_rrop(*dst, and, xor, mask);
  92
  93                 if (axis == X_AXIS) {
  94                         if (signdx < 0)
  95                                 mask = ao_left(mask, 1);
  96                         else
  97                                 mask = ao_right(mask, 1);
  98                         if (!mask) {
  99                                 dst += signdx;
 100                                 mask = mask0;
 101                         }
 102                         e += e1;
 103                         if (e >= 0) {
 104                                 dst += stride;
 105                                 e += e3;
 106                         }
 107                 } else {
 108                         dst += stride;
 109                         e += e1;
 110                         if (e >= 0) {
 111                                 if (signdx < 0)
 112                                         mask = ao_left(mask, 1);
 113                                 else
 114                                         mask = ao_right(mask, 1);
 115                                 if (!mask) {
 116                                         dst += signdx;
 117                                         mask = mask0;
 118                                 }
 119                                 e += e3;
 120                         }
 121                 }
 122         }
 123 }
 124
 125 struct ao_cc {
 126         int16_t major;
 127         int16_t minor;
 128         int16_t sign_major;
 129         int16_t sign_minor;
 130         int16_t e;
 131         int16_t e1;
 132         int16_t e3;
 133         int8_t  first;
 134 };
 135
 136 /* line clipping box */
 137 struct ao_cbox {
 138         int16_t maj1, min1;
 139         int16_t maj2, min2;
 140 };
 141
 142 /* -b <= a, so we need to make a bigger */
 143 static int16_t
 144 div_ceil(int32_t a, int16_t b) {
 145         return (a + b + b - 1) / b - 1;
 146 }
 147
 148 static int16_t
 149 div_floor_plus_one(int32_t a, int16_t b) {
 150         return (a + b) / b;
 151 }
 152
 153 static int8_t
 154 ao_clip_line(struct ao_cc *c, struct ao_cbox *b)
 155 {
 156         int32_t adjust_major = 0, adjust_minor = 0;
 157
 158         /* Clip major axis */
 159         if (c->major < b->maj1) {
 160                 if (c->sign_major <= 0)
 161                         return false;
 162                 adjust_major = b->maj1 - c->major;
 163         } else if (c->major >= b->maj2) {
 164                 if (c->sign_major >= 0)
 165                         return false;
 166                 adjust_major = c->major - (b->maj2-1);
 167         }
 168
 169         /* Clip minor axis */
 170         if (c->minor < b->min1) {
 171                 if (c->sign_minor <= 0)
 172                         return false;
 173                 adjust_minor = b->min1 - c->minor;
 174         } else if (c->minor >= b->min2) {
 175                 if (c->sign_minor >= 0)
 176                         return false;
 177                 adjust_minor = c->minor - (b->min2-1);
 178         }
 179
 180         /* If unclipped, we're done */
 181         if (adjust_major == 0 && adjust_minor == 0)
 182                 return true;
 183
 184         /* See how much minor adjustment would happen during
 185          * a major clip. This is a bit tricky because line drawing
 186          * isn't symmetrical when the line passes exactly between
 187          * two pixels, we have to pick which one gets drawn
 188          */
 189         int32_t adj_min;
 190
 191         if (!c->first)
 192                 adj_min = div_ceil(c->e + adjust_major * c->e1, -c->e3);
 193         else
 194                 adj_min = div_floor_plus_one(c->e + adjust_major * c->e1, -c->e3);
 195
 196         if (adj_min < adjust_minor) {
 197                 if (c->first)
 198                         adjust_major = div_ceil(c->e - adjust_minor * c->e3, c->e1);
 199                 else
 200                         adjust_major = div_floor_plus_one(c->e - adjust_minor * c->e3, c->e1);
 201         } else {
 202                 adjust_minor = adj_min;
 203         }
 204
 205         c->e += adjust_major * c->e1 + adjust_minor * c->e3;
 206
 207         c->major += c->sign_major * adjust_major;
 208         c->minor += c->sign_minor * adjust_minor;
 209
 210         return true;
 211 }
 212
 213 void
 214 ao_line(const struct ao_bitmap  *dst,
 215         int16_t                 x1,
 216         int16_t                 y1,
 217         int16_t                 x2,
 218         int16_t                 y2,
 219         uint32_t                fill,
 220         uint8_t                 rop)
 221 {
 222         int16_t adx, ady;
 223         int16_t e, e1, e2, e3;
 224         int16_t signdx = 1, signdy = 1;
 225         int16_t axis;
 226         int16_t len;
 227         struct ao_cc    clip_1, clip_2;
 228         struct ao_cbox  cbox;
 229
 230         if ((adx = x2 - x1) < 0) {
 231                 adx = -adx;
 232                 signdx = -1;
 233         }
 234         if ((ady = y2 - y1) < 0) {
 235                 ady = -ady;
 236                 signdy = -1;
 237         }
 238
 239         if (adx > ady) {
 240                 axis = X_AXIS;
 241                 e1 = ady << 1;
 242                 e2 = e1 - (adx << 1);
 243                 e = e1 - adx;
 244
 245                 clip_1.major = x1;
 246                 clip_1.minor = y1;
 247                 clip_2.major = x2;
 248                 clip_2.minor = y2;
 249                 clip_1.sign_major = signdx;
 250                 clip_1.sign_minor = signdy;
 251
 252                 cbox.maj1 = 0;
 253                 cbox.maj2 = dst->width;
 254                 cbox.min1 = 0;
 255                 cbox.min2 = dst->height;
 256         } else {
 257                 axis = Y_AXIS;
 258                 e1 = adx << 1;
 259                 e2 = e1 - (ady << 1);
 260                 e = e1 - ady;
 261
 262                 clip_1.major = y1;
 263                 clip_1.minor = x1;
 264                 clip_2.major = y2;
 265                 clip_2.minor = x2;
 266                 clip_1.sign_major = signdy;
 267                 clip_1.sign_minor = signdx;
 268
 269                 cbox.maj1 = 0;
 270                 cbox.maj2 = dst->height;
 271                 cbox.min1 = 0;
 272                 cbox.min2 = dst->width;
 273         }
 274
 275         e3 = e2 - e1;
 276         e = e - e1;
 277
 278         clip_1.first = true;
 279         clip_2.first = false;
 280         clip_2.e = clip_1.e = e;
 281         clip_2.e1 = clip_1.e1 = e1;
 282         clip_2.e3 = clip_1.e3 = e3;
 283         clip_2.sign_major = -clip_1.sign_major;
 284         clip_2.sign_minor = -clip_1.sign_minor;
 285
 286         if (!ao_clip_line(&clip_1, &cbox))
 287                 return;
 288
 289         if (!ao_clip_line(&clip_2, &cbox))
 290                 return;
 291
 292         len = clip_1.sign_major * (clip_2.major - clip_1.major) + clip_2.first;
 293
 294         if (len <= 0)
 295                 return;
 296
 297         if (adx > ady) {
 298                 x1 = clip_1.major;
 299                 y1 = clip_1.minor;
 300         } else {
 301                 x1 = clip_1.minor;
 302                 y1 = clip_1.major;
 303         }
 304         ao_bres(dst,
 305                 signdx,
 306                 signdy,
 307                 axis,
 308                 x1,
 309                 y1,
 310                 clip_1.e, e1, e3, len,
 311                 ao_and(rop, fill),
 312                 ao_xor(rop, fill));
 313 }