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 "nr-svp-render.h"
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);
22 static void nr_svp_run_A8_OR (unsigned char *d, int len, int c0_24, int s0_24, void *data);
24 /* Renders graymask of svl into buffer */
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 }
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 }
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 };
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);
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 };
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);
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;
102 if (!svp || !svp->length) return;
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 }
116 dX0 = iX0;
117 dY0 = iY0;
118 dX1 = iX1;
119 dY1 = iY1;
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;
141 /* Row buffer */
142 /* fixme: not needed */
143 rowbuffer = px;
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;
155 dy0 = iy0;
156 dy1 = dy0 + 1.0;
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 }
257 /* Running buffer */
258 d = rowbuffer + bpp * (xstart - iX0);
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;
270 dx0 = ix0;
271 dx1 = dx0 + 1.0;
272 ix1 = ix0 + 1;
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 }
351 /* Slices */
353 #define NR_SLICE_ALLOC_SIZE 32
354 static NRSlice *ffslice = NULL;
356 static NRSlice *
357 nr_slice_new (int wind, NRPoint *points, unsigned int length, NR::Coord y)
358 {
359 NRSlice *s;
360 NRPoint *p;
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); */
370 s = ffslice;
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 }
382 s->next = NULL;
383 s->wind = wind;
384 s->points = points;
385 s->current = 0;
386 s->last = length - 1;
388 while ((s->current < s->last) && (s->points[s->current + 1].y <= y)) s->current += 1;
389 p = s->points + s->current;
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);
399 return s;
400 }
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 }
412 static void
413 nr_slice_free_list (NRSlice *slice)
414 {
415 NRSlice *l;
417 if (!slice) return;
419 for (l = slice; l->next != NULL; l = l->next);
421 l->next = ffslice;
422 ffslice = slice;
423 }
425 static NRSlice *
426 nr_slice_insort (NRSlice * start, NRSlice * slice)
427 {
428 NRSlice * s, * l;
430 if (!start) return slice;
431 if (!slice) return start;
433 if (nr_slice_compare (slice, start) <= 0) {
434 slice->next = start;
435 return slice;
436 }
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 }
448 slice->next = NULL;
449 s->next = slice;
451 return start;
452 }
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 }
508 /*
509 * Memory management stuff follows (remember goals?)
510 */
512 #define NR_RUN_ALLOC_SIZE 32
513 static NRRun *ffrun = NULL;
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;
520 r = ffrun;
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 }
532 r->next = NULL;
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 }
548 r->final = (float) (wind * (y1 - y0));
550 r->value = 0.0;
551 r->x = r->x0;
553 return r;
554 }
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 }
566 static void
567 nr_run_free_list (NRRun * run)
568 {
569 NRRun * l;
571 if (!run) return;
573 for (l = run; l->next != NULL; l = l->next);
574 l->next = ffrun;
575 ffrun = run;
576 }
578 static NRRun *
579 nr_run_insort (NRRun * start, NRRun * run)
580 {
581 NRRun * s, * l;
583 if (!start) return run;
584 if (!run) return start;
586 if (run->x0 < start->x0) {
587 run->next = start;
588 return run;
589 }
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 }
601 s->next = run;
603 return start;
604 }
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 :