Mercurial > hgrepos > Python2 > PyMuPDF

comparison mupdf-source/source/fitz/draw-edge.c @ 3:2c135c81b16c

Find changesets by keywords (author, files, the commit message), revision number or hash, or revset expression.
MERGE: upstream PyMuPDF 1.26.4 with MuPDF 1.26.7
author Franz Glasner <fzglas.hg@dom66.de>
date Mon, 15 Sep 2025 11:44:09 +0200
parents b50eed0cc0ef
children
comparison
equal deleted inserted replaced
0:6015a75abc2d 3:2c135c81b16c
1 // Copyright (C) 2004-2025 Artifex Software, Inc.
2 //
3 // This file is part of MuPDF.
4 //
5 // MuPDF is free software: you can redistribute it and/or modify it under the
6 // terms of the GNU Affero General Public License as published by the Free
7 // Software Foundation, either version 3 of the License, or (at your option)
8 // any later version.
9 //
10 // MuPDF is distributed in the hope that it will be useful, but WITHOUT ANY
11 // WARRANTY; without even the implied warranty of MERCHANTABILITY or FITNESS
12 // FOR A PARTICULAR PURPOSE. See the GNU Affero General Public License for more
13 // details.
14 //
15 // You should have received a copy of the GNU Affero General Public License
16 // along with MuPDF. If not, see <https://www.gnu.org/licenses/agpl-3.0.en.html>
17 //
18 // Alternative licensing terms are available from the licensor.
19 // For commercial licensing, see <https://www.artifex.com/> or contact
20 // Artifex Software, Inc., 39 Mesa Street, Suite 108A, San Francisco,
21 // CA 94129, USA, for further information.
22
23 #include "mupdf/fitz.h"
24 #include "draw-imp.h"
25
26 #include <assert.h>
27 #include <limits.h>
28 #include <math.h>
29 #include <stdlib.h>
30 #include <string.h>
31
32 /*
33 * Global Edge List -- list of straight path segments for scan conversion
34 *
35 * Stepping along the edges is with Bresenham's line algorithm.
36 *
37 * See Mike Abrash -- Graphics Programming Black Book (notably chapter 40)
38 */
39
40 typedef struct fz_edge_s
41 {
42 int x, e, h, y;
43 int adj_up, adj_down;
44 int xmove;
45 int xdir, ydir; /* -1 or +1 */
46 } fz_edge;
47
48 typedef struct fz_gel_s
49 {
50 fz_rasterizer super;
51 int cap, len;
52 fz_edge *edges;
53 int acap, alen;
54 fz_edge **active;
55 int bcap;
56 unsigned char *alphas;
57 int *deltas;
58 } fz_gel;
59
60 static int
61 fz_reset_gel(fz_context *ctx, fz_rasterizer *rast)
62 {
63 fz_gel *gel = (fz_gel *)rast;
64
65 gel->len = 0;
66 gel->alen = 0;
67
68 return 0;
69 }
70
71 static void
72 fz_drop_gel(fz_context *ctx, fz_rasterizer *rast)
73 {
74 fz_gel *gel = (fz_gel *)rast;
75 if (gel == NULL)
76 return;
77 fz_free(ctx, gel->active);
78 fz_free(ctx, gel->edges);
79 fz_free(ctx, gel->alphas);
80 fz_free(ctx, gel->deltas);
81 fz_free(ctx, gel);
82 }
83
84 enum { INSIDE, OUTSIDE, LEAVE, ENTER };
85
86 #define clip_lerp_y(v,m,x0,y0,x1,y1,t) clip_lerp_x(v,m,y0,x0,y1,x1,t)
87
88 static int
89 clip_lerp_x(int val, int m, int x0, int y0, int x1, int y1, int *out)
90 {
91 int v0out = m ? x0 > val : x0 < val;
92 int v1out = m ? x1 > val : x1 < val;
93
94 if (v0out + v1out == 0)
95 return INSIDE;
96
97 if (v0out + v1out == 2)
98 return OUTSIDE;
99
100 if (v1out)
101 {
102 *out = y0 + (int)(((float)(y1 - y0)) * (val - x0) / (x1 - x0));
103 return LEAVE;
104 }
105
106 else
107 {
108 *out = y1 + (int)(((float)(y0 - y1)) * (val - x1) / (x0 - x1));
109 return ENTER;
110 }
111 }
112
113 static void
114 fz_insert_gel_raw(fz_context *ctx, fz_rasterizer *ras, int x0, int y0, int x1, int y1)
115 {
116 fz_gel *gel = (fz_gel *)ras;
117 fz_edge *edge;
118 int dx, dy;
119 int winding;
120 int width;
121 int tmp;
122
123 if (y0 == y1)
124 return;
125
126 if (y0 > y1) {
127 winding = -1;
128 tmp = x0; x0 = x1; x1 = tmp;
129 tmp = y0; y0 = y1; y1 = tmp;
130 }
131 else
132 winding = 1;
133
134 if (x0 < gel->super.bbox.x0) gel->super.bbox.x0 = x0;
135 if (x0 > gel->super.bbox.x1) gel->super.bbox.x1 = x0;
136 if (x1 < gel->super.bbox.x0) gel->super.bbox.x0 = x1;
137 if (x1 > gel->super.bbox.x1) gel->super.bbox.x1 = x1;
138
139 if (y0 < gel->super.bbox.y0) gel->super.bbox.y0 = y0;
140 if (y1 > gel->super.bbox.y1) gel->super.bbox.y1 = y1;
141
142 if (gel->len + 1 == gel->cap) {
143 int new_cap = gel->cap * 2;
144 gel->edges = fz_realloc_array(ctx, gel->edges, new_cap, fz_edge);
145 gel->cap = new_cap;
146 }
147
148 edge = &gel->edges[gel->len++];
149
150 dy = y1 - y0;
151 dx = x1 - x0;
152 width = fz_absi(dx);
153
154 edge->xdir = dx > 0 ? 1 : -1;
155 edge->ydir = winding;
156 edge->x = x0;
157 edge->y = y0;
158 edge->h = dy;
159 edge->adj_down = dy;
160
161 /* initial error term going l->r and r->l */
162 if (dx >= 0)
163 edge->e = 0;
164 else
165 edge->e = -dy + 1;
166
167 /* y-major edge */
168 if (dy >= width) {
169 edge->xmove = 0;
170 edge->adj_up = width;
171 }
172
173 /* x-major edge */
174 else {
175 edge->xmove = (width / dy) * edge->xdir;
176 edge->adj_up = width % dy;
177 }
178 }
179
180 static void
181 fz_insert_gel(fz_context *ctx, fz_rasterizer *ras, float fx0, float fy0, float fx1, float fy1, int rev)
182 {
183 int x0, y0, x1, y1;
184 int d, v;
185 const int hscale = fz_rasterizer_aa_hscale(ras);
186 const int vscale = fz_rasterizer_aa_vscale(ras);
187
188 fx0 = floorf(fx0 * hscale);
189 fx1 = floorf(fx1 * hscale);
190 fy0 = floorf(fy0 * vscale);
191 fy1 = floorf(fy1 * vscale);
192
193 /* Call fz_clamp so that clamping is done in the float domain, THEN
194 * cast down to an int. Calling fz_clampi causes problems due to the
195 * implicit cast down from float to int of the first argument
196 * over/underflowing and flipping sign at extreme values. */
197 x0 = (int)fz_clamp(fx0, BBOX_MIN * hscale, BBOX_MAX * hscale);
198 y0 = (int)fz_clamp(fy0, BBOX_MIN * vscale, BBOX_MAX * vscale);
199 x1 = (int)fz_clamp(fx1, BBOX_MIN * hscale, BBOX_MAX * hscale);
200 y1 = (int)fz_clamp(fy1, BBOX_MIN * vscale, BBOX_MAX * vscale);
201
202 d = clip_lerp_y(ras->clip.y0, 0, x0, y0, x1, y1, &v);
203 if (d == OUTSIDE) return;
204 if (d == LEAVE) { y1 = ras->clip.y0; x1 = v; }
205 if (d == ENTER) { y0 = ras->clip.y0; x0 = v; }
206
207 d = clip_lerp_y(ras->clip.y1, 1, x0, y0, x1, y1, &v);
208 if (d == OUTSIDE) return;
209 if (d == LEAVE) { y1 = ras->clip.y1; x1 = v; }
210 if (d == ENTER) { y0 = ras->clip.y1; x0 = v; }
211
212 d = clip_lerp_x(ras->clip.x0, 0, x0, y0, x1, y1, &v);
213 if (d == OUTSIDE) {
214 x0 = x1 = ras->clip.x0;
215 }
216 if (d == LEAVE) {
217 fz_insert_gel_raw(ctx, ras, ras->clip.x0, v, ras->clip.x0, y1);
218 x1 = ras->clip.x0;
219 y1 = v;
220 }
221 if (d == ENTER) {
222 fz_insert_gel_raw(ctx, ras, ras->clip.x0, y0, ras->clip.x0, v);
223 x0 = ras->clip.x0;
224 y0 = v;
225 }
226
227 d = clip_lerp_x(ras->clip.x1, 1, x0, y0, x1, y1, &v);
228 if (d == OUTSIDE) {
229 x0 = x1 = ras->clip.x1;
230 }
231 if (d == LEAVE) {
232 fz_insert_gel_raw(ctx, ras, ras->clip.x1, v, ras->clip.x1, y1);
233 x1 = ras->clip.x1;
234 y1 = v;
235 }
236 if (d == ENTER) {
237 fz_insert_gel_raw(ctx, ras, ras->clip.x1, y0, ras->clip.x1, v);
238 x0 = ras->clip.x1;
239 y0 = v;
240 }
241
242 fz_insert_gel_raw(ctx, ras, x0, y0, x1, y1);
243 }
244
245 static void
246 fz_insert_gel_rect(fz_context *ctx, fz_rasterizer *ras, float fx0, float fy0, float fx1, float fy1)
247 {
248 int x0, y0, x1, y1;
249 const int hscale = fz_rasterizer_aa_hscale(ras);
250 const int vscale = fz_rasterizer_aa_vscale(ras);
251
252 fx0 = floorf(fx0 * hscale);
253 fx1 = floorf(fx1 * hscale);
254 if (fx1 == fx0)
255 fx1++;
256 fy0 = floorf(fy0 * vscale);
257 fy1 = floorf(fy1 * vscale);
258 if (fy1 == fy0)
259 fy1++;
260
261 fx0 = fz_clamp(fx0, ras->clip.x0, ras->clip.x1);
262 fx1 = fz_clamp(fx1, ras->clip.x0, ras->clip.x1);
263 fy0 = fz_clamp(fy0, ras->clip.y0, ras->clip.y1);
264 fy1 = fz_clamp(fy1, ras->clip.y0, ras->clip.y1);
265
266 /* Call fz_clamp so that clamping is done in the float domain, THEN
267 * cast down to an int. Calling fz_clampi causes problems due to the
268 * implicit cast down from float to int of the first argument
269 * over/underflowing and flipping sign at extreme values. */
270 x0 = (int)fz_clamp(fx0, BBOX_MIN * hscale, BBOX_MAX * hscale);
271 y0 = (int)fz_clamp(fy0, BBOX_MIN * vscale, BBOX_MAX * vscale);
272 x1 = (int)fz_clamp(fx1, BBOX_MIN * hscale, BBOX_MAX * hscale);
273 y1 = (int)fz_clamp(fy1, BBOX_MIN * vscale, BBOX_MAX * vscale);
274
275 fz_insert_gel_raw(ctx, ras, x1, y0, x1, y1);
276 fz_insert_gel_raw(ctx, ras, x0, y1, x0, y0);
277 }
278
279 static int
280 cmpedge(const void *va, const void *vb)
281 {
282 const fz_edge *a = va;
283 const fz_edge *b = vb;
284 return a->y - b->y;
285 }
286
287 static void
288 sort_gel(fz_context *ctx, fz_gel *gel)
289 {
290 fz_edge *a = gel->edges;
291 int n = gel->len;
292 int h, i, k;
293 fz_edge t;
294
295 /* quick sort for long lists */
296 if (n > 10000)
297 {
298 qsort(a, n, sizeof *a, cmpedge);
299 return;
300 }
301
302 /* shell sort for short lists */
303 h = 1;
304 if (n < 14) {
305 h = 1;
306 }
307 else {
308 while (h < n)
309 h = 3 * h + 1;
310 h /= 3;
311 h /= 3;
312 }
313
314 while (h > 0)
315 {
316 for (i = 0; i < n; i++) {
317 t = a[i];
318 k = i - h;
319 /* TODO: sort on y major, x minor */
320 while (k >= 0 && a[k].y > t.y) {
321 a[k + h] = a[k];
322 k -= h;
323 }
324 a[k + h] = t;
325 }
326 h /= 3;
327 }
328 }
329
330 static int
331 fz_is_rect_gel(fz_context *ctx, fz_rasterizer *ras)
332 {
333 fz_gel *gel = (fz_gel *)ras;
334 /* a rectangular path is converted into two vertical edges of identical height */
335 if (gel->len == 2)
336 {
337 fz_edge *a = gel->edges + 0;
338 fz_edge *b = gel->edges + 1;
339 return a->y == b->y && a->h == b->h &&
340 a->xmove == 0 && a->adj_up == 0 &&
341 b->xmove == 0 && b->adj_up == 0;
342 }
343 return 0;
344 }
345
346 /*
347 * Active Edge List -- keep track of active edges while sweeping
348 */
349
350 static void
351 sort_active(fz_edge **a, int n)
352 {
353 int h, i, k;
354 fz_edge *t;
355
356 h = 1;
357 if (n < 14) {
358 h = 1;
359 }
360 else {
361 while (h < n)
362 h = 3 * h + 1;
363 h /= 3;
364 h /= 3;
365 }
366
367 while (h > 0)
368 {
369 for (i = 0; i < n; i++) {
370 t = a[i];
371 k = i - h;
372 while (k >= 0 && a[k]->x > t->x) {
373 a[k + h] = a[k];
374 k -= h;
375 }
376 a[k + h] = t;
377 }
378
379 h /= 3;
380 }
381 }
382
383 static int
384 insert_active(fz_context *ctx, fz_gel *gel, int y, int *e_)
385 {
386 int h_min = INT_MAX;
387 int e = *e_;
388
389 /* insert edges that start here */
390 if (e < gel->len && gel->edges[e].y == y)
391 {
392 do {
393 if (gel->alen + 1 == gel->acap) {
394 int newcap = gel->acap + 64;
395 fz_edge **newactive = fz_realloc_array(ctx, gel->active, newcap, fz_edge*);
396 gel->active = newactive;
397 gel->acap = newcap;
398 }
399 gel->active[gel->alen++] = &gel->edges[e++];
400 } while (e < gel->len && gel->edges[e].y == y);
401 *e_ = e;
402 }
403
404 if (e < gel->len)
405 h_min = gel->edges[e].y - y;
406
407 for (e=0; e < gel->alen; e++)
408 {
409 if (gel->active[e]->xmove != 0 || gel->active[e]->adj_up != 0)
410 {
411 h_min = 1;
412 break;
413 }
414 if (gel->active[e]->h < h_min)
415 {
416 h_min = gel->active[e]->h;
417 if (h_min == 1)
418 break;
419 }
420 }
421
422 /* shell-sort the edges by increasing x */
423 sort_active(gel->active, gel->alen);
424
425 return h_min;
426 }
427
428 static void
429 advance_active(fz_context *ctx, fz_gel *gel, int inc)
430 {
431 fz_edge *edge;
432 int i = 0;
433
434 while (i < gel->alen)
435 {
436 edge = gel->active[i];
437
438 edge->h -= inc;
439
440 /* terminator! */
441 if (edge->h == 0) {
442 gel->active[i] = gel->active[--gel->alen];
443 }
444
445 else {
446 edge->x += edge->xmove;
447 edge->e += edge->adj_up;
448 if (edge->e > 0) {
449 edge->x += edge->xdir;
450 edge->e -= edge->adj_down;
451 }
452 i ++;
453 }
454 }
455 }
456
457 /*
458 * Anti-aliased scan conversion.
459 */
460
461 static inline void
462 add_span_aa(fz_context *ctx, fz_gel *gel, int *list, int x0, int x1, int xofs, int h)
463 {
464 int x0pix, x0sub;
465 int x1pix, x1sub;
466 const int hscale = fz_rasterizer_aa_hscale(&gel->super);
467
468 if (x0 == x1)
469 return;
470
471 /* x between 0 and width of bbox */
472 x0 -= xofs;
473 x1 -= xofs;
474
475 /* The cast to unsigned below helps the compiler produce faster
476 * code on ARMs as the multiply by reciprocal trick it uses does not
477 * need to correct for signedness. */
478 x0pix = ((unsigned int)x0) / hscale;
479 x0sub = ((unsigned int)x0) % hscale;
480 x1pix = ((unsigned int)x1) / hscale;
481 x1sub = ((unsigned int)x1) % hscale;
482
483 if (x0pix == x1pix)
484 {
485 list[x0pix] += h*(x1sub - x0sub);
486 list[x0pix+1] += h*(x0sub - x1sub);
487 }
488
489 else
490 {
491 list[x0pix] += h*(hscale - x0sub);
492 list[x0pix+1] += h*x0sub;
493 list[x1pix] += h*(x1sub - hscale);
494 list[x1pix+1] += h*-x1sub;
495 }
496 }
497
498 static inline void
499 non_zero_winding_aa(fz_context *ctx, fz_gel *gel, int *list, int xofs, int h)
500 {
501 int winding = 0;
502 int x = 0;
503 int i;
504
505 for (i = 0; i < gel->alen; i++)
506 {
507 if (!winding && (winding + gel->active[i]->ydir))
508 x = gel->active[i]->x;
509 if (winding && !(winding + gel->active[i]->ydir))
510 add_span_aa(ctx, gel, list, x, gel->active[i]->x, xofs, h);
511 winding += gel->active[i]->ydir;
512 }
513 }
514
515 static inline void
516 even_odd_aa(fz_context *ctx, fz_gel *gel, int *list, int xofs, int h)
517 {
518 int even = 0;
519 int x = 0;
520 int i;
521
522 for (i = 0; i < gel->alen; i++)
523 {
524 if (!even)
525 x = gel->active[i]->x;
526 else
527 add_span_aa(ctx, gel, list, x, gel->active[i]->x, xofs, h);
528 even = !even;
529 }
530 }
531
532 static inline void
533 undelta_aa(fz_context *ctx, unsigned char * FZ_RESTRICT out, int * FZ_RESTRICT in, int n, int scale)
534 {
535 int d = 0;
536 (void)scale; /* Avoid warnings in some builds */
537
538 while (n--)
539 {
540 d += *in++;
541 *out++ = AA_SCALE(scale, d);
542 }
543 }
544
545 static inline void
546 blit_aa(fz_pixmap *dst, int x, int y, unsigned char *mp, int w, unsigned char *color, void *fn, fz_overprint *eop)
547 {
548 unsigned char *dp;
549 dp = dst->samples + (y - dst->y) * (size_t)dst->stride + (x - dst->x) * (size_t)dst->n;
550 if (color)
551 (*(fz_span_color_painter_t *)fn)(dp, mp, dst->n, w, color, dst->alpha, eop);
552 else
553 (*(fz_span_painter_t *)fn)(dp, dst->alpha, mp, 1, 0, w, 255, eop);
554 }
555
556 static void
557 fz_scan_convert_aa(fz_context *ctx, fz_gel *gel, int eofill, const fz_irect *clip, fz_pixmap *dst, unsigned char *color, void *painter, fz_overprint *eop)
558 {
559 unsigned char *alphas;
560 int *deltas;
561 int y, e;
562 int yd, yc;
563 int height, h0, rh;
564 int bcap;
565 const int hscale = fz_rasterizer_aa_hscale(&gel->super);
566 const int vscale = fz_rasterizer_aa_vscale(&gel->super);
567 const int scale = fz_rasterizer_aa_scale(&gel->super);
568
569 int xmin = fz_idiv(gel->super.bbox.x0, hscale);
570 int xmax = fz_idiv_up(gel->super.bbox.x1, hscale);
571
572 int xofs = xmin * hscale;
573
574 int skipx = clip->x0 - xmin;
575 int clipn = clip->x1 - clip->x0;
576
577 if (gel->len == 0)
578 return;
579
580 assert(xmin < xmax);
581 assert(clip->x0 >= xmin);
582 assert(clip->x1 <= xmax);
583
584 bcap = xmax - xmin + 2; /* big enough for both alphas and deltas */
585 if (bcap > gel->bcap)
586 {
587 gel->bcap = bcap;
588 fz_free(ctx, gel->alphas);
589 fz_free(ctx, gel->deltas);
590 gel->alphas = NULL;
591 gel->deltas = NULL;
592 gel->alphas = Memento_label(fz_malloc_array(ctx, bcap, unsigned char), "gel_alphas");
593 gel->deltas = Memento_label(fz_malloc_array(ctx, bcap, int), "gel_deltas");
594 }
595 alphas = gel->alphas;
596 deltas = gel->deltas;
597
598 memset(deltas, 0, (xmax - xmin + 1) * sizeof(int));
599 gel->alen = 0;
600
601 /* The theory here is that we have a list of the edges (gel) of length
602 * gel->len. We have an initially empty list of 'active' edges (of
603 * length gel->alen). As we increase y, we move any edge that is
604 * active at this point into the active list. We know that any edge
605 * before index 'e' is either active, or has been retired.
606 * Once the length of the active list is 0, and e has reached gel->len
607 * we know we are finished.
608 *
609 * As we move through the list, we group fz_aa_vscale 'sub scanlines'
610 * into single scanlines, and we blit them.
611 */
612
613 e = 0;
614 y = gel->edges[0].y;
615 yd = fz_idiv(y, vscale);
616
617 /* Quickly skip to the start of the clip region */
618 while (yd < clip->y0 && (gel->alen > 0 || e < gel->len))
619 {
620 /* rh = remaining height = number of subscanlines left to be
621 * inserted into the current scanline, which will be plotted
622 * at yd. */
623 rh = (yd+1)*vscale - y;
624
625 /* height = The number of subscanlines with identical edge
626 * positions (i.e. 1 if we have any non vertical edges). */
627 height = insert_active(ctx, gel, y, &e);
628 h0 = height;
629 if (h0 >= rh)
630 {
631 /* We have enough subscanlines to skip to the next
632 * scanline. */
633 h0 -= rh;
634 yd++;
635 }
636 /* Skip any whole scanlines we can */
637 while (yd < clip->y0 && h0 >= vscale)
638 {
639 h0 -= vscale;
640 yd++;
641 }
642 /* If we haven't hit the start of the clip region, then we
643 * have less than a scanline left. */
644 if (yd < clip->y0)
645 {
646 h0 = 0;
647 }
648 height -= h0;
649 advance_active(ctx, gel, height);
650
651 y += height;
652 }
653
654 /* Now do the active lines */
655 while (gel->alen > 0 || e < gel->len)
656 {
657 yc = fz_idiv(y, vscale); /* yc = current scanline */
658 /* rh = remaining height = number of subscanlines left to be
659 * inserted into the current scanline, which will be plotted
660 * at yd. */
661 rh = (yc+1)*vscale - y;
662 if (yc != yd)
663 {
664 undelta_aa(ctx, alphas, deltas, skipx + clipn, scale);
665 blit_aa(dst, xmin + skipx, yd, alphas + skipx, clipn, color, painter, eop);
666 memset(deltas, 0, (skipx + clipn) * sizeof(int));
667 }
668 yd = yc;
669 if (yd >= clip->y1)
670 break;
671
672 /* height = The number of subscanlines with identical edge
673 * positions (i.e. 1 if we have any non vertical edges). */
674 height = insert_active(ctx, gel, y, &e);
675 h0 = height;
676 if (h0 > rh)
677 {
678 if (rh < vscale)
679 {
680 /* We have to finish a scanline off, and we
681 * have more sub scanlines than will fit into
682 * it. */
683 if (eofill)
684 even_odd_aa(ctx, gel, deltas, xofs, rh);
685 else
686 non_zero_winding_aa(ctx, gel, deltas, xofs, rh);
687 undelta_aa(ctx, alphas, deltas, skipx + clipn, scale);
688 blit_aa(dst, xmin + skipx, yd, alphas + skipx, clipn, color, painter, eop);
689 memset(deltas, 0, (skipx + clipn) * sizeof(int));
690 yd++;
691 if (yd >= clip->y1)
692 break;
693 h0 -= rh;
694 }
695 if (h0 > vscale)
696 {
697 /* Calculate the deltas for any completely full
698 * scanlines. */
699 h0 -= vscale;
700 if (eofill)
701 even_odd_aa(ctx, gel, deltas, xofs, vscale);
702 else
703 non_zero_winding_aa(ctx, gel, deltas, xofs, vscale);
704 undelta_aa(ctx, alphas, deltas, skipx + clipn, scale);
705 do
706 {
707 /* Do any successive whole scanlines - no need
708 * to recalculate deltas here. */
709 blit_aa(dst, xmin + skipx, yd, alphas + skipx, clipn, color, painter, eop);
710 yd++;
711 if (yd >= clip->y1)
712 goto clip_ended;
713 h0 -= vscale;
714 }
715 while (h0 > 0);
716 /* If we have exactly one full scanline left
717 * to go, then the deltas/alphas are set up
718 * already. */
719 if (h0 == 0)
720 goto advance;
721 memset(deltas, 0, (skipx + clipn) * sizeof(int));
722 h0 += vscale;
723 }
724 }
725 if (eofill)
726 even_odd_aa(ctx, gel, deltas, xofs, h0);
727 else
728 non_zero_winding_aa(ctx, gel, deltas, xofs, h0);
729 advance:
730 advance_active(ctx, gel, height);
731
732 y += height;
733 }
734
735 if (yd < clip->y1)
736 {
737 undelta_aa(ctx, alphas, deltas, skipx + clipn, scale);
738 blit_aa(dst, xmin + skipx, yd, alphas + skipx, clipn, color, painter, eop);
739 }
740 clip_ended:
741 ;
742 }
743
744 /*
745 * Sharp (not anti-aliased) scan conversion
746 */
747
748 static inline void
749 blit_sharp(int x0, int x1, int y, const fz_irect *clip, fz_pixmap *dst, unsigned char *color, fz_solid_color_painter_t *fn, fz_overprint *eop)
750 {
751 unsigned char *dp;
752 int da = dst->alpha;
753 x0 = fz_clampi(x0, dst->x, dst->x + dst->w);
754 x1 = fz_clampi(x1, dst->x, dst->x + dst->w);
755 if (x0 < x1)
756 {
757 dp = dst->samples + (y - dst->y) * (size_t)dst->stride + (x0 - dst->x) * (size_t)dst->n;
758 if (color)
759 (*fn)(dp, dst->n, x1 - x0, color, da, eop);
760 else
761 memset(dp, 255, x1-x0);
762 }
763 }
764
765 static inline void
766 non_zero_winding_sharp(fz_context *ctx, fz_gel *gel, int y, const fz_irect *clip, fz_pixmap *dst, unsigned char *color, fz_solid_color_painter_t *fn, fz_overprint *eop)
767 {
768 int winding = 0;
769 int x = 0;
770 int i;
771 for (i = 0; i < gel->alen; i++)
772 {
773 if (!winding && (winding + gel->active[i]->ydir))
774 x = gel->active[i]->x;
775 if (winding && !(winding + gel->active[i]->ydir))
776 blit_sharp(x, gel->active[i]->x, y, clip, dst, color, fn, eop);
777 winding += gel->active[i]->ydir;
778 }
779 }
780
781 static inline void
782 even_odd_sharp(fz_context *ctx, fz_gel *gel, int y, const fz_irect *clip, fz_pixmap *dst, unsigned char *color, fz_solid_color_painter_t *fn, fz_overprint *eop)
783 {
784 int even = 0;
785 int x = 0;
786 int i;
787 for (i = 0; i < gel->alen; i++)
788 {
789 if (!even)
790 x = gel->active[i]->x;
791 else
792 blit_sharp(x, gel->active[i]->x, y, clip, dst, color, fn, eop);
793 even = !even;
794 }
795 }
796
797 static void
798 fz_scan_convert_sharp(fz_context *ctx,
799 fz_gel *gel, int eofill, const fz_irect *clip,
800 fz_pixmap *dst, unsigned char *color, fz_solid_color_painter_t *fn, fz_overprint *eop)
801 {
802 int e = 0;
803 int y = gel->edges[0].y;
804 int height;
805
806 gel->alen = 0;
807
808 /* Skip any lines before the clip region */
809 if (y < clip->y0)
810 {
811 while (gel->alen > 0 || e < gel->len)
812 {
813 height = insert_active(ctx, gel, y, &e);
814 y += height;
815 if (y >= clip->y0)
816 {
817 y = clip->y0;
818 break;
819 }
820 }
821 }
822
823 /* Now process as lines within the clip region */
824 while (gel->alen > 0 || e < gel->len)
825 {
826 height = insert_active(ctx, gel, y, &e);
827
828 if (gel->alen == 0)
829 y += height;
830 else
831 {
832 int h;
833 if (height >= clip->y1 - y)
834 height = clip->y1 - y;
835
836 h = height;
837 while (h--)
838 {
839 if (eofill)
840 even_odd_sharp(ctx, gel, y, clip, dst, color, fn, eop);
841 else
842 non_zero_winding_sharp(ctx, gel, y, clip, dst, color, fn, eop);
843 y++;
844 }
845 }
846 if (y >= clip->y1)
847 break;
848
849 advance_active(ctx, gel, height);
850 }
851 }
852
853 static void
854 fz_convert_gel(fz_context *ctx, fz_rasterizer *rast, int eofill, const fz_irect *clip, fz_pixmap *dst, unsigned char *color, fz_overprint *eop)
855 {
856 fz_gel *gel = (fz_gel *)rast;
857
858 sort_gel(ctx, gel);
859
860 if (fz_aa_bits > 0)
861 {
862 void *fn;
863 if (color)
864 fn = (void *)fz_get_span_color_painter(dst->n, dst->alpha, color, eop);
865 else
866 fn = (void *)fz_get_span_painter(dst->alpha, 1, 0, 255, eop);
867 if (fn == NULL)
868 return;
869 fz_scan_convert_aa(ctx, gel, eofill, clip, dst, color, fn, eop);
870 }
871 else
872 {
873 fz_solid_color_painter_t *fn = fz_get_solid_color_painter(dst->n, color, dst->alpha, eop);
874 assert(fn);
875 if (fn == NULL)
876 return;
877 fz_scan_convert_sharp(ctx, gel, eofill, clip, dst, color, (fz_solid_color_painter_t *)fn, eop);
878 }
879 }
880
881 static const fz_rasterizer_fns gel_rasterizer =
882 {
883 fz_drop_gel,
884 fz_reset_gel,
885 NULL, /* postindex */
886 fz_insert_gel,
887 fz_insert_gel_rect,
888 NULL, /* gap */
889 fz_convert_gel,
890 fz_is_rect_gel,
891 0 /* Not reusable */
892 };
893
894 fz_rasterizer *
895 fz_new_gel(fz_context *ctx)
896 {
897 fz_gel *gel;
898
899 gel = fz_new_derived_rasterizer(ctx, fz_gel, &gel_rasterizer);
900 fz_try(ctx)
901 {
902 gel->edges = NULL;
903 gel->cap = 512;
904 gel->len = 0;
905 gel->edges = Memento_label(fz_malloc_array(ctx, gel->cap, fz_edge), "gel_edges");
906
907 gel->acap = 64;
908 gel->alen = 0;
909 gel->active = Memento_label(fz_malloc_array(ctx, gel->acap, fz_edge*), "gel_active");
910 }
911 fz_catch(ctx)
912 {
913 fz_free(ctx, gel->edges);
914 fz_free(ctx, gel);
915 fz_rethrow(ctx);
916 }
917
918 return &gel->super;
919 }