Subversion Repositories planix.SVN

/* Copyright (C) 1989-2003 artofcode LLC.  All rights reserved.

  This software is provided AS-IS with no warranty, either express or

  implied.

  This software is distributed under license and may not be copied,

  modified or distributed except as expressly authorized under the terms

  of the license contained in the file LICENSE in this distribution.

  For more information about licensing, please refer to

  http://www.ghostscript.com/licensing/. For information on

  commercial licensing, go to http://www.artifex.com/licensing/ or

  contact Artifex Software, Inc., 101 Lucas Valley Road #110,

  San Rafael, CA  94903, U.S.A., +1(415)492-9861.

*/

/* $Id: gxfill.c,v 1.122 2005/08/22 14:29:18 igor Exp $ */

/* A topological spot decomposition algorithm with dropout prevention. */

/* 

   This is a dramaticly reorganized and improved revision of the 

   filling algorithm, iwhich was nitially coded by Henry Stiles. 

   The main improvements are: 

	1. A dropout prevention for character fill.

	2. The spot topology analysys support

	   for True Type grid fitting.

	3. Fixed the contiguty of a spot covering 

	   for shading fills with no dropouts.

*/

/* See PSEUDO_RASTERISATION and "pseudo_rasterization".

   about the dropout previntion logics. */

/* See is_spotan about the spot topology analyzis support. */

/* Also defining lower-level path filling procedures */

#include "gx.h"

#include "gserrors.h"

#include "gsstruct.h"

#include "gxfixed.h"

#include "gxdevice.h"

#include "gzpath.h"

#include "gzcpath.h"

#include "gxdcolor.h"

#include "gxhttile.h"

#include "gxistate.h"

#include "gxpaint.h"		/* for prototypes */

#include "gxfdrop.h"

#include "gxfill.h"

#include "gsptype2.h"

#include "gdevddrw.h"

#include "gzspotan.h" /* Only for gx_san_trap_store. */

#include "memory_.h"

#include "stdint_.h"

#include "vdtrace.h"

/*

#include "gxfilltr.h" - Do not remove this comment. "gxfilltr.h" is included below.

#include "gxfillsl.h" - Do not remove this comment. "gxfillsl.h" is included below.

#include "gxfillts.h" - Do not remove this comment. "gxfillts.h" is included below.

*/

#ifdef DEBUG

/* Define the statistics structure instance. */

stats_fill_t stats_fill;

#endif

/* A predicate for spot insideness. */

/* 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. */

#define INSIDE_PATH_P(inside, rule) ((inside & rule) != 0)

/* ---------------- Active line management ---------------- */

/*

 * Define the ordering criterion for active lines that overlap in Y.

 * Return -1, 0, or 1 if lp1 precedes, coincides with, or follows lp2.

 *

 * The lines' x_current values are correct for some Y value that crosses

 * both of them and that is not both the start of one and the end of the

 * other.  (Neither line is horizontal.)  We want the ordering at this

 * Y value, or, of the x_current values are equal, greater Y values

 * (if any: this Y value might be the end of both lines).

 */

private int

x_order(const active_line *lp1, const active_line *lp2)

{

    bool s1;

    INCR(order);

    if (lp1->x_current < lp2->x_current)

	return -1;

    else if (lp1->x_current > lp2->x_current)

	return 1;

    /*

     * We need to compare the slopes of the lines.  Start by

     * checking one fast case, where the slopes have opposite signs.

     */

    if ((s1 = lp1->start.x < lp1->end.x) != (lp2->start.x < lp2->end.x))

	return (s1 ? 1 : -1);

    /*

     * We really do have to compare the slopes.  Fortunately, this isn't

     * needed very often.  We want the sign of the comparison

     * dx1/dy1 - dx2/dy2, or (since we know dy1 and dy2 are positive)

     * dx1 * dy2 - dx2 * dy1.  In principle, we can't simply do this using

     * doubles, since we need complete accuracy and doubles don't have

     * enough fraction bits.  However, with the usual 20+12-bit fixeds and

     * 64-bit doubles, both of the factors would have to exceed 2^15

     * device space pixels for the result to be inaccurate, so we

     * simply disregard this possibility.  ****** FIX SOMEDAY ******

     */

    INCR(slow_order);

    {

	fixed dx1 = lp1->end.x - lp1->start.x,

	    dy1 = lp1->end.y - lp1->start.y;

	fixed dx2 = lp2->end.x - lp2->start.x,

	    dy2 = lp2->end.y - lp2->start.y;

	double diff = (double)dx1 * dy2 - (double)dx2 * dy1;

	return (diff < 0 ? -1 : diff > 0 ? 1 : 0);

    }

}

