⟦f3f34d554⟧

TextFile

/* Copyright (C) 1989 Aladdin Enterprises.  All rights reserved.
   Distributed by Free Software Foundation, Inc.

This file is part of Ghostscript.

Ghostscript is distributed in the hope that it will be useful, but
WITHOUT ANY WARRANTY.  No author or distributor accepts responsibility
to anyone for the consequences of using it or for whether it serves any
particular purpose or works at all, unless he says so in writing.  Refer
to the Ghostscript General Public License for full details.

Everyone is granted permission to copy, modify and redistribute
Ghostscript, but only under the conditions described in the Ghostscript
General Public License.  A copy of this license is supposed to have been
given to you along with Ghostscript so you can know your rights and
responsibilities.  It should be in a file named COPYING.  Among other
things, the copyright notice and this notice must be preserved on all
copies.  */

/* gxfill.c */
/* Lower-level path filling procedures for GhostScript library */
#include "gx.h"
#include "malloc_.h"
#include "gserrors.h"
#include "gxfixed.h"
#include "gxmatrix.h"
#include "gxdevice.h"			/* for gx_color_index */
#include "gzcolor.h"
#include "gzpath.h"
#include "gzstate.h"

/* Define the structure for keeping track of active lines. */
typedef struct active_line_s {
	gs_fixed_point end;		/* x,y where line ends */
	fixed x_current;		/* current x position */
	fixed y_next;			/* y of next recalc */
	segment *pseg;			/* endpoint of this line */
	float slope;			/* delta x / delta y */
#define al_slope(alp) (alp)->slope
#define compute_al_slope(alp, start, end)\
  (alp)->slope = (float)(end.x - start.x) / (end.y - start.y)
	int direction;			/* direction of line segment */
#define dir_up 1
#define dir_down (-1)
	short tag;			/* distinguish path from clip path */
	short end_mark;			/* marks lines about to end (even) */
					/* or cross (odd) */
/* "Pending" lines (not reached in the Y ordering yet) use next and prev */
/* to order lines by increasing starting Y.  "Active" lines (being scanned) */
/* use next and prev to order lines by increasing current X, or if the */
/* current Xs are equal, by increasing final X. */
	struct active_line_s
		*prev, *next;
} active_line;

#ifdef DEBUG
/* Internal procedure for printing an active line */
private void
print_active_line(char *label, active_line *alp)
{	printf("[f]%s %lx(%d): x_current=%f y_next=%f pt_end=%lx(%f,%f)\n",
		label, (ulong)alp, alp->tag, fixed2float(alp->x_current),
		fixed2float(alp->y_next), (ulong)alp->pseg,
		fixed2float(alp->end.x), fixed2float(alp->end.y));
	printf("     slope=%f", alp->slope);
	printf(" mark=%d dir=%d prev=%lx next=%lx\n",
		alp->end_mark, alp->direction,
		(ulong)alp->prev, (ulong)alp->next);
}
#define print_al(label,alp)\
  if ( gs_debug['f'] ) print_active_line(label, alp)
#else
#define print_al(label,alp) 0
#endif

/* Line list structure */
struct line_list_s {
	active_line *area;		/* allocated area */
	uint area_size;
	active_line *next;		/* next allocation slot */
	active_line *y_list;		/* Y-sorted list of pending lines */
	active_line *y_line;		/* most recently inserted line */
	active_line x_head;		/* X-sorted list of active lines */
#define x_list x_head.next
	int no_clip;			/* true if clipping not needed */
};
typedef struct line_list_s line_list;

/* Forward declarations */
private int alloc_line_list(P2(line_list *, int));
private int add_y_list(P4(gx_path *, short, line_list *, gs_fixed_rect *));
private void add_y_line(P5(segment *, segment *, int, short, line_list *));
private void fill_loop(P4(gs_color *, int, line_list *, gs_state *));
private void insert_x_new(P2(active_line *, line_list *));
private void swap_group(P1(active_line *));
private void ended_line(P1(active_line *));

/* Statistics */
#ifdef DEBUG
#define stat(x) (x++)
#define statn(x,n) (x += (n))
private long n_fill;
private long n_fill_alloc;
private long n_y_up;
private long n_y_down;
private long n_x_step;
private long n_iter;
private long n_find_y;
private long n_band;
private long n_band_step;
private long n_band_fill;
#else
#define stat(x) 0
#define statn(x,n) 0
#endif

