From ba166d59c4c6672c8cb65c881193bb104c629bf7 Mon Sep 17 00:00:00 2001 From: Matthias Kramm Date: Fri, 15 May 2009 14:04:52 -0700 Subject: [PATCH] small speed improvements --- lib/gfxpoly/active.c | 41 ++++++++++++++++------------------------- lib/gfxpoly/active.h | 5 +++-- lib/gfxpoly/convert.c | 23 ++++++++++++++++++----- lib/gfxpoly/poly.c | 15 ++++++++------- lib/gfxpoly/poly.h | 4 +++- 5 files changed, 48 insertions(+), 40 deletions(-) diff --git a/lib/gfxpoly/active.c b/lib/gfxpoly/active.c index 34fe9d5..5a2c451 100644 --- a/lib/gfxpoly/active.c +++ b/lib/gfxpoly/active.c @@ -89,7 +89,20 @@ segment_t* actlist_find(actlist_t*a, point_t p1, point_t p2) 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; @@ -445,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 @@ -454,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; @@ -551,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) { @@ -566,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 diff --git a/lib/gfxpoly/active.h b/lib/gfxpoly/active.h index 6809e7b..02073b0 100644 --- a/lib/gfxpoly/active.h +++ b/lib/gfxpoly/active.h @@ -12,6 +12,9 @@ typedef struct _actlist #endif } actlist_t; +#define actlist_left(a,s) ((s)->left) +#define actlist_right(a,s) ((s)?(s)->right:(a)->list) + actlist_t* actlist_new(); void actlist_destroy(actlist_t*a); int actlist_size(actlist_t*a); @@ -21,9 +24,7 @@ segment_t* actlist_find(actlist_t*a, point_t p1, point_t p2); // finds segment void actlist_insert(actlist_t*a, point_t p1, point_t p2, segment_t*s); void actlist_delete(actlist_t*a, segment_t*s); void actlist_swap(actlist_t*a, segment_t*s1, segment_t*s2); -segment_t* actlist_left(actlist_t*a, segment_t*s); segment_t* actlist_leftmost(actlist_t*a); segment_t* actlist_rightmost(actlist_t*a); -segment_t* actlist_right(actlist_t*a, segment_t*s); #endif diff --git a/lib/gfxpoly/convert.c b/lib/gfxpoly/convert.c index aea0a17..e326333 100644 --- a/lib/gfxpoly/convert.c +++ b/lib/gfxpoly/convert.c @@ -5,6 +5,9 @@ #include "../mem.h" #include "poly.h" +/* factor that determines into how many line fragments a spline is converted */ +#define SUBFRACTION (2.4) + static edge_t*edge_new(int x1, int y1, int x2, int y2) { edge_t*s = rfx_calloc(sizeof(edge_t)); @@ -21,6 +24,7 @@ static inline void gfxpoly_add_edge(gfxpoly_t*poly, double _x1, double _y1, doub int y1 = ceil(_y1); int x2 = ceil(_x2); int y2 = ceil(_y2); + if(x1!=x2 || y1!=y2) { edge_t*s = edge_new(x1, y1, x2, y2); s->next = poly->edges; @@ -32,9 +36,6 @@ gfxpoly_t* gfxpoly_from_gfxline(gfxline_t*line, double gridsize) { gfxpoly_t*p = gfxpoly_new(gridsize); - /* factor that determines into how many line fragments a spline is converted */ - double subfraction = 2.4;//0.3 - double z = 1.0 / gridsize; double lastx=0, lasty=0; @@ -47,7 +48,7 @@ gfxpoly_t* gfxpoly_from_gfxline(gfxline_t*line, double gridsize) gfxpoly_add_edge(p, lastx, lasty, x, y); } else if(line->type == gfx_splineTo) { int parts = (int)(sqrt(fabs(line->x-2*line->sx+lastx) + - fabs(line->y-2*line->sy+lasty))*subfraction); + fabs(line->y-2*line->sy+lasty))*SUBFRACTION); if(!parts) parts = 1; double stepsize = 1.0/parts; int i; @@ -65,11 +66,23 @@ gfxpoly_t* gfxpoly_from_gfxline(gfxline_t*line, double gridsize) lasty = y; line = line->next; } - + gfxline_free(line); return p; } +typedef struct _gfxstroke { + segment_dir_t dir; + point_t*stroke; + fillstyle_t*fs; + int num_points; +} gfxstroke_t; +typedef struct _gfxcompactpoly { + double gridsize; + int num_strokes; + gfxstroke_t strokes[0]; +} gfxcompactpoly_t; + static char* readline(FILE*fi) { char c; diff --git a/lib/gfxpoly/poly.c b/lib/gfxpoly/poly.c index 1ef8618..26218ab 100644 --- a/lib/gfxpoly/poly.c +++ b/lib/gfxpoly/poly.c @@ -67,7 +67,10 @@ typedef struct _status { #endif } status_t; -int compare_events_simple(const void*_a,const void*_b) +/* compare_events_simple differs from compare_events in that it schedules + events from left to right regardless of type. It's only used in horizontal + processing, in order to get an x-wise sorting of the current scanline */ +static int compare_events_simple(const void*_a,const void*_b) { event_t* a = (event_t*)_a; event_t* b = (event_t*)_b; @@ -83,7 +86,7 @@ int compare_events_simple(const void*_a,const void*_b) return 0; } -int compare_events(const void*_a,const void*_b) +static int compare_events(const void*_a,const void*_b) { event_t* a = (event_t*)_a; event_t* b = (event_t*)_b; @@ -300,9 +303,9 @@ void gfxpoly_enqueue(edge_t*list, heap_t*queue, windstate_t initial, int polygon continue; } segment_t*s = segment_new(l->a.x, l->a.y, l->b.x, l->b.y, initial, polygon_nr); +#ifdef DEBUG if(l->tmp) s->nr = l->tmp; -#ifdef DEBUG fprintf(stderr, "[%d] (%d,%d) -> (%d,%d) %s\n", s->nr, s->a.x, s->a.y, s->b.x, s->b.y, s->dir==DIR_UP?"up":"down"); @@ -528,7 +531,9 @@ static void insert_point_into_segment(status_t*status, segment_t*s, point_t p) // omit horizontal lines if(s->pos.y != p.y) { edge_t*e = rfx_calloc(sizeof(edge_t)); +#ifdef DEBUG e->tmp = s->nr; +#endif e->a = s->pos; e->b = p; assert(e->a.y != e->b.y); @@ -543,9 +548,6 @@ static void insert_point_into_segment(status_t*status, segment_t*s, point_t p) s->pos = p; } -/* by restricting the recalculation of line segments to a range between the lowest - and the highest modified segment, we only do about a 33% overprocessing of fill - styles. (update: that statistic might be outdated now that xmin/xmax are double) */ typedef struct _segrange { double xmin; segment_t*segmin; @@ -969,7 +971,6 @@ static void add_horizontals(gfxpoly_t*poly, windrule_t*windrule) actlist_dump(actlist, y-1); #endif #ifdef CHECKS - /* FIXME: this actually fails sometimes */ actlist_verify(actlist, y-1); #endif do { diff --git a/lib/gfxpoly/poly.h b/lib/gfxpoly/poly.h index ac1ff37..dfada99 100644 --- a/lib/gfxpoly/poly.h +++ b/lib/gfxpoly/poly.h @@ -5,7 +5,7 @@ #include "../q.h" //#define DEBUG -#define CHECKS +//#define CHECKS #define SPLAY typedef enum {DIR_UP, DIR_DOWN} segment_dir_t; @@ -25,7 +25,9 @@ typedef struct _edge { point_t a; point_t b; fillstyle_t*style; +#ifdef DEBUG int tmp; +#endif struct _edge *next; } edge_t; -- 1.7.10.4