[Commit] twin ChangeLog, 1.2, 1.3 Makefile.am, 1.2, 1.3 twin.h, 1.2, 1.3 twin_convolve.c, NONE, 1.1 twin_geom.c, NONE, 1.1 twin_path.c, 1.1, 1.2 twin_poly.c, 1.1, 1.2 twin_spline.c, 1.1, 1.2 twinint.h, 1.2, 1.3 xtwin.c, 1.2, 1.3

[Keith Packard]

Committed by: keithp

Update of /local/src/CVS/twin
In directory evo:/home/keithp/src/twin

Modified Files:
	ChangeLog Makefile.am twin.h twin_path.c twin_poly.c 
	twin_spline.c twinint.h xtwin.c 
Added Files:
	twin_convolve.c twin_geom.c 
Log Message:
2004-09-21  Keith Packard  <keithp at 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


Index: ChangeLog
===================================================================
RCS file: /local/src/CVS/twin/ChangeLog,v
retrieving revision 1.2
retrieving revision 1.3
diff -u -d -r1.2 -r1.3
--- ChangeLog	21 Sep 2004 03:55:30 -0000	1.2
+++ ChangeLog	21 Sep 2004 07:27:08 -0000	1.3
@@ -1,3 +1,28 @@
+2004-09-21  Keith Packard  <keithp at 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 at keithp.com>
 
 	* .cvsignore:

Index: Makefile.am
===================================================================
RCS file: /local/src/CVS/twin/Makefile.am,v
retrieving revision 1.2
retrieving revision 1.3
diff -u -d -r1.2 -r1.3
--- Makefile.am	21 Sep 2004 03:55:30 -0000	1.2
+++ Makefile.am	21 Sep 2004 07:27:08 -0000	1.3
@@ -16,7 +16,9 @@
 
 xtwin_SOURCES = \
 	twin.h \
+	twin_convolve.c \
 	twin_draw.c \
+	twin_geom.c \
 	twin_path.c \
 	twin_pixmap.c \
 	twin_poly.c \

Index: twin.h
===================================================================
RCS file: /local/src/CVS/twin/twin.h,v
retrieving revision 1.2
retrieving revision 1.3
diff -u -d -r1.2 -r1.3
--- twin.h	21 Sep 2004 03:55:30 -0000	1.2
+++ twin.h	21 Sep 2004 07:27:08 -0000	1.3
@@ -42,7 +42,8 @@
 #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_ONE		(0x10)
+#define TWIN_FIXED_TOLERANCE	(TWIN_FIXED_ONE >> 1)
 
 #define TWIN_FALSE  0
 #define TWIN_TRUE   1
@@ -154,6 +155,14 @@
 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
  */
 
@@ -191,6 +200,9 @@
 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

--- NEW FILE: twin_convolve.c ---
(This appears to be a binary file; contents omitted.)

--- NEW FILE: twin_geom.c ---
(This appears to be a binary file; contents omitted.)

Index: twin_path.c
===================================================================
RCS file: /local/src/CVS/twin/twin_path.c,v
retrieving revision 1.1
retrieving revision 1.2
diff -u -d -r1.1 -r1.2
--- twin_path.c	21 Sep 2004 03:55:30 -0000	1.1
+++ twin_path.c	21 Sep 2004 07:27:08 -0000	1.2
@@ -83,6 +83,132 @@
     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)
 {
@@ -98,16 +224,18 @@
     nedges = 0;
     for (s = 0; s <= path->nsublen; s++)
     {
+	int sublen;
 	int npoints;
 	
 	if (s == path->nsublen)
-	    npoints = path->npoints - p;
+	    sublen = path->npoints;
 	else
-	    npoints = path->sublen[s] - p;
+	    sublen = path->sublen[s];
+	npoints = sublen - p;
 	if (npoints)
 	{
 	    n = _twin_edge_build (path->points + p, npoints, edges + nedges);
-	    p = path->sublen[s];
+	    p = sublen;
 	    nedges += n;
 	}
     }

Index: twin_poly.c
===================================================================
RCS file: /local/src/CVS/twin/twin_poly.c,v
retrieving revision 1.1
retrieving revision 1.2
diff -u -d -r1.1 -r1.2
--- twin_poly.c	21 Sep 2004 03:55:30 -0000	1.1
+++ twin_poly.c	21 Sep 2004 07:27:08 -0000	1.2
@@ -43,21 +43,6 @@
     edge->e = e % edge->dy;
 }
 
