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