X-Git-Url: http://git.asbjorn.biz/?p=swftools.git;a=blobdiff_plain;f=lib%2Fgfxpoly%2Factive.c;h=340d5bcd568e1759a98f210a5bad716a29eac15a;hp=7f761b942ee1dd9f6fa7a861bbdd095c2ab33c19;hb=e3f35893d64112de70839da517c31e239a250b6a;hpb=33e9461da6b886671749d6cbabd80b355ab1f6d9 diff --git a/lib/gfxpoly/active.c b/lib/gfxpoly/active.c index 7f761b9..340d5bc 100644 --- a/lib/gfxpoly/active.c +++ b/lib/gfxpoly/active.c @@ -1,4 +1,6 @@ +#include #include +#include #include "../q.h" #include "active.h" @@ -44,7 +46,7 @@ void actlist_verify(actlist_t*a, int32_t y) /* we need to re-evaluate the x of the previous segment. if we try to store it, it might end up being converted to a double, which will make it non-equal to (and possibly larger than) the - "long double" the FPU has in it's register. This only happens + "long double" the FPU has in its register. This only happens when compiler optimizations are turned on. */ assert((XPOS(s, y) - XPOS(l, y)) >= 0); assert(XDIFF(s,l,y) >= 0); @@ -57,6 +59,11 @@ void actlist_verify(actlist_t*a, int32_t y) } } +static inline double single_cmp(segment_t*s, point_t p1) +{ + return LINE_EQ(p1, s); +} + static inline double cmp(segment_t*s, point_t p1, point_t p2) { double d = LINE_EQ(p1, s); @@ -73,13 +80,118 @@ static inline double cmp(segment_t*s, point_t p1, point_t p2) return d; } +#ifdef SPLAY +static void actlist_splay_dump(actlist_t*a); +segment_t* actlist_find(actlist_t*a, point_t p1, point_t p2) +{ +#ifdef CHECKS + segment_t*t = a->list; + char to_the_left = 0; + char fail = 0; + while(t) { + /* this check doesn't work out with cmp() because during horizontal + processing, both segments ending as well as segments starting will + be active in this scanline */ + //double d = cmp(t, p1, p2); + double d = single_cmp(t, p1); + if(d>=0 && to_the_left) { + segment_t*s = a->list; + while(s) { + fprintf(stderr, "[%d] %f/%f (%d,%d) -> (%d,%d)\n", s->nr, + single_cmp(s,p1), cmp(s,p1,p2), + s->a.x, s->a.y, s->b.x, s->b.y); + s = s->right; + } + } + assert(!(d>=0 && to_the_left)); + if(d<0) to_the_left=1; + t = t->right; + } +#if 0 + if(a->size > 100) { + static actlist_t*last = 0; + if(last != a) { + last = a; + actlist_splay_dump(a); + } + } +#endif +#endif + segment_t*last=0, *s = a->root; + if(!s) return 0; + double d=0; + int depth = 0; + while(s) { + last = s; + depth++; + d = single_cmp(s, p1); + if(d<=0) { + s = s->leftchild; + } else { + s = s->rightchild; + } + } +//#ifdef DEBUG +#if 0 + if(a->size > 1) { + /* 80% hit, average cost per miss ~ 4 nodes */ + int expected_depth = (int)((double)log2((double)a->size+1))+1; + static int hits = 0; + static int misses = 0; + static int miss_cost = 0; + if(depth <= expected_depth) hits++; + else {misses++; + miss_cost += depth - expected_depth; + } + if(hits && misses) + fprintf(stderr, "%02.2f%% %f\n", hits / (double)(hits+misses), miss_cost / (double)misses); + } +#endif + + segment_t*out = last; + if(d<0 || (d==0 && LINE_EQ(p2,last)<0)) { + last = last->left; + if(!last) { + assert(cmp(a->list, p1, p2)<0); + return 0; + } + } else { + while(last->right && cmp(last->right, p1, p2)>=0) { + last = last->right; + } + } + +#ifdef CHECKS + segment_t*l=0; + s = a->list; + while(s) { + if(cmp(s, p1, p2)<0) + break; + l = s;s = s->right; + } + if(l!=last) { + printf("[%d]!=[%d]\n", SEGNR(l), SEGNR(last)); + printf("after tree: [%d]\n", SEGNR(out)); + actlist_splay_dump(a); + s = a->list; + while(s) { + double d1 = single_cmp(s,p1); + double d2 = cmp(s,p1,p2); + int x1 = d1<0?-1:(d1>0?1:0); + int x2 = d2<0?-1:(d2>0?1:0); + printf("[%d](%d,%d) ", SEGNR(s), x1, x2); + s = s->right; + } + printf("\n"); + } + assert(l == last); +#endif + + return last; +} +#else segment_t* actlist_find(actlist_t*a, point_t p1, point_t p2) { - /* this runs in O(n) right now, and should be optimized using a splay - tree to run in ammortized O(log(n)) - (update: currently only 2.5% of the algorithm's running time is spent here, - so maybe we don't need to bother) - */ segment_t*last=0, *s = a->list; if(!s) return last; while(s) { @@ -91,8 +203,8 @@ segment_t* actlist_find(actlist_t*a, point_t p1, point_t p2) } return last; } +#endif -#define SEGNR(s) ((s)?(s)->nr:-1) #ifdef SPLAY #define LINK(node,side,child) (node)->side = (child);if(child) {(child)->parent = (node);} @@ -175,29 +287,47 @@ static int actlist_splay_verify(actlist_t*a) if(c) return 0; return 1; } -static void actlist_splay_dump2(actlist_t*a, segment_t*s, int indent) +static void actlist_splay_dump2(actlist_t*a, segment_t*s, char*mid, char*up, char*down) { if(!s) return; - int t; + if(s->leftchild || s->rightchild) { - fprintf(stderr, "("); - fprintf(stderr, "[%d]", SEGNR(s->leftchild)); + int t; + if(s->leftchild) { - actlist_splay_dump2(a, s->leftchild, indent+8); + char*o3 = malloc(strlen(up)+3); + strcpy(o3, up);strcat(o3, "+-"); + char*newup = malloc(strlen(up)+3); + strcpy(newup, up);strcat(newup, "| "); + char*newup2 = malloc(strlen(up)+3); + strcpy(newup2, up);strcat(newup2, " "); + actlist_splay_dump2(a, s->leftchild, o3, newup2, newup); + fprintf(stderr, "%s| \n", up); + free(newup); + free(newup2); + free(o3); } - fprintf(stderr, ","); - fprintf(stderr, "[%d]", SEGNR(s->rightchild)); + fprintf(stderr, "%s[%d]\n", mid, SEGNR(s)); if(s->rightchild) { - actlist_splay_dump2(a, s->rightchild, indent+8); + char*o3 = malloc(strlen(down)+3); + strcpy(o3, down);strcat(o3, "+-"); + char*newdown = malloc(strlen(down)+3); + strcpy(newdown, down);strcat(newdown, "| "); + char*newdown2 = malloc(strlen(down)+3); + strcpy(newdown2, down);strcat(newdown2, " "); + fprintf(stderr, "%s| \n", down); + actlist_splay_dump2(a, s->rightchild, o3, newdown, newdown2); + free(newdown); + free(newdown2); + free(o3); } - fprintf(stderr, ")"); + } else { + fprintf(stderr, "%s[%d]\n", mid, SEGNR(s)); } } static void actlist_splay_dump(actlist_t*a) { - fprintf(stderr, "[%d]", SEGNR(a->root)); - actlist_splay_dump2(a, a->root, 1); - fprintf(stderr, "\n"); + actlist_splay_dump2(a, a->root, "", "", ""); } @@ -328,7 +458,6 @@ static void actlist_insert_after(actlist_t*a, segment_t*left, segment_t*s) if(a->root) { move_to_root(a, left); - if(left) { LINK(s,leftchild,a->root); // steal right child from (previous) root @@ -337,18 +466,6 @@ static void actlist_insert_after(actlist_t*a, segment_t*left, segment_t*s) } else { LINK(s,rightchild,a->root); } - - /*if(cmp(a->root, s->a, s->b) < 0) { - LINK(s,rightchild,a->root); - // steal left child from (previous) root - LINK(s,leftchild,a->root->leftchild); - a->root->leftchild = 0; - } else { - LINK(s,leftchild,a->root); - // steal right child from (previous) root - LINK(s,rightchild,a->root->rightchild); - a->root->rightchild = 0; - }*/ } a->root = s; a->root->parent = 0; @@ -434,6 +551,9 @@ segment_t* actlist_leftmost(actlist_t*a) segment_t* actlist_rightmost(actlist_t*a) { /* this is only used in checks, so it doesn't matter that it's slow */ +#ifndef CHECKS + fprintf(stderr, "Warning: actlist_rightmost should not be used\n"); +#endif segment_t*s = a->list; segment_t*last = 0; while(s) { @@ -449,18 +569,6 @@ void actlist_insert(actlist_t*a, point_t p1, point_t p2, segment_t*s) actlist_insert_after(a, left, s); } - -segment_t* actlist_left(actlist_t*a, segment_t*s) -{ - return s->left; -} - -segment_t* actlist_right(actlist_t*a, segment_t*s) -{ - if(s) return s->right; - else return a->list; -} - void actlist_swap(actlist_t*a, segment_t*s1, segment_t*s2) { #ifdef SPLAY @@ -569,10 +677,8 @@ void actlist_swap(actlist_t*a, segment_t*s1, segment_t*s2) if(s2->leftchild) s2->leftchild->parent = s2; if(s1->rightchild) s1->rightchild->parent = s1; if(s2->rightchild) s2->rightchild->parent = s2; - if(!actlist_splay_verify(a)) { - actlist_splay_dump(a); - actlist_dump(a, s1->a.y); - } + + assert(actlist_splay_verify(a)); #endif //#endif