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 #ifdef VALIDATE
  58 #include <stdio.h>
  59 #endif
  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         dst = dst + y1 * stride + (x1 >> AO_SHIFT);
  84         mask = ao_right(1, x1 & AO_MASK);
  85
  86         if (signdy < 0)
  87                 stride = -stride;
  88
  89         while (len--) {
  90                 /* clip each point */
  91
  92 #ifdef VALIDATE
  93                 if (x1 < 0 || dst_bitmap->width <= x1) {
  94                         printf("bad line x %d\n", x1);
  95                         return;
  96                 }
  97                 if (y1 < 0 || dst_bitmap->height <= y1) {
  98                         printf("bad line y %d\n", y1);
  99                         return;
 100                 }
 101 #endif
 102                 *dst = ao_do_mask_rrop(*dst, and, xor, mask);
 103
 104                 if (axis == X_AXIS) {
 105 #ifdef VALIDATE
 106                         x1 += signdx;
 107 #endif
 108                         if (signdx < 0)
 109                                 mask = ao_left(mask, 1);
 110                         else
 111                                 mask = ao_right(mask, 1);
 112                         if (!mask) {
 113                                 dst += signdx;
 114                                 mask = mask0;
 115                         }
 116                         e += e1;
 117                         if (e >= 0) {
 118 #ifdef VALIDATE
 119                                 y1 += signdy;
 120 #endif
 121                                 dst += stride;
 122                                 e += e3;
 123                         }
 124                 } else {
 125 #ifdef VALIDATE
 126                         y1 += signdy;
 127 #endif
 128                         dst += stride;
 129                         e += e1;
 130                         if (e >= 0) {
 131 #ifdef VALIDATE
 132                                 x1 += signdx;
 133 #endif
 134                                 if (signdx < 0)
 135                                         mask = ao_left(mask, 1);
 136                                 else
 137                                         mask = ao_right(mask, 1);
 138                                 if (!mask) {
 139                                         dst += signdx;
 140                                         mask = mask0;
 141                                 }
 142                                 e += e3;
 143                         }
 144                 }
 145         }
 146 }
 147
 148 struct ao_cc {
 149         int16_t major;
 150         int16_t minor;
 151         int16_t sign_major;
 152         int16_t sign_minor;
 153         int16_t e;
 154         int16_t e1;
 155         int16_t e3;
 156         int8_t  first;
 157 };
 158
 159 /* line clipping box */
 160 struct ao_cbox {
 161         int16_t maj1, min1;
 162         int16_t maj2, min2;
 163 };
 164
 165 /* -b <= a, so we need to make a bigger */
 166 static int16_t
 167 div_ceil(int32_t a, int16_t b) {
 168         return (int16_t) ((a + b + b - 1) / b - 1);
 169 }
 170
 171 static int16_t
 172 div_floor_plus_one(int32_t a, int16_t b) {
 173         return (int16_t) ((a + b) / b);
 174 }
 175
 176 static int8_t
 177 ao_clip_line(struct ao_cc *c, struct ao_cbox *b)
 178 {
 179         int32_t adjust_major = 0, adjust_minor = 0;
 180
 181         /* Clip major axis */
 182         if (c->major < b->maj1) {
 183                 if (c->sign_major <= 0)
 184                         return false;
 185                 adjust_major = b->maj1 - c->major;
 186         } else if (c->major >= b->maj2) {
 187                 if (c->sign_major >= 0)
 188                         return false;
 189                 adjust_major = c->major - (b->maj2-1);
 190         }
 191
 192         /* Clip minor axis */
 193         if (c->minor < b->min1) {
 194                 if (c->sign_minor <= 0)
 195                         return false;
 196                 adjust_minor = b->min1 - c->minor;
 197         } else if (c->minor >= b->min2) {
 198                 if (c->sign_minor >= 0)
 199                         return false;
 200                 adjust_minor = c->minor - (b->min2-1);
 201         }
 202
 203         /* If unclipped, we're done */
 204         if (adjust_major == 0 && adjust_minor == 0)
 205                 return true;
 206
 207         /* See how much minor adjustment would happen during
 208          * a major clip. This is a bit tricky because line drawing
 209          * isn't symmetrical when the line passes exactly between
 210          * two pixels, we have to pick which one gets drawn
 211          */
 212         int32_t adj_min;
 213
 214         if (!c->first)
 215                 adj_min = div_ceil(c->e + adjust_major * c->e1, -c->e3);
 216         else
 217                 adj_min = div_floor_plus_one(c->e + adjust_major * c->e1, -c->e3);
 218
 219         if (adj_min < adjust_minor) {
 220                 if (c->first)
 221                         adjust_major = div_ceil(c->e - adjust_minor * c->e3, c->e1);
 222                 else
 223                         adjust_major = div_floor_plus_one(c->e - adjust_minor * c->e3, c->e1);
 224         } else {
 225                 adjust_minor = adj_min;
 226         }
 227
 228         c->e = (int16_t) (c->e + adjust_major * c->e1 + adjust_minor * c->e3);
 229
 230         c->major = (int16_t) (c->major + c->sign_major * adjust_major);
 231         c->minor = (int16_t) (c->minor + c->sign_minor * adjust_minor);
 232
 233         return true;
 234 }
 235
 236 void
 237 ao_line(const struct ao_bitmap  *dst,
 238         int16_t                 x1,
 239         int16_t                 y1,
 240         int16_t                 x2,
 241         int16_t                 y2,
 242         uint32_t                fill,
 243         uint8_t                 rop)
 244 {
 245         int16_t adx, ady;
 246         int16_t e, e1, e2, e3;
 247         int16_t signdx = 1, signdy = 1;
 248         int16_t axis;
 249         int16_t len;
 250         struct ao_cc    clip_1, clip_2;
 251         struct ao_cbox  cbox;
 252
 253         if ((adx = x2 - x1) < 0) {
 254                 adx = -adx;
 255                 signdx = -1;
 256         }
 257         if ((ady = y2 - y1) < 0) {
 258                 ady = -ady;
 259                 signdy = -1;
 260         }
 261
 262         if (adx > ady) {
 263                 axis = X_AXIS;
 264                 e1 = ady << 1;
 265                 e2 = e1 - (int16_t) (adx << 1);
 266                 e = e1 - adx;
 267
 268                 clip_1.major = x1;
 269                 clip_1.minor = y1;
 270                 clip_2.major = x2;
 271                 clip_2.minor = y2;
 272                 clip_1.sign_major = signdx;
 273                 clip_1.sign_minor = signdy;
 274
 275                 cbox.maj1 = 0;
 276                 cbox.maj2 = dst->width;
 277                 cbox.min1 = 0;
 278                 cbox.min2 = dst->height;
 279         } else {
 280                 axis = Y_AXIS;
 281                 e1 = adx << 1;
 282                 e2 = e1 - (int16_t) (ady << 1);
 283                 e = e1 - ady;
 284
 285                 clip_1.major = y1;
 286                 clip_1.minor = x1;
 287                 clip_2.major = y2;
 288                 clip_2.minor = x2;
 289                 clip_1.sign_major = signdy;
 290                 clip_1.sign_minor = signdx;
 291
 292                 cbox.maj1 = 0;
 293                 cbox.maj2 = dst->height;
 294                 cbox.min1 = 0;
 295                 cbox.min2 = dst->width;
 296         }
 297
 298         e3 = e2 - e1;
 299         e = e - e1;
 300
 301         clip_1.first = true;
 302         clip_2.first = false;
 303         clip_2.e = clip_1.e = e;
 304         clip_2.e1 = clip_1.e1 = e1;
 305         clip_2.e3 = clip_1.e3 = e3;
 306         clip_2.sign_major = -clip_1.sign_major;
 307         clip_2.sign_minor = -clip_1.sign_minor;
 308
 309         if (!ao_clip_line(&clip_1, &cbox))
 310                 return;
 311
 312         if (!ao_clip_line(&clip_2, &cbox))
 313                 return;
 314
 315         len = (int16_t) (clip_1.sign_major * (clip_2.major - clip_1.major) + clip_2.first);
 316
 317         if (len <= 0)
 318                 return;
 319
 320         if (adx > ady) {
 321                 x1 = clip_1.major;
 322                 y1 = clip_1.minor;
 323         } else {
 324                 x1 = clip_1.minor;
 325                 y1 = clip_1.major;
 326         }
 327         ao_bres(dst,
 328                 signdx,
 329                 signdy,
 330                 axis,
 331                 x1,
 332                 y1,
 333                 clip_1.e, e1, e3, len,
 334                 ao_and(rop, fill),
 335                 ao_xor(rop, fill));
 336 }