Commit | Line | Data |
---|---|---|
315fde06 WJ |
1 | /* Copyright (C) 1989, 1990, 1991 Aladdin Enterprises. All rights reserved. |
2 | Distributed by Free Software Foundation, Inc. | |
3 | ||
4 | This file is part of Ghostscript. | |
5 | ||
6 | Ghostscript is distributed in the hope that it will be useful, but | |
7 | WITHOUT ANY WARRANTY. No author or distributor accepts responsibility | |
8 | to anyone for the consequences of using it or for whether it serves any | |
9 | particular purpose or works at all, unless he says so in writing. Refer | |
10 | to the Ghostscript General Public License for full details. | |
11 | ||
12 | Everyone is granted permission to copy, modify and redistribute | |
13 | Ghostscript, but only under the conditions described in the Ghostscript | |
14 | General Public License. A copy of this license is supposed to have been | |
15 | given to you along with Ghostscript so you can know your rights and | |
16 | responsibilities. It should be in a file named COPYING. Among other | |
17 | things, the copyright notice and this notice must be preserved on all | |
18 | copies. */ | |
19 | ||
20 | /* gxfill.c */ | |
21 | /* Lower-level path filling procedures for GhostScript library */ | |
22 | #include "gx.h" | |
23 | #include "gserrors.h" | |
24 | #include "gxfixed.h" | |
25 | #include "gxmatrix.h" | |
26 | #include "gxdevice.h" /* for gx_color_index */ | |
27 | #include "gzcolor.h" | |
28 | #include "gzpath.h" | |
29 | #include "gzstate.h" | |
30 | #include "gxcpath.h" | |
31 | ||
32 | /* Import the fixed * fixed / fixed routine from gxdraw.c. */ | |
33 | /* The second argument must be less than or equal to the third; */ | |
34 | /* all must be non-negative, and the last must be non-zero. */ | |
35 | extern fixed fixed_mult_quo(P3(fixed, fixed, fixed)); | |
36 | ||
37 | /* Define the structure for keeping track of active lines. */ | |
38 | typedef struct active_line_s active_line; | |
39 | struct active_line_s { | |
40 | gs_fixed_point start; /* x,y where line starts */ | |
41 | gs_fixed_point end; /* x,y where line ends */ | |
42 | #define al_dx(alp) ((alp)->end.x - (alp)->start.x) | |
43 | #define al_dy(alp) ((alp)->end.y - (alp)->start.y) | |
44 | fixed y_fast_max; /* can do x_at_y in fixed point */ | |
45 | /* if y <= y_fast_max */ | |
46 | #define set_al_points(alp, startp, endp)\ | |
47 | (alp)->y_fast_max = max_fixed / (((endp).x > (startp).x ?\ | |
48 | (endp).x - (startp).x : (startp).x - (endp).x) | 1) + (startp).y,\ | |
49 | (alp)->start = startp, (alp)->end = endp | |
50 | #define al_x_at_y(alp, yv)\ | |
51 | ((yv) == (alp)->end.y ? (alp)->end.x :\ | |
52 | ((yv) <= (alp)->y_fast_max ?\ | |
53 | ((yv) - (alp)->start.y) * al_dx(alp) / al_dy(alp) :\ | |
54 | (stat(n_slow_x),\ | |
55 | fixed_mult_quo(al_dx(alp), (yv) - (alp)->start.y, al_dy(alp)))) +\ | |
56 | (alp)->start.x) | |
57 | fixed x_current; /* current x position */ | |
58 | fixed x_next; /* x position at end of band */ | |
59 | segment *pseg; /* endpoint of this line */ | |
60 | int direction; /* direction of line segment */ | |
61 | #define dir_up 1 | |
62 | #define dir_down (-1) | |
63 | /* "Pending" lines (not reached in the Y ordering yet) use next and prev */ | |
64 | /* to order lines by increasing starting Y. "Active" lines (being scanned) */ | |
65 | /* use next and prev to order lines by increasing current X, or if the */ | |
66 | /* current Xs are equal, by increasing final X. */ | |
67 | active_line *prev, *next; | |
68 | /* Link together active_lines allocated individually */ | |
69 | active_line *alloc_next; | |
70 | }; | |
71 | ||
72 | /* Define the ordering criterion for active lines. */ | |
73 | /* The xc argument is a copy of lp2->x_current. */ | |
74 | #define x_precedes(lp1, lp2, xc)\ | |
75 | (lp1->x_current < xc || lp1->x_current == xc &&\ | |
76 | (lp1->start.x > lp2->start.x || lp1->end.x < lp2->end.x)) | |
77 | ||
78 | #ifdef DEBUG | |
79 | /* Internal procedures for printing active lines */ | |
80 | private void | |
81 | print_active_line(char *label, active_line *alp) | |
82 | { dprintf5("[f]%s %lx(%d): x_current=%f x_next=%f\n", | |
83 | label, (ulong)alp, alp->direction, | |
84 | fixed2float(alp->x_current), fixed2float(alp->x_next)); | |
85 | dprintf5(" start=(%f,%f) pt_end=%lx(%f,%f)\n", | |
86 | fixed2float(alp->start.x), fixed2float(alp->start.y), | |
87 | (ulong)alp->pseg, | |
88 | fixed2float(alp->end.x), fixed2float(alp->end.y)); | |
89 | dprintf2(" prev=%lx next=%lx\n", | |
90 | (ulong)alp->prev, (ulong)alp->next); | |
91 | } | |
92 | private void | |
93 | print_line_list(active_line *flp) | |
94 | { active_line *lp; | |
95 | for ( lp = flp; lp != 0; lp = lp->next ) | |
96 | { fixed xc = lp->x_current, xn = lp->x_next; | |
97 | dprintf3("[f]%lx(%d): x_current/next=%g", | |
98 | (ulong)lp, lp->direction, | |
99 | fixed2float(xc)); | |
100 | if ( xn != xc ) dprintf1("/%g", fixed2float(xn)); | |
101 | dputc('\n'); | |
102 | } | |
103 | } | |
104 | #define print_al(label,alp)\ | |
105 | if ( gs_debug['F'] ) print_active_line(label, alp) | |
106 | #else | |
107 | #define print_al(label,alp) 0 | |
108 | #endif | |
109 | ||
110 | /* Line list structure */ | |
111 | struct line_list_s { | |
112 | active_line *active_area; /* allocated active_line list */ | |
113 | line_close_segment *close_area; /* allocated closing line area */ | |
114 | uint close_count; | |
115 | gs_fixed_rect box; /* intersection of bounding boxes, */ | |
116 | /* disregard lines outside this */ | |
117 | active_line *next_active; /* next allocation slot */ | |
118 | active_line *limit; /* limit of local allocation */ | |
119 | line_close_segment *next_line; /* next line allocation slot */ | |
120 | active_line *y_list; /* Y-sorted list of pending lines */ | |
121 | active_line *y_line; /* most recently inserted line */ | |
122 | active_line x_head; /* X-sorted list of active lines */ | |
123 | #define x_list x_head.next | |
124 | /* Put the arrays last so the scalars will have */ | |
125 | /* small displacements. */ | |
126 | /* Allocate a few active_lines and line_close_segments */ | |
127 | /* locally to avoid round trips through the allocator. */ | |
128 | #define max_local_active 20 | |
129 | active_line local_active[max_local_active]; | |
130 | #define max_local_close 5 | |
131 | line_close_segment local_close[max_local_close]; | |
132 | }; | |
133 | typedef struct line_list_s line_list; | |
134 | typedef line_list _ss *ll_ptr; | |
135 | ||
136 | /* Forward declarations */ | |
137 | private int alloc_line_list(P2(ll_ptr, uint)); | |
138 | private void free_line_list(P1(ll_ptr)); | |
139 | private int add_y_list(P2(gx_path *, ll_ptr)); | |
140 | private int add_y_line(P4(segment *, segment *, int, ll_ptr)); | |
141 | private int fill_loop(P5(gx_device_color *, int, ll_ptr, | |
142 | gs_state *, fixed)); | |
143 | private void insert_x_new(P2(active_line *, ll_ptr)); | |
144 | private void update_x_list(P2(active_line *, fixed)); | |
145 | ||
146 | /* Statistics */ | |
147 | #ifdef DEBUG | |
148 | #define stat(x) (x++) | |
149 | #define statn(x,n) (x += (n)) | |
150 | private long n_fill; | |
151 | private long n_fill_alloc; | |
152 | private long n_y_up; | |
153 | private long n_y_down; | |
154 | private long n_x_step; | |
155 | private long n_slow_x; | |
156 | private long n_iter; | |
157 | private long n_find_y; | |
158 | private long n_band; | |
159 | private long n_band_step; | |
160 | private long n_band_fill; | |
161 | #else | |
162 | #define stat(x) 0 | |
163 | #define statn(x,n) 0 | |
164 | #endif | |
165 | ||
166 | /* General area filling algorithm. */ | |
167 | /* The adjust parameter is a hack for keeping small characters */ | |
168 | /* from coming out too faint: it specifies an amount by which to expand */ | |
169 | /* all sides of every filled region. */ | |
170 | int | |
171 | gx_fill_path(gx_path *ppath, gx_device_color *pdevc, gs_state *pgs, | |
172 | int rule, fixed adjust) | |
173 | { gx_clip_path *pcpath = pgs->clip_path; | |
174 | gs_fixed_rect cbox; | |
175 | gx_path *pfpath; | |
176 | gx_path ffpath; | |
177 | int code; | |
178 | line_list lst; | |
179 | uint sub_count; | |
180 | gx_device_clip cdev; | |
181 | int do_clip; | |
182 | /* Fatten everything a little to make it look better. */ | |
183 | /****** This is something of a hack. ******/ | |
184 | if ( adjust == 0 ) adjust = float2fixed(0.25); | |
185 | /* Start by flattening the path. We should do this on-the-fly.... */ | |
186 | if ( !ppath->curve_count ) /* don't need to flatten */ | |
187 | pfpath = ppath; | |
188 | else | |
189 | { if ( (code = gx_path_flatten(ppath, &ffpath, pgs->flatness)) < 0 ) return code; | |
190 | pfpath = &ffpath; | |
191 | } | |
192 | /* Check the bounding boxes. */ | |
193 | #define ibox lst.box | |
194 | gx_path_bbox(pfpath, &ibox); | |
195 | gx_cpath_box_for_check(pcpath, &cbox); | |
196 | if ( ibox.q.y <= cbox.q.y && ibox.q.x <= cbox.q.x && | |
197 | ibox.p.y >= cbox.p.y && ibox.p.x >= cbox.p.x | |
198 | ) | |
199 | { /* Path lies entirely within clipping rectangle */ | |
200 | do_clip = 0; | |
201 | } | |
202 | else | |
203 | { /* Intersect the path box and the clip bounding box. */ | |
204 | /* If the intersection is empty, this fill is a no-op. */ | |
205 | gs_fixed_rect bbox; | |
206 | bbox = pcpath->path.bbox; | |
207 | if ( ibox.p.x >= bbox.q.x || ibox.p.y >= bbox.q.y || | |
208 | ibox.q.x <= bbox.p.x || ibox.q.y <= bbox.p.y | |
209 | ) | |
210 | { /* Intersection of boxes is empty! */ | |
211 | code = 0; | |
212 | goto skip; | |
213 | } | |
214 | do_clip = 1; | |
215 | } | |
216 | #undef ibox | |
217 | sub_count = pfpath->subpath_count; | |
218 | if ( !(code = alloc_line_list(&lst, sub_count)) ) | |
219 | { gx_device *save_dev; | |
220 | if ( (code = add_y_list(pfpath, &lst)) < 0 ) | |
221 | goto nope; | |
222 | if ( do_clip ) | |
223 | { /* Set up a clipping device. */ | |
224 | gx_device *dev = (gx_device *)&cdev; | |
225 | save_dev = gs_currentdevice(pgs); | |
226 | cdev = gs_clip_device; | |
227 | cdev.target = save_dev; | |
228 | cdev.list = pcpath->list; | |
229 | gx_set_device_only(pgs, dev); | |
230 | (*dev->procs->open_device)(dev); | |
231 | } | |
232 | code = fill_loop(pdevc, rule, &lst, pgs, adjust); | |
233 | if ( do_clip ) | |
234 | gx_set_device_only(pgs, save_dev); | |
235 | nope: free_line_list(&lst); | |
236 | } | |
237 | skip: if ( pfpath != ppath ) /* had to flatten */ | |
238 | gx_path_release(pfpath); | |
239 | #ifdef DEBUG | |
240 | if ( gs_debug['f'] || gs_debug['F'] ) | |
241 | { dputs("[f]calls alloc up down step slowx iter find band bstep bfill\n"); | |
242 | dprintf4(" %5ld %5ld %5ld %5ld", | |
243 | n_fill, n_fill_alloc, n_y_up, n_y_down); | |
244 | dprintf4(" %5ld %5ld %5ld %5ld", | |
245 | n_x_step, n_slow_x, n_iter, n_find_y); | |
246 | dprintf3(" %5ld %5ld %5ld\n", | |
247 | n_band, n_band_step, n_band_fill); | |
248 | } | |
249 | #endif | |
250 | return code; | |
251 | } | |
252 | ||
253 | /* Create a line list for a (flattened) path. */ | |
254 | /* We pass in the list size, so that we can use this to iterate */ | |
255 | /* over more than one path simultaneously (needed for clipping). */ | |
256 | private int | |
257 | alloc_line_list(ll_ptr ll, uint sub_count) | |
258 | { ll->active_area = 0; | |
259 | ll->close_count = sub_count; | |
260 | ll->close_area = | |
261 | (sub_count <= max_local_close ? | |
262 | ll->local_close : | |
263 | (line_close_segment *)gs_malloc(sub_count, sizeof(line_close_segment), | |
264 | "closing lines")); | |
265 | ll->next_line = ll->close_area; | |
266 | if ( ll->close_area == 0 ) | |
267 | return_error(gs_error_VMerror); | |
268 | ll->next_active = ll->local_active; | |
269 | ll->limit = ll->next_active + max_local_active; | |
270 | ll->y_list = 0; | |
271 | ll->y_line = 0; | |
272 | stat(n_fill); | |
273 | return 0; | |
274 | } | |
275 | ||
276 | /* Free the line list */ | |
277 | private void | |
278 | free_line_list(ll_ptr ll) | |
279 | { line_close_segment *lp; | |
280 | active_line *alp; | |
281 | /* Splice out any inserted closing lines */ | |
282 | for ( lp = ll->close_area; lp != ll->next_line; lp++ ) | |
283 | { segment *prev = lp->prev, *next = lp->next; | |
284 | prev->next = next; | |
285 | if ( next ) next->prev = prev; | |
286 | lp->sub->last = prev; | |
287 | } | |
288 | /* Free any individually allocated active_lines. */ | |
289 | while ( (alp = ll->active_area) != 0 ) | |
290 | { active_line *next = alp->alloc_next; | |
291 | gs_free((char *)alp, 1, sizeof(active_line), | |
292 | "active line"); | |
293 | ll->active_area = next; | |
294 | } | |
295 | /* Free any separately allocated closing lines. */ | |
296 | if ( ll->close_area != ll->local_close && ll->close_area != 0 ) | |
297 | { gs_free((char *)ll->close_area, ll->close_count, | |
298 | sizeof(line_close_segment), "closing lines"); | |
299 | } | |
300 | } | |
301 | ||
302 | /* Construct a Y-sorted list of lines for a (flattened) path. */ | |
303 | /* We assume the path is non-empty. Only include non-horizontal */ | |
304 | /* lines where one endpoint is locally Y-minimal. */ | |
305 | private int | |
306 | add_y_list(gx_path *ppath, ll_ptr ll) | |
307 | { register segment *pseg = (segment *)ppath->first_subpath; | |
308 | subpath *psub; | |
309 | segment *plast; | |
310 | int first_dir, prev_dir, dir; | |
311 | segment *prev; | |
312 | /* fixed xmin = ll->box.p.x; */ /* not currently used */ | |
313 | fixed ymin = ll->box.p.y; | |
314 | fixed xmax = ll->box.q.x; | |
315 | fixed ymax = ll->box.q.y; | |
316 | int code; | |
317 | ||
318 | while ( pseg ) | |
319 | { switch ( pseg->type ) | |
320 | { /* No curves left */ | |
321 | case s_start: | |
322 | psub = (subpath *)pseg; | |
323 | plast = psub->last; | |
324 | dir = 2; /* hack to skip first line */ | |
325 | if ( plast->type != s_line_close ) | |
326 | { /* Create a fake s_line_close */ | |
327 | line_close_segment *lp = ll->next_line++; | |
328 | segment *next = plast->next; | |
329 | lp->next = next; | |
330 | lp->prev = plast; | |
331 | plast->next = (segment *)lp; | |
332 | if ( next ) next->prev = (segment *)lp; | |
333 | lp->type = s_line_close; | |
334 | lp->pt = psub->pt; | |
335 | lp->sub = psub; | |
336 | plast = (segment *)lp; | |
337 | psub->last = plast; | |
338 | } | |
339 | break; | |
340 | default: /* s_line, _close */ | |
341 | { fixed iy = pseg->pt.y; | |
342 | fixed py = prev->pt.y; | |
343 | /* Lines falling entirely outside the ibox */ | |
344 | /* are treated as though they were horizontal, */ | |
345 | /* i.e., they are never put on the list. */ | |
346 | #define compute_dir(xo, xe, yo, ye)\ | |
347 | (xo > xmax && xe > xmax ? 0 :\ | |
348 | ye > yo ? (ye <= ymin || yo >= ymax ? 0 : dir_up) :\ | |
349 | ye < yo ? (yo <= ymin || ye >= ymax ? 0 : dir_down) :\ | |
350 | 0) | |
351 | #define add_dir_lines(prev2, prev, this, pdir, dir)\ | |
352 | if ( pdir )\ | |
353 | { if ( (code = add_y_line(prev2, prev, pdir, ll)) < 0 ) return code; }\ | |
354 | if ( dir )\ | |
355 | { if ( (code = add_y_line(prev, this, dir, ll)) < 0 ) return code; } | |
356 | dir = compute_dir(prev->pt.x, pseg->pt.x, py, iy); | |
357 | if ( dir > prev_dir ) | |
358 | { add_dir_lines(prev->prev, prev, pseg, prev_dir, dir); | |
359 | } | |
360 | else if ( prev_dir == 2 ) /* first line */ | |
361 | first_dir = dir; | |
362 | if ( pseg == plast ) | |
363 | { /* We skipped the first segment of the */ | |
364 | /* subpath, so the last segment must */ | |
365 | /* receive special consideration. */ | |
366 | /* Note that we have `closed' all subpaths. */ | |
367 | if ( first_dir > dir ) | |
368 | { add_dir_lines(prev, pseg, psub->next, dir, first_dir); | |
369 | } | |
370 | } | |
371 | } | |
372 | #undef compute_dir | |
373 | #undef add_dir_lines | |
374 | } | |
375 | prev = pseg; | |
376 | prev_dir = dir; | |
377 | pseg = pseg->next; | |
378 | } | |
379 | return 0; | |
380 | } | |
381 | /* Internal routine to test a line segment and add it to the */ | |
382 | /* pending list if appropriate. */ | |
383 | private int | |
384 | add_y_line(segment *prev_lp, segment *lp, int dir, ll_ptr ll) | |
385 | { gs_fixed_point this, prev; | |
386 | register active_line *alp = ll->next_active; | |
387 | fixed y_start; | |
388 | if ( alp == ll->limit ) | |
389 | { /* Allocate separately */ | |
390 | alp = (active_line *)gs_malloc(1, sizeof(active_line), "active line"); | |
391 | if ( alp == 0 ) return_error(gs_error_VMerror); | |
392 | alp->alloc_next = ll->active_area; | |
393 | ll->active_area = alp; | |
394 | stat(n_fill_alloc); | |
395 | } | |
396 | else | |
397 | ll->next_active++; | |
398 | this.x = lp->pt.x; | |
399 | this.y = lp->pt.y; | |
400 | prev.x = prev_lp->pt.x; | |
401 | prev.y = prev_lp->pt.y; | |
402 | if ( (alp->direction = dir) > 0 ) | |
403 | { /* Upward line */ | |
404 | y_start = prev.y; | |
405 | set_al_points(alp, prev, this); | |
406 | alp->pseg = lp; | |
407 | } | |
408 | else | |
409 | { /* Downward line */ | |
410 | y_start = this.y; | |
411 | set_al_points(alp, this, prev); | |
412 | alp->pseg = prev_lp; | |
413 | } | |
414 | /* Insert the new line in the Y ordering */ | |
415 | { register active_line *yp = ll->y_line; | |
416 | register active_line *nyp; | |
417 | if ( yp == 0 ) | |
418 | { alp->next = alp->prev = 0; | |
419 | ll->y_list = alp; | |
420 | } | |
421 | else if ( y_start >= yp->start.y ) | |
422 | { /* Insert the new line after y_line */ | |
423 | while ( stat(n_y_up), (nyp = yp->next) != NULL && y_start > nyp->start.y ) | |
424 | yp = nyp; | |
425 | alp->next = nyp; | |
426 | alp->prev = yp; | |
427 | yp->next = alp; | |
428 | if ( nyp ) nyp->prev = alp; | |
429 | } | |
430 | else | |
431 | { /* Insert the new line before y_line */ | |
432 | while ( stat(n_y_down), (nyp = yp->prev) != NULL && y_start < nyp->start.y ) | |
433 | yp = nyp; | |
434 | alp->prev = nyp; | |
435 | alp->next = yp; | |
436 | yp->prev = alp; | |
437 | if ( nyp ) nyp->next = alp; | |
438 | else ll->y_list = alp; | |
439 | } | |
440 | } | |
441 | ll->y_line = alp; | |
442 | print_al("add ", alp); | |
443 | return 0; | |
444 | } | |
445 | ||
446 | /* Main filling loop. Takes lines off of y_list and adds them to */ | |
447 | /* x_list as needed. */ | |
448 | private int | |
449 | fill_loop(gx_device_color *pdevc, int rule, ll_ptr ll, | |
450 | gs_state *pgs, fixed adjust) | |
451 | { fixed adj2 = adjust << 1; | |
452 | active_line *yll = ll->y_list; | |
453 | gs_fixed_point pmax; | |
454 | fixed y; | |
455 | if ( yll == 0 ) return 0; /* empty list */ | |
456 | pmax = ll->box.q; | |
457 | y = yll->start.y; /* first Y value */ | |
458 | ll->x_list = 0; | |
459 | ll->x_head.x_current = min_fixed; /* stop backward scan */ | |
460 | while ( 1 ) | |
461 | { fixed y1, y0; | |
462 | active_line *endp, *alp, *stopx; | |
463 | fixed x; | |
464 | int draw; | |
465 | stat(n_iter); | |
466 | /* Check whether we've reached the maximum y. */ | |
467 | if ( y >= pmax.y ) break; | |
468 | /* Move newly active lines from y to x list. */ | |
469 | while ( yll != 0 && yll->start.y == y ) | |
470 | { active_line *ynext = yll->next; /* insert smashes next/prev links */ | |
471 | insert_x_new(yll, ll); | |
472 | yll = ynext; | |
473 | } | |
474 | if ( ll->x_list == 0 ) | |
475 | { /* No active lines, skip to next start */ | |
476 | if ( yll == 0 ) break; /* no lines left */ | |
477 | y = yll->start.y; | |
478 | continue; | |
479 | } | |
480 | /* Find the next evaluation point. */ | |
481 | /* Start by finding the smallest y value */ | |
482 | /* at which any currently active line ends */ | |
483 | /* (or the next to-be-active line begins). */ | |
484 | y1 = (yll != 0 ? yll->start.y : max_fixed); | |
485 | for ( alp = ll->x_list; alp != 0; alp = alp->next ) | |
486 | if ( alp->end.y < y1 ) y1 = alp->end.y; | |
487 | #ifdef DEBUG | |
488 | if ( gs_debug['F'] ) | |
489 | { dprintf2("[f]before loop: y=%f y1=%f:\n", | |
490 | fixed2float(y), fixed2float(y1)); | |
491 | print_line_list(ll->x_list); | |
492 | } | |
493 | #endif | |
494 | /* Now look for line intersections before y1. */ | |
495 | x = min_fixed; | |
496 | y0 = y - adjust; | |
497 | #define have_pixels() (fixed_rounded(y0) < fixed_rounded(y1 + adjust)) | |
498 | draw = (have_pixels() ? 1 : -1); | |
499 | /* | |
500 | * Loop invariants: | |
501 | * alp = endp->next; | |
502 | * for all lines lp from stopx up to alp, | |
503 | * lp->x_next = al_x_at_y(lp, y1). | |
504 | */ | |
505 | for ( alp = stopx = ll->x_list; stat(n_find_y), alp != 0; | |
506 | endp = alp, alp = alp->next | |
507 | ) | |
508 | { fixed nx = al_x_at_y(alp, y1); | |
509 | fixed dx_old, dx_den; | |
510 | /* Check for intersecting lines. */ | |
511 | if ( nx >= x ) | |
512 | x = nx; | |
513 | else if | |
514 | ( draw >= 0 && /* don't bother if no pixels */ | |
515 | (dx_old = alp->x_current - endp->x_current) >= 0 && | |
516 | (dx_den = dx_old + endp->x_next - nx) > dx_old | |
517 | ) | |
518 | { /* Make a good guess at the intersection */ | |
519 | /* Y value using only local information. */ | |
520 | fixed dy = y1 - y, y_new; | |
521 | #ifdef DEBUG | |
522 | if ( gs_debug['f'] || gs_debug['F'] ) | |
523 | dprintf3("[f]cross: dy=%g, dx_old=%g, dx_new=%g\n", | |
524 | fixed2float(dy), fixed2float(dx_old), | |
525 | fixed2float(dx_den - dx_old)); | |
526 | #endif | |
527 | /* Do the computation in single precision */ | |
528 | /* if the values are small enough. */ | |
529 | y_new = | |
530 | ((dy | dx_old) < 1L << (sizeof(fixed)*4-1) ? | |
531 | dy * dx_old / dx_den : | |
532 | fixed_mult_quo(dy, dx_old, dx_den)) | |
533 | + y; | |
534 | /* The crossing value doesn't have to be */ | |
535 | /* very accurate, but it does have to be */ | |
536 | /* greater than y and less than y1. */ | |
537 | #ifdef DEBUG | |
538 | if ( gs_debug['f'] || gs_debug['F'] ) | |
539 | dprintf3("[f]cross y=%g, y_new=%g, y1=%g\n", | |
540 | fixed2float(y), fixed2float(y_new), | |
541 | fixed2float(y1)); | |
542 | #endif | |
543 | stopx = alp; | |
544 | if ( y_new <= y ) y_new = y + 1; | |
545 | if ( y_new < y1 ) | |
546 | { y1 = y_new; | |
547 | nx = al_x_at_y(alp, y1); | |
548 | draw = 0; | |
549 | } | |
550 | if ( nx > x ) x = nx; | |
551 | } | |
552 | alp->x_next = nx; | |
553 | } | |
554 | /* Recompute next_x for lines before the intersection. */ | |
555 | for ( alp = ll->x_list; alp != stopx; alp = alp->next ) | |
556 | alp->x_next = al_x_at_y(alp, y1); | |
557 | #ifdef DEBUG | |
558 | if ( gs_debug['F'] ) | |
559 | { dprintf1("[f]after loop: y1=%f\n", fixed2float(y1)); | |
560 | print_line_list(ll->x_list); | |
561 | } | |
562 | #endif | |
563 | /* Fill a multi-trapezoid band for the active lines. */ | |
564 | /* Don't bother if no pixel centers lie within the band. */ | |
565 | if ( draw > 0 || draw == 0 && have_pixels() ) | |
566 | { active_line *alp = ll->x_list; | |
567 | fixed height = y1 - y + adj2; | |
568 | fixed xlbot, xltop; /* as of last "outside" line */ | |
569 | int inside = 0; | |
570 | stat(n_band); | |
571 | x = min_fixed; | |
572 | /* rule = -1 for winding number rule, i.e. */ | |
573 | /* we are inside if the winding number is non-zero; */ | |
574 | /* rule = 1 for even-odd rule, i.e. */ | |
575 | /* we are inside if the winding number is odd. */ | |
576 | /* Clever, eh? */ | |
577 | #define inside_path_p() (inside & rule) | |
578 | while ( alp != 0 ) | |
579 | { fixed xbot = alp->x_current; | |
580 | fixed xtop = alp->x_next; | |
581 | print_al("step", alp); | |
582 | stat(n_band_step); | |
583 | if ( inside_path_p() ) | |
584 | { inside += alp->direction; | |
585 | if ( !inside_path_p() ) /* about to go out */ | |
586 | { fixed wbot = xbot - xlbot + adj2; | |
587 | fixed wtop = xtop - xltop + adj2; | |
588 | int code; | |
589 | stat(n_band_fill); | |
590 | /* If lines are temporarily out of */ | |
591 | /* order, wtop might be negative. */ | |
592 | /* Patch this up now. */ | |
593 | if ( wtop < 0 ) | |
594 | { xltop += wtop >> 1; | |
595 | wtop = 0; | |
596 | } | |
597 | code = gz_fill_trapezoid_fixed( | |
598 | xlbot - adjust, | |
599 | wbot, y0, | |
600 | xltop - adjust, wtop, | |
601 | height, 0, pdevc, pgs); | |
602 | if ( code < 0 ) return code; | |
603 | } | |
604 | } | |
605 | else /* outside */ | |
606 | { inside += alp->direction; | |
607 | if ( inside_path_p() ) /* about to go in */ | |
608 | xlbot = xbot, xltop = xtop; | |
609 | } | |
610 | alp = alp->next; | |
611 | } | |
612 | } | |
613 | update_x_list(ll->x_list, y1); | |
614 | y = y1; | |
615 | } | |
616 | return 0; | |
617 | } | |
618 | ||
619 | /* Insert a newly active line in the X ordering. */ | |
620 | private void | |
621 | insert_x_new(active_line *alp, ll_ptr ll) | |
622 | { register active_line *next; | |
623 | register active_line *prev = &ll->x_head; | |
624 | register fixed x = alp->start.x; | |
625 | alp->x_current = x; | |
626 | while ( stat(n_x_step), | |
627 | (next = prev->next) != 0 && x_precedes(next, alp, x) | |
628 | ) | |
629 | prev = next; | |
630 | alp->next = next; | |
631 | alp->prev = prev; | |
632 | if ( next != 0 ) next->prev = alp; | |
633 | prev->next = alp; | |
634 | } | |
635 | ||
636 | /* Clean up after a pass through the main loop. */ | |
637 | /* If any lines are out of order, re-sort them now. */ | |
638 | /* Also drop any ended lines. */ | |
639 | private void | |
640 | update_x_list(active_line *x_first, fixed y1) | |
641 | { fixed x; | |
642 | register active_line *alp; | |
643 | active_line *nlp; | |
644 | for ( x = min_fixed, alp = x_first; alp != 0; alp = nlp ) | |
645 | { fixed nx = alp->x_current = alp->x_next; | |
646 | nlp = alp->next; | |
647 | #ifdef DEBUG | |
648 | if ( gs_debug['f'] || gs_debug['F'] ) | |
649 | dprintf4("[f]check %lx,x=%g %lx,x=%g\n", | |
650 | (ulong)alp->prev, fixed2float(x), | |
651 | (ulong)alp, fixed2float(nx)); | |
652 | #endif | |
653 | if ( alp->end.y == y1 ) | |
654 | { /* Handle a line segment that just ended. */ | |
655 | segment *pseg = alp->pseg; | |
656 | segment *next; | |
657 | gs_fixed_point npt; | |
658 | /* | |
659 | * The computation of next relies on the fact that | |
660 | * all subpaths have been closed. When we cycle | |
661 | * around to the other end of a subpath, we must be | |
662 | * sure not to process the start/end point twice. | |
663 | */ | |
664 | next = | |
665 | (alp->direction == dir_up ? | |
666 | (/* Upward line, go forward along path. */ | |
667 | pseg->type == s_line_close ? /* end of subpath */ | |
668 | ((line_close_segment *)pseg)->sub->next : | |
669 | pseg->next) : | |
670 | (/* Downward line, go backward along path. */ | |
671 | pseg->type == s_start ? /* start of subpath */ | |
672 | ((subpath *)pseg)->last->prev : | |
673 | pseg->prev) | |
674 | ); | |
675 | npt.y = next->pt.y; | |
676 | #ifdef DEBUG | |
677 | if ( gs_debug['F'] ) | |
678 | dprintf5("[f]ended %lx: pseg=%lx y=%f next=%lx npt.y=%f\n", | |
679 | (ulong)alp, (ulong)pseg, fixed2float(pseg->pt.y), | |
680 | (ulong)next, fixed2float(npt.y)); | |
681 | #endif | |
682 | if ( npt.y <= pseg->pt.y ) | |
683 | { /* End of a line sequence */ | |
684 | alp->prev->next = nlp; | |
685 | if ( nlp ) nlp->prev = alp->prev; | |
686 | #ifdef DEBUG | |
687 | if ( gs_debug['F'] ) | |
688 | dprintf1("[f]drop %lx\n", (ulong)alp); | |
689 | #endif | |
690 | continue; | |
691 | } | |
692 | else | |
693 | { alp->pseg = next; | |
694 | npt.x = next->pt.x; | |
695 | set_al_points(alp, alp->end, npt); | |
696 | print_al("repl", alp); | |
697 | } | |
698 | } | |
699 | if ( nx <= x ) | |
700 | { /* Move alp backward in the list. */ | |
701 | active_line *prev = alp->prev; | |
702 | active_line *next = nlp; | |
703 | prev->next = next; | |
704 | if ( next ) next->prev = prev; | |
705 | while ( !x_precedes(prev, alp, nx) ) | |
706 | { | |
707 | #ifdef DEBUG | |
708 | if ( gs_debug['f'] || gs_debug['F'] ) | |
709 | dprintf2("[f]swap %lx,%lx\n", | |
710 | (ulong)alp, (ulong)prev); | |
711 | #endif | |
712 | next = prev, prev = prev->prev; | |
713 | } | |
714 | alp->next = next; | |
715 | alp->prev = prev; | |
716 | /* next might be null, if alp was in */ | |
717 | /* the correct spot already. */ | |
718 | if ( next ) next->prev = alp; | |
719 | prev->next = alp; | |
720 | } | |
721 | else | |
722 | x = nx; | |
723 | } | |
724 | #ifdef DEBUG | |
725 | if ( gs_debug['f'] || gs_debug['F'] ) | |
726 | for ( alp = x_first; alp != 0; alp = alp->next ) | |
727 | if ( alp->next != 0 && alp->next->x_current < alp->x_current ) | |
728 | { lprintf("[f]Lines out of order!\n"); | |
729 | print_active_line(" 1:", alp); | |
730 | print_active_line(" 2:", alp->next); | |
731 | gs_exit(1); | |
732 | } | |
733 | #endif | |
734 | } |