1 #define __NR_SVP_RENDER_C__
3 /*
4 * Pixel buffer rendering library
5 *
6 * Authors:
7 * Lauris Kaplinski <lauris@kaplinski.com>
8 *
9 * This code is in public domain
10 */
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)
15 #define noNR_VERBOSE
17 #include <glib/gmem.h>
18 #include "nr-svp-render.h"
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);
23 static void nr_svp_run_A8_OR (unsigned char *d, int len, int c0_24, int s0_24, void *data);
25 /* Renders graymask of svl into buffer */
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 }
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 }
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 };
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);
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 };
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);
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;
103 if (!svp || !svp->length) return;
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 }
117 dX0 = iX0;
118 dY0 = iY0;
119 dX1 = iX1;
120 dY1 = iY1;
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;
142 /* Row buffer */
143 /* fixme: not needed */
144 rowbuffer = px;
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;
156 dy0 = iy0;
157 dy1 = dy0 + 1.0;
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 }
258 /* Running buffer */
259 d = rowbuffer + bpp * (xstart - iX0);
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;
271 dx0 = ix0;
272 dx1 = dx0 + 1.0;
273 ix1 = ix0 + 1;
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 }
352 /* Slices */
354 #define NR_SLICE_ALLOC_SIZE 32
355 static NRSlice *ffslice = NULL;
357 static NRSlice *
358 nr_slice_new (int wind, NRPoint *points, unsigned int length, NR::Coord y)
359 {
360 NRSlice *s;
361 NRPoint *p;
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); */
371 s = ffslice;
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 }
383 s->next = NULL;
384 s->wind = wind;
385 s->points = points;
386 s->current = 0;
387 s->last = length - 1;
389 while ((s->current < s->last) && (s->points[s->current + 1].y <= y)) s->current += 1;
390 p = s->points + s->current;
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);
400 return s;
401 }
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 }
413 static void
414 nr_slice_free_list (NRSlice *slice)
415 {
416 NRSlice *l;
418 if (!slice) return;
420 for (l = slice; l->next != NULL; l = l->next);
422 l->next = ffslice;
423 ffslice = slice;
424 }
426 static NRSlice *
427 nr_slice_insort (NRSlice * start, NRSlice * slice)
428 {
429 NRSlice * s, * l;
431 if (!start) return slice;
432 if (!slice) return start;
434 if (nr_slice_compare (slice, start) <= 0) {
435 slice->next = start;
436 return slice;
437 }
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 }
449 slice->next = NULL;
450 s->next = slice;
452 return start;
453 }
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 }
509 /*
510 * Memory management stuff follows (remember goals?)
511 */
513 #define NR_RUN_ALLOC_SIZE 32
514 static NRRun *ffrun = NULL;
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;
521 r = ffrun;
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 }
533 r->next = NULL;
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 }
549 r->final = (float) (wind * (y1 - y0));
551 r->value = 0.0;
552 r->x = r->x0;
554 return r;
555 }
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 }
567 static void
568 nr_run_free_list (NRRun * run)
569 {
570 NRRun * l;
572 if (!run) return;
574 for (l = run; l->next != NULL; l = l->next);
575 l->next = ffrun;
576 ffrun = run;
577 }
579 static NRRun *
580 nr_run_insort (NRRun * start, NRRun * run)
581 {
582 NRRun * s, * l;
584 if (!start) return run;
585 if (!run) return start;
587 if (run->x0 < start->x0) {
588 run->next = start;
589 return run;
590 }
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 }
602 s->next = run;
604 return start;
605 }
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 :