/*

 * The active_line structure isn't really simple, but since its instances

 * only exist temporarily during a fill operation, we don't have to

 * worry about a garbage collection occurring.

 */

gs_private_st_simple(st_active_line, active_line, "active_line");

#ifdef DEBUG

/* Internal procedures for printing and checking active lines. */

private void

print_active_line(const char *label, const active_line * alp)

{

    dlprintf5("[f]%s 0x%lx(%d): x_current=%f x_next=%f\n",

	      label, (ulong) alp, alp->direction,

	      fixed2float(alp->x_current), fixed2float(alp->x_next));

    dlprintf5("    start=(%f,%f) pt_end=0x%lx(%f,%f)\n",

	      fixed2float(alp->start.x), fixed2float(alp->start.y),

	      (ulong) alp->pseg,

	      fixed2float(alp->end.x), fixed2float(alp->end.y));

    dlprintf2("    prev=0x%lx next=0x%lx\n",

	      (ulong) alp->prev, (ulong) alp->next);

}

private void

print_line_list(const active_line * flp)

{

    const active_line *lp;

    for (lp = flp; lp != 0; lp = lp->next) {

	fixed xc = lp->x_current, xn = lp->x_next;

	dlprintf3("[f]0x%lx(%d): x_current/next=%g",

		  (ulong) lp, lp->direction,

		  fixed2float(xc));

	if (xn != xc)

	    dprintf1("/%g", fixed2float(xn));

	dputc('\n');

    }

}

inline private void

print_al(const char *label, const active_line * alp)

{

    if (gs_debug_c('F'))

	print_active_line(label, alp);

}

#else

#define print_al(label,alp) DO_NOTHING

#endif

private inline bool

is_spotan_device(gx_device * dev)

{

    return dev->memory != NULL && 

	    gs_object_type(dev->memory, dev) == &st_device_spot_analyzer;

}

/* Forward declarations */

private void free_line_list(line_list *);

private int add_y_list(gx_path *, line_list *);

private int add_y_line_aux(const segment * prev_lp, const segment * lp, 

	    const gs_fixed_point *curr, const gs_fixed_point *prev, int dir, line_list *ll);

private void insert_x_new(active_line *, line_list *);

private bool end_x_line(active_line *, const line_list *, bool);

private void step_al(active_line *alp, bool move_iterator);

#define FILL_LOOP_PROC(proc) int proc(line_list *, fixed band_mask)

private FILL_LOOP_PROC(spot_into_scan_lines);

private FILL_LOOP_PROC(spot_into_trapezoids);

/*

 * This is the general path filling algorithm.

 * It uses the center-of-pixel rule for filling

 * (except for pseudo_rasterization - see below).

 * We can implement Microsoft's upper-left-corner-of-pixel rule

 * by subtracting (0.5, 0.5) from all the coordinates in the path.

 *

 * The adjust parameters are a hack for keeping regions

 * from coming out too faint: they specify an amount by which to expand

 * the sides of every filled region.

 * Setting adjust = fixed_half is supposed to produce the effect of Adobe's

 * any-part-of-pixel rule, but it doesn't quite, because of the

 * closed/open interval rule for regions.  We detect this as a special case

 * and do the slightly ugly things necessary to make it work.

 */

/* Initialize the line list for a path. */

private inline void

init_line_list(line_list *ll, gs_memory_t * mem)

{

    ll->memory = mem;

    ll->active_area = 0;

    ll->next_active = ll->local_active;

    ll->limit = ll->next_active + MAX_LOCAL_ACTIVE;

    ll->close_count = 0;

    ll->y_list = 0;

    ll->y_line = 0;

    ll->h_list0 = ll->h_list1 = 0;

    ll->margin_set0.margin_list = ll->margin_set1.margin_list = 0;

    ll->margin_set0.margin_touched = ll->margin_set1.margin_touched = 0;

    ll->margin_set0.y = ll->margin_set1.y = 0; /* A stub against indeterminism. Don't use it. */

    ll->free_margin_list = 0;

    ll->local_margin_alloc_count = 0;

    ll->margin_set0.sect = ll->local_section0;

    ll->margin_set1.sect = ll->local_section1;

    /* Do not initialize ll->bbox_left, ll->bbox_width - they were set in advance. */

    INCR(fill);

}