/* Main filling algorithm. */
/* Caller has done compute_draw_color. */
int
gx_fill_path(gx_path *ppath, gs_color *pcolor, gs_state *pgs, int rule)
{	gx_path *cpath = pgs->clip_path;
	gx_path fpath;
	int code;
	line_list lst;
	int max_active;
	/* Start by flattening the path.  We should do this on-the-fly.... */
	if ( !ppath->curve_count )	/* don't need to flatten */
		fpath = *ppath;
	else
	   {	if ( (code = gx_path_flatten(ppath, &fpath, pgs->flatness)) < 0 ) return code;
	   }
	/* may be 1 extra segment per subpath, for closing */
	max_active = fpath.segment_count + fpath.subpath_count +
		cpath->segment_count + cpath->subpath_count;
	if ( !(code = alloc_line_list(&lst, max_active)) )
	   {	if ( add_y_list(&fpath, 0, &lst, &cpath->cbox) )
		   {	/* Path lies entirely within clipping rectangle */
			lst.no_clip = 1;
		   }
		else
		   {	static gs_fixed_rect no_box = { 0, 0, 0, 0 };
			lst.no_clip = 0;
			add_y_list(pgs->clip_path, 1, &lst, &no_box);
		   }
		fill_loop(pcolor, rule, &lst, pgs);
		free((char *)lst.area);
	   }
	if ( ppath->curve_count )	/* had to flatten */
		gx_path_release(&fpath);
#ifdef DEBUG
if ( gs_debug['f'] )
	   {	printf("[f]calls alloc   up   down  step  iter  find  band bstep bfill\n");
		printf("   %5ld %5ld %5ld %5ld %5ld %5ld %5ld %5ld %5ld %5ld\n",
			n_fill, n_fill_alloc, n_y_up, n_y_down, n_x_step,
			n_iter, n_find_y, n_band, n_band_step, n_band_fill);
	   }
#endif
	return code;
}

/* Create a line list for a (flattened) path. */
/* We pass in the list size, so that we can use this to iterate */
/* over more than one path simultaneously (needed for clipping). */
private int
alloc_line_list(line_list *ll, int count)
{	ll->area_size = count * sizeof(active_line);
	ll->area = (active_line *)malloc(ll->area_size);
	if ( ll->area == 0 ) return_error(gs_error_VMerror);
	ll->next = ll->area;
	ll->y_list = 0;
	ll->y_line = 0;
	stat(n_fill);
	statn(n_fill_alloc, count);
	return 0;
}

