[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