/* Unlink any line_close segments added temporarily. */

private inline void

unclose_path(gx_path * ppath, int count)

{

    subpath *psub;

    for (psub = ppath->first_subpath; count != 0;

	 psub = (subpath *) psub->last->next

	)

	if (psub->last == (segment *) & psub->closer) {

	    segment *prev = psub->closer.prev, *next = psub->closer.next;

	    prev->next = next;

	    if (next)

		next->prev = prev;

	    psub->last = prev;

	    count--;

	}

}

/*

 * Tweak the fill adjustment if necessary so that (nearly) empty

 * rectangles are guaranteed to produce some output.  This is a hack

 * to work around a bug in the Microsoft Windows PostScript driver,

 * which draws thin lines by filling zero-width rectangles, and in

 * some other drivers that try to fill epsilon-width rectangles.

 */

void

gx_adjust_if_empty(const gs_fixed_rect * pbox, gs_fixed_point * adjust)

{

    /*

     * For extremely large coordinates, the obvious subtractions could

     * overflow.  We can work around this easily by noting that since

     * we know q.{x,y} >= p.{x,y}, the subtraction overflows iff the

     * result is negative.

     */

    const fixed

	  dx = pbox->q.x - pbox->p.x, dy = pbox->q.y - pbox->p.y;

    if (dx < fixed_half && dx > 0 && (dy >= int2fixed(2) || dy < 0)) {

	adjust->x = arith_rshift_1(fixed_1 + fixed_epsilon - dx);

	if_debug1('f', "[f]thin adjust_x=%g\n",

		  fixed2float(adjust->x));

    } else if (dy < fixed_half && dy > 0 && (dx >= int2fixed(2) || dx < 0)) {

	adjust->y = arith_rshift_1(fixed_1 + fixed_epsilon - dy);

	if_debug1('f', "[f]thin adjust_y=%g\n",

		  fixed2float(adjust->y));

    }

}

/*

 * The general fill  path algorithm.

 */

private int

gx_general_fill_path(gx_device * pdev, const gs_imager_state * pis,

		     gx_path * ppath, const gx_fill_params * params,

		 const gx_device_color * pdevc, const gx_clip_path * pcpath)

