summaryrefslogtreecommitdiff
path: root/raster/pathscan.c
diff options
context:
space:
mode:
Diffstat (limited to 'raster/pathscan.c')
-rw-r--r--raster/pathscan.c531
1 files changed, 0 insertions, 531 deletions
diff --git a/raster/pathscan.c b/raster/pathscan.c
deleted file mode 100644
index 0ea46502..00000000
--- a/raster/pathscan.c
+++ /dev/null
@@ -1,531 +0,0 @@
-#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-27 12:13:14 +0000