/src/ghostpdl/base/gxfilltr.h

Source (jump to first uncovered line)
/* 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 decomposing a spot into trapezoids. */

/*
 * Since we need several statically defined variants of this algorithm,
 * we store it in .h file and include it several times into gxfill.c .
 * Configuration macros (template arguments) are :
 *
 *  IS_SPOTAN - is the target device a spot analyzer ("spotan").
 *  SMART_WINDING - even-odd filling rule for each contour independently.
 *  FILL_ADJUST - fill adjustment is not zero
 *  FILL_DIRECT - See LOOP_FILL_RECTANGLE_DIRECT.
 *  TEMPLATE_spot_into_trapezoids - the name of the procedure to generate.
 *  ADVANCE_WINDING(inside, alp, ll) - a macro for advancing the winding counter.
 *  INSIDE_PATH_P(inside, rule) - a macro for checking the winding rule.
*/

#if defined(TEMPLATE_spot_into_trapezoids) && defined(INCR) && defined(FILL_ADJUST) && defined(LOOP_FILL_RECTANGLE_DIRECT) && defined(COVERING_PIXEL_CENTERS)

/* ---------------- Trapezoid decomposition loop ---------------- */

/* Takes lines off of y_list and adds them to */
/* x_list as needed.  band_mask limits the size of each band, */
/* by requiring that ((y1 - 1) & band_mask) == (y0 & band_mask). */
static int
TEMPLATE_spot_into_trapezoids (line_list *ll, fixed band_mask)
{
    const fill_options fo = *ll->fo;
    int rule = fo.rule;
    const fixed y_limit = fo.ymax;
    active_line *yll = ll->y_list;
    fixed y;
    int code;
    const bool all_bands = fo.is_spotan;

    if (yll == 0)
        return 0;   /* empty list */
    y = yll->start.y;   /* first Y value */
    ll->x_list = 0;
    ll->x_head.x_current = min_fixed; /* stop backward scan */
    while (1) {
        fixed y1;
        active_line *alp;
        bool covering_pixel_centers;

        INCR(iter);
        /* Move newly active lines from y to x list. */
        while (yll != 0 && yll->start.y == y) {
            active_line *ynext = yll->next; /* insert smashes next/prev links */

            ll->y_list = ynext;
            if (ll->y_line == yll)
                ll->y_line = ynext;
            if (ynext != NULL)
                ynext->prev = NULL;
            if (yll->direction == DIR_HORIZONTAL) {
                /*
                 * This is a hack to make sure that isolated horizontal
                 * lines get stroked.
                 */
                int yi = fixed2int_pixround(y - (!FILL_ADJUST ? 0 : fo.adjust_below));
                int xi, wi;

                if (yll->start.x <= yll->end.x) {
                    xi = fixed2int_pixround(yll->start.x - (!FILL_ADJUST ? 0 : fo.adjust_left));
                    wi = fixed2int_pixround(yll->end.x + (!FILL_ADJUST ? 0 : fo.adjust_right)) - xi;
                } else {
                    xi = fixed2int_pixround(yll->end.x - (!FILL_ADJUST ? 0 : fo.adjust_left));
                    wi = fixed2int_pixround(yll->start.x + (!FILL_ADJUST ? 0 : fo.adjust_right)) - xi;
                }
                code = LOOP_FILL_RECTANGLE_DIRECT(&fo, xi, yi, wi, 1);
                if (code < 0)
                    return code;
            } else
                insert_x_new(yll, ll);
            yll = ynext;
        }
        /* Mustn't leave by Y before process_h_segments. */
        if (ll->x_list == 0) { /* No active lines, skip to next start */
            if (yll == 0)
                break;   /* no lines left */
            /* We don't close margin set here because the next set
             * may fall into same window. */
            y = yll->start.y;
            ll->h_list1 = ll->h_list0;
            ll->h_list0 = 0;
            continue;
        }
        /* Find the next evaluation point. */
        /* Start by finding the smallest y value */
        /* at which any currently active line ends */
        /* (or the next to-be-active line begins). */
        y1 = (yll != 0 ? yll->start.y : ll->y_break);
        /* Make sure we don't exceed the maximum band height. */
        {
            fixed y_band = y | ~band_mask;

            if (y1 > y_band)
                y1 = y_band + 1;
        }
        for (alp = ll->x_list; alp != 0; alp = alp->next) {
            if (alp->end.y < y1)
                y1 = alp->end.y;
        }
# ifdef DEBUG
            if (gs_debug_c('F')) {
                dmlprintf2(ll->memory, "[F]before loop: y=%f y1=%f:\n",
                          fixed2float(y), fixed2float(y1));
                print_line_list(ll->memory, ll->x_list);
            }
# endif
        if (y == y1) {
            code = process_h_segments(ll, y);
            if (code < 0)
                return code;
            { int code1 = move_al_by_y(ll, y1);
                if (code1 < 0)
                    return code1;
            }
            if (code > 0) {
                yll = ll->y_list; /* add_y_line_aux in process_h_segments changes it. */
                continue;
            }

        }
        if (y >= y_limit)
            break;
        /* Now look for line intersections before y1. */
        covering_pixel_centers = COVERING_PIXEL_CENTERS(y, y1,
                            (!FILL_ADJUST ? 0 : fo.adjust_below),
                            (!FILL_ADJUST ? 0 : fo.adjust_above));
        if (y != y1) {
            intersect_al(ll, y, &y1, (covering_pixel_centers ? 1 : -1), all_bands); /* May change y1. */
            covering_pixel_centers = COVERING_PIXEL_CENTERS(y, y1,
                            (!FILL_ADJUST ? 0 : fo.adjust_below),
                            (!FILL_ADJUST ? 0 : fo.adjust_above));
        }
        /* Fill a multi-trapezoid band for the active lines. */
        if (covering_pixel_centers || all_bands) {
            int inside = 0;
            active_line *flp = NULL;

            if (SMART_WINDING)
                memset(ll->windings, 0, sizeof(ll->windings[0]) * ll->contour_count);
            INCR(band);
            /* Generate trapezoids */
            for (alp = ll->x_list; alp != 0; alp = alp->next) {
                int code;

                print_al(ll->memory, "step", alp);
                INCR(band_step);
                if (!INSIDE_PATH_P(inside, rule)) {   /* i.e., outside */
                    ADVANCE_WINDING(inside, alp, ll);
                    if (INSIDE_PATH_P(inside, rule)) /* about to go in */
                        flp = alp;
                    continue;
                }
                /* We're inside a region being filled. */
                ADVANCE_WINDING(inside, alp, ll);
                if (INSIDE_PATH_P(inside, rule)) /* not about to go out */
                    continue;
                /* We just went from inside to outside,
                   chech whether we'll immediately go inside. */
                if (alp->next != NULL &&
                    alp->x_current == alp->next->x_current &&
                    alp->x_next == alp->next->x_next) {
                    /* If the next trapezoid contacts this one, unite them.
                       This simplifies data for the spot analyzer
                       and reduces the number of trapezoids in the rasterization.
                       Note that the topology possibly isn't exactly such
                       as we generate by this uniting :
                       Due to arithmetic errors in x_current, x_next
                       we can unite things, which really are not contacting.
                       But this level of the topology precision is enough for
                       the glyph grid fitting.
                       Also note that
                       while a rasterization with dropout prevention
                       it may cause a shift when choosing a pixel
                       to paint with a narrow trapezoid. */
                    alp = alp->next;
                    ADVANCE_WINDING(inside, alp, ll);
                    continue;
                }
                /* We just went from inside to outside, so fill the region. */
                INCR(band_fill);
                if (FILL_ADJUST && !(flp->end.x == flp->start.x && alp->end.x == alp->start.x) &&
                    (fo.adjust_below | fo.adjust_above) != 0) {
                    if (FILL_DIRECT)
                        code = slant_into_trapezoids__fd(ll, flp, alp, y, y1);
                    else
                        code = slant_into_trapezoids__nd(ll, flp, alp, y, y1);
                } else {
                    fixed ybot = max(y, fo.pbox->p.y);
                    fixed ytop = min(y1, fo.pbox->q.y);

                    if (IS_SPOTAN) {
                        /* We can't pass data through the device interface because
                           we need to pass segment pointers. We're unhappy of that. */
                        code = gx_san_trap_store((gx_device_spot_analyzer *)fo.dev,
                            y, y1, flp->x_current, alp->x_current, flp->x_next, alp->x_next,
                            flp->pseg, alp->pseg, flp->direction, alp->direction);
                    } else {
                        if (flp->end.x == flp->start.x && alp->end.x == alp->start.x) {
                            if (FILL_ADJUST) {
                                ybot = max(y  - fo.adjust_below, fo.pbox->p.y);
                                ytop = min(y1 + fo.adjust_above, fo.pbox->q.y);
                            }
                            if (ytop > ybot) {
                                int yi = fixed2int_pixround(ybot);
                                int hi = fixed2int_pixround(ytop) - yi;
                                int xli = fixed2int_var_pixround(flp->end.x - (!FILL_ADJUST ? 0 : fo.adjust_left));
                                int xi  = fixed2int_var_pixround(alp->end.x + (!FILL_ADJUST ? 0 : fo.adjust_right));

#ifdef FILL_ZERO_WIDTH
                                if ( xli == xi && FILL_ADJUST &&
                                     (fo.adjust_right | fo.adjust_left) != 0 ) {
#else
                                if (0) {
#endif
                                    /*
                                    * The scan is empty but we should paint something
                                    * against a dropout. Choose one of two pixels which
                                    * is closer to the "axis".
                                    */
                                    fixed xx = int2fixed(xli);

                                    if (xx - flp->end.x < alp->end.x - xx)
                                        ++xi;
                                    else
                                        --xli;
                                }
                                code = LOOP_FILL_RECTANGLE_DIRECT(&fo, xli, yi, xi - xli, hi);
                            } else
                                code = 0;
                        } else if (ybot < ytop) {
                            gs_fixed_edge le, re;

                            le.start = flp->start;
                            le.end = flp->end;
                            re.start = alp->start;
                            re.end = alp->end;
                            code = fo.fill_trap(fo.dev,
                                    &le, &re, ybot, ytop, false, fo.pdevc, fo.lop);
                        } else
                            code = 0;
                    }
                }
                if (code < 0)
                    return code;
            }
        }
        code = move_al_by_y(ll, y1);
        if (code < 0)
            return code;
        ll->h_list1 = ll->h_list0;
        ll->h_list0 = 0;
        y = y1;
    }
    return 0;
}

#else
int dummy;
#endif

Coverage Report

Created: 2025-06-24 07:01

Line	Count	Source (jump to first uncovered line)
1		/* Copyright (C) 2001-2023 Artifex Software, Inc.
2		All Rights Reserved.
3
4		This software is provided AS-IS with no warranty, either express or
5		implied.
6
7		This software is distributed under license and may not be copied,
8		modified or distributed except as expressly authorized under the terms
9		of the license contained in the file LICENSE in this distribution.
10
11		Refer to licensing information at http://www.artifex.com or contact
12		Artifex Software, Inc., 39 Mesa Street, Suite 108A, San Francisco,
13		CA 94129, USA, for further information.
14		*/
15
16
17		/* Configurable algorithm for decomposing a spot into trapezoids. */
18
19		/*
20		* Since we need several statically defined variants of this algorithm,
21		* we store it in .h file and include it several times into gxfill.c .
22		* Configuration macros (template arguments) are :
23		*
24		* IS_SPOTAN - is the target device a spot analyzer ("spotan").
25		* SMART_WINDING - even-odd filling rule for each contour independently.
26		* FILL_ADJUST - fill adjustment is not zero
27		* FILL_DIRECT - See LOOP_FILL_RECTANGLE_DIRECT.
28		* TEMPLATE_spot_into_trapezoids - the name of the procedure to generate.
29		* ADVANCE_WINDING(inside, alp, ll) - a macro for advancing the winding counter.
30		* INSIDE_PATH_P(inside, rule) - a macro for checking the winding rule.
31		*/
32
33		#if defined(TEMPLATE_spot_into_trapezoids) && defined(INCR) && defined(FILL_ADJUST) && defined(LOOP_FILL_RECTANGLE_DIRECT) && defined(COVERING_PIXEL_CENTERS)
34
35		/* ---------------- Trapezoid decomposition loop ---------------- */
36
37		/* Takes lines off of y_list and adds them to */
38		/* x_list as needed. band_mask limits the size of each band, */
39		/* by requiring that ((y1 - 1) & band_mask) == (y0 & band_mask). */
40		static int
41		TEMPLATE_spot_into_trapezoids (line_list *ll, fixed band_mask)
42	0	{
43	0	const fill_options fo = *ll->fo;
44	0	int rule = fo.rule;
45	0	const fixed y_limit = fo.ymax;
46	0	active_line *yll = ll->y_list;
47	0	fixed y;
48	0	int code;
49	0	const bool all_bands = fo.is_spotan;
50
51	0	if (yll == 0)
52	0	return 0; /* empty list */
53	0	y = yll->start.y; /* first Y value */
54	0	ll->x_list = 0;
55	0	ll->x_head.x_current = min_fixed; /* stop backward scan */
56	0	while (1) {
57	0	fixed y1;
58	0	active_line *alp;
59	0	bool covering_pixel_centers;
60
61	0	INCR(iter);
62		/* Move newly active lines from y to x list. */
63	0	while (yll != 0 && yll->start.y == y) {
64	0	active_line ynext = yll->next; / insert smashes next/prev links */
65
66	0	ll->y_list = ynext;
67	0	if (ll->y_line == yll)
68	0	ll->y_line = ynext;
69	0	if (ynext != NULL)
70	0	ynext->prev = NULL;
71	0	if (yll->direction == DIR_HORIZONTAL) {
72		/*
73		* This is a hack to make sure that isolated horizontal
74		* lines get stroked.
75		*/
76	0	int yi = fixed2int_pixround(y - (!FILL_ADJUST ? 0 : fo.adjust_below));
77	0	int xi, wi;
78
79	0	if (yll->start.x <= yll->end.x) {
80	0	xi = fixed2int_pixround(yll->start.x - (!FILL_ADJUST ? 0 : fo.adjust_left));
81	0	wi = fixed2int_pixround(yll->end.x + (!FILL_ADJUST ? 0 : fo.adjust_right)) - xi;
82	0	} else {
83	0	xi = fixed2int_pixround(yll->end.x - (!FILL_ADJUST ? 0 : fo.adjust_left));
84	0	wi = fixed2int_pixround(yll->start.x + (!FILL_ADJUST ? 0 : fo.adjust_right)) - xi;
85	0	}
86	0	code = LOOP_FILL_RECTANGLE_DIRECT(&fo, xi, yi, wi, 1);
87	0	if (code < 0)
88	0	return code;
89	0	} else
90	0	insert_x_new(yll, ll);
91	0	yll = ynext;
92	0	}
93		/* Mustn't leave by Y before process_h_segments. */
94	0	if (ll->x_list == 0) { /* No active lines, skip to next start */
95	0	if (yll == 0)
96	0	break; /* no lines left */
97		/* We don't close margin set here because the next set
98		* may fall into same window. */
99	0	y = yll->start.y;
100	0	ll->h_list1 = ll->h_list0;
101	0	ll->h_list0 = 0;
102	0	continue;
103	0	}
104		/* Find the next evaluation point. */
105		/* Start by finding the smallest y value */
106		/* at which any currently active line ends */
107		/* (or the next to-be-active line begins). */
108	0	y1 = (yll != 0 ? yll->start.y : ll->y_break);
109		/* Make sure we don't exceed the maximum band height. */
110	0	{
111	0	fixed y_band = y \| ~band_mask;
112
113	0	if (y1 > y_band)
114	0	y1 = y_band + 1;
115	0	}
116	0	for (alp = ll->x_list; alp != 0; alp = alp->next) {
117	0	if (alp->end.y < y1)
118	0	y1 = alp->end.y;
119	0	}
120		# ifdef DEBUG
121		if (gs_debug_c('F')) {
122		dmlprintf2(ll->memory, "[F]before loop: y=%f y1=%f:\n",
123		fixed2float(y), fixed2float(y1));
124		print_line_list(ll->memory, ll->x_list);
125		}
126		# endif
127	0	if (y == y1) {
128	0	code = process_h_segments(ll, y);
129	0	if (code < 0)
130	0	return code;
131	0	{ int code1 = move_al_by_y(ll, y1);
132	0	if (code1 < 0)
133	0	return code1;
134	0	}
135	0	if (code > 0) {
136	0	yll = ll->y_list; /* add_y_line_aux in process_h_segments changes it. */
137	0	continue;
138	0	}
139
140	0	}
141	0	if (y >= y_limit)
142	0	break;
143		/* Now look for line intersections before y1. */
144	0	covering_pixel_centers = COVERING_PIXEL_CENTERS(y, y1,
145	0	(!FILL_ADJUST ? 0 : fo.adjust_below),
146	0	(!FILL_ADJUST ? 0 : fo.adjust_above));
147	0	if (y != y1) {
148	0	intersect_al(ll, y, &y1, (covering_pixel_centers ? 1 : -1), all_bands); /* May change y1. */
149	0	covering_pixel_centers = COVERING_PIXEL_CENTERS(y, y1,
150	0	(!FILL_ADJUST ? 0 : fo.adjust_below),
151	0	(!FILL_ADJUST ? 0 : fo.adjust_above));
152	0	}
153		/* Fill a multi-trapezoid band for the active lines. */
154	0	if (covering_pixel_centers \|\| all_bands) {
155	0	int inside = 0;
156	0	active_line *flp = NULL;
157
158	0	if (SMART_WINDING)
159	0	memset(ll->windings, 0, sizeof(ll->windings[0]) * ll->contour_count);
160	0	INCR(band);
161		/* Generate trapezoids */
162	0	for (alp = ll->x_list; alp != 0; alp = alp->next) {
163	0	int code;
164
165	0	print_al(ll->memory, "step", alp);
166	0	INCR(band_step);
167	0	if (!INSIDE_PATH_P(inside, rule)) { /* i.e., outside */
168	0	ADVANCE_WINDING(inside, alp, ll);
169	0	if (INSIDE_PATH_P(inside, rule)) /* about to go in */
170	0	flp = alp;
171	0	continue;
172	0	}
173		/* We're inside a region being filled. */
174	0	ADVANCE_WINDING(inside, alp, ll);
175	0	if (INSIDE_PATH_P(inside, rule)) /* not about to go out */
176	0	continue;
177		/* We just went from inside to outside,
178		chech whether we'll immediately go inside. */
179	0	if (alp->next != NULL &&
180	0	alp->x_current == alp->next->x_current &&
181	0	alp->x_next == alp->next->x_next) {
182		/* If the next trapezoid contacts this one, unite them.
183		This simplifies data for the spot analyzer
184		and reduces the number of trapezoids in the rasterization.
185		Note that the topology possibly isn't exactly such
186		as we generate by this uniting :
187		Due to arithmetic errors in x_current, x_next
188		we can unite things, which really are not contacting.
189		But this level of the topology precision is enough for
190		the glyph grid fitting.
191		Also note that
192		while a rasterization with dropout prevention
193		it may cause a shift when choosing a pixel
194		to paint with a narrow trapezoid. */
195	0	alp = alp->next;
196	0	ADVANCE_WINDING(inside, alp, ll);
197	0	continue;
198	0	}
199		/* We just went from inside to outside, so fill the region. */
200	0	INCR(band_fill);
201	0	if (FILL_ADJUST && !(flp->end.x == flp->start.x && alp->end.x == alp->start.x) &&
202	0	(fo.adjust_below \| fo.adjust_above) != 0) {
203	0	if (FILL_DIRECT)
204	0	code = slant_into_trapezoids__fd(ll, flp, alp, y, y1);
205	0	else
206	0	code = slant_into_trapezoids__nd(ll, flp, alp, y, y1);
207	0	} else {
208	0	fixed ybot = max(y, fo.pbox->p.y);
209	0	fixed ytop = min(y1, fo.pbox->q.y);
210
211	0	if (IS_SPOTAN) {
212		/* We can't pass data through the device interface because
213		we need to pass segment pointers. We're unhappy of that. */
214	0	code = gx_san_trap_store((gx_device_spot_analyzer *)fo.dev,
215	0	y, y1, flp->x_current, alp->x_current, flp->x_next, alp->x_next,
216	0	flp->pseg, alp->pseg, flp->direction, alp->direction);
217	0	} else {
218	0	if (flp->end.x == flp->start.x && alp->end.x == alp->start.x) {
219	0	if (FILL_ADJUST) {
220	0	ybot = max(y - fo.adjust_below, fo.pbox->p.y);
221	0	ytop = min(y1 + fo.adjust_above, fo.pbox->q.y);
222	0	}
223	0	if (ytop > ybot) {
224	0	int yi = fixed2int_pixround(ybot);
225	0	int hi = fixed2int_pixround(ytop) - yi;
226	0	int xli = fixed2int_var_pixround(flp->end.x - (!FILL_ADJUST ? 0 : fo.adjust_left));
227	0	int xi = fixed2int_var_pixround(alp->end.x + (!FILL_ADJUST ? 0 : fo.adjust_right));
228
229		#ifdef FILL_ZERO_WIDTH
230		if ( xli == xi && FILL_ADJUST &&
231		(fo.adjust_right \| fo.adjust_left) != 0 ) {
232		#else
233	0	if (0) {
234	0	#endif
235		/*
236		* The scan is empty but we should paint something
237		* against a dropout. Choose one of two pixels which
238		* is closer to the "axis".
239		*/
240	0	fixed xx = int2fixed(xli);
241
242	0	if (xx - flp->end.x < alp->end.x - xx)
243	0	++xi;
244	0	else
245	0	--xli;
246	0	}
247	0	code = LOOP_FILL_RECTANGLE_DIRECT(&fo, xli, yi, xi - xli, hi);
248	0	} else
249	0	code = 0;
250	0	} else if (ybot < ytop) {
251	0	gs_fixed_edge le, re;
252
253	0	le.start = flp->start;
254	0	le.end = flp->end;
255	0	re.start = alp->start;
256	0	re.end = alp->end;
257	0	code = fo.fill_trap(fo.dev,
258	0	&le, &re, ybot, ytop, false, fo.pdevc, fo.lop);
259	0	} else
260	0	code = 0;
261	0	}
262	0	}
263	0	if (code < 0)
264	0	return code;
265	0	}
266	0	}
267	0	code = move_al_by_y(ll, y1);
268	0	if (code < 0)
269	0	return code;
270	0	ll->h_list1 = ll->h_list0;
271	0	ll->h_list0 = 0;
272	0	y = y1;
273	0	}
274	0	return 0;
275	0	} Unexecuted instantiation: gxfill.c:spot_into_trapezoids__spotan Unexecuted instantiation: gxfill.c:spot_into_trapezoids__aj_fd Unexecuted instantiation: gxfill.c:spot_into_trapezoids__aj_nd Unexecuted instantiation: gxfill.c:spot_into_trapezoids__nj_fd_sw Unexecuted instantiation: gxfill.c:spot_into_trapezoids__nj_nd_sw Unexecuted instantiation: gxfill.c:spot_into_trapezoids__nj_fd Unexecuted instantiation: gxfill.c:spot_into_trapezoids__nj_nd
276
277		#else
278		int dummy;
279		#endif