{

    gs_fixed_point adjust;

    gs_logical_operation_t lop = pis->log_op;

    gs_fixed_rect ibox, bbox, sbox;

    gx_device_clip cdev;

    gx_device *dev = pdev;

    gx_device *save_dev = dev;

    gx_path ffpath;

    gx_path *pfpath;

    int code;

    int max_fill_band = dev->max_fill_band;

#define NO_BAND_MASK ((fixed)(-1) << (sizeof(fixed) * 8 - 1))

    const bool is_character = params->adjust.x == -1; /* See gxistate.h */

    bool fill_by_trapezoids;

    bool pseudo_rasterization;

    bool big_path = ppath->subpath_count > 50;

    fill_options fo;

    line_list lst;

    *(const fill_options **)&lst.fo = &fo; /* break 'const'. */

    /*

     * Compute the bounding box before we flatten the path.

     * This can save a lot of time if the path has curves.

     * If the path is neither fully within nor fully outside

     * the quick-check boxes, we could recompute the bounding box

     * and make the checks again after flattening the path,

     * but right now we don't bother.

     */

    gx_path_bbox(ppath, &ibox);

#   define SMALL_CHARACTER 500

    pseudo_rasterization = (is_character && 

			    !is_spotan_device(dev) &&

			    ibox.q.y - ibox.p.y < SMALL_CHARACTER * fixed_scale &&

			    ibox.q.x - ibox.p.x < SMALL_CHARACTER * fixed_scale);

    if (is_character)

	adjust.x = adjust.y = 0;

    else

	adjust = params->adjust;

    if (params->fill_zero_width && !pseudo_rasterization)

	gx_adjust_if_empty(&ibox, &adjust);

    lst.bbox_left = fixed2int(ibox.p.x - adjust.x - fixed_epsilon);

    lst.bbox_width = fixed2int(fixed_ceiling(ibox.q.x + adjust.x)) - lst.bbox_left;

    if (vd_enabled) {

	fixed x0 = int2fixed(fixed2int(ibox.p.x - adjust.x - fixed_epsilon));

	fixed x1 = int2fixed(fixed2int(ibox.q.x + adjust.x + fixed_scale - fixed_epsilon));

	fixed y0 = int2fixed(fixed2int(ibox.p.y - adjust.y - fixed_epsilon));

	fixed y1 = int2fixed(fixed2int(ibox.q.y + adjust.y + fixed_scale - fixed_epsilon)), k;

	for (k = x0; k <= x1; k += fixed_scale)

	    vd_bar(k, y0, k, y1, 1, RGB(128, 128, 128));

	for (k = y0; k <= y1; k += fixed_scale)

	    vd_bar(x0, k, x1, k, 1, RGB(128, 128, 128));

    }

    /* Check the bounding boxes. */

    if_debug6('f', "[f]adjust=%g,%g bbox=(%g,%g),(%g,%g)\n",

	      fixed2float(adjust.x), fixed2float(adjust.y),

	      fixed2float(ibox.p.x), fixed2float(ibox.p.y),

	      fixed2float(ibox.q.x), fixed2float(ibox.q.y));

    if (pcpath)

	gx_cpath_inner_box(pcpath, &bbox);

    else

	(*dev_proc(dev, get_clipping_box)) (dev, &bbox);

    if (!rect_within(ibox, bbox)) {

	/*

	 * Intersect the path box and the clip bounding box.

	 * If the intersection is empty, this fill is a no-op.

	 */

	if (pcpath)

	    gx_cpath_outer_box(pcpath, &bbox);

	if_debug4('f', "   outer_box=(%g,%g),(%g,%g)\n",

		  fixed2float(bbox.p.x), fixed2float(bbox.p.y),

		  fixed2float(bbox.q.x), fixed2float(bbox.q.y));

	rect_intersect(ibox, bbox);

	if (ibox.p.x - adjust.x >= ibox.q.x + adjust.x ||

	    ibox.p.y - adjust.y >= ibox.q.y + adjust.y

	    ) { 		/* Intersection of boxes is empty! */

	    return 0;

	}

	/*

	 * The path is neither entirely inside the inner clip box

	 * nor entirely outside the outer clip box.

	 * If we had to flatten the path, this is where we would

	 * recompute its bbox and make the tests again,

	 * but we don't bother right now.

	 *

	 * If there is a clipping path, set up a clipping device.

	 */

	if (pcpath) {

	    dev = (gx_device *) & cdev;

	    gx_make_clip_device(&cdev, gx_cpath_list(pcpath));

	    cdev.target = save_dev;

	    cdev.max_fill_band = save_dev->max_fill_band;

	    (*dev_proc(dev, open_device)) (dev);

	}

    }

    /*

     * Compute the proper adjustment values.

     * To get the effect of the any-part-of-pixel rule,

     * we may have to tweak them slightly.

     * NOTE: We changed the adjust_right/above value from 0.5+epsilon

     * to 0.5 in release 5.01; even though this does the right thing

     * in every case we could imagine, we aren't confident that it's

     * correct.  (The old values were definitely incorrect, since they

     * caused 1-pixel-wide/high objects to color 2 pixels even if

     * they fell exactly on pixel boundaries.)

     */

    if (adjust.x == fixed_half)

	fo.adjust_left = fixed_half - fixed_epsilon,

	    fo.adjust_right = fixed_half /* + fixed_epsilon */ ;	/* see above */

    else

	fo.adjust_left = fo.adjust_right = adjust.x;

    if (adjust.y == fixed_half)

	fo.adjust_below = fixed_half - fixed_epsilon,

	    fo.adjust_above = fixed_half /* + fixed_epsilon */ ;	/* see above */

    else

	fo.adjust_below = fo.adjust_above = adjust.y;

    /* Initialize the active line list. */

    init_line_list(&lst, ppath->memory);

    sbox.p.x = ibox.p.x - adjust.x;

    sbox.p.y = ibox.p.y - adjust.y;

    sbox.q.x = ibox.q.x + adjust.x;

    sbox.q.y = ibox.q.y + adjust.y;

    fo.pseudo_rasterization = pseudo_rasterization;

    fo.pdevc = pdevc;

    fo.lop = lop;

    fo.fixed_flat = float2fixed(params->flatness);

    fo.ymin = ibox.p.y;

    fo.ymax = ibox.q.y;

    fo.dev = dev;

    fo.lop = lop;

    fo.pbox = &sbox;

    fo.rule = params->rule;

    fo.is_spotan = is_spotan_device(dev);

    fo.fill_direct = color_writes_pure(pdevc, lop);

    fo.fill_rect = (fo.fill_direct ? dev_proc(dev, fill_rectangle) : NULL);

    fo.fill_trap = dev_proc(dev, fill_trapezoid);

    /*

     * We have a choice of two different filling algorithms:

     * scan-line-based and trapezoid-based.  They compare as follows:

     *

     *	    Scan    Trap

     *	    ----    ----

     *	     skip   +draw   0-height horizontal lines

     *	     slow   +fast   rectangles

     *	    +fast    slow   curves

     *	    +yes     no     write pixels at most once when adjust != 0

     *

     * Normally we use the scan line algorithm for characters, where curve

     * speed is important, and for non-idempotent RasterOps, where double

     * pixel writing must be avoided, and the trapezoid algorithm otherwise.

     * However, we always use the trapezoid algorithm for rectangles.

     */

    fill_by_trapezoids =

	(pseudo_rasterization || !gx_path_has_curves(ppath) || 

	 params->flatness >= 1.0 || fo.is_spotan);

    if (fill_by_trapezoids && !fo.is_spotan && !lop_is_idempotent(lop)) {

	gs_fixed_rect rbox;

	if (gx_path_is_rectangular(ppath, &rbox)) {

	    int x0 = fixed2int_pixround(rbox.p.x - fo.adjust_left);

	    int y0 = fixed2int_pixround(rbox.p.y - fo.adjust_below);

	    int x1 = fixed2int_pixround(rbox.q.x + fo.adjust_right);

	    int y1 = fixed2int_pixround(rbox.q.y + fo.adjust_above);

	    return gx_fill_rectangle_device_rop(x0, y0, x1 - x0, y1 - y0,

						pdevc, dev, lop);

	}

	if (fo.adjust_left | fo.adjust_right | fo.adjust_below | fo.adjust_above)

	    fill_by_trapezoids = false; /* avoid double writing pixels */

    }

    gx_path_init_local(&ffpath, ppath->memory);

    if (!big_path && !gx_path_has_curves(ppath))	/* don't need to flatten */

	pfpath = ppath;

    else if (is_spotan_device(dev))

	pfpath = ppath;

    else if (!big_path && gx_path__check_curves(ppath, pco_small_curves, fo.fixed_flat))

	pfpath = ppath;

    else {

	code = gx_path_copy_reducing(ppath, &ffpath, fo.fixed_flat, NULL, 

			    pco_small_curves);

	if (code < 0)

	    return code;

	pfpath = &ffpath;

	if (big_path) {

	    code = gx_path_merge_contacting_contours(pfpath);

	    if (code < 0)

		return code;

	}

    }

    fo.fill_by_trapezoids = fill_by_trapezoids;

    if ((code = add_y_list(pfpath, &lst)) < 0)

	goto nope;

    {

	FILL_LOOP_PROC((*fill_loop));

	/* Some short-sighted compilers won't allow a conditional here.... */

	if (fill_by_trapezoids)

	    fill_loop = spot_into_trapezoids;

	else

	    fill_loop = spot_into_scan_lines;

	if (lst.bbox_width > MAX_LOCAL_SECTION && fo.pseudo_rasterization) {

	    /*

	     * Note that execution pass here only for character size

	     * grater that MAX_LOCAL_SECTION and lesser than 

	     * SMALL_CHARACTER. Therefore with !arch_small_memory

	     * the dynamic allocation only happens for characters 

	     * wider than 100 pixels.

	     */

	    lst.margin_set0.sect = (section *)gs_alloc_struct_array(pdev->memory, lst.bbox_width * 2, 

						   section, &st_section, "section");

	    if (lst.margin_set0.sect == 0)

		return_error(gs_error_VMerror);

	    lst.margin_set1.sect = lst.margin_set0.sect + lst.bbox_width;

	}

	if (fo.pseudo_rasterization) {

	    init_section(lst.margin_set0.sect, 0, lst.bbox_width);

	    init_section(lst.margin_set1.sect, 0, lst.bbox_width);

	}

	code = (*fill_loop)

	    (&lst, (max_fill_band == 0 ? NO_BAND_MASK : int2fixed(-max_fill_band)));

	if (lst.margin_set0.sect != lst.local_section0 && 

	    lst.margin_set0.sect != lst.local_section1)

	    gs_free_object(pdev->memory, min(lst.margin_set0.sect, lst.margin_set1.sect), "section");

    }

  nope:if (lst.close_count != 0)

	unclose_path(pfpath, lst.close_count);

    free_line_list(&lst);

    if (pfpath != ppath)	/* had to flatten */

	gx_path_free(pfpath, "gx_general_fill_path");

#ifdef DEBUG

    if (gs_debug_c('f')) {

	dlputs("[f]  # alloc    up  down horiz step slowx  iter  find  band bstep bfill\n");

	dlprintf5(" %5ld %5ld %5ld %5ld %5ld",

		  stats_fill.fill, stats_fill.fill_alloc,

		  stats_fill.y_up, stats_fill.y_down,

		  stats_fill.horiz);

	dlprintf4(" %5ld %5ld %5ld %5ld",

		  stats_fill.x_step, stats_fill.slow_x,

		  stats_fill.iter, stats_fill.find_y);

	dlprintf3(" %5ld %5ld %5ld\n",

		  stats_fill.band, stats_fill.band_step,

		  stats_fill.band_fill);

	dlputs("[f]    afill slant shall sfill mqcrs order slowo\n");

	dlprintf7("       %5ld %5ld %5ld %5ld %5ld %5ld %5ld\n",

		  stats_fill.afill, stats_fill.slant,

		  stats_fill.slant_shallow, stats_fill.sfill,

		  stats_fill.mq_cross, stats_fill.order,

		  stats_fill.slow_order);

    }

#endif

    return code;

}

