Add a few definitions

Find pen starting point as closest to the normal to the path. Restructure
    convolve loop to be easier to understand
Round circle coordinates instead of truncating them
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.
Stroke a path.

7 files changed, 210 insertions, 111 deletions

diff --git a/ChangeLog b/ChangeLog
index 051a94f..d432886 100644
--- a/ChangeLog
+++ b/ChangeLog
@@ -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),
diff --git a/twin.h b/twin.h
index 183d784..b8e1c88 100644
--- a/twin.h
+++ b/twin.h
@@ -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);)
diff --git a/twinint.h b/twinint.h
index 0fcd202..cc5c0c7 100644
--- a/twinint.h
+++ b/twinint.h
@@ -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.
  */
diff --git a/xtwin.c b/xtwin.c
index 01d57b4..b049a78 100644
--- a/xtwin.c
+++ b/xtwin.c
@@ -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 (;;)
     {