Hmm. Not sure this is right, but I'm giving it a try. Recognize closed

    paths and attempt to construct two disjoint paths as their convolution
    with the pen. This appears to break when the path has a radius of
    curvature smaller than the radius of the pen. I'm committing it to CVS
    mostly so I don't lose the code; I will shortly commit a patch which
    eliminates the check for a closed path.
Oh, one correct change is to _twin_path_leftpoint which used to try to be
    clever about point selection. Now that pens are forced to be convex,
    the correct point to use is the one furthest from the line.
Ignore subpaths containing a single point. Add 'twin_path_append' to glue
    one path into another.
Add debug output that shows vertices of polygons
Code to test convolution change mentioned above

6 files changed, 140 insertions, 62 deletions

diff --git a/ChangeLog b/ChangeLog
index 655eea1..9b51c7e 100644
--- a/ChangeLog
+++ b/ChangeLog
@@ -1,3 +1,31 @@
+2004-09-26  Keith Packard  <keithp@keithp.com>
+
+	* twin.h:
+	* twin_convolve.c: (_twin_path_leftpoint), (_twin_path_step),
+	(_twin_subpath_convolve):
+	Hmm.  Not sure this is right, but I'm giving it a try.
+	Recognize closed paths and attempt to construct two
+	disjoint paths as their convolution with the pen.  This
+	appears to break when the path has a radius of curvature smaller
+	than the radius of the pen.  I'm committing it to CVS mostly
+	so I don't lose the code; I will shortly commit a patch which
+	eliminates the check for a closed path.
+
+	Oh, one correct change is to _twin_path_leftpoint which used
+	to try to be clever about point selection.  Now that pens are
+	forced to be convex, the correct point to use is the one furthest
+	from the line.
+	
+	* twin_path.c: (twin_path_fill), (twin_path_append):
+	Ignore subpaths containing a single point.
+	Add 'twin_path_append' to glue one path into another.
+
+	* twin_poly.c: (_twin_edge_build), (_twin_edge_fill):
+	Add debug output that shows vertices of polygons
+	
+	* xtwin.c: (main):
+	Code to test convolution change mentioned above
+
 2004-09-25  Keith Packard  <keithp@keithp.com>
 
 	* twin_font.c:
diff --git a/twin.h b/twin.h
index 72fdb70..346f79d 100644
--- a/twin.h
+++ b/twin.h
@@ -47,7 +47,7 @@ typedef int32_t	    twin_dfixed_t;
 
 #define TWIN_FIXED_ONE		(0x10)
 #define TWIN_FIXED_HALF		(0x08)
-#define TWIN_FIXED_TOLERANCE	(1)
+#define TWIN_FIXED_TOLERANCE	(TWIN_FIXED_ONE >> 2)
 
 #define TWIN_FALSE  0
 #define TWIN_TRUE   1
@@ -275,6 +275,9 @@ twin_path_fill (twin_pixmap_t *pixmap, twin_path_t *path);
 void
 twin_path_empty (twin_path_t *path);
 
+void
+twin_path_append (twin_path_t *dst, twin_path_t *src);
+
 twin_path_t *
 twin_path_create (void);
 
diff --git a/twin_convolve.c b/twin_convolve.c
index cbddb9f..54b3c0f 100644
--- a/twin_convolve.c
+++ b/twin_convolve.c
@@ -25,66 +25,62 @@
 #include "twinint.h"
 	    
 /*
- * Find the point in path which is left of the line and
- * closest to a line normal to p1-p2 passing through p1
+ * Find the point in path which is furthest left of the line
  */
 static int
 _twin_path_leftpoint (twin_path_t  *path,
 		      twin_point_t *p1,
 		      twin_point_t *p2)
 {
+    twin_point_t    *points = path->points;
     int		    p;
     int		    best = 0;
     /*
-     * Along the path
+     * Normal form of the line is Ax + By + C = 0,
+     * these are the A and B factors.  As we're just comparing
+     * across x and y, the value of C isn't relevant
      */
     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;
+    twin_dfixed_t   max = -0x7fffffff;
     
     for (p = 0; p < path->npoints; p++)
     {
-	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;
+	twin_dfixed_t	vp = Ap * points[p].x + Bp * points[p].y;
 
-	if (vn < 0) vn = -vn;
-	if (vp > 0 && vn < min)
+	if (vp > max)
 	{
-	    min = vn;
+	    max = vp;
 	    best = p;
 	}
     }
     return best;
 }
 
+/*
+ * step along a path avoiding coincident points.  These
+ * occur in closed paths where the first and final points are
+ * always the same
+ */
+
 static int