/*

 * Fill a path.  This is the default implementation of the driver

 * fill_path procedure.

 */

int

gx_default_fill_path(gx_device * pdev, const gs_imager_state * pis,

		     gx_path * ppath, const gx_fill_params * params,

		 const gx_device_color * pdevc, const gx_clip_path * pcpath)

{

    int code;

    if (gx_dc_is_pattern2_color(pdevc)) {

	/*  Optimization for shading fill :

	    The general path filling algorithm subdivides fill region with 

	    trapezoid or rectangle subregions and then paints each subregion 

	    with given color. If the color is shading, each subregion to be 

	    subdivided into areas of constant color. But with radial 

	    shading each area is a high order polygon, being 

	    subdivided into smaller subregions, so as total number of

	    subregions grows huge. Faster processing is done here by changing 

	    the order of subdivision cycles : we first subdivide the shading into 

	    areas of constant color, then apply the general path filling algorithm 

	    (i.e. subdivide each area into trapezoids or rectangles), using the 

	    filling path as clip mask.

	*/

	gx_clip_path cpath_intersection;

	gx_path path_intersection;

	/*  Shading fill algorithm uses "current path" parameter of the general

	    path filling algorithm as boundary of constant color area,

	    so we need to intersect the filling path with the clip path now,

	    reducing the number of pathes passed to it :

	*/

	gx_path_init_local(&path_intersection, pdev->memory);

	gx_cpath_init_local_shared(&cpath_intersection, pcpath, pdev->memory);

	if ((code = gx_cpath_intersect(&cpath_intersection, ppath, params->rule, (gs_imager_state *)pis)) >= 0)

	    code = gx_cpath_to_path(&cpath_intersection, &path_intersection);

	/* Do fill : */

	if (code >= 0)

	    code = gx_dc_pattern2_fill_path(pdevc, &path_intersection, NULL,  pdev);

	/* Destruct local data and return :*/

	gx_path_free(&path_intersection, "shading_fill_path_intersection");

	gx_cpath_free(&cpath_intersection, "shading_fill_cpath_intersection");

    } else {

	bool got_dc = false;

        vd_save;

	if (vd_allowed('F') || vd_allowed('f')) {

	    if (!vd_enabled) {

		vd_get_dc( (params->adjust.x | params->adjust.y)  ? 'F' : 'f');

		got_dc = vd_enabled;

	    }

	    if (vd_enabled) {

		vd_set_shift(0, 100);

		vd_set_scale(VD_SCALE);

		vd_set_origin(0, 0);

		vd_erase(RGB(192, 192, 192));

	    }

	} else

	    vd_disable;

	code = gx_general_fill_path(pdev, pis, ppath, params, pdevc, pcpath);

	if (got_dc)

	    vd_release_dc;

	vd_restore;

    }

    return code;

}

