diff options
| -rw-r--r-- | ChangeLog | 23 | ||||
| -rw-r--r-- | twin.h | 4 | ||||
| -rw-r--r-- | twin_convolve.c | 145 | ||||
| -rw-r--r-- | twin_path.c | 5 | ||||
| -rw-r--r-- | twin_poly.c | 107 | ||||
| -rw-r--r-- | twinint.h | 4 | ||||
| -rw-r--r-- | xtwin.c | 33 |
7 files changed, 210 insertions, 111 deletions
@@ -1,5 +1,28 @@ 2004-09-21 Keith Packard <keithp@keithp.com> + * twin.h: + * twinint.h: + Add a few definitions + + * twin_convolve.c: (_twin_path_leftpoint), (twin_path_convolve): + Find pen starting point as closest to the normal to the path. + Restructure convolve loop to be easier to understand + + * twin_path.c: (twin_path_circle): + Round circle coordinates instead of truncating them + + * twin_poly.c: (_twin_fixed_grid_ceil), (_twin_edge_build), + (_span_fill), (_twin_edge_fill): + Move sample grid by 1/2 sample step. + Clip polygons to mask pixmap. + Modest performance improvement in span filling. + Fix end case to remove edges before stepping. + + * xtwin.c: (main): + Stroke a path. + +2004-09-21 Keith Packard <keithp@keithp.com> + * Makefile.am: * twin.h: * twin_convolve.c: (_twin_path_leftmost), (_twin_path_step), @@ -41,9 +41,11 @@ typedef int32_t twin_dfixed_t; #define twin_double_to_fixed(d) ((twin_fixed_t) ((d) * 16.0)) #define twin_fixed_to_double(f) ((double) (f) / 16.0) +#define twin_int_to_fixed(i) ((twin_fixed_t) ((i) * 16)) #define TWIN_FIXED_ONE (0x10) -#define TWIN_FIXED_TOLERANCE (TWIN_FIXED_ONE >> 1) +#define TWIN_FIXED_HALF (0x08) +#define TWIN_FIXED_TOLERANCE (TWIN_FIXED_HALF) #define TWIN_FALSE 0 #define TWIN_TRUE 1 diff --git a/twin_convolve.c b/twin_convolve.c index dab05d2..78559bc 100644 --- a/twin_convolve.c +++ b/twin_convolve.c @@ -23,32 +23,46 @@ */ #include "twinint.h" - + /* - * Find the point in path closest to a line normal to p1-p2 which passes through p1 - * (this does not do this yet, but it should) + * Find the point in path which is left of the line and + * closest to a line normal to p1-p2 passing through p1 */ static int -_twin_path_leftmost (twin_path_t *path, - twin_point_t *p1, - twin_point_t *p2) +_twin_path_leftpoint (twin_path_t *path, + twin_point_t *p1, + twin_point_t *p2) { int p; int best = 0; - twin_dfixed_t A = p2->y - p1->y; - twin_dfixed_t B = p1->x - p2->x; - twin_dfixed_t C = ((twin_dfixed_t) p1->y * p2->x - - (twin_dfixed_t) p1->x * p2->y); - twin_dfixed_t max = -0x7fffffff; + /* + * Along the path + */ + twin_dfixed_t Ap = p2->y - p1->y; + twin_dfixed_t Bp = p1->x - p2->x; + + /* + * Normal to the path + */ + + twin_fixed_t xn = (p1->x - (p2->y - p1->y)); + twin_fixed_t yn = (p1->y + (p2->x - p1->x)); + twin_dfixed_t An = yn - p1->y; + twin_dfixed_t Bn = p1->x - xn; + + twin_dfixed_t min = 0x7fffffff; for (p = 0; p < path->npoints; p++) { - twin_fixed_t x = path->points[p].x + p1->x; - twin_fixed_t y = path->points[p].y + p1->y; - twin_dfixed_t v = A * x + B * y + C; - if (v > max) + twin_fixed_t x = path->points[p].x; + twin_fixed_t y = path->points[p].y; + twin_dfixed_t vp = Ap * x + Bp * y; + twin_dfixed_t vn = An * x + Bn * y; + + if (vn < 0) vn = -vn; + if (vp > 0 && vn < min) { - max = v; + min = vn; best = p; } } @@ -87,23 +101,21 @@ _clockwise (twin_point_t *a1, return diff <= 0; } -#include <stdio.h> - void twin_path_convolve (twin_path_t *path, twin_path_t *stroke, twin_path_t *pen) { - twin_point_t *sp = stroke->points; - twin_point_t *pp = pen->points; - int ns = stroke->npoints; - int np = pen->npoints; - int start = _twin_path_leftmost (pen, - &sp[0], - &sp[_twin_path_step(stroke,0,1)]); - int ret = _twin_path_leftmost (pen, - &sp[ns-1], - &sp[_twin_path_step(stroke,ns-1,-1)]); + twin_point_t *sp = stroke->points; + twin_point_t *pp = pen->points; + int ns = stroke->npoints; + int np = pen->npoints; + twin_point_t *sp0 = &sp[0]; + twin_point_t *sp1 = &sp[_twin_path_step(stroke,0,1)]; + int start = _twin_path_leftpoint (pen, sp0, sp1); + twin_point_t *spn1 = &sp[ns-1]; + twin_point_t *spn2 = &sp[_twin_path_step(stroke,ns-1,-1)]; + int ret = _twin_path_leftpoint (pen, spn1, spn2); int p; int s; int starget; @@ -124,46 +136,55 @@ twin_path_convolve (twin_path_t *path, ptarget = ret; for (;;) { - int sn = _twin_path_step(stroke,s,inc); - int pn = _twin_path_step(pen,p,1); - int pm = _twin_path_step(pen,p,-1); - /* - * step along pen (forwards or backwards) or stroke as appropriate + * Convolve the edges */ - - if (!_clockwise (&sp[s],&sp[sn],&pp[p],&pp[pn])) - p = pn; - else if (_clockwise(&sp[s],&sp[sn],&pp[pm],&pp[p])) - p = pm; - else - s = sn; - - twin_path_draw (path, sp[s].x + pp[p].x, sp[s].y + pp[p].y); - - if (s == starget) + while (s != starget) { - if (closed) - { - twin_path_close (path); - if (inc == 1) - twin_path_move (path, sp[s].x + pp[p].x, sp[s].y + pp[p].y); - } + int sn = _twin_path_step(stroke,s,inc); + int pn = _twin_path_step(pen,p,1); + int pm = _twin_path_step(pen,p,-1); + + /* + * step along pen (forwards or backwards) or stroke as appropriate + */ + + if (!_clockwise (&sp[s],&sp[sn],&pp[p],&pp[pn])) + p = pn; + else if (_clockwise(&sp[s],&sp[sn],&pp[pm],&pp[p])) + p = pm; else + s = sn; + twin_path_draw (path, sp[s].x + pp[p].x, sp[s].y + pp[p].y); + } + + /* + * Finish this edge + */ + if (closed) + { + twin_path_close (path); + p = ptarget; + } + else + { + /* draw a cap */ + while (p != ptarget) { - /* draw a cap */ - while (p != ptarget) - { - if (++p == np) p = 0; - twin_path_draw (path, sp[s].x + pp[p].x, sp[s].y + pp[p].y); - } + if (++p == np) p = 0; + twin_path_draw (path, sp[s].x + pp[p].x, sp[s].y + pp[p].y); } - if (inc == -1) - break; - /* reach the end of the path? Go back the other way now */ - inc = -1; - starget = 0; - ptarget = start; } + if (inc == -1) + break; + + + /* reach the end of the path? Go back the other way now */ + inc = -1; + starget = 0; + ptarget = start; + + if (closed) + twin_path_move (path, sp[s].x + pp[p].x, sp[s].y + pp[p].y); } } diff --git a/twin_path.c b/twin_path.c index ce5c8f0..be44bf4 100644 --- a/twin_path.c +++ b/twin_path.c @@ -179,6 +179,7 @@ twin_path_circle (twin_path_t *path, twin_fixed_t radius) int sides = (4 * radius) / TWIN_FIXED_TOLERANCE; int n; twin_fixed_t cx, cy; + twin_dfixed_t dradius = (twin_dfixed_t) radius; int i; if (sides > 256) sides = 256; @@ -201,8 +202,8 @@ twin_path_circle (twin_path_t *path, twin_fixed_t radius) for (i = 1; i < (1 << n); i++) { - twin_fixed_t x = ((twin_dfixed_t) radius * _cos (i, n - 2)) >> 14; - twin_fixed_t y = ((twin_dfixed_t) radius * _sin (i, n - 2)) >> 14; + twin_fixed_t x = (dradius * _cos (i, n - 2) + (1 << 13)) >> 14; + twin_fixed_t y = (dradius * _sin (i, n - 2) + (1 << 13)) >> 14; twin_path_draw (path, cx + x, cy + y); } diff --git a/twin_poly.c b/twin_poly.c index eadce4c..12832c2 100644 --- a/twin_poly.c +++ b/twin_poly.c @@ -23,7 +23,7 @@ */ #include "twinint.h" - + static int _edge_compare_y (const void *a, const void *b) { @@ -43,6 +43,18 @@ _edge_step_by (twin_edge_t *edge, twin_fixed_t dy) edge->e = e % edge->dy; } +/* + * Returns the nearest grid coordinate no less than f + * + * Grid coordinates are at TWIN_POLY_STEP/2 + n*TWIN_POLY_STEP + */ + +static twin_fixed_t +_twin_fixed_grid_ceil (twin_fixed_t f) +{ + return ((f + (TWIN_POLY_START - 1)) & ~(TWIN_POLY_STEP - 1)) + TWIN_POLY_START; +} + int _twin_edge_build (twin_point_t *vertices, int nvertices, twin_edge_t *edges) { @@ -75,19 +87,16 @@ _twin_edge_build (twin_point_t *vertices, int nvertices, twin_edge_t *edges) bv = v; } - y = vertices[tv].y; - if (y < 0) - y = 0; - y = (y + 0x7) & ~0x7; + /* snap top to first grid point in pixmap */ + y = _twin_fixed_grid_ceil (vertices[tv].y); + if (y < TWIN_POLY_START) + y = TWIN_POLY_START; /* skip vertices which don't span a sample row */ if (y >= vertices[bv].y) continue; - /* Compute bresenham terms for 2x2 oversampling - * which is 8 sub-pixel steps per - */ - + /* Compute bresenham terms */ edges[e].dx = vertices[bv].x - vertices[tv].x; edges[e].dy = vertices[bv].y - vertices[tv].y; if (edges[e].dx >= 0) @@ -100,12 +109,13 @@ _twin_edge_build (twin_point_t *vertices, int nvertices, twin_edge_t *edges) edges[e].step_x = edges[e].inc_x * (edges[e].dx / edges[e].dy); edges[e].dx = edges[e].dx % edges[e].dy; - edges[e].top = y; + edges[e].top = vertices[tv].y; edges[e].bot = vertices[bv].y; edges[e].x = vertices[tv].x; edges[e].e = 0; + /* step to first grid point */ _edge_step_by (&edges[e], y - edges[e].top); edges[e].top = y; @@ -115,9 +125,6 @@ _twin_edge_build (twin_point_t *vertices, int nvertices, twin_edge_t *edges) return e; } -#define twin_fixed_ceil_half(f) (((f) + 7) & ~7) -#define TWIN_FIXED_HALF (TWIN_FIXED_ONE >> 1) - static void _span_fill (twin_pixmap_t *pixmap, twin_fixed_t y, @@ -134,11 +141,49 @@ _span_fill (twin_pixmap_t *pixmap, twin_a8_t *span = pixmap->p.a8 + row * pixmap->stride; twin_fixed_t x; twin_a16_t a; + twin_a16_t w; - for (x = twin_fixed_ceil_half (left); x < right; x += TWIN_FIXED_HALF) + /* clip to pixmap */ + if (left < 0) + left = 0; + + if (twin_fixed_trunc (right) > pixmap->width) + right = twin_int_to_fixed (pixmap->width); + + left = _twin_fixed_grid_ceil (left); + right = _twin_fixed_grid_ceil (right); + + /* check for empty */ + if (right < left) + return; + + x = left; + + /* starting address */ + span += twin_fixed_trunc(x); + + /* first pixel */ + if (x & TWIN_FIXED_HALF) { - a = (twin_a16_t) cover[(x >> 3) & 1] + (twin_a16_t) span[twin_fixed_trunc(x)]; - span[twin_fixed_trunc(x)] = twin_sat(a); + a = *span + (twin_a16_t) cover[1]; + *span++ = twin_sat (a); + x += TWIN_FIXED_HALF; + } + + /* middle pixels */ + w = cover[0] + cover[1]; + while (x < right - TWIN_FIXED_HALF) + { + a = *span + w; + *span++ = twin_sat (a); + x += TWIN_FIXED_ONE; + } + + /* last pixel */ + if (x < right) + { + a = *span + (twin_a16_t) cover[0]; + *span = twin_sat (a); } } @@ -156,10 +201,6 @@ _twin_edge_fill (twin_pixmap_t *pixmap, twin_edge_t *edges, int nedges) active = 0; for (;;) { - /* strip out dead edges */ - for (prev = &active; (a = *prev); prev = &(a->next)) - if (a->bot <= y) - *prev = a->next; /* add in new edges */ for (;e < nedges && edges[e].top <= y; e++) { @@ -169,8 +210,7 @@ _twin_edge_fill (twin_pixmap_t *pixmap, twin_edge_t *edges, int nedges) edges[e].next = *prev; *prev = &edges[e]; } - if (!active) - break; + /* walk this y value marking coverage */ w = 0; for (a = active; a; a = a->next) @@ -181,10 +221,29 @@ _twin_edge_fill (twin_pixmap_t *pixmap, twin_edge_t *edges, int nedges) if (w == 0) _span_fill (pixmap, y, x0, a->x); } - y += TWIN_FIXED_ONE >> 1; + + /* step down, clipping to pixmap */ + y += TWIN_POLY_STEP; + + if (twin_fixed_trunc (y) >= pixmap->height) + break; + + /* strip out dead edges */ + for (prev = &active; (a = *prev);) + { + if (a->bot <= y) + *prev = a->next; + else + prev = &a->next; + } + + /* check for all done */ + if (!active && e == nedges) + break; + /* step all edges */ for (a = active; a; a = a->next) - _edge_step_by (a, TWIN_FIXED_ONE >> 1); + _edge_step_by (a, TWIN_POLY_STEP); /* fix x sorting */ for (prev = &active; (a = *prev) && (n = a->next);) @@ -242,6 +242,10 @@ typedef struct _twin_edge { int winding; } twin_edge_t; +#define TWIN_POLY_STEP TWIN_FIXED_HALF +#define TWIN_POLY_START (TWIN_POLY_STEP / 2) +#define TWIN_POLY_CEIL(c) (((c) + (TWIN_POLY_STEP-1)) & ~(TWIN_POLY_STEP-1)) + /* * Pixmap must be in a8 format. */ @@ -27,6 +27,8 @@ #include <string.h> #include <stdio.h> +#define D(x) twin_double_to_fixed(x) + int main (int argc, char **argv) { @@ -50,31 +52,22 @@ main (int argc, char **argv) path = twin_path_create (); -#if 1 pen = twin_path_create (); - twin_path_circle (pen, twin_double_to_fixed (6)); + twin_path_circle (pen, D (3)); stroke = twin_path_create (); - twin_path_move (stroke, twin_double_to_fixed (10), twin_double_to_fixed (50)); - twin_path_draw (stroke, twin_double_to_fixed (30), twin_double_to_fixed (50)); - twin_path_draw (stroke, twin_double_to_fixed (10), twin_double_to_fixed (10)); + twin_path_move (stroke, D (10), D (40)); + twin_path_draw (stroke, D (40), D (40)); + twin_path_draw (stroke, D (10), D (10)); twin_path_convolve (path, stroke, pen); -#else - twin_path_move (path, twin_double_to_fixed (10), twin_double_to_fixed (10)); - twin_path_circle (path, twin_double_to_fixed (10)); -#endif twin_path_fill (alpha, path); twin_path_empty (path); - twin_path_move (path, - twin_double_to_fixed (50), twin_double_to_fixed (50)); - twin_path_curve (path, - twin_double_to_fixed (70), twin_double_to_fixed (70), - twin_double_to_fixed (80), twin_double_to_fixed (70), - twin_double_to_fixed (100), twin_double_to_fixed (50)); + twin_path_move (path, D (50), D (50)); + twin_path_curve (path, D (70), D (70), D (80), D (70), D (100), D (50)); twin_path_fill (alpha, path); @@ -85,13 +78,9 @@ main (int argc, char **argv) twin_composite (blue, 0, 0, &source, 0, 0, &mask, 0, 0, TWIN_OVER, 100, 100); - /* - twin_fill (blue, 0x80000080, TWIN_SOURCE, 0, 0, 100, 100); - twin_fill (blue, 0xff00c000, TWIN_SOURCE, 25, 25, 50, 50); - */ - twin_pixmap_move (red, 20, 20); - twin_pixmap_move (blue, 80, 80); -/* twin_pixmap_show (red, x11->screen, 0); */ + twin_pixmap_move (red, 0, 0); + twin_pixmap_move (blue, 100, 100); + twin_pixmap_show (red, x11->screen, 0); twin_pixmap_show (blue, x11->screen, 0); for (;;) { |