src/libnr/nr-svp-render.cpp

   1 #define __NR_SVP_RENDER_C__
   2
   3 /*
   4  * Pixel buffer rendering library
   5  *
   6  * Authors:
   7  *   Lauris Kaplinski <lauris@kaplinski.com>
   8  *
   9  * This code is in public domain
  10  */
  11
  12 #define NR_SVPSEG_Y0(s,i) ((s)->points[(s)->segments[i].start].y)
  13 #define NR_SVPSEG_Y1(s,i) ((s)->points[(s)->segments[i].start + (s)->segments[i].length - 1].y)
  14
  15 #define noNR_VERBOSE
  16
  17 #include "nr-svp-render.h"
  18
  19 static void nr_svp_render (NRSVP *svp, unsigned char *px, unsigned int bpp, unsigned int rs, int x0, int y0, int x1, int y1,
  20                            void (* run) (unsigned char *px, int len, int c0_24, int s0_24, void *data), void *data);
  21
  22 static void nr_svp_run_A8_OR (unsigned char *d, int len, int c0_24, int s0_24, void *data);
  23
  24 /* Renders graymask of svl into buffer */
  25
  26 void
  27 nr_pixblock_render_svp_mask_or (NRPixBlock *d, NRSVP *svp)
  28 {
  29     nr_svp_render (svp, NR_PIXBLOCK_PX (d), 1, d->rs,
  30                    d->area.x0, d->area.y0, d->area.x1, d->area.y1,
  31                    nr_svp_run_A8_OR, NULL);
  32 }
  33
  34 static void
  35 nr_svp_run_A8_OR (unsigned char *d, int len, int c0_24, int s0_24, void *data)
  36 {
  37     if ((c0_24 >= 0xff0000) && (s0_24 == 0x0)) {
  38         /* Simple copy */
  39         while (len > 0) {
  40             d[0] = 255;
  41             d += 1;
  42             len -= 1;
  43         }
  44     } else {
  45         while (len > 0) {
  46             unsigned int ca, da;
  47             /* Draw */
  48             ca = c0_24 >> 16;
  49             da = 65025 - (255 - ca) * (255 - d[0]);
  50             d[0] = (da + 127) / 255;
  51             d += 1;
  52             c0_24 += s0_24;
  53             c0_24 = CLAMP (c0_24, 0, 16777216);
  54             len -= 1;
  55         }
  56     }
  57 }
  58
  59
  60 struct NRRun {
  61     NRRun *next;
  62     NR::Coord x0, y0, x1, y1;
  63     float step;
  64     float final;
  65     NR::Coord x;
  66     NR::Coord value;
  67 };
  68
  69 static NRRun *nr_run_new (NR::Coord x0, NR::Coord y0, NR::Coord x1, NR::Coord y1, int wind);
  70 static NRRun *nr_run_free_one (NRRun *run);
  71 static void nr_run_free_list (NRRun *run);
  72 static NRRun *nr_run_insort (NRRun *start, NRRun *run);
  73
  74 struct NRSlice {
  75     NRSlice *next;
  76     int wind;
  77     NRPoint *points;
  78     unsigned int current;
  79     unsigned int last;
  80     NR::Coord x;
  81     NR::Coord y;
  82     NR::Coord stepx;
  83 };
  84
  85 static NRSlice *nr_slice_new (int wind, NRPoint *points, unsigned int length, NR::Coord y);
  86 static NRSlice *nr_slice_free_one (NRSlice *s);
  87 static void nr_slice_free_list (NRSlice *s);
  88 static NRSlice *nr_slice_insort (NRSlice *start, NRSlice *slice);
  89 static int nr_slice_compare (NRSlice *l, NRSlice *r);
  90
  91 static void
  92 nr_svp_render (NRSVP *svp, unsigned char *px, unsigned int bpp, unsigned int rs, int iX0, int iY0, int iX1, int iY1,
  93                void (* run) (unsigned char *px, int len, int c0_24, int s0_24, void *data), void *data)
  94 {
  95     NR::Coord dX0, dY0, dX1, dY1;
  96     NRSlice *slices;
  97     unsigned int sidx;
  98     int ystart;
  99     unsigned char *rowbuffer;
 100     int iy0;
 101
 102     if (!svp || !svp->length) return;
 103
 104     /* Find starting pixel row */
 105     /* g_assert (svl->bbox.y0 == svl->vertex->y); */
 106     sidx = 0;
 107     while (NR_SVPSEG_IS_FLAT (svp, sidx) && (sidx < svp->length)) sidx += 1;
 108     if (sidx >= svp->length) return;
 109     ystart = (int) floor (NR_SVPSEG_Y0 (svp, sidx));
 110     if (ystart > iY0) {
 111         if (ystart >= iY1) return;
 112         px += (ystart - iY0) * rs;
 113         iY0 = ystart;
 114     }
 115
 116     dX0 = iX0;
 117     dY0 = iY0;
 118     dX1 = iX1;
 119     dY1 = iY1;
 120
 121     /* Construct initial slice list */
 122     slices = NULL;
 123     while (sidx < svp->length) {
 124         if (!NR_SVPSEG_IS_FLAT (svp, sidx)) {
 125             NRSVPSegment *seg;
 126             /* It is real renderable segment */
 127             /* Postpone if starts above initial slice */
 128             if (NR_SVPSEG_Y0 (svp, sidx) > dY0) break;
 129             seg = svp->segments + sidx;
 130             if (seg->wind && (NR_SVPSEG_Y1 (svp, sidx) > dY0)) {
 131                 /* We are renderable and cross initial slice */
 132                 NRSlice *newslice;
 133                 newslice = nr_slice_new (seg->wind, svp->points + seg->start, seg->length, dY0);
 134                 slices = nr_slice_insort (slices, newslice);
 135             }
 136         }
 137         sidx += 1;
 138     }
 139     if (!slices && (sidx >= svp->length)) return;
 140
 141     /* Row buffer */
 142     /* fixme: not needed */
 143     rowbuffer = px;
 144
 145     /* Main iteration */
 146     for (iy0 = iY0; iy0 < iY1; iy0 += 1) {
 147         NR::Coord dy0, dy1;
 148         NRSlice *ss, *cs;
 149         NRRun *runs;
 150         int xstart;
 151         float globalval;
 152         unsigned char *d;
 153         int ix0;
 154
 155         dy0 = iy0;
 156         dy1 = dy0 + 1.0;
 157
 158         /* Add possible new svls to slice list */
 159         while (sidx < svp->length) {
 160             if (!NR_SVPSEG_IS_FLAT (svp, sidx)) {
 161                 NRSVPSegment *seg;
 162                 /* It is real renderable segment */
 163                 /* Postpone if starts above ending slice */
 164                 if (NR_SVPSEG_Y0 (svp, sidx) > dy1) break;
 165                 seg = svp->segments + sidx;
 166                 if (seg->wind) {
 167                     NR::Coord y;
 168                     NRSlice *newslice;
 169                     /* We are renderable */
 170                     /* fixme: we should use safely nsvl->vertex->y here */
 171                     y = MAX (dy0, NR_SVPSEG_Y0 (svp, sidx));
 172                     newslice = nr_slice_new (seg->wind, svp->points + seg->start, seg->length, y);
 173                     slices = nr_slice_insort (slices, newslice);
 174                 }
 175             }
 176             sidx += 1;
 177         }
 178         /* Construct runs, stretching slices */
 179         /* fixme: This step can be optimized by continuing long runs and adding only new ones (Lauris) */
 180         runs = NULL;
 181         ss = NULL;
 182         cs = slices;
 183         while (cs) {
 184             /* g_assert (cs->y >= y0); */
 185             /* g_assert (cs->y < (y + 1)); */
 186             while ((cs->y < dy1) && (cs->current < cs->last)) {
 187                 NR::Coord rx0, ry0, rx1, ry1;
 188                 NRRun * newrun;
 189                 rx0 = cs->x;
 190                 ry0 = cs->y;
 191                 if (cs->points[cs->current + 1].y > dy1) {
 192                     /* The same slice continues */
 193                     rx1 = rx0 + (dy1 - ry0) * cs->stepx;
 194                     ry1 = dy1;
 195                     cs->x = rx1;
 196                     cs->y = ry1;
 197                 } else {
 198                     /* Subpixel height run */
 199                     cs->current += 1;
 200                     rx1 = cs->points[cs->current].x;
 201                     ry1 = cs->points[cs->current].y;
 202                     cs->x = rx1;
 203                     cs->y = ry1;
 204                     if (cs->current < cs->last) {
 205                         cs->stepx = (cs->points[cs->current + 1].x - rx1) / (cs->points[cs->current + 1].y - ry1);
 206                     }
 207                 }
 208                 newrun = nr_run_new (rx0, ry0, rx1, ry1, cs->wind);
 209                 /* fixme: we should use walking forward/backward instead */
 210                 runs = nr_run_insort (runs, newrun);
 211             }
 212             if (cs->current < cs->last) {
 213                 ss = cs;
 214                 cs = cs->next;
 215             } else {
 216                 /* Slice is exhausted */
 217                 cs = nr_slice_free_one (cs);
 218                 if (ss) {
 219                     ss->next = cs;
 220                 } else {
 221                     slices = cs;
 222                 }
 223             }
 224         }
 225         /* Slices are expanded to next scanline */
 226         /* Run list is generated */
 227         /* Globalval is the sum of all finished runs */
 228         globalval = 0.0;
 229         if ((runs) && (dX0 < runs->x0)) {
 230             /* First run starts right from x0 */
 231             xstart = (int) floor (runs->x0);
 232         } else {
 233             NRRun *sr, *cr;
 234             /* First run starts left from x0 */
 235             xstart = iX0;
 236             sr = NULL;
 237             cr = runs;
 238             while ((cr) && (cr->x0 < dX0)) {
 239                 if (cr->x1 <= dX0) {
 240                     globalval += cr->final;
 241                     /* Remove exhausted current run */
 242                     cr = nr_run_free_one (cr);
 243                     if (sr) {
 244                         sr->next = cr;
 245                     } else {
 246                         runs = cr;
 247                     }
 248                 } else {
 249                     cr->x = dX0;
 250                     cr->value = (dX0 - cr->x0) * cr->step;
 251                     sr = cr;
 252                     cr = cr->next;
 253                 }
 254             }
 255         }
 256
 257         /* Running buffer */
 258         d = rowbuffer + bpp * (xstart - iX0);
 259
 260         for (ix0 = xstart; (runs) && (ix0 < iX1); ix0++) {
 261             NR::Coord dx0, dx1;
 262             int ix1;
 263             NRRun *sr, *cr;
 264             float localval;
 265             unsigned int fill;
 266             float fillstep;
 267             int rx1;
 268             int c24;
 269
 270             dx0 = ix0;
 271             dx1 = dx0 + 1.0;
 272             ix1 = ix0 + 1;
 273
 274             /* process runs */
 275             localval = globalval;
 276             sr = NULL;
 277             cr = runs;
 278             fill = TRUE;
 279             fillstep = 0.0;
 280             rx1 = iX1;
 281             while ((cr) && (cr->x0 < dx1)) {
 282                 if (cr->x1 <= dx1) {
 283                     /* Run ends here */
 284                     /* No fill */
 285                     fill = FALSE;
 286                     /* Continue with final value */
 287                     globalval += cr->final;
 288                     /* Add initial trapezoid */
 289                     localval += (float) (0.5 * (cr->x1 - cr->x) * (cr->value + cr->final));
 290                     /* Add final rectangle */
 291                     localval += (float) ((dx1 - cr->x1) * cr->final);
 292                     /* Remove exhausted run */
 293                     cr = nr_run_free_one (cr);
 294                     if (sr) {
 295                         sr->next = cr;
 296                     } else {
 297                         runs = cr;
 298                     }
 299                 } else {
 300                     /* Run continues through xnext */
 301                     if (fill) {
 302                         if (cr->x0 > ix0) {
 303                             fill = FALSE;
 304                         } else {
 305                             rx1 = MIN (rx1, (int) floor (cr->x1));
 306                             fillstep += cr->step;
 307                         }
 308                     }
 309                     localval += (float) ((dx1 - cr->x) * (cr->value + (dx1 - cr->x) * cr->step / 2.0));
 310                     cr->x = dx1;
 311                     cr->value = (dx1 - cr->x0) * cr->step;
 312                     sr = cr;
 313                     cr = cr->next;
 314                 }
 315             }
 316             if (fill) {
 317                 if (cr) rx1 = MIN (rx1, (int) floor (cr->x0));
 318             }
 319 #ifdef NR_VERBOSE
 320             if ((localval < -0.01) || (localval > 1.01)) {
 321                 printf ("Weird localval %g : gv %g\n", localval, globalval); // localizing ok
 322             }
 323 #endif
 324             localval = CLAMP (localval, 0.0F, 1.0F);
 325             c24 = (int) floor (16777215 * localval + 0.5);
 326             if (fill && (rx1 > ix1)) {
 327                 NRRun *r;
 328                 int s24;
 329                 s24 = (int) floor (16777215 * fillstep + 0.5);
 330                 if ((s24 != 0) || (c24 > 65535)) {
 331                     run (d, rx1 - ix0, c24, s24, data);
 332                 }
 333                 /* We have to rewind run positions as well */
 334                 for (r = runs; r && (r->x0 < dx1); r = r->next) {
 335                     r->x = rx1;
 336                     r->value = (rx1 - r->x0) * r->step;
 337                 }
 338                 d += bpp * (rx1 - ix0);
 339                 ix0 = rx1 - 1;
 340             } else {
 341                 run (d, 1, c24, 0, data);
 342                 d += bpp;
 343             }
 344         }
 345         nr_run_free_list (runs);
 346         rowbuffer += rs;
 347     }
 348     if (slices) nr_slice_free_list (slices);
 349 }
 350
 351 /* Slices */
 352
 353 #define NR_SLICE_ALLOC_SIZE 32
 354 static NRSlice *ffslice = NULL;
 355
 356 static NRSlice *
 357 nr_slice_new (int wind, NRPoint *points, unsigned int length, NR::Coord y)
 358 {
 359     NRSlice *s;
 360     NRPoint *p;
 361
 362     /* g_assert (svl); */
 363     /* g_assert (svl->vertex); */
 364     /* fixme: not sure, whether correct */
 365     /* g_assert (y == NR_COORD_SNAP (y)); */
 366     /* Slices startpoints are included, endpoints excluded */
 367     /* g_return_val_if_fail (y >= svl->bbox.y0, NULL); */
 368     /* g_return_val_if_fail (y < svl->bbox.y1, NULL); */
 369
 370     s = ffslice;
 371
 372     if (s == NULL) {
 373         int i;
 374         s = nr_new (NRSlice, NR_SLICE_ALLOC_SIZE);
 375         for (i = 1; i < (NR_SLICE_ALLOC_SIZE - 1); i++) s[i].next = &s[i + 1];
 376         s[NR_SLICE_ALLOC_SIZE - 1].next = NULL;
 377         ffslice = s + 1;
 378     } else {
 379         ffslice = s->next;
 380     }
 381
 382     s->next = NULL;
 383     s->wind = wind;
 384     s->points = points;
 385     s->current = 0;
 386     s->last = length - 1;
 387
 388     while ((s->current < s->last) && (s->points[s->current + 1].y <= y)) s->current += 1;
 389     p = s->points + s->current;
 390
 391     if (s->points[s->current].y == y) {
 392         s->x = p[0].x;
 393     } else {
 394         s->x = p[0].x + (p[1].x - p[0].x) * (y - p[0].y) / (p[1].y - p[0].y);
 395     }
 396     s->y = y;
 397     s->stepx = (p[1].x - p[0].x) / (p[1].y - p[0].y);
 398
 399     return s;
 400 }
 401
 402 static NRSlice *
 403 nr_slice_free_one (NRSlice *slice)
 404 {
 405     NRSlice *next;
 406     next = slice->next;
 407     slice->next = ffslice;
 408     ffslice = slice;
 409     return next;
 410 }
 411
 412 static void
 413 nr_slice_free_list (NRSlice *slice)
 414 {
 415     NRSlice *l;
 416
 417     if (!slice) return;
 418
 419     for (l = slice; l->next != NULL; l = l->next);
 420
 421     l->next = ffslice;
 422     ffslice = slice;
 423 }
 424
 425 static NRSlice *
 426 nr_slice_insort (NRSlice * start, NRSlice * slice)
 427 {
 428     NRSlice * s, * l;
 429
 430     if (!start) return slice;
 431     if (!slice) return start;
 432
 433     if (nr_slice_compare (slice, start) <= 0) {
 434         slice->next = start;
 435         return slice;
 436     }
 437
 438     s = start;
 439     for (l = start->next; l != NULL; l = l->next) {
 440         if (nr_slice_compare (slice, l) <= 0) {
 441             slice->next = l;
 442             s->next = slice;
 443             return start;
 444         }
 445         s = l;
 446     }
 447
 448     slice->next = NULL;
 449     s->next = slice;
 450
 451     return start;
 452 }
 453
 454 static int
 455 nr_slice_compare (NRSlice *l, NRSlice *r)
 456 {
 457     if (l->y == r->y) {
 458         if (l->x < r->x) return -1;
 459         if (l->x > r->x) return 1;
 460         if (l->stepx < r->stepx) return -1;
 461         if (l->stepx > r->stepx) return 1;
 462     } else if (l->y > r->y) {
 463         unsigned int pidx;
 464         NRPoint *p;
 465         NR::Coord x, ldx, rdx;
 466         /* This is bitch - we have to determine r values at l->y */
 467         pidx = 0;
 468         while ((pidx < r->last) && (r->points[pidx + 1].y <= l->y)) pidx += 1;
 469         /* If v is last vertex, r ends before l starts */
 470         if (pidx >= r->last) return 1;
 471         p = r->points + pidx;
 472         if (p[0].y == l->y) {
 473             x = p[0].x;
 474         } else {
 475             x = p[0].x + (p[1].x - p[0].x) * (l->y - p[0].y) / (p[1].y - p[0].y);
 476         }
 477         if (l->x < x) return -1;
 478         if (l->x > x) return 1;
 479         ldx = l->stepx * (p[1].y - p[0].y);
 480         rdx = p[1].x - p[0].x;
 481         if (ldx < rdx) return -1;
 482         if (ldx > rdx) return 1;
 483     } else {
 484         unsigned int pidx;
 485         NRPoint *p;
 486         NR::Coord x, ldx, rdx;
 487         /* This is bitch - we have to determine l value at r->y */
 488         pidx = 0;
 489         while ((pidx < l->last) && (l->points[pidx + 1].y <= r->y)) pidx += 1;
 490         /* If v is last vertex, l ends before r starts */
 491         if (pidx >= l->last) return 1;
 492         p = l->points + pidx;
 493         if (p[0].y == r->y) {
 494             x = p[0].x;
 495         } else {
 496             x = p[0].x + (p[1].x - p[0].x) * (r->y - p[0].y) / (p[1].y - p[0].y);
 497         }
 498         if (x < r->x) return -1;
 499         if (x > r->x) return 1;
 500         ldx = l->stepx * (p[1].y - p[0].y);
 501         rdx = p[1].x - p[0].x;
 502         if (ldx < rdx) return -1;
 503         if (ldx > rdx) return 1;
 504     }
 505     return 0;
 506 }
 507
 508 /*
 509  * Memory management stuff follows (remember goals?)
 510  */
 511
 512 #define NR_RUN_ALLOC_SIZE 32
 513 static NRRun *ffrun = NULL;
 514
 515 static NRRun *
 516 nr_run_new (NR::Coord x0, NR::Coord y0, NR::Coord x1, NR::Coord y1, int wind)
 517 {
 518     NRRun * r;
 519
 520     r = ffrun;
 521
 522     if (r == NULL) {
 523         int i;
 524         r = nr_new (NRRun, NR_RUN_ALLOC_SIZE);
 525         for (i = 1; i < (NR_RUN_ALLOC_SIZE - 1); i++) (r + i)->next = (r + i + 1);
 526         (r + NR_RUN_ALLOC_SIZE - 1)->next = NULL;
 527         ffrun = r + 1;
 528     } else {
 529         ffrun = r->next;
 530     }
 531
 532     r->next = NULL;
 533
 534     if (x0 <= x1) {
 535         r->x0 = x0;
 536         r->x1 = x1;
 537         r->y0 = y0;
 538         r->y1 = y1;
 539         r->step = (x0 == x1) ? 0.0F : (float) (wind * (y1 - y0) / (x1 - x0));
 540     } else {
 541         r->x0 = x1;
 542         r->x1 = x0;
 543         r->y0 = y1;
 544         r->y1 = y0;
 545         r->step = (float) (wind * (y1 - y0) / (x0 - x1));
 546     }
 547
 548     r->final = (float) (wind * (y1 - y0));
 549
 550     r->value = 0.0;
 551     r->x = r->x0;
 552
 553     return r;
 554 }
 555
 556 static NRRun *
 557 nr_run_free_one (NRRun *run)
 558 {
 559     NRRun *next;
 560     next = run->next;
 561     run->next = ffrun;
 562     ffrun = run;
 563     return next;
 564 }
 565
 566 static void
 567 nr_run_free_list (NRRun * run)
 568 {
 569     NRRun * l;
 570
 571     if (!run) return;
 572
 573     for (l = run; l->next != NULL; l = l->next);
 574     l->next = ffrun;
 575     ffrun = run;
 576 }
 577
 578 static NRRun *
 579 nr_run_insort (NRRun * start, NRRun * run)
 580 {
 581     NRRun * s, * l;
 582
 583     if (!start) return run;
 584     if (!run) return start;
 585
 586     if (run->x0 < start->x0) {
 587         run->next = start;
 588         return run;
 589     }
 590
 591     s = start;
 592     for (l = start->next; l != NULL; l = l->next) {
 593         if (run->x0 < l->x0) {
 594             run->next = l;
 595             s->next = run;
 596             return start;
 597         }
 598         s = l;
 599     }
 600
 601     s->next = run;
 602
 603     return start;
 604 }
 605
 606 /*
 607   Local Variables:
 608   mode:c++
 609   c-file-style:"stroustrup"
 610   c-file-offsets:((innamespace . 0)(inline-open . 0)(case-label . +))
 611   indent-tabs-mode:nil
 612   fill-column:99
 613   End:
 614 */
 615 // vim: filetype=cpp:expandtab:shiftwidth=4:tabstop=8:softtabstop=4:encoding=utf-8:textwidth=99 :