1 /* Copyright (C) 1989-2003 artofcode LLC. All rights reserved. 2 3 This software is provided AS-IS with no warranty, either express or 4 implied. 5 6 This software is distributed under license and may not be copied, 7 modified or distributed except as expressly authorized under the terms 8 of the license contained in the file LICENSE in this distribution. 9 10 For more information about licensing, please refer to 11 http://www.ghostscript.com/licensing/. For information on 12 commercial licensing, go to http://www.artifex.com/licensing/ or 13 contact Artifex Software, Inc., 101 Lucas Valley Road #110, 14 San Rafael, CA 94903, U.S.A., +1(415)492-9861. 15 */ 16 17 /* $Id: gxfill.c,v 1.122 2005/08/22 14:29:18 igor Exp $ */ 18 /* A topological spot decomposition algorithm with dropout prevention. */ 19 /* 20 This is a dramaticly reorganized and improved revision of the 21 filling algorithm, iwhich was nitially coded by Henry Stiles. 22 The main improvements are: 23 1. A dropout prevention for character fill. 24 2. The spot topology analysys support 25 for True Type grid fitting. 26 3. Fixed the contiguty of a spot covering 27 for shading fills with no dropouts. 28 */ 29 /* See PSEUDO_RASTERISATION and "pseudo_rasterization". 30 about the dropout previntion logics. */ 31 /* See is_spotan about the spot topology analyzis support. */ 32 /* Also defining lower-level path filling procedures */ 33 34 #include "gx.h" 35 #include "gserrors.h" 36 #include "gsstruct.h" 37 #include "gxfixed.h" 38 #include "gxdevice.h" 39 #include "gzpath.h" 40 #include "gzcpath.h" 41 #include "gxdcolor.h" 42 #include "gxhttile.h" 43 #include "gxistate.h" 44 #include "gxpaint.h" /* for prototypes */ 45 #include "gxfdrop.h" 46 #include "gxfill.h" 47 #include "gsptype2.h" 48 #include "gdevddrw.h" 49 #include "gzspotan.h" /* Only for gx_san_trap_store. */ 50 #include "memory_.h" 51 #include "stdint_.h" 52 #include "vdtrace.h" 53 /* 54 #include "gxfilltr.h" - Do not remove this comment. "gxfilltr.h" is included below. 55 #include "gxfillsl.h" - Do not remove this comment. "gxfillsl.h" is included below. 56 #include "gxfillts.h" - Do not remove this comment. "gxfillts.h" is included below. 57 */ 58 59 #ifdef DEBUG 60 /* Define the statistics structure instance. */ 61 stats_fill_t stats_fill; 62 #endif 63 64 /* A predicate for spot insideness. */ 65 /* rule = -1 for winding number rule, i.e. */ 66 /* we are inside if the winding number is non-zero; */ 67 /* rule = 1 for even-odd rule, i.e. */ 68 /* we are inside if the winding number is odd. */ 69 #define INSIDE_PATH_P(inside, rule) ((inside & rule) != 0) 70 71 72 /* ---------------- Active line management ---------------- */ 73 74 75 /* 76 * Define the ordering criterion for active lines that overlap in Y. 77 * Return -1, 0, or 1 if lp1 precedes, coincides with, or follows lp2. 78 * 79 * The lines' x_current values are correct for some Y value that crosses 80 * both of them and that is not both the start of one and the end of the 81 * other. (Neither line is horizontal.) We want the ordering at this 82 * Y value, or, of the x_current values are equal, greater Y values 83 * (if any: this Y value might be the end of both lines). 84 */ 85 private int 86 x_order(const active_line *lp1, const active_line *lp2) 87 { 88 bool s1; 89 90 INCR(order); 91 if (lp1->x_current < lp2->x_current) 92 return -1; 93 else if (lp1->x_current > lp2->x_current) 94 return 1; 95 /* 96 * We need to compare the slopes of the lines. Start by 97 * checking one fast case, where the slopes have opposite signs. 98 */ 99 if ((s1 = lp1->start.x < lp1->end.x) != (lp2->start.x < lp2->end.x)) 100 return (s1 ? 1 : -1); 101 /* 102 * We really do have to compare the slopes. Fortunately, this isn't 103 * needed very often. We want the sign of the comparison 104 * dx1/dy1 - dx2/dy2, or (since we know dy1 and dy2 are positive) 105 * dx1 * dy2 - dx2 * dy1. In principle, we can't simply do this using 106 * doubles, since we need complete accuracy and doubles don't have 107 * enough fraction bits. However, with the usual 20+12-bit fixeds and 108 * 64-bit doubles, both of the factors would have to exceed 2^15 109 * device space pixels for the result to be inaccurate, so we 110 * simply disregard this possibility. ****** FIX SOMEDAY ****** 111 */ 112 INCR(slow_order); 113 { 114 fixed dx1 = lp1->end.x - lp1->start.x, 115 dy1 = lp1->end.y - lp1->start.y; 116 fixed dx2 = lp2->end.x - lp2->start.x, 117 dy2 = lp2->end.y - lp2->start.y; 118 double diff = (double)dx1 * dy2 - (double)dx2 * dy1; 119 120 return (diff < 0 ? -1 : diff > 0 ? 1 : 0); 121 } 122 } 123 124 /* 125 * The active_line structure isn't really simple, but since its instances 126 * only exist temporarily during a fill operation, we don't have to 127 * worry about a garbage collection occurring. 128 */ 129 gs_private_st_simple(st_active_line, active_line, "active_line"); 130 131 #ifdef DEBUG 132 /* Internal procedures for printing and checking active lines. */ 133 private void 134 print_active_line(const char *label, const active_line * alp) 135 { 136 dlprintf5("[f]%s 0x%lx(%d): x_current=%f x_next=%f\n", 137 label, (ulong) alp, alp->direction, 138 fixed2float(alp->x_current), fixed2float(alp->x_next)); 139 dlprintf5(" start=(%f,%f) pt_end=0x%lx(%f,%f)\n", 140 fixed2float(alp->start.x), fixed2float(alp->start.y), 141 (ulong) alp->pseg, 142 fixed2float(alp->end.x), fixed2float(alp->end.y)); 143 dlprintf2(" prev=0x%lx next=0x%lx\n", 144 (ulong) alp->prev, (ulong) alp->next); 145 } 146 private void 147 print_line_list(const active_line * flp) 148 { 149 const active_line *lp; 150 151 for (lp = flp; lp != 0; lp = lp->next) { 152 fixed xc = lp->x_current, xn = lp->x_next; 153 154 dlprintf3("[f]0x%lx(%d): x_current/next=%g", 155 (ulong) lp, lp->direction, 156 fixed2float(xc)); 157 if (xn != xc) 158 dprintf1("/%g", fixed2float(xn)); 159 dputc('\n'); 160 } 161 } 162 inline private void 163 print_al(const char *label, const active_line * alp) 164 { 165 if (gs_debug_c('F')) 166 print_active_line(label, alp); 167 } 168 #else 169 #define print_al(label,alp) DO_NOTHING 170 #endif 171 172 private inline bool 173 is_spotan_device(gx_device * dev) 174 { 175 return dev->memory != NULL && 176 gs_object_type(dev->memory, dev) == &st_device_spot_analyzer; 177 } 178 179 /* Forward declarations */ 180 private void free_line_list(line_list *); 181 private int add_y_list(gx_path *, line_list *); 182 private int add_y_line_aux(const segment * prev_lp, const segment * lp, 183 const gs_fixed_point *curr, const gs_fixed_point *prev, int dir, line_list *ll); 184 private void insert_x_new(active_line *, line_list *); 185 private bool end_x_line(active_line *, const line_list *, bool); 186 private void step_al(active_line *alp, bool move_iterator); 187 188 189 #define FILL_LOOP_PROC(proc) int proc(line_list *, fixed band_mask) 190 private FILL_LOOP_PROC(spot_into_scan_lines); 191 private FILL_LOOP_PROC(spot_into_trapezoids); 192 193 /* 194 * This is the general path filling algorithm. 195 * It uses the center-of-pixel rule for filling 196 * (except for pseudo_rasterization - see below). 197 * We can implement Microsoft's upper-left-corner-of-pixel rule 198 * by subtracting (0.5, 0.5) from all the coordinates in the path. 199 * 200 * The adjust parameters are a hack for keeping regions 201 * from coming out too faint: they specify an amount by which to expand 202 * the sides of every filled region. 203 * Setting adjust = fixed_half is supposed to produce the effect of Adobe's 204 * any-part-of-pixel rule, but it doesn't quite, because of the 205 * closed/open interval rule for regions. We detect this as a special case 206 * and do the slightly ugly things necessary to make it work. 207 */ 208 209 /* Initialize the line list for a path. */ 210 private inline void 211 init_line_list(line_list *ll, gs_memory_t * mem) 212 { 213 ll->memory = mem; 214 ll->active_area = 0; 215 ll->next_active = ll->local_active; 216 ll->limit = ll->next_active + MAX_LOCAL_ACTIVE; 217 ll->close_count = 0; 218 ll->y_list = 0; 219 ll->y_line = 0; 220 ll->h_list0 = ll->h_list1 = 0; 221 ll->margin_set0.margin_list = ll->margin_set1.margin_list = 0; 222 ll->margin_set0.margin_touched = ll->margin_set1.margin_touched = 0; 223 ll->margin_set0.y = ll->margin_set1.y = 0; /* A stub against indeterminism. Don't use it. */ 224 ll->free_margin_list = 0; 225 ll->local_margin_alloc_count = 0; 226 ll->margin_set0.sect = ll->local_section0; 227 ll->margin_set1.sect = ll->local_section1; 228 /* Do not initialize ll->bbox_left, ll->bbox_width - they were set in advance. */ 229 INCR(fill); 230 } 231 232 233 /* Unlink any line_close segments added temporarily. */ 234 private inline void 235 unclose_path(gx_path * ppath, int count) 236 { 237 subpath *psub; 238 239 for (psub = ppath->first_subpath; count != 0; 240 psub = (subpath *) psub->last->next 241 ) 242 if (psub->last == (segment *) & psub->closer) { 243 segment *prev = psub->closer.prev, *next = psub->closer.next; 244 245 prev->next = next; 246 if (next) 247 next->prev = prev; 248 psub->last = prev; 249 count--; 250 } 251 } 252 253 /* 254 * Tweak the fill adjustment if necessary so that (nearly) empty 255 * rectangles are guaranteed to produce some output. This is a hack 256 * to work around a bug in the Microsoft Windows PostScript driver, 257 * which draws thin lines by filling zero-width rectangles, and in 258 * some other drivers that try to fill epsilon-width rectangles. 259 */ 260 void 261 gx_adjust_if_empty(const gs_fixed_rect * pbox, gs_fixed_point * adjust) 262 { 263 /* 264 * For extremely large coordinates, the obvious subtractions could 265 * overflow. We can work around this easily by noting that since 266 * we know q.{x,y} >= p.{x,y}, the subtraction overflows iff the 267 * result is negative. 268 */ 269 const fixed 270 dx = pbox->q.x - pbox->p.x, dy = pbox->q.y - pbox->p.y; 271 272 if (dx < fixed_half && dx > 0 && (dy >= int2fixed(2) || dy < 0)) { 273 adjust->x = arith_rshift_1(fixed_1 + fixed_epsilon - dx); 274 if_debug1('f', "[f]thin adjust_x=%g\n", 275 fixed2float(adjust->x)); 276 } else if (dy < fixed_half && dy > 0 && (dx >= int2fixed(2) || dx < 0)) { 277 adjust->y = arith_rshift_1(fixed_1 + fixed_epsilon - dy); 278 if_debug1('f', "[f]thin adjust_y=%g\n", 279 fixed2float(adjust->y)); 280 } 281 } 282 283 /* 284 * The general fill path algorithm. 285 */ 286 private int 287 gx_general_fill_path(gx_device * pdev, const gs_imager_state * pis, 288 gx_path * ppath, const gx_fill_params * params, 289 const gx_device_color * pdevc, const gx_clip_path * pcpath) 290 { 291 gs_fixed_point adjust; 292 gs_logical_operation_t lop = pis->log_op; 293 gs_fixed_rect ibox, bbox, sbox; 294 gx_device_clip cdev; 295 gx_device *dev = pdev; 296 gx_device *save_dev = dev; 297 gx_path ffpath; 298 gx_path *pfpath; 299 int code; 300 int max_fill_band = dev->max_fill_band; 301 #define NO_BAND_MASK ((fixed)(-1) << (sizeof(fixed) * 8 - 1)) 302 const bool is_character = params->adjust.x == -1; /* See gxistate.h */ 303 bool fill_by_trapezoids; 304 bool pseudo_rasterization; 305 bool big_path = ppath->subpath_count > 50; 306 fill_options fo; 307 line_list lst; 308 309 *(const fill_options **)&lst.fo = &fo; /* break 'const'. */ 310 /* 311 * Compute the bounding box before we flatten the path. 312 * This can save a lot of time if the path has curves. 313 * If the path is neither fully within nor fully outside 314 * the quick-check boxes, we could recompute the bounding box 315 * and make the checks again after flattening the path, 316 * but right now we don't bother. 317 */ 318 gx_path_bbox(ppath, &ibox); 319 # define SMALL_CHARACTER 500 320 pseudo_rasterization = (is_character && 321 !is_spotan_device(dev) && 322 ibox.q.y - ibox.p.y < SMALL_CHARACTER * fixed_scale && 323 ibox.q.x - ibox.p.x < SMALL_CHARACTER * fixed_scale); 324 if (is_character) 325 adjust.x = adjust.y = 0; 326 else 327 adjust = params->adjust; 328 if (params->fill_zero_width && !pseudo_rasterization) 329 gx_adjust_if_empty(&ibox, &adjust); 330 lst.bbox_left = fixed2int(ibox.p.x - adjust.x - fixed_epsilon); 331 lst.bbox_width = fixed2int(fixed_ceiling(ibox.q.x + adjust.x)) - lst.bbox_left; 332 if (vd_enabled) { 333 fixed x0 = int2fixed(fixed2int(ibox.p.x - adjust.x - fixed_epsilon)); 334 fixed x1 = int2fixed(fixed2int(ibox.q.x + adjust.x + fixed_scale - fixed_epsilon)); 335 fixed y0 = int2fixed(fixed2int(ibox.p.y - adjust.y - fixed_epsilon)); 336 fixed y1 = int2fixed(fixed2int(ibox.q.y + adjust.y + fixed_scale - fixed_epsilon)), k; 337 338 for (k = x0; k <= x1; k += fixed_scale) 339 vd_bar(k, y0, k, y1, 1, RGB(128, 128, 128)); 340 for (k = y0; k <= y1; k += fixed_scale) 341 vd_bar(x0, k, x1, k, 1, RGB(128, 128, 128)); 342 } 343 /* Check the bounding boxes. */ 344 if_debug6('f', "[f]adjust=%g,%g bbox=(%g,%g),(%g,%g)\n", 345 fixed2float(adjust.x), fixed2float(adjust.y), 346 fixed2float(ibox.p.x), fixed2float(ibox.p.y), 347 fixed2float(ibox.q.x), fixed2float(ibox.q.y)); 348 if (pcpath) 349 gx_cpath_inner_box(pcpath, &bbox); 350 else 351 (*dev_proc(dev, get_clipping_box)) (dev, &bbox); 352 if (!rect_within(ibox, bbox)) { 353 /* 354 * Intersect the path box and the clip bounding box. 355 * If the intersection is empty, this fill is a no-op. 356 */ 357 if (pcpath) 358 gx_cpath_outer_box(pcpath, &bbox); 359 if_debug4('f', " outer_box=(%g,%g),(%g,%g)\n", 360 fixed2float(bbox.p.x), fixed2float(bbox.p.y), 361 fixed2float(bbox.q.x), fixed2float(bbox.q.y)); 362 rect_intersect(ibox, bbox); 363 if (ibox.p.x - adjust.x >= ibox.q.x + adjust.x || 364 ibox.p.y - adjust.y >= ibox.q.y + adjust.y 365 ) { /* Intersection of boxes is empty! */ 366 return 0; 367 } 368 /* 369 * The path is neither entirely inside the inner clip box 370 * nor entirely outside the outer clip box. 371 * If we had to flatten the path, this is where we would 372 * recompute its bbox and make the tests again, 373 * but we don't bother right now. 374 * 375 * If there is a clipping path, set up a clipping device. 376 */ 377 if (pcpath) { 378 dev = (gx_device *) & cdev; 379 gx_make_clip_device(&cdev, gx_cpath_list(pcpath)); 380 cdev.target = save_dev; 381 cdev.max_fill_band = save_dev->max_fill_band; 382 (*dev_proc(dev, open_device)) (dev); 383 } 384 } 385 /* 386 * Compute the proper adjustment values. 387 * To get the effect of the any-part-of-pixel rule, 388 * we may have to tweak them slightly. 389 * NOTE: We changed the adjust_right/above value from 0.5+epsilon 390 * to 0.5 in release 5.01; even though this does the right thing 391 * in every case we could imagine, we aren't confident that it's 392 * correct. (The old values were definitely incorrect, since they 393 * caused 1-pixel-wide/high objects to color 2 pixels even if 394 * they fell exactly on pixel boundaries.) 395 */ 396 if (adjust.x == fixed_half) 397 fo.adjust_left = fixed_half - fixed_epsilon, 398 fo.adjust_right = fixed_half /* + fixed_epsilon */ ; /* see above */ 399 else 400 fo.adjust_left = fo.adjust_right = adjust.x; 401 if (adjust.y == fixed_half) 402 fo.adjust_below = fixed_half - fixed_epsilon, 403 fo.adjust_above = fixed_half /* + fixed_epsilon */ ; /* see above */ 404 else 405 fo.adjust_below = fo.adjust_above = adjust.y; 406 /* Initialize the active line list. */ 407 init_line_list(&lst, ppath->memory); 408 sbox.p.x = ibox.p.x - adjust.x; 409 sbox.p.y = ibox.p.y - adjust.y; 410 sbox.q.x = ibox.q.x + adjust.x; 411 sbox.q.y = ibox.q.y + adjust.y; 412 fo.pseudo_rasterization = pseudo_rasterization; 413 fo.pdevc = pdevc; 414 fo.lop = lop; 415 fo.fixed_flat = float2fixed(params->flatness); 416 fo.ymin = ibox.p.y; 417 fo.ymax = ibox.q.y; 418 fo.dev = dev; 419 fo.lop = lop; 420 fo.pbox = &sbox; 421 fo.rule = params->rule; 422 fo.is_spotan = is_spotan_device(dev); 423 fo.fill_direct = color_writes_pure(pdevc, lop); 424 fo.fill_rect = (fo.fill_direct ? dev_proc(dev, fill_rectangle) : NULL); 425 fo.fill_trap = dev_proc(dev, fill_trapezoid); 426 427 /* 428 * We have a choice of two different filling algorithms: 429 * scan-line-based and trapezoid-based. They compare as follows: 430 * 431 * Scan Trap 432 * ---- ---- 433 * skip +draw 0-height horizontal lines 434 * slow +fast rectangles 435 * +fast slow curves 436 * +yes no write pixels at most once when adjust != 0 437 * 438 * Normally we use the scan line algorithm for characters, where curve 439 * speed is important, and for non-idempotent RasterOps, where double 440 * pixel writing must be avoided, and the trapezoid algorithm otherwise. 441 * However, we always use the trapezoid algorithm for rectangles. 442 */ 443 fill_by_trapezoids = 444 (pseudo_rasterization || !gx_path_has_curves(ppath) || 445 params->flatness >= 1.0 || fo.is_spotan); 446 if (fill_by_trapezoids && !fo.is_spotan && !lop_is_idempotent(lop)) { 447 gs_fixed_rect rbox; 448 449 if (gx_path_is_rectangular(ppath, &rbox)) { 450 int x0 = fixed2int_pixround(rbox.p.x - fo.adjust_left); 451 int y0 = fixed2int_pixround(rbox.p.y - fo.adjust_below); 452 int x1 = fixed2int_pixround(rbox.q.x + fo.adjust_right); 453 int y1 = fixed2int_pixround(rbox.q.y + fo.adjust_above); 454 455 return gx_fill_rectangle_device_rop(x0, y0, x1 - x0, y1 - y0, 456 pdevc, dev, lop); 457 } 458 if (fo.adjust_left | fo.adjust_right | fo.adjust_below | fo.adjust_above) 459 fill_by_trapezoids = false; /* avoid double writing pixels */ 460 } 461 gx_path_init_local(&ffpath, ppath->memory); 462 if (!big_path && !gx_path_has_curves(ppath)) /* don't need to flatten */ 463 pfpath = ppath; 464 else if (is_spotan_device(dev)) 465 pfpath = ppath; 466 else if (!big_path && gx_path__check_curves(ppath, pco_small_curves, fo.fixed_flat)) 467 pfpath = ppath; 468 else { 469 code = gx_path_copy_reducing(ppath, &ffpath, fo.fixed_flat, NULL, 470 pco_small_curves); 471 if (code < 0) 472 return code; 473 pfpath = &ffpath; 474 if (big_path) { 475 code = gx_path_merge_contacting_contours(pfpath); 476 if (code < 0) 477 return code; 478 } 479 } 480 fo.fill_by_trapezoids = fill_by_trapezoids; 481 if ((code = add_y_list(pfpath, &lst)) < 0) 482 goto nope; 483 { 484 FILL_LOOP_PROC((*fill_loop)); 485 486 /* Some short-sighted compilers won't allow a conditional here.... */ 487 if (fill_by_trapezoids) 488 fill_loop = spot_into_trapezoids; 489 else 490 fill_loop = spot_into_scan_lines; 491 if (lst.bbox_width > MAX_LOCAL_SECTION && fo.pseudo_rasterization) { 492 /* 493 * Note that execution pass here only for character size 494 * grater that MAX_LOCAL_SECTION and lesser than 495 * SMALL_CHARACTER. Therefore with !arch_small_memory 496 * the dynamic allocation only happens for characters 497 * wider than 100 pixels. 498 */ 499 lst.margin_set0.sect = (section *)gs_alloc_struct_array(pdev->memory, lst.bbox_width * 2, 500 section, &st_section, "section"); 501 if (lst.margin_set0.sect == 0) 502 return_error(gs_error_VMerror); 503 lst.margin_set1.sect = lst.margin_set0.sect + lst.bbox_width; 504 } 505 if (fo.pseudo_rasterization) { 506 init_section(lst.margin_set0.sect, 0, lst.bbox_width); 507 init_section(lst.margin_set1.sect, 0, lst.bbox_width); 508 } 509 code = (*fill_loop) 510 (&lst, (max_fill_band == 0 ? NO_BAND_MASK : int2fixed(-max_fill_band))); 511 if (lst.margin_set0.sect != lst.local_section0 && 512 lst.margin_set0.sect != lst.local_section1) 513 gs_free_object(pdev->memory, min(lst.margin_set0.sect, lst.margin_set1.sect), "section"); 514 } 515 nope:if (lst.close_count != 0) 516 unclose_path(pfpath, lst.close_count); 517 free_line_list(&lst); 518 if (pfpath != ppath) /* had to flatten */ 519 gx_path_free(pfpath, "gx_general_fill_path"); 520 #ifdef DEBUG 521 if (gs_debug_c('f')) { 522 dlputs("[f] # alloc up down horiz step slowx iter find band bstep bfill\n"); 523 dlprintf5(" %5ld %5ld %5ld %5ld %5ld", 524 stats_fill.fill, stats_fill.fill_alloc, 525 stats_fill.y_up, stats_fill.y_down, 526 stats_fill.horiz); 527 dlprintf4(" %5ld %5ld %5ld %5ld", 528 stats_fill.x_step, stats_fill.slow_x, 529 stats_fill.iter, stats_fill.find_y); 530 dlprintf3(" %5ld %5ld %5ld\n", 531 stats_fill.band, stats_fill.band_step, 532 stats_fill.band_fill); 533 dlputs("[f] afill slant shall sfill mqcrs order slowo\n"); 534 dlprintf7(" %5ld %5ld %5ld %5ld %5ld %5ld %5ld\n", 535 stats_fill.afill, stats_fill.slant, 536 stats_fill.slant_shallow, stats_fill.sfill, 537 stats_fill.mq_cross, stats_fill.order, 538 stats_fill.slow_order); 539 } 540 #endif 541 return code; 542 } 543 544 /* 545 * Fill a path. This is the default implementation of the driver 546 * fill_path procedure. 547 */ 548 int 549 gx_default_fill_path(gx_device * pdev, const gs_imager_state * pis, 550 gx_path * ppath, const gx_fill_params * params, 551 const gx_device_color * pdevc, const gx_clip_path * pcpath) 552 { 553 int code; 554 555 if (gx_dc_is_pattern2_color(pdevc)) { 556 /* Optimization for shading fill : 557 The general path filling algorithm subdivides fill region with 558 trapezoid or rectangle subregions and then paints each subregion 559 with given color. If the color is shading, each subregion to be 560 subdivided into areas of constant color. But with radial 561 shading each area is a high order polygon, being 562 subdivided into smaller subregions, so as total number of 563 subregions grows huge. Faster processing is done here by changing 564 the order of subdivision cycles : we first subdivide the shading into 565 areas of constant color, then apply the general path filling algorithm 566 (i.e. subdivide each area into trapezoids or rectangles), using the 567 filling path as clip mask. 568 */ 569 570 gx_clip_path cpath_intersection; 571 gx_path path_intersection; 572 573 /* Shading fill algorithm uses "current path" parameter of the general 574 path filling algorithm as boundary of constant color area, 575 so we need to intersect the filling path with the clip path now, 576 reducing the number of pathes passed to it : 577 */ 578 gx_path_init_local(&path_intersection, pdev->memory); 579 gx_cpath_init_local_shared(&cpath_intersection, pcpath, pdev->memory); 580 if ((code = gx_cpath_intersect(&cpath_intersection, ppath, params->rule, (gs_imager_state *)pis)) >= 0) 581 code = gx_cpath_to_path(&cpath_intersection, &path_intersection); 582 583 /* Do fill : */ 584 if (code >= 0) 585 code = gx_dc_pattern2_fill_path(pdevc, &path_intersection, NULL, pdev); 586 587 /* Destruct local data and return :*/ 588 gx_path_free(&path_intersection, "shading_fill_path_intersection"); 589 gx_cpath_free(&cpath_intersection, "shading_fill_cpath_intersection"); 590 } else { 591 bool got_dc = false; 592 vd_save; 593 if (vd_allowed('F') || vd_allowed('f')) { 594 if (!vd_enabled) { 595 vd_get_dc( (params->adjust.x | params->adjust.y) ? 'F' : 'f'); 596 got_dc = vd_enabled; 597 } 598 if (vd_enabled) { 599 vd_set_shift(0, 100); 600 vd_set_scale(VD_SCALE); 601 vd_set_origin(0, 0); 602 vd_erase(RGB(192, 192, 192)); 603 } 604 } else 605 vd_disable; 606 code = gx_general_fill_path(pdev, pis, ppath, params, pdevc, pcpath); 607 if (got_dc) 608 vd_release_dc; 609 vd_restore; 610 } 611 return code; 612 } 613 614 /* Free the line list. */ 615 private void 616 free_line_list(line_list *ll) 617 { 618 /* Free any individually allocated active_lines. */ 619 gs_memory_t *mem = ll->memory; 620 active_line *alp; 621 622 while ((alp = ll->active_area) != 0) { 623 active_line *next = alp->alloc_next; 624 625 gs_free_object(mem, alp, "active line"); 626 ll->active_area = next; 627 } 628 free_all_margins(ll); 629 } 630 631 private inline active_line * 632 make_al(line_list *ll) 633 { 634 active_line *alp = ll->next_active; 635 636 if (alp == ll->limit) { /* Allocate separately */ 637 alp = gs_alloc_struct(ll->memory, active_line, 638 &st_active_line, "active line"); 639 if (alp == 0) 640 return NULL; 641 alp->alloc_next = ll->active_area; 642 ll->active_area = alp; 643 INCR(fill_alloc); 644 } else 645 ll->next_active++; 646 return alp; 647 } 648 649 /* Insert the new line in the Y ordering */ 650 private void 651 insert_y_line(line_list *ll, active_line *alp) 652 { 653 active_line *yp = ll->y_line; 654 active_line *nyp; 655 fixed y_start = alp->start.y; 656 657 vd_bar(alp->start.x, alp->start.y, alp->end.x, alp->end.y, 0, RGB(255, 0, 0)); 658 if (yp == 0) { 659 alp->next = alp->prev = 0; 660 ll->y_list = alp; 661 } else if (y_start >= yp->start.y) { /* Insert the new line after y_line */ 662 while (INCR_EXPR(y_up), 663 ((nyp = yp->next) != NULL && 664 y_start > nyp->start.y) 665 ) 666 yp = nyp; 667 alp->next = nyp; 668 alp->prev = yp; 669 yp->next = alp; 670 if (nyp) 671 nyp->prev = alp; 672 } else { /* Insert the new line before y_line */ 673 while (INCR_EXPR(y_down), 674 ((nyp = yp->prev) != NULL && 675 y_start < nyp->start.y) 676 ) 677 yp = nyp; 678 alp->prev = nyp; 679 alp->next = yp; 680 yp->prev = alp; 681 if (nyp) 682 nyp->next = alp; 683 else 684 ll->y_list = alp; 685 } 686 ll->y_line = alp; 687 vd_bar(alp->start.x, alp->start.y, alp->end.x, alp->end.y, 1, RGB(0, 255, 0)); 688 print_al("add ", alp); 689 } 690 691 typedef struct contour_cursor_s { 692 segment *prev, *pseg, *pfirst, *plast; 693 gx_flattened_iterator *fi; 694 bool more_flattened; 695 bool first_flattened; 696 int dir; 697 bool monotonic_y; 698 bool monotonic_x; 699 bool crossing; 700 } contour_cursor; 701 702 private inline int 703 compute_dir(const fill_options *fo, fixed y0, fixed y1) 704 { 705 if (max(y0, y1) < fo->ymin) 706 return 2; 707 if (min(y0, y1) > fo->ymax) 708 return 2; 709 return (y0 < y1 ? DIR_UP : 710 y0 > y1 ? DIR_DOWN : DIR_HORIZONTAL); 711 } 712 713 private inline int 714 add_y_curve_part(line_list *ll, segment *s0, segment *s1, int dir, 715 gx_flattened_iterator *fi, bool more1, bool step_back, bool monotonic_x) 716 { 717 active_line *alp = make_al(ll); 718 719 if (alp == NULL) 720 return_error(gs_error_VMerror); 721 alp->pseg = (dir == DIR_UP ? s1 : s0); 722 alp->direction = dir; 723 alp->fi = *fi; 724 alp->more_flattened = more1; 725 if (dir != DIR_UP && more1) 726 gx_flattened_iterator__switch_to_backscan(&alp->fi, more1); 727 if (step_back) { 728 do { 729 alp->more_flattened = gx_flattened_iterator__prev(&alp->fi); 730 if (compute_dir(ll->fo, alp->fi.ly0, alp->fi.ly1) != 2) 731 break; 732 } while (alp->more_flattened); 733 } 734 step_al(alp, false); 735 alp->monotonic_y = false; 736 alp->monotonic_x = monotonic_x; 737 insert_y_line(ll, alp); 738 return 0; 739 } 740 741 private inline int 742 add_y_line(const segment * prev_lp, const segment * lp, int dir, line_list *ll) 743 { 744 return add_y_line_aux(prev_lp, lp, &lp->pt, &prev_lp->pt, dir, ll); 745 } 746 747 private inline int 748 start_al_pair(line_list *ll, contour_cursor *q, contour_cursor *p) 749 { 750 int code; 751 752 if (q->monotonic_y) 753 code = add_y_line(q->prev, q->pseg, DIR_DOWN, ll); 754 else 755 code = add_y_curve_part(ll, q->prev, q->pseg, DIR_DOWN, q->fi, 756 !q->first_flattened, false, q->monotonic_x); 757 if (code < 0) 758 return code; 759 if (p->monotonic_y) 760 code = add_y_line(p->prev, p->pseg, DIR_UP, ll); 761 else 762 code = add_y_curve_part(ll, p->prev, p->pseg, DIR_UP, p->fi, 763 p->more_flattened, false, p->monotonic_x); 764 return code; 765 } 766 767 /* Start active lines from a minimum of a possibly non-monotonic curve. */ 768 private int 769 start_al_pair_from_min(line_list *ll, contour_cursor *q) 770 { 771 int dir, code; 772 const fill_options * const fo = ll->fo; 773 774 /* q stands at the first segment, which isn't last. */ 775 do { 776 q->more_flattened = gx_flattened_iterator__next(q->fi); 777 dir = compute_dir(fo, q->fi->ly0, q->fi->ly1); 778 if (q->fi->ly0 > fo->ymax && ll->y_break > q->fi->y0) 779 ll->y_break = q->fi->ly0; 780 if (q->fi->ly1 > fo->ymax && ll->y_break > q->fi->ly1) 781 ll->y_break = q->fi->ly1; 782 if (dir == DIR_UP && ll->main_dir == DIR_DOWN && q->fi->ly0 >= fo->ymin) { 783 code = add_y_curve_part(ll, q->prev, q->pseg, DIR_DOWN, q->fi, 784 true, true, q->monotonic_x); 785 if (code < 0) 786 return code; 787 code = add_y_curve_part(ll, q->prev, q->pseg, DIR_UP, q->fi, 788 q->more_flattened, false, q->monotonic_x); 789 if (code < 0) 790 return code; 791 } else if (q->fi->ly0 < fo->ymin && q->fi->ly1 >= fo->ymin) { 792 code = add_y_curve_part(ll, q->prev, q->pseg, DIR_UP, q->fi, 793 q->more_flattened, false, q->monotonic_x); 794 if (code < 0) 795 return code; 796 } else if (q->fi->ly0 >= fo->ymin && q->fi->ly1 < fo->ymin) { 797 code = add_y_curve_part(ll, q->prev, q->pseg, DIR_DOWN, q->fi, 798 true, false, q->monotonic_x); 799 if (code < 0) 800 return code; 801 } 802 q->first_flattened = false; 803 q->dir = dir; 804 ll->main_dir = (dir == DIR_DOWN ? DIR_DOWN : 805 dir == DIR_UP ? DIR_UP : ll->main_dir); 806 if (!q->more_flattened) 807 break; 808 } while(q->more_flattened); 809 /* q stands at the last segment. */ 810 return 0; 811 /* note : it doesn't depend on the number of curve minimums, 812 which may vary due to arithmetic errors. */ 813 } 814 815 private inline void 816 init_contour_cursor(line_list *ll, contour_cursor *q) 817 { 818 const fill_options * const fo = ll->fo; 819 820 if (q->pseg->type == s_curve) { 821 curve_segment *s = (curve_segment *)q->pseg; 822 fixed ymin = min(min(q->prev->pt.y, s->p1.y), min(s->p2.y, s->pt.y)); 823 fixed ymax = max(max(q->prev->pt.y, s->p1.y), max(s->p2.y, s->pt.y)); 824 bool in_band = ymin <= fo->ymax && ymax >= fo->ymin; 825 q->crossing = ymin < fo->ymin && ymax >= fo->ymin; 826 q->monotonic_y = !in_band || 827 (!q->crossing && 828 ((q->prev->pt.y <= s->p1.y && s->p1.y <= s->p2.y && s->p2.y <= s->pt.y) || 829 (q->prev->pt.y >= s->p1.y && s->p1.y >= s->p2.y && s->p2.y >= s->pt.y))); 830 q->monotonic_x = 831 ((q->prev->pt.x <= s->p1.x && s->p1.x <= s->p2.x && s->p2.x <= s->pt.x) || 832 (q->prev->pt.x >= s->p1.x && s->p1.x >= s->p2.x && s->p2.x >= s->pt.x)); 833 } else 834 q->monotonic_y = true; 835 if (!q->monotonic_y) { 836 curve_segment *s = (curve_segment *)q->pseg; 837 int k = gx_curve_log2_samples(q->prev->pt.x, q->prev->pt.y, s, fo->fixed_flat); 838 839 gx_flattened_iterator__init(q->fi, q->prev->pt.x, q->prev->pt.y, s, k); 840 } else { 841 q->dir = compute_dir(fo, q->prev->pt.y, q->pseg->pt.y); 842 gx_flattened_iterator__init_line(q->fi, 843 q->prev->pt.x, q->prev->pt.y, q->pseg->pt.x, q->pseg->pt.y); /* fake for curves. */ 844 vd_bar(q->prev->pt.x, q->prev->pt.y, q->pseg->pt.x, q->pseg->pt.y, 1, RGB(0, 0, 255)); 845 } 846 q->first_flattened = true; 847 } 848 849 private int 850 scan_contour(line_list *ll, contour_cursor *q) 851 { 852 contour_cursor p; 853 gx_flattened_iterator fi, save_fi; 854 segment *pseg; 855 int code; 856 bool only_horizontal = true, saved = false; 857 const fill_options * const fo = ll->fo; 858 contour_cursor save_q; 859 860 p.fi = &fi; 861 save_q.dir = 2; 862 ll->main_dir = DIR_HORIZONTAL; 863 for (; ; q->pseg = q->prev, q->prev = q->prev->prev) { 864 init_contour_cursor(ll, q); 865 while(gx_flattened_iterator__next(q->fi)) { 866 q->first_flattened = false; 867 q->dir = compute_dir(fo, q->fi->ly0, q->fi->ly1); 868 ll->main_dir = (q->dir == DIR_DOWN ? DIR_DOWN : 869 q->dir == DIR_UP ? DIR_UP : ll->main_dir); 870 } 871 q->dir = compute_dir(fo, q->fi->ly0, q->fi->ly1); 872 q->more_flattened = false; 873 ll->main_dir = (q->dir == DIR_DOWN ? DIR_DOWN : 874 q->dir == DIR_UP ? DIR_UP : ll->main_dir); 875 if (ll->main_dir != DIR_HORIZONTAL) { 876 only_horizontal = false; 877 break; 878 } 879 if (!saved && q->dir != 2) { 880 save_q = *q; 881 save_fi = *q->fi; 882 saved = true; 883 } 884 if (q->prev == q->pfirst) 885 break; 886 } 887 if (saved) { 888 *q = save_q; 889 *q->fi = save_fi; 890 } 891 for (pseg = q->pfirst; pseg != q->plast; pseg = pseg->next) { 892 p.prev = pseg; 893 p.pseg = pseg->next; 894 if (!fo->pseudo_rasterization || only_horizontal 895 || p.prev->pt.x != p.pseg->pt.x || p.prev->pt.y != p.pseg->pt.y 896 || p.pseg->type == s_curve) { 897 init_contour_cursor(ll, &p); 898 p.more_flattened = gx_flattened_iterator__next(p.fi); 899 p.dir = compute_dir(fo, p.fi->ly0, p.fi->ly1); 900 if (p.fi->ly0 > fo->ymax && ll->y_break > p.fi->ly0) 901 ll->y_break = p.fi->ly0; 902 if (p.fi->ly1 > fo->ymax && ll->y_break > p.fi->ly1) 903 ll->y_break = p.fi->ly1; 904 if (p.monotonic_y && p.dir == DIR_HORIZONTAL && 905 !fo->pseudo_rasterization && 906 fixed2int_pixround(p.pseg->pt.y - fo->adjust_below) < 907 fixed2int_pixround(p.pseg->pt.y + fo->adjust_above)) { 908 /* Add it here to avoid double processing in process_h_segments. */ 909 code = add_y_line(p.prev, p.pseg, DIR_HORIZONTAL, ll); 910 if (code < 0) 911 return code; 912 } 913 if (p.monotonic_y && p.dir == DIR_HORIZONTAL && 914 fo->pseudo_rasterization && only_horizontal) { 915 /* Add it here to avoid double processing in process_h_segments. */ 916 code = add_y_line(p.prev, p.pseg, DIR_HORIZONTAL, ll); 917 if (code < 0) 918 return code; 919 } 920 if (p.fi->ly0 >= fo->ymin && p.dir == DIR_UP && ll->main_dir == DIR_DOWN) { 921 code = start_al_pair(ll, q, &p); 922 if (code < 0) 923 return code; 924 } 925 if (p.fi->ly0 < fo->ymin && p.fi->ly1 >= fo->ymin) { 926 if (p.monotonic_y) 927 code = add_y_line(p.prev, p.pseg, DIR_UP, ll); 928 else 929 code = add_y_curve_part(ll, p.prev, p.pseg, DIR_UP, p.fi, 930 p.more_flattened, false, p.monotonic_x); 931 if (code < 0) 932 return code; 933 } 934 if (p.fi->ly0 >= fo->ymin && p.fi->ly1 < fo->ymin) { 935 if (p.monotonic_y) 936 code = add_y_line(p.prev, p.pseg, DIR_DOWN, ll); 937 else 938 code = add_y_curve_part(ll, p.prev, p.pseg, DIR_DOWN, p.fi, 939 !p.first_flattened, false, p.monotonic_x); 940 if (code < 0) 941 return code; 942 } 943 ll->main_dir = (p.dir == DIR_DOWN ? DIR_DOWN : 944 p.dir == DIR_UP ? DIR_UP : ll->main_dir); 945 if (!p.monotonic_y && p.more_flattened) { 946 code = start_al_pair_from_min(ll, &p); 947 if (code < 0) 948 return code; 949 } 950 if (p.dir == DIR_DOWN || p.dir == DIR_HORIZONTAL) { 951 gx_flattened_iterator *fi1 = q->fi; 952 q->prev = p.prev; 953 q->pseg = p.pseg; 954 q->monotonic_y = p.monotonic_y; 955 q->more_flattened = p.more_flattened; 956 q->first_flattened = p.first_flattened; 957 q->fi = p.fi; 958 q->dir = p.dir; 959 p.fi = fi1; 960 } 961 } 962 } 963 q->fi = NULL; /* safety. */ 964 return 0; 965 } 966 967 /* 968 * Construct a Y-sorted list of segments for rasterizing a path. We assume 969 * the path is non-empty. Only include non-horizontal lines or (monotonic) 970 * curve segments where one endpoint is locally Y-minimal, and horizontal 971 * lines that might color some additional pixels. 972 */ 973 private int 974 add_y_list(gx_path * ppath, line_list *ll) 975 { 976 subpath *psub = ppath->first_subpath; 977 int close_count = 0; 978 int code; 979 contour_cursor q; 980 gx_flattened_iterator fi; 981 982 ll->y_break = max_fixed; 983 984 for (;psub; psub = (subpath *)psub->last->next) { 985 /* We know that pseg points to a subpath head (s_start). */ 986 segment *pfirst = (segment *)psub; 987 segment *plast = psub->last, *prev; 988 989 q.fi = &fi; 990 if (plast->type != s_line_close) { 991 /* Create a fake s_line_close */ 992 line_close_segment *lp = &psub->closer; 993 segment *next = plast->next; 994 995 lp->next = next; 996 lp->prev = plast; 997 plast->next = (segment *) lp; 998 if (next) 999 next->prev = (segment *) lp; 1000 lp->type = s_line_close; 1001 lp->pt = psub->pt; 1002 lp->sub = psub; 1003 psub->last = plast = (segment *) lp; 1004 ll->close_count++; 1005 } 1006 prev = plast->prev; 1007 if (ll->fo->pseudo_rasterization && prev != pfirst && 1008 prev->pt.x == plast->pt.x && prev->pt.y == plast->pt.y) { 1009 plast = prev; 1010 prev = prev->prev; 1011 } 1012 q.prev = prev; 1013 q.pseg = plast; 1014 q.pfirst = pfirst; 1015 q.plast = plast; 1016 code = scan_contour(ll, &q); 1017 if (code < 0) 1018 return code; 1019 } 1020 return close_count; 1021 } 1022 1023 1024 private void 1025 step_al(active_line *alp, bool move_iterator) 1026 { 1027 bool forth = (alp->direction == DIR_UP || !alp->fi.curve); 1028 1029 if (move_iterator) { 1030 if (forth) 1031 alp->more_flattened = gx_flattened_iterator__next(&alp->fi); 1032 else 1033 alp->more_flattened = gx_flattened_iterator__prev(&alp->fi); 1034 } else 1035 vd_bar(alp->fi.lx0, alp->fi.ly0, alp->fi.lx1, alp->fi.ly1, 1, RGB(0, 0, 255)); 1036 /* Note that we can get alp->fi.ly0 == alp->fi.ly1 1037 if the curve tangent is horizontal. */ 1038 alp->start.x = (forth ? alp->fi.lx0 : alp->fi.lx1); 1039 alp->start.y = (forth ? alp->fi.ly0 : alp->fi.ly1); 1040 alp->end.x = (forth ? alp->fi.lx1 : alp->fi.lx0); 1041 alp->end.y = (forth ? alp->fi.ly1 : alp->fi.ly0); 1042 alp->diff.x = alp->end.x - alp->start.x; 1043 alp->diff.y = alp->end.y - alp->start.y; 1044 SET_NUM_ADJUST(alp); 1045 (alp)->y_fast_max = MAX_MINUS_NUM_ADJUST(alp) / 1046 ((alp->diff.x >= 0 ? alp->diff.x : -alp->diff.x) | 1) + alp->start.y; 1047 } 1048 1049 private void 1050 init_al(active_line *alp, const segment *s0, const segment *s1, const line_list *ll) 1051 { 1052 const segment *ss = (alp->direction == DIR_UP ? s1 : s0); 1053 /* Warning : p0 may be equal to &alp->end. */ 1054 bool curve = (ss != NULL && ss->type == s_curve); 1055 1056 if (curve) { 1057 if (alp->direction == DIR_UP) { 1058 const curve_segment *cs = (const curve_segment *)s1; 1059 int k = gx_curve_log2_samples(s0->pt.x, s0->pt.y, cs, ll->fo->fixed_flat); 1060 1061 gx_flattened_iterator__init(&alp->fi, 1062 s0->pt.x, s0->pt.y, (const curve_segment *)s1, k); 1063 step_al(alp, true); 1064 if (!ll->fo->fill_by_trapezoids) { 1065 alp->monotonic_y = (s0->pt.y <= cs->p1.y && cs->p1.y <= cs->p2.y && cs->p2.y <= cs->pt.y); 1066 alp->monotonic_x = (s0->pt.x <= cs->p1.x && cs->p1.x <= cs->p2.x && cs->p2.x <= cs->pt.x) || 1067 (s0->pt.x >= cs->p1.x && cs->p1.x >= cs->p2.x && cs->p2.x >= cs->pt.x); 1068 } 1069 } else { 1070 const curve_segment *cs = (const curve_segment *)s0; 1071 int k = gx_curve_log2_samples(s1->pt.x, s1->pt.y, cs, ll->fo->fixed_flat); 1072 bool more; 1073 1074 gx_flattened_iterator__init(&alp->fi, 1075 s1->pt.x, s1->pt.y, (const curve_segment *)s0, k); 1076 alp->more_flattened = false; 1077 do { 1078 more = gx_flattened_iterator__next(&alp->fi); 1079 alp->more_flattened |= more; 1080 } while(more); 1081 gx_flattened_iterator__switch_to_backscan(&alp->fi, alp->more_flattened); 1082 step_al(alp, false); 1083 if (!ll->fo->fill_by_trapezoids) { 1084 alp->monotonic_y = (s0->pt.y >= cs->p1.y && cs->p1.y >= cs->p2.y && cs->p2.y >= cs->pt.y); 1085 alp->monotonic_x = (s0->pt.x <= cs->p1.x && cs->p1.x <= cs->p2.x && cs->p2.x <= cs->pt.x) || 1086 (s0->pt.x >= cs->p1.x && cs->p1.x >= cs->p2.x && cs->p2.x >= cs->pt.x); 1087 } 1088 } 1089 } else { 1090 gx_flattened_iterator__init_line(&alp->fi, 1091 s0->pt.x, s0->pt.y, s1->pt.x, s1->pt.y); 1092 step_al(alp, true); 1093 alp->monotonic_x = alp->monotonic_y = true; 1094 } 1095 alp->pseg = s1; 1096 } 1097 /* 1098 * Internal routine to test a segment and add it to the pending list if 1099 * appropriate. 1100 */ 1101 private int 1102 add_y_line_aux(const segment * prev_lp, const segment * lp, 1103 const gs_fixed_point *curr, const gs_fixed_point *prev, int dir, line_list *ll) 1104 { 1105 active_line *alp = make_al(ll); 1106 if (alp == NULL) 1107 return_error(gs_error_VMerror); 1108 alp->more_flattened = false; 1109 switch ((alp->direction = dir)) { 1110 case DIR_UP: 1111 init_al(alp, prev_lp, lp, ll); 1112 break; 1113 case DIR_DOWN: 1114 init_al(alp, lp, prev_lp, ll); 1115 break; 1116 case DIR_HORIZONTAL: 1117 alp->start = *prev; 1118 alp->end = *curr; 1119 /* Don't need to set dx or y_fast_max */ 1120 alp->pseg = prev_lp; /* may not need this either */ 1121 break; 1122 default: /* can't happen */ 1123 return_error(gs_error_unregistered); 1124 } 1125 insert_y_line(ll, alp); 1126 return 0; 1127 } 1128 1129 1130 /* ---------------- Filling loop utilities ---------------- */ 1131 1132 /* Insert a newly active line in the X ordering. */ 1133 private void 1134 insert_x_new(active_line * alp, line_list *ll) 1135 { 1136 active_line *next; 1137 active_line *prev = &ll->x_head; 1138 1139 vd_bar(alp->start.x, alp->start.y, alp->end.x, alp->end.y, 1, RGB(128, 128, 0)); 1140 alp->x_current = alp->start.x; 1141 alp->x_next = alp->start.x; /* If the spot starts with a horizontal segment, 1142 we need resort_x_line to work properly 1143 in the very beginning. */ 1144 while (INCR_EXPR(x_step), 1145 (next = prev->next) != 0 && x_order(next, alp) < 0 1146 ) 1147 prev = next; 1148 alp->next = next; 1149 alp->prev = prev; 1150 if (next != 0) 1151 next->prev = alp; 1152 prev->next = alp; 1153 } 1154 1155 /* Insert a newly active line in the h list. */ 1156 /* h list isn't ordered because x intervals may overlap. */ 1157 /* todo : optimize with maintaining ordered interval list; 1158 Unite contacting inrevals, like we did in add_margin. 1159 */ 1160 private inline void 1161 insert_h_new(active_line * alp, line_list *ll) 1162 { 1163 alp->next = ll->h_list0; 1164 alp->prev = 0; 1165 if (ll->h_list0 != 0) 1166 ll->h_list0->prev = alp; 1167 ll->h_list0 = alp; 1168 /* 1169 * h list keeps horizontal lines for a given y. 1170 * There are 2 lists, corresponding to upper and lower ends 1171 * of the Y-interval, which spot_into_trapezoids currently proceeds. 1172 * Parts of horizontal lines, which do not contact a filled trapezoid, 1173 * are parts of the spot bondairy. They to be marked in 1174 * the 'sect' array. - see process_h_lists. 1175 */ 1176 } 1177 1178 private inline void 1179 remove_al(const line_list *ll, active_line *alp) 1180 { 1181 active_line *nlp = alp->next; 1182 1183 alp->prev->next = nlp; 1184 if (nlp) 1185 nlp->prev = alp->prev; 1186 if_debug1('F', "[F]drop 0x%lx\n", (ulong) alp); 1187 } 1188 1189 /* 1190 * Handle a line segment that just ended. Return true iff this was 1191 * the end of a line sequence. 1192 */ 1193 private bool 1194 end_x_line(active_line *alp, const line_list *ll, bool update) 1195 { 1196 const segment *pseg = alp->pseg; 1197 /* 1198 * The computation of next relies on the fact that 1199 * all subpaths have been closed. When we cycle 1200 * around to the other end of a subpath, we must be 1201 * sure not to process the start/end point twice. 1202 */ 1203 const segment *next = 1204 (alp->direction == DIR_UP ? 1205 ( /* Upward line, go forward along path. */ 1206 pseg->type == s_line_close ? /* end of subpath */ 1207 ((const line_close_segment *)pseg)->sub->next : 1208 pseg->next) : 1209 ( /* Downward line, go backward along path. */ 1210 pseg->type == s_start ? /* start of subpath */ 1211 ((const subpath *)pseg)->last->prev : 1212 pseg->prev) 1213 ); 1214 1215 if (alp->end.y < alp->start.y) { 1216 /* fixme: The condition above causes a horizontal 1217 part of a curve near an Y maximum to process twice : 1218 once scanning the left spot boundary and once scanning the right one. 1219 In both cases it will go to the H list. 1220 However the dropout prevention logic isn't 1221 sensitive to that, and such segments does not affect 1222 trapezoids. Thus the resulting raster doesn't depend on that. 1223 However it would be nice to improve someday. 1224 */ 1225 remove_al(ll, alp); 1226 return true; 1227 } else if (alp->more_flattened) 1228 return false; 1229 init_al(alp, pseg, next, ll); 1230 if (alp->start.y > alp->end.y) { 1231 /* See comment above. */ 1232 remove_al(ll, alp); 1233 return true; 1234 } 1235 alp->x_current = alp->x_next = alp->start.x; 1236 vd_bar(alp->start.x, alp->start.y, alp->end.x, alp->end.y, 1, RGB(128, 0, 128)); 1237 print_al("repl", alp); 1238 return false; 1239 } 1240 1241 private inline int 1242 add_margin(line_list * ll, active_line * flp, active_line * alp, fixed y0, fixed y1) 1243 { vd_bar(alp->start.x, alp->start.y, alp->end.x, alp->end.y, 1, RGB(255, 255, 255)); 1244 vd_bar(flp->start.x, flp->start.y, flp->end.x, flp->end.y, 1, RGB(255, 255, 255)); 1245 return continue_margin_common(ll, &ll->margin_set0, flp, alp, y0, y1); 1246 } 1247 1248 private inline int 1249 continue_margin(line_list * ll, active_line * flp, active_line * alp, fixed y0, fixed y1) 1250 { 1251 return continue_margin_common(ll, &ll->margin_set0, flp, alp, y0, y1); 1252 } 1253 1254 private inline int 1255 complete_margin(line_list * ll, active_line * flp, active_line * alp, fixed y0, fixed y1) 1256 { 1257 return continue_margin_common(ll, &ll->margin_set1, flp, alp, y0, y1); 1258 } 1259 1260 /* 1261 * Handle the case of a slanted trapezoid with adjustment. 1262 * To do this exactly right requires filling a central trapezoid 1263 * (or rectangle) plus two horizontal almost-rectangles. 1264 */ 1265 private int 1266 fill_slant_adjust(const line_list *ll, 1267 const active_line *flp, const active_line *alp, fixed y, fixed y1) 1268 { 1269 const fill_options * const fo = ll->fo; 1270 const fixed Yb = y - fo->adjust_below; 1271 const fixed Ya = y + fo->adjust_above; 1272 const fixed Y1b = y1 - fo->adjust_below; 1273 const fixed Y1a = y1 + fo->adjust_above; 1274 const gs_fixed_edge *plbot, *prbot, *pltop, *prtop; 1275 gs_fixed_edge vert_left, slant_left, vert_right, slant_right; 1276 int code; 1277 1278 INCR(slant); 1279 vd_quad(flp->x_current, y, alp->x_current, y, 1280 alp->x_next, y1, flp->x_next, y1, 1, VD_TRAP_COLOR); /* fixme: Wrong X. */ 1281 1282 /* Set up all the edges, even though we may not need them all. */ 1283 1284 if (flp->start.x < flp->end.x) { 1285 vert_left.start.x = vert_left.end.x = flp->x_current - fo->adjust_left; 1286 vert_left.start.y = Yb, vert_left.end.y = Ya; 1287 vert_right.start.x = vert_right.end.x = alp->x_next + fo->adjust_right; 1288 vert_right.start.y = Y1b, vert_right.end.y = Y1a; 1289 slant_left.start.y = flp->start.y + fo->adjust_above; 1290 slant_left.end.y = flp->end.y + fo->adjust_above; 1291 slant_right.start.y = alp->start.y - fo->adjust_below; 1292 slant_right.end.y = alp->end.y - fo->adjust_below; 1293 plbot = &vert_left, prbot = &slant_right; 1294 pltop = &slant_left, prtop = &vert_right; 1295 } else { 1296 vert_left.start.x = vert_left.end.x = flp->x_next - fo->adjust_left; 1297 vert_left.start.y = Y1b, vert_left.end.y = Y1a; 1298 vert_right.start.x = vert_right.end.x = alp->x_current + fo->adjust_right; 1299 vert_right.start.y = Yb, vert_right.end.y = Ya; 1300 slant_left.start.y = flp->start.y - fo->adjust_below; 1301 slant_left.end.y = flp->end.y - fo->adjust_below; 1302 slant_right.start.y = alp->start.y + fo->adjust_above; 1303 slant_right.end.y = alp->end.y + fo->adjust_above; 1304 plbot = &slant_left, prbot = &vert_right; 1305 pltop = &vert_left, prtop = &slant_right; 1306 } 1307 slant_left.start.x = flp->start.x - fo->adjust_left; 1308 slant_left.end.x = flp->end.x - fo->adjust_left; 1309 slant_right.start.x = alp->start.x + fo->adjust_right; 1310 slant_right.end.x = alp->end.x + fo->adjust_right; 1311 1312 if (Ya >= Y1b) { 1313 /* 1314 * The upper and lower adjustment bands overlap. 1315 * Since the entire entity is less than 2 pixels high 1316 * in this case, we could handle it very efficiently 1317 * with no more than 2 rectangle fills, but for right now 1318 * we don't attempt to do this. 1319 */ 1320 int iYb = fixed2int_var_pixround(Yb); 1321 int iYa = fixed2int_var_pixround(Ya); 1322 int iY1b = fixed2int_var_pixround(Y1b); 1323 int iY1a = fixed2int_var_pixround(Y1a); 1324 1325 INCR(slant_shallow); 1326 if (iY1b > iYb) { 1327 code = fo->fill_trap(fo->dev, plbot, prbot, 1328 Yb, Y1b, false, fo->pdevc, fo->lop); 1329 if (code < 0) 1330 return code; 1331 } 1332 if (iYa > iY1b) { 1333 int ix = fixed2int_var_pixround(vert_left.start.x); 1334 int iw = fixed2int_var_pixround(vert_right.start.x) - ix; 1335 1336 code = gx_fill_rectangle_device_rop(ix, iY1b, iw, iYa - iY1b, 1337 fo->pdevc, fo->dev, fo->lop); 1338 if (code < 0) 1339 return code; 1340 } 1341 if (iY1a > iYa) 1342 code = fo->fill_trap(fo->dev, pltop, prtop, 1343 Ya, Y1a, false, fo->pdevc, fo->lop); 1344 else 1345 code = 0; 1346 } else { 1347 /* 1348 * Clip the trapezoid if possible. This can save a lot 1349 * of work when filling paths that cross band boundaries. 1350 */ 1351 fixed Yac; 1352 1353 if (fo->pbox->p.y < Ya) { 1354 code = fo->fill_trap(fo->dev, plbot, prbot, 1355 Yb, Ya, false, fo->pdevc, fo->lop); 1356 if (code < 0) 1357 return code; 1358 Yac = Ya; 1359 } else 1360 Yac = fo->pbox->p.y; 1361 if (fo->pbox->q.y > Y1b) { 1362 code = fo->fill_trap(fo->dev, &slant_left, &slant_right, 1363 Yac, Y1b, false, fo->pdevc, fo->lop); 1364 if (code < 0) 1365 return code; 1366 code = fo->fill_trap(fo->dev, pltop, prtop, 1367 Y1b, Y1a, false, fo->pdevc, fo->lop); 1368 } else 1369 code = fo->fill_trap(fo->dev, &slant_left, &slant_right, 1370 Yac, fo->pbox->q.y, false, fo->pdevc, fo->lop); 1371 } 1372 return code; 1373 } 1374 1375 /* Re-sort the x list by moving alp backward to its proper spot. */ 1376 private inline void 1377 resort_x_line(active_line * alp) 1378 { 1379 active_line *prev = alp->prev; 1380 active_line *next = alp->next; 1381 1382 prev->next = next; 1383 if (next) 1384 next->prev = prev; 1385 while (x_order(prev, alp) > 0) { 1386 if_debug2('F', "[F]swap 0x%lx,0x%lx\n", 1387 (ulong) alp, (ulong) prev); 1388 next = prev, prev = prev->prev; 1389 } 1390 alp->next = next; 1391 alp->prev = prev; 1392 /* next might be null, if alp was in the correct spot already. */ 1393 if (next) 1394 next->prev = alp; 1395 prev->next = alp; 1396 } 1397 1398 /* Move active lines by Y. */ 1399 private inline void 1400 move_al_by_y(line_list *ll, fixed y1) 1401 { 1402 fixed x; 1403 active_line *alp, *nlp; 1404 1405 for (x = min_fixed, alp = ll->x_list; alp != 0; alp = nlp) { 1406 bool notend = false; 1407 alp->x_current = alp->x_next; 1408 1409 nlp = alp->next; 1410 if (alp->end.y == y1 && alp->more_flattened) { 1411 step_al(alp, true); 1412 alp->x_current = alp->x_next = alp->start.x; 1413 notend = (alp->end.y >= alp->start.y); 1414 } 1415 if (alp->end.y > y1 || notend || !end_x_line(alp, ll, true)) { 1416 if (alp->x_next <= x) 1417 resort_x_line(alp); 1418 else 1419 x = alp->x_next; 1420 } 1421 } 1422 if (ll->x_list != 0 && ll->fo->pseudo_rasterization) { 1423 /* Ensure that contacting vertical stems are properly ordered. 1424 We don't want to unite contacting stems into 1425 a single margin, because it can cause a dropout : 1426 narrow stems are widened against a dropout, but 1427 an united wide one may be left unwidened. 1428 */ 1429 for (alp = ll->x_list; alp->next != 0; ) { 1430 if (alp->start.x == alp->end.x && 1431 alp->start.x == alp->next->start.x && 1432 alp->next->start.x == alp->next->end.x && 1433 alp->direction > alp->next->direction) { 1434 /* Exchange. */ 1435 active_line *prev = alp->prev; 1436 active_line *next = alp->next; 1437 active_line *next2 = next->next; 1438 if (prev) 1439 prev->next = next; 1440 else 1441 ll->x_list = next; 1442 next->prev = prev; 1443 alp->prev = next; 1444 alp->next = next2; 1445 next->next = alp; 1446 if (next2) 1447 next2->prev = alp; 1448 } else 1449 alp = alp->next; 1450 } 1451 } 1452 } 1453 1454 /* Process horizontal segment of curves. */ 1455 private inline int 1456 process_h_segments(line_list *ll, fixed y) 1457 { 1458 active_line *alp, *nlp; 1459 int code, inserted = 0; 1460 1461 for (alp = ll->x_list; alp != 0; alp = nlp) { 1462 nlp = alp->next; 1463 if (alp->start.y == y && alp->end.y == y) { 1464 if (ll->fo->pseudo_rasterization) { 1465 code = add_y_line_aux(NULL, NULL, &alp->start, &alp->end, DIR_HORIZONTAL, ll); 1466 if (code < 0) 1467 return code; 1468 } 1469 inserted = 1; 1470 } 1471 } 1472 return inserted; 1473 /* After this should call move_al_by_y and step to the next band. */ 1474 } 1475 1476 private inline int 1477 loop_fill_trap_np(const line_list *ll, const gs_fixed_edge *le, const gs_fixed_edge *re, fixed y, fixed y1) 1478 { 1479 const fill_options * const fo = ll->fo; 1480 fixed ybot = max(y, fo->pbox->p.y); 1481 fixed ytop = min(y1, fo->pbox->q.y); 1482 1483 if (ybot >= ytop) 1484 return 0; 1485 vd_quad(le->start.x, ybot, re->start.x, ybot, re->end.x, ytop, le->end.x, ytop, 1, VD_TRAP_COLOR); 1486 return (*fo->fill_trap) 1487 (fo->dev, le, re, ybot, ytop, false, fo->pdevc, fo->lop); 1488 } 1489 1490 /* Define variants of the algorithm for filling a slanted trapezoid. */ 1491 #define TEMPLATE_slant_into_trapezoids slant_into_trapezoids__fd 1492 #define FILL_DIRECT 1 1493 #include "gxfillts.h" 1494 #undef TEMPLATE_slant_into_trapezoids 1495 #undef FILL_DIRECT 1496 1497 #define TEMPLATE_slant_into_trapezoids slant_into_trapezoids__nd 1498 #define FILL_DIRECT 0 1499 #include "gxfillts.h" 1500 #undef TEMPLATE_slant_into_trapezoids 1501 #undef FILL_DIRECT 1502 1503 1504 #define COVERING_PIXEL_CENTERS(y, y1, adjust_below, adjust_above)\ 1505 (fixed_pixround(y - adjust_below) < fixed_pixround(y1 + adjust_above)) 1506 1507 /* Find an intersection within y, y1. */ 1508 /* lp->x_current, lp->x_next must be set for y, y1. */ 1509 private bool 1510 intersect(active_line *endp, active_line *alp, fixed y, fixed y1, fixed *p_y_new) 1511 { 1512 fixed y_new, dy; 1513 fixed dx_old = alp->x_current - endp->x_current; 1514 fixed dx_den = dx_old + endp->x_next - alp->x_next; 1515 1516 if (dx_den <= dx_old) 1517 return false; /* Intersection isn't possible. */ 1518 dy = y1 - y; 1519 if_debug3('F', "[F]cross: dy=%g, dx_old=%g, dx_new=%g\n", 1520 fixed2float(dy), fixed2float(dx_old), 1521 fixed2float(dx_den - dx_old)); 1522 /* Do the computation in single precision */ 1523 /* if the values are small enough. */ 1524 y_new = 1525 ((dy | dx_old) < 1L << (size_of(fixed) * 4 - 1) ? 1526 dy * dx_old / dx_den : 1527 (INCR_EXPR(mq_cross), fixed_mult_quo(dy, dx_old, dx_den))) 1528 + y; 1529 /* The crossing value doesn't have to be */ 1530 /* very accurate, but it does have to be */ 1531 /* greater than y and less than y1. */ 1532 if_debug3('F', "[F]cross y=%g, y_new=%g, y1=%g\n", 1533 fixed2float(y), fixed2float(y_new), 1534 fixed2float(y1)); 1535 if (y_new <= y) { 1536 /* 1537 * This isn't possible. Recompute the intersection 1538 * accurately. 1539 */ 1540 fixed ys, xs0, xs1, ye, xe0, xe1, dy, dx0, dx1; 1541 1542 INCR(cross_slow); 1543 if (endp->start.y < alp->start.y) 1544 ys = alp->start.y, 1545 xs0 = AL_X_AT_Y(endp, ys), xs1 = alp->start.x; 1546 else 1547 ys = endp->start.y, 1548 xs0 = endp->start.x, xs1 = AL_X_AT_Y(alp, ys); 1549 if (endp->end.y > alp->end.y) 1550 ye = alp->end.y, 1551 xe0 = AL_X_AT_Y(endp, ye), xe1 = alp->end.x; 1552 else 1553 ye = endp->end.y, 1554 xe0 = endp->end.x, xe1 = AL_X_AT_Y(alp, ye); 1555 dy = ye - ys; 1556 dx0 = xe0 - xs0; 1557 dx1 = xe1 - xs1; 1558 /* We need xs0 + cross * dx0 == xs1 + cross * dx1. */ 1559 if (dx0 == dx1) { 1560 /* The two lines are coincident. Do nothing. */ 1561 y_new = y1; 1562 } else { 1563 double cross = (double)(xs0 - xs1) / (dx1 - dx0); 1564 1565 y_new = (fixed)(ys + cross * dy); 1566 if (y_new <= y) { 1567 /* 1568 * This can only happen through some kind of 1569 * numeric disaster, but we have to check. 1570 */ 1571 INCR(cross_low); 1572 y_new = y + fixed_epsilon; 1573 } 1574 } 1575 } 1576 *p_y_new = y_new; 1577 return true; 1578 } 1579 1580 private inline void 1581 set_x_next(active_line *endp, active_line *alp, fixed x) 1582 { 1583 while(endp != alp) { 1584 endp->x_next = x; 1585 endp = endp->next; 1586 } 1587 } 1588 1589 private inline int 1590 coord_weight(const active_line *alp) 1591 { 1592 return 1 + min(any_abs((int)((int64_t)alp->diff.y * 8 / alp->diff.x)), 256); 1593 } 1594 1595 1596 /* Find intersections of active lines within the band. 1597 Intersect and reorder them, and correct the bund top. */ 1598 private void 1599 intersect_al(line_list *ll, fixed y, fixed *y_top, int draw, bool all_bands) 1600 { 1601 fixed x = min_fixed, y1 = *y_top; 1602 active_line *alp, *stopx = NULL; 1603 active_line *endp = NULL; 1604 1605 /* don't bother if no pixels with no pseudo_rasterization */ 1606 if (y == y1) { 1607 /* Rather the intersection algorithm can handle this case with 1608 retrieving x_next equal to x_current, 1609 we bypass it for safety reason. 1610 */ 1611 } else if (ll->fo->pseudo_rasterization || draw >= 0 || all_bands) { 1612 /* 1613 * Loop invariants: 1614 * alp = endp->next; 1615 * for all lines lp from stopx up to alp, 1616 * lp->x_next = AL_X_AT_Y(lp, y1). 1617 */ 1618 for (alp = stopx = ll->x_list; 1619 INCR_EXPR(find_y), alp != 0; 1620 endp = alp, alp = alp->next 1621 ) { 1622 fixed nx = AL_X_AT_Y(alp, y1); 1623 fixed y_new; 1624 1625 alp->x_next = nx; 1626 /* Check for intersecting lines. */ 1627 if (nx >= x) 1628 x = nx; 1629 else if (alp->x_current >= endp->x_current && 1630 intersect(endp, alp, y, y1, &y_new)) { 1631 if (y_new <= y1) { 1632 stopx = endp; 1633 y1 = y_new; 1634 if (endp->diff.x == 0) 1635 nx = endp->start.x; 1636 else if (alp->diff.x == 0) 1637 nx = alp->start.x; 1638 else { 1639 fixed nx0 = AL_X_AT_Y(endp, y1); 1640 fixed nx1 = AL_X_AT_Y(alp, y1); 1641 if (nx0 != nx1) { 1642 /* Different results due to arithmetic errors. 1643 Choose an imtermediate point. 1644 We don't like to use floating numbners here, 1645 but the code with int64_t isn't much better. */ 1646 int64_t w0 = coord_weight(endp); 1647 int64_t w1 = coord_weight(alp); 1648 1649 nx = (fixed)((w0 * nx0 + w1 * nx1) / (w0 + w1)); 1650 } else 1651 nx = nx0; 1652 } 1653 endp->x_next = alp->x_next = nx; /* Ensure same X. */ 1654 draw = 0; 1655 /* Can't guarantee same x for triple intersections here. 1656 Will take care below */ 1657 } 1658 if (nx > x) 1659 x = nx; 1660 } 1661 } 1662 /* Recompute next_x for lines before the intersection. */ 1663 for (alp = ll->x_list; alp != stopx; alp = alp->next) 1664 alp->x_next = AL_X_AT_Y(alp, y1); 1665 /* Ensure X monotonity (particularly imporoves triple intersections). */ 1666 if (ll->x_list != NULL) { 1667 for (;;) { 1668 fixed x1; 1669 double sx = 0xbaadf00d; /* 'fixed' can overflow. We operate 7-bytes integers. */ 1670 int k = 0xbaadf00d, n; 1671 1672 endp = ll->x_list; 1673 x1 = endp->x_next; 1674 for (alp = endp->next; alp != NULL; x1 = alp->x_next, alp = alp->next) 1675 if (alp->x_next < x1) 1676 break; 1677 if (alp == NULL) 1678 break; 1679 x1 = endp->x_next; 1680 n = 0; 1681 for (alp = endp->next; alp != NULL; alp = alp->next) { 1682 x = alp->x_next; 1683 if (x < x1) { 1684 if (n == 0) { 1685 if (endp->diff.x == 0) { 1686 k = -1; 1687 sx = x1; 1688 } else { 1689 k = coord_weight(endp); 1690 sx = (double)x1 * k; 1691 } 1692 n = 1; 1693 } 1694 n++; 1695 if (alp->diff.x == 0) { 1696 /* Vertical lines have a higher priority. */ 1697 if (k <= -1) { 1698 sx += x; 1699 k--; 1700 } else { 1701 k = -1; 1702 sx = x; 1703 } 1704 } else if (k > 0) { 1705 int w = coord_weight(alp); 1706 1707 sx += (double)x * w; 1708 k += w; 1709 } 1710 } else { 1711 if (n > 1) { 1712 k = any_abs(k); 1713 set_x_next(endp, alp, (fixed)((sx + k / 2) / k)); 1714 } 1715 x1 = alp->x_next; 1716 n = 0; 1717 endp = alp; 1718 } 1719 } 1720 if (n > 1) { 1721 k = any_abs(k); 1722 set_x_next(endp, alp, (fixed)((sx + k / 2) / k)); 1723 } 1724 } 1725 } 1726 } else { 1727 /* Recompute next_x for lines before the intersection. */ 1728 for (alp = ll->x_list; alp != stopx; alp = alp->next) 1729 alp->x_next = AL_X_AT_Y(alp, y1); 1730 } 1731 #ifdef DEBUG 1732 if (gs_debug_c('F')) { 1733 dlprintf1("[F]after loop: y1=%f\n", fixed2float(y1)); 1734 print_line_list(ll->x_list); 1735 } 1736 #endif 1737 *y_top = y1; 1738 } 1739 1740 /* ---------------- Trapezoid filling loop ---------------- */ 1741 1742 /* Generate specialized algorythms for the most important cases : */ 1743 1744 #define IS_SPOTAN 1 1745 #define PSEUDO_RASTERIZATION 0 1746 #define FILL_ADJUST 0 1747 #define FILL_DIRECT 1 1748 #define TEMPLATE_spot_into_trapezoids spot_into_trapezoids__spotan 1749 #include "gxfilltr.h" 1750 #undef IS_SPOTAN 1751 #undef PSEUDO_RASTERIZATION 1752 #undef FILL_ADJUST 1753 #undef FILL_DIRECT 1754 #undef TEMPLATE_spot_into_trapezoids 1755 1756 #define IS_SPOTAN 0 1757 #define PSEUDO_RASTERIZATION 1 1758 #define FILL_ADJUST 0 1759 #define FILL_DIRECT 1 1760 #define TEMPLATE_spot_into_trapezoids spot_into_trapezoids__pr_fd 1761 #include "gxfilltr.h" 1762 #undef IS_SPOTAN 1763 #undef PSEUDO_RASTERIZATION 1764 #undef FILL_ADJUST 1765 #undef FILL_DIRECT 1766 #undef TEMPLATE_spot_into_trapezoids 1767 1768 #define IS_SPOTAN 0 1769 #define PSEUDO_RASTERIZATION 1 1770 #define FILL_ADJUST 0 1771 #define FILL_DIRECT 0 1772 #define TEMPLATE_spot_into_trapezoids spot_into_trapezoids__pr_nd 1773 #include "gxfilltr.h" 1774 #undef IS_SPOTAN 1775 #undef PSEUDO_RASTERIZATION 1776 #undef FILL_ADJUST 1777 #undef FILL_DIRECT 1778 #undef TEMPLATE_spot_into_trapezoids 1779 1780 #define IS_SPOTAN 0 1781 #define PSEUDO_RASTERIZATION 0 1782 #define FILL_ADJUST 1 1783 #define FILL_DIRECT 1 1784 #define TEMPLATE_spot_into_trapezoids spot_into_trapezoids__aj_fd 1785 #include "gxfilltr.h" 1786 #undef IS_SPOTAN 1787 #undef PSEUDO_RASTERIZATION 1788 #undef FILL_ADJUST 1789 #undef FILL_DIRECT 1790 #undef TEMPLATE_spot_into_trapezoids 1791 1792 #define IS_SPOTAN 0 1793 #define PSEUDO_RASTERIZATION 0 1794 #define FILL_ADJUST 1 1795 #define FILL_DIRECT 0 1796 #define TEMPLATE_spot_into_trapezoids spot_into_trapezoids__aj_nd 1797 #include "gxfilltr.h" 1798 #undef IS_SPOTAN 1799 #undef PSEUDO_RASTERIZATION 1800 #undef FILL_ADJUST 1801 #undef FILL_DIRECT 1802 #undef TEMPLATE_spot_into_trapezoids 1803 1804 #define IS_SPOTAN 0 1805 #define PSEUDO_RASTERIZATION 0 1806 #define FILL_ADJUST 0 1807 #define FILL_DIRECT 1 1808 #define TEMPLATE_spot_into_trapezoids spot_into_trapezoids__nj_fd 1809 #include "gxfilltr.h" 1810 #undef IS_SPOTAN 1811 #undef PSEUDO_RASTERIZATION 1812 #undef FILL_ADJUST 1813 #undef FILL_DIRECT 1814 #undef TEMPLATE_spot_into_trapezoids 1815 1816 #define IS_SPOTAN 0 1817 #define PSEUDO_RASTERIZATION 0 1818 #define FILL_ADJUST 0 1819 #define FILL_DIRECT 0 1820 #define TEMPLATE_spot_into_trapezoids spot_into_trapezoids__nj_nd 1821 #include "gxfilltr.h" 1822 #undef IS_SPOTAN 1823 #undef PSEUDO_RASTERIZATION 1824 #undef FILL_ADJUST 1825 #undef FILL_DIRECT 1826 #undef TEMPLATE_spot_into_trapezoids 1827 1828 1829 /* Main filling loop. Takes lines off of y_list and adds them to */ 1830 /* x_list as needed. band_mask limits the size of each band, */ 1831 /* by requiring that ((y1 - 1) & band_mask) == (y0 & band_mask). */ 1832 private int 1833 spot_into_trapezoids(line_list *ll, fixed band_mask) 1834 { 1835 /* For better porformance, choose a specialized algorithm : */ 1836 const fill_options * const fo = ll->fo; 1837 1838 if (fo->is_spotan) 1839 return spot_into_trapezoids__spotan(ll, band_mask); 1840 if (fo->pseudo_rasterization) { 1841 if (fo->fill_direct) 1842 return spot_into_trapezoids__pr_fd(ll, band_mask); 1843 else 1844 return spot_into_trapezoids__pr_nd(ll, band_mask); 1845 } 1846 if (fo->adjust_below | fo->adjust_above | fo->adjust_left | fo->adjust_right) { 1847 if (fo->fill_direct) 1848 return spot_into_trapezoids__aj_fd(ll, band_mask); 1849 else 1850 return spot_into_trapezoids__aj_nd(ll, band_mask); 1851 } else { 1852 if (fo->fill_direct) 1853 return spot_into_trapezoids__nj_fd(ll, band_mask); 1854 else 1855 return spot_into_trapezoids__nj_nd(ll, band_mask); 1856 } 1857 } 1858 1859 /* ---------------- Range list management ---------------- */ 1860 1861 /* 1862 * We originally thought we would store fixed values in coordinate ranges, 1863 * but it turned out we want to store integers. 1864 */ 1865 typedef int coord_value_t; 1866 #define MIN_COORD_VALUE min_int 1867 #define MAX_COORD_VALUE max_int 1868 /* 1869 * The invariant for coord_range_ts in a coord_range_list_t: 1870 * if prev == 0: 1871 * next != 0 1872 * rmin == rmax == MIN_COORD_VALUE 1873 * else if next == 0: 1874 * prev != 0 1875 * rmin == rmax == MAX_COORD_VALUE 1876 * else 1877 * rmin < rmax 1878 * if prev != 0: 1879 * prev->next == this 1880 * prev->rmax < rmin 1881 * if next != 0: 1882 * next->prev = this 1883 * next->rmin > rmax 1884 * A coord_range_list_t has a boundary element at each end to avoid having 1885 * to test for null pointers in the insertion loop. The boundary elements 1886 * are the only empty ranges. 1887 */ 1888 typedef struct coord_range_s coord_range_t; 1889 struct coord_range_s { 1890 coord_value_t rmin, rmax; 1891 coord_range_t *prev, *next; 1892 coord_range_t *alloc_next; 1893 }; 1894 /* We declare coord_range_ts as simple because they only exist transiently. */ 1895 gs_private_st_simple(st_coord_range, coord_range_t, "coord_range_t"); 1896 1897 typedef struct coord_range_list_s { 1898 gs_memory_t *memory; 1899 struct rl_ { 1900 coord_range_t *first, *next, *limit; 1901 } local; 1902 coord_range_t *allocated; 1903 coord_range_t *freed; 1904 coord_range_t *current; 1905 coord_range_t first, last; 1906 } coord_range_list_t; 1907 1908 private coord_range_t * 1909 range_alloc(coord_range_list_t *pcrl) 1910 { 1911 coord_range_t *pcr; 1912 1913 if (pcrl->freed) { 1914 pcr = pcrl->freed; 1915 pcrl->freed = pcr->next; 1916 } else if (pcrl->local.next < pcrl->local.limit) 1917 pcr = pcrl->local.next++; 1918 else { 1919 pcr = gs_alloc_struct(pcrl->memory, coord_range_t, &st_coord_range, 1920 "range_alloc"); 1921 if (pcr == 0) 1922 return 0; 1923 pcr->alloc_next = pcrl->allocated; 1924 pcrl->allocated = pcr; 1925 } 1926 return pcr; 1927 } 1928 1929 private void 1930 range_delete(coord_range_list_t *pcrl, coord_range_t *pcr) 1931 { 1932 if_debug3('Q', "[Qr]delete 0x%lx: [%d,%d)\n", (ulong)pcr, pcr->rmin, 1933 pcr->rmax); 1934 pcr->prev->next = pcr->next; 1935 pcr->next->prev = pcr->prev; 1936 pcr->next = pcrl->freed; 1937 pcrl->freed = pcr; 1938 } 1939 1940 private void 1941 range_list_clear(coord_range_list_t *pcrl) 1942 { 1943 if_debug0('Q', "[Qr]clearing\n"); 1944 pcrl->first.next = &pcrl->last; 1945 pcrl->last.prev = &pcrl->first; 1946 pcrl->current = &pcrl->last; 1947 } 1948 1949 /* ------ "Public" procedures ------ */ 1950 1951 /* Initialize a range list. We require num_local >= 2. */ 1952 private void range_list_clear(coord_range_list_t *); 1953 private void 1954 range_list_init(coord_range_list_t *pcrl, coord_range_t *pcr_local, 1955 int num_local, gs_memory_t *mem) 1956 { 1957 pcrl->memory = mem; 1958 pcrl->local.first = pcrl->local.next = pcr_local; 1959 pcrl->local.limit = pcr_local + num_local; 1960 pcrl->allocated = pcrl->freed = 0; 1961 pcrl->first.rmin = pcrl->first.rmax = MIN_COORD_VALUE; 1962 pcrl->first.prev = 0; 1963 pcrl->last.rmin = pcrl->last.rmax = MAX_COORD_VALUE; 1964 pcrl->last.next = 0; 1965 range_list_clear(pcrl); 1966 } 1967 1968 /* Reset an initialized range list to the empty state. */ 1969 private void 1970 range_list_reset(coord_range_list_t *pcrl) 1971 { 1972 if (pcrl->first.next != &pcrl->last) { 1973 pcrl->last.prev->next = pcrl->freed; 1974 pcrl->freed = pcrl->first.next; 1975 range_list_clear(pcrl); 1976 } 1977 } 1978 1979 /* 1980 * Move the cursor to the beginning of a range list, in the belief that 1981 * the next added ranges will roughly parallel the existing ones. 1982 * (Only affects performance, not function.) 1983 */ 1984 inline private void 1985 range_list_rescan(coord_range_list_t *pcrl) 1986 { 1987 pcrl->current = pcrl->first.next; 1988 } 1989 1990 /* Free a range list. */ 1991 private void 1992 range_list_free(coord_range_list_t *pcrl) 1993 { 1994 coord_range_t *pcr; 1995 1996 while ((pcr = pcrl->allocated) != 0) { 1997 coord_range_t *next = pcr->alloc_next; 1998 1999 gs_free_object(pcrl->memory, pcr, "range_list_free"); 2000 pcrl->allocated = next; 2001 } 2002 } 2003 2004 /* Add a range. */ 2005 private int 2006 range_list_add(coord_range_list_t *pcrl, coord_value_t rmin, coord_value_t rmax) 2007 { 2008 coord_range_t *pcr = pcrl->current; 2009 2010 if (rmin >= rmax) 2011 return 0; 2012 /* 2013 * Usually, ranges are added in increasing order within each scan line, 2014 * and overlapping ranges don't differ much. Optimize accordingly. 2015 */ 2016 top: 2017 if (rmax < pcr->rmin) { 2018 if (rmin > pcr->prev->rmax) 2019 goto ins; 2020 pcr = pcr->prev; 2021 goto top; 2022 } 2023 if (rmin > pcr->rmax) { 2024 pcr = pcr->next; 2025 if (rmax < pcr->rmin) 2026 goto ins; 2027 goto top; 2028 } 2029 /* 2030 * Now we know that (rmin,rmax) overlaps (pcr->rmin,pcr->rmax). 2031 * Don't delete or merge into the special min and max ranges. 2032 */ 2033 while (rmin <= pcr->prev->rmax) { 2034 /* Merge the range below pcr into this one. */ 2035 if (!pcr->prev->prev) 2036 break; /* don't merge into the min range */ 2037 pcr->rmin = pcr->prev->rmin; 2038 range_delete(pcrl, pcr->prev); 2039 } 2040 while (rmax >= pcr->next->rmin) { 2041 /* Merge the range above pcr into this one. */ 2042 if (!pcr->next->next) 2043 break; /* don't merge into the max range */ 2044 pcr->rmax = pcr->next->rmax; 2045 range_delete(pcrl, pcr->next); 2046 } 2047 /* 2048 * Now we know that the union of (rmin,rmax) and (pcr->rmin,pcr->rmax) 2049 * doesn't overlap or abut either adjacent range, except that it may 2050 * abut if the adjacent range is the special min or max range. 2051 */ 2052 if (rmin < pcr->rmin) { 2053 if_debug3('Q', "[Qr]update 0x%lx => [%d,%d)\n", (ulong)pcr, rmin, 2054 pcr->rmax); 2055 pcr->rmin = rmin; 2056 } 2057 if (rmax > pcr->rmax) { 2058 if_debug3('Q', "[Qr]update 0x%lx => [%d,%d)\n", (ulong)pcr, pcr->rmin, 2059 rmax); 2060 pcr->rmax = rmax; 2061 } 2062 pcrl->current = pcr->next; 2063 return 0; 2064 ins: 2065 /* Insert a new range below pcr. */ 2066 { 2067 coord_range_t *prev = range_alloc(pcrl); 2068 2069 if (prev == 0) 2070 return_error(gs_error_VMerror); 2071 if_debug3('Q', "[Qr]insert 0x%lx: [%d,%d)\n", (ulong)prev, rmin, rmax); 2072 prev->rmin = rmin, prev->rmax = rmax; 2073 (prev->prev = pcr->prev)->next = prev; 2074 prev->next = pcr; 2075 pcr->prev = prev; 2076 } 2077 pcrl->current = pcr; 2078 return 0; 2079 } 2080 2081 /* 2082 * Merge regions for active segments starting at a given Y, or all active 2083 * segments, up to the end of the sampling band or the end of the segment, 2084 * into the range list. 2085 */ 2086 private int 2087 merge_ranges(coord_range_list_t *pcrl, const line_list *ll, fixed y_min, fixed y_top) 2088 { 2089 active_line *alp, *nlp; 2090 int code = 0; 2091 2092 range_list_rescan(pcrl); 2093 for (alp = ll->x_list; alp != 0 && code >= 0; alp = nlp) { 2094 fixed x0 = alp->x_current, x1, xt; 2095 2096 nlp = alp->next; 2097 if (alp->start.y < y_min) 2098 continue; 2099 if (alp->monotonic_x && alp->monotonic_y && alp->fi.y3 <= y_top) { 2100 vd_bar(alp->start.x, alp->start.y, alp->end.x, alp->end.y, 0, RGB(255, 0, 0)); 2101 x1 = alp->fi.x3; 2102 if (x0 > x1) 2103 xt = x0, x0 = x1, x1 = xt; 2104 code = range_list_add(pcrl, 2105 fixed2int_pixround(x0 - ll->fo->adjust_left), 2106 fixed2int_rounded(x1 + ll->fo->adjust_right)); 2107 alp->more_flattened = false; /* Skip all the segments left. */ 2108 } else { 2109 x1 = x0; 2110 for (;;) { 2111 if (alp->end.y <= y_top) 2112 xt = alp->end.x; 2113 else 2114 xt = AL_X_AT_Y(alp, y_top); 2115 x0 = min(x0, xt); 2116 x1 = max(x1, xt); 2117 if (!alp->more_flattened || alp->end.y > y_top) 2118 break; 2119 step_al(alp, true); 2120 if (alp->end.y < alp->start.y) { 2121 remove_al(ll, alp); /* End of a monotonic part of a curve. */ 2122 break; 2123 } 2124 } 2125 code = range_list_add(pcrl, 2126 fixed2int_pixround(x0 - ll->fo->adjust_left), 2127 fixed2int_rounded(x1 + ll->fo->adjust_right)); 2128 } 2129 2130 } 2131 return code; 2132 } 2133 2134 /* ---------------- Scan line filling loop ---------------- */ 2135 2136 /* defina specializations of the scanline algorithm. */ 2137 2138 #define FILL_DIRECT 1 2139 #define TEMPLATE_spot_into_scanlines spot_into_scan_lines_fd 2140 #include "gxfillsl.h" 2141 #undef FILL_DIRECT 2142 #undef TEMPLATE_spot_into_scanlines 2143 2144 #define FILL_DIRECT 0 2145 #define TEMPLATE_spot_into_scanlines spot_into_scan_lines_nd 2146 #include "gxfillsl.h" 2147 #undef FILL_DIRECT 2148 #undef TEMPLATE_spot_into_scanlines 2149 2150 private int 2151 spot_into_scan_lines(line_list *ll, fixed band_mask) 2152 { 2153 if (ll->fo->fill_direct) 2154 return spot_into_scan_lines_fd(ll, band_mask); 2155 else 2156 return spot_into_scan_lines_nd(ll, band_mask); 2157 } 2158 2159