Add convolution. Pen starting position needs work.

Move shared geometric functions to new file
Add twin_path_circle to generate pens. Fix path edge generator to handle
    last subpath right.
Skip vertices which don't span a sample row
test convolutions
Add .cvsignore file
Mention path primitives
Add paths
Eliminate some unused variables.
Simple path construction
Anti-aliased polygon fill code
Change twin_bool to twin_bool_t
Append cubic Bézier splines to paths
Test paths

13 files changed, 1112 insertions, 8 deletions

diff --git a/ChangeLog b/ChangeLog
index e69de29..051a94f 100644
--- a/ChangeLog
+++ b/ChangeLog
@@ -0,0 +1,61 @@
+2004-09-21  Keith Packard  <keithp@keithp.com>
+
+	* Makefile.am:
+	* twin.h:
+	* twin_convolve.c: (_twin_path_leftmost), (_twin_path_step),
+	(_clockwise), (twin_path_convolve):
+	Add convolution.  Pen starting position needs work.
+	
+	* twin_geom.c: (_twin_distance_to_point_squared),
+	(_twin_distance_to_line_squared):
+	* twin_spline.c: (_twin_spline_error_squared), (twin_path_curve):
+	* twinint.h:
+	Move shared geometric functions to new file
+	
+	* twin_path.c: (_sin), (_cos), (twin_path_circle),
+	(twin_path_fill):
+	Add twin_path_circle to generate pens.
+	Fix path edge generator to handle last subpath right.
+
+	* twin_poly.c: (_twin_edge_build):
+	Skip vertices which don't span a sample row
+	
+	* xtwin.c: (main):
+	test convolutions
+
+2004-09-20  Keith Packard  <keithp@keithp.com>
+
+	* .cvsignore:
+	Add .cvsignore file
+	
+	* architecture:
+	Mention path primitives
+	* Makefile.am:
+	* twin.h:
+	* twinint.h:
+	Add paths
+	
+	* twin_draw.c: (twin_composite):
+	Eliminate some unused variables.
+	
+	* twin_path.c: (twin_path_move), (twin_path_draw),
+	(twin_path_close), (twin_path_fill), (twin_path_empty),
+	(twin_path_create), (twin_path_destroy):
+	Simple path construction
+	
+	* twin_poly.c: (_edge_compare_y), (_edge_step_by), (_dump_edge),
+	(_twin_edge_build), (_span_fill), (_twin_edge_fill),
+	(twin_polygon):
+	Anti-aliased polygon fill code
+	
+	* twin_screen.c:
+	Change twin_bool to twin_bool_t
+	
+	* twin_spline.c: (_lerp_half), (_de_casteljau),
+	(_distance_squared_to_point), (_distance_squared_to_segment),
+	(_twin_spline_error_squared), (_twin_spline_decompose),
+	(twin_path_curve):
+	Append cubic Bézier splines to paths
+
+	* xtwin.c: (main):
+	Test paths
diff --git a/Makefile.am b/Makefile.am
index a673b9e..56ab1a2 100644
--- a/Makefile.am
+++ b/Makefile.am
@@ -16,10 +16,15 @@ bin_PROGRAMS = xtwin
 
 xtwin_SOURCES = \
 	twin.h \
+	twin_convolve.c \
 	twin_draw.c \
+	twin_geom.c \
+	twin_path.c \
 	twin_pixmap.c \
+	twin_poly.c \
 	twin_primitive.c \
 	twin_screen.c \
+	twin_spline.c \
 	twin_x11.c \
 	twinint.h \
 	xtwin.c
diff --git a/architecture b/architecture
index dd095fd..8834dd9 100644
--- a/architecture
+++ b/architecture
@@ -52,3 +52,9 @@ all of the windows the screen is white.
 Geometry can be displayed by computing an appropriate A8 pixmap and
 compositing the result to a pixmap.
 
+7. Paths
+
+To draw the A8 pixmap mentioned above, use a combination of move, draw
+and curve primitives to construct a path and then fill it.  To outline a
+path, use the convolution operator to convolve a pen with the path to
+construct a closed path surrounding the stroke.
diff --git a/twin.h b/twin.h
index 1154790..183d784 100644
--- a/twin.h
+++ b/twin.h
@@ -29,9 +29,21 @@
 #include <stdint.h>
 
 typedef uint8_t	    twin_a8_t;
+typedef uint16_t    twin_a16_t;
 typedef uint16_t    twin_rgb16_t;
 typedef uint32_t    twin_argb32_t;
-typedef int	    twin_bool;
+typedef int	    twin_bool_t;
+typedef int16_t	    twin_fixed_t;   /* 12.4 format */
+typedef int32_t	    twin_dfixed_t;
+
+#define twin_fixed_floor(f) ((((f) < 0) ? ((f) + 0xf) : (f)) >> 4)
+#define twin_fixed_trunc(f) ((f) >> 4)
+
+#define twin_double_to_fixed(d)	((twin_fixed_t) ((d) * 16.0))
+#define twin_fixed_to_double(f)	((double) (f) / 16.0)
+
+#define TWIN_FIXED_ONE		(0x10)
+#define TWIN_FIXED_TOLERANCE	(TWIN_FIXED_ONE >> 1)
 
 #define TWIN_FALSE  0
 #define TWIN_TRUE   1
