path: root/base/gxdtfill.h

/* Copyright (C) 2001-2023 Artifex Software, Inc.
   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.

   Refer to licensing information at http://www.artifex.com or contact
   Artifex Software, Inc.,  39 Mesa Street, Suite 108A, San Francisco,
   CA 94129, USA, for further information.
*/


/* Configurable algorithm for filling a trapezoid */

/*
 * Since we need several statically defined variants of this agorithm,
 * we store it in .h file and include several times into gdevddrw.c and
 * into gxfill.h . Configuration flags (macros) are :
 *
 *   GX_FILL_TRAPEZOID - a name of method
 *   CONTIGUOUS_FILL   - prevent dropouts in narrow trapezoids
 *   SWAP_AXES         - assume swapped axes
 *   FILL_DIRECT       - See LOOP_FILL_RECTANGLE_DIRECT.
 *   LINEAR_COLOR      - Fill with a linear color.
 *   EDGE_TYPE	       - a type of edge structure.
 *   FILL_ATTRS        - operation attributes.
 */

/*
 * Fill a trapezoid.  left.start => left.end and right.start => right.end
 * define the sides; ybot and ytop define the top and bottom.  Requires:
 *      {left,right}->start.y <= ybot <= ytop <= {left,right}->end.y.
 * Lines where left.x >= right.x will not be drawn.  Thanks to Paul Haeberli
 * for an early floating point version of this algorithm.
 */

/*
 * With CONTIGUOUS_FILL is off,
 * this algorithm paints pixels, which centers fall between
 * the left and the right side of the trapezoid, excluding the
 * right side (see PLRM3, 7.5. Scan conversion details).
 * Particularly 0-width trapezoids are not painted.
 *
 * Similarly, it paints pixels, which centers
 * fall between ybot and ytop, excluding ytop.
 * Particularly 0-height trapezoids are not painted.
 *
 * With CONTIGUOUS_FILL is on, it paints a contigous area,
 * adding a minimal number of pixels outside the trapezoid.
 * Particularly it may paint pixels on the right and on the top sides,
 * if they are necessary for the contiguity.
 *
 * With LINEAR_COLOR returns 1 if the gradient arithmetics overflows..
 */

/*
We must paint pixels with index i such that

    Xl <= i + 0.5 < Xr

The condition is is equivalent to

    Xl - 0.5 <= i < Xr - 0.5

which is equivalent to

    (is_integer(Xl - 0.5) ? Xl - 0.5 : ceil(Xl - 0.5)) <= i <
    (is_integer(Xr - 0.5) ? Xr - 0.5 : floor(Xr - 0.5) + 1)

(the last '+1" happens due to the strong comparizon '<')
which is equivalent to

    ceil(Xl - 0.5) <= i < ceil(Xr - 0.5)

trap_line represents the intersection coordinate as a rational value :

    Xl = xl + e - fl
    Xr = xr + e - fr

Where 'e' is 'fixed_epsilon', 0.5 is 'fixed_half', and fl == l.fx / l.h, fr == - r.fx / r.h,
e <= fl < 0, e <= fr < 0.
Let

    xl' := xl + 0.5
    xr' := xr + 0.5

Then

    xl = xl' - 0.5
    xr = xr' - 0.5

    Xl = xl' - 0.5 + e - fl
    Xr = xr' - 0.5 + e - fr

    ceil(xl' - 0.5 + e - fl - 0.5) <= i < ceil(xr' - 0.5 + e - fr - 0.5)

which is equivalent to

    ceil(xl' + e - fl) - 1 <= i < ceil(xr' + e - fr) - 1

which is equivalent to

    (is_integer(xl' + e - fl) ? xl' + e - fl - 1 : ceil(xl' + e - fl) - 1) <= i <
    (is_integer(xr' + e - fr) ? xr' + e - fr - 1 : ceil(xr' + e - fr) - 1)

which is equivalent to

    (is_integer(xl' + e - fl) ? xl' + e - fl - 1 : floor(xl' + e - fl)) <= i <
    (is_integer(xr' + e - fr) ? xr' + e - fr - 1 : floor(xr' + e - fr))

which is equivalent to

    (is_integer(xl') && e == fl ? xl' - 1 : floor(xl' + e - fl)) <= i <
    (is_integer(xr') && e == fr ? xr' - 1 : floor(xr' + e - fr))

Note that e != fl ==> floor(xl' + e - fl) == floor(xl')  due to e - fl < LeastSignificantBit(xl') ;
          e == fl ==> floor(xl' + e - fl) == floor(xl')  due to e - fl == 0;

thus the condition is is equivalent to

    (is_integer(xl') && e == fl ? xl' - 1 : floor(xl')) <= i <
    (is_integer(xr') && e == fr ? xr' - 1 : floor(xr'))

It is computed with the macro 'rational_floor'.

*/

