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