/* Construct a Y-sorted list of lines for a (flattened) path. */
/* We assume the path is non-empty.  Only include non-horizontal */
/* lines where one endpoint is locally Y-minimal. */
/* Return true if the path falls entirely within the clipping rectangle. */
private int
add_y_list(gx_path *ppath, short tag, line_list *ll, gs_fixed_rect *pbox)
{	segment *pseg = (segment *)ppath->first_subpath;
	subpath *psub;
	segment *plast;
	int prev_dir, dir;
	segment *prev;
	fixed	cxmin = pbox->xmin, cxmax = pbox->xmax,
		cymin = pbox->ymin, cymax = pbox->ymax;
	while ( pseg )
	   {	if ( cxmax > cxmin )
		   {	/* Check for point within clipping rectangle */
			fixed ix = pseg->pt.x, iy = pseg->pt.y;
			if ( !(ix > cxmin && ix < cxmax && iy > cymin && iy < cymax) )
				cxmax = cxmin;	/* fast clipping failed */
		   }
		switch ( pseg->type )
		   {	/* No curves left */
		case s_start:
			psub = (subpath *)pseg;
			plast = psub->last;
			dir = 0;
			break;
		default:		/* s_line, _close */
		   {	fixed dy = pseg->pt.y - prev->pt.y;
			dir = (dy > 0 ? dir_up : dy < 0 ? dir_down : 0);
			if ( dir > prev_dir )
			   {	if ( prev_dir )
				  add_y_line(prev->prev, prev, prev_dir, tag, ll);
				if ( dir )
				  add_y_line(prev, pseg, dir, tag, ll);
			   }
			if ( pseg == plast )
			   {	/* The beginning of a subpath is always */
				/* treated like a horizontal line, */
				/* so the last segment must receive */
				/* special consideration. */
				if ( pseg->type != s_line_close )
				   {	/* "Close" an open subpath */
					fixed cdy = psub->pt.y - pseg->pt.y;
					int cdir = (cdy > 0 ? dir_up : cdy < 0 ? dir_down : 0);
					if ( cdir > dir && dir )
					  add_y_line(prev, pseg, dir, tag, ll);
					if ( cdir > dir && cdir || cdir < 0 )
					  add_y_line(pseg, (segment *)psub, cdir, tag, ll);
				   }
				else
				   {	/* Just add the closing line if needed */
					if ( dir < 0 )
					  add_y_line(prev, pseg, dir, tag, ll);
				   }
			   }
		   }
		   }
		prev = pseg;
		prev_dir = dir;
		pseg = pseg->next;
	   }
	return cxmax > cxmin;
}
/* Internal routine to test a line segment and add it to the */
/* pending list if appropriate. */
private void
add_y_line(segment *prev_lp, segment *lp, int dir, short tag, line_list *ll)
{	gs_fixed_point this, prev;
	register active_line *alp = ll->next++;
	fixed y_start;
	this = lp->pt;
	prev = prev_lp->pt;
	alp->tag = tag;
	if ( (alp->direction = dir) > 0 )
	   {	/* Upward line */
		alp->x_current = prev.x;
		alp->y_next = y_start = prev.y;
		alp->end = this;
		compute_al_slope(alp, prev, this);
		alp->pseg = lp;
	   }
	else
	   {	/* Downward line */
		alp->x_current = this.x;
		alp->y_next = y_start = this.y;
		alp->end = prev;
		compute_al_slope(alp, this, prev);
		alp->pseg = prev_lp;
	   }
	/* Insert the new line in the Y ordering */
	   {	register active_line *yp = ll->y_line;
		register active_line *nyp;
		if ( yp == 0 )
		   {	alp->next = alp->prev = 0;
			ll->y_list = alp;
		   }
		else if ( y_start >= yp->y_next )
		   {	/* Insert the new line after y_line */
			while ( stat(n_y_up), (nyp = yp->next) != NULL && y_start > nyp->y_next )
				yp = nyp;
			alp->next = nyp;
			alp->prev = yp;
			yp->next = alp;
			if ( nyp ) nyp->prev = alp;
		   }
		else
		   {	/* Insert the new line before y_line */
			while ( stat(n_y_down), (nyp = yp->prev) != NULL && y_start < nyp->y_next )
				yp = nyp;
			alp->prev = nyp;
			alp->next = yp;
			yp->prev = alp;
			if ( nyp ) nyp->next = alp;
			else ll->y_list = alp;
		   }
	   }
	ll->y_line = alp;
	print_al("add ", alp);
}

/* Find the intersection of two active lines, if any. */
/* Only called if alp->x_current >= endp->x_current and */
/* alp->slope < endp->slope. */
/* Store the y coordinate of the intersection in *cross_yp and return 1, */
/* or return 0 if no intersection. */
private int
find_cross_y(active_line *endp, active_line *alp,
  fixed y,				/* current y position */
  fixed y1,				/* max y for intersection */
  fixed *cross_yp)
{	float cross_slope = al_slope(endp) - al_slope(alp);	/* known > 0 */
	fixed diff_x = alp->x_current - endp->x_current;	/* known >= 0 */
	fixed y_limit;
	/* Compute the y limit, the min of endp's end, alp's end, and y1. */
	y_limit = endp->end.y;
	if ( alp->end.y < y_limit ) y_limit = alp->end.y;
	if ( y1 < y_limit) y_limit = y1;
#ifdef DEBUG
if ( gs_debug['f'] )
	printf("[f]cross? %lx %lx dx=%f cs=%f y=%f y_limit=%f -> ",
	       (ulong)endp, (ulong)alp,
	       fixed2float(diff_x), cross_slope,
	       fixed2float(y), fixed2float(y_limit));
#endif
	if ( diff_x < (y_limit - y) * cross_slope )
	  { *cross_yp = y + (fixed)(diff_x / cross_slope);
#ifdef DEBUG
if ( gs_debug['f'] )
	    printf("%f\n", fixed2float(*cross_yp));
#endif
	    return 1;
	  }
	else
	  {
#ifdef DEBUG
if ( gs_debug['f'] )
	    printf("<no>\n");
#endif
	    return 0;
	  }
}