#if defined(GX_FILL_TRAPEZOID) && defined(EDGE_TYPE)

GX_FILL_TRAPEZOID (gx_device * dev, const EDGE_TYPE * left,
    const EDGE_TYPE * right, fixed ybot, fixed ytop, int flags,
    const gx_device_color * pdevc, FILL_ATTRS fa)
{
    const fixed ymin = fixed_pixround(ybot) + fixed_half;
    const fixed ymax = fixed_pixround(ytop);

    if (ymin >= ymax)
        return 0;		/* no scan lines to sample */
    {
        int iy = fixed2int_var(ymin);
        const int iy1 = fixed2int_var(ymax);
        trap_line l, r;
        register int rxl, rxr;
#if !LINEAR_COLOR
        int ry;
#endif
        const fixed
            x0l = left->start.x, x1l = left->end.x, x0r = right->start.x,
            x1r = right->end.x, dxl = x1l - x0l, dxr = x1r - x0r;
        const fixed	/* partial pixel offset to first line to sample */
            ysl = ymin - left->start.y, ysr = ymin - right->start.y;
        fixed fxl;
        int code;
#	if CONTIGUOUS_FILL
            const bool peak0 = ((flags & 1) != 0);
            const bool peak1 = ((flags & 2) != 0);
            int peak_y0 = ybot + fixed_half;
            int peak_y1 = ytop - fixed_half;
#	endif
#	if LINEAR_COLOR
            int num_components = dev->color_info.num_components;
            frac31 lgc[GX_DEVICE_COLOR_MAX_COMPONENTS];
            int32_t lgf[GX_DEVICE_COLOR_MAX_COMPONENTS];
            int32_t lgnum[GX_DEVICE_COLOR_MAX_COMPONENTS];
            frac31 rgc[GX_DEVICE_COLOR_MAX_COMPONENTS];
            int32_t rgf[GX_DEVICE_COLOR_MAX_COMPONENTS];
            int32_t rgnum[GX_DEVICE_COLOR_MAX_COMPONENTS];
            frac31 xgc[GX_DEVICE_COLOR_MAX_COMPONENTS];
            int32_t xgf[GX_DEVICE_COLOR_MAX_COMPONENTS];
            int32_t xgnum[GX_DEVICE_COLOR_MAX_COMPONENTS];
            trap_gradient lg, rg, xg;
#	else
            gx_color_index cindex = pdevc->colors.pure;
            dev_proc_fill_rectangle((*fill_rect)) =
                dev_proc(dev, fill_rectangle);
#	endif

        if_debug2m('z', dev->memory, "[z]y=[%d,%d]\n", iy, iy1);

        l.h = left->end.y - left->start.y;
        if (l.h == 0)
           return 0;
        r.h = right->end.y - right->start.y;
        if (r.h == 0)
           return 0;
        l.x = x0l + (fixed_half - fixed_epsilon);
        r.x = x0r + (fixed_half - fixed_epsilon);
#if !LINEAR_COLOR
        ry = iy;
#endif

/*
 * Free variables of FILL_TRAP_RECT:
 *	SWAP_AXES, pdevc, dev, fa
 * Free variables of FILL_TRAP_RECT_DIRECT:
 *	SWAP_AXES, fill_rect, dev, cindex
 */
#define FILL_TRAP_RECT_INDIRECT(x,y,w,h)\
  (SWAP_AXES ? gx_fill_rectangle_device_rop(y, x, h, w, pdevc, dev, fa) :\
   gx_fill_rectangle_device_rop(x, y, w, h, pdevc, dev, fa))
#define FILL_TRAP_RECT_DIRECT(x,y,w,h)\
  (SWAP_AXES ? (*fill_rect)(dev, y, x, h, w, cindex) :\
   (*fill_rect)(dev, x, y, w, h, cindex))

#if LINEAR_COLOR
#   define FILL_TRAP_RECT(x,y,w,h)\
        (!(w) ? 0 : dev_proc(dev, fill_linear_color_scanline)(dev, fa, x, y, w, xg.c, xg.f, xg.num, xg.den))
#else
#   define FILL_TRAP_RECT(x,y,w,h)\
        (FILL_DIRECT ? FILL_TRAP_RECT_DIRECT(x,y,w,h) : FILL_TRAP_RECT_INDIRECT(x,y,w,h))
#endif

        /* Compute the dx/dy ratios. */

        /*
         * Compute the x offsets at the first scan line to sample.  We need
         * to be careful in computing ys# * dx#f {/,%} h# because the
         * multiplication may overflow.  We know that all the quantities
         * involved are non-negative, and that ys# is usually less than 1 (as
         * a fixed, of course); this gives us a cheap conservative check for
         * overflow in the multiplication.
         */
#define YMULT_QUO(ys, tl)\
  (ys < fixed_1 && tl.df < YMULT_LIMIT ? ys * tl.df / tl.h :\
   fixed_mult_quo(ys, tl.df, tl.h))

#if CONTIGUOUS_FILL
/*
 * If left and right boundary round to same pixel index,
 * we would not paing the scan and would get a dropout.
 * Check for this case and choose one of two pixels
 * which is closer to the "axis". We need to exclude
 * 'peak' because it would paint an excessive pixel.
 */
#define SET_MINIMAL_WIDTH(ixl, ixr, l, r) \
    if (ixl == ixr) \
        if ((!peak0 || iy >= peak_y0) && (!peak1 || iy <= peak_y1)) {\
            fixed x = int2fixed(ixl) + fixed_half;\
            if (x - l.x < r.x - x)\
                ++ixr;\
            else\
                --ixl;\
        }

#define CONNECT_RECTANGLES(ixl, ixr, rxl, rxr, iy, ry, adj1, adj2, fill)\
    if (adj1 < adj2) {\
        if (iy - ry > 1) {\
            code = fill(rxl, ry, rxr - rxl, iy - ry - 1);\
            if (code < 0)\
                goto xit;\
            ry = iy - 1;\
        }\
        adj1 = adj2 = (adj2 + adj2) / 2;\
    }

#else
#define SET_MINIMAL_WIDTH(ixl, ixr, l, r) DO_NOTHING
#define CONNECT_RECTANGLES(ixl, ixr, rxl, rxr, iy, ry, adj1, adj2, fill) DO_NOTHING
#endif
        if (fixed_floor(l.x) == fixed_pixround(x1l)) {
            /* Left edge is vertical, we don't need to increment. */
            l.di = 0, l.df = 0;
            fxl = 0;
        } else {
            compute_dx(&l, dxl, ysl);
            fxl = YMULT_QUO(ysl, l);
            l.x += fxl;
        }
        if (fixed_floor(r.x) == fixed_pixround(x1r)) {
            /* Right edge is vertical.  If both are vertical, */
            /* we have a rectangle. */
#	    if !LINEAR_COLOR
                if (l.di == 0 && l.df == 0) {
                    rxl = fixed2int_var(l.x);
                    rxr = fixed2int_var(r.x);
                    SET_MINIMAL_WIDTH(rxl, rxr, l, r);
                    code = FILL_TRAP_RECT(rxl, ry, rxr - rxl, iy1 - ry);
                    goto xit;
                }
#	    endif
            r.di = 0, r.df = 0;
        }
        /*
         * The test for fxl != 0 is required because the right edge might
         * cross some pixel centers even if the left edge doesn't.
         */
        else if (dxr == dxl && fxl != 0) {
            if (l.di == 0)
                r.di = 0, r.df = l.df;
            else
                compute_dx(&r, dxr, ysr);
            if (ysr == ysl && r.h == l.h)
                r.x += fxl;
            else
                r.x += YMULT_QUO(ysr, r);
        } else {
            compute_dx(&r, dxr, ysr);
            r.x += YMULT_QUO(ysr, r);
        }
        /* Compute one line's worth of dx/dy. */
        compute_ldx(&l, ysl);
        compute_ldx(&r, ysr);
        /* We subtracted fixed_epsilon from l.x, r.x to simplify rounding
           when the rational part is zero. Now add it back to get xl', xr' */
        l.x += fixed_epsilon;
        r.x += fixed_epsilon;
#	if LINEAR_COLOR
#	    ifdef DEBUG
                if (check_gradient_overflow(left, right)) {
                    /* The caller must care of.
                       Checking it here looses some performance with triangles. */
                    return_error(gs_error_unregistered);
                }
#	    endif
            lg.c = lgc;
            lg.f = lgf;
            lg.num = lgnum;
            rg.c = rgc;
            rg.f = rgf;
            rg.num = rgnum;
            xg.c = xgc;
            xg.f = xgf;
            xg.num = xgnum;
            code = init_gradient(&lg, fa, left, right, &l, ymin, num_components);
            if (code < 0)
                return code;
            code = init_gradient(&rg, fa, right, left, &r, ymin, num_components);
            if (code < 0)
                return code;

#	endif

#define rational_floor(tl)\
  fixed2int_var(fixed_is_int(tl.x) && tl.xf == -tl.h ? tl.x - fixed_1 : tl.x)
#define STEP_LINE(ix, tl)\
  tl.x += tl.ldi;\
  if ( (tl.xf += tl.ldf) >= 0 ) tl.xf -= tl.h, tl.x++;\
  ix = rational_floor(tl)

        rxl = rational_floor(l);
        rxr = rational_floor(r);
        SET_MINIMAL_WIDTH(rxl, rxr, l, r);
        while (LINEAR_COLOR ? 1 : ++iy != iy1) {
#	    if LINEAR_COLOR
                if (rxl != rxr) {
                    code = set_x_gradient(&xg, &lg, &rg, &l, &r, rxl, rxr, num_components);
                    if (code < 0)
                        goto xit;
                    code = FILL_TRAP_RECT(rxl, iy, rxr - rxl, 1);
                    if (code < 0)
                        goto xit;
                }
                if (++iy == iy1)
                    break;
                STEP_LINE(rxl, l);
                STEP_LINE(rxr, r);
                step_gradient(&lg, num_components);
                step_gradient(&rg, num_components);
#	    else
                register int ixl, ixr;

                STEP_LINE(ixl, l);
                STEP_LINE(ixr, r);
                SET_MINIMAL_WIDTH(ixl, ixr, l, r);
                if (ixl != rxl || ixr != rxr) {
                    CONNECT_RECTANGLES(ixl, ixr, rxl, rxr, iy, ry, rxr, ixl, FILL_TRAP_RECT);
                    CONNECT_RECTANGLES(ixl, ixr, rxl, rxr, iy, ry, ixr, rxl, FILL_TRAP_RECT);
                    code = FILL_TRAP_RECT(rxl, ry, rxr - rxl, iy - ry);
                    if (code < 0)
                        goto xit;
                    rxl = ixl, rxr = ixr, ry = iy;
                }
#	    endif
        }
#	if !LINEAR_COLOR
            code = FILL_TRAP_RECT(rxl, ry, rxr - rxl, iy - ry);
#	else
            code = 0;
#	endif
#undef STEP_LINE
#undef SET_MINIMAL_WIDTH
#undef CONNECT_RECTANGLES
#undef FILL_TRAP_RECT
#undef FILL_TRAP_RECT_DIRECT
#undef FILL_TRAP_RECT_INRECT
#undef YMULT_QUO
xit:	if (code < 0 && FILL_DIRECT)
            return_error(code);
        return_if_interrupt(dev->memory);
        return code;
    }
}

#undef GX_FILL_TRAPEZOID
#undef CONTIGUOUS_FILL
#undef SWAP_AXES
#undef FLAGS_TYPE

#else
int dummy;
#endif