summaryrefslogtreecommitdiff
path: root/fitzdraw/pathscan.c
diff options
context:
space:
mode:
Diffstat (limited to 'fitzdraw/pathscan.c')
-rw-r--r--fitzdraw/pathscan.c531
1 files changed, 531 insertions, 0 deletions
diff --git a/fitzdraw/pathscan.c b/fitzdraw/pathscan.c
new file mode 100644
index 00000000..0ea46502
--- /dev/null
+++ b/fitzdraw/pathscan.c
@@ -0,0 +1,531 @@
+#include "fitz-base.h"
+#include "fitz-world.h"
+#include "fitz-draw.h"
+
+enum { HSCALE = 17, VSCALE = 15, SF = 1 };
+
+/*
+ * Global Edge List -- list of straight path segments for scan conversion
+ *
+ * Stepping along the edges is with bresenham's line algorithm.
+ *
+ * See Mike Abrash -- Graphics Programming Black Book (notably chapter 40)
+ */
+
+fz_error *
+fz_newgel(fz_gel **gelp)
+{
+ fz_gel *gel;
+
+ gel = *gelp = fz_malloc(sizeof(fz_gel));
+ if (!gel)
+ return fz_outofmem;
+
+ gel->edges = nil;
+
+ gel->cap = 512;
+ gel->len = 0;
+ gel->edges = fz_malloc(sizeof(fz_edge) * gel->cap);
+ if (!gel->edges) {
+ fz_free(gel);
+ return fz_outofmem;
+ }
+
+ gel->clip.x0 = gel->clip.y0 = INT_MAX;
+ gel->clip.x1 = gel->clip.y1 = INT_MIN;
+
+ gel->bbox.x0 = gel->bbox.y0 = INT_MAX;
+ gel->bbox.x1 = gel->bbox.y1 = INT_MIN;
+
+ return fz_okay;
+}
+
+void
+fz_resetgel(fz_gel *gel, fz_irect clip)
+{
+ if (fz_isinfiniterect(clip))
+ {
+ gel->clip.x0 = gel->clip.y0 = INT_MAX;
+ gel->clip.x1 = gel->clip.y1 = INT_MIN;
+ }
+ else {
+ gel->clip.x0 = clip.x0 * HSCALE;
+ gel->clip.x1 = clip.x1 * HSCALE;
+ gel->clip.y0 = clip.y0 * VSCALE;
+ gel->clip.y1 = clip.y1 * VSCALE;
+ }
+
+ gel->bbox.x0 = gel->bbox.y0 = INT_MAX;
+ gel->bbox.x1 = gel->bbox.y1 = INT_MIN;
+
+ gel->len = 0;
+}
+
+void
+fz_dropgel(fz_gel *gel)
+{
+ fz_free(gel->edges);
+ fz_free(gel);
+}
+
+fz_irect
+fz_boundgel(fz_gel *gel)
+{
+ fz_irect bbox;
+ bbox.x0 = fz_idiv(gel->bbox.x0, HSCALE);
+ bbox.y0 = fz_idiv(gel->bbox.y0, VSCALE);
+ bbox.x1 = fz_idiv(gel->bbox.x1, HSCALE) + 1;
+ bbox.y1 = fz_idiv(gel->bbox.y1, VSCALE) + 1;
+ return bbox;
+}
+
+enum { INSIDE, OUTSIDE, LEAVE, ENTER };
+
+#define cliplerpy(v,m,x0,y0,x1,y1,t) cliplerpx(v,m,y0,x0,y1,x1,t)
+
+static int
+cliplerpx(int val, int m, int x0, int y0, int x1, int y1, int *out)
+{
+ int v0out = m ? x0 > val : x0 < val;
+ int v1out = m ? x1 > val : x1 < val;
+
+ if (v0out + v1out == 0)
+ return INSIDE;
+
+ if (v0out + v1out == 2)
+ return OUTSIDE;
+
+ if (v1out)
+ {
+ *out = y0 + (y1 - y0) * (val - x0) / (x1 - x0);
+ return LEAVE;
+ }
+
+ else
+ {
+ *out = y1 + (y0 - y1) * (val - x1) / (x0 - x1);
+ return ENTER;
+ }
+}
+
+fz_error *
+fz_insertgel(fz_gel *gel, float fx0, float fy0, float fx1, float fy1)
+{
+ fz_edge *edge;
+ int dx, dy;
+ int winding;
+ int width;
+ int tmp;
+ int v;
+ int d;
+
+ int x0 = fz_floor(fx0 * HSCALE);
+ int y0 = fz_floor(fy0 * VSCALE);
+ int x1 = fz_floor(fx1 * HSCALE);
+ int y1 = fz_floor(fy1 * VSCALE);
+
+ d = cliplerpy(gel->clip.y0, 0, x0, y0, x1, y1, &v);
+ if (d == OUTSIDE) return fz_okay;
+ if (d == LEAVE) { y1 = gel->clip.y0; x1 = v; }
+ if (d == ENTER) { y0 = gel->clip.y0; x0 = v; }
+
+ d = cliplerpy(gel->clip.y1, 1, x0, y0, x1, y1, &v);
+ if (d == OUTSIDE) return fz_okay;
+ if (d == LEAVE) { y1 = gel->clip.y1; x1 = v; }
+ if (d == ENTER) { y0 = gel->clip.y1; x0 = v; }
+
+ if (y0 == y1)
+ return fz_okay;
+
+ if (y0 > y1) {
+ winding = -1;
+ tmp = x0; x0 = x1; x1 = tmp;
+ tmp = y0; y0 = y1; y1 = tmp;
+ }
+ else
+ winding = 1;
+
+ if (x0 < gel->bbox.x0) gel->bbox.x0 = x0;
+ if (x0 > gel->bbox.x1) gel->bbox.x1 = x0;
+ if (x1 < gel->bbox.x0) gel->bbox.x0 = x1;
+ if (x1 > gel->bbox.x1) gel->bbox.x1 = x1;
+
+ if (y0 < gel->bbox.y0) gel->bbox.y0 = y0;
+ if (y1 > gel->bbox.y1) gel->bbox.y1 = y1;
+
+ if (gel->len + 1 == gel->cap) {
+ int newcap = gel->cap + 512;
+ fz_edge *newedges = fz_realloc(gel->edges, sizeof(fz_edge) * newcap);
+ if (!newedges)
+ return fz_outofmem;
+ gel->cap = newcap;
+ gel->edges = newedges;
+ }
+
+ edge = &gel->edges[gel->len++];
+
+ dy = y1 - y0;
+ dx = x1 - x0;
+ width = dx < 0 ? -dx : dx;
+
+ edge->xdir = dx > 0 ? 1 : -1;
+ edge->ydir = winding;
+ edge->x = x0;
+ edge->y = y0;
+ edge->h = dy;
+ edge->adjdown = dy;
+
+ /* initial error term going l->r and r->l */
+ if (dx >= 0)
+ edge->e = 0;
+ else
+ edge->e = -dy + 1;
+
+ /* y-major edge */
+ if (dy >= width) {
+ edge->xmove = 0;
+ edge->adjup = width;
+ }
+
+ /* x-major edge */
+ else {
+ edge->xmove = (width / dy) * edge->xdir;
+ edge->adjup = width % dy;
+ }
+
+ return fz_okay;
+}
+
+void
+fz_sortgel(fz_gel *gel)
+{
+ fz_edge *a = gel->edges;
+ int n = gel->len;
+
+ int h, i, k;
+ fz_edge t;
+
+ h = 1;
+ if (n < 14) {
+ h = 1;
+ }
+ else {
+ while (h < n)
+ h = 3 * h + 1;
+ h /= 3;
+ h /= 3;
+ }
+
+ while (h > 0)
+ {
+ for (i = 0; i < n; i++) {
+ t = a[i];
+ k = i - h;
+ /* TODO: sort on y major, x minor */
+ while (k >= 0 && a[k].y > t.y) {
+ a[k + h] = a[k];
+ k -= h;
+ }
+ a[k + h] = t;
+ }
+
+ h /= 3;
+ }
+}
+
+/*
+ * Active Edge List -- keep track of active edges while sweeping
+ */
+
+fz_error *
+fz_newael(fz_ael **aelp)
+{
+ fz_ael *ael;
+
+ ael = *aelp = fz_malloc(sizeof(fz_ael));
+ if (!ael)
+ return fz_outofmem;
+
+ ael->cap = 64;
+ ael->len = 0;
+ ael->edges = fz_malloc(sizeof(fz_edge*) * ael->cap);
+ if (!ael->edges) {
+ fz_free(ael);
+ return fz_outofmem;
+ }
+
+ return fz_okay;
+}
+
+void
+fz_dropael(fz_ael *ael)
+{
+ fz_free(ael->edges);
+ fz_free(ael);
+}
+
+static inline void
+sortael(fz_edge **a, int n)
+{
+ int h, i, k;
+ fz_edge *t;
+
+ h = 1;
+ if (n < 14) {
+ h = 1;
+ }
+ else {
+ while (h < n)
+ h = 3 * h + 1;
+ h /= 3;
+ h /= 3;
+ }
+
+ while (h > 0)
+ {
+ for (i = 0; i < n; i++) {
+ t = a[i];
+ k = i - h;
+ while (k >= 0 && a[k]->x > t->x) {
+ a[k + h] = a[k];
+ k -= h;
+ }
+ a[k + h] = t;
+ }
+
+ h /= 3;
+ }
+}
+
+static fz_error *
+insertael(fz_ael *ael, fz_gel *gel, int y, int *e)
+{
+ /* insert edges that start here */
+ while (*e < gel->len && gel->edges[*e].y == y) {
+ if (ael->len + 1 == ael->cap) {
+ int newcap = ael->cap + 64;
+ fz_edge **newedges = fz_realloc(ael->edges, sizeof(fz_edge*) * newcap);
+ if (!newedges)
+ return fz_outofmem;
+ ael->edges = newedges;
+ ael->cap = newcap;
+ }
+ ael->edges[ael->len++] = &gel->edges[(*e)++];
+ }
+
+ /* shell-sort the edges by increasing x */
+ sortael(ael->edges, ael->len);
+
+ return fz_okay;
+}
+
+static void
+advanceael(fz_ael *ael)
+{
+ fz_edge *edge;
+ int i = 0;
+
+ while (i < ael->len)
+ {
+ edge = ael->edges[i];
+
+ edge->h --;
+
+ /* terminator! */
+ if (edge->h == 0) {
+ ael->edges[i] = ael->edges[--ael->len];
+ }
+
+ else {
+ edge->x += edge->xmove;
+ edge->e += edge->adjup;
+ if (edge->e > 0) {
+ edge->x += edge->xdir;
+ edge->e -= edge->adjdown;
+ }
+ i ++;
+ }
+ }
+}
+
+/*
+ * Scan convert
+ */
+
+static inline void
+addspan(unsigned char *list, int x0, int x1, int xofs)
+{
+ int x0pix, x0sub;
+ int x1pix, x1sub;
+
+ if (x0 == x1)
+ return;
+
+ /* x between 0 and width of bbox */
+ x0 -= xofs;
+ x1 -= xofs;
+
+ x0pix = x0 / HSCALE;
+ x0sub = x0 % HSCALE;
+ x1pix = x1 / HSCALE;
+ x1sub = x1 % HSCALE;
+
+ if (x0pix == x1pix)
+ {
+ list[x0pix] += x1sub - x0sub;
+ list[x0pix+1] += x0sub - x1sub;
+ }
+
+ else
+ {
+ list[x0pix] += HSCALE - x0sub;
+ list[x0pix+1] += x0sub;
+ list[x1pix] += x1sub - HSCALE;
+ list[x1pix+1] += -x1sub;
+ }
+}
+
+static inline void
+nonzerowinding(fz_ael *ael, unsigned char *list, int xofs)
+{
+ int winding = 0;
+ int x = 0;
+ int i;
+ for (i = 0; i < ael->len; i++)
+ {
+ if (!winding && (winding + ael->edges[i]->ydir))
+ x = ael->edges[i]->x;
+ if (winding && !(winding + ael->edges[i]->ydir))
+ addspan(list, x, ael->edges[i]->x, xofs);
+ winding += ael->edges[i]->ydir;
+ }
+}
+
+static inline void
+evenodd(fz_ael *ael, unsigned char *list, int xofs)
+{
+ int even = 0;
+ int x = 0;
+ int i;
+ for (i = 0; i < ael->len; i++)
+ {
+ if (!even)
+ x = ael->edges[i]->x;
+ else
+ addspan(list, x, ael->edges[i]->x, xofs);
+ even = !even;
+ }
+}
+
+static inline void toalpha(unsigned char *list, int n)
+{
+ int d = 0;
+ while (n--)
+ {
+ d += *list;
+ *list++ = d;
+ }
+}
+
+static inline void blit(fz_pixmap *pix, int x, int y,
+ unsigned char *list, int skipx, int len,
+ unsigned char *argb, int over)
+{
+ unsigned char *dst;
+ unsigned char cov;
+
+ dst = pix->samples + ( (y - pix->y) * pix->w + (x - pix->x) ) * pix->n;
+ cov = 0;
+
+ while (skipx--)
+ {
+ cov += *list;
+ *list = 0;
+ ++list;
+ }
+
+ if (argb)
+ fz_path_w4i1o4(argb, list, cov, len, dst);
+ else if (over)
+ fz_path_1o1(list, cov, len, dst);
+ else
+ fz_path_1c1(list, cov, len, dst);
+}
+
+fz_error *
+fz_scanconvert(fz_gel *gel, fz_ael *ael, int eofill, fz_irect clip,
+ fz_pixmap *pix, unsigned char *argb, int over)
+{
+ fz_error *error;
+ unsigned char *deltas;
+ int y, e;
+ int yd, yc;
+
+ int xmin = fz_idiv(gel->bbox.x0, HSCALE);
+ int xmax = fz_idiv(gel->bbox.x1, HSCALE) + 1;
+
+ int xofs = xmin * HSCALE;
+
+ int skipx = clip.x0 - xmin;
+ int clipn = clip.x1 - clip.x0;
+
+ assert(clip.x0 >= xmin);
+ assert(clip.x1 <= xmax);
+
+ if (gel->len == 0)
+ return fz_okay;
+
+ deltas = fz_malloc(xmax - xmin + 1);
+ if (!deltas)
+ return fz_outofmem;
+
+ memset(deltas, 0, xmax - xmin + 1);
+
+ e = 0;
+ y = gel->edges[0].y;
+ yc = fz_idiv(y, VSCALE);
+ yd = yc;
+
+ while (ael->len > 0 || e < gel->len)
+ {
+ yc = fz_idiv(y, VSCALE);
+ if (yc != yd)
+ {
+ if (yd >= clip.y0 && yd < clip.y1)
+ {
+ blit(pix, xmin + skipx, yd, deltas, skipx, clipn, argb, over);
+ }
+ }
+ yd = yc;
+
+ error = insertael(ael, gel, y, &e);
+ if (error) {
+ fz_free(deltas);
+ return error;
+ }
+
+ if (yd >= clip.y0 && yd < clip.y1)
+ {
+ if (eofill)
+ evenodd(ael, deltas, xofs);
+ else
+ nonzerowinding(ael, deltas, xofs);
+ }
+
+ advanceael(ael);
+
+ if (ael->len > 0)
+ y ++;
+ else if (e < gel->len)
+ y = gel->edges[e].y;
+ }
+
+ if (yd >= clip.y0 && yd < clip.y1)
+ {
+ blit(pix, xmin + skipx, yd, deltas, skipx, clipn, argb, over);
+ }
+
+ fz_free(deltas);
+ return fz_okay;
+}
+
generated by cgit v1.2.3 (git 2.25.1) at 2025-03-21 07:27:24 +0000