lib/gfxpoly/poly.c

   1 #include <stdlib.h>
   2 #include <assert.h>
   3 #include <memory.h>
   4 #include <math.h>
   5 #include "../mem.h"
   6 #include "../q.h"
   7 #include "poly.h"
   8 #include "active.h"
   9 #include "xrow.h"
  10
  11 //#define DEBUG
  12 //#undef assert
  13 //#define assert(x)
  14
  15 char point_equals(const void*o1, const void*o2)
  16 {
  17     const point_t*p1 = o1;
  18     const point_t*p2 = o2;
  19     return p1->x == p2->x && p1->y == p2->y;
  20 }
  21 unsigned int point_hash(const void*o)
  22 {
  23     const point_t*p = o;
  24     return p->x^p->y;
  25 }
  26 void* point_dup(const void*o)
  27 {
  28     const point_t*p = o;
  29     point_t*n = malloc(sizeof(point_t));
  30     n->x = p->x;
  31     n->y = p->y;
  32     return n;
  33 }
  34 void point_free(void*o)
  35 {
  36     point_t*p = o;
  37     p->x = 0;
  38     p->y = 0;
  39     free(p);
  40 }
  41 type_t point_type = {
  42     equals: point_equals,
  43     hash: point_hash,
  44     dup: point_dup,
  45     free: point_free,
  46 };
  47
  48 typedef struct _status {
  49     int y;
  50     actlist_t*actlist;
  51     heap_t*queue;
  52     edge_t*output;
  53 #ifdef DEBUG
  54     dict_t*seen_crossings; //list of crossing we saw so far
  55     dict_t*intersecting_segs; //list of segments intersecting in this scanline
  56     dict_t*segs_with_point; //lists of segments that received a point in this scanline
  57 #endif
  58 } status_t;
  59
  60 int compare_events(const void*_a,const void*_b)
  61 {
  62     event_t* a = (event_t*)_a;
  63     event_t* b = (event_t*)_b;
  64     if(a->p.y < b->p.y) {
  65         return 1;
  66     } else if(a->p.y > b->p.y) {
  67         return -1;
  68     /* we should schedule start events after end/intersect.
  69        The order of end/intersect doesn't actually matter, however,
  70        so this might be doing too much */
  71     } else if(a->type < b->type) {
  72         return 1;
  73     } else if(a->type > b->type) {
  74         return -1;
  75     } else if(a->p.x < b->p.x) {
  76         return 1;
  77     } else if(a->p.x > b->p.x) {
  78         return -1;
  79     } else
  80         return 0;
  81 }
  82
  83 gfxpoly_t* gfxpoly_new()
  84 {
  85     return 0;
  86 }
  87 void gfxpoly_destroy(gfxpoly_t*poly)
  88 {
  89     edge_t* s = poly;
  90     while(s) {
  91         edge_t*next  = s->next;
  92         free(s);
  93         s = next;
  94     }
  95 }
  96
  97 void gfxpoly_dump(gfxpoly_t*poly)
  98 {
  99     edge_t* s = (edge_t*)poly;
 100     while(s) {
 101         fprintf(stderr, "(%d,%d) -> (%d,%d)\n", s->a.x, s->a.y, s->b.x, s->b.y);
 102         s = s->next;
 103     }
 104 }
 105
 106 inline static event_t event_new()
 107 {
 108     event_t e;
 109     memset(&e, 0, sizeof(e));
 110     return e;
 111 }
 112
 113 void event_dump(event_t*e)
 114 {
 115     if(e->type == EVENT_START) {
 116         fprintf(stderr, "event: segment [%d] starts at (%d,%d)\n", e->s1->nr, e->p.x, e->p.y);
 117     } else if(e->type == EVENT_END) {
 118         fprintf(stderr, "event: segment [%d] ends at (%d,%d)\n", e->s1->nr, e->p.x, e->p.y);
 119     } else if(e->type == EVENT_CROSS) {
 120         fprintf(stderr, "event: segment [%d] and [%d] intersect at (%d,%d)\n", e->s1->nr, e->s2->nr, e->p.x, e->p.y);
 121     } else {
 122         assert(0);
 123     }
 124 }
 125
 126 static inline max32(int32_t v1, int32_t v2) {return v1>v2?v1:v2;}
 127 static inline min32(int32_t v1, int32_t v2) {return v1<v2?v1:v2;}
 128
 129 void segment_init(segment_t*s, int x1, int y1, int x2, int y2)
 130 {
 131     assert(y1!=y2);
 132     if(y1<y2) {
 133         s->dir = DIR_DOWN;
 134     } else {
 135         int x = x1;x1=x2;x2=x;
 136         int y = y1;y1=y2;y2=y;
 137         s->dir = DIR_UP;
 138     }
 139     s->a.x = x1;
 140     s->a.y = y1;
 141     s->b.x = x2;
 142     s->b.y = y2;
 143     s->k = (double)x1*y2-(double)x2*y1;
 144     s->left = s->right = 0;
 145     s->delta.x = x2-x1;
 146     s->delta.y = y2-y1;
 147     s->pos = s->a;
 148     s->tmp = -1;
 149 #ifdef DEBUG
 150     static int segment_count=0; //for debugging
 151     s->nr = segment_count++;
 152 #endif
 153
 154     assert(LINE_EQ(s->a, s) == 0);
 155     assert(LINE_EQ(s->b, s) == 0);
 156
 157     /* check that all signs are in order:
 158        a        a
 159        |\      /|
 160        | \    / |
 161      minx-b  b--maxx
 162      < 0        > 0
 163     */
 164     point_t p = s->b;
 165     p.x = min32(s->a.x, s->b.x);
 166     assert(LINE_EQ(p, s) <= 0);
 167     p.x = max32(s->a.x, s->b.x);
 168     assert(LINE_EQ(p, s) >= 0);
 169
 170     dict_init2(&s->scheduled_crossings, &ptr_type, 0);
 171 }
 172
 173 segment_t* segment_new(int32_t x1, int32_t y1, int32_t x2, int32_t y2)
 174 {
 175     segment_t*s = (segment_t*)rfx_calloc(sizeof(segment_t));
 176     segment_init(s, x1, y1, x2, y2);
 177     return s;
 178 }
 179 void segment_destroy(segment_t*s)
 180 {
 181     dict_clear(&s->scheduled_crossings);
 182     free(s);
 183 }
 184
 185 void gfxpoly_enqueue(edge_t*list, heap_t*queue)
 186 {
 187     edge_t*l = list;
 188     while(l) {
 189         segment_t*s = segment_new(l->a.x, l->a.y, l->b.x, l->b.y);
 190 #ifdef DEBUG
 191         fprintf(stderr, "[%d] (%d,%d) -> (%d,%d) %s\n",
 192                 s->nr, s->a.x, s->a.y, s->b.x, s->b.y,
 193                 s->dir==DIR_UP?"up":"down");
 194 #endif
 195         event_t e = event_new();
 196         e.type = EVENT_START;
 197         e.p = s->a;
 198         e.s1 = s;
 199         e.s2 = 0;
 200         heap_put(queue, &e);
 201         l = l->next;
 202     }
 203 }
 204
 205 void schedule_endpoint(status_t*status, segment_t*s)
 206 {
 207     // schedule end point of segment
 208     assert(s->b.y > status->y);
 209     event_t e;
 210     e.type = EVENT_END;
 211     e.p = s->b;
 212     e.s1 = s;
 213     e.s2 = 0;
 214     heap_put(status->queue, &e);
 215 }
 216
 217 void schedule_crossing(status_t*status, segment_t*s1, segment_t*s2)
 218 {
 219     /* the code that's required (and the checks you can perform) before
 220        it can be said with 100% certainty that we indeed have a valid crossing
 221        amazes me every time. -mk */
 222     assert(s1!=s2);
 223
 224     /* we probably could precompute these */
 225     int32_t minx1 = min32(s1->a.x,s1->b.x);
 226     int32_t miny1 = min32(s1->a.y,s1->b.y);
 227     int32_t maxx1 = max32(s1->a.x,s1->b.x);
 228     int32_t maxy1 = max32(s1->a.y,s1->b.y);
 229     int32_t minx2 = min32(s2->a.x,s2->b.x);
 230     int32_t miny2 = min32(s2->a.y,s2->b.y);
 231     int32_t maxx2 = max32(s2->a.x,s2->b.x);
 232     int32_t maxy2 = max32(s2->a.y,s2->b.y);
 233
 234     /* both segments are active, so this can't happen */
 235     assert(!(maxy1 <= miny2 || maxy2 <= miny1));
 236
 237     /* TODO: optimize this. remove y, precompute the two x values */
 238     if(maxx1 <= minx2 || maxx2 <= minx1 ||
 239        maxy1 <= miny2 || maxy2 <= miny1) {
 240         /* bounding boxes don't intersect */
 241         return;
 242     }
 243
 244     if(dict_contains(&s1->scheduled_crossings, s2)) {
 245         // we already know about this one
 246         return;
 247     }
 248
 249     double adx = s1->delta.x;
 250     double ady = s1->delta.y;
 251     double bdx = s2->delta.x;
 252     double bdy = s2->delta.y;
 253     double det = adx*bdy - ady*bdx;
 254     if(!det) {
 255         if(s1->k == s2->k) {
 256             // lines are exactly on top of each other (ignored)
 257 #ifdef DEBUG
 258             fprintf(stderr, "Notice: segments [%d] and [%d] are exactly on top of each other\n", s1->nr, s2->nr);
 259 #endif
 260             return;
 261         } else {
 262             /* lines are parallel */
 263             return;
 264         }
 265     }
 266     double asign2 = LINE_EQ(s1->a, s2);
 267     double bsign2 = LINE_EQ(s1->b, s2);
 268     if(asign2<0 && bsign2<0) {
 269         // segment1 is completely to the left of segment2
 270         return;
 271     }
 272     if(asign2>0 && bsign2>0)  {
 273         // segment2 is completely to the left of segment1
 274         return;
 275     }
 276     if(asign2==0) {
 277         // segment1 touches segment2 in a single point (ignored)
 278 #ifdef DEBUG
 279         fprintf(stderr, "Notice: segment [%d]'s start point touches segment [%d]\n", s1->nr, s2->nr);
 280 #endif
 281         return;
 282     }
 283     if(bsign2==0) {
 284         // segment1 touches segment2 in a single point (ignored)
 285 #ifdef DEBUG
 286         fprintf(stderr, "Notice: segment [%d]'s end point touches segment [%d]\n", s1->nr, s2->nr);
 287 #endif
 288         return;
 289     }
 290     double asign1 = LINE_EQ(s2->a, s1);
 291     double bsign1 = LINE_EQ(s2->b, s1);
 292     if(asign1<0 && bsign1<0) {
 293         // segment1 is completely to the left of segment2
 294         return;
 295     }
 296     if(asign1>0 && bsign1>0)  {
 297         // segment2 is completely to the left of segment1
 298         return;
 299     }
 300     if(asign1==0) {
 301         // segment2 touches segment1 in a single point (ignored)
 302 #ifdef DEBUG
 303         fprintf(stderr, "Notice: segment [%d]'s start point touches segment [%d]\n", s2->nr, s1->nr);
 304 #endif
 305         return;
 306     }
 307     if(asign2==0) {
 308         // segment2 touches segment1 in a single point (ignored)
 309 #ifdef DEBUG
 310         fprintf(stderr, "Notice: segment [%d]'s end point touches segment [%d]\n", s2->nr, s1->nr);
 311 #endif
 312         return;
 313     }
 314
 315     double la = (double)s1->a.x*(double)s1->b.y - (double)s1->a.y*(double)s1->b.x;
 316     double lb = (double)s2->a.x*(double)s2->b.y - (double)s2->a.y*(double)s2->b.x;
 317
 318     point_t p;
 319     p.x = (int32_t)ceil((-la*bdx +lb*adx) / det);
 320     p.y = (int32_t)ceil((+lb*ady -la*bdy) / det);
 321
 322     assert(p.y >= status->y);
 323 #ifdef DEBUG
 324     point_t pair;
 325     pair.x = s1->nr;
 326     pair.y = s2->nr;
 327     assert(!dict_contains(status->seen_crossings, &pair));
 328     dict_put(status->seen_crossings, &pair, 0);
 329     fprintf(stderr, "schedule crossing between [%d] and [%d] at (%d,%d)\n", s1->nr, s2->nr, p.x, p.y);
 330 #endif
 331
 332     /* we insert into each other's intersection history because these segments might switch
 333        places and we still want to look them up quickly after they did */
 334     dict_put(&s1->scheduled_crossings, s2, 0);
 335     dict_put(&s2->scheduled_crossings, s1, 0);
 336
 337     event_t e = event_new();
 338     e.type = EVENT_CROSS;
 339     e.p = p;
 340     e.s1 = s1;
 341     e.s2 = s2;
 342     heap_put(status->queue, &e);
 343     return;
 344 }
 345
 346 void exchange_two(status_t*status, event_t*e)
 347 {
 348     //exchange two segments in list
 349     segment_t*s1 = e->s1;
 350     segment_t*s2 = e->s2;
 351 #ifdef DEBUG
 352     if(!dict_contains(status->intersecting_segs, s1))
 353         dict_put(status->intersecting_segs, s1, 0);
 354     if(!dict_contains(status->intersecting_segs, s2))
 355         dict_put(status->intersecting_segs, s2, 0);
 356 #endif
 357     segment_t*left = actlist_left(status->actlist, s2);
 358     segment_t*right = actlist_right(status->actlist, s1);
 359     assert(left == s1);
 360     assert(right == s2);
 361     actlist_swap(status->actlist, s1, s2);
 362     assert(actlist_right(status->actlist, s2) == s1);
 363     assert(actlist_left(status->actlist, s1) == s2);
 364     left = actlist_left(status->actlist, s2);
 365     right = actlist_right(status->actlist, s1);
 366     if(left)
 367         schedule_crossing(status, left, s2);
 368     if(right)
 369         schedule_crossing(status, s1, right);
 370 }
 371
 372 void insert_point_into_segment(status_t*status, segment_t*s, point_t p)
 373 {
 374 #ifdef DEBUG
 375     if(s->pos.x == p.x && s->pos.y == p.y) {
 376         fprintf(stderr, "Error: tried to add (%d,%d) to segment [%d] twice\n", p.x, p.y, s->nr);
 377     }
 378 #endif
 379     assert(s->pos.x != p.x || s->pos.y != p.y);
 380 #ifdef DEBUG
 381     fprintf(stderr, "[%d] gets extra point (%d,%d)\n", s->nr, p.x, p.y);
 382 #endif
 383
 384     edge_t*e = malloc(sizeof(edge_t));
 385     e->a = s->pos;
 386     e->b = p;
 387     e->next = status->output;
 388     status->output = e;
 389
 390     s->pos = p;
 391 }
 392
 393 typedef struct _box {
 394     point_t left1, left2, right1, right2;
 395 } box_t;
 396 static inline box_t box_new(int x, int y)
 397 {
 398     box_t box;
 399     box.right1.x = box.right2.x = x;
 400     box.left1.x = box.left2.x = x-1;
 401     box.left1.y = box.right1.y = y-1;
 402     box.left2.y = box.right2.y = y;
 403     return box;
 404 }
 405
 406 /* possible optimizations:
 407    1.) keep two different active lists around, one for negative and one for
 408        positive slopes
 409    2.) delay starting events until after this function (tricky, because we *do*
 410        need the start coordinates)
 411 */
 412 /*
 413    SLOPE_POSITIVE:
 414        +     \ +
 415 ------ I      \I
 416       -I\----  I
 417        I \   --I\---
 418        I  \    I \  -------
 419        +   \   +  \
 420 */
 421 void add_points_to_positively_sloped_segments(status_t*status, xrow_t*xrow, int32_t y)
 422 {
 423     int t;
 424     for(t=0;t<xrow->num;t++) {
 425         box_t box = box_new(xrow->x[t], y);
 426         segment_t*seg = actlist_find(status->actlist, box.left2, box.left2);
 427         if(seg)
 428             seg = seg->right;
 429         else
 430             seg = actlist_leftmost(status->actlist);
 431         while(seg) {
 432             if(seg->a.y == y) {
 433                 // this segment just started, ignore it
 434             } else if(seg->delta.x < 0) {
 435                 // ignore segment w/ negative slope
 436             } else {
 437                 double d1 = LINE_EQ(box.right1, seg);
 438                 double d2 = LINE_EQ(box.right2, seg);
 439                 if(d1>=0 || d2>=0) {
 440 #ifdef DEBUG
 441                     dict_put(status->segs_with_point, seg, 0);
 442 #endif
 443                     insert_point_into_segment(status, seg, box.right2);
 444                 } else {
 445                     break;
 446                 }
 447             }
 448             seg = seg->right;
 449         }
 450     }
 451 }
 452 /* SLOPE_NEGATIVE:
 453    |   +   /|  +  /    /
 454    |   I  / |  I /    /
 455    |   I /  |  I/    /
 456    |   I/   |  I    /
 457    |   I    | /I   /
 458    |  /+    |/ +  /
 459 */
 460 void add_points_to_negatively_sloped_segments(status_t*status, xrow_t*xrow, int32_t y)
 461 {
 462     int t;
 463     for(t=xrow->num-1;t>=0;t--) {
 464         box_t box = box_new(xrow->x[t], y);
 465         segment_t*seg = actlist_find(status->actlist, box.right2, box.right2);
 466         while(seg) {
 467             if(seg->a.y == y) {
 468                 // this segment just started, ignore it
 469             } else if(seg->delta.x >= 0) {
 470                 // ignore segment w/ positive slope
 471             } else {
 472                 double d1 = LINE_EQ(box.left1, seg);
 473                 double d2 = LINE_EQ(box.left2, seg);
 474                 if(d1<0 || d2<0) {
 475 #ifdef DEBUG
 476                     dict_put(status->segs_with_point, seg, 0);
 477 #endif
 478                     insert_point_into_segment(status, seg, box.right2);
 479                 } else {
 480                     break;
 481                 }
 482             }
 483             seg = seg->left;
 484         }
 485     }
 486 }
 487
 488 void event_apply(status_t*status, event_t*e)
 489 {
 490     switch(e->type) {
 491         case EVENT_END: {
 492             //delete segment from list
 493             segment_t*s = e->s1;
 494 #ifdef DEBUG
 495             event_dump(e);
 496             dict_del(status->intersecting_segs, s);
 497             dict_del(status->segs_with_point, s);
 498             assert(!dict_contains(status->intersecting_segs, s));
 499             assert(!dict_contains(status->segs_with_point, s));
 500 #endif
 501             insert_point_into_segment(status, s, s->b);
 502             segment_t*left = actlist_left(status->actlist, s);
 503             segment_t*right = actlist_right(status->actlist, s);
 504             actlist_delete(status->actlist, s);
 505             if(left && right)
 506                 schedule_crossing(status, left, right);
 507             segment_destroy(s);e->s1=0;
 508             break;
 509         }
 510         case EVENT_START: {
 511             //insert segment into list
 512 #ifdef DEBUG
 513             event_dump(e);
 514 #endif
 515             segment_t*s = e->s1;
 516             actlist_insert(status->actlist, e->p, s);
 517             segment_t*left = actlist_left(status->actlist, s);
 518             segment_t*right = actlist_right(status->actlist, s);
 519             if(left)
 520                 schedule_crossing(status, left, s);
 521             if(right)
 522                 schedule_crossing(status, s, right);
 523
 524             schedule_endpoint(status, e->s1);
 525             break;
 526         }
 527         case EVENT_CROSS: {
 528             // exchange two (or more) segments
 529             if(actlist_right(status->actlist, e->s1) == e->s2 &&
 530                actlist_left(status->actlist, e->s2) == e->s1) {
 531                 exchange_two(status, e);
 532             } else {
 533                 /* ignore this crossing for now (there are some line segments in between).
 534                    it'll get rescheduled as soon as the "obstacles" are gone */
 535                 char del1 = dict_del(&e->s1->scheduled_crossings, e->s2);
 536                 char del2 = dict_del(&e->s2->scheduled_crossings, e->s1);
 537                 assert(del1 && del2);
 538 #ifdef DEBUG
 539                 point_t pair;
 540                 pair.x = e->s1->nr;
 541                 pair.y = e->s2->nr;
 542                 assert(dict_contains(status->seen_crossings, &pair));
 543                 dict_del(status->seen_crossings, &pair);
 544 #endif
 545             }
 546         }
 547     }
 548 }
 549
 550 #ifdef DEBUG
 551 void check_status(status_t*status)
 552 {
 553     DICT_ITERATE_KEY(status->intersecting_segs, segment_t*, s) {
 554         if((s->pos.x != s->b.x ||
 555             s->pos.y != s->b.y) &&
 556            !dict_contains(status->segs_with_point, s)) {
 557             fprintf(stderr, "Error: segment [%d] (%sslope) intersects in scanline %d, but it didn't receive a point\n",
 558                     s->nr,
 559                     s->delta.x<0?"-":"+",
 560                     status->y);
 561             assert(0);
 562         }
 563     }
 564 }
 565 #endif
 566
 567 edge_t* gfxpoly_process(edge_t*poly)
 568 {
 569     heap_t* queue = heap_new(sizeof(event_t), compare_events);
 570     gfxpoly_enqueue(poly, queue);
 571     status_t status;
 572     memset(&status, 0, sizeof(status_t));
 573     status.queue = queue;
 574     status.actlist = actlist_new();
 575 #ifdef DEBUG
 576     status.seen_crossings = dict_new2(&point_type);
 577     gfxpoly_dump(poly);
 578 #endif
 579
 580     xrow_t*xrow = xrow_new();
 581
 582     event_t*e = heap_chopmax(queue);
 583     while(e) {
 584         status.y = e->p.y;
 585 #ifdef DEBUG
 586         status.intersecting_segs = dict_new2(&ptr_type);
 587         status.segs_with_point = dict_new2(&ptr_type);
 588         fprintf(stderr, "----------------------------------- %d\n", status.y);
 589         actlist_verify_and_dump(status.actlist, status.y-1);
 590 #endif
 591         xrow_reset(xrow);
 592         do {
 593             xrow_add(xrow, e->p.x);
 594             event_apply(&status, e);
 595             free(e);
 596             e = heap_chopmax(queue);
 597         } while(e && status.y == e->p.y);
 598
 599         xrow_sort(xrow);
 600         add_points_to_positively_sloped_segments(&status, xrow, status.y);
 601         add_points_to_negatively_sloped_segments(&status, xrow, status.y);
 602 #ifdef DEBUG
 603         check_status(&status);
 604         dict_destroy(status.intersecting_segs);
 605         dict_destroy(status.segs_with_point);
 606 #endif
 607     }
 608 #ifdef DEBUG
 609     dict_destroy(status.seen_crossings);
 610 #endif
 611     actlist_destroy(status.actlist);
 612     heap_destroy(queue);
 613     xrow_destroy(xrow);
 614
 615     return status.output;
 616 }