@@ -133,6 +145,24 @@ typedef struct _twin_operand {
 typedef enum { TWIN_OVER, TWIN_SOURCE } twin_operator_t;
 
 /*
+ * A (fixed point) point
+ */
+
+typedef struct _twin_point {
+    twin_fixed_t    x, y;
+} twin_point_t;
+
+typedef struct _twin_path twin_path_t;
+
+/*
+ * twin_convolve.c
+ */
+void
+twin_path_convolve (twin_path_t	*dest,
+		    twin_path_t	*stroke,
+		    twin_path_t	*pen);
+
+/*
  * twin_draw.c
  */
 
@@ -160,6 +190,34 @@ twin_fill (twin_pixmap_t    *dst,
 	   int		    height);
 
 /*
+ * twin_path.c
+ */
+
+void 
+twin_path_move (twin_path_t *path, twin_fixed_t x, twin_fixed_t y);
+
+void
+twin_path_draw (twin_path_t *path, twin_fixed_t x, twin_fixed_t y);
+
+void
+twin_path_circle(twin_path_t *path, twin_fixed_t radius);
+
+void
+twin_path_close (twin_path_t *path);
+
+void
+twin_path_fill (twin_pixmap_t *pixmap, twin_path_t *path);
+
+void
+twin_path_empty (twin_path_t *path);
+
+twin_path_t *
+twin_path_create (void);
+
+void
+twin_path_destroy (twin_path_t *path);
+
+/*
  * twin_pixmap.c
  */
 
@@ -188,6 +246,12 @@ twin_pointer_t
 twin_pixmap_pointer (twin_pixmap_t *pixmap, int x, int y);
 
 /*
+ * twin_poly.c
+ */
+void
+twin_polygon (twin_pixmap_t *pixmap, twin_point_t *vertices, int nvertices);
+
+/*
  * twin_screen.c
  */
 
@@ -207,13 +271,25 @@ twin_screen_damage (twin_screen_t *screen,
 void
 twin_screen_resize (twin_screen_t *screen, int width, int height);
 
-twin_bool
+twin_bool_t
 twin_screen_damaged (twin_screen_t *screen);
 
 void
 twin_screen_update (twin_screen_t *screen);
 
-/* twin_x11.c */
+/*
+ * twin_spline.c
+ */
+
+void
+twin_path_curve (twin_path_t	*path,
+		 twin_fixed_t	x1, twin_fixed_t y1,
+		 twin_fixed_t	x2, twin_fixed_t y2,
+		 twin_fixed_t	x3, twin_fixed_t y3);
+
+/*
+ * twin_x11.c 
+ */
 
 #include <X11/Xlib.h>
 
diff --git a/twin_convolve.c b/twin_convolve.c
new file mode 100644
index 0000000..dab05d2
--- /dev/null
+++ b/twin_convolve.c
@@ -0,0 +1,169 @@
+/*
+ * $Id$
+ *
+ * Copyright © 2004 Keith Packard
+ *
+ * Permission to use, copy, modify, distribute, and sell this software and its
+ * documentation for any purpose is hereby granted without fee, provided that
+ * the above copyright notice appear in all copies and that both that
+ * copyright notice and this permission notice appear in supporting
+ * documentation, and that the name of Keith Packard not be used in
+ * advertising or publicity pertaining to distribution of the software without
+ * specific, written prior permission.  Keith Packard makes no
+ * representations about the suitability of this software for any purpose.  It
+ * is provided "as is" without express or implied warranty.
+ *
+ * KEITH PACKARD DISCLAIMS ALL WARRANTIES WITH REGARD TO THIS SOFTWARE,
+ * INCLUDING ALL IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS, IN NO
+ * EVENT SHALL KEITH PACKARD BE LIABLE FOR ANY SPECIAL, INDIRECT OR
+ * CONSEQUENTIAL DAMAGES OR ANY DAMAGES WHATSOEVER RESULTING FROM LOSS OF USE,
+ * DATA OR PROFITS, WHETHER IN AN ACTION OF CONTRACT, NEGLIGENCE OR OTHER
+ * TORTIOUS ACTION, ARISING OUT OF OR IN CONNECTION WITH THE USE OR
+ * PERFORMANCE OF THIS SOFTWARE.
+ */
+
+#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)
+ */
+static int
+_twin_path_leftmost (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;
+    
+    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)
+	{
+	    max = v;
+	    best = p;
+	}
+    }
+    return best;
+}
+
+static int
+_twin_path_step (twin_path_t	*path,
+		 int		p,
+		 int		inc)
+{
+    for (;;)
+    {
+	int n = p + 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;
+    }
+    return 0;
+}
+
+static twin_bool_t
+_clockwise (twin_point_t    *a1,
+	    twin_point_t    *a2,
+	    twin_point_t    *b1,
+	    twin_point_t    *b2)
+{
+    twin_dfixed_t   adx = (a2->x - a1->x);
+    twin_dfixed_t   ady = (a2->y - a1->y);
+    twin_dfixed_t   bdx = (b2->x - b1->x);
+    twin_dfixed_t   bdy = (b2->y - b1->y);
+    twin_dfixed_t   diff = (ady * bdx - bdy * adx);
+
+    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)]);
+    int		    p;
+    int		    s;
+    int		    starget;
+    int		    ptarget;
+    int		    inc;
+    twin_bool_t	    closed = TWIN_FALSE;
+
+    if (sp[0].x == sp[ns - 1].x && sp[0].y == sp[ns - 1].y)
+	closed = TWIN_TRUE;
+    
+    s = 0;
+    p = start;
+    twin_path_draw (path, sp[s].x + pp[p].x, sp[s].y + pp[p].y);
+    
+    /* step along the path first */
+    inc = 1;
+    starget = ns - 1;
+    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
+	 */
+	 
+	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)
+	{
+	    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);
+	    }
+	    else
+	    {
+		/* 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 (inc == -1)
+		break;
+	    /* reach the end of the path?  Go back the other way now */
+	    inc = -1;
+	    starget = 0;
+	    ptarget = start;
+	}
+    }
+}
diff --git a/twin_draw.c b/twin_draw.c
index b7c7a1f..00485a4 100644
--- a/twin_draw.c
+++ b/twin_draw.c
@@ -280,9 +280,6 @@ twin_composite (twin_pixmap_t	*dst,
 	twin_src_msk_op	op;
 	twin_source_u   s, m;
 	int		sdx, sdy, mdx, mdy;
-	twin_argb32_t	*src_tmp;
-	twin_argb32_t	*msk_tmp;
-	twin_argb32_t	*dst_tmp;
 	
 	sdx = src_x - dst_x;
 	sdy = src_y - dst_y;
diff --git a/twin_geom.c b/twin_geom.c
new file mode 100644
index 0000000..21fa694
--- /dev/null
+++ b/twin_geom.c
@@ -0,0 +1,65 @@
+/*
+ * $Id$
+ *
+ * Copyright © 2004 Keith Packard
+ *
+ * Permission to use, copy, modify, distribute, and sell this software and its
+ * documentation for any purpose is hereby granted without fee, provided that
+ * the above copyright notice appear in all copies and that both that
+ * copyright notice and this permission notice appear in supporting
+ * documentation, and that the name of Keith Packard not be used in
+ * advertising or publicity pertaining to distribution of the software without
+ * specific, written prior permission.  Keith Packard makes no
+ * representations about the suitability of this software for any purpose.  It
+ * is provided "as is" without express or implied warranty.
+ *
+ * KEITH PACKARD DISCLAIMS ALL WARRANTIES WITH REGARD TO THIS SOFTWARE,
+ * INCLUDING ALL IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS, IN NO
+ * EVENT SHALL KEITH PACKARD BE LIABLE FOR ANY SPECIAL, INDIRECT OR
+ * CONSEQUENTIAL DAMAGES OR ANY DAMAGES WHATSOEVER RESULTING FROM LOSS OF USE,
+ * DATA OR PROFITS, WHETHER IN AN ACTION OF CONTRACT, NEGLIGENCE OR OTHER
+ * TORTIOUS ACTION, ARISING OUT OF OR IN CONNECTION WITH THE USE OR
+ * PERFORMANCE OF THIS SOFTWARE.
+ */
+
+#include "twinint.h"
+
+twin_dfixed_t
+_twin_distance_to_point_squared (twin_point_t *a, twin_point_t *b)
+{
+    twin_dfixed_t dx = (b->x - a->x);
+    twin_dfixed_t dy = (b->y - a->y);
+
+    return dx*dx + dy*dy;
+}
+
+twin_dfixed_t
+_twin_distance_to_line_squared (twin_point_t *p, twin_point_t *p1, twin_point_t *p2)
+{
+    /*
+     * Convert to normal form (AX + BY + C = 0)
+     *
+     * (X - x1) * (y2 - y1) = (Y - y1) * (x2 - x1)
+     *
+     * X * (y2 - y1) - Y * (x2 - x1) - x1 * (y2 - y1) + y1 * (x2 - x1) = 0
+     *
+     * A = (y2 - y1)
+     * B = (x1 - x2)
+     * C = (y1x2 - x1y2)
+     *
+     * distance² = (AX + BC + C)² / (A² + B²)
+     */
+    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   den, num;
+
+    num = A * p->x + B * p->y + C;
+    den = A * A + B * B;
+    if (den == 0 || num >= 0x10000)
+	return _twin_distance_to_point_squared (p, p1);
+    else
+	return (num * num) / den;
+}
+
diff --git a/twin_path.c b/twin_path.c
new file mode 100644
index 0000000..ce5c8f0
--- /dev/null
+++ b/twin_path.c
@@ -0,0 +1,274 @@
+/*
+ * $Id$
+ *
+ * Copyright © 2004 Keith Packard
+ *
+ * Permission to use, copy, modify, distribute, and sell this software and its
+ * documentation for any purpose is hereby granted without fee, provided that
+ * the above copyright notice appear in all copies and that both that
+ * copyright notice and this permission notice appear in supporting
+ * documentation, and that the name of Keith Packard not be used in
+ * advertising or publicity pertaining to distribution of the software without
+ * specific, written prior permission.  Keith Packard makes no
+ * representations about the suitability of this software for any purpose.  It
+ * is provided "as is" without express or implied warranty.
+ *
+ * KEITH PACKARD DISCLAIMS ALL WARRANTIES WITH REGARD TO THIS SOFTWARE,
+ * INCLUDING ALL IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS, IN NO
+ * EVENT SHALL KEITH PACKARD BE LIABLE FOR ANY SPECIAL, INDIRECT OR
+ * CONSEQUENTIAL DAMAGES OR ANY DAMAGES WHATSOEVER RESULTING FROM LOSS OF USE,
+ * DATA OR PROFITS, WHETHER IN AN ACTION OF CONTRACT, NEGLIGENCE OR OTHER
+ * TORTIOUS ACTION, ARISING OUT OF OR IN CONNECTION WITH THE USE OR
+ * PERFORMANCE OF THIS SOFTWARE.
+ */
+
+#include "twinint.h"
+
+void 
+twin_path_move (twin_path_t *path, twin_fixed_t x, twin_fixed_t y)
+{
+    if (path->npoints)
+	twin_path_close (path);
+    twin_path_draw (path, x, y);
+}
+
+void
+twin_path_draw (twin_path_t *path, twin_fixed_t x, twin_fixed_t y)
+{
+    if (path->npoints == path->size_points)
+    {
+	int		size_points;
+	twin_point_t	*points;
+	
+	if (path->size_points > 0)
+	    size_points = path->size_points * 2;
+	else
+	    size_points = 16;
+	if (path->points)
+	    points = realloc (path->points, size_points * sizeof (twin_point_t));
+	else
+	    points = malloc (size_points * sizeof (twin_point_t));
+	if (!points)
+	    return;
+	path->points = points;
+	path->size_points = size_points;
+    }
+    path->points[path->npoints].x = x;
+    path->points[path->npoints].y = y;
+    path->npoints++;
+}
+
+void
+twin_path_close (twin_path_t *path)
+{
+    if (path->nsublen == path->size_sublen)
+    {
+	int	size_sublen;
+	int	*sublen;
+	
+	if (path->size_sublen > 0)
+	    size_sublen = path->size_sublen * 2;
+	else
+	    size_sublen = 16;
+	if (path->sublen)
+	    sublen = realloc (path->sublen, size_sublen * sizeof (int));
+	else
+	    sublen = malloc (size_sublen * sizeof (int));
+	if (!sublen)
+	    return;
+	path->sublen = sublen;
+	path->size_sublen = size_sublen;
+    }
+    path->sublen[path->nsublen] = path->npoints;
+    path->nsublen++;
+}
+
+static const twin_fixed_t _sin_table[] = {
+    0x0000, /*  0 */
+    0x0192, /*  1 */
+    0x0324, /*  2 */
+    0x04b5, /*  3 */
+    0x0646, /*  4 */
+    0x07d6, /*  5 */
+    0x0964, /*  6 */
+    0x0af1, /*  7 */
+    0x0c7c, /*  8 */
+    0x0e06, /*  9 */
+    0x0f8d, /* 10 */
+    0x1112, /* 11 */
+    0x1294, /* 12 */
+    0x1413, /* 13 */
+    0x1590, /* 14 */
+    0x1709, /* 15 */
+    0x187e, /* 16 */
+    0x19ef, /* 17 */
+    0x1b5d, /* 18 */
+    0x1cc6, /* 19 */
+    0x1e2b, /* 20 */
+    0x1f8c, /* 21 */
+    0x20e7, /* 22 */
+    0x223d, /* 23 */
+    0x238e, /* 24 */
+    0x24da, /* 25 */
+    0x2620, /* 26 */
+    0x2760, /* 27 */
+    0x289a, /* 28 */
+    0x29ce, /* 29 */
+    0x2afb, /* 30 */
+    0x2c21, /* 31 */
+    0x2d41, /* 32 */
+    0x2e5a, /* 33 */
+    0x2f6c, /* 34 */
+    0x3076, /* 35 */
+    0x3179, /* 36 */
+    0x3274, /* 37 */
+    0x3368, /* 38 */
+    0x3453, /* 39 */
+    0x3537, /* 40 */
+    0x3612, /* 41 */
+    0x36e5, /* 42 */
+    0x37b0, /* 43 */
+    0x3871, /* 44 */
+    0x392b, /* 45 */
+    0x39db, /* 46 */
+    0x3a82, /* 47 */
+    0x3b21, /* 48 */
+    0x3bb6, /* 49 */
+    0x3c42, /* 50 */
+    0x3cc5, /* 51 */
+    0x3d3f, /* 52 */
+    0x3daf, /* 53 */
+    0x3e15, /* 54 */
+    0x3e72, /* 55 */
+    0x3ec5, /* 56 */
+    0x3f0f, /* 57 */
+    0x3f4f, /* 58 */
+    0x3f85, /* 59 */
+    0x3fb1, /* 60 */
+    0x3fd4, /* 61 */
+    0x3fec, /* 62 */
+    0x3ffb, /* 63 */
+    0x4000, /* 64 */
+};
+
+static twin_fixed_t
+_sin (int i, int n) 
+{
+    int	e = i << (6 - n);
+    twin_fixed_t    v;
+    
+    e &= 0xff;
+    if (e & 0x40)
+	v = _sin_table[0x40 - (e & 0x3f)];
+    else
+	v = _sin_table[e & 0x3f];
+    if (e & 0x80)
+	v = -v;
+    return v;
+}
+
+static twin_fixed_t
+_cos (int i, int n)
+{
+    return _sin (i + (0x40 >> (6 - n)), n);
+}
+
+void
+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;
+    int		    i;
+
+    if (sides > 256) sides = 256;
+    n = 2;
+    while ((1 << n) < sides)
+	n++;
+
+    if (!path->npoints)
+    {
+	cx = 0;
+	cy = 0;
+    }
+    else
+    {
+	cx = path->points[path->npoints - 1].x;
+	cy = path->points[path->npoints - 1].y;
+    }
+
+    twin_path_move (path, cx + radius, cy);
+
+    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_path_draw (path, cx + x, cy + y);
+    }
+    twin_path_close (path);
+}
+
+void
+twin_path_fill (twin_pixmap_t *pixmap, twin_path_t *path)
+{
+    twin_edge_t	*edges;
+    int		nedges, n;
+    int		nalloc;
+    int		s;
+    int		p;
+
+    nalloc = path->npoints + path->nsublen + 1;
+    edges = malloc (sizeof (twin_edge_t) * nalloc);
+    p = 0;
+    nedges = 0;
+    for (s = 0; s <= path->nsublen; s++)
+    {
+	int sublen;
+	int npoints;
+	
+	if (s == path->nsublen)
+	    sublen = path->npoints;
+	else
+	    sublen = path->sublen[s];
+	npoints = sublen - p;
+	if (npoints)
+	{
+	    n = _twin_edge_build (path->points + p, npoints, edges + nedges);
+	    p = sublen;
+	    nedges += n;
+	}
+    }
+    _twin_edge_fill (pixmap, edges, nedges);
+    free (edges);
+}
+
+void
+twin_path_empty (twin_path_t *path)
+{
+    path->npoints = 0;
+    path->nsublen = 0;
+}
+
+twin_path_t *
+twin_path_create (void)
+{
+    twin_path_t	*path;
+
+    path = malloc (sizeof (twin_path_t));
+    path->npoints = path->size_points = 0;
+    path->nsublen = path->size_sublen = 0;
+    path->points = 0;
+    path->sublen = 0;
+    return path;
+}
+
+void
+twin_path_destroy (twin_path_t *path)
+{
+    if (path->points)
+	free (path->points);
+    if (path->sublen)
+	free (path->sublen);
+    free (path);
+}
diff --git a/twin_poly.c b/twin_poly.c
new file mode 100644
index 0000000..eadce4c
--- /dev/null
+++ b/twin_poly.c
@@ -0,0 +1,220 @@
+/*
+ * $Id$
+ *
+ * Copyright © 2004 Keith Packard
+ *
+ * Permission to use, copy, modify, distribute, and sell this software and its
+ * documentation for any purpose is hereby granted without fee, provided that
+ * the above copyright notice appear in all copies and that both that
+ * copyright notice and this permission notice appear in supporting
+ * documentation, and that the name of Keith Packard not be used in
+ * advertising or publicity pertaining to distribution of the software without
+ * specific, written prior permission.  Keith Packard makes no
+ * representations about the suitability of this software for any purpose.  It
+ * is provided "as is" without express or implied warranty.
+ *
+ * KEITH PACKARD DISCLAIMS ALL WARRANTIES WITH REGARD TO THIS SOFTWARE,
+ * INCLUDING ALL IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS, IN NO
+ * EVENT SHALL KEITH PACKARD BE LIABLE FOR ANY SPECIAL, INDIRECT OR
+ * CONSEQUENTIAL DAMAGES OR ANY DAMAGES WHATSOEVER RESULTING FROM LOSS OF USE,
+ * DATA OR PROFITS, WHETHER IN AN ACTION OF CONTRACT, NEGLIGENCE OR OTHER
+ * TORTIOUS ACTION, ARISING OUT OF OR IN CONNECTION WITH THE USE OR
+ * PERFORMANCE OF THIS SOFTWARE.
+ */
+
+#include "twinint.h"
+
+static int
+_edge_compare_y (const void *a, const void *b)
+{
+    const twin_edge_t	*ae = a;
+    const twin_edge_t	*be = b;
+
+    return (int) (ae->top - be->top);
+}
+
+static void
+_edge_step_by (twin_edge_t  *edge, twin_fixed_t dy)
+{
+    twin_dfixed_t   e;
+    
+    e = edge->e + (twin_dfixed_t) dy * edge->dx;
+    edge->x += edge->step_x * dy + edge->inc_x * (e / edge->dy);
+    edge->e = e % edge->dy;
+}
+
+int
+_twin_edge_build (twin_point_t *vertices, int nvertices, twin_edge_t *edges)
+{
+    int		    v, nv;
+    int		    tv, bv;
+    int		    e;
+    twin_fixed_t    y;
+
+    e = 0;
+    for (v = 0; v < nvertices; v++)
+    {
+	nv = v + 1;
+	if (nv == nvertices) nv = 0;
+	
+	/* skip horizontal edges */
+	if (vertices[v].y == vertices[nv].y)
+	    continue;
+
+	/* figure winding */
+	if (vertices[v].y < vertices[nv].y)
+	{
+	    edges[e].winding = 1;
+	    tv = v;
+	    bv = nv;
+	}
+	else
+	{
+	    edges[e].winding = -1;
+	    tv = nv;
+	    bv = v;
+	}
+
+	y = vertices[tv].y;
+	if (y < 0)
+	    y = 0;
+	y = (y + 0x7) & ~0x7;
+	
+	/* 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 
+	 */
+
+	edges[e].dx = vertices[bv].x - vertices[tv].x;
+	edges[e].dy = vertices[bv].y - vertices[tv].y;
+	if (edges[e].dx >= 0)
+	    edges[e].inc_x = 1;
+	else
+	{
+	    edges[e].inc_x = -1;
+	    edges[e].dx = -edges[e].dx;
+	}
+	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].bot = vertices[bv].y;
+
+	edges[e].x = vertices[tv].x;
+	edges[e].e = 0;
+
+	_edge_step_by (&edges[e], y - edges[e].top);
+
+	edges[e].top = y;
+	e++;
+    }
+    qsort (edges, e, sizeof (twin_edge_t), _edge_compare_y);
+    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,
+	    twin_fixed_t    left,
+	    twin_fixed_t    right)
+{
+    /* 2x2 oversampling yields slightly uneven alpha values */
+    static const twin_a8_t	coverage[2][2] = {
+	{ 0x40, 0x40 },
+	{ 0x3f, 0x40 },
+    };
+    const twin_a8_t *cover = coverage[(y >> 3) & 1];
+    int		    row = twin_fixed_trunc (y);
+    twin_a8_t	    *span = pixmap->p.a8 + row * pixmap->stride;
+    twin_fixed_t    x;
+    twin_a16_t	    a;
+    
+    for (x = twin_fixed_ceil_half (left); x < right; 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);
+    }
+}
+
+void
+_twin_edge_fill (twin_pixmap_t *pixmap, twin_edge_t *edges, int nedges)
+{
+    twin_edge_t	    *active, *a, *n, **prev;
+    int		    e;
+    twin_fixed_t    y;
+    twin_fixed_t    x0;
+    int		    w;
+    
+    e = 0;
+    y = edges[0].top;
+    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++)
+	{
+	    for (prev = &active; (a = *prev); prev = &(a->next))
+		if (a->x > edges[e].x)
+		    break;
+	    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)
+	{
+	    if (w == 0)
+		x0 = a->x;
+	    w += a->winding;
+	    if (w == 0)
+		_span_fill (pixmap, y, x0, a->x);
+	}
+	y += TWIN_FIXED_ONE >> 1;
+	/* step all edges */
+	for (a = active; a; a = a->next)
+	    _edge_step_by (a, TWIN_FIXED_ONE >> 1);
+	
+	/* fix x sorting */
+	for (prev = &active; (a = *prev) && (n = a->next);)
+	{
+	    if (a->x > n->x)
+	    {
+		a->next = n->next;
+		n->next = a;
+		*prev = n;
+		prev = &active;
+	    }
+	    else
+		prev = &a->next;
+	}
+    }
+}
+
+void
+twin_polygon (twin_pixmap_t *pixmap, twin_point_t *vertices, int nvertices)
+{
+    twin_edge_t	    *edges;
+    int		    nedges;
+    
+    /*
+     * Construct the edge table
+     */
+    edges = malloc (sizeof (twin_edge_t) * (nvertices + 1));
+    if (!edges)
+	return;
+    nedges = _twin_edge_build (vertices, nvertices, edges);
+    _twin_edge_fill (pixmap, edges, nedges);
+    free (edges);
+}
diff --git a/twin_screen.c b/twin_screen.c
index c8936f7..1662c9d 100644
--- a/twin_screen.c
+++ b/twin_screen.c
@@ -83,7 +83,7 @@ twin_screen_resize (twin_screen_t *screen, int width, int height)
     twin_screen_damage (screen, 0, 0, screen->width, screen->height);
 }
 
-twin_bool
+twin_bool_t
 twin_screen_damaged (twin_screen_t *screen)
 {
     return (screen->damage.left < screen->damage.right &&
diff --git a/twin_spline.c b/twin_spline.c
new file mode 100644
index 0000000..ee92216
--- /dev/null
+++ b/twin_spline.c
@@ -0,0 +1,124 @@
+/*
+ * $Id$
+ *
+ * Copyright © 2004 Carl Worth
+ *
+ * Permission to use, copy, modify, distribute, and sell this software and its
+ * documentation for any purpose is hereby granted without fee, provided that
+ * the above copyright notice appear in all copies and that both that
+ * copyright notice and this permission notice appear in supporting
+ * documentation, and that the name of Carl Worth not be used in
+ * advertising or publicity pertaining to distribution of the software without
+ * specific, written prior permission.  Carl Worth makes no
+ * representations about the suitability of this software for any purpose.  It
+ * is provided "as is" without express or implied warranty.
+ *
+ * CARL WORTH DISCLAIMS ALL WARRANTIES WITH REGARD TO THIS SOFTWARE,
+ * INCLUDING ALL IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS, IN NO
+ * EVENT SHALL CARL WORTH BE LIABLE FOR ANY SPECIAL, INDIRECT OR
+ * CONSEQUENTIAL DAMAGES OR ANY DAMAGES WHATSOEVER RESULTING FROM LOSS OF USE,
+ * DATA OR PROFITS, WHETHER IN AN ACTION OF CONTRACT, NEGLIGENCE OR OTHER
+ * TORTIOUS ACTION, ARISING OUT OF OR IN CONNECTION WITH THE USE OR
+ * PERFORMANCE OF THIS SOFTWARE.
+ */
+
+#include "twinint.h"
+
+typedef struct _twin_spline {
+    twin_point_t    a, b, c, d;
+} twin_spline_t;
+
+static void
+_lerp_half (twin_point_t *a, twin_point_t *b, twin_point_t *result)
+{
+    result->x = a->x + ((b->x - a->x) >> 1);
+    result->y = a->y + ((b->y - a->y) >> 1);
+}
+
+static void
+_de_casteljau (twin_spline_t *spline, twin_spline_t *s1, twin_spline_t *s2)
+{
+    twin_point_t ab, bc, cd;
+    twin_point_t abbc, bccd;
+    twin_point_t final;
+
+    _lerp_half (&spline->a, &spline->b, &ab);
+    _lerp_half (&spline->b, &spline->c, &bc);
+    _lerp_half (&spline->c, &spline->d, &cd);
+    _lerp_half (&ab, &bc, &abbc);
+    _lerp_half (&bc, &cd, &bccd);
+    _lerp_half (&abbc, &bccd, &final);
+
+    s1->a = spline->a;
+    s1->b = ab;
+    s1->c = abbc;
+    s1->d = final;
+
+    s2->a = final;
+    s2->b = bccd;
+    s2->c = cd;
+    s2->d = spline->d;
+}
+
+/*
+ * Return an upper bound on the error (squared) that could
+ * result from approximating a spline as a line segment 
+ * connecting the two endpoints 
+ */
+
+static twin_dfixed_t
+_twin_spline_error_squared (twin_spline_t *spline)
+{
+    twin_dfixed_t berr, cerr;
+
+    berr = _twin_distance_to_line_squared (&spline->b, &spline->a, &spline->d);
+    cerr = _twin_distance_to_line_squared (&spline->c, &spline->a, &spline->d);
+
+    if (berr > cerr)
+	return berr;
+    else
+	return cerr;
+}
+
+/*
+ * Pure recursive spline decomposition.
+ */
+
+static void
+_twin_spline_decompose (twin_path_t	*path,
+			twin_spline_t	*spline, 
+			twin_dfixed_t	tolerance_squared)
+{
+    if (_twin_spline_error_squared (spline) < tolerance_squared)
+    {
+	twin_path_draw (path, spline->a.x, spline->a.y);
+    }
+    else
+    {
+	twin_spline_t s1, s2;
+	_de_casteljau (spline, &s1, &s2);
+	_twin_spline_decompose (path, &s1, tolerance_squared);
+	_twin_spline_decompose (path, &s2, tolerance_squared);
+    }
+}
+
+void
+twin_path_curve (twin_path_t	*path,
+		 twin_fixed_t	x1, twin_fixed_t y1,
+		 twin_fixed_t	x2, twin_fixed_t y2,
+		 twin_fixed_t	x3, twin_fixed_t y3)
+{
+    twin_spline_t   spline;
+
+    if (path->npoints == 0)
+	twin_path_move (path, 0, 0);
+    spline.a = path->points[path->npoints - 1];
+    spline.b.x = x1;
+    spline.b.y = y1;
+    spline.c.x = x2;
+    spline.c.y = y2;
+    spline.d.x = x3;
+    spline.d.y = y3;
+    _twin_spline_decompose (path, &spline, TWIN_FIXED_TOLERANCE * TWIN_FIXED_TOLERANCE);
+    twin_path_draw (path, x3, y3);
+}
diff --git a/twinint.h b/twinint.h
index 3c2dc6d..0fcd202 100644
--- a/twinint.h
+++ b/twinint.h
@@ -28,6 +28,9 @@
 #include "twin.h"
 #include <string.h>
 
+/*
+ * Compositing stuff
+ */
 #define twin_int_mult(a,b,t)	((t) = (a) * (b) + 0x80, \
 				 ((((t)>>8 ) + (t))>>8 ))
 #define twin_int_div(a,b)	(((uint16_t) (a) * 255) / (b))
@@ -79,6 +82,9 @@ typedef void twin_op_func (twin_pointer_t	dst,
 			   twin_source_u	src,
 			   int			width);
 
+/*
+ * This needs to be refactored to reduce the number of functions...
+ */
 twin_in_op_func _twin_argb32_in_argb32_over_argb32;
 twin_in_op_func _twin_argb32_in_rgb16_over_argb32;
 twin_in_op_func _twin_argb32_in_a8_over_argb32;
@@ -210,4 +216,57 @@ _twin_fetch_rgb16 (twin_pixmap_t *pixmap, int x, int y, int w, twin_argb32_t *sp
 twin_argb32_t *
 _twin_fetch_argb32 (twin_pixmap_t *pixmap, int x, int y, int w, twin_argb32_t *span);
 
+/*
+ * Geometry helper functions
+ */
+
+twin_dfixed_t
+_twin_distance_to_point_squared (twin_point_t *a, twin_point_t *b);
+
+twin_dfixed_t
+_twin_distance_to_line_squared (twin_point_t *p, twin_point_t *p1, twin_point_t *p2);
+
+
+/*
+ * Polygon stuff
+ */
+
+typedef struct _twin_edge {
+    struct _twin_edge	*next;
+    twin_fixed_t	top, bot;
+    twin_fixed_t	x;
+    twin_fixed_t	e;
+    twin_fixed_t	dx, dy;
+    twin_fixed_t	inc_x;
+    twin_fixed_t	step_x;
+    int			winding;
+} twin_edge_t;
+
+/*
+ * Pixmap must be in a8 format.
+ */
+
+int
+_twin_edge_build (twin_point_t *vertices, int nvertices, twin_edge_t *edges);
+
+void
+_twin_edge_fill (twin_pixmap_t *pixmap, twin_edge_t *edges, int nedges);
+
+/*
+ * Path stuff
+ */
+
+/*
+ * A (fixed point) path
+ */
+
+struct _twin_path {
+    twin_point_t    *points;
+    int		    size_points;
+    int		    npoints;
+    int		    *sublen;
+    int		    size_sublen;
+    int		    nsublen;
+};
+
 #endif /* _TWININT_H_ */
diff --git a/xtwin.c b/xtwin.c
index c91de18..01d57b4 100644
--- a/xtwin.c
+++ b/xtwin.c
@@ -34,16 +34,64 @@ main (int argc, char **argv)
     twin_x11_t	    *x11 = twin_x11_create (dpy, 256, 256);
     twin_pixmap_t   *red = twin_pixmap_create (TWIN_ARGB32, 100, 100);
     twin_pixmap_t   *blue = twin_pixmap_create (TWIN_ARGB32, 100, 100);
+    twin_pixmap_t   *alpha = twin_pixmap_create (TWIN_A8, 100, 100);
+    twin_operand_t  source, mask;
+    twin_path_t	    *path;
+    twin_path_t	    *pen;
+    twin_path_t	    *stroke;
     XEvent	    ev;
     int		    x, y;
 
     twin_fill (red, 0x80800000, TWIN_SOURCE, 0, 0, 100, 100);
     twin_fill (red, 0xffffff00, TWIN_SOURCE, 25, 25, 50, 50);
+
+    twin_fill (blue, 0x00000000, TWIN_SOURCE, 0, 0, 100, 100);
+    twin_fill (alpha, 0x00000000, TWIN_SOURCE, 0, 0, 100, 100);
+
+    path = twin_path_create ();
+
+#if 1
+    pen = twin_path_create ();
+    twin_path_circle (pen, twin_double_to_fixed (6));
+    
+    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_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_fill (alpha, path);
+
+    source.source_kind = TWIN_SOLID;
+    source.u.argb = 0xff0000ff;
+    mask.source_kind = TWIN_PIXMAP;
+    mask.u.pixmap = alpha;
+    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_show (red, x11->screen, 0); */
     twin_pixmap_show (blue, x11->screen, 0);
     for (;;)
     {