/* Free the line list. */

private void

free_line_list(line_list *ll)

{

    /* Free any individually allocated active_lines. */

    gs_memory_t *mem = ll->memory;

    active_line *alp;

    while ((alp = ll->active_area) != 0) {

	active_line *next = alp->alloc_next;

	gs_free_object(mem, alp, "active line");

	ll->active_area = next;

    }

    free_all_margins(ll);

}

private inline active_line *

make_al(line_list *ll)

{

    active_line *alp = ll->next_active;

    if (alp == ll->limit) {	/* Allocate separately */

	alp = gs_alloc_struct(ll->memory, active_line,

			      &st_active_line, "active line");

	if (alp == 0)

	    return NULL;

	alp->alloc_next = ll->active_area;

	ll->active_area = alp;

	INCR(fill_alloc);

    } else

	ll->next_active++;

    return alp;

}

/* Insert the new line in the Y ordering */

private void

insert_y_line(line_list *ll, active_line *alp)

{

    active_line *yp = ll->y_line;

    active_line *nyp;

    fixed y_start = alp->start.y;

    vd_bar(alp->start.x, alp->start.y, alp->end.x, alp->end.y, 0, RGB(255, 0, 0));

    if (yp == 0) {

	alp->next = alp->prev = 0;

	ll->y_list = alp;

    } else if (y_start >= yp->start.y) {	/* Insert the new line after y_line */

	while (INCR_EXPR(y_up),

	       ((nyp = yp->next) != NULL &&

		y_start > nyp->start.y)

	    )

	    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 (INCR_EXPR(y_down),

	       ((nyp = yp->prev) != NULL &&

		y_start < nyp->start.y)

	    )

	    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;

    vd_bar(alp->start.x, alp->start.y, alp->end.x, alp->end.y, 1, RGB(0, 255, 0));

    print_al("add ", alp);

}

typedef struct contour_cursor_s {

    segment *prev, *pseg, *pfirst, *plast;

    gx_flattened_iterator *fi;

    bool more_flattened;

    bool first_flattened;

    int dir;

    bool monotonic_y;

    bool monotonic_x;

    bool crossing;

} contour_cursor;

private inline int

compute_dir(const fill_options *fo, fixed y0, fixed y1)

{

    if (max(y0, y1) < fo->ymin)

	return 2;

    if (min(y0, y1) > fo->ymax)

	return 2;

    return (y0 < y1 ? DIR_UP : 

	    y0 > y1 ? DIR_DOWN : DIR_HORIZONTAL);

}

private inline int

add_y_curve_part(line_list *ll, segment *s0, segment *s1, int dir, 

    gx_flattened_iterator *fi, bool more1, bool step_back, bool monotonic_x)

{

    active_line *alp = make_al(ll);

    if (alp == NULL)

	return_error(gs_error_VMerror);

    alp->pseg = (dir == DIR_UP ? s1 : s0);

    alp->direction = dir;

    alp->fi = *fi;

    alp->more_flattened = more1;

    if (dir != DIR_UP && more1)

	gx_flattened_iterator__switch_to_backscan(&alp->fi, more1);

    if (step_back) {

	do {

	    alp->more_flattened = gx_flattened_iterator__prev(&alp->fi);

	    if (compute_dir(ll->fo, alp->fi.ly0, alp->fi.ly1) != 2)

		break;

	} while (alp->more_flattened);

    }

    step_al(alp, false);

    alp->monotonic_y = false;

    alp->monotonic_x = monotonic_x;

    insert_y_line(ll, alp);

    return 0;

}

private inline int

add_y_line(const segment * prev_lp, const segment * lp, int dir, line_list *ll)

{

    return add_y_line_aux(prev_lp, lp, &lp->pt, &prev_lp->pt, dir, ll);

}

private inline int

start_al_pair(line_list *ll, contour_cursor *q, contour_cursor *p)

{

    int code;

    if (q->monotonic_y)

	code = add_y_line(q->prev, q->pseg, DIR_DOWN, ll);

    else 

	code = add_y_curve_part(ll, q->prev, q->pseg, DIR_DOWN, q->fi, 

			    !q->first_flattened, false, q->monotonic_x);

    if (code < 0) 

	return code;

    if (p->monotonic_y)

	code = add_y_line(p->prev, p->pseg, DIR_UP, ll);

    else

	code = add_y_curve_part(ll, p->prev, p->pseg, DIR_UP, p->fi, 

			    p->more_flattened, false, p->monotonic_x);

    return code;

}

/* Start active lines from a minimum of a possibly non-monotonic curve. */

private int

start_al_pair_from_min(line_list *ll, contour_cursor *q)

{

    int dir, code;

    const fill_options * const fo = ll->fo;

    /* q stands at the first segment, which isn't last. */

    do {

	q->more_flattened = gx_flattened_iterator__next(q->fi);

	dir = compute_dir(fo, q->fi->ly0, q->fi->ly1);

	if (q->fi->ly0 > fo->ymax && ll->y_break > q->fi->y0)

	    ll->y_break = q->fi->ly0;

	if (q->fi->ly1 > fo->ymax && ll->y_break > q->fi->ly1)

	    ll->y_break = q->fi->ly1;

	if (dir == DIR_UP && ll->main_dir == DIR_DOWN && q->fi->ly0 >= fo->ymin) {

	    code = add_y_curve_part(ll, q->prev, q->pseg, DIR_DOWN, q->fi, 

			    true, true, q->monotonic_x);

	    if (code < 0) 

		return code; 

	    code = add_y_curve_part(ll, q->prev, q->pseg, DIR_UP, q->fi, 

			    q->more_flattened, false, q->monotonic_x);

	    if (code < 0) 

		return code; 

	} else if (q->fi->ly0 < fo->ymin && q->fi->ly1 >= fo->ymin) {

	    code = add_y_curve_part(ll, q->prev, q->pseg, DIR_UP, q->fi, 

			    q->more_flattened, false, q->monotonic_x);

	    if (code < 0) 

		return code; 

	} else if (q->fi->ly0 >= fo->ymin && q->fi->ly1 < fo->ymin) {

	    code = add_y_curve_part(ll, q->prev, q->pseg, DIR_DOWN, q->fi, 

			    true, false, q->monotonic_x);

	    if (code < 0) 

		return code; 

	}

	q->first_flattened = false;

        q->dir = dir;

	ll->main_dir = (dir == DIR_DOWN ? DIR_DOWN : 

			dir == DIR_UP ? DIR_UP : ll->main_dir);

	if (!q->more_flattened)

	    break;

    } while(q->more_flattened);

    /* q stands at the last segment. */

    return 0;

    /* note : it doesn't depend on the number of curve minimums,

       which may vary due to arithmetic errors. */

}

private inline void

init_contour_cursor(line_list *ll, contour_cursor *q) 

{

    const fill_options * const fo = ll->fo;

    if (q->pseg->type == s_curve) {

	curve_segment *s = (curve_segment *)q->pseg;

	fixed ymin = min(min(q->prev->pt.y, s->p1.y), min(s->p2.y, s->pt.y));

	fixed ymax = max(max(q->prev->pt.y, s->p1.y), max(s->p2.y, s->pt.y));

	bool in_band = ymin <= fo->ymax && ymax >= fo->ymin;

	q->crossing = ymin < fo->ymin && ymax >= fo->ymin;

	q->monotonic_y = !in_band ||

	    (!q->crossing &&

	    ((q->prev->pt.y <= s->p1.y && s->p1.y <= s->p2.y && s->p2.y <= s->pt.y) ||

	     (q->prev->pt.y >= s->p1.y && s->p1.y >= s->p2.y && s->p2.y >= s->pt.y)));

	q->monotonic_x = 

	    ((q->prev->pt.x <= s->p1.x && s->p1.x <= s->p2.x && s->p2.x <= s->pt.x) ||

	     (q->prev->pt.x >= s->p1.x && s->p1.x >= s->p2.x && s->p2.x >= s->pt.x));

    } else 

	q->monotonic_y = true;

    if (!q->monotonic_y) {

	curve_segment *s = (curve_segment *)q->pseg;

	int k = gx_curve_log2_samples(q->prev->pt.x, q->prev->pt.y, s, fo->fixed_flat);

	gx_flattened_iterator__init(q->fi, q->prev->pt.x, q->prev->pt.y, s, k);

    } else {

	q->dir = compute_dir(fo, q->prev->pt.y, q->pseg->pt.y);

	gx_flattened_iterator__init_line(q->fi, 

	    q->prev->pt.x, q->prev->pt.y, q->pseg->pt.x, q->pseg->pt.y); /* fake for curves. */

	vd_bar(q->prev->pt.x, q->prev->pt.y, q->pseg->pt.x, q->pseg->pt.y, 1, RGB(0, 0, 255));

    }

    q->first_flattened = true;

}

private int

scan_contour(line_list *ll, contour_cursor *q)

{

    contour_cursor p;

    gx_flattened_iterator fi, save_fi;

    segment *pseg;

    int code;

    bool only_horizontal = true, saved = false;

    const fill_options * const fo = ll->fo;