1/*********************************************************************** 2 * * 3 * $Id: hpgsscanline.c 374 2007-01-24 15:57:52Z softadm $ 4 * * 5 * hpgs - HPGl Script, a hpgl/2 interpreter, which uses a Postscript * 6 * API for rendering a scene and thus renders to a variety of * 7 * devices and fileformats. * 8 * * 9 * (C) 2004-2006 ev-i Informationstechnologie GmbH http://www.ev-i.at * 10 * * 11 * Author: Wolfgang Glas * 12 * * 13 * hpgs is free software; you can redistribute it and/or * 14 * modify it under the terms of the GNU Lesser General Public * 15 * License as published by the Free Software Foundation; either * 16 * version 2.1 of the License, or (at your option) any later version. * 17 * * 18 * hpgs is distributed in the hope that it will be useful, * 19 * but WITHOUT ANY WARRANTY; without even the implied warranty of * 20 * MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the GNU * 21 * Lesser General Public License for more details. * 22 * * 23 * You should have received a copy of the GNU Lesser General Public * 24 * License along with this library; if not, write to the * 25 * Free Software Foundation, Inc., 59 Temple Place, Suite 330, * 26 * Boston, MA 02111-1307 USA * 27 * * 28 *********************************************************************** 29 * * 30 * The implementation of the API for scanline handling. * 31 * * 32 ***********************************************************************/ 33 34#include<hpgspaint.h> 35#include<math.h> 36#include<string.h> 37#if defined ( __MINGW32__ ) || defined ( _MSC_VER ) 38#include<malloc.h> 39#else 40#include<alloca.h> 41#endif 42 43//#define HPGS_DEBUG_CUT 44//#define HPGS_DEBUG_THIN_CUT 45//#define HPGS_DEBUG_ALPHA_CUT 46//#define HPGS_DEBUG_EMIT_ALPHA 47//#define HPGS_DEBUG_EMIT_0 48//#define HPGS_DEBUG_CLIP 49 50static int hpgs_paint_scanline_add_point(hpgs_paint_scanline *s, double x, int o); 51static int hpgs_paint_scanline_add_slope(hpgs_paint_scanline *s, double x1, double x2, int o1, int o2); 52 53/*! \defgroup scanline scanline handling. 54 55 This module contains the documentation of the internals 56 of the vector graphics renderer \c hpgs_paint_device. 57 58 The dcomumentation of \c hpgs_paint_clipper_st explains the 59 concepts used throughout the implementation of the objects 60 in this module. 61*/ 62 63/*! 64 Initializes the given scanline structure for the given initial size \c msize 65 of intersection points. The minimal value of \c msize is 4. 66 67 Return value: 68 \li 0 Success. 69 \li -1 The system is out of memory. 70*/ 71static int hpgs_paint_scanline_init(hpgs_paint_scanline *s, int msize) 72{ 73 s->points_malloc_size = msize < 4 ? 4 : msize; 74 s->n_points = 0; 75 s->points = (hpgs_scanline_point *)malloc(sizeof(hpgs_scanline_point)*s->points_malloc_size); 76 77 return s->points ? 0 : -1; 78} 79 80/*! 81 Frees the vector of of intersection points of the given scanline. 82*/ 83static void hpgs_paint_scanline_cleanup(hpgs_paint_scanline *s) 84{ 85 if (s->points) 86 free(s->points); 87} 88 89/* Internal: 90 Adds an edge of a path to the given scanline. 91 92 \c order 1 is the intersection order 93 (1 upwards, 0 horizontal, -1 downwards) 94 of the path segment before the given edge point. 95 96 \c order2 is the intersection order 97 of the path segment after the given edge point. 98 99 If the two orders are of a different sign ((1,-1) or (-1,1)), 100 the edge is inserted twice with an opposite sign in order to draw 101 line segments of width 0. 102 103 Return value: 104 \li 0 Success. 105 \li -1 The system is out of memory. 106*/ 107static int add_edge(hpgs_paint_scanline *s, 108 hpgs_path_point *point, 109 int order1, int order2) 110{ 111#ifdef HPGS_DEBUG_CUT 112 hpgs_log("add_edge: x,y,o1,o2 = %lg,%lg,%d,%d.\n", 113 point->p.x,point->p.y,order1,order2); 114#endif 115 if (order1+order2 > 0) 116 { 117 if (hpgs_paint_scanline_add_point(s,point->p.x,1)) 118 return -1; 119 } 120 else if (order1+order2 < 0) 121 { 122 if (hpgs_paint_scanline_add_point(s,point->p.x,-1)) 123 return -1; 124 } 125 else 126 if (order1 > 0) 127 { 128 if (hpgs_paint_scanline_add_point(s,point->p.x,1) || 129 hpgs_paint_scanline_add_point(s,point->p.x,-1) ) 130 return -1; 131 } 132 else if (order1 < 0) 133 { 134 if (hpgs_paint_scanline_add_point(s,point->p.x,-1) || 135 hpgs_paint_scanline_add_point(s,point->p.x,1) ) 136 return -1; 137 } 138 139 return 0; 140} 141 142/* Internal: 143 Sorts the intersection points of the the given scanline 144 using merge sort. Merge sort is used in order to preserve 145 the order of two equal x positions with opposite sign. 146 (see add_egde above) 147 148 As a side effect, this approach is ways faster than qsort(). 149 150 Internal routine. Driver routine below. 151*/ 152static void scanline_msort(hpgs_scanline_point *a, int n, 153 hpgs_scanline_point *res, 154 hpgs_scanline_point *tmp ) 155{ 156 int n1 = n/2; 157 int n2 = n - n1; 158 hpgs_scanline_point *b=a+n1; 159 hpgs_scanline_point *te=tmp+n1; 160 hpgs_scanline_point *be=a+n; 161 162 // sort first half of a into tmp. 163 switch (n1) 164 { 165 case 1: 166 *tmp = *a; 167 case 0: 168 break; 169 default: 170 scanline_msort(a,n1,tmp,te); 171 } 172 173 // sort second half of a (aka b) in place. 174 if (n2 > 1) 175 scanline_msort(b,n2,b,te); 176 177 // now merge the results. 178 while (tmp < te && b < be) 179 { 180 // stable sort characteristics: prefer first half. 181 if (tmp->x <= b->x) 182 *res = *tmp++; 183 else 184 *res = *b++; 185 186 ++res; 187 } 188 189 // copy rest of first sorted half 190 while (tmp < te) 191 *res++ = *tmp++; 192 193 // copy rest of second half, if not co-located 194 if (res!=b) 195 while (b < be) 196 *res++ = *b++; 197} 198 199/* Internal: 200 Sorts the intersection points of the the given scanline 201 using merge sort. Internal subroutine and docs above. 202*/ 203static void scanline_sort (hpgs_scanline_point *a, int n) 204{ 205 hpgs_scanline_point *tmp = hpgs_alloca(sizeof(hpgs_scanline_point) * n); 206 207 scanline_msort(a,n,a,tmp); 208} 209 210/* Internal: 211 Cuts the bezier segment with the scanlines of the clipper. 212 213 Returns the scanline number of the endpoint hit or -1, 214 if endpoint is not an exact hit. 215 216 Upon memory error return -2; 217*/ 218 219static int bezier_clipper_cut (hpgs_paint_clipper *c, 220 hpgs_paint_path *path, int i, 221 double t0, double t1, 222 double y0, 223 double y1, 224 double y2, 225 double y3 ) 226{ 227 double ymin0 = (y0 < y1) ? y0 : y1; 228 double ymin1 = (y2 < y3) ? y2 : y3; 229 double ymin = ymin0<ymin1 ? ymin0 : ymin1; 230 231 double ymax0 = (y0 > y1) ? y0 : y1; 232 double ymax1 = (y2 > y3) ? y2 : y3; 233 double ymax = ymax0>ymax1 ? ymax0 : ymax1; 234 235 double dscan0 = (c->y0 - ymax)/c->yfac; 236 double dscan1 = (c->y0 - ymin)/c->yfac; 237 238 double rdscan0 = ceil(dscan0); 239 double rdscan1 = floor(dscan1); 240 241 int iscan0 = (int)rdscan0; 242 int iscan1 = (int)rdscan1; 243 244 if (iscan0 > iscan1 || iscan1 < 0 || iscan0 >= c->n_scanlines) 245 { 246 return -1; 247 } 248 else if (t1-t0 < 1.0e-8 && iscan0 == iscan1) 249 { 250 int o0; 251 252 if (y1 > y0) o0 = 1; 253 else if (y1 < y0) o0 = -1; 254 else if (y2 > y0) o0 = 1; 255 else if (y2 < y0) o0 = -1; 256 else if (y3 > y0) o0 = 1; 257 else if (y3 < y0) o0 = -1; 258 else o0 = 0; 259 260 int o1; 261 262 if (y2 > y3) o1 = -1; 263 else if (y2 < y3) o1 = 1; 264 else if (y1 > y3) o1 = -1; 265 else if (y1 < y3) o1 = 1; 266 else if (y0 > y3) o1 = -1; 267 else if (y0 < y3) o1 = 1; 268 else o1 = 0; 269 270 // horizontal cut. 271 if (o0*o1 == 0) 272 { 273 return -1; 274 } 275 276 // filter out startpoint hit. 277 if (t0 == -0.5 && 278 ((y0 == ymin && dscan1 == rdscan1) || 279 (y0 == ymax && dscan0 == rdscan0) )) return -1; 280 281 // filter out endpoint hit. 282 if (t1 == 0.5 && 283 ((y3 == ymin && dscan1 == rdscan1) || 284 (y3 == ymax && dscan0 == rdscan0) )) return iscan0; 285 286 if (iscan0 < c->iscan0) c->iscan0 = iscan0; 287 if (iscan0 > c->iscan1) c->iscan1 = iscan0; 288 289 if (o0*o1 > 0) 290 { 291 if (hpgs_paint_scanline_add_point(c->scanlines+iscan0, 292 hpgs_bezier_path_x(path,i,0.5*(t0+t1)), 293 o0)) 294 return -2; 295 296 return -1; 297 } 298 else 299 { 300 if (hpgs_paint_scanline_add_point(c->scanlines+iscan0, 301 hpgs_bezier_path_x(path,i,t0), 302 o0)) 303 return -2; 304 305 if (hpgs_paint_scanline_add_point(c->scanlines+iscan0, 306 hpgs_bezier_path_x(path,i,t1), 307 o1)) 308 return -2; 309 310 return -1; 311 } 312 } 313 else if (t1-t0 < 1.0e-15) 314 { 315 return -1; 316 } 317 else 318 { 319 // partition the spline. 320 double tmid = 0.5*(t0+t1); 321 322 // midpoint. 323 double ymid,y1l,y2l,y1u,y2u; 324 325 y1l = 0.5 * (y0 + y1); 326 327 y2l = 0.25 * (y0 + y2) + 0.5 * y1; 328 329 ymid = 330 (y0 + y3) * 0.125 + 0.375 * (y1 + y2); 331 332 y1u = 0.25 * (y1 + y3) + 0.5 * y2; 333 334 y2u = 0.5 * (y2 + y3); 335 336 if (bezier_clipper_cut (c,path,i,t0,tmid,y0,y1l,y2l,ymid) < -1) 337 return -2; 338 339 return bezier_clipper_cut (c,path,i,tmid,t1,ymid,y1u,y2u,y3); 340 } 341} 342 343/*! 344 Cuts te given \c path with the scanlines of the given 345 clipper \c c. If you emit the clipper afterwards, the interior 346 of the given path is drawn to the image. 347 348 If you want to stroke the path use either \c hpgs_paint_clipper_thin_cut 349 for thin lines or contruct the outline of a thick line using 350 the line style of a graphics state with \c hpgs_paint_path_stroke_path. 351 352 Return value: 353 \li 0 Success. 354 \li -1 The system is out of memory. 355*/ 356static int hpgs_paint_clipper_cut_0(hpgs_paint_clipper *c, 357 hpgs_paint_path *path) 358{ 359 int i; 360 int start_order=0,last_order=0; 361 hpgs_path_point *deferred_edge_cut = 0; 362 int deferred_edge_cut_is = -1; 363 int iscan; 364 365 // catch path' which lie outside of the area of interest. 366 if (path->bb.urx < c->bb.llx) return 0; 367 if (path->bb.llx > c->bb.urx) return 0; 368 if (path->bb.ury < c->bb.lly) return 0; 369 if (path->bb.lly > c->bb.ury) return 0; 370 371 for (i=0;i<path->n_points;++i) 372 { 373 hpgs_path_point *point = &path->points[i]; 374 hpgs_path_point *next_point; 375 hpgs_path_point *next_edge_cut=0; 376 int next_edge_cut_is=-1; 377 378 int order1 = 0; 379 int order2 = 0; 380 int iscan0,iscan1; 381 382 switch (point->flags & HPGS_POINT_ROLE_MASK) 383 { 384 case HPGS_POINT_LINE: 385 case HPGS_POINT_FILL_LINE: 386 { 387 next_point = &path->points[i+1]; 388 389 double dscan0 = (c->y0 - point->p.y)/c->yfac; 390 double dscan1 = (c->y0 - next_point->p.y)/c->yfac; 391 392#ifdef HPGS_DEBUG_CUT 393 hpgs_log("cut_line: x1,y1,x2,y2 = %lg,%lg,%lg,%lg.\n", 394 point->p.x,point->p.y,next_point->p.x,next_point->p.y); 395#endif 396 397 398 if (dscan0 < dscan1) 399 { 400 double rdscan0 = ceil(dscan0); 401 double rdscan1 = floor(dscan1); 402 403 iscan0 = (int)rdscan0; 404 iscan1 = (int)rdscan1; 405 406 // startpoint hit 407 if (rdscan0 == dscan0) 408 ++iscan0; 409 410 // endpoint hit 411 if (rdscan1 == dscan1) 412 { 413 if (iscan1 >= 0 && iscan1 < c->n_scanlines) 414 { 415 next_edge_cut = next_point; 416 next_edge_cut_is = iscan1; 417 } 418 --iscan1; 419 } 420 } 421 else 422 { 423 double rdscan0 = ceil(dscan1); 424 double rdscan1 = floor(dscan0); 425 426 iscan0 = (int)rdscan0; 427 iscan1 = (int)rdscan1; 428 429 // startpoint hit 430 if (rdscan1 == dscan1) 431 --iscan1; 432 433 // endpoint hit 434 if (rdscan0 == dscan0) 435 { 436 if (iscan0 >= 0 && iscan0 < c->n_scanlines) 437 { 438 next_edge_cut = next_point; 439 next_edge_cut_is = iscan0; 440 } 441 ++iscan0; 442 } 443 } 444 445 if (iscan0 < 0) iscan0 = 0; 446 if (iscan1 >= c->n_scanlines) iscan1 = c->n_scanlines-1; 447 448 if (iscan0 < c->iscan0) c->iscan0 = iscan0; 449 if (iscan1 > c->iscan1) c->iscan1 = iscan1; 450 451 if (next_point->p.y > point->p.y) 452 order1 = 1; 453 else if (next_point->p.y < point->p.y) 454 order1 = -1; 455 else 456 order1 = 0; 457 458 order2 = order1; 459 460 if (point->p.x != next_point->p.x) 461 for (iscan=iscan0;iscan<=iscan1;++iscan) 462 { 463 double y = c->y0 - iscan * c->yfac; 464 double x = 465 (point->p.x * (next_point->p.y - y) + 466 next_point->p.x * (y - point->p.y) ) / 467 (next_point->p.y - point->p.y); 468 469 if (hpgs_paint_scanline_add_point(c->scanlines+iscan,x,order1)) 470 return -1; 471 } 472 else 473 for (iscan=iscan0;iscan<=iscan1;++iscan) 474 { 475 if (hpgs_paint_scanline_add_point(c->scanlines+iscan, 476 point->p.x,order1)) 477 return -1; 478 } 479 } 480 break; 481 case HPGS_POINT_BEZIER: 482 next_point = &path->points[i+3]; 483 484#ifdef HPGS_DEBUG_CUT 485 hpgs_log("cut_bezier: x1,y1,x4,y4 = %lg,%lg,%lg,%lg.\n", 486 point->p.x,point->p.y,next_point->p.x,next_point->p.y); 487#endif 488 489 if (path->points[i+1].p.y > point->p.y) 490 order1 = 1; 491 else if (path->points[i+1].p.y < point->p.y) 492 order1 = -1; 493 else if (path->points[i+2].p.y > point->p.y) 494 order1 = 1; 495 else if (path->points[i+2].p.y < point->p.y) 496 order1 = -1; 497 else if (next_point->p.y > point->p.y) 498 order1 = 1; 499 else if (next_point->p.y < point->p.y) 500 order1 = -1; 501 else 502 order1 = 0; 503 504 if (path->points[i+2].p.y < next_point->p.y) 505 order2 = 1; 506 else if (path->points[i+2].p.y > next_point->p.y) 507 order2 = -1; 508 else if (path->points[i+1].p.y < next_point->p.y) 509 order2 = 1; 510 else if (path->points[i+1].p.y > next_point->p.y) 511 order2 = -1; 512 else if (point->p.y < next_point->p.y) 513 order2 = 1; 514 else if (point->p.y > next_point->p.y) 515 order2 = -1; 516 else 517 order2 = 0; 518 519 iscan1 = bezier_clipper_cut (c,path,i,-0.5,0.5, 520 point->p.y, 521 path->points[i+1].p.y, 522 path->points[i+2].p.y, 523 next_point->p.y ); 524 525 if (iscan1 < -1) return -1; 526 527 if (iscan1 >= 0 && iscan1 < c->n_scanlines) 528 { 529 next_edge_cut = next_point; 530 next_edge_cut_is = iscan1; 531 } 532 533 // ignore control points. 534 i+=2; 535 break; 536 } 537 538 if (point->flags & HPGS_POINT_SUBPATH_END) 539 { 540 if (deferred_edge_cut) 541 if (add_edge(c->scanlines+deferred_edge_cut_is, 542 deferred_edge_cut,last_order,start_order)) 543 return -1; 544 } 545 else 546 { 547 if (deferred_edge_cut) 548 if (add_edge(c->scanlines+deferred_edge_cut_is, 549 deferred_edge_cut,last_order,order1)) 550 return -1; 551 } 552 553 if (point->flags & HPGS_POINT_SUBPATH_START) 554 start_order = order1; 555 556 last_order = order2; 557 deferred_edge_cut = next_edge_cut; 558 deferred_edge_cut_is = next_edge_cut_is; 559 } 560 561 if (deferred_edge_cut) 562 if (add_edge(c->scanlines+deferred_edge_cut_is, 563 deferred_edge_cut,last_order,start_order)) 564 return -1; 565 566 // search for minimal figures, which did not hit any scanline 567 // (horizontal fills with a height below 1 pixel...). 568 if (c->iscan0 > c->iscan1 && path->n_points) 569 { 570 iscan = (int)floor((c->y0 - 0.5 * (path->bb.lly + path->bb.ury))/c->yfac + 0.5); 571 572#ifdef HPGS_DEBUG_CUT 573 hpgs_log("cut_minimal: llx,lly,urx,ury,iscan,n = %lg,%lg,%lg,%lg.\n", 574 path->bb.llx,path->bb.lly,path->bb.urx,path->bb.ury); 575#endif 576 577 if (iscan < 0 || iscan >= c->n_scanlines) return 0; 578 579 c->iscan0 = c->iscan1 = iscan; 580 581 if (hpgs_paint_scanline_add_point(c->scanlines+iscan,path->bb.llx,1) || 582 hpgs_paint_scanline_add_point(c->scanlines+iscan,path->bb.urx,-1) ) 583 return -1; 584 585 return 0; 586 } 587 588 for (iscan = c->iscan0;iscan<=c->iscan1;++iscan) 589 { 590 scanline_sort(c->scanlines[iscan].points,c->scanlines[iscan].n_points); 591#ifdef HPGS_DEBUG_CUT 592 { 593 int j; 594 595 hpgs_log("iscan = %d, np = %d ****************************************\n", 596 iscan,c->scanlines[iscan].n_points); 597 598 if (c->scanlines[iscan].n_points & 1) 599 hpgs_log("np odd !!!!!!!!!!!!!!!\n"); 600 601 for (j=0;j<c->scanlines[iscan].n_points;++j) 602 hpgs_log("%lg(%d) ", 603 c->scanlines[iscan].points[j].x, 604 c->scanlines[iscan].points[j].order); 605 606 hpgs_log("\n"); 607 } 608#endif 609 } 610 611 return 0; 612} 613 614/* Internal: 615 Cuts the bezier segment with the scanlines of the clipper 616 as for thin lines. 617 618 Returns 0 upon success or -1 on memory error. 619*/ 620 621typedef struct hpgs_bezier_clipper_thin_cut_data_st hpgs_bezier_clipper_thin_cut_data; 622 623struct hpgs_bezier_clipper_thin_cut_data_st 624{ 625 hpgs_paint_clipper *c; 626 hpgs_paint_path *path; 627 int i; 628 629 double t0; 630 double t1; 631 632 double t_last; 633 double x_last; 634 int iscan_last; 635}; 636 637static int hpgs_bezier_clipper_thin_cut_data_push(hpgs_bezier_clipper_thin_cut_data *d, 638 double t, double x, int iscan, int o) 639{ 640 if (d->iscan_last >= 0 && d->iscan_last < d->c->n_scanlines) 641 { 642 if (d->iscan_last < d->c->iscan0) 643 d->c->iscan0 = d->iscan_last; 644 645 if (d->iscan_last > d->c->iscan1) 646 d->c->iscan1 = d->iscan_last; 647 648 int order = x > d->x_last ? 1 : -1; 649 650 if (hpgs_paint_scanline_add_point(d->c->scanlines+d->iscan_last,d->x_last,order)) 651 return -1; 652 653 if (hpgs_paint_scanline_add_point(d->c->scanlines+d->iscan_last,x,-order)) 654 return -1; 655 } 656 657 if (o > 0) 658 d->iscan_last = iscan; 659 else 660 d->iscan_last = iscan+1; 661 662 d->x_last = x; 663 d->t_last = t; 664 665 return 0; 666} 667 668static int bezier_clipper_thin_cut (hpgs_bezier_clipper_thin_cut_data *d, 669 double t0, double t1, 670 double y0, 671 double y1, 672 double y2, 673 double y3 ) 674{ 675 double ymin0 = (y0 < y1) ? y0 : y1; 676 double ymin1 = (y2 < y3) ? y2 : y3; 677 double ymin = ymin0<ymin1 ? ymin0 : ymin1; 678 679 double ymax0 = (y0 > y1) ? y0 : y1; 680 double ymax1 = (y2 > y3) ? y2 : y3; 681 double ymax = ymax0>ymax1 ? ymax0 : ymax1; 682 683 double dscan0 = (d->c->y0 - ymax)/d->c->yfac - 0.5; 684 double dscan1 = (d->c->y0 - ymin)/d->c->yfac - 0.5; 685 686 double rdscan0 = ceil(dscan0); 687 double rdscan1 = floor(dscan1); 688 689 int iscan0 = (int)rdscan0; 690 int iscan1 = (int)rdscan1; 691 692 if (iscan0 > iscan1 || iscan1 < -1 || iscan0 >= d->c->n_scanlines) 693 { 694 return 0; 695 } 696 else if (t1-t0 < 1.0e-8 && iscan0 == iscan1) 697 { 698 int o0; 699 700 if (y1 > y0) o0 = 1; 701 else if (y1 < y0) o0 = -1; 702 else if (y2 > y0) o0 = 1; 703 else if (y2 < y0) o0 = -1; 704 else if (y3 > y0) o0 = 1; 705 else if (y3 < y0) o0 = -1; 706 else o0 = 0; 707 708 int o1; 709 710 if (y2 > y3) o1 = -1; 711 else if (y2 < y3) o1 = 1; 712 else if (y1 > y3) o1 = -1; 713 else if (y1 < y3) o1 = 1; 714 else if (y0 > y3) o1 = -1; 715 else if (y0 < y3) o1 = 1; 716 else o1 = 0; 717 718 // horizontal cut. 719 if (o0*o1 == 0) 720 { 721 return 0; 722 } 723 724 // filter out startpoint hit. 725 if (t0 == d->t0 && 726 ((y0 == ymin && dscan1 == rdscan1) || 727 (y0 == ymax && dscan0 == rdscan0) )) return 0; 728 729 // filter out endpoint hit. 730 if (t1 == d->t1 && 731 ((y3 == ymin && dscan1 == rdscan1) || 732 (y3 == ymax && dscan0 == rdscan0) )) return 0; 733 734 if (iscan0 < d->c->iscan0) 735 { 736 if (iscan0 < 0) 737 d->c->iscan0 = 0; 738 else 739 d->c->iscan0 = iscan0; 740 } 741 742 if (iscan0 >= d->c->iscan1) 743 { 744 if (iscan0+1 >= d->c->n_scanlines) 745 d->c->iscan1 = d->c->n_scanlines-1; 746 else 747 d->c->iscan1 = iscan0+1; 748 } 749 750 if (o0*o1 > 0) 751 { 752 double t = 0.5*(t0+t1); 753 double x = hpgs_bezier_path_x(d->path,d->i,t); 754 755 return hpgs_bezier_clipper_thin_cut_data_push(d,t,x,iscan0,o0); 756 } 757 else 758 { 759 double x0 = hpgs_bezier_path_x(d->path,d->i,t0); 760 double x1 = hpgs_bezier_path_x(d->path,d->i,t1); 761 762 if (hpgs_bezier_clipper_thin_cut_data_push(d,t0,x0,iscan0,o0)) 763 return -1; 764 765 return hpgs_bezier_clipper_thin_cut_data_push(d,t1,x1,iscan0,o1); 766 } 767 } 768 else if (t1-t0 < 1.0e-15) 769 { 770 return 0; 771 } 772 else 773 { 774 // partition the spline. 775 double tmid = 0.5*(t0+t1); 776 777 // midpoint. 778 double ymid,y1l,y2l,y1u,y2u; 779 780 y1l = 0.5 * (y0 + y1); 781 782 y2l = 0.25 * (y0 + y2) + 0.5 * y1; 783 784 ymid = 785 (y0 + y3) * 0.125 + 0.375 * (y1 + y2); 786 787 y1u = 0.25 * (y1 + y3) + 0.5 * y2; 788 789 y2u = 0.5 * (y2 + y3); 790 791 if (bezier_clipper_thin_cut (d,t0,tmid,y0,y1l,y2l,ymid)) 792 return -1; 793 794 if (bezier_clipper_thin_cut (d,tmid,t1,ymid,y1u,y2u,y3)) 795 return -1; 796 797 return 0; 798 } 799} 800 801static int thin_push_dot(hpgs_paint_clipper *c, const hpgs_point *p) 802{ 803 int iscan = floor((c->y0 - p->y)/c->yfac + 0.5); 804 805 if (iscan < 0 || iscan >= c->n_scanlines) return 0; 806 807#ifdef HPGS_DEBUG_CUT 808 hpgs_log("push_dot: x,y,iscan = %lg,%lg,%d.\n", 809 p->x,p->y,iscan); 810#endif 811 812 if (hpgs_paint_scanline_add_point(c->scanlines+iscan,p->x,1) || 813 hpgs_paint_scanline_add_point(c->scanlines+iscan,p->x,-1) ) 814 return -1; 815 816 if (iscan < c->iscan0) c->iscan0 = iscan; 817 if (iscan > c->iscan1) c->iscan1 = iscan; 818 return 0; 819} 820 821/* Internal: 822 Cut a part of a path with a linewidth below the width of a pixel with 823 the scanlines of the given clipper \c c. 824 825 The subpath starts at the path segment starting at point \c i0 at the 826 curve parameter \c t0 (t=-0.5 start of segment, t=0.5 end of segment). 827 828 The scanline ends at the path segment starting at point \c i1 at the 829 curve parameter \c t1. 830 831 The actual intersections are undertaken at an y value in the middle between 832 the two y values of adjacent scanlines. The actual intersection points with 833 this intermediate scanline is inserted twice, once in the adjacent scanline 834 above and below the intermediate scanline. 835*/ 836static int thin_cut_segment(hpgs_paint_clipper *c, 837 hpgs_paint_path *path, 838 int i0, double t0, 839 int i1, double t1 ) 840{ 841 int i; 842 int iscan; 843 844 for (i=i0;i<=i1;++i) 845 { 846 hpgs_path_point *point = &path->points[i]; 847 hpgs_path_point *next_point; 848 double x0,x1,y0,y1; 849 int iscan0,iscan1,order; 850 851 double tt0 = (i == i0) ? t0 : -0.5; 852 double tt1 = (i == i1) ? t1 : 0.5; 853 854 switch (point->flags & HPGS_POINT_ROLE_MASK) 855 { 856 case HPGS_POINT_DOT: 857 if (thin_push_dot(c,&path->points[i].p)) return -1; 858 break; 859 860 case HPGS_POINT_LINE: 861 next_point = &path->points[i+1]; 862 863 if (tt0 > -0.5) 864 { 865 x0 = (0.5 - tt0) * point->p.x + (0.5 + tt0) * next_point->p.x; 866 y0 = (0.5 - tt0) * point->p.y + (0.5 + tt0) * next_point->p.y; 867 } 868 else 869 { 870 x0 = point->p.x; 871 y0 = point->p.y; 872 } 873 874 if (tt1 < 0.5) 875 { 876 x1 = (0.5 - tt1) * point->p.x + (0.5 + tt1) * next_point->p.x; 877 y1 = (0.5 - tt1) * point->p.y + (0.5 + tt1) * next_point->p.y; 878 } 879 else 880 { 881 x1 = next_point->p.x; 882 y1 = next_point->p.y; 883 } 884 885 order = x1 < x0 ? -1 : 1; 886 887 iscan0 = 888 (int)floor((c->y0 - y0)/c->yfac + 0.5); 889 iscan1 = 890 (int)floor((c->y0 - y1)/c->yfac + 0.5); 891 892 if (iscan0 >= 0 && iscan0 < c->n_scanlines && 893 hpgs_paint_scanline_add_point(c->scanlines+iscan0,x0,order)) 894 return -1; 895 896 if (iscan1 >= 0 && iscan1 < c->n_scanlines && 897 hpgs_paint_scanline_add_point(c->scanlines+iscan1,x1,-order)) 898 return -1; 899 900 if (iscan0 > iscan1) 901 { int tmp = iscan0; iscan0 = iscan1; iscan1 = tmp; order = -order; } 902 903 if (iscan0 < 0) 904 { 905 iscan0 = -1; 906 c->iscan0 = 0; 907 } 908 else 909 if (iscan0 < c->iscan0) 910 c->iscan0 = iscan0; 911 912 if (iscan1 >= c->n_scanlines) 913 { 914 iscan1 = c->n_scanlines; 915 c->iscan1 = c->n_scanlines-1; 916 } 917 else 918 if (iscan1 > c->iscan1) 919 c->iscan1 = iscan1; 920 921 if (point->p.x != next_point->p.x) 922 for (iscan=iscan0;iscan<iscan1;++iscan) 923 { 924 double y = c->y0 - (iscan + 0.5) * c->yfac; 925 926 double x = 927 (point->p.x * (next_point->p.y - y) + 928 next_point->p.x * (y - point->p.y) ) / 929 (next_point->p.y - point->p.y); 930 931 if (iscan >= 0 && 932 hpgs_paint_scanline_add_point(c->scanlines+iscan,x,-order)) 933 return -1; 934 935 if (iscan < c->n_scanlines-1 && 936 hpgs_paint_scanline_add_point(c->scanlines+iscan+1,x,order)) 937 return -1; 938 } 939 else 940 for (iscan=iscan0;iscan<iscan1;++iscan) 941 { 942 if (iscan >= 0 && 943 hpgs_paint_scanline_add_point(c->scanlines+iscan, 944 point->p.x,-order)) 945 return -1; 946 947 if (iscan < c->n_scanlines-1 && 948 hpgs_paint_scanline_add_point(c->scanlines+iscan+1, 949 point->p.x,order)) 950 return -1; 951 } 952 953 break; 954 case HPGS_POINT_BEZIER: 955 next_point = &path->points[i+3]; 956 957 { 958 double yc0,yc1; 959 960 // start point. 961 if (tt0 > -0.5) 962 { 963 x0 = hpgs_bezier_path_x(path,i,tt0); 964 y0 = hpgs_bezier_path_y(path,i,tt0); 965 } 966 else 967 { 968 x0 = point->p.x; 969 y0 = point->p.y; 970 } 971 972 973 // end point 974 if (tt1 < 0.5) 975 { 976 x1 = hpgs_bezier_path_x(path,i,tt1); 977 y1 = hpgs_bezier_path_y(path,i,tt1); 978 } 979 else 980 { 981 x1 = next_point->p.x; 982 y1 = next_point->p.y; 983 } 984 985 // control points 986 if (tt0 > -0.5 || tt1 < 0.5) 987 { 988 yc0 = y0 + (tt1-tt0) * hpgs_bezier_path_delta_y(path,i,tt0)/3.0; 989 yc1 = y1 - (tt1-tt0) * hpgs_bezier_path_delta_y(path,i,tt1)/3.0; 990 } 991 else 992 { 993 yc0 = path->points[i+1].p.y; 994 yc1 = path->points[i+2].p.y; 995 } 996 997 hpgs_bezier_clipper_thin_cut_data d = 998 { c,path,i,tt0,tt1,tt0,x0, 999 (int)floor((c->y0 - y0)/c->yfac + 0.5) }; 1000 1001 if (bezier_clipper_thin_cut (&d,tt0,tt1,y0,yc0,yc1,y1)) 1002 return -1; 1003 1004 // add endpoint with appropriate order. 1005 if (d.iscan_last >= 0 && d.iscan_last < c->n_scanlines) 1006 { 1007 int order = x1 > d.x_last ? 1 : -1; 1008 1009 if (d.iscan_last < c->iscan0) 1010 c->iscan0 = d.iscan_last; 1011 1012 if (d.iscan_last > c->iscan1) 1013 c->iscan1 = d.iscan_last; 1014 1015 if (hpgs_paint_scanline_add_point(c->scanlines+d.iscan_last,d.x_last,order)) 1016 return -1; 1017 1018 if (hpgs_paint_scanline_add_point(c->scanlines+d.iscan_last,x1,-order)) 1019 return -1; 1020 } 1021 } 1022 // ignore control points. 1023 i+=2; 1024 break; 1025 } 1026 } 1027 1028 return 0; 1029} 1030 1031/* Internal: 1032 Cut path which is dashed according to the given \c gstate and has a linewidth 1033 below the width of a pixel with the scanlines of the given clipper \c c. 1034*/ 1035static int thin_cut_dashed(hpgs_paint_clipper *c, 1036 hpgs_paint_path *path, 1037 const hpgs_gstate *gstate) 1038{ 1039 int i0=0,i1=-1,i; 1040 int idash = 0; 1041 double t0=-0.5; 1042 double t1=0.5; 1043 1044 double l=gstate->dash_offset; 1045 int out_state = 0; 1046 double ltot = 0.0; 1047 double next_l = 0.0; 1048 double lseg; 1049 1050 hpgs_bezier_length bl; 1051 1052 for (idash=0;idash<gstate->n_dashes;++idash) 1053 ltot += gstate->dash_lengths[idash]; 1054 1055 for (i=0;i<path->n_points;++i) 1056 { 1057 int role = path->points[i].flags & HPGS_POINT_ROLE_MASK; 1058 int end_line = 0; 1059 1060 if (role == HPGS_POINT_BEZIER || role == HPGS_POINT_LINE) 1061 i1 = i; 1062 1063 if (path->points[i].flags & HPGS_POINT_SUBPATH_START) 1064 { 1065 if (role == HPGS_POINT_DOT) 1066 { 1067 if (thin_push_dot(c,&path->points[i].p)) return -1; 1068 i1 = -1; 1069 continue; 1070 } 1071 else 1072 { 1073 i0 = i1; 1074 t0 = -0.5; 1075 1076 l=fmod(gstate->dash_offset,ltot); 1077 if (l<0.0) l+= ltot; 1078 1079 next_l = 0.0; 1080 for (idash=0;idash<gstate->n_dashes;++idash) 1081 { 1082 next_l += gstate->dash_lengths[idash]; 1083 if (next_l > l) 1084 break; 1085 } 1086 1087 out_state = (idash+1) & 1; 1088 } 1089 } 1090 1091 switch (role) 1092 { 1093 case HPGS_POINT_LINE: 1094 lseg = hypot(path->points[i+1].p.x - path->points[i].p.x, 1095 path->points[i+1].p.y - path->points[i].p.y ); 1096 1097 end_line = 1098 (path->points[i+1].flags & HPGS_POINT_SUBPATH_END) || 1099 i >= path->n_points-2; 1100 1101 break; 1102 case HPGS_POINT_BEZIER: 1103 hpgs_bezier_length_init(&bl,path,i); 1104 1105 lseg = bl.l[HPGS_BEZIER_NSEGS]; 1106 1107 end_line = 1108 (path->points[i+3].flags & HPGS_POINT_SUBPATH_END) || 1109 i >= path->n_points-4; 1110 break; 1111 1112 default: 1113 lseg = 0.0; 1114 } 1115 1116 if (role == HPGS_POINT_BEZIER || role == HPGS_POINT_LINE) 1117 { 1118 while (l+lseg > next_l) 1119 { 1120 if (role == HPGS_POINT_BEZIER) 1121 t1 = hpgs_bezier_length_param(&bl,next_l - l); 1122 else 1123 t1 = (next_l - l) / lseg - 0.5; 1124 1125 idash = (idash+1) % gstate->n_dashes; 1126 next_l += gstate->dash_lengths[idash]; 1127 1128 if (out_state) 1129 { 1130 if (thin_cut_segment(c,path,i0,t0,i1,t1)) 1131 return -1; 1132 } 1133 1134 i0 = i1; 1135 t0 = t1; 1136 1137 out_state = (idash+1) & 1; 1138 } 1139 1140 l+=lseg; 1141 } 1142 1143 if (end_line && out_state && (i0<i1 || t0 < 0.5) ) 1144 { 1145 if (thin_cut_segment(c,path,i0,t0,i1,0.5)) 1146 return -1; 1147 } 1148 } 1149 return 0; 1150} 1151 1152/*! 1153 Cuts the border of the given \c path with the scanlines of the given 1154 clipper \c c. The linewidth of the given \c gstate is ignored and an 1155 optimized algorithm is used in order to retrieve the cut of the border 1156 of the path as if the linewidth has been exactly one pixel of the 1157 underlying image. 1158 1159 Return value: 1160 \li 0 Success. 1161 \li -1 The system is out of memory. 1162*/ 1163int hpgs_paint_clipper_thin_cut(hpgs_paint_clipper *c, 1164 hpgs_paint_path *path, 1165 const hpgs_gstate *gstate) 1166{ 1167 int iscan; 1168 1169 if (path->n_points < 1) return 0; 1170 1171 // catch path' which lie outside of the area of interest. 1172 if (path->bb.urx < c->bb.llx) return 0; 1173 if (path->bb.llx > c->bb.urx) return 0; 1174 if (path->bb.ury < c->bb.lly) return 0; 1175 if (path->bb.lly > c->bb.ury) return 0; 1176 1177 if (gstate->n_dashes == 0) 1178 { 1179 if (thin_cut_segment (c,path, 1180 0,-0.5,path->n_points-1,0.5)) 1181 return -1; 1182 } 1183 else 1184 { 1185 if (thin_cut_dashed(c,path,gstate)) 1186 return -1; 1187 } 1188 1189 for (iscan = c->iscan0;iscan<=c->iscan1;++iscan) 1190 { 1191 scanline_sort(c->scanlines[iscan].points,c->scanlines[iscan].n_points); 1192 1193#ifdef HPGS_DEBUG_THIN_CUT 1194 { 1195 int j; 1196 1197 hpgs_log("iscan = %d, np = %d ****************************************\n", 1198 iscan,c->scanlines[iscan].n_points); 1199 1200 if (c->scanlines[iscan].n_points & 1) 1201 hpgs_log("np odd !!!!!!!!!!!!!!!\n"); 1202 1203 for (j=0;j<c->scanlines[iscan].n_points;++j) 1204 hpgs_log("%lg(%d) ", 1205 c->scanlines[iscan].points[j].x, 1206 c->scanlines[iscan].points[j].order); 1207 1208 hpgs_log("\n"); 1209 } 1210#endif 1211 } 1212 1213 return 0; 1214} 1215 1216/* Internal: 1217 Cuts the bezier segment with the scanlines of the clipper 1218 and creates alpha slopes on the generated scanline intersection points. 1219 1220 Returns 0 upon success or -1 on memory error. 1221*/ 1222 1223typedef struct hpgs_bezier_clipper_alpha_cut_data_st hpgs_bezier_clipper_alpha_cut_data; 1224 1225struct hpgs_bezier_clipper_alpha_cut_data_st 1226{ 1227 hpgs_paint_clipper *c; 1228 hpgs_paint_path *path; 1229 int i; 1230 1231 double t_last; 1232 double x_last; 1233 int o_last; 1234 int iscan_last; 1235}; 1236 1237static int hpgs_bezier_clipper_alpha_cut_data_push(hpgs_bezier_clipper_alpha_cut_data *d, 1238 double t, double x, 1239 int iscan, int order, 1240 int o) 1241{ 1242 if (d->iscan_last >= 0 && d->iscan_last < d->c->n_scanlines) 1243 { 1244 if (d->iscan_last < d->c->iscan0) 1245 d->c->iscan0 = d->iscan_last; 1246 1247 if (d->iscan_last > d->c->iscan1) 1248 d->c->iscan1 = d->iscan_last; 1249 1250 if (hpgs_paint_scanline_add_slope(d->c->scanlines+d->iscan_last,d->x_last,x, 1251 d->o_last,o<=0 ? order : 0)) 1252 return -1; 1253 } 1254 1255 if (o < 0) 1256 { 1257 d->iscan_last = iscan+1; 1258 d->o_last = 0; 1259 } 1260 else 1261 { 1262 d->iscan_last = iscan; 1263 d->o_last = order; 1264 } 1265 1266 d->x_last = x; 1267 d->t_last = t; 1268 1269 return 0; 1270} 1271 1272static int bezier_clipper_alpha_cut_isolate_extrema (hpgs_bezier_clipper_alpha_cut_data *d, 1273 double t0, double t1, 1274 double y0, 1275 double y1, 1276 double y2, 1277 double y3, hpgs_bool do_max ) 1278{ 1279 // Ya olde golden cut... 1280 double c0 = .38196601125010515180; 1281 double c1 = .61803398874989484820; 1282 1283 double tt0 = -0.5; 1284 double tt1 = -0.5 * c1 + 0.5 * c0; 1285 double tt2 = -0.5 * c0 + 0.5 * c1; 1286 double tt3 = 0.5; 1287 1288 double tp = tt1 + 0.5; 1289 double tm = 0.5 - tt1; 1290 1291 double yy1 = y0 *tm*tm*tm + 3.0 * tm*tp * (y1 * tm + y2 * tp) + y3 * tp*tp*tp; 1292 1293 tp = tt2 + 0.5; 1294 tm = 0.5 - tt2; 1295 1296 double yy2 = y0 *tm*tm*tm + 3.0 * tm*tp * (y1 * tm + y2 * tp) + y3 * tp*tp*tp; 1297 1298 1299 while ((tt2-tt1)*(t1-t0) > 1.0e-8) 1300 if ((do_max && yy1 > yy2) || (!do_max && yy1 < yy2)) 1301 { 1302 tt3 = tt2; 1303 tt2 = tt1; 1304 yy2 = yy1; 1305 tt1 = tt3 * c0 + tt0 * c1; 1306 1307 tp = tt1 + 0.5; 1308 tm = 0.5 - tt1; 1309 yy1 = y0 *tm*tm*tm + 3.0 * tm*tp * (y1 * tm + y2 * tp) + y3 * tp*tp*tp; 1310 } 1311 else 1312 { 1313 tt0 = tt1; 1314 tt1 = tt2; 1315 yy1 = yy2; 1316 tt2 = tt3 * c1 + tt0 * c0; 1317 1318 tp = tt2 + 0.5; 1319 tm = 0.5 - tt2; 1320 yy2 = y0 *tm*tm*tm + 3.0 * tm*tp * (y1 * tm + y2 * tp) + y3 * tp*tp*tp; 1321 } 1322 1323 double tt = 0.5 * (tt1+tt2); 1324 double t = t0 * (0.5-tt) + t1 * (0.5+tt); 1325 double x = hpgs_bezier_path_x(d->path,d->i,t); 1326 1327 double dscan = (d->c->y0 - 0.5 * (yy1+yy2))/d->c->yfac + 0.5; 1328 double rdscan = floor(dscan); 1329 int iscan = (int)rdscan; 1330 int order = (int)((dscan-rdscan)*256.0+0.5); 1331 1332 return hpgs_bezier_clipper_alpha_cut_data_push(d,t,x,iscan,order,0); 1333} 1334 1335static int bezier_clipper_alpha_cut (hpgs_bezier_clipper_alpha_cut_data *d, 1336 double t0, double t1, 1337 double y0, 1338 double y1, 1339 double y2, 1340 double y3 ) 1341{ 1342 double ymin0 = (y0 < y1) ? y0 : y1; 1343 double ymin1 = (y2 < y3) ? y2 : y3; 1344 double ymin = ymin0<ymin1 ? ymin0 : ymin1; 1345 1346 double ymax0 = (y0 > y1) ? y0 : y1; 1347 double ymax1 = (y2 > y3) ? y2 : y3; 1348 double ymax = ymax0>ymax1 ? ymax0 : ymax1; 1349 1350 double dscan0 = (d->c->y0 - ymax)/d->c->yfac - 0.5; 1351 double dscan1 = (d->c->y0 - ymin)/d->c->yfac - 0.5; 1352 1353 double rdscan0 = ceil(dscan0); 1354 double rdscan1 = floor(dscan1); 1355 1356 int iscan0 = (int)rdscan0; 1357 int iscan1 = (int)rdscan1; 1358 1359 if ((iscan0 > iscan1 && 1360 (((y1 != ymin || y0 == ymin) && 1361 y2 != ymin && 1362 (y1 != ymax || y0 == ymax) && 1363 y2 != ymax ) || ymin == ymax)) || 1364 iscan1 < -1 || iscan0 >= d->c->n_scanlines) 1365 { 1366 return 0; 1367 } 1368 else if (t1-t0 < 1.0e-8 && iscan0 == iscan1) 1369 { 1370 int o0; 1371 1372 if (y1 > y0) o0 = 1; 1373 else if (y1 < y0) o0 = -1; 1374 else if (y2 > y0) o0 = 1; 1375 else if (y2 < y0) o0 = -1; 1376 else if (y3 > y0) o0 = 1; 1377 else if (y3 < y0) o0 = -1; 1378 else o0 = 0; 1379 1380 int o1; 1381 1382 if (y2 > y3) o1 = -1; 1383 else if (y2 < y3) o1 = 1; 1384 else if (y1 > y3) o1 = -1; 1385 else if (y1 < y3) o1 = 1; 1386 else if (y0 > y3) o1 = -1; 1387 else if (y0 < y3) o1 = 1; 1388 else o1 = 0; 1389 1390 // horizontal cut. 1391 if (o0*o1 == 0) 1392 { 1393 return 0; 1394 } 1395 1396 // filter out startpoint hit. 1397 if (t0 == -0.5 && 1398 ((y0 == ymin && dscan1 == rdscan1) || 1399 (y0 == ymax && dscan0 == rdscan0) )) return 0; 1400 1401 // filter out endpoint hit. 1402 if (t1 == 0.5 && 1403 ((y3 == ymin && dscan1 == rdscan1) || 1404 (y3 == ymax && dscan0 == rdscan0) )) return 0; 1405 1406 double t = 0.5*(t0+t1); 1407 double x = hpgs_bezier_path_x(d->path,d->i,t); 1408 int o; 1409 1410 if (o0*o1 > 0) 1411 o=o0; 1412 else 1413 o=0; 1414 1415 return hpgs_bezier_clipper_alpha_cut_data_push(d,t,x,iscan0,256,o); 1416 } 1417 else if (iscan0 == iscan1+1 && 1418 ((y1 == ymin && y0 != ymin) || 1419 y2 == ymin )) 1420 { 1421 if (y2 == ymin && y2 == y3) 1422 { 1423 if (t1 != 0.5) 1424 { 1425 int order = (int)((dscan1-rdscan1)*256.0+0.5); 1426 double x = hpgs_bezier_path_x(d->path,d->i,t1); 1427 return hpgs_bezier_clipper_alpha_cut_data_push(d,t1,x,iscan0,order,0); 1428 } 1429 else 1430 return 0; 1431 } 1432 else 1433 return bezier_clipper_alpha_cut_isolate_extrema (d,t0,t1,y0,y1,y2,y3,HPGS_FALSE); 1434 } 1435 else if (iscan0 == iscan1+1 && 1436 ((y1 == ymax && y0 != ymax) || 1437 y2 == ymax )) 1438 { 1439 if (y2 == ymax && y2 == y3) 1440 { 1441 if (t1 != 0.5) 1442 { 1443 int order = (int)((dscan1-rdscan1)*256.0+0.5); 1444 double x = hpgs_bezier_path_x(d->path,d->i,t1); 1445 return hpgs_bezier_clipper_alpha_cut_data_push(d,t1,x,iscan0,order,0); 1446 } 1447 else 1448 return 0; 1449 } 1450 1451 return bezier_clipper_alpha_cut_isolate_extrema (d,t0,t1,y0,y1,y2,y3,HPGS_TRUE); 1452 } 1453 else if (t1-t0 < 1.0e-15) 1454 { 1455 return 0; 1456 } 1457 else 1458 { 1459 // partition the spline. 1460 double tmid = 0.5*(t0+t1); 1461 1462 // midpoint. 1463 double ymid,y1l,y2l,y1u,y2u; 1464 1465 y1l = 0.5 * (y0 + y1); 1466 1467 y2l = 0.25 * (y0 + y2) + 0.5 * y1; 1468 1469 ymid = 1470 (y0 + y3) * 0.125 + 0.375 * (y1 + y2); 1471 1472 y1u = 0.25 * (y1 + y3) + 0.5 * y2; 1473 1474 y2u = 0.5 * (y2 + y3); 1475 1476 if (bezier_clipper_alpha_cut (d,t0,tmid,y0,y1l,y2l,ymid)) 1477 return -1; 1478 1479 if (bezier_clipper_alpha_cut (d,tmid,t1,ymid,y1u,y2u,y3)) 1480 return -1; 1481 1482 return 0; 1483 } 1484} 1485 1486/*! 1487 Cuts the border of the given \c path with the scanlines of the given 1488 clipper \c cand creates alpha slopes on the generated scanline 1489 intersection points. This methid is used in order to create the 1490 basic data for antialiasing output in \c scanline_emit_alpha 1491 1492 Return value: 1493 \li 0 Success. 1494 \li -1 The system is out of memory. 1495*/ 1496static int hpgs_paint_clipper_alpha_cut(hpgs_paint_clipper *c, 1497 hpgs_paint_path *path) 1498{ 1499 int i; 1500 int iscan; 1501 1502 if (path->n_points < 2) return 0; 1503 1504 // catch path' which lie outside of the area of interest. 1505 if (path->bb.urx < c->bb.llx) return 0; 1506 if (path->bb.llx > c->bb.urx) return 0; 1507 if (path->bb.ury < c->bb.lly) return 0; 1508 if (path->bb.lly > c->bb.ury) return 0; 1509 1510 for (i=0;i<path->n_points;++i) 1511 { 1512 hpgs_path_point *point = &path->points[i]; 1513 hpgs_path_point *next_point; 1514 double dscan0,dscan1,rdscan0,rdscan1,x0,y0,x1,y1; 1515 int iscan0,iscan1,o,order; 1516 1517 switch (point->flags & HPGS_POINT_ROLE_MASK) 1518 { 1519 case HPGS_POINT_LINE: 1520 case HPGS_POINT_FILL_LINE: 1521 next_point = &path->points[i+1]; 1522 1523 if (next_point->p.y < point->p.y) 1524 { 1525 o = 1; 1526 1527 x0 = point->p.x; 1528 y0 = point->p.y; 1529 x1 = next_point->p.x; 1530 y1 = next_point->p.y; 1531 } 1532 else 1533 { 1534 o = -1; 1535 1536 x0 = next_point->p.x; 1537 y0 = next_point->p.y; 1538 x1 = point->p.x; 1539 y1 = point->p.y; 1540 } 1541 1542 dscan0 = (c->y0 - y0)/c->yfac + 0.5; 1543 dscan1 = (c->y0 - y1)/c->yfac + 0.5; 1544 1545 rdscan0 = floor(dscan0); 1546 rdscan1 = floor(dscan1); 1547 1548 iscan0 = (int)rdscan0; 1549 iscan1 = (int)rdscan1; 1550 1551 if (iscan0 < c->n_scanlines) 1552 { 1553 int last_order; 1554 double last_x; 1555 1556 if (iscan0 < 0) 1557 { 1558 if (iscan1 < 0) continue; 1559 1560 double y = c->y0 + 0.5 * c->yfac; 1561 1562 if (x0!=x1) 1563 last_x = 1564 (x0 * (y1 - y) + x1 * (y - y0) ) / (y1 - y0); 1565 else 1566 last_x = x0; 1567 1568 iscan0 = 0; 1569 last_order = 0; 1570 c->iscan0 = 0; 1571 } 1572 else 1573 { 1574 last_order = o * (int)(256 * (dscan0 - rdscan0) + 0.5); 1575 last_x = x0; 1576 1577 if (iscan0 < c->iscan0) 1578 c->iscan0 = iscan0; 1579 } 1580 1581 if (x0 != x1) 1582 for (iscan=iscan0;iscan<iscan1 && iscan < c->n_scanlines;++iscan) 1583 { 1584 double y = c->y0 - (iscan + 0.5) * c->yfac; 1585 1586 double x = 1587 (x0 * (y1 - y) + x1 * (y - y0) ) / (y1 - y0); 1588 1589 if (hpgs_paint_scanline_add_slope(c->scanlines+iscan,last_x,x,last_order,o*256)) 1590 return -1; 1591 1592 last_x = x; 1593 last_order = 0; 1594 } 1595 else 1596 for (iscan=iscan0;iscan<iscan1 && iscan < c->n_scanlines;++iscan) 1597 { 1598 if (hpgs_paint_scanline_add_slope(c->scanlines+iscan,last_x,last_x,last_order,o*256)) 1599 return -1; 1600 1601 last_order = 0; 1602 } 1603 1604 if (iscan < c->n_scanlines) 1605 { 1606 order = o*(int)(256 * (dscan1 - rdscan1) + 0.5); 1607 1608 if (hpgs_paint_scanline_add_slope(c->scanlines+iscan,last_x,x1,last_order,order)) 1609 return -1; 1610 1611 if (iscan > c->iscan1) c->iscan1=iscan; 1612 } 1613 else 1614 c->iscan1 = c->n_scanlines-1; 1615 } 1616 1617 break; 1618 case HPGS_POINT_BEZIER: 1619 next_point = &path->points[i+3]; 1620 1621 { 1622 double yc0,yc1; 1623 1624 // start point. 1625 x0 = point->p.x; 1626 y0 = point->p.y; 1627 1628 // end point 1629 x1 = next_point->p.x; 1630 y1 = next_point->p.y; 1631 1632 // control points 1633 yc0 = path->points[i+1].p.y; 1634 yc1 = path->points[i+2].p.y; 1635 1636 dscan0 = (c->y0 - y0)/c->yfac + 0.5; 1637 rdscan0 = floor(dscan0); 1638 1639 hpgs_bezier_clipper_alpha_cut_data d = 1640 { c,path,i,-0.5,x0,(int)((dscan0-rdscan0)*256.0+0.5),(int)rdscan0 }; 1641 1642 if (bezier_clipper_alpha_cut (&d,-0.5,0.5,y0,yc0,yc1,y1)) 1643 return -1; 1644 1645 // add endpoint with appropriate order. 1646 if (d.iscan_last >= 0 && d.iscan_last < c->n_scanlines) 1647 { 1648 dscan1 = (c->y0 - y1)/c->yfac + 0.5; 1649 rdscan1 = floor(dscan1); 1650 iscan1=(int)rdscan1; 1651 1652 if (d.iscan_last < c->iscan0) 1653 c->iscan0 = d.iscan_last; 1654 1655 if (d.iscan_last > c->iscan1) 1656 c->iscan1 = d.iscan_last; 1657 1658 order = (int)((dscan1-rdscan1)*256.0+0.5); 1659 1660 if (hpgs_paint_scanline_add_slope(c->scanlines+d.iscan_last, 1661 d.x_last,x1, 1662 d.o_last, 1663 order)) 1664 return -1; 1665 } 1666 } 1667 // ignore control points. 1668 i+=2; 1669 break; 1670 } 1671 } 1672 1673#ifdef HPGS_DEBUG_ALPHA_CUT 1674 for (iscan = c->iscan0;iscan<=c->iscan1;++iscan) 1675 { 1676 int j; 1677 int so = 0; 1678 1679 hpgs_log("iscan = %d, np = %d ****************************************\n", 1680 iscan,c->scanlines[iscan].n_points); 1681 1682 for (j=0;j<c->scanlines[iscan].n_points;++j) 1683 { 1684 so += c->scanlines[iscan].points[j].order; 1685 hpgs_log("%lg(%d,%d) ", 1686 c->scanlines[iscan].points[j].x, 1687 c->scanlines[iscan].points[j].order,so); 1688 } 1689 1690 if (so) 1691 hpgs_log("so !!!!!!!!!!!!!!!"); 1692 1693 hpgs_log("\n"); 1694 } 1695#endif 1696 1697 return 0; 1698} 1699 1700static int hpgs_paint_scanline_reserve_point(hpgs_paint_scanline *s) 1701{ 1702 if (s->n_points >= s->points_malloc_size) 1703 { 1704 int nsz = s->points_malloc_size * 2; 1705 hpgs_scanline_point *np = (hpgs_scanline_point *) 1706 realloc(s->points, 1707 sizeof(hpgs_scanline_point)*nsz); 1708 1709 if (!np) return -1; 1710 s->points = np; 1711 s->points_malloc_size = nsz; 1712 } 1713 1714 return 0; 1715} 1716 1717/*! 1718 Adds an intersection point with coordinate \c x and order \c 0 to the 1719 given scanline \c s. 1720 1721 Return value: 1722 \li 0 Success. 1723 \li -1 The system is out of memory. 1724*/ 1725int hpgs_paint_scanline_add_point(hpgs_paint_scanline *s, double x, int o) 1726{ 1727 if (hpgs_paint_scanline_reserve_point(s)) 1728 return -1; 1729 1730 s->points[s->n_points].x = x; 1731 s->points[s->n_points].order = o; 1732 ++s->n_points; 1733 return 0; 1734} 1735 1736int hpgs_paint_scanline_add_slope(hpgs_paint_scanline *s, double x1, double x2, int o1, int o2) 1737{ 1738 int o = o2-o1; 1739 1740 if (x1 > x2) 1741 { 1742 double tmp = x1; 1743 x1 = x2; 1744 x2 = tmp; 1745 } 1746 1747 // binary search for x1. 1748 int i0 = 0; 1749 int i1 = s->n_points; 1750 1751 while (i1>i0) 1752 { 1753 int i = i0+(i1-i0)/2; 1754 1755 if (s->points[i].x < x1) 1756 i0 = i+1; 1757 else 1758 i1 = i; 1759 } 1760 1761 // insert x1, if not found 1762 if (i0 >= s->n_points || s->points[i0].x > x1) 1763 { 1764 if (hpgs_paint_scanline_reserve_point(s)) 1765 return -1; 1766 1767 if (s->n_points - i0) 1768 memmove(s->points+i0+1,s->points+i0, 1769 sizeof(hpgs_scanline_point) * (s->n_points - i0)); 1770 ++s->n_points; 1771 1772 // interpolate order of already exiting segment. 1773 s->points[i0].x = x1; 1774 int order = 1775 (i0 > 0 && i0+1 < s->n_points) ? 1776 (int)((s->points[i0+1].order * (x1-s->points[i0-1].x) )/ 1777 (s->points[i0+1].x-s->points[i0-1].x)+0.5 ) 1778 : 0; 1779 1780 s->points[i0].order = order; 1781 1782 // subtract intermediate order from already existing next point. 1783 ++i0; 1784 if (order) 1785 s->points[i0].order -= order; 1786 } 1787 else 1788 ++i0; 1789 1790 int last_order = 0; 1791 1792 // go on to x2. 1793 while (i0 < s->n_points && s->points[i0].x < x2) 1794 { 1795 int order = 1796 (int)((o * (s->points[i0].x-x1))/(x2-x1)+0.5); 1797 1798 s->points[i0].order += order - last_order; 1799 last_order = order; 1800 ++i0; 1801 } 1802 1803 // insert x2, if not found 1804 if (i0 >= s->n_points || s->points[i0].x > x2) 1805 { 1806 if (hpgs_paint_scanline_reserve_point(s)) 1807 return -1; 1808 1809 if (s->n_points - i0) 1810 memmove(s->points+i0+1,s->points+i0, 1811 sizeof(hpgs_scanline_point) * (s->n_points - i0)); 1812 ++s->n_points; 1813 1814 // interpolate order of already exiting segment. 1815 int order = 1816 (i0 > 0 && i0+1 < s->n_points) ? 1817 (int)((s->points[i0+1].order * (x2-s->points[i0-1].x) )/ 1818 (s->points[i0+1].x-s->points[i0-1].x)+0.5 ) 1819 : 0; 1820 1821 s->points[i0].x = x2; 1822 s->points[i0].order = order + o - last_order; 1823 1824 // subtract intermediate order from already existing next point. 1825 ++i0; 1826 if (order) 1827 s->points[i0].order -= order; 1828 } 1829 else 1830 // x2 already present -> add point. 1831 s->points[i0].order += o-last_order; 1832 1833 return 0; 1834} 1835 1836/*! 1837 Cuts te given \c path with the scanlines of the given 1838 clipper \c c. If you emit the clipper afterwards, the interior 1839 of the given path is drawn to the image. 1840 1841 If you want to stroke the path use either \c hpgs_paint_clipper_thin_cut 1842 for thin lines or contruct the outline of a thick line using 1843 the line style of a graphics state with \c hpgs_paint_path_stroke_path. 1844 1845 Return value: 1846 \li 0 Success. 1847 \li -1 The system is out of memory. 1848*/ 1849int hpgs_paint_clipper_cut(hpgs_paint_clipper *c, 1850 hpgs_paint_path *path) 1851{ 1852 if (c->overscan) 1853 return hpgs_paint_clipper_alpha_cut(c,path); 1854 else 1855 return hpgs_paint_clipper_cut_0(c,path); 1856} 1857 1858 1859/*! Sets the intersection of the given scanlines \c orig and \c clip 1860 to the scanline \c res. This is the worker function, which 1861 finds the intersection of visible segment of \c orig with the 1862 visible segments of \c clip and adds them to \c res. 1863 1864 If \c winding is \c HPGS_TRUE, the non-zero winding rule is used for the 1865 segment intersection, otherwise the exclusive-or rule applies. 1866 1867 Return values: 1868 1869 \li 0 Sucess. 1870 \li -1 The system is out of memory. 1871*/ 1872static int hpgs_paint_scanline_clip(hpgs_paint_scanline *res, 1873 const hpgs_paint_scanline *orig, 1874 const hpgs_paint_scanline *clip, 1875 hpgs_bool winding) 1876{ 1877 int io = 0; 1878 int ic = 0; 1879 int owind=0; 1880 int cwind=0; 1881 1882 int last_out_state = 0; 1883 double last_x=0.0; 1884 1885 res->n_points = 0; 1886 1887 while (io < orig->n_points && ic < clip->n_points) 1888 { 1889 int out_state; 1890 double x= orig->points[io].x; 1891 1892 if (clip->points[ic].x < x) x = clip->points[ic].x; 1893 1894 while (io < orig->n_points && x == orig->points[io].x) 1895 { 1896 owind += orig->points[io].order; 1897 ++io; 1898 } 1899 1900 while (ic < clip->n_points && x == clip->points[ic].x) 1901 { 1902 cwind += clip->points[ic].order; 1903 ++ic; 1904 } 1905 1906 out_state = 1907 cwind && ((winding && owind) || (!winding && (owind & 1))); 1908 1909 if (!out_state && last_out_state) 1910 { 1911 if (hpgs_paint_scanline_add_point(res,last_x,1) || 1912 hpgs_paint_scanline_add_point(res,x,-1) ) 1913 return -1; 1914 } 1915 1916 last_out_state = out_state; 1917 if (out_state) last_x = x; 1918 } 1919 1920 return 0; 1921} 1922 1923/*! Sets the intersection of the given scanlines \c orig and \c clip 1924 to the scanline \c res. This is the worker function, which 1925 finds the intersection of visible segment of \c orig with the 1926 visible segments of \c clip and adds them to \c res. 1927 1928 Antialiasing method with broken down winding counts for alpha 1929 calculation. 1930 1931 If \c winding is \c HPGS_TRUE, the non-zero winding rule is used for the 1932 segment intersection, otherwise the exclusive-or rule applies. 1933 1934 Return values: 1935 1936 \li 0 Sucess. 1937 \li -1 The system is out of memory. 1938*/ 1939static int hpgs_paint_scanline_clip_alpha(hpgs_paint_scanline *res, 1940 const hpgs_paint_scanline *orig, 1941 const hpgs_paint_scanline *clip, 1942 hpgs_bool winding) 1943{ 1944 int io = 0; 1945 int ic = 0; 1946 int owind=0; 1947 int cwind=0; 1948 int last_out_state = 0; 1949 1950 res->n_points = 0; 1951 1952 while (io < orig->n_points && ic < clip->n_points) 1953 { 1954 int out_state; 1955 hpgs_bool have_2; 1956 double x= orig->points[io].x; 1957 1958 if (clip->points[ic].x < x) x = clip->points[ic].x; 1959 1960 if (io < orig->n_points && x == orig->points[io].x) 1961 { 1962 owind += orig->points[io].order; 1963 ++io; 1964 } 1965 1966 if (ic < clip->n_points && x == clip->points[ic].x) 1967 { 1968 cwind += clip->points[ic].order; 1969 ++ic; 1970 } 1971 1972 if (winding) 1973 { 1974 if (owind <= -256 || owind >= 256) 1975 out_state = 256; 1976 else if (owind >= 0) 1977 out_state = owind; 1978 else 1979 out_state = -owind; 1980 } 1981 else 1982 { 1983 if (owind & 0x100) 1984 out_state = 256 - (owind & 0xff); 1985 else 1986 out_state = (owind & 0xff); 1987 } 1988 1989 if (out_state > cwind) out_state=cwind; 1990 1991 if (hpgs_paint_scanline_add_point(res,x,out_state-last_out_state)) 1992 return -1; 1993 1994 last_out_state = out_state; 1995 1996 have_2 = HPGS_FALSE; 1997 1998 while (io < orig->n_points && x == orig->points[io].x) 1999 { 2000 owind += orig->points[io].order; 2001 ++io; 2002 have_2 = HPGS_TRUE; 2003 } 2004 2005 while (ic < clip->n_points && x == clip->points[ic].x) 2006 { 2007 cwind += clip->points[ic].order; 2008 ++ic; 2009 have_2 = HPGS_TRUE; 2010 } 2011 2012 if (have_2) 2013 { 2014 if (winding) 2015 { 2016 if (owind <= -256 || owind >= 256) 2017 out_state = 256; 2018 else if (owind >= 0) 2019 out_state = owind; 2020 else 2021 out_state = -owind; 2022 } 2023 else 2024 { 2025 if (owind & 0x100) 2026 out_state = 256 - (owind & 0xff); 2027 else 2028 out_state = (owind & 0xff); 2029 } 2030 2031 if (out_state > cwind) out_state=cwind; 2032 2033 if (out_state != last_out_state) 2034 { 2035 if (hpgs_paint_scanline_add_point(res,x,out_state-last_out_state)) 2036 return -1; 2037 2038 last_out_state = out_state; 2039 } 2040 } 2041 } 2042 2043 return 0; 2044} 2045 2046/*! Returna a new clipper on the heap, which holds the intersection of the 2047 given path clipper with the current clip clipper. 2048 2049 If \c winding is \c HPGS_TRUE, the non-zero winding rule is used for the 2050 path intersection, otherwise the exclusive-or rule applies. 2051 2052 Use \c hpgs_paint_clipper_destroy in order to destroy the returned 2053 \c hpgs_paint_clipper from the heap. 2054 2055 Returns a null pointer, if the system is out of memory. 2056*/ 2057hpgs_paint_clipper *hpgs_paint_clipper_clip(const hpgs_paint_clipper *orig, 2058 const hpgs_paint_clipper *clip, 2059 hpgs_bool winding) 2060{ 2061 hpgs_paint_clipper *ret = 0; 2062 int i; 2063 2064 if (clip->height != orig->height || 2065 clip->n_scanlines != orig->n_scanlines) 2066 return ret; 2067 2068 ret = hpgs_new_paint_clipper(&orig->bb, 2069 orig->height, 2070 16,orig->overscan); 2071 2072 if (!ret) return ret; 2073 2074#ifdef HPGS_DEBUG_CLIP 2075 hpgs_log("orig: iscan0,iscan1 = %d,%d.\n",orig->iscan0,orig->iscan1); 2076 hpgs_log("clip: iscan0,iscan1 = %d,%d.\n",clip->iscan0,clip->iscan1); 2077#endif 2078 2079 ret->iscan0 = orig->iscan0 > clip->iscan0 ? orig->iscan0 : clip->iscan0; 2080 ret->iscan1 = orig->iscan1 < clip->iscan1 ? orig->iscan1 : clip->iscan1; 2081 2082 if (orig->overscan) 2083 { 2084 for (i=ret->iscan0;i<=ret->iscan1;++i) 2085 { 2086 if (hpgs_paint_scanline_clip_alpha(ret->scanlines+i, 2087 orig->scanlines+i, 2088 clip->scanlines+i,winding)) 2089 { hpgs_paint_clipper_destroy(ret); ret =0; break; } 2090 } 2091 } 2092 else 2093 { 2094 for (i=ret->iscan0;i<=ret->iscan1;++i) 2095 { 2096 if (hpgs_paint_scanline_clip(ret->scanlines+i, 2097 orig->scanlines+i, 2098 clip->scanlines+i,winding)) 2099 { hpgs_paint_clipper_destroy(ret); ret =0; break; } 2100 } 2101 } 2102 2103 return ret; 2104} 2105 2106/* Internal: 2107 Worker routine, which finds the visible segments from the 2108 intersection of the two scanlines and writes them to the physical 2109 row\c iy of the image. 2110*/ 2111static int scanline_emit_0(hpgs_image *image, 2112 double llx, double urx, int iy, 2113 const hpgs_paint_scanline *img, 2114 const hpgs_paint_scanline *clip, 2115 const hpgs_paint_color *c, 2116 hpgs_bool winding, hpgs_bool stroke) 2117{ 2118 int io = 0; 2119 int ic = 0; 2120 int owind=0; 2121 int cwind=0; 2122 2123 int last_out_state = 0; 2124 double last_x=0.0; 2125 2126 while (io < img->n_points && ic < clip->n_points) 2127 { 2128 int out_state; 2129 double x= img->points[io].x; 2130 2131 if (clip->points[ic].x < x) x = clip->points[ic].x; 2132 2133 while (io < img->n_points && x == img->points[io].x) 2134 { 2135 owind += img->points[io].order; 2136 ++io; 2137 // output zero-width chunks for stroke, 2138 // so we quit here. 2139 if (stroke) break; 2140 } 2141 2142 while (ic < clip->n_points && x == clip->points[ic].x) 2143 { 2144 cwind += clip->points[ic].order; 2145 ++ic; 2146 } 2147 2148 if (winding) 2149 out_state = cwind && owind; 2150 else 2151 out_state = cwind && (owind & 1); 2152 2153 if (last_out_state && out_state!=last_out_state) 2154 { 2155 // overestimate the thickness of chunks 2156 int ix1 = (int)(image->width*(last_x - llx)/(urx-llx)); 2157 int ix2 = (int)(image->width*(x - llx)/(urx-llx)); 2158 2159 if (ix1 < 0) ix1=0; 2160 else if (ix1 >= image->width) ix1=image->width-1; 2161 2162 if (ix2 < 0) ix2=0; 2163 else if (ix2 >= image->width) ix2=image->width-1; 2164 2165 if (ix2<ix1) ix2=ix1; 2166 2167#ifdef HPGS_DEBUG_EMIT_0 2168 hpgs_log("last_x,x,ix1,ix2,last_out_state,out_state = %lg,%lg,%d,%d,%d,%d.\n", 2169 last_x,x,ix1,ix2,last_out_state,out_state); 2170 2171#endif 2172 2173 if (hpgs_image_rop3_chunk (image,ix1,ix2,iy,c)) 2174 return -1; 2175 } 2176 2177 if (out_state!=last_out_state) 2178 { 2179 last_x = x; 2180 last_out_state = out_state; 2181 } 2182 } 2183 2184 return 0; 2185} 2186 2187/* Internal: 2188 Worker routine, which does the alpha calculation from n scanlines and 2189 writes the calculated pixels to a physical row of the image. 2190 2191 The calculation of the alpha values is based on broken down winding 2192 values. A non-antialiased winding value of 1 is represented as 2193 a broken down winding value of 256, value between 0 and 256 2194 correspond to the corresponding alpha value in the interval [0.0,1.0]. 2195 2196*/ 2197static int scanline_emit_alpha(hpgs_image *image, 2198 double llx, double urx, int iy, 2199 const hpgs_paint_scanline *img, 2200 const hpgs_paint_scanline *clip, 2201 const hpgs_paint_color *c, 2202 hpgs_bool winding) 2203{ 2204 int io = 0.0; 2205 int ic = 0.0; 2206 int owind = 0.0; 2207 int cwind = 0.0; 2208 double last_alpha = 0.0; 2209 2210 int last_partial_ix = -1; 2211 double last_partial_alpha = 0.0; 2212 2213 double last_x=0.0; 2214 double clip_last_x=0.0; 2215 2216 while (io < img->n_points && ic < clip->n_points) 2217 { 2218 int out_state; 2219 double x= img->points[io].x; 2220 double alpha; 2221 double clip_alpha; 2222 2223 if (clip->points[ic].x < x) x = clip->points[ic].x; 2224 2225 if (io < img->n_points && x == img->points[io].x) 2226 { 2227 owind += img->points[io].order; 2228 ++io; 2229 } 2230 2231 if (ic < clip->n_points && x == clip->points[ic].x) 2232 { 2233 clip_last_x = clip->points[ic].x; 2234 cwind += clip->points[ic].order; 2235 ++ic; 2236 } 2237 2238 if (ic == 0 || ic >= clip->n_points || x == clip_last_x) 2239 clip_alpha = (double)cwind/256.0; 2240 else 2241 clip_alpha = 2242 (cwind+clip->points[ic].order*(x-clip_last_x)/(clip->points[ic].x-clip_last_x))/256.0; 2243 2244#ifdef HPGS_DEBUG_EMIT_ALPHA 2245 hpgs_log("ic,x,clip_last_x,cx,cwind,o,clip_alpha = %d,%lg,%lg,%lg,%d,%d,%lg.\n", 2246 ic,x,clip_last_x, 2247 ic < clip->n_points ? clip->points[ic].x : -1.0e20, 2248 cwind, 2249 ic < clip->n_points ? clip->points[ic].order : -1, 2250 clip_alpha); 2251#endif 2252 2253 if (winding) 2254 { 2255 if (owind <= -256 || owind >= 256) 2256 out_state = 256; 2257 else if (owind >= 0) 2258 out_state = owind; 2259 else 2260 out_state = -owind; 2261 } 2262 else 2263 { 2264 if (owind & 0x100) 2265 out_state = 256 - (owind & 0xff); 2266 else 2267 out_state = (owind & 0xff); 2268 } 2269 2270 2271 alpha = out_state / 256.0; 2272 2273 if (alpha > clip_alpha) 2274 alpha=clip_alpha; 2275 2276 if (x>last_x && (alpha > 0.0 || last_alpha > 0.0)) 2277 { 2278 double x1 = image->width*(last_x - llx)/(urx-llx); 2279 double x2 = image->width*(x - llx)/(urx-llx); 2280 2281 int i,ix1,ix2; 2282 2283#ifdef HPGS_DEBUG_EMIT_ALPHA 2284 hpgs_log("last_x,x,out_state,last_alpha,alpha = %lg,%lg,%d,%lg,%lg.\n", 2285 last_x,x,out_state,last_alpha,alpha); 2286 2287#endif 2288 ix1 = (int)floor(x1); 2289 ix2 = (int)floor(x2); 2290 2291 if (ix1 < -1) ix1=-1; 2292 else if (ix1 >= image->width) ix1=image->width-1; 2293 2294 if (ix2 < 0) ix2=0; 2295 else if (ix2 >= image->width) ix2=image->width; 2296 2297 // alpha value for a given pixel position. 2298#define ALPHA_X(xx) ((last_alpha*(x2-(xx))+alpha*((xx)-x1))/(x2-x1)) 2299 2300 // emit first partial pixel. 2301 if (ix1 >= 0) 2302 { 2303 double aa; 2304 2305 if (ix2 > ix1) 2306 aa = (1.0 - (x1 - ix1)) * 0.5 * (last_alpha+ALPHA_X(ix1+1)); 2307 else 2308 aa = (x2 - x1) * 0.5 * (last_alpha + alpha); 2309 2310 if (ix1 != last_partial_ix) 2311 { 2312 if (last_partial_ix >= 0 && 2313 hpgs_image_rop3_pixel (image,last_partial_ix,iy, 2314 c,last_partial_alpha)) 2315 return -1; 2316 2317 last_partial_ix = ix1; 2318 last_partial_alpha = 0.0; 2319 } 2320 2321 last_partial_alpha += aa; 2322 } 2323 2324 // emit solid core segment. 2325 if (last_alpha == 1.0 && alpha == 1.0) 2326 { 2327 if (ix2 > ix1+1 && hpgs_image_rop3_chunk (image,ix1+1,ix2-1,iy,c)) 2328 return -1; 2329 } 2330 else 2331 { 2332 for (i=ix1+1;i<ix2;++i) 2333 { 2334 if (hpgs_image_rop3_pixel (image,i,iy,c, 2335 ALPHA_X(i+0.5))) 2336 return -1; 2337 } 2338 } 2339 2340 // emit last partial pixel. 2341 if (ix2 < image->width && ix2 > ix1) 2342 { 2343 double aa = (x2 - ix2) * 0.5 * (alpha + ALPHA_X(ix2)); 2344 2345 if (ix2 != last_partial_ix) 2346 { 2347 if (last_partial_ix >= 0 && 2348 hpgs_image_rop3_pixel (image,last_partial_ix,iy, 2349 c,last_partial_alpha)) 2350 return -1; 2351 2352 last_partial_ix = ix2; 2353 last_partial_alpha = 0.0; 2354 } 2355 2356 last_partial_alpha += aa; 2357 } 2358#undef ALPHA_X 2359 } 2360 2361 last_alpha = alpha; 2362 last_x = x; 2363 } 2364 2365 if (last_partial_ix >= 0 && 2366 hpgs_image_rop3_pixel (image,last_partial_ix,iy, 2367 c,last_partial_alpha)) 2368 return -1; 2369 2370 return 0; 2371} 2372 2373/*! Emits the intersection of the visible segments of the given clippers 2374 \c img and \c clip to the given image \c img using 2375 the given color \c c. 2376 2377 If \c stroke is \c HPGS_TRUE, zero-width segments are also emitted, which 2378 is feasible for clippers retrieved through \c hpgs_paint_clipper_thin_cut. 2379 2380 If \c winding is \c HPGS_TRUE, the non-zero winding rule is used for the 2381 segment intersection, otherwise the exclusive-or rule applies. 2382 2383 Return values: 2384 2385 \li 0 Sucess. 2386 \li -1 The system is out of memory or an error from the image has occurred. 2387*/ 2388int hpgs_paint_clipper_emit (hpgs_image *image, 2389 const hpgs_paint_clipper *img, 2390 const hpgs_paint_clipper *clip, 2391 const hpgs_paint_color *c, 2392 hpgs_bool winding, hpgs_bool stroke) 2393{ 2394 int iscan0,iscan1,iscan; 2395 2396 if (image->height != img->height || 2397 image->height != clip->height || 2398 clip->n_scanlines != img->n_scanlines) 2399 return -1; 2400 2401 iscan0 = img->iscan0 > clip->iscan0 ? img->iscan0 : clip->iscan0; 2402 iscan1 = img->iscan1 < clip->iscan1 ? img->iscan1 : clip->iscan1; 2403 2404#if defined (HPGS_DEBUG_EMIT_0) || defined(HPGS_DEBUG_EMIT_ALPHA) 2405 hpgs_log("emit: iscan0,iscan1 = %d,%d *************************\n",iscan0,iscan1); 2406#endif 2407 2408 if (img->overscan) 2409 { 2410 for (iscan = iscan0; iscan<=iscan1; ++iscan) 2411 { 2412#ifdef HPGS_DEBUG_EMIT_ALPHA 2413 hpgs_log("emit_alpha: iscan = %d ********************\n",iscan); 2414#endif 2415 if (scanline_emit_alpha(image,img->bb.llx,img->bb.urx,iscan, 2416 img->scanlines + iscan, 2417 clip->scanlines + iscan, 2418 c,winding)) 2419 return -1; 2420 } 2421 } 2422 else 2423 { 2424 for (iscan = iscan0; iscan<=iscan1; ++iscan) 2425 { 2426#ifdef HPGS_DEBUG_EMIT_0 2427 hpgs_log("emit_0: iscan = %d **************************\n",iscan); 2428#endif 2429 if (scanline_emit_0(image,img->bb.llx,img->bb.urx,iscan, 2430 img->scanlines + iscan, 2431 clip->scanlines + iscan, 2432 c,winding,stroke)) 2433 return -1; 2434 } 2435 } 2436 return 0; 2437} 2438 2439/*! Returns a new clipper on the heap, which covers the given bounding box 2440 an applies to an image with \c height rows. 2441 2442 \c scanline_msize determines the number of intersection points, for which 2443 memory is preallocated in each scanline. 2444 2445 The value of \c overscan determines the type of antialiasing applied as 2446 described under \c hpgs_paint_device_st::overscan. 2447 2448 Use \c hpgs_paint_clipper_destroy in order to destroy the returned 2449 \c hpgs_paint_clipper from the heap. 2450 2451 Returns a null pointer, if the system is out of memory. 2452*/ 2453hpgs_paint_clipper *hpgs_new_paint_clipper(const hpgs_bbox * bb, 2454 int height, 2455 int scanline_msize, 2456 int overscan) 2457{ 2458 hpgs_paint_clipper *ret = 2459 (hpgs_paint_clipper *)malloc(sizeof(hpgs_paint_clipper)); 2460 2461 if (ret) 2462 { 2463 int i; 2464 2465 ret->bb = *bb; 2466 2467 ret->n_scanlines = height; 2468 // slightly reinterpret lly and ury in order to 2469 // meet scanline y coordinates 2470 ret->yfac = (bb->ury-bb->lly) / height; 2471 ret->y0 = bb->ury - 0.5 * ret->yfac; 2472 2473 ret->overscan = overscan; 2474 ret->height = height; 2475 ret->iscan0 = ret->n_scanlines; 2476 ret->iscan1 = -1; 2477 2478 ret->scanlines = (hpgs_paint_scanline *) 2479 malloc(sizeof(hpgs_paint_scanline)*ret->n_scanlines); 2480 2481 if (ret->scanlines) 2482 for (i=0;i<ret->n_scanlines;++i) 2483 { 2484 if (hpgs_paint_scanline_init(ret->scanlines+i,scanline_msize)) 2485 break; 2486 } 2487 else 2488 i=-1; 2489 2490 // error recovery 2491 if (i<ret->n_scanlines) 2492 { 2493 for (;i>=0;--i) 2494 hpgs_paint_scanline_cleanup(ret->scanlines+i); 2495 2496 if (ret->scanlines) free(ret->scanlines); 2497 2498 free(ret); 2499 ret = 0; 2500 } 2501 } 2502 return ret; 2503} 2504 2505/*! Resets a clipper to be empty and to cover the whole 2506 rectanlge of an image covering the \c x coordinates in the range 2507 from \c llx to \c urx. 2508 2509 \li 0 Sucess. 2510 \li -1 The system is out of memory. 2511*/ 2512int hpgs_paint_clipper_reset(hpgs_paint_clipper *c, double llx, double urx) 2513{ 2514 int i; 2515 2516 if (c->overscan) 2517 { 2518 for (i=0;i<c->n_scanlines;++i) 2519 { 2520 hpgs_paint_scanline *s = c->scanlines+i; 2521 2522 s->n_points=0; 2523 if (hpgs_paint_scanline_add_point(s,llx,0) || 2524 hpgs_paint_scanline_add_point(s,llx,256) || 2525 hpgs_paint_scanline_add_point(s,urx,0) || 2526 hpgs_paint_scanline_add_point(s,urx,-256) ) 2527 return -1; 2528 } 2529 } 2530 else 2531 { 2532 for (i=0;i<c->n_scanlines;++i) 2533 { 2534 hpgs_paint_scanline *s = c->scanlines+i; 2535 2536 s->n_points=0; 2537 if (hpgs_paint_scanline_add_point(s,llx,1) || 2538 hpgs_paint_scanline_add_point(s,urx,-1) ) 2539 return -1; 2540 } 2541 } 2542 2543 c->iscan0 = 0; 2544 c->iscan1 = c->n_scanlines-1; 2545 2546 return 0; 2547} 2548 2549/*! Resets a clipper to be completely empty . 2550 2551 \li 0 Sucess. 2552 \li -1 The system is out of memory. 2553*/ 2554void hpgs_paint_clipper_clear(hpgs_paint_clipper *c) 2555{ 2556 int i; 2557 2558 for (i=c->iscan0;i<=c->iscan1;++i) 2559 { 2560 hpgs_paint_scanline *s = c->scanlines+i; 2561 2562 s->n_points=0; 2563 } 2564 2565 c->iscan0 = c->n_scanlines; 2566 c->iscan1 = -1; 2567} 2568 2569/*! Destroys a clipper from the heap. 2570*/ 2571void hpgs_paint_clipper_destroy(hpgs_paint_clipper *c) 2572{ 2573 int i; 2574 2575 if (c->scanlines) 2576 { 2577 for (i=0;i<c->n_scanlines;++i) 2578 hpgs_paint_scanline_cleanup(c->scanlines+i); 2579 2580 free(c->scanlines); 2581 } 2582 2583 free(c); 2584} 2585 2586