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