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

   1 #!/usr/bin/nickle
   2
   3 autoimport Cairo;
   4 autoload PRNG;
   5
   6 int
   7 sign(int x)
   8 {
   9         return x == 0 ? 0 : x < 0 ? -1 : 1;
  10 }
  11
  12 int X_AXIS = 0;
  13 int Y_AXIS = 1;
  14
  15 typedef struct {
  16         int     major;
  17         int     minor;
  18         int     sign_major;
  19         int     sign_minor;
  20         int     e;
  21         int     e1;
  22         int     e3;
  23         bool    first;
  24 } clip_context;
  25
  26 typedef struct {
  27         int     maj1, min1, maj2, min2;
  28 } clip_box;
  29
  30 typedef struct {
  31         int     x1, y1, x2, y2;
  32 } box;
  33
  34 typedef struct {
  35         int     x, y;
  36 } point;
  37
  38 typedef struct {
  39         int     x1, y1, x2, y2;
  40         box     b;
  41         point[] clipped;
  42         point[] run;
  43 } test;
  44
  45 box     bounds = { .x1 = 10, .x2 = 30, .y1 = 10, .y2 = 30 };
  46
  47 int
  48 div_ceil(a, b) {
  49         a += b;
  50         assert(a >= 0 && b > 0, "bad divide args %d %d\n", a, b);
  51         return (a + b - 1) // b - 1;
  52 }
  53
  54 int
  55 div_floor_plus_one(a, b) {
  56         a += b;
  57         assert(a >= 0 && b > 0, "bad divide args %d %d\n", a, b);
  58         return a // b;
  59 }
  60
  61 bool
  62 clip(*clip_context c, *clip_box b)
  63 {
  64         int     adjust_major = 0, adjust_minor = 0;
  65
  66         /* Clip major axis */
  67         if (c->major < b->maj1) {
  68                 if (c->sign_major <= 0)
  69                         return false;
  70                 adjust_major = b->maj1 - c->major;
  71         } else if (c->major >= b->maj2) {
  72                 if (c->sign_major >= 0)
  73                         return false;
  74                 adjust_major = c->major - (b->maj2-1);
  75         }
  76
  77         /* Clip minor axis */
  78         if (c->minor < b->min1) {
  79                 if (c->sign_minor <= 0)
  80                         return false;
  81                 adjust_minor = b->min1 - c->minor;
  82         } else if (c->minor >= b->min2) {
  83                 if (c->sign_minor >= 0)
  84                         return false;
  85                 adjust_minor = c->minor - (b->min2-1);
  86         }
  87
  88         /* If unclipped, we're done */
  89         if (adjust_major == 0 && adjust_minor == 0)
  90                 return true;
  91
  92         /* See how much minor adjustment would happen during
  93          * a major clip. This is a bit tricky because line drawing
  94          * isn't symmetrical when the line passes exactly between
  95          * two pixels, we have to pick which one gets drawn
  96          */
  97         int     adj_min;
  98
  99         if (!c->first)
 100                 adj_min = div_ceil(c->e + adjust_major * c->e1, -c->e3);
 101         else
 102                 adj_min = div_floor_plus_one(c->e + adjust_major * c->e1, -c->e3);
 103
 104         /* Compare that to the minor clip and pick
 105          * the larger amount.
 106          */
 107         printf ("\tinitial major %d minor %d error %d e1 %d e3 %d\n", c->major, c->minor, c->e, c->e1, c->e3);
 108
 109         if (adj_min < adjust_minor) {
 110                 printf("\tminor clip dominates %d < %d. adjust major %d -> ",
 111                        adj_min, adjust_minor, adjust_major);
 112                 if (c->first)
 113                         adjust_major = div_ceil(c->e - adjust_minor * c->e3, c->e1);
 114                 else
 115                         adjust_major = div_floor_plus_one(c->e - adjust_minor * c->e3, c->e1);
 116                 printf("%d\n", adjust_major);
 117         } else {
 118                 printf("\tminor clip dominates %d > %d. adjust minor %d -> ",
 119                        adj_min, adjust_minor, adjust_minor);
 120                 adjust_minor = adj_min;
 121                 printf("%d\n", adjust_minor);
 122         }
 123
 124         c->e += adjust_major * c->e1 + adjust_minor * c->e3;
 125
 126         c->major += c->sign_major * adjust_major;
 127         c->minor += c->sign_minor * adjust_minor;
 128
 129         printf ("\tadjust major %d adjust minor %d e %d e1 %d e3 %e\n",
 130                 adjust_major, adjust_minor, c->e, c->e1, c->e3);
 131
 132         if (c->e >= 0)
 133                 printf ("error positive e %d e1 %d e3 %d\n",
 134                         c->e, c->e1, c->e3);
 135         if (c->e < c->e3)
 136                 printf ("error magnitude too large e %d e1 %d e3 %d\n", c->e, c->e1, c->e3);
 137
 138         return true;
 139 }
 140
 141 test
 142 line(int x1, int y1, int x2, int y2, *box b) {
 143
 144         int     dx = x2 - x1;
 145         int     dy = y2 - y1;
 146         int     signdx = sign(dx);
 147         int     signdy = sign(dy);
 148         int     adx = abs(dx);
 149         int     ady = abs(dy);
 150         int     axis;
 151         int     e, e1, e2, e3;
 152         int     len;
 153         clip_context    clip_1, clip_2;
 154         clip_box        c;
 155         bool            clipped = false;
 156         test            t = {
 157                 .x1 = x1,
 158                 .y1 = y1,
 159                 .x2 = x2,
 160                 .y2 = y2,
 161                 .b = *b,
 162                 .clipped = (point[...]) {},
 163                 .run = (point[...]) {}
 164         };
 165
 166         if (adx >= ady) {
 167                 axis = X_AXIS;
 168                 e1 = ady << 1;
 169                 e2 = e1 - (adx << 1);
 170                 e = e1 - adx;
 171                 len = adx;
 172
 173                 clip_1.major = x1;
 174                 clip_1.minor = y1;
 175                 clip_2.major = x2;
 176                 clip_2.minor = y2;
 177                 clip_1.sign_major = signdx;
 178                 clip_1.sign_minor = signdy;
 179
 180                 c.maj1 = b->x1;
 181                 c.maj2 = b->x2;
 182                 c.min1 = b->y1;
 183                 c.min2 = b->y2;
 184         } else {
 185                 axis = Y_AXIS;
 186                 e1 = adx << 1;
 187                 e2 = e1 - (ady << 1);
 188                 e = e1 - ady;
 189                 len = ady;
 190
 191                 clip_1.major = y1;
 192                 clip_1.minor = x1;
 193                 clip_2.major = y2;
 194                 clip_2.minor = x2;
 195                 clip_1.sign_major = signdy;
 196                 clip_1.sign_minor = signdx;
 197                 c.maj1 = b->y1;
 198                 c.maj2 = b->y2;
 199                 c.min1 = b->x1;
 200                 c.min2 = b->x2;
 201         }
 202
 203         e3 = e2 - e1;
 204         e = e - e1;
 205
 206         clip_1.first = true;
 207         clip_2.first = false;
 208         clip_2.e = clip_1.e = e;
 209         clip_2.e1 = clip_1.e1 = e1;
 210         clip_2.e3 = clip_1.e3 = e3;
 211         clip_2.sign_major = -clip_1.sign_major;
 212         clip_2.sign_minor = -clip_1.sign_minor;
 213
 214         printf ("clip start:\n");
 215         if (!clip(&clip_1, &c))
 216                 clipped = true;
 217
 218         printf("clip end:\n");
 219         if (!clip(&clip_2, &c))
 220                 clipped = true;
 221
 222         int     clip_len;
 223         int     clip_x, clip_y;
 224         int     clip_e;
 225         int     x_major, x_minor;
 226         int     y_major, y_minor;
 227
 228         clip_len = clip_1.sign_major * (clip_2.major - clip_1.major);
 229         if (clip_len < 0)
 230                 clipped = true;
 231
 232         int x, y;
 233
 234         if (axis == X_AXIS) {
 235                 x = clip_1.major;
 236                 y = clip_1.minor;
 237                 x_major = clip_1.sign_major;
 238                 x_minor = 0;
 239                 y_major = 0;
 240                 y_minor = clip_1.sign_minor;
 241         } else {
 242                 x = clip_1.minor;
 243                 y = clip_1.major;
 244                 x_major = 0;
 245                 x_minor = clip_1.sign_minor;
 246                 y_major = clip_1.sign_major;
 247                 y_minor = 0;
 248         }
 249
 250         clip_e = clip_1.e;
 251
 252         if (clipped)
 253                 clip_len = -1;
 254
 255         while (clip_len-- >= 0) {
 256                 t.clipped[dim(t.clipped)] = (point) { .x = x, .y = y };
 257                 x += x_major;
 258                 y += y_major;
 259                 clip_e += e1;
 260                 if (clip_e >= 0) {
 261                         x += x_minor;
 262                         y += y_minor;
 263                         clip_e += e3;
 264                 }
 265         }
 266
 267         x = x1;
 268         y = y1;
 269
 270         while (len-- >= 0) {
 271                 if (bounds.x1 <= x && x < bounds.x2 &&
 272                     bounds.y1 <= y && y < bounds.y2) {
 273                         t.run[dim(t.run)] = (point) { .x = x, .y = y };
 274                 }
 275                 x += x_major;
 276                 y += y_major;
 277                 e += e1;
 278                 if (e >= 0) {
 279                         x += x_minor;
 280                         y += y_minor;
 281                         e += e3;
 282                 }
 283         }
 284         return t;
 285 }
 286
 287 void read_events (Cairo::cairo_t cr)
 288 {
 289         file    event = Cairo::open_event(cr);
 290
 291         while (!File::end(event)) {
 292                 string  event_line = File::fgets(event);
 293                 if (String::index(event_line, "delete") >= 0)
 294                         exit(0);
 295         }
 296 }
 297
 298 #for (int y = 0; y < 20; y++)
 299
 300 void
 301 show(cairo_t cr, test t)
 302 {
 303         rectangle(cr, 0, 0, 40, 40);
 304         set_source_rgba(cr, 1, 1, 1, 1);
 305         fill(cr);
 306
 307         set_source_rgba(cr, 0, 1, 0, .2);
 308         set_line_width(cr, 0.1);
 309         for (int x = 0; x < 40; x++) {
 310                 move_to(cr, 0, x);
 311                 line_to(cr, 40, x);
 312                 move_to(cr, x, 0);
 313                 line_to(cr, x, 40);
 314         }
 315         stroke(cr);
 316
 317         rectangle(cr, t.b.x1, t.b.y1, t.b.x2 - t.b.x1, t.b.y2 - t.b.y1);
 318         set_line_width(cr, 0.1);
 319         set_source_rgba(cr, 0, 0, 0, 1);
 320         stroke(cr);
 321
 322         move_to(cr, t.x1+.5, t.y1+.5);
 323         line_to(cr, t.x2+.5, t.y2+.5);
 324         move_to(cr, t.x2, t.y2);
 325         line_to(cr, t.x2+1, t.y2+1);
 326         move_to(cr, t.x2+1, t.y2);
 327         line_to(cr, t.x2, t.y2+1);
 328         stroke(cr);
 329
 330         void pixels(point[] pt) {
 331                 for (int i = 0; i < dim(pt); i++) {
 332                         rectangle(cr, pt[i].x, pt[i].y, 1, 1);
 333                 }
 334                 fill(cr);
 335         }
 336
 337         set_source_rgba(cr, 1, 0, 0, .5);
 338         pixels(t.clipped);
 339
 340         set_source_rgba(cr, 0, 0, 1, .5);
 341         pixels(t.run);
 342 }
 343
 344 bool
 345 compare(test t)
 346 {
 347         if (dim(t.clipped) != dim(t.run))
 348                 return false;
 349
 350         for (int i = 0; i < dim(t.clipped); i++)
 351                 if (t.clipped[i] != t.run[i])
 352                         return false;
 353         return true;
 354 }
 355
 356 void
 357 doit(int i)
 358 {
 359         int     n;
 360         *box    b = &bounds;
 361
 362         cairo_t cr = new(800, 800);
 363
 364         scale(cr, 20, 20);
 365
 366         for (;;) {
 367                 PRNG::srandom(i);
 368                 int     x1 = PRNG::randint(40);
 369                 int     x2 = PRNG::randint(40);
 370                 int     y1 = PRNG::randint(40);
 371                 int     y2 = PRNG::randint(40);
 372
 373                 test t = line (x1, y1, x2, y2, &bounds);
 374                 show(cr, t);
 375                 if (!compare(t)) {
 376                         printf("line %d -- %d x %d - %d x %d\n", i, x1, y1, x2, y2);
 377                         gets();
 378                 }
 379                 i++;
 380         }
 381
 382         read_events(cr);
 383 }
 384
 385 int i = 0;
 386 if (dim(argv) > 1)
 387         i = atoi(argv[1]);
 388
 389 doit(i);