lib/gfxpoly/active.c

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