lib/gfxpoly/active.c

   1 #include <memory.h>
   2 #include "../q.h"
   3 #include "active.h"
   4
   5 actlist_t* actlist_new()
   6 {
   7     NEW(actlist_t, a);
   8     return a;
   9 }
  10 void actlist_destroy(actlist_t*a)
  11 {
  12     free(a);
  13 }
  14
  15 void actlist_dump(actlist_t*a, int32_t y)
  16 {
  17     segment_t*s = a->list;
  18     double lastx;
  19     char bad = 0;
  20     while(s) {
  21         if(y) {
  22             double x = ((double)s->delta.x*(y-s->a.y)/s->delta.y)+s->a.x;
  23             if(s!=a->list) {
  24                 if(lastx>x)
  25                     fprintf(stderr, "?%f<->%f? ", lastx, x);
  26             }
  27             lastx = x;
  28         }
  29         fprintf(stderr, "[%d]", s->nr);
  30         s = s->right;
  31         if(s) fprintf(stderr, " ");
  32         else fprintf(stderr, "\n");
  33     }
  34 }
  35 void actlist_verify(actlist_t*a, int32_t y)
  36 {
  37     segment_t*s = a->list;
  38     assert(!s || !s->left);
  39     segment_t*l = 0;
  40     while(s) {
  41         if(y) {
  42             if(l) {
  43                 /* we need to re-evaluate the x of the previous segment. if we
  44                    try to store it, it might end up being converted to a double,
  45                    which will make it non-equal to (and possibly larger than) the
  46                    "long double" the FPU has in it's register. This only happens
  47                    when compiler optimizations are turned on. */
  48                 assert((XPOS(s, y) - XPOS(l, y)) >= 0);
  49                 assert(XDIFF(s,l,y) >= 0);
  50             }
  51             l = s;
  52         }
  53         assert(!s->left || s->left->right == s);
  54         assert(!s->right || s->right->left == s);
  55         s = s->right;
  56     }
  57 }
  58
  59 static inline double cmp(segment_t*s, point_t p1, point_t p2)
  60 {
  61     double d = LINE_EQ(p1, s);
  62     if(d==0) {
  63         d = LINE_EQ(p2, s);
  64         if(d==0) {
  65             /* We default to always inserting the new segment to the right of the old segment.
  66                We do this so that we don't place new segments into the middle of already
  67                overlapping lines which may have intersections scheduled.
  68              */
  69             //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);
  70         }
  71     }
  72     return d;
  73 }
  74
  75 segment_t* actlist_find(actlist_t*a, point_t p1, point_t p2)
  76 {
  77     /* this runs in O(n) right now, and should be optimized using a splay
  78        tree to run in ammortized O(log(n))
  79        (update: currently only 2.5% of the algorithm's running time is spent here,
  80         so maybe we don't need to bother)
  81      */
  82     segment_t*last=0, *s = a->list;
  83     if(!s) return last;
  84     while(s) {
  85         double d = cmp(s, p1, p2);
  86         if(d<0)
  87             break;
  88         last = s;
  89         s = s->right;
  90     }
  91     return last;
  92 }
  93
  94 #ifdef SPLAY
  95
  96 #define LINK(node,side,child) (node)->side = (child);if(child) {(child)->parent = (node);};printf("%08x->%s now %08x\n", node, __STRING(side), child);
  97
  98 // rotates segment's left node to the top
  99 static inline segment_t*rotate_right(actlist_t*a, segment_t*s)
 100 {
 101     /*      s             n
 102            /               \
 103           n      ->         s
 104            \               /
 105             l             l
 106     */
 107     assert(s->leftchild);
 108     segment_t*p = s->parent;
 109     segment_t*n = s->leftchild;
 110     segment_t*l = s->rightchild;
 111     LINK(n,rightchild,s);
 112     LINK(s,leftchild,l);
 113     n->parent = p;
 114     if(p) {
 115         if(p->leftchild == s)
 116             p->leftchild = n;
 117         else if(p->rightchild == s)
 118             p->rightchild = n;
 119     } else {
 120         a->root = n;
 121     }
 122     return n;
 123 }
 124 // rotates segment's right node to the top
 125 static inline segment_t*rotate_left(actlist_t*a, segment_t*s)
 126 {
 127     /*      s             n
 128              \           /
 129               n  ->     s
 130              /           \
 131             r             r
 132     */
 133     assert(s->rightchild);
 134     segment_t*p = s->parent;
 135     segment_t*n = s->rightchild;
 136     segment_t*r = n->leftchild;
 137     LINK(n,leftchild,s);
 138     LINK(s,rightchild,r);
 139     n->parent = p;
 140     if(p) {
 141         if(p->leftchild == s)
 142             p->leftchild = n;
 143         else if(p->rightchild == s)
 144             p->rightchild = n;
 145     } else {
 146         a->root = n;
 147     }
 148     return n;
 149 }
 150 static void move_to_root(actlist_t*a, segment_t*s)
 151 {
 152     /* this is a textbook implementation of the three splay operations
 153        zig, zig-zig and zig-zag */
 154     while(a->root != s) {
 155         assert(s->parent);
 156         segment_t*p = s->parent;
 157         if(p == a->root) {
 158             // zig
 159             if(a->root->leftchild == s) {
 160                 rotate_right(a, a->root);
 161             } else {
 162                 rotate_left(a, a->root);
 163             }
 164             assert(a->root == s);
 165         } else {
 166             segment_t*pp = p->parent;
 167             if(p->leftchild == s && p->parent->leftchild == p->parent) {
 168                 // zig-zig (left)
 169                 rotate_right(a, pp);
 170                 rotate_right(a, pp);
 171             } else if(p->rightchild == s && p->parent->rightchild == p->parent) {
 172                 // zig-zig (right)
 173                 rotate_left(a, pp);
 174                 rotate_left(a, pp);
 175             } else if(p->leftchild == s && p->parent->rightchild == p->parent) {
 176                 // zig-zag (left)
 177                 rotate_right(a, p);
 178                 rotate_left(a, pp);
 179             } else if(p->rightchild == s && p->parent->leftchild == p->parent) {
 180                 // zig-zag (right)
 181                 rotate_right(a, p);
 182                 rotate_left(a, pp);
 183             }
 184         }
 185     }
 186 }
 187
 188 static int actlist_splay(actlist_t*a, point_t p1, point_t p2)
 189 {
 190     if(!a->list) return;
 191
 192     segment_t tmp;
 193     memset(&tmp, 0, sizeof(tmp));
 194     segment_t*left=&tmp,*right=&tmp;
 195
 196     while(1) {
 197         if(cmp(a->root,p1,p2)<0) {
 198             /* we're to the left of the root */
 199             if(!a->root->leftchild)
 200                 return -1;
 201             if(cmp(a->root->leftchild,p1,p2)<0) {
 202                 /* we're also to the left of the root's left child
 203                    -> rotate right, so that the left child is root */
 204                 segment_t*s = a->root->leftchild;
 205                 LINK(a->root, leftchild, s->rightchild);
 206                 LINK(s, rightchild, a->root);
 207                 a->root = s;
 208                 if(!a->root->leftchild)
 209                     return -1;
 210             }
 211             LINK(right, leftchild, a->root);
 212             right = a->root;
 213             a->root = a->root->leftchild;
 214         } else /* cmp(a->root,p1,p2)>=0 */ {
 215             /* we're to the right of the root */
 216             if(!a->root->rightchild)
 217                 return 1;
 218             if(cmp(a->root->rightchild,p1,p2)>=0) {
 219                 /* we're also to the right of the root's right child
 220                    -> rotate left, so that the right child is root */
 221                 segment_t*s = a->root->rightchild;
 222                 LINK(a->root, rightchild, s->leftchild);
 223                 LINK(s, leftchild, a->root);
 224                 a->root = s;
 225                 if(!a->root->rightchild)
 226                     return 1;
 227             }
 228             LINK(left, rightchild, a->root);
 229             left = a->root;
 230             a->root = a->root->rightchild;
 231         }
 232     }
 233     LINK(left, rightchild, a->root->leftchild);
 234     LINK(right, leftchild, a->root->rightchild);
 235     LINK(a->root, leftchild, tmp.rightchild);
 236     LINK(a->root, rightchild, tmp.leftchild);
 237 }
 238
 239 #endif
 240
 241 static void actlist_insert_after(actlist_t*a, segment_t*left, segment_t*s)
 242 {
 243     s->left = left;
 244     if(left) {
 245         s->right = left->right;
 246     } else {
 247         s->right = a->list;
 248         a->list = s;
 249     }
 250     if(s->left)
 251         s->left->right = s;
 252     if(s->right)
 253         s->right->left = s;
 254
 255 #ifdef SPLAY
 256     // we insert nodes not trees
 257     assert(!s->leftchild);
 258     assert(!s->rightchild);
 259
 260     if(a->root) {
 261         //if(actlist_splay(a, s->a, s->b) < 0) {
 262         if(cmp(a->root, s->a, s->b) < 0) {
 263             printf("new node %08x, link root (%08x) to the right\n", s, a->root);
 264             LINK(s,rightchild,a->root);
 265             // steal left child from (previous) root
 266             LINK(s,leftchild,a->root->leftchild);
 267             a->root->leftchild = 0;
 268         } else {
 269             printf("new node %08x, link root (%08x) to the left\n", s, a->root);
 270             LINK(s,leftchild,a->root);
 271             // steal right child from (previous) root
 272             LINK(s,rightchild,a->root->rightchild);
 273             a->root->rightchild = 0;
 274         }
 275     }
 276     a->root = s;
 277     a->root->parent = 0;
 278 #endif
 279
 280     a->size++;
 281 }
 282
 283 void actlist_insert(actlist_t*a, point_t p1, point_t p2, segment_t*s)
 284 {
 285     segment_t*left = actlist_find(a, p1, p2);
 286     actlist_insert_after(a, left, s);
 287 }
 288
 289 void actlist_delete(actlist_t*a, segment_t*s)
 290 {
 291     if(s->left) {
 292         s->left->right = s->right;
 293     } else {
 294         a->list = s->right;
 295     }
 296     if(s->right) {
 297         s->right->left = s->left;
 298     }
 299     s->left = s->right = 0;
 300     a->size--;
 301 #ifdef SPLAY
 302     printf("delete %08x\n", s);
 303     move_to_root(a, s);
 304     assert(a->root == s);
 305     // delete root node
 306     if(!a->root->leftchild) {
 307         printf("shift %08x->rightchild (%08x) to root\n", a->root, a->root->rightchild);
 308         a->root = a->root->rightchild;
 309     } else if(!a->root->rightchild) {
 310         printf("shift %08x->leftchild (%08x) to root\n", a->root, a->root->leftchild);
 311         a->root = a->root->leftchild;
 312     } else {
 313         printf("freeing up %08x->left->right\n", a->root);
 314         // free up root->left->right
 315         segment_t*t = a->root->leftchild;
 316         while(t->rightchild) {
 317             segment_t*r = t->rightchild;
 318             segment_t*l = r->leftchild;
 319             LINK(r, leftchild, t);
 320             LINK(t, rightchild, l);
 321             t = r;
 322         }
 323         LINK(a->root,leftchild,t);
 324         assert(!a->root->leftchild->rightchild);
 325         LINK(a->root->leftchild,rightchild,a->root->right);
 326         a->root = a->root->leftchild;
 327     }
 328     if(a->root)
 329         a->root->parent = 0;
 330     s->leftchild = s->rightchild = s->parent = 0;
 331 #endif
 332 }
 333 int actlist_size(actlist_t*a)
 334 {
 335     return a->size;
 336 }
 337
 338 segment_t* actlist_leftmost(actlist_t*a)
 339 {
 340     return a->list;
 341 }
 342
 343 segment_t* actlist_rightmost(actlist_t*a)
 344 {
 345     /* this is only used in checks, so it doesn't matter that it's slow */
 346     segment_t*s = a->list;
 347     segment_t*last = 0;
 348     while(s) {
 349         last = s;
 350         s = s->right;
 351     }
 352     return last;
 353 }
 354
 355 segment_t* actlist_left(actlist_t*a, segment_t*s)
 356 {
 357     return s->left;
 358 }
 359
 360 segment_t* actlist_right(actlist_t*a, segment_t*s)
 361 {
 362     if(s) return s->right;
 363     else  return a->list;
 364 }
 365
 366 void actlist_swap(actlist_t*a, segment_t*s1, segment_t*s2)
 367 {
 368     // for splaying this needs to be rewritten (can't use insert_after)
 369     actlist_delete(a, s1);
 370     actlist_insert_after(a, s2, s1);
 371 }