[Commit] twin ChangeLog, 1.2, 1.3 twin.h, 1.2, 1.3 twin_convolve.c, 1.1, 1.2 twin_path.c, 1.1, 1.2 twin_poly.c, 1.1, 1.2 twinint.h, 1.2, 1.3 xtwin.c, 1.2, 1.3

Keith Packard commit at keithp.com
Tue Sep 21 11:28:40 PDT 2004


Committed by: keithp

Update of /local/src/CVS/twin
In directory home.keithp.com:/tmp/cvs-serv14502

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


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 15:42:56 -0000	1.2
+++ ChangeLog	21 Sep 2004 18:28:38 -0000	1.3
@@ -1,5 +1,28 @@
 2004-09-21  Keith Packard  <keithp at 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 at keithp.com>
+
 	* Makefile.am:
 	* twin.h:
 	* twin_convolve.c: (_twin_path_leftmost), (_twin_path_step),

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 15:42:56 -0000	1.2
+++ twin.h	21 Sep 2004 18:28:38 -0000	1.3
@@ -41,9 +41,11 @@
 
 #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

Index: twin_convolve.c
===================================================================
RCS file: /local/src/CVS/twin/twin_convolve.c,v
retrieving revision 1.1
retrieving revision 1.2
diff -u -d -r1.1 -r1.2
--- twin_convolve.c	21 Sep 2004 15:42:56 -0000	1.1
+++ twin_convolve.c	21 Sep 2004 18:28:38 -0000	1.2
@@ -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 @@
     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 @@
     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);
     }
 }

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 15:42:56 -0000	1.1
+++ twin_path.c	21 Sep 2004 18:28:38 -0000	1.2
@@ -179,6 +179,7 @@
     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 @@
 
     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);
     }

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 15:42:57 -0000	1.1
+++ twin_poly.c	21 Sep 2004 18:28:38 -0000	1.2
@@ -23,7 +23,7 @@
  */
 
 #include "twinint.h"
-
+	    
 static int
 _edge_compare_y (const void *a, const void *b)
 {
@@ -43,6 +43,18 @@
     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 @@
 	    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 @@
 	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 @@
     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 @@
     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 @@
     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 @@
 	    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 @@
 	    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);)

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 15:42:57 -0000	1.2
+++ twinint.h	21 Sep 2004 18:28:38 -0000	1.3
@@ -242,6 +242,10 @@
     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.
  */

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 15:42:57 -0000	1.2
+++ xtwin.c	21 Sep 2004 18:28:38 -0000	1.3
@@ -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 @@
 
     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 @@
     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 (;;)
     {




More information about the Commit mailing list