summaryrefslogtreecommitdiff
diff options
context:
space:
mode:
authorKeith Packard <keithp@keithp.com>2004-09-21 18:28:38 +0000
committerKeith Packard <keithp@keithp.com>2004-09-21 18:28:38 +0000
commitb09a282fc5594db6ee26f1f578f1c04e1ad37fac (patch)
tree9b48402e9e69ea2abad3138a1f09faef91d43dbf
parent3e4457dd55823fa5cf4754f1a7849a4c2090af08 (diff)
Add a few definitions
Find pen starting point as closest to the normal to the path. Restructure convolve loop to be easier to understand Round circle coordinates instead of truncating them 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. Stroke a path.
-rw-r--r--ChangeLog23
-rw-r--r--twin.h4
-rw-r--r--twin_convolve.c145
-rw-r--r--twin_path.c5
-rw-r--r--twin_poly.c107
-rw-r--r--twinint.h4
-rw-r--r--xtwin.c33
7 files changed, 210 insertions, 111 deletions
diff --git a/ChangeLog b/ChangeLog
index 051a94f..d432886 100644
--- a/ChangeLog
+++ b/ChangeLog
@@ -1,5 +1,28 @@
2004-09-21 Keith Packard <keithp@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@keithp.com>
+
* Makefile.am:
* twin.h:
* twin_convolve.c: (_twin_path_leftmost), (_twin_path_step),
diff --git a/twin.h b/twin.h
index 183d784..b8e1c88 100644
--- a/twin.h
+++ b/twin.h
@@ -41,9 +41,11 @@ typedef int32_t twin_dfixed_t;
#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
diff --git a/twin_convolve.c b/twin_convolve.c
index dab05d2..78559bc 100644
--- a/twin_convolve.c
+++ b/twin_convolve.c
@@ -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 @@ _clockwise (twin_point_t *a1,
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 @@ twin_path_convolve (twin_path_t *path,
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);
}
}
diff --git a/twin_path.c b/twin_path.c
index ce5c8f0..be44bf4 100644
--- a/twin_path.c
+++ b/twin_path.c
@@ -179,6 +179,7 @@ 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;
+ twin_dfixed_t dradius = (twin_dfixed_t) radius;
int i;
if (sides > 256) sides = 256;
@@ -201,8 +202,8 @@ twin_path_circle (twin_path_t *path, twin_fixed_t radius)
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);
}
diff --git a/twin_poly.c b/twin_poly.c
index eadce4c..12832c2 100644
--- a/twin_poly.c
+++ b/twin_poly.c
@@ -23,7 +23,7 @@
*/
#include "twinint.h"
-
+
static int
_edge_compare_y (const void *a, const void *b)
{
@@ -43,6 +43,18 @@ _edge_step_by (twin_edge_t *edge, twin_fixed_t dy)
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 @@ _twin_edge_build (twin_point_t *vertices, int nvertices, twin_edge_t *edges)
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 @@ _twin_edge_build (twin_point_t *vertices, int nvertices, twin_edge_t *edges)
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 @@ _twin_edge_build (twin_point_t *vertices, int nvertices, twin_edge_t *edges)
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 @@ _span_fill (twin_pixmap_t *pixmap,
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 @@ _twin_edge_fill (twin_pixmap_t *pixmap, twin_edge_t *edges, int nedges)
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 @@ _twin_edge_fill (twin_pixmap_t *pixmap, twin_edge_t *edges, int nedges)
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 @@ _twin_edge_fill (twin_pixmap_t *pixmap, twin_edge_t *edges, int nedges)
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);)
diff --git a/twinint.h b/twinint.h
index 0fcd202..cc5c0c7 100644
--- a/twinint.h
+++ b/twinint.h
@@ -242,6 +242,10 @@ typedef struct _twin_edge {
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.
*/
diff --git a/xtwin.c b/xtwin.c
index 01d57b4..b049a78 100644
--- a/xtwin.c
+++ b/xtwin.c
@@ -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 @@ main (int argc, char **argv)
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 @@ main (int argc, char **argv)
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 (;;)
{