lib/gfxpoly/active.c

   1 #include <stdlib.h>
   2 #include <memory.h>
   3 #include <math.h>
   4 #include "../q.h"
   5 #include "active.h"
   6
   7 actlist_t* actlist_new()
   8 {
   9     NEW(actlist_t, a);
  10     return a;
  11 }
  12 void actlist_destroy(actlist_t*a)
  13 {
  14     free(a);
  15 }
  16
  17 void actlist_dump(actlist_t*a, int32_t y)
  18 {
  19     segment_t*s = a->list;
  20     double lastx;
  21     char bad = 0;
  22     if(!s) fprintf(stderr, "(empty)\n");
  23     while(s) {
  24         if(y) {
  25             double x = ((double)s->delta.x*(y-s->a.y)/s->delta.y)+s->a.x;
  26             if(s!=a->list) {
  27                 if(lastx>x)
  28                     fprintf(stderr, "?%f<->%f? ", lastx, x);
  29             }
  30             lastx = x;
  31         }
  32         fprintf(stderr, "[%d]", s->nr);
  33         s = s->right;
  34         if(s) fprintf(stderr, " ");
  35         else fprintf(stderr, "\n");
  36     }
  37 }
  38 void actlist_verify(actlist_t*a, int32_t y)
  39 {
  40     segment_t*s = a->list;
  41     assert(!s || !s->left);
  42     segment_t*l = 0;
  43     while(s) {
  44         if(y) {
  45             if(l) {
  46                 /* we need to re-evaluate the x of the previous segment. if we
  47                    try to store it, it might end up being converted to a double,
  48                    which will make it non-equal to (and possibly larger than) the
  49                    "long double" the FPU has in it's register. This only happens
  50                    when compiler optimizations are turned on. */
  51                 assert((XPOS(s, y) - XPOS(l, y)) >= 0);
  52                 assert(XDIFF(s,l,y) >= 0);
  53             }
  54             l = s;
  55         }
  56         assert(!s->left || s->left->right == s);
  57         assert(!s->right || s->right->left == s);
  58         s = s->right;
  59     }
  60 }
  61
  62 static inline double single_cmp(segment_t*s, point_t p1)
  63 {
  64     return LINE_EQ(p1, s);
  65 }
  66
  67 static inline double cmp(segment_t*s, point_t p1, point_t p2)
  68 {
  69     double d = LINE_EQ(p1, s);
  70     if(d==0) {
  71         d = LINE_EQ(p2, s);
  72         if(d==0) {
  73             /* We default to always inserting the new segment to the right of the old segment.
  74                We do this so that we don't place new segments into the middle of already
  75                overlapping lines which may have intersections scheduled.
  76              */
  77             //fprintf(stderr, "Notice: actlist_find: both points (%d,%d) and (%d,%d) exactly on segment [%d]\n", p1.x, p1.y, p2.x, p2.y, s->nr);
  78         }
  79     }
  80     return d;
  81 }
  82
  83 #ifdef SPLAY
  84 static void actlist_splay_dump(actlist_t*a);
  85 segment_t* actlist_find(actlist_t*a, point_t p1, point_t p2)
  86 {
  87 #ifdef CHECKS
  88     segment_t*t = a->list;
  89     char to_the_left = 0;
  90     char fail = 0;
  91     while(t) {
  92         /* this check doesn't work out with cmp() because during horizontal
  93            processing, both segments ending as well as segments starting will
  94            be active in this scanline */
  95         //double d = cmp(t, p1, p2);
  96         double d = single_cmp(t, p1);
  97         if(d>=0 && to_the_left) {
  98             segment_t*s = a->list;
  99             while(s) {
 100                 fprintf(stderr, "[%d] %f/%f (%d,%d) -> (%d,%d)\n", s->nr,
 101                         single_cmp(s,p1), cmp(s,p1,p2),
 102                         s->a.x, s->a.y, s->b.x, s->b.y);
 103                 s = s->right;
 104             }
 105         }
 106         assert(!(d>=0 && to_the_left));
 107         if(d<0) to_the_left=1;
 108         t = t->right;
 109     }
 110 #if 0
 111     if(a->size > 100) {
 112         static actlist_t*last = 0;
 113         if(last != a) {
 114             last = a;
 115             actlist_splay_dump(a);
 116         }
 117     }
 118 #endif
 119 #endif
 120     segment_t*last=0, *s = a->root;
 121     if(!s) return 0;
 122     double d=0;
 123     int depth = 0;
 124     while(s) {
 125         last = s;
 126         depth++;
 127         d = single_cmp(s, p1);
 128         if(d<=0) {
 129             s = s->leftchild;
 130         } else {
 131             s = s->rightchild;
 132         }
 133     }
 134 //#ifdef DEBUG
 135 #if 0
 136     if(a->size > 1) {
 137         /* 80% hit, average cost per miss ~ 4 nodes */
 138         int expected_depth = (int)((double)log2((double)a->size+1))+1;
 139         static int hits = 0;
 140         static int misses = 0;
 141         static int miss_cost = 0;
 142         if(depth <= expected_depth) hits++;
 143         else {misses++;
 144             miss_cost += depth - expected_depth;
 145         }
 146         if(hits && misses)
 147             fprintf(stderr, "%02.2f%% %f\n", hits / (double)(hits+misses), miss_cost / (double)misses);
 148     }
 149 #endif
 150
 151     segment_t*out = last;
 152     if(d<0 || (d==0 && LINE_EQ(p2,last)<0)) {
 153         last = last->left;
 154         if(!last) {
 155             assert(cmp(a->list, p1, p2)<0);
 156             return 0;
 157         }
 158     } else {
 159         while(last->right && cmp(last->right, p1, p2)>=0) {
 160             last = last->right;
 161         }
 162     }
 163
 164 #ifdef CHECKS
 165     segment_t*l=0;
 166     s = a->list;
 167     while(s) {
 168         if(cmp(s, p1, p2)<0)
 169             break;
 170         l = s;s = s->right;
 171     }
 172     if(l!=last) {
 173         printf("[%d]!=[%d]\n", SEGNR(l), SEGNR(last));
 174         printf("after tree: [%d]\n", SEGNR(out));
 175         actlist_splay_dump(a);
 176         s = a->list;
 177         while(s) {
 178             double d1 = single_cmp(s,p1);
 179             double d2 = cmp(s,p1,p2);
 180             int x1 = d1<0?-1:(d1>0?1:0);
 181             int x2 = d2<0?-1:(d2>0?1:0);
 182             printf("[%d](%d,%d) ", SEGNR(s), x1, x2);
 183             s = s->right;
 184         }
 185         printf("\n");
 186     }
 187     assert(l == last);
 188 #endif
 189
 190     return last;
 191 }
 192 #else
 193 segment_t* actlist_find(actlist_t*a, point_t p1, point_t p2)
 194 {
 195     segment_t*last=0, *s = a->list;
 196     if(!s) return last;
 197     while(s) {
 198         double d = cmp(s, p1, p2);
 199         if(d<0)
 200             break;
 201         last = s;
 202         s = s->right;
 203     }
 204     return last;
 205 }
 206 #endif
 207
 208 #ifdef SPLAY
 209
 210 #define LINK(node,side,child) (node)->side = (child);if(child) {(child)->parent = (node);}
 211  //;fprintf(stderr, "[%d]->%s now [%d]\n", SEGNR(node), __STRING(side), SEGNR(child));
 212
 213 // rotates segment's left node to the top
 214 static inline segment_t*rotate_right(actlist_t*a, segment_t*s)
 215 {
 216     /*      s             n
 217            /               \
 218           n      ->         s
 219            \               /
 220             l             l
 221     */
 222     assert(s->leftchild);
 223     segment_t*p = s->parent;
 224     segment_t*n = s->leftchild;
 225     segment_t*l = n->rightchild;
 226     LINK(n,rightchild,s);
 227     LINK(s,leftchild,l);
 228     n->parent = p;
 229     if(p) {
 230         if(p->leftchild == s)
 231             p->leftchild = n;
 232         else if(p->rightchild == s)
 233             p->rightchild = n;
 234     } else {
 235         a->root = n;
 236     }
 237     return n;
 238 }
 239 // rotates segment's right node to the top
 240 static inline segment_t*rotate_left(actlist_t*a, segment_t*s)
 241 {
 242     /*      s             n
 243              \           /
 244               n  ->     s
 245              /           \
 246             r             r
 247     */
 248     assert(s->rightchild);
 249     segment_t*p = s->parent;
 250     segment_t*n = s->rightchild;
 251     segment_t*r = n->leftchild;
 252     LINK(n,leftchild,s);
 253     LINK(s,rightchild,r);
 254     n->parent = p;
 255     if(p) {
 256         if(p->leftchild == s)
 257             p->leftchild = n;
 258         else if(p->rightchild == s)
 259             p->rightchild = n;
 260     } else {
 261         a->root = n;
 262     }
 263     return n;
 264 }
 265
 266 static int actlist_splay_walk(actlist_t*a, segment_t*s, segment_t**ss, segment_t*parent)
 267 {
 268     if(!s) return 1;
 269     if(parent != s->parent) {
 270         fprintf(stderr, "Parent mismatch in [%d]: [%d] != [%d]\n", SEGNR(s), SEGNR(parent), SEGNR(s->parent));
 271         return 0;
 272     }
 273     if(!actlist_splay_walk(a, s->leftchild, ss, s)) return 0;
 274     if(s != *ss) {
 275         fprintf(stderr, "[%d] != [%d]\n", SEGNR(s), SEGNR(*ss));
 276         return 0;
 277     }
 278     (*ss) = (*ss)->right;
 279     if(!actlist_splay_walk(a, s->rightchild, ss, s)) return 0;
 280     return 1;
 281 }
 282
 283 static int actlist_splay_verify(actlist_t*a)
 284 {
 285     segment_t*c = a->list;
 286     if(!actlist_splay_walk(a, a->root, &c, 0)) return 0;
 287     if(c) return 0;
 288     return 1;
 289 }
 290 static void actlist_splay_dump2(actlist_t*a, segment_t*s, char*mid, char*up, char*down)
 291 {
 292     if(!s) return;
 293
 294     if(s->leftchild || s->rightchild) {
 295         int t;
 296
 297         if(s->leftchild) {
 298             char*o3 = malloc(strlen(up)+3);
 299             strcpy(o3, up);strcat(o3, "+-");
 300             char*newup = malloc(strlen(up)+3);
 301             strcpy(newup, up);strcat(newup, "| ");
 302             char*newup2 = malloc(strlen(up)+3);
 303             strcpy(newup2, up);strcat(newup2, "  ");
 304             actlist_splay_dump2(a, s->leftchild, o3, newup2, newup);
 305             fprintf(stderr, "%s| \n", up);
 306             free(newup);
 307             free(newup2);
 308             free(o3);
 309         }
 310         fprintf(stderr, "%s[%d]\n", mid, SEGNR(s));
 311         if(s->rightchild) {
 312             char*o3 = malloc(strlen(down)+3);
 313             strcpy(o3, down);strcat(o3, "+-");
 314             char*newdown = malloc(strlen(down)+3);
 315             strcpy(newdown, down);strcat(newdown, "| ");
 316             char*newdown2 = malloc(strlen(down)+3);
 317             strcpy(newdown2, down);strcat(newdown2, "  ");
 318             fprintf(stderr, "%s| \n", down);
 319             actlist_splay_dump2(a, s->rightchild, o3, newdown, newdown2);
 320             free(newdown);
 321             free(newdown2);
 322             free(o3);
 323         }
 324     } else {
 325         fprintf(stderr, "%s[%d]\n", mid, SEGNR(s));
 326     }
 327 }
 328 static void actlist_splay_dump(actlist_t*a)
 329 {
 330     actlist_splay_dump2(a, a->root, "", "", "");
 331 }
 332
 333
 334 static void move_to_root(actlist_t*a, segment_t*s)
 335 {
 336     if(!s) return;
 337     /* this is a textbook implementation of the three splay operations
 338        zig, zig-zig and zig-zag */
 339     int nr=0;
 340     while(a->root != s) {
 341         assert(s->parent);
 342         segment_t*p = s->parent;
 343         if(p == a->root) {
 344             // zig
 345             if(a->root->leftchild == s) {
 346                 rotate_right(a, a->root);
 347             } else {
 348                 rotate_left(a, a->root);
 349             }
 350             assert(a->root == s);
 351         } else {
 352             segment_t*pp = p->parent;
 353             if(p->leftchild == s && pp->leftchild == p) {
 354                 // zig-zig (left)
 355                 rotate_right(a, pp);
 356                 rotate_right(a, s->parent);
 357             } else if(p->rightchild == s && pp->rightchild == p) {
 358                 // zig-zig (right)
 359                 rotate_left(a, pp);
 360                 rotate_left(a, s->parent);
 361             } else if(p->leftchild == s && pp->rightchild == p) {
 362                 // zig-zag (left)
 363                 rotate_right(a, p);
 364                 rotate_left(a, s->parent);
 365             } else if(p->rightchild == s && pp->leftchild == p) {
 366                 // zig-zag (right)
 367                 rotate_left(a, p);
 368                 rotate_right(a, s->parent);
 369             } else {
 370                 assert(0);
 371             }
 372         }
 373     }
 374 }
 375
 376 static int actlist_splay(actlist_t*a, point_t p1, point_t p2)
 377 {
 378     if(!a->list) return;
 379
 380     segment_t tmp;
 381     memset(&tmp, 0, sizeof(tmp));
 382     segment_t*left=&tmp,*right=&tmp;
 383
 384     int c = 0;
 385     while(1) {
 386         if(cmp(a->root,p1,p2)<0) {
 387             /* we're to the left of the root */
 388             if(!a->root->leftchild) {
 389                 c = -1;break;
 390             }
 391             if(cmp(a->root->leftchild,p1,p2)<0) {
 392                 /* we're also to the left of the root's left child
 393                    -> rotate right, so that the left child is root */
 394                 segment_t*s = a->root->leftchild;
 395                 LINK(a->root, leftchild, s->rightchild);
 396                 LINK(s, rightchild, a->root);
 397                 a->root = s;
 398                 if(!a->root->leftchild) {
 399                     c = -1;break;
 400                 }
 401             }
 402             LINK(right, leftchild, a->root);
 403             right = a->root;
 404             a->root = a->root->leftchild;
 405         } else /* cmp(a->root,p1,p2)>=0 */ {
 406             /* we're to the right of the root */
 407             if(!a->root->rightchild) {
 408                 c = 1;break;
 409             }
 410             if(cmp(a->root->rightchild,p1,p2)>=0) {
 411                 /* we're also to the right of the root's right child
 412                    -> rotate left, so that the right child is root */
 413                 segment_t*s = a->root->rightchild;
 414                 LINK(a->root, rightchild, s->leftchild);
 415                 LINK(s, leftchild, a->root);
 416                 a->root = s;
 417                 if(!a->root->rightchild)
 418                     c = 1;break;
 419             }
 420             LINK(left, rightchild, a->root);
 421             left = a->root;
 422             a->root = a->root->rightchild;
 423         }
 424     }
 425     LINK(left, rightchild, a->root->leftchild);
 426     LINK(right, leftchild, a->root->rightchild);
 427     LINK(a->root, leftchild, tmp.rightchild);
 428     LINK(a->root, rightchild, tmp.leftchild);
 429     a->root->parent = 0;
 430 }
 431
 432 #endif
 433
 434 static void actlist_insert_after(actlist_t*a, segment_t*left, segment_t*s)
 435 {
 436 #ifdef SPLAY
 437     //fprintf(stderr, "insert [%d] after [%d]\n", SEGNR(s), SEGNR(left));
 438     //actlist_splay_dump(a);
 439     //actlist_dump(a, s->a.y);
 440 #endif
 441
 442     s->left = left;
 443     if(left) {
 444         s->right = left->right;
 445     } else {
 446         s->right = a->list;
 447         a->list = s;
 448     }
 449     if(s->left)
 450         s->left->right = s;
 451     if(s->right)
 452         s->right->left = s;
 453
 454 #ifdef SPLAY
 455     // we insert nodes not trees
 456     assert(!s->leftchild);
 457     assert(!s->rightchild);
 458
 459     if(a->root) {
 460         move_to_root(a, left);
 461         if(left) {
 462             LINK(s,leftchild,a->root);
 463             // steal right child from (previous) root
 464             LINK(s,rightchild,a->root->rightchild);
 465             a->root->rightchild = 0;
 466         } else {
 467             LINK(s,rightchild,a->root);
 468         }
 469     }
 470     a->root = s;
 471     a->root->parent = 0;
 472
 473     assert(actlist_splay_verify(a));
 474 #endif
 475
 476     a->size++;
 477 }
 478
 479 void actlist_delete(actlist_t*a, segment_t*s)
 480 {
 481 #ifdef SPLAY
 482     assert(actlist_splay_verify(a));
 483     move_to_root(a, s);
 484     assert(actlist_splay_verify(a));
 485 #endif
 486     if(s->left) {
 487         s->left->right = s->right;
 488     } else {
 489         a->list = s->right;
 490     }
 491     if(s->right) {
 492         s->right->left = s->left;
 493     }
 494     s->left = s->right = 0;
 495     a->size--;
 496 #ifdef SPLAY
 497     assert(a->root == s);
 498     // delete root node
 499     if(!a->root->leftchild) {
 500         a->root = a->root->rightchild;
 501     } else if(!a->root->rightchild) {
 502         a->root = a->root->leftchild;
 503     } else {
 504         if(lrand48()&1) {
 505             // free up root->left->right
 506             segment_t*t = a->root->leftchild;
 507             while(t->rightchild) {
 508                 segment_t*r = t->rightchild;
 509                 segment_t*l = r->leftchild;
 510                 LINK(r, leftchild, t);
 511                 LINK(t, rightchild, l);
 512                 t = r;
 513             }
 514             LINK(a->root,leftchild,t);
 515             assert(!a->root->leftchild->rightchild);
 516             LINK(a->root->leftchild,rightchild,a->root->rightchild);
 517             a->root = a->root->leftchild;
 518         } else {
 519             // free up root->right->left
 520             segment_t*t = a->root->rightchild;
 521             while(t->leftchild) {
 522                 segment_t*l = t->leftchild;
 523                 segment_t*r = l->rightchild;
 524                 LINK(l, rightchild, t);
 525                 LINK(t, leftchild, r);
 526                 t = l;
 527             }
 528             LINK(a->root,rightchild,t);
 529             assert(!a->root->rightchild->leftchild);
 530             LINK(a->root->rightchild,leftchild,a->root->leftchild);
 531             a->root = a->root->rightchild;
 532         }
 533     }
 534     if(a->root)
 535         a->root->parent = 0;
 536     s->leftchild = s->rightchild = s->parent = 0;
 537
 538     assert(actlist_splay_verify(a));
 539 #endif
 540 }
 541 int actlist_size(actlist_t*a)
 542 {
 543     return a->size;
 544 }
 545
 546 segment_t* actlist_leftmost(actlist_t*a)
 547 {
 548     return a->list;
 549 }
 550
 551 segment_t* actlist_rightmost(actlist_t*a)
 552 {
 553     /* this is only used in checks, so it doesn't matter that it's slow */
 554 #ifndef CHECKS
 555     fprintf(stderr, "Warning: actlist_rightmost should not be used\n");
 556 #endif
 557     segment_t*s = a->list;
 558     segment_t*last = 0;
 559     while(s) {
 560         last = s;
 561         s = s->right;
 562     }
 563     return last;
 564 }
 565
 566 void actlist_insert(actlist_t*a, point_t p1, point_t p2, segment_t*s)
 567 {
 568     segment_t*left = actlist_find(a, p1, p2);
 569     actlist_insert_after(a, left, s);
 570 }
 571
 572 void actlist_swap(actlist_t*a, segment_t*s1, segment_t*s2)
 573 {
 574 #ifdef SPLAY
 575     assert(actlist_splay_verify(a));
 576 #endif
 577 #ifdef CHECKS
 578     /* test that s1 is to the left of s2- our swap
 579        code depends on that */
 580     segment_t*s = s1;
 581     while(s && s!=s2) s = s->right;
 582     assert(s==s2);
 583 #endif
 584 /*#ifndef SPLAY
 585     actlist_delete(a, s1);
 586     actlist_insert_after(a, s2, s1);
 587 #else*/
 588     segment_t*s1l = s1->left;
 589     segment_t*s1r = s1->right;
 590     segment_t*s2l = s2->left;
 591     segment_t*s2r = s2->right;
 592     if(s1l) s1l->right = s2;
 593     else    a->list = s2;
 594     s2->left = s1l;
 595     if(s2r) s2r->left = s1;
 596     s1->right = s2r;
 597     if(s2l!=s1) s1->left = s2l;
 598     else        s1->left = s2;
 599     if(s1r!=s2) s2->right = s1r;
 600     else        s2->right = s1;
 601
 602 #ifdef SPLAY
 603     if(s2->parent==s1) {
 604         /*
 605              s1            s2
 606             /      ->     /
 607           s2            s1
 608         */
 609         segment_t*l = s2->leftchild;
 610         segment_t*r = s2->rightchild;
 611         assert(s1->rightchild == s2); // because s1 < s2
 612         segment_t*l1 = s1->leftchild;
 613         segment_t*p = s1->parent;
 614         s1->parent = s2;
 615         s2->parent = p;
 616         if(p) {
 617             if(p->leftchild == s1) p->leftchild=s2;
 618             else {assert(p->rightchild == s1);p->rightchild=s2;}
 619         } else {
 620             a->root = s2;
 621         }
 622         s2->leftchild = l1;
 623         s2->rightchild = s1;
 624         s1->leftchild = l;
 625         s1->rightchild = r;
 626     } else if(s1->parent==s2) {
 627         /*
 628              s2            s1
 629             /      ->     /
 630           s1            s2
 631         */
 632         segment_t*l = s1->leftchild;
 633         segment_t*r = s1->rightchild;
 634         segment_t*r2 = s2->rightchild;
 635         assert(s2->leftchild == s1); // because s1 < s2
 636         segment_t*p = s2->parent;
 637         s2->parent = s1;
 638         s1->parent = p;
 639         if(p) {
 640             if(p->leftchild == s2) p->leftchild=s1;
 641             else {assert(p->rightchild == s2);p->rightchild=s1;}
 642         } else {
 643             a->root = s1;
 644         }
 645         s1->leftchild = s2;
 646         s1->rightchild = r2;
 647         s2->leftchild = l;
 648         s2->rightchild = r;
 649     } else {
 650         segment_t*s1p = s1->parent;
 651         segment_t*s1l = s1->leftchild;
 652         segment_t*s1r = s1->rightchild;
 653         segment_t*s2p = s2->parent;
 654         segment_t*s2l = s2->leftchild;
 655         segment_t*s2r = s2->rightchild;
 656         s2->parent = s1p;
 657         s2->leftchild = s1l;
 658         s2->rightchild = s1r;
 659         s1->parent = s2p;
 660         s1->leftchild = s2l;
 661         s1->rightchild = s2r;
 662         assert(s1p || s2p);
 663         if(s1p) {
 664             if(s1p->leftchild == s1) s1p->leftchild=s2;
 665             else {assert(s1p->rightchild == s1);s1p->rightchild=s2;}
 666         } else {
 667             a->root = s2;
 668         }
 669         if(s2p) {
 670             if(s2p->leftchild == s2) s2p->leftchild=s1;
 671             else {assert(s2p->rightchild == s2);s2p->rightchild=s1;}
 672         } else {
 673             a->root = s1;
 674         }
 675     }
 676     if(s1->leftchild) s1->leftchild->parent = s1;
 677     if(s2->leftchild) s2->leftchild->parent = s2;
 678     if(s1->rightchild) s1->rightchild->parent = s1;
 679     if(s2->rightchild) s2->rightchild->parent = s2;
 680
 681     assert(actlist_splay_verify(a));
 682 #endif
 683
 684 //#endif
 685 }