/* Main filling loop.  Takes lines off of y_list and adds them to */
/* x_list as needed. */
private void
fill_loop(gs_color *pcolor, int rule, line_list *ll, gs_state *pgs)
{	active_line *yll = ll->y_list;
	fixed y;
	if ( yll == 0 ) return;		/* empty list */
	y = yll->y_next;		/* first Y value */
	ll->x_list = 0;
	ll->x_head.end_mark = -4;	/* to delimit swap group */
	while ( 1 )
	   {	fixed y1;
		int end_count;
		active_line *endp;
		stat(n_iter);
		/* Move newly active lines from y to x list. */
		while ( yll != 0 && yll->y_next == y )
		   {	active_line *ynext = yll->next;	/* insert smashes next/prev links */
			insert_x_new(yll, ll);
			print_al("acti", yll);
			yll = ynext;
		   }
		if ( ll->x_list == 0 )
		   {	/* No active lines, skip to next start */
			if ( yll == 0 ) break;	/* no lines left */
			y = yll->y_next;
			continue;
		   }
		/* Find the next evaluation point. */
		/* The lines requiring attention are those */
		/* whose end_mark >= end_count. */
		/* Each time we reset y1 downward, */
		/* we increment end_count by 4 so that we don't */
		/* try to swap or drop lines that haven't */
		/* crossed or ended yet. */
		endp = ll->x_list;
		end_count = 0;
		endp->end_mark = 0;
		y1 = endp->end.y;
		   {	active_line *alp = endp->next;
			while ( stat(n_find_y), alp != 0 )
			   {	fixed py = alp->end.y;
				fixed cross_y;
				/* Check for intersecting lines */
				if ( alp->slope < endp->slope &&	/* Might intersect, check */
				     find_cross_y(endp, alp, y, y1, &cross_y)
				   )
				   {	/* stop at intersection */
					if ( cross_y < y1 )
					   {	end_count += 4;
						y1 = cross_y;
					   }
					endp->end_mark = end_count + 3;
					alp->end_mark = end_count + 1;
				   }
				else if ( py <= y1 )
				   {	if ( py < y1 )
					   {	end_count += 4;
						y1 = py;
					   }
					alp->end_mark = end_count;
				   }
				else
					alp->end_mark = -2;
				print_al("find", alp);
				endp = alp;
				alp = alp->next;
			   }
		   }
		if ( yll != 0 && yll->y_next < y1 )
		   {	end_count += 4;	/* no lines end here */
			y1 = yll->y_next;
		   }
#ifdef DEBUG
if ( gs_debug['f'] )
   {		active_line *alp;
		printf("[f]y=%f y1=%f end_count=%d\n",
			fixed2float(y), fixed2float(y1), end_count);
		for ( alp = ll->x_list; alp != 0; alp = alp->next )
			print_al("band", alp);
   }
#endif
		/* Fill a multi-trapezoid band for the active lines. */
		/* Drop ended lines (with end_mark = end_count) from the */
		/* list.  Reverse the order of groups of adjacent lines */
		/* that intersect at y = y1: the last line of such a group */
		/* has end_mark = end_count+1, the previous ones have */
		/* end_mark = end_count+3. */
		   {	active_line *alp = ll->x_list;
			fixed height = y1 - y;
			int y_bot = fixed2int_rounded(y);
			int ht = fixed2int_rounded(y1) - y_bot;
			fixed xlbot, xltop;	/* as of last "outside" line */
			int inside[2];
			inside[0] = 0;			/* 0 for path */
			inside[1] = ll->no_clip;	/* 1 for clip path */
			stat(n_band);
			/* rule = -1 for winding number rule, i.e. */
			/* we are inside if the winding number is non-zero; */
			/* rule = 1 for even-odd rule, i.e. */
			/* we are inside if the winding number is odd. */
			/* Clever, eh? */
#define inside_path_p() ((inside[0] & rule) && (inside[1] & pgs->clip_rule))
			while ( alp != 0 )
			   {	fixed xbot = alp->x_current;
				fixed xtop =
					(alp->end.y == y1 ? alp->end.x :
					 xbot + (fixed)(al_slope(alp) * height));
				active_line *next = alp->next;
				print_al("step", alp);
				stat(n_band_step);
				if ( inside_path_p() )
				   {	inside[alp->tag] += alp->direction;
					if ( !inside_path_p() )	/* about to go out */
					   {	int xb = fixed2int_rounded(xlbot);
						int xt = fixed2int_rounded(xltop);
						stat(n_band_fill);
						gz_fill_trapezoid(
							xb, fixed2int_rounded(xbot) - xb, y_bot,
							xt, fixed2int_rounded(xtop) - xt, ht,
							pcolor, pgs);
					   }
				   }
				else			/* outside */
				   {	inside[alp->tag] += alp->direction;
					if ( inside_path_p() )	/* about to go in */
						xlbot = xbot, xltop = xtop;
				   }
				alp->x_current = xtop;
				if ( alp->end_mark >= end_count )
				   {	/* This line is ending here, or */
					/* this is the last of an */
					/* intersection group. */
					switch ( alp->end_mark & 3 )
					   {
					/* case 3: in a group, not last */
					case 1:	/* last line of a group */
						swap_group(alp);
						break;
					case 0:	/* ending line */
						ended_line(alp);
					   }
				   }
				alp = next;
			   }
		   }
		y = y1;
	   }
}

