apdf/server/rasterize.h

   1 //========================================================================
   2 //
   3 // rasterize.h
   4 //
   5 // Copyright 2000-2001 Emmanuel Lesueur
   6 //
   7 //========================================================================
   8
   9 #include <stdlib.h>
  10 #include "AOutputDev.h"
  11
  12 #define IDB(x)  //x
  13 #define DB(x)   //x
  14
  15 #if 0
  16 #define CHECKBM(bm)     check_start = bm.data(); \
  17                         check_stop = check_start + bm.modulo * bm.height * bm.bpp;
  18 #define CHECK(p)        if ((Guchar*)(p) < check_start || (Guchar*)(p) >= check_stop) { \
  19                                 dprintf("#### Error: overflow line %d\n", __LINE__); \
  20                                 return; \
  21                         }
  22
  23 Guchar *check_start;
  24 Guchar *check_stop;
  25 extern "C" void dprintf(const char *,...);
  26 #else
  27 #define CHECKBM(bm)
  28 #define CHECK(p)
  29 #endif
  30
  31 inline double length(double x, double y) { return sqrt(x * x + y * y); }
  32 template<class T> inline T abs(T x) { return x < 0 ? -x : x; }
  33 template<class T> inline T max(T x, T y) { return x < y ? y : x; }
  34 template<class T> inline T min(T x, T y) { return x < y ? x : y; }
  35 template<class T> inline void swap(T& x, T& y) { T t = x; x = y; y = t; }
  36
  37 template<class colorT> inline
  38 void _rectfill(ABitmap& bm, int x0, int y0, int w, int h, colorT color) {
  39   CHECKBM(bm);
  40
  41   int modulo = bm.modulo;
  42   colorT *dest = (colorT*) bm.data();
  43
  44   x0 -= bm.xoffset;
  45   y0 -= bm.yoffset;
  46
  47   if (x0 < 0) {
  48     w += y0;
  49     x0 = 0;
  50   }
  51   if (x0 + w >= bm.width)
  52     w = bm.width - x0;
  53   if (y0 < 0) {
  54     h += y0;
  55     y0 = 0;
  56   }
  57   if (y0 + h >= bm.height)
  58     h = bm.height - y0;
  59
  60   dest += y0 * modulo + x0;
  61   modulo -= w;
  62   if (w > 0) {
  63     while (--h >= 0) {
  64       int k = w;
  65       while (--k >= 0) {
  66         CHECK(dest);
  67         *dest++ = color;
  68       }
  69       dest += modulo;
  70     }
  71   }
  72 }
  73
  74 template<class colorT> inline
  75 void _fill(ABitmap& bm, int x0, int y0, region* area, colorT color) {
  76   CHECKBM(bm);
  77
  78   int modulo = bm.modulo;
  79   colorT *dest = (colorT*) bm.data();
  80
  81   x0 += NEARESTPEL(area->origin.x) - bm.xoffset;
  82   y0 += NEARESTPEL(area->origin.y) - bm.yoffset;
  83
  84   int w = bm.width;
  85   int h = bm.height;
  86
  87   //printf("fill (%d,%d,%d,%d)\n",area->xmin,area->ymin,w,h);
  88   for (edgelist *edge = area->anchor; VALIDEDGE(edge); edge = edge->link->link) {
  89     pel *leftP = edge->xvalues;
  90     pel *rightP = edge->link->xvalues;
  91     int y1 = edge->ymin + y0;
  92     int y2 = min(edge->ymax + y0, h);
  93     //printf("edge: %d -> %d\n",y1,y2);
  94     if (y1 < 0) {
  95       leftP -= y1;
  96       rightP -= y1;
  97       y1 = 0;
  98     }
  99     colorT* p = dest + y1 * modulo;
 100     while (y1 < y2) {
 101       int x1 = max(*leftP++ + x0, 0);
 102       int x2 = min(*rightP++ + x0, w);
 103       //printf("\t %d -> %d\n",x1,x2);
 104       colorT* q = p + x1;
 105       while (x1 < x2) {
 106         CHECK(q);
 107         *q++ = color;
 108         ++x1;
 109       }
 110       ++y1;
 111       p += modulo;
 112     }
 113   }
 114 }
 115
 116
 117 template<class colorT>
 118 void AAfillrun(colorT* q, int x1, int x2, colorT c1, colorT c2) {
 119   if (x1 < x2) {
 120     q += x1 >> 1;
 121     if (x1 & 1) {
 122       CHECK(q);
 123       *q++ = c1;
 124       ++x1;
 125     }
 126     int x2odd = x2 & 1;
 127     x2 &= ~1;
 128     while (x1 < x2) {
 129       CHECK(q);
 130       *q++ = c2;
 131       x1 += 2;
 132     }
 133     if (x2odd) {
 134       CHECK(q);
 135       *q = c1;
 136     }
 137   }
 138 }
 139
 140 template<class colorT> inline
 141 void _AAfill(ABitmap& bm, int x0, int y0, region* area,
 142              colorT c1, colorT c2, colorT c3, colorT c4) {
 143   CHECKBM(bm);
 144   edgelist *prev = area->anchor;
 145   if (!prev)
 146     return;
 147   int modulo = bm.modulo;
 148   colorT *dest = (colorT*) bm.data();
 149   int bw = bm.width << 1;
 150   int bh = bm.height << 1;
 151   int bx = bm.xoffset - x0 - NEARESTPEL(area->origin.x) << 1;
 152   int by = bm.yoffset - y0 - NEARESTPEL(area->origin.y) << 1;
 153   /*DB(printf("--------------AAFill--------------\n");
 154      for(edgelist* e=area->anchor;VALIDEDGE(e);e=e->link->link) {
 155          printf("swath : y1=%d, y2=%d, top: %d -> %d, bottom : %d -> %d\n",
 156                 e->ymin-by,e->ymax-by,
 157                 *e->xvalues-bx,*e->link->xvalues-by,
 158                 e->xvalues[e->ymax-e->ymin-1]-bx,
 159                 e->link->xvalues[e->ymax-e->ymin-1]-by);
 160      })*/
 161   edgelist *prevprev = NULL;
 162   int prev_ymin = prev->ymin;
 163   for (edgelist *edge = area->anchor; VALIDEDGE(edge); edge = edge->link->link) {
 164     pel *leftP = edge->xvalues;
 165     pel *rightP = edge->link->xvalues;
 166     int y1 = edge->ymin - by;
 167     int y2 = min(edge->ymax - by, bh);
 168     if (y1 != prev_ymin) {
 169       prevprev = prev;
 170       prev = edge;
 171       prev_ymin = y1;
 172     }
 173     //printf("edge: %d -> %d\n",y1,y2);
 174     if (y1 < 0) {
 175       leftP -= y1;
 176       rightP -= y1;
 177       y1 = 0;
 178     }
 179     if (y1 >= y2)
 180       continue;
 181     colorT* p = dest + (y1 >> 1) * modulo;
 182     if (y1 & 1) {
 183       int x1 = max(*leftP++ - bx, 0);
 184       int x2 = min(*rightP++ - bx, bw);
 185       if (prevprev == NULL || prevprev->ymax - by != y1)
 186         AAfillrun(p, x1, x2, c1, c2);
 187       else {
 188         colorT* q = p + (x1 >> 1);
 189         for (edgelist *e = prevprev; x1 < x2 && e != prev; e = e->link->link) {
 190           int z1 = max(e->xvalues[e->ymax - e->ymin - 1] - bx, 0);
 191           int z2 = min(e->link->xvalues[e->ymax - e->ymin - 1] - bx, bw);
 192           if (z1 >= x2 || z2 <= x1 || z1 >= z2)
 193             continue;
 194           if (x1 < z1) {
 195             if (x1 & 1) {
 196               CHECK(q);
 197               *q++ = c1;
 198               ++x1;
 199             }
 200             int z1odd = z1 & 1;
 201             z1 &= ~1;
 202             while (x1 < z1) {
 203               CHECK(q);
 204               *q++ = c2;
 205               x1 += 2;
 206             }
 207             if (z1odd) {
 208               CHECK(q);
 209               *q++ = c3;
 210               x1 += 2;
 211             }
 212           } else if (x1 == z1 && (x1 & 1)) {
 213             CHECK(q);
 214             *q++ = c2;
 215             ++x1;
 216           }
 217           int z2i = z2;
 218           if (z2 > x2)
 219             z2 = x2;
 220           int z2odd = z2 & 1;
 221           z2 &= ~1;
 222           while (x1 < z2) {
 223             CHECK(q);
 224             *q++ = c4;
 225             x1 += 2;
 226           }
 227           if (z2odd) {
 228             if (z2i == x2) {
 229               CHECK(q);
 230               *q++ = c2;
 231             } else {
 232               CHECK(q);
 233               *q++ = c3;
 234             }
 235             x1 += 2;
 236           }
 237         }
 238         AAfillrun(p, x1, x2, c1, c2);
 239       }
 240       ++y1;
 241       p += modulo;
 242     }
 243     int oddy2 = y2 & 1;
 244     y2 &= ~1;
 245     while (y1 < y2) {
 246       int x1 = max(*leftP++ - bx, 0);
 247       int x2 = min(*rightP++ - bx, bw);
 248       int z1 = max(*leftP++ - bx, 0);
 249       int z2 = min(*rightP++ - bx, bw);
 250       //printf("\t %d -> %d\n",x1,x2);
 251       if (z1 >= x2 || z1 >= z2 || x1 >= x2) {
 252         if (z1 == x2)
 253           x2 = z1 = z2;
 254         AAfillrun(p, x1, x2, c1, c2);
 255         AAfillrun(p, z1, z2, c1, c2);
 256       } else {
 257         // general case :
 258         //              ***********
 259         //     ****************************
 260         //    x1       z1         z2      x2
 261         // -> (1)  2   (3)   4    (3)  2  (1)
 262
 263         if (x1 > z1) {  // We are only interested in the
 264           int t = x1;   // average number of filled pixels
 265           x1 = z1;      // in a 2x2 square, so we can
 266           z1 = t;       // replace a situation like:
 267         }               //     *****          ***
 268         if (z2 > x2) {  //   *****     by   *******
 269           int t = x2;
 270           x2 = z2;
 271           z2 = t;
 272         }
 273         // Here, we have  x1 <= z1 < z2 <= x2
 274         colorT* q = p + (x1 >> 1);
 275         if (x1 & 1) {
 276           if (x1 < z1){
 277             CHECK(q)    //  |  | ****
 278             *q++ = c1;  //  | *|******
 279           } else {
 280             CHECK(q)
 281             *q++ = c2;  //  | *|****
 282             ++z1;       //  | *|******
 283           }
 284           ++x1;
 285         }
 286         int z1odd = z1 & 1;
 287         z1 &= ~1;
 288         while (x1 < z1) {
 289           CHECK(q)
 290           *q++ = c2;
 291           x1 += 2;
 292         }
 293         if (z1odd) {
 294           CHECK(q)
 295           *q++ = c3;
 296           x1 += 2;
 297         }
 298         if (x1 < z2) {
 299           int z2odd = z2 & 1;
 300           z2 &= ~1;
 301           while (x1 < z2) {
 302             CHECK(q)
 303             *q++ = c4;
 304             x1 += 2;
 305           }
 306           if (z2odd) {
 307             x1 += 2;
 308             if (z2 + 1 == x2) {
 309               CHECK(q)
 310               *q++ = c2;
 311               x2 = x1;
 312             } else {
 313               CHECK(q)
 314               *q++ = c3;
 315             }
 316           }
 317           if (x1 < x2) {
 318             int x2odd = x2 & 1;
 319             x2 &= ~1;
 320             while (x1 < x2) {
 321               CHECK(q)
 322               *q++ = c2;
 323               x1 += 2;
 324             }
 325             if (x2odd) {
 326               CHECK(q)
 327               *q++ = c1;
 328             }
 329           }
 330         }
 331       }
 332       y1 += 2;
 333       p += modulo;
 334     }
 335     if (oddy2) {
 336       int x1 = max(*leftP++ - bx, 0);
 337       int x2 = min(*rightP++ - bx, bw);
 338       AAfillrun(p, x1, x2, c1, c2);
 339     }
 340   }
 341   //DB(printf("-----------------------------------\n");)
 342 }
 343
 344
 345 template<class colorT> inline
 346 void _clippedHLine(ABitmap& bm, int y, int x1, int x2, colorT color, DashState& ds) {
 347   CHECKBM(bm)
 348   colorT *p = (colorT*)bm.data() + y * bm.modulo + x1;
 349   if (ds.isSolid()) {
 350     while (x1 <= x2) {
 351       CHECK(p)
 352       *p++ = color;
 353       ++x1;
 354     }
 355   } else {
 356     while (x1 < x2) {
 357       if (ds.isOn()) {
 358         CHECK(p)
 359         *p = color;
 360       }
 361       ++p;
 362       ds.advance(1 << DashState::fractBits);
 363       ++x1;
 364     }
 365     if (x1 == x2 && ds.isOn()) {
 366       CHECK(p)
 367       *p = color;
 368     }
 369   }
 370 }
 371
 372 template<class colorT> inline
 373 void _clippedVLine(ABitmap& bm, int x, int y1, int y2, colorT color, DashState& ds) {
 374   CHECKBM(bm)
 375   int m = bm.modulo;
 376   colorT *p = (colorT*)bm.data() + y1 * m + x;
 377   if (ds.isSolid()) {
 378     while (y1 <= y2) {
 379       CHECK(p)
 380       *p = color;
 381       p += m;
 382       ++y1;
 383     }
 384   } else {
 385     while (y1 < y2) {
 386       if (ds.isOn()) {
 387         CHECK(p)
 388         *p = color;
 389       }
 390       p += m;
 391       ds.advance(1 << DashState::fractBits);
 392       ++y1;
 393     }
 394     if (y1 == y2 && ds.isOn()) {
 395       CHECK(p)
 396       *p = color;
 397     }
 398   }
 399 }
 400
 401 inline int RoundFP(int xy, int b) { return xy + (1 << b - 1) >> b; }
 402 inline int TruncFP(int xy, int b) { return xy >> b; }
 403
 404 // called with y1 < y2
 405 // use the exact algorithm of the type1 rasterizer, so that shapes filled
 406 // and stroked have a boundary that matches the interior.
 407 template<class colorT> inline
 408 void _clippedLine(ABitmap& bm, fractpel x1, fractpel y1, fractpel x2, fractpel y2, colorT color, DashState& ds) {
 409   CHECKBM(bm)
 410   const int PREC = 8;
 411
 412   x1 = TruncFP(x1, FRACTBITS - PREC);
 413   y1 = TruncFP(y1, FRACTBITS - PREC);
 414   x2 = TruncFP(x2, FRACTBITS - PREC);
 415   y2 = TruncFP(y2, FRACTBITS - PREC);
 416 //dprintf("line x=%d..%d, y=%d..%d, bm %dx%d\n",x1,x2,y1,y2,bm.width,bm.height);
 417
 418   int dx = x2 - x1;
 419   int dy = y2 - y1;
 420
 421   int x = RoundFP(x1, PREC);
 422   int y = RoundFP(y1, PREC);
 423   int m = bm.modulo;
 424   colorT *p = (colorT*)bm.data() + y * m + x;
 425 //dprintf("x=%d..%d, y=%d..%d\n",x,RoundFP(x2,PREC),y,RoundFP(y2,PREC));
 426   CHECK(p)
 427   CHECK((colorT*)bm.data() + RoundFP(y2, PREC) * m + RoundFP(x2, PREC))
 428   int county = RoundFP(y2, PREC) - y;
 429   int countx = RoundFP(x2, PREC) - x;
 430   int d;
 431   int pstep;
 432   if (dx < 0) {
 433     dx = -dx;
 434     countx = -countx;
 435     d = (dy * (x1 - (x << PREC) + (1 << (PREC - 1))) -
 436         dx * ((y << PREC) - y1 + (1 << (PREC - 1)))) >> PREC;
 437     pstep = -1;
 438   } else {
 439     d = (dy * ((x << PREC) - x1 + (1 << (PREC - 1))) -
 440         dx * ((y << PREC) - y1 + (1 << (PREC - 1)))) >> PREC;
 441     pstep = 1;
 442   }
 443 //dprintf("d=%d dx=%d dy=%d pstep=%d count %d countx %d\n", d,dx,dy,pstep,count,countx);
 444   if (ds.isSolid()) {
 445     if (d < 0) {
 446       CHECK(p)
 447       *p = color;
 448     }
 449     while (--county >= 0) {
 450       if (d < 0) {
 451         --countx;
 452         p += pstep;
 453         d += dy;
 454         while (d < 0) {
 455           CHECK(p)
 456           *p = color;
 457           --countx;
 458           p += pstep;
 459           d += dy;
 460         }
 461       }
 462       CHECK(p)
 463       *p = color;
 464       p += m;
 465       d -= dx;
 466     }
 467     if (d < 0) {
 468       --countx;
 469       p += pstep;
 470     }
 471     while (countx-- >= 0) {
 472       CHECK(p)
 473       *p = color;
 474       p += pstep;
 475     }
 476   } else {
 477     int xStep, yStep;
 478     double l = length(dx << DashState::fractBits, dy << DashState::fractBits);
 479     if (dx > dy) {
 480       xStep = int(l / dx);
 481       yStep = 0;
 482
 483     } else {
 484       xStep = 0;
 485       yStep = int(l / dy);
 486     }
 487     if (d < 0) {
 488       CHECK(p)
 489       if (ds.isOn())
 490         *p = color;
 491     }
 492     while (--county >= 0) {
 493       if (d < 0) {
 494         --countx;
 495         p += pstep;
 496         ds.advance(xStep);
 497         d += dy;
 498         while (d < 0) {
 499           CHECK(p)
 500           if (ds.isOn())
 501             *p = color;
 502           --countx;
 503           p += pstep;
 504           ds.advance(xStep);
 505           d += dy;
 506         }
 507       }
 508       CHECK(p)
 509       if(ds.isOn())
 510         *p = color;
 511       p += m;
 512       ds.advance(yStep);
 513       d -= dx;
 514     }
 515     if (d < 0) {
 516       --countx;
 517       p += pstep;
 518       ds.advance(yStep);
 519     }
 520     while (countx-- >= 0) {
 521       CHECK(p)
 522       if(ds.isOn())
 523         *p = color;
 524       p += pstep;
 525       ds.advance(xStep);
 526     }
 527   }
 528 }
 529
 530 #if 0
 531 template<class colorT>
 532 inline void clippedLine(ABitmap& bm, int x1, int y1, int x2, int y2, colorT color) {
 533   int dx = x2 - x1;
 534   int adx = dx < 0 ? -dx : dx;
 535   int dy = y2 - y1;
 536   int ady = dy < 0 ? -dy : dy;
 537
 538   if (adx > ady) {
 539     int m = bm.modulo;
 540     int sx = dx < 0 ? -1 : 1;
 541     colorT *p = (colorT*)bm.data() + /*y1 * m +*/ x1;
 542     int sy = (ady << 16) / adx;
 543     int ry = ((ady << 16) % adx) >> 1;
 544     if (dy < 0) {
 545       sy = -sy;
 546       ry = -ry;
 547     }
 548     y1 <<= 16;
 549     y1 += ry + (1 << 15);
 550     do {
 551       p[(y1 >> 16) * m] = color;
 552       y1 += sy;
 553       p += sx;
 554     } while (--adx >= 0);
 555   } else {
 556     int m = bm.modulo;
 557     colorT *p = (colorT*)bm.data() + y1 * m;
 558     if (dy < 0)
 559       m = -m;
 560     int sx = (adx << 16) / ady;
 561     int rx = ((adx << 16) % ady) >> 1;
 562     if (dx < 0) {
 563       sx = -sx;
 564       rx = -rx;
 565     }
 566     x1 <<= 16;
 567     x1 += rx + (1 << 15);
 568     do {
 569       p[x1 >> 16] = color;
 570       x1 += sx;
 571       p += m;
 572     } while (--ady >= 0);
 573   }
 574 }
 575 #endif
 576
 577 // copy bm2 to bm1 through area. 'area' and 'bm2' *must* be clipped to
 578 // the boundary of bm1.
 579 template<int BPP> inline
 580 void _clippedCopy(ABitmap& bm1, ABitmap& bm2, region* area) {
 581   CHECKBM(bm1)
 582   int modulo1 = bm1.modulo * BPP;
 583   int modulo2 = bm2.modulo * BPP;
 584   int xoffs1 = bm1.xoffset - NEARESTPEL(area->origin.x);
 585   int yoffs1 = bm1.yoffset - NEARESTPEL(area->origin.y);
 586   int xoffs2 = bm2.xoffset - bm1.xoffset;
 587   int yoffs2 = bm2.yoffset - bm1.yoffset;
 588   Guchar *dest = (Guchar*) bm1.data();
 589   const Guchar *src = (const Guchar*) bm2.data();
 590   int width = bm1.width;
 591   int height = bm1.height;
 592
 593   for (edgelist *edge = area->anchor; VALIDEDGE(edge); edge = edge->link->link) {
 594     pel *leftP = edge->xvalues;
 595     pel *rightP = edge->link->xvalues;
 596     int y1 = edge->ymin - yoffs1;
 597     int y2 = edge->ymax - yoffs1;
 598     Guchar *p;
 599     const Guchar *q;
 600
 601     if (y1 < 0) {
 602         leftP -= y1;
 603         rightP -= y1;
 604         y1 = 0;
 605     }
 606     if (y2 > height)
 607         y2 = height;
 608
 609     p = dest + y1 * modulo1;
 610     q = src + (y1 - yoffs2) * modulo2;
 611
 612     while (y1 < y2) {
 613       int x1 = *leftP++ - xoffs1;
 614       int x2 = *rightP++ - xoffs1;
 615
 616       if (x1 < 0)
 617           x1 = 0;
 618       if (x2 > width)
 619           x2 = width;
 620
 621       if (x1 < x2) {
 622         CHECK(p + x1 * BPP)
 623         CHECK(p + (x2 - 1) * BPP)
 624         memcpy(p + x1 * BPP,
 625                q + (x1 - xoffs2) * BPP, (x2 - x1) * BPP);
 626       }
 627
 628       ++y1;
 629       p += modulo1;
 630       q += modulo2;
 631     }
 632   }
 633 }
 634
 635 template<class colorT> inline
 636 void _drawPicLine(AOutputDev::DrawPicParams& params,
 637                   int y, int x1, int x2,
 638                   int xp1, int yp1, int xp2, int yp2) {
 639   int dxp, dyp;
 640
 641   IDB(printf("drawPicLine(y=%d, %d -> %d, (%d,%d)->(%d,%d)\n", y, x1, x2, xp1, yp1, xp2, yp2));
 642   if (x1 >= x2) {
 643     dxp = 0;
 644     dyp = 0;
 645   } else {
 646     dxp = ((xp2 - xp1) << 16) / (x2 - x1);
 647     dyp = ((yp2 - yp1) << 16) / (x2 - x1);
 648   }
 649
 650   int xp = xp1 << 16;
 651   int yp = yp1 << 16;
 652
 653   if (x1 < 0) {
 654     xp -= dxp * x1;
 655     yp -= dyp * x1;
 656     x1 = 0;
 657   }
 658   if (x2 >= params.bm->width)
 659     x2 = params.bm->width - 1;
 660
 661   int w = params.srcWidth;
 662   colorT *q = (colorT*)params.bm->data() + y * params.bm->modulo + x1;
 663
 664   if (params.maskSrc) {
 665     const Guchar *p = params.maskSrc;
 666     colorT c(params.color);
 667
 668     for (int x = x1; x <= x2; ++x) {
 669       if (p[(yp >> 16) * w + (xp >> 16)])
 670         *q = c;
 671       ++q;
 672       xp += dxp;
 673       yp += dyp;
 674     }
 675
 676   } else {
 677     const colorT *p = (const colorT*)params.src;
 678
 679     for (int x = x1; x <= x2; ++x) {
 680       *q++ = p[(yp >> 16) * w + (xp >> 16)];
 681       xp += dxp;
 682       yp += dyp;
 683     }
 684   }
 685 }
 686