lib/gfxpoly/active.c

   1 #include "../q.h"
   2 #include "active.h"
   3
   4 actlist_t* actlist_new()
   5 {
   6     NEW(actlist_t, a);
   7     return a;
   8 }
   9 void actlist_destroy(actlist_t*a)
  10 {
  11     free(a);
  12 }
  13
  14 void actlist_dump(actlist_t*a, int32_t y)
  15 {
  16     segment_t*s = a->list;
  17     double lastx;
  18     char bad = 0;
  19     while(s) {
  20         if(y) {
  21             double x = ((double)s->delta.x*(y-s->a.y)/s->delta.y)+s->a.x;
  22             if(s!=a->list) {
  23                 if(lastx>x)
  24                     fprintf(stderr, "?%f<->%f? ", lastx, x);
  25             }
  26             lastx = x;
  27         }
  28         fprintf(stderr, "[%d]", s->nr);
  29         s = s->right;
  30         if(s) fprintf(stderr, " ");
  31         else fprintf(stderr, "\n");
  32     }
  33 }
  34 void actlist_verify(actlist_t*a, int32_t y)
  35 {
  36     segment_t*s = a->list;
  37     assert(!s || !s->left);
  38     segment_t*l = 0;
  39     while(s) {
  40         if(y) {
  41             if(l) {
  42                 /* we need to re-evaluate the x of the previous segment. if we
  43                    try to store it, it might end up being converted to a double,
  44                    which will make it non-equal to (and possibly larger than) the
  45                    "long double" the FPU has in it's register. This only happens
  46                    when compiler optimizations are turned on. */
  47                 assert((XPOS(s, y) - XPOS(l, y)) >= 0);
  48                 assert(XDIFF(s,l,y) >= 0);
  49             }
  50             l = s;
  51         }
  52         assert(!s->left || s->left->right == s);
  53         assert(!s->right || s->right->left == s);
  54         s = s->right;
  55     }
  56 }
  57
  58 segment_t* actlist_find(actlist_t*a, point_t p1, point_t p2)
  59 {
  60     /* this runs in O(n) right now, and should be optimized using a splay
  61        tree to run in ammortized O(log(n))
  62        (update: currently only 2.5% of the algorithm's running time is spent here,
  63         so maybe we don't need to bother)
  64      */
  65     segment_t*last=0, *s = a->list;
  66     if(!s) return last;
  67     while(s) {
  68         double d = LINE_EQ(p1, s);
  69         if(d==0) {
  70             d = LINE_EQ(p2, s);
  71             if(d==0) {
  72                 /* We default to always inserting the new segment to the right of the old segment.
  73                    We do this so that we don't place new segments into the middle of already
  74                    overlapping lines which may have intersections scheduled.
  75                  */
  76                 //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);
  77             }
  78         }
  79         if(d<0)
  80             break;
  81         last = s;
  82         s = s->right;
  83     }
  84     return last;
  85 }
  86
  87 static void actlist_insert_after(actlist_t*a, segment_t*left, segment_t*s)
  88 {
  89     s->left = left;
  90     if(left) {
  91         s->right = left->right;
  92     } else {
  93         s->right = a->list;
  94         a->list = s;
  95     }
  96     if(s->left)
  97         s->left->right = s;
  98     if(s->right)
  99         s->right->left = s;
 100     a->size++;
 101 }
 102
 103 void actlist_insert(actlist_t*a, point_t p, segment_t*s)
 104 {
 105     segment_t*left = actlist_find(a, p, s->b);
 106     actlist_insert_after(a, left, s);
 107 }
 108
 109 void actlist_delete(actlist_t*a, segment_t*s)
 110 {
 111     if(s->left) {
 112         s->left->right = s->right;
 113     } else {
 114         a->list = s->right;
 115     }
 116     if(s->right) {
 117         s->right->left = s->left;
 118     }
 119     s->left = s->right = 0;
 120     a->size--;
 121 }
 122 int actlist_size(actlist_t*a)
 123 {
 124     return a->size;
 125 }
 126
 127 segment_t* actlist_leftmost(actlist_t*a)
 128 {
 129     return a->list;
 130 }
 131
 132 segment_t* actlist_rightmost(actlist_t*a)
 133 {
 134     /* this is only used in checks, so it doesn't matter that it's slow */
 135     segment_t*s = a->list;
 136     segment_t*last = 0;
 137     while(s) {
 138         last = s;
 139         s = s->right;
 140     }
 141     return last;
 142 }
 143
 144 segment_t* actlist_left(actlist_t*a, segment_t*s)
 145 {
 146     return s->left;
 147 }
 148
 149 segment_t* actlist_right(actlist_t*a, segment_t*s)
 150 {
 151     if(s) return s->right;
 152     else  return a->list;
 153 }
 154
 155 void actlist_swap(actlist_t*a, segment_t*s1, segment_t*s2)
 156 {
 157     actlist_delete(a, s1);
 158     actlist_insert_after(a, s2, s1);
 159 }