-_twin_path_step (twin_path_t	*path,
+_twin_path_step (twin_point_t	*points,
+		 int		npoints,
 		 int		p,
 		 int		inc)
 {
     int n = p;
+
     for (;;)
     {
 	n += inc;
-	if (n < 0) n += path->npoints;
-	else if (n >= path->npoints) n -= path->npoints;
-	if (path->points[n].x != path->points[p].x || 
-	    path->points[n].y != path->points[p].y)
-	    return n;
+	if (n < 0) n += npoints;
+	else if (n >= npoints) n -= npoints;
+	if (points[n].x != points[p].x || points[n].y != points[p].y)
+	    break;
     }
-    return 0;
+    return n;
 }
 
 static int
@@ -124,6 +120,10 @@ _angle (twin_point_t *a, twin_point_t *b)
 #define DBGOUT(x...)
 #endif
 
+/*
+ * Convolve one subpath with a convex pen.  The result is
+ * a closed path.
+ */
 static void
 _twin_subpath_convolve (twin_path_t	*path,
 			twin_path_t	*stroke,
@@ -134,10 +134,10 @@ _twin_subpath_convolve (twin_path_t	*path,
     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)];
+    twin_point_t    *sp1  = &sp[_twin_path_step(sp,ns,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)];
+    twin_point_t    *spn2 = &sp[_twin_path_step(sp,ns,ns-1,-1)];
     int		    ret   = _twin_path_leftpoint (pen, spn1, spn2);
     int		    p;
     int		    s;
@@ -168,21 +168,27 @@ _twin_subpath_convolve (twin_path_t	*path,
     
     /* step along the path first */
     inc = 1;
-    starget = ns - 1;
     if (closed)
+    {
+	starget = ns-1;
 	ptarget = start;
+    }
     else
+    {
+	starget = ns-1;
 	ptarget = ret;
+    }
     for (;;)
     {
 	/*
 	 * Convolve the edges
 	 */
-	while (s != starget)
+	do
 	{
-	    int	sn = _twin_path_step(stroke,s,inc);
-	    int	pn = _twin_path_step(pen,p,1);
-	    int	pm = _twin_path_step(pen,p,-1);
+	    int	sn = _twin_path_step(sp,ns,s,inc);
+	    int	pn = (p == np - 1) ? 0 : p + 1;
+	    int	pm = (p == 0) ? np - 1 : p - 1;
+	    int o;
     
 	    /*
 	     * step along pen (forwards or backwards) or stroke as appropriate
@@ -192,12 +198,14 @@ _twin_subpath_convolve (twin_path_t	*path,
 		    _angle (&sp[s], &sp[sn]),
 		    _angle (&pp[p], &pp[pn]),
 		    _angle (&pp[pm], &pp[p]));
-	    if (_around_order (&sp[s],&sp[sn],&pp[p],&pp[pn]) > 0)
+	    o = _around_order (&sp[s],&sp[sn],&pp[p],&pp[pn]);
+	    if (o > 0 || (o == 0 && (closed && s == starget)))
 	    {
 		DBGOUT ("+pen:   ");
 		p = pn;
 	    }
-	    else if (_around_order (&sp[s],&sp[sn],&pp[pm],&pp[p]) < 0)
+	    else if ((s == starget && closed)
+		     || _around_order (&sp[s],&sp[sn],&pp[pm],&pp[p]) < 0)
 	    {
 		DBGOUT ("-pen:   ");
 		p = pm;
@@ -212,41 +220,49 @@ _twin_subpath_convolve (twin_path_t	*path,
 		    p, F(pp[p].x), F(pp[p].y),
 		    F(sp[s].x + pp[p].x), F(sp[s].y + pp[p].y));
 	    twin_path_draw (path, sp[s].x + pp[p].x, sp[s].y + pp[p].y);
-	}
+	} while (s != starget || (closed && p != ptarget));
 	
-	/* draw a cap */
-	while (p != ptarget)
-	{
-	    if (++p == np) p = 0;
-	    DBGOUT("cap:    ");
-	    DBGOUT ("s%02d (%9.4f, %9.4f), p%02d (%9.4f, %9.4f): %9.4f, %9.4f\n",
-		    s, F(sp[s].x), F(sp[s].y),
-		    p, F(pp[p].x), F(pp[p].y),
-		    F(sp[s].x + pp[p].x), F(sp[s].y + pp[p].y));
-	    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);
+	}
+	else
+	{
+	    /* draw a cap */
+	    while (p != ptarget)
+	    {
+		if (++p == np) p = 0;
+		DBGOUT("cap:    ");
+		DBGOUT ("s%02d (%9.4f, %9.4f), p%02d (%9.4f, %9.4f): %9.4f, %9.4f\n",
+			s, F(sp[s].x), F(sp[s].y),
+			p, F(pp[p].x), F(pp[p].y),
+			F(sp[s].x + pp[p].x), F(sp[s].y + pp[p].y));
+		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 (closed)
 	{
 	    p = ret;
 	    ptarget = ret;
+	    starget = 0;
 	    twin_path_move (path, sp[s].x + pp[p].x, sp[s].y + pp[p].y);
 	}
 	else
+	{
 	    ptarget = start;
+	    starget = 0;
+	}
     }
 }
 
diff --git a/twin_path.c b/twin_path.c
index 232f5aa..1578485 100644
--- a/twin_path.c
+++ b/twin_path.c
@@ -273,7 +273,7 @@ twin_path_fill (twin_pixmap_t *pixmap, twin_path_t *path)
 	else
 	    sublen = path->sublen[s];
 	npoints = sublen - p;
-	if (npoints)
+	if (npoints > 1)
 	{
 	    n = _twin_edge_build (path->points + p, npoints, edges + nedges);
 	    p = sublen;
@@ -291,6 +291,23 @@ twin_path_empty (twin_path_t *path)
     path->nsublen = 0;
 }
 
+void
+twin_path_append (twin_path_t *dst, twin_path_t *src)
+{
+    int	    p;
+    int	    s = 0;
+
+    for (p = 0; p < src->npoints; p++)
+    {
+	if (s < src->nsublen && p == src->sublen[s])
+	{
+	    twin_path_close (dst);
+	    s++;
+	}
+	twin_path_draw (dst, src->points[p].x, src->points[p].y);
+    }
+}
+
 twin_path_t *
 twin_path_create (void)
 {
diff --git a/twin_poly.c b/twin_poly.c
index 85d22f5..4a15cbd 100644
--- a/twin_poly.c
+++ b/twin_poly.c
@@ -64,6 +64,14 @@ _twin_fixed_grid_ceil (twin_fixed_t f)
     return ((f + (TWIN_POLY_START - 1)) & ~(TWIN_POLY_STEP - 1)) + TWIN_POLY_START;
 }
 
+#if 0
+#include <stdio.h>
+#define F(x)	twin_fixed_to_double(x)
+#define DBGOUT(x...)	printf(x)
+#else
+#define DBGOUT(x...)
+#endif
+
 int
 _twin_edge_build (twin_point_t *vertices, int nvertices, twin_edge_t *edges)
 {
@@ -82,6 +90,8 @@ _twin_edge_build (twin_point_t *vertices, int nvertices, twin_edge_t *edges)
 	if (vertices[v].y == vertices[nv].y)
 	    continue;
 
+	DBGOUT ("Vertex: %9.4f, %9.4f\n", F(vertices[v].x), F(vertices[v].y));
+
 	/* figure winding */
 	if (vertices[v].y < vertices[nv].y)
 	{
@@ -244,14 +254,6 @@ _span_fill (twin_pixmap_t   *pixmap,
     }
 }
 
-#if 0
-#include <stdio.h>
-#define F(x)	twin_fixed_to_double(x)
-#define DBGOUT(x...)	printf(x)
-#else
-#define DBGOUT(x...)
-#endif
-
 void
 _twin_edge_fill (twin_pixmap_t *pixmap, twin_edge_t *edges, int nedges)
 {
@@ -287,7 +289,10 @@ _twin_edge_fill (twin_pixmap_t *pixmap, twin_edge_t *edges, int nedges)
 		x0 = a->x;
 	    w += a->winding;
 	    if (w == 0)
+	    {
+		DBGOUT (" F ");
 		_span_fill (pixmap, y, x0, a->x);
+	    }
 	}
 	DBGOUT ("\n");
 	
diff --git a/xtwin.c b/xtwin.c
index 626366b..58d178e 100644
--- a/xtwin.c
+++ b/xtwin.c
@@ -76,6 +76,15 @@ main (int argc, char **argv)
     }
 #endif
 #if 1
+    stroke = twin_path_create ();
+    twin_path_move (stroke, D(-1), D(7));
+    twin_path_string (stroke, D(20), D(20), TWIN_TEXT_BOLD, ".");
+/*    twin_path_convolve (path, stroke, pen); */
+    twin_path_append (path, stroke);
+    twin_path_destroy (stroke);
+#endif
+    
+#if 0
     fx = D(3);
     fy = 0;
     for (g = 8; g < 30; g += 4)
@@ -137,7 +146,7 @@ main (int argc, char **argv)
 
     twin_fill (blue, 0x00000000, TWIN_SOURCE, 0, 0, 100, 100);
 
-#if 1
+#if 0
     path = twin_path_create ();
 
     stroke = twin_path_create ();
@@ -194,7 +203,7 @@ main (int argc, char **argv)
     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);
+    twin_pixmap_show (blue, x11->screen, 0);
     had_motion = TWIN_FALSE;
     for (;;)
     {