/* Internal routine to insert an active line in the X ordering */
private void
insert_x_new(active_line *alp, line_list *ll)
{	register fixed x = alp->x_current;
	register active_line *prev = &ll->x_head;
	register active_line *next;
	while ( stat(n_x_step), (next = prev->next) != 0 &&
		  (next->x_current < x || next->x_current == x &&
		    al_slope(alp) > al_slope(next)) )
		prev = next;
	alp->next = next;
	alp->prev = prev;
	if ( next != 0 ) next->prev = alp;
	prev->next = alp;
}
/* Auxiliary procedure to swap the lines of an intersection group */
private void
swap_group(active_line *alp)
{	/* This line is the last of the group: */
	/* find the beginning of the group. */
	active_line *prev;
	active_line *last = alp;
	active_line *first;
	active_line *next = alp->next;
	while ( ((prev = alp->prev)->end_mark & 3) == 3 )
		alp = prev;
	first = alp;
	print_al("swap", first);
	print_al("thru", last);
	/* Swap the group end-for-end. */
	/* Start by fixing up the ends. */
	prev->next = last;
	if ( next != 0 )
		next->prev = first;
	first->prev = next;
	last->next = prev;
	do
	   {	active_line *nlp = alp->next;
		alp->next = alp->prev;
		alp->prev = nlp;
		alp = nlp;
	   }
	while ( alp != prev );
}
/* Auxiliary procedure to handle a line that just ended */
private void
ended_line(register active_line *alp)
{	segment *pseg = alp->pseg;
	segment *next;
	fixed y = pseg->pt.y;
	if ( alp->direction == dir_up )
	   {	/* Upward line, go forward along path */
		next = pseg->next;
		if ( next == 0 || next->type == s_start )
			next = pseg;	/* stop here */
	   }
	else
	   {	/* Downward line, go backward along path */
		next = (pseg->type == s_start ? pseg /* stop here */ : pseg->prev);
	   }
	if ( next->pt.y <= y )
	   {	/* End of a line sequence */
		active_line *nlp = alp->next;
		alp->prev->next = nlp;
		if ( nlp ) nlp->prev = alp->prev;
		print_al("drop", alp);
	   }
	else
	   {	alp->y_next = y;
		alp->pseg = next;
		compute_al_slope(alp, alp->end, next->pt);
		alp->end = next->pt;
		print_al("repl", alp);
	   }
}
DataMuseum.dk

DKUUG/EUUG Conference tapes

⟦f3f34d554⟧ TextFile

Derivation

TextFile
