X-Git-Url: http://git.asbjorn.biz/?a=blobdiff_plain;f=lib%2Fgfxpoly%2Factive.c;h=5d01c304592a977fa42baa0dbbafff046befce74;hb=c768cd47515e9101d8d38de85cc2f6fcbfccaef6;hp=b0ef07ca08d8286c06554eb5833ac230bd6ba8f5;hpb=ae7c92fe5721f97e786a8bbe9153eadbf292460d;p=swftools.git

diff --git a/lib/gfxpoly/active.c b/lib/gfxpoly/active.c
index b0ef07c..5d01c30 100644
--- a/lib/gfxpoly/active.c
+++ b/lib/gfxpoly/active.c
@@ -1,4 +1,4 @@
-#include <assert.h>
+#include <memory.h>
 #include "../q.h"
 #include "active.h"
 
@@ -36,14 +36,19 @@ void actlist_verify(actlist_t*a, int32_t y)
 {
     segment_t*s = a->list;
     assert(!s || !s->left);
-    double lastx;
+    segment_t*l = 0;
     while(s) {
         if(y) {
-            double x = ((double)s->delta.x*(y-s->a.y)/s->delta.y)+s->a.x;
-            if(s!=a->list) {
-                assert(lastx<=x);
+            if(l) {
+                /* 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
+                   when compiler optimizations are turned on. */
+                assert((XPOS(s, y) - XPOS(l, y)) >= 0);
+                assert(XDIFF(s,l,y) >= 0);
             }
-            lastx = x;
+            l = s;
         }
         assert(!s->left || s->left->right == s);
         assert(!s->right || s->right->left == s);
@@ -51,6 +56,22 @@ void actlist_verify(actlist_t*a, int32_t y)
     }
 }
 
+static inline double cmp(segment_t*s, point_t p1, point_t p2)
+{
+    double d = LINE_EQ(p1, s);
+    if(d==0) {
+	d = LINE_EQ(p2, s);
+	if(d==0) {
+	    /* We default to always inserting the new segment to the right of the old segment.
+	       We do this so that we don't place new segments into the middle of already
+	       overlapping lines which may have intersections scheduled.
+	     */
+	    //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);
+	}
+    }
+    return d;
+}
+
 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
@@ -61,17 +82,7 @@ segment_t* actlist_find(actlist_t*a, point_t p1, point_t p2)
     segment_t*last=0, *s = a->list;
     if(!s) return last;
     while(s) {
-        double d = LINE_EQ(p1, s);
-        if(d==0) {
-            d = LINE_EQ(p2, s);
-            if(d==0) {
-                /* We default to always inserting the new segment to the right of the old segment.
-                   We do this so that we don't place new segments into the middle of already
-                   overlapping lines which may have intersections scheduled.
-                 */
-                //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);
-            }
-        }
+	double d = cmp(s, p1, p2);
         if(d<0)
             break;
         last = s;
@@ -80,6 +91,153 @@ segment_t* actlist_find(actlist_t*a, point_t p1, point_t p2)
     return last;
 }
 
+#ifdef SPLAY
+
+#define LINK(node,side,child) (node)->side = (child);if(child) {(child)->parent = (node);};printf("%08x->%s now %08x\n", node, __STRING(side), child);
+
+// rotates segment's left node to the top
+static inline segment_t*rotate_right(actlist_t*a, segment_t*s)
+{
+    /*      s             n
+	   /               \
+	  n      ->         s
+	   \               /
+	    l             l
+    */
+    assert(s->leftchild);
+    segment_t*p = s->parent;
+    segment_t*n = s->leftchild;
+    segment_t*l = s->rightchild;
+    LINK(n,rightchild,s);
+    LINK(s,leftchild,l);
+    n->parent = p;
+    if(p) {
+	if(p->leftchild == s)
+	    p->leftchild = n;
+	else if(p->rightchild == s)
+	    p->rightchild = n;
+    } else {
+	a->root = n;
+    }
+    return n;
+}
+// rotates segment's right node to the top
+static inline segment_t*rotate_left(actlist_t*a, segment_t*s)
+{
+    /*      s             n
+	     \           /
+	      n  ->     s
+	     /           \
+	    r             r
+    */
+    assert(s->rightchild);
+    segment_t*p = s->parent;
+    segment_t*n = s->rightchild;
+    segment_t*r = n->leftchild;
+    LINK(n,leftchild,s);
+    LINK(s,rightchild,r);
+    n->parent = p;
+    if(p) {
+	if(p->leftchild == s)
+	    p->leftchild = n;
+	else if(p->rightchild == s)
+	    p->rightchild = n;
+    } else {
+	a->root = n;
+    }
+    return n;
+}
+static void move_to_root(actlist_t*a, segment_t*s)
+{
+    /* this is a textbook implementation of the three splay operations
+       zig, zig-zig and zig-zag */
+    while(a->root != s) {
+	assert(s->parent);
+	segment_t*p = s->parent;
+	if(p == a->root) {
+	    // zig
+	    if(a->root->leftchild == s) {
+		rotate_right(a, a->root);
+	    } else {
+		rotate_left(a, a->root);
+	    }
+	    assert(a->root == s);
+        } else {
+	    segment_t*pp = p->parent;
+	    if(p->leftchild == s && p->parent->leftchild == p->parent) {
+		// zig-zig (left)
+		rotate_right(a, pp);
+		rotate_right(a, pp);
+	    } else if(p->rightchild == s && p->parent->rightchild == p->parent) {
+		// zig-zig (right)
+		rotate_left(a, pp);
+		rotate_left(a, pp);
+	    } else if(p->leftchild == s && p->parent->rightchild == p->parent) {
+		// zig-zag (left)
+		rotate_right(a, p);
+		rotate_left(a, pp);
+	    } else if(p->rightchild == s && p->parent->leftchild == p->parent) {
+		// zig-zag (right)
+		rotate_right(a, p);
+		rotate_left(a, pp);
+	    }
+	}
+    }
+}
+
+static int actlist_splay(actlist_t*a, point_t p1, point_t p2)
+{
+    if(!a->list) return;
+
+    segment_t tmp;
+    memset(&tmp, 0, sizeof(tmp));
+    segment_t*left=&tmp,*right=&tmp;
+    
+    while(1) {
+	if(cmp(a->root,p1,p2)<0) {
+	    /* we're to the left of the root */
+	    if(!a->root->leftchild)
+		return -1;
+	    if(cmp(a->root->leftchild,p1,p2)<0) {
+		/* we're also to the left of the root's left child
+		   -> rotate right, so that the left child is root */
+		segment_t*s = a->root->leftchild;
+		LINK(a->root, leftchild, s->rightchild);
+		LINK(s, rightchild, a->root);
+		a->root = s;
+		if(!a->root->leftchild)
+		    return -1;
+	    }
+	    LINK(right, leftchild, a->root);
+	    right = a->root;
+	    a->root = a->root->leftchild;
+	} else /* cmp(a->root,p1,p2)>=0 */ {
+	    /* we're to the right of the root */
+	    if(!a->root->rightchild)
+		return 1;
+	    if(cmp(a->root->rightchild,p1,p2)>=0) {
+		/* we're also to the right of the root's right child
+		   -> rotate left, so that the right child is root */
+		segment_t*s = a->root->rightchild;
+		LINK(a->root, rightchild, s->leftchild);
+		LINK(s, leftchild, a->root);
+		a->root = s;
+		if(!a->root->rightchild)
+		    return 1;
+	    }
+	    LINK(left, rightchild, a->root);
+	    left = a->root;
+	    a->root = a->root->rightchild;
+	}
+    }
+    LINK(left, rightchild, a->root->leftchild);
+    LINK(right, leftchild, a->root->rightchild);
+    LINK(a->root, leftchild, tmp.rightchild);
+    LINK(a->root, rightchild, tmp.leftchild);
+}
+
+#endif
+
 static void actlist_insert_after(actlist_t*a, segment_t*left, segment_t*s)
 {
     s->left = left;
@@ -93,12 +251,38 @@ static void actlist_insert_after(actlist_t*a, segment_t*left, segment_t*s)
         s->left->right = s;
     if(s->right) 
         s->right->left = s;
+
+#ifdef SPLAY
+    // we insert nodes not trees 
+    assert(!s->leftchild);
+    assert(!s->rightchild);
+
+    if(a->root) {
+	//if(actlist_splay(a, s->a, s->b) < 0) {
+	if(cmp(a->root, s->a, s->b) < 0) {
+	    printf("new node %08x, link root (%08x) to the right\n", s, a->root);
+	    LINK(s,rightchild,a->root);
+	    // steal left child from (previous) root
+	    LINK(s,leftchild,a->root->leftchild);
+	    a->root->leftchild = 0;
+	} else {
+	    printf("new node %08x, link root (%08x) to the left\n", s, a->root);
+	    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;
+#endif
+
     a->size++;
 }
 
-void actlist_insert(actlist_t*a, point_t p, segment_t*s)
+void actlist_insert(actlist_t*a, point_t p1, point_t p2, segment_t*s)
 {
-    segment_t*left = actlist_find(a, p, s->b);
+    segment_t*left = actlist_find(a, p1, p2);
     actlist_insert_after(a, left, s);
 }
 
@@ -114,6 +298,37 @@ void actlist_delete(actlist_t*a, segment_t*s)
     }
     s->left = s->right = 0;
     a->size--;
+#ifdef SPLAY
+    printf("delete %08x\n", s);
+    move_to_root(a, s);
+    assert(a->root == s);
+    // delete root node
+    if(!a->root->leftchild) {
+	printf("shift %08x->rightchild (%08x) to root\n", a->root, a->root->rightchild);
+	a->root = a->root->rightchild;
+    } else if(!a->root->rightchild) {
+	printf("shift %08x->leftchild (%08x) to root\n", a->root, a->root->leftchild);
+	a->root = a->root->leftchild;
+    } else {
+	printf("freeing up %08x->left->right\n", a->root);
+	// free up root->left->right
+	segment_t*t = a->root->leftchild;
+	while(t->rightchild) {
+	    segment_t*r = t->rightchild;
+	    segment_t*l = r->leftchild;
+	    LINK(r, leftchild, t);
+	    LINK(t, rightchild, l);
+	    t = r;
+	}
+	LINK(a->root,leftchild,t);
+	assert(!a->root->leftchild->rightchild);
+	LINK(a->root->leftchild,rightchild,a->root->right);
+	a->root = a->root->leftchild;
+    }
+    if(a->root) 
+	a->root->parent = 0;
+    s->leftchild = s->rightchild = s->parent = 0;
+#endif
 }
 int actlist_size(actlist_t*a)
 {
@@ -150,6 +365,7 @@ segment_t* actlist_right(actlist_t*a, segment_t*s)
 
 void actlist_swap(actlist_t*a, segment_t*s1, segment_t*s2)
 {
+    // for splaying this needs to be rewritten (can't use insert_after)
     actlist_delete(a, s1);
     actlist_insert_after(a, s2, s1);
 }