-#if 0
-#include <stdio.h>
-
-static void
-_dump_edge (twin_edge_t	*edge)
-{
-    printf ("Edge 0x%x\n", (int) edge);
-    printf ("\ttop: %4x bot: %4x\n", edge->top, edge->bot);
-    printf ("\t  x: %4x,   e: %4x   dx: %4x   dy: %4x\n",
-	    edge->x, edge->e, edge->dx, edge->dy);
-    printf ("\tinc_x: %4x step_x: %4x winding: %d\n",
-	    edge->inc_x, edge->step_x, edge->winding);
-}
-#endif
-
 int
 _twin_edge_build (twin_point_t *vertices, int nvertices, twin_edge_t *edges)
 {
@@ -90,6 +75,15 @@
 	    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 
 	 */
@@ -106,24 +100,15 @@
 	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 = vertices[tv].y;
+	edges[e].top = y;
 	edges[e].bot = vertices[bv].y;
 
 	edges[e].x = vertices[tv].x;
 	edges[e].e = 0;
 
-	y = edges[e].top;
-	if (y < 0)
-	    y = 0;
-
-	y = (y + 0x7) & ~0x7;
-
 	_edge_step_by (&edges[e], y - edges[e].top);
 
 	edges[e].top = y;
-#if 0
-	_dump_edge (&edges[e]);
-#endif
 	e++;
     }
     qsort (edges, e, sizeof (twin_edge_t), _edge_compare_y);

Index: twin_spline.c
===================================================================
RCS file: /local/src/CVS/twin/twin_spline.c,v
retrieving revision 1.1
retrieving revision 1.2
diff -u -d -r1.1 -r1.2
--- twin_spline.c	21 Sep 2004 03:55:30 -0000	1.1
+++ twin_spline.c	21 Sep 2004 07:27:08 -0000	1.2
@@ -60,45 +60,6 @@
     s2->d = spline->d;
 }
 
-static twin_dfixed_t
-_distance_squared_to_point (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;
-}
-
-static twin_dfixed_t
-_distance_squared_to_segment (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 _distance_squared_to_point (p, p1);
-    else
-	return (num * num) / den;
-}
-
 /*
  * Return an upper bound on the error (squared) that could
  * result from approximating a spline as a line segment 
@@ -110,8 +71,8 @@
 {
     twin_dfixed_t berr, cerr;
 
-    berr = _distance_squared_to_segment (&spline->b, &spline->a, &spline->d);
-    cerr = _distance_squared_to_segment (&spline->c, &spline->a, &spline->d);
+    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;
@@ -158,6 +119,6 @@
     spline.c.y = y2;
     spline.d.x = x3;
     spline.d.y = y3;
-    _twin_spline_decompose (path, &spline, TWIN_FIXED_ONE >> 2);
+    _twin_spline_decompose (path, &spline, TWIN_FIXED_TOLERANCE * TWIN_FIXED_TOLERANCE);
     twin_path_draw (path, x3, y3);
 }

Index: twinint.h
===================================================================
RCS file: /local/src/CVS/twin/twinint.h,v
retrieving revision 1.2
retrieving revision 1.3
diff -u -d -r1.2 -r1.3
--- twinint.h	21 Sep 2004 03:55:30 -0000	1.2
+++ twinint.h	21 Sep 2004 07:27:08 -0000	1.3
@@ -217,6 +217,17 @@
 _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
  */
 

Index: xtwin.c
===================================================================
RCS file: /local/src/CVS/twin/xtwin.c,v
retrieving revision 1.2
retrieving revision 1.3
diff -u -d -r1.2 -r1.3
--- xtwin.c	21 Sep 2004 03:55:30 -0000	1.2
+++ xtwin.c	21 Sep 2004 07:27:08 -0000	1.3
@@ -37,6 +37,8 @@
     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;
 
@@ -48,10 +50,21 @@
 
     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_draw (path, twin_double_to_fixed (30), twin_double_to_fixed (20));
-    twin_path_draw (path, twin_double_to_fixed (5), twin_double_to_fixed (50));
-    twin_path_close (path);
+    twin_path_circle (path, twin_double_to_fixed (10));
+#endif
 
     twin_path_fill (alpha, path);
     twin_path_empty (path);
@@ -78,7 +91,7 @@
      */
     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 (;;)
     {