Line data Source code
1 : /*
2 : * Copyright © 2004 Carl Worth
3 : * Copyright © 2006 Red Hat, Inc.
4 : * Copyright © 2007 David Turner
5 : * Copyright © 2008 M Joonas Pihlaja
6 : * Copyright © 2008 Chris Wilson
7 : * Copyright © 2009 Intel Corporation
8 : *
9 : * This library is free software; you can redistribute it and/or
10 : * modify it either under the terms of the GNU Lesser General Public
11 : * License version 2.1 as published by the Free Software Foundation
12 : * (the "LGPL") or, at your option, under the terms of the Mozilla
13 : * Public License Version 1.1 (the "MPL"). If you do not alter this
14 : * notice, a recipient may use your version of this file under either
15 : * the MPL or the LGPL.
16 : *
17 : * You should have received a copy of the LGPL along with this library
18 : * in the file COPYING-LGPL-2.1; if not, write to the Free Software
19 : * Foundation, Inc., 51 Franklin Street, Suite 500, Boston, MA 02110-1335, USA
20 : * You should have received a copy of the MPL along with this library
21 : * in the file COPYING-MPL-1.1
22 : *
23 : * The contents of this file are subject to the Mozilla Public License
24 : * Version 1.1 (the "License"); you may not use this file except in
25 : * compliance with the License. You may obtain a copy of the License at
26 : * http://www.mozilla.org/MPL/
27 : *
28 : * This software is distributed on an "AS IS" basis, WITHOUT WARRANTY
29 : * OF ANY KIND, either express or implied. See the LGPL or the MPL for
30 : * the specific language governing rights and limitations.
31 : *
32 : * The Original Code is the cairo graphics library.
33 : *
34 : * The Initial Developer of the Original Code is Carl Worth
35 : *
36 : * Contributor(s):
37 : * Carl D. Worth <cworth@cworth.org>
38 : * M Joonas Pihlaja <jpihlaja@cc.helsinki.fi>
39 : * Chris Wilson <chris@chris-wilson.co.uk>
40 : */
41 :
42 : /* Provide definitions for standalone compilation */
43 : #include "cairoint.h"
44 :
45 : #include "cairo-error-private.h"
46 : #include "cairo-list-private.h"
47 : #include "cairo-freelist-private.h"
48 : #include "cairo-combsort-private.h"
49 :
50 : #include <setjmp.h>
51 :
52 : #define STEP_X CAIRO_FIXED_ONE
53 : #define STEP_Y CAIRO_FIXED_ONE
54 : #define UNROLL3(x) x x x
55 :
56 : #define STEP_XY (2*STEP_X*STEP_Y) /* Unit area in the step. */
57 : #define AREA_TO_ALPHA(c) (((c)*255 + STEP_XY/2) / STEP_XY)
58 :
59 : typedef struct _cairo_bo_intersect_ordinate {
60 : int32_t ordinate;
61 : enum { EXACT, INEXACT } exactness;
62 : } cairo_bo_intersect_ordinate_t;
63 :
64 : typedef struct _cairo_bo_intersect_point {
65 : cairo_bo_intersect_ordinate_t x;
66 : cairo_bo_intersect_ordinate_t y;
67 : } cairo_bo_intersect_point_t;
68 :
69 : struct quorem {
70 : cairo_fixed_t quo;
71 : cairo_fixed_t rem;
72 : };
73 :
74 : struct run {
75 : struct run *next;
76 : int sign;
77 : cairo_fixed_t y;
78 : };
79 :
80 : typedef struct edge {
81 : cairo_list_t link;
82 :
83 : cairo_edge_t edge;
84 :
85 : /* Current x coordinate and advancement.
86 : * Initialised to the x coordinate of the top of the
87 : * edge. The quotient is in cairo_fixed_t units and the
88 : * remainder is mod dy in cairo_fixed_t units.
89 : */
90 : cairo_fixed_t dy;
91 : struct quorem x;
92 : struct quorem dxdy;
93 : struct quorem dxdy_full;
94 :
95 : cairo_bool_t vertical;
96 : unsigned int flags;
97 :
98 : int current_sign;
99 : struct run *runs;
100 : } edge_t;
101 :
102 : enum {
103 : START = 0x1,
104 : STOP = 0x2,
105 : };
106 :
107 : /* the parent is always given by index/2 */
108 : #define PQ_PARENT_INDEX(i) ((i) >> 1)
109 : #define PQ_FIRST_ENTRY 1
110 :
111 : /* left and right children are index * 2 and (index * 2) +1 respectively */
112 : #define PQ_LEFT_CHILD_INDEX(i) ((i) << 1)
113 :
114 : typedef enum {
115 : EVENT_TYPE_STOP,
116 : EVENT_TYPE_INTERSECTION,
117 : EVENT_TYPE_START
118 : } event_type_t;
119 :
120 : typedef struct _event {
121 : cairo_fixed_t y;
122 : event_type_t type;
123 : } event_t;
124 :
125 : typedef struct _start_event {
126 : cairo_fixed_t y;
127 : event_type_t type;
128 : edge_t *edge;
129 : } start_event_t;
130 :
131 : typedef struct _queue_event {
132 : cairo_fixed_t y;
133 : event_type_t type;
134 : edge_t *e1;
135 : edge_t *e2;
136 : } queue_event_t;
137 :
138 : typedef struct _pqueue {
139 : int size, max_size;
140 :
141 : event_t **elements;
142 : event_t *elements_embedded[1024];
143 : } pqueue_t;
144 :
145 : struct cell {
146 : struct cell *prev;
147 : struct cell *next;
148 : int x;
149 : int uncovered_area;
150 : int covered_height;
151 : };
152 :
153 : typedef struct _sweep_line {
154 : cairo_list_t active;
155 : cairo_list_t stopped;
156 : cairo_list_t *insert_cursor;
157 : cairo_bool_t is_vertical;
158 :
159 : cairo_fixed_t current_row;
160 : cairo_fixed_t current_subrow;
161 :
162 : struct coverage {
163 : struct cell head;
164 : struct cell tail;
165 :
166 : struct cell *cursor;
167 : int count;
168 :
169 : cairo_freepool_t pool;
170 : } coverage;
171 :
172 : struct event_queue {
173 : pqueue_t pq;
174 : event_t **start_events;
175 :
176 : cairo_freepool_t pool;
177 : } queue;
178 :
179 : cairo_freepool_t runs;
180 :
181 : jmp_buf unwind;
182 : } sweep_line_t;
183 :
184 : cairo_always_inline static struct quorem
185 : floored_divrem (int a, int b)
186 : {
187 : struct quorem qr;
188 0 : qr.quo = a/b;
189 0 : qr.rem = a%b;
190 0 : if ((a^b)<0 && qr.rem) {
191 0 : qr.quo--;
192 0 : qr.rem += b;
193 : }
194 0 : return qr;
195 : }
196 :
197 : static struct quorem
198 0 : floored_muldivrem(int x, int a, int b)
199 : {
200 : struct quorem qr;
201 0 : long long xa = (long long)x*a;
202 0 : qr.quo = xa/b;
203 0 : qr.rem = xa%b;
204 0 : if ((xa>=0) != (b>=0) && qr.rem) {
205 0 : qr.quo--;
206 0 : qr.rem += b;
207 : }
208 0 : return qr;
209 : }
210 :
211 : static cairo_fixed_t
212 0 : line_compute_intersection_x_for_y (const cairo_line_t *line,
213 : cairo_fixed_t y)
214 : {
215 : cairo_fixed_t x, dy;
216 :
217 0 : if (y == line->p1.y)
218 0 : return line->p1.x;
219 0 : if (y == line->p2.y)
220 0 : return line->p2.x;
221 :
222 0 : x = line->p1.x;
223 0 : dy = line->p2.y - line->p1.y;
224 0 : if (dy != 0) {
225 0 : x += _cairo_fixed_mul_div_floor (y - line->p1.y,
226 0 : line->p2.x - line->p1.x,
227 : dy);
228 : }
229 :
230 0 : return x;
231 : }
232 :
233 : /*
234 : * We need to compare the x-coordinates of a pair of lines for a particular y,
235 : * without loss of precision.
236 : *
237 : * The x-coordinate along an edge for a given y is:
238 : * X = A_x + (Y - A_y) * A_dx / A_dy
239 : *
240 : * So the inequality we wish to test is:
241 : * A_x + (Y - A_y) * A_dx / A_dy ∘ B_x + (Y - B_y) * B_dx / B_dy,
242 : * where ∘ is our inequality operator.
243 : *
244 : * By construction, we know that A_dy and B_dy (and (Y - A_y), (Y - B_y)) are
245 : * all positive, so we can rearrange it thus without causing a sign change:
246 : * A_dy * B_dy * (A_x - B_x) ∘ (Y - B_y) * B_dx * A_dy
247 : * - (Y - A_y) * A_dx * B_dy
248 : *
249 : * Given the assumption that all the deltas fit within 32 bits, we can compute
250 : * this comparison directly using 128 bit arithmetic. For certain, but common,
251 : * input we can reduce this down to a single 32 bit compare by inspecting the
252 : * deltas.
253 : *
254 : * (And put the burden of the work on developing fast 128 bit ops, which are
255 : * required throughout the tessellator.)
256 : *
257 : * See the similar discussion for _slope_compare().
258 : */
259 : static int
260 0 : edges_compare_x_for_y_general (const cairo_edge_t *a,
261 : const cairo_edge_t *b,
262 : int32_t y)
263 : {
264 : /* XXX: We're assuming here that dx and dy will still fit in 32
265 : * bits. That's not true in general as there could be overflow. We
266 : * should prevent that before the tessellation algorithm
267 : * begins.
268 : */
269 : int32_t dx;
270 : int32_t adx, ady;
271 : int32_t bdx, bdy;
272 : enum {
273 : HAVE_NONE = 0x0,
274 : HAVE_DX = 0x1,
275 : HAVE_ADX = 0x2,
276 : HAVE_DX_ADX = HAVE_DX | HAVE_ADX,
277 : HAVE_BDX = 0x4,
278 : HAVE_DX_BDX = HAVE_DX | HAVE_BDX,
279 : HAVE_ADX_BDX = HAVE_ADX | HAVE_BDX,
280 : HAVE_ALL = HAVE_DX | HAVE_ADX | HAVE_BDX
281 0 : } have_dx_adx_bdx = HAVE_ALL;
282 :
283 : /* don't bother solving for abscissa if the edges' bounding boxes
284 : * can be used to order them. */
285 : {
286 : int32_t amin, amax;
287 : int32_t bmin, bmax;
288 0 : if (a->line.p1.x < a->line.p2.x) {
289 0 : amin = a->line.p1.x;
290 0 : amax = a->line.p2.x;
291 : } else {
292 0 : amin = a->line.p2.x;
293 0 : amax = a->line.p1.x;
294 : }
295 0 : if (b->line.p1.x < b->line.p2.x) {
296 0 : bmin = b->line.p1.x;
297 0 : bmax = b->line.p2.x;
298 : } else {
299 0 : bmin = b->line.p2.x;
300 0 : bmax = b->line.p1.x;
301 : }
302 0 : if (amax < bmin) return -1;
303 0 : if (amin > bmax) return +1;
304 : }
305 :
306 0 : ady = a->line.p2.y - a->line.p1.y;
307 0 : adx = a->line.p2.x - a->line.p1.x;
308 0 : if (adx == 0)
309 0 : have_dx_adx_bdx &= ~HAVE_ADX;
310 :
311 0 : bdy = b->line.p2.y - b->line.p1.y;
312 0 : bdx = b->line.p2.x - b->line.p1.x;
313 0 : if (bdx == 0)
314 0 : have_dx_adx_bdx &= ~HAVE_BDX;
315 :
316 0 : dx = a->line.p1.x - b->line.p1.x;
317 0 : if (dx == 0)
318 0 : have_dx_adx_bdx &= ~HAVE_DX;
319 :
320 : #define L _cairo_int64x32_128_mul (_cairo_int32x32_64_mul (ady, bdy), dx)
321 : #define A _cairo_int64x32_128_mul (_cairo_int32x32_64_mul (adx, bdy), y - a->line.p1.y)
322 : #define B _cairo_int64x32_128_mul (_cairo_int32x32_64_mul (bdx, ady), y - b->line.p1.y)
323 0 : switch (have_dx_adx_bdx) {
324 : default:
325 : case HAVE_NONE:
326 0 : return 0;
327 : case HAVE_DX:
328 : /* A_dy * B_dy * (A_x - B_x) ∘ 0 */
329 0 : return dx; /* ady * bdy is positive definite */
330 : case HAVE_ADX:
331 : /* 0 ∘ - (Y - A_y) * A_dx * B_dy */
332 0 : return adx; /* bdy * (y - a->top.y) is positive definite */
333 : case HAVE_BDX:
334 : /* 0 ∘ (Y - B_y) * B_dx * A_dy */
335 0 : return -bdx; /* ady * (y - b->top.y) is positive definite */
336 : case HAVE_ADX_BDX:
337 : /* 0 ∘ (Y - B_y) * B_dx * A_dy - (Y - A_y) * A_dx * B_dy */
338 0 : if ((adx ^ bdx) < 0) {
339 0 : return adx;
340 0 : } else if (a->line.p1.y == b->line.p1.y) { /* common origin */
341 : cairo_int64_t adx_bdy, bdx_ady;
342 :
343 : /* ∴ A_dx * B_dy ∘ B_dx * A_dy */
344 :
345 0 : adx_bdy = _cairo_int32x32_64_mul (adx, bdy);
346 0 : bdx_ady = _cairo_int32x32_64_mul (bdx, ady);
347 :
348 0 : return _cairo_int64_cmp (adx_bdy, bdx_ady);
349 : } else
350 0 : return _cairo_int128_cmp (A, B);
351 : case HAVE_DX_ADX:
352 : /* A_dy * (A_x - B_x) ∘ - (Y - A_y) * A_dx */
353 0 : if ((-adx ^ dx) < 0) {
354 0 : return dx;
355 : } else {
356 : cairo_int64_t ady_dx, dy_adx;
357 :
358 0 : ady_dx = _cairo_int32x32_64_mul (ady, dx);
359 0 : dy_adx = _cairo_int32x32_64_mul (a->line.p1.y - y, adx);
360 :
361 0 : return _cairo_int64_cmp (ady_dx, dy_adx);
362 : }
363 : case HAVE_DX_BDX:
364 : /* B_dy * (A_x - B_x) ∘ (Y - B_y) * B_dx */
365 0 : if ((bdx ^ dx) < 0) {
366 0 : return dx;
367 : } else {
368 : cairo_int64_t bdy_dx, dy_bdx;
369 :
370 0 : bdy_dx = _cairo_int32x32_64_mul (bdy, dx);
371 0 : dy_bdx = _cairo_int32x32_64_mul (y - b->line.p1.y, bdx);
372 :
373 0 : return _cairo_int64_cmp (bdy_dx, dy_bdx);
374 : }
375 : case HAVE_ALL:
376 : /* XXX try comparing (a->line.p2.x - b->line.p2.x) et al */
377 0 : return _cairo_int128_cmp (L, _cairo_int128_sub (B, A));
378 : }
379 : #undef B
380 : #undef A
381 : #undef L
382 : }
383 :
384 : /*
385 : * We need to compare the x-coordinate of a line for a particular y wrt to a
386 : * given x, without loss of precision.
387 : *
388 : * The x-coordinate along an edge for a given y is:
389 : * X = A_x + (Y - A_y) * A_dx / A_dy
390 : *
391 : * So the inequality we wish to test is:
392 : * A_x + (Y - A_y) * A_dx / A_dy ∘ X
393 : * where ∘ is our inequality operator.
394 : *
395 : * By construction, we know that A_dy (and (Y - A_y)) are
396 : * all positive, so we can rearrange it thus without causing a sign change:
397 : * (Y - A_y) * A_dx ∘ (X - A_x) * A_dy
398 : *
399 : * Given the assumption that all the deltas fit within 32 bits, we can compute
400 : * this comparison directly using 64 bit arithmetic.
401 : *
402 : * See the similar discussion for _slope_compare() and
403 : * edges_compare_x_for_y_general().
404 : */
405 : static int
406 0 : edge_compare_for_y_against_x (const cairo_edge_t *a,
407 : int32_t y,
408 : int32_t x)
409 : {
410 : int32_t adx, ady;
411 : int32_t dx, dy;
412 : cairo_int64_t L, R;
413 :
414 0 : if (a->line.p1.x <= a->line.p2.x) {
415 0 : if (x < a->line.p1.x)
416 0 : return 1;
417 0 : if (x > a->line.p2.x)
418 0 : return -1;
419 : } else {
420 0 : if (x < a->line.p2.x)
421 0 : return 1;
422 0 : if (x > a->line.p1.x)
423 0 : return -1;
424 : }
425 :
426 0 : adx = a->line.p2.x - a->line.p1.x;
427 0 : dx = x - a->line.p1.x;
428 :
429 0 : if (adx == 0)
430 0 : return -dx;
431 0 : if (dx == 0 || (adx ^ dx) < 0)
432 0 : return adx;
433 :
434 0 : dy = y - a->line.p1.y;
435 0 : ady = a->line.p2.y - a->line.p1.y;
436 :
437 0 : L = _cairo_int32x32_64_mul (dy, adx);
438 0 : R = _cairo_int32x32_64_mul (dx, ady);
439 :
440 0 : return _cairo_int64_cmp (L, R);
441 : }
442 :
443 : static int
444 0 : edges_compare_x_for_y (const cairo_edge_t *a,
445 : const cairo_edge_t *b,
446 : int32_t y)
447 : {
448 : /* If the sweep-line is currently on an end-point of a line,
449 : * then we know its precise x value (and considering that we often need to
450 : * compare events at end-points, this happens frequently enough to warrant
451 : * special casing).
452 : */
453 : enum {
454 : HAVE_NEITHER = 0x0,
455 : HAVE_AX = 0x1,
456 : HAVE_BX = 0x2,
457 : HAVE_BOTH = HAVE_AX | HAVE_BX
458 0 : } have_ax_bx = HAVE_BOTH;
459 : int32_t ax, bx;
460 :
461 : /* XXX given we have x and dx? */
462 :
463 0 : if (y == a->line.p1.y)
464 0 : ax = a->line.p1.x;
465 0 : else if (y == a->line.p2.y)
466 0 : ax = a->line.p2.x;
467 : else
468 0 : have_ax_bx &= ~HAVE_AX;
469 :
470 0 : if (y == b->line.p1.y)
471 0 : bx = b->line.p1.x;
472 0 : else if (y == b->line.p2.y)
473 0 : bx = b->line.p2.x;
474 : else
475 0 : have_ax_bx &= ~HAVE_BX;
476 :
477 0 : switch (have_ax_bx) {
478 : default:
479 : case HAVE_NEITHER:
480 0 : return edges_compare_x_for_y_general (a, b, y);
481 : case HAVE_AX:
482 0 : return -edge_compare_for_y_against_x (b, y, ax);
483 : case HAVE_BX:
484 0 : return edge_compare_for_y_against_x (a, y, bx);
485 : case HAVE_BOTH:
486 0 : return ax - bx;
487 : }
488 : }
489 :
490 : static inline int
491 0 : slope_compare (const edge_t *a,
492 : const edge_t *b)
493 : {
494 : cairo_int64_t L, R;
495 : int cmp;
496 :
497 0 : cmp = a->dxdy.quo - b->dxdy.quo;
498 0 : if (cmp)
499 0 : return cmp;
500 :
501 0 : if (a->dxdy.rem == 0)
502 0 : return -b->dxdy.rem;
503 0 : if (b->dxdy.rem == 0)
504 0 : return a->dxdy.rem;
505 :
506 0 : L = _cairo_int32x32_64_mul (b->dy, a->dxdy.rem);
507 0 : R = _cairo_int32x32_64_mul (a->dy, b->dxdy.rem);
508 0 : return _cairo_int64_cmp (L, R);
509 : }
510 :
511 : static inline int
512 0 : line_equal (const cairo_line_t *a, const cairo_line_t *b)
513 : {
514 0 : return a->p1.x == b->p1.x && a->p1.y == b->p1.y &&
515 0 : a->p2.x == b->p2.x && a->p2.y == b->p2.y;
516 : }
517 :
518 : static inline int
519 0 : sweep_line_compare_edges (const edge_t *a,
520 : const edge_t *b,
521 : cairo_fixed_t y)
522 : {
523 : int cmp;
524 :
525 0 : if (line_equal (&a->edge.line, &b->edge.line))
526 0 : return 0;
527 :
528 0 : cmp = edges_compare_x_for_y (&a->edge, &b->edge, y);
529 0 : if (cmp)
530 0 : return cmp;
531 :
532 0 : return slope_compare (a, b);
533 : }
534 :
535 : static inline cairo_int64_t
536 0 : det32_64 (int32_t a, int32_t b,
537 : int32_t c, int32_t d)
538 : {
539 : /* det = a * d - b * c */
540 0 : return _cairo_int64_sub (_cairo_int32x32_64_mul (a, d),
541 : _cairo_int32x32_64_mul (b, c));
542 : }
543 :
544 : static inline cairo_int128_t
545 0 : det64x32_128 (cairo_int64_t a, int32_t b,
546 : cairo_int64_t c, int32_t d)
547 : {
548 : /* det = a * d - b * c */
549 0 : return _cairo_int128_sub (_cairo_int64x32_128_mul (a, d),
550 : _cairo_int64x32_128_mul (c, b));
551 : }
552 :
553 : /* Compute the intersection of two lines as defined by two edges. The
554 : * result is provided as a coordinate pair of 128-bit integers.
555 : *
556 : * Returns %CAIRO_BO_STATUS_INTERSECTION if there is an intersection or
557 : * %CAIRO_BO_STATUS_PARALLEL if the two lines are exactly parallel.
558 : */
559 : static cairo_bool_t
560 0 : intersect_lines (const edge_t *a, const edge_t *b,
561 : cairo_bo_intersect_point_t *intersection)
562 : {
563 : cairo_int64_t a_det, b_det;
564 :
565 : /* XXX: We're assuming here that dx and dy will still fit in 32
566 : * bits. That's not true in general as there could be overflow. We
567 : * should prevent that before the tessellation algorithm begins.
568 : * What we're doing to mitigate this is to perform clamping in
569 : * cairo_bo_tessellate_polygon().
570 : */
571 0 : int32_t dx1 = a->edge.line.p1.x - a->edge.line.p2.x;
572 0 : int32_t dy1 = a->edge.line.p1.y - a->edge.line.p2.y;
573 :
574 0 : int32_t dx2 = b->edge.line.p1.x - b->edge.line.p2.x;
575 0 : int32_t dy2 = b->edge.line.p1.y - b->edge.line.p2.y;
576 :
577 : cairo_int64_t den_det;
578 : cairo_int64_t R;
579 : cairo_quorem64_t qr;
580 :
581 0 : den_det = det32_64 (dx1, dy1, dx2, dy2);
582 :
583 : /* Q: Can we determine that the lines do not intersect (within range)
584 : * much more cheaply than computing the intersection point i.e. by
585 : * avoiding the division?
586 : *
587 : * X = ax + t * adx = bx + s * bdx;
588 : * Y = ay + t * ady = by + s * bdy;
589 : * ∴ t * (ady*bdx - bdy*adx) = bdx * (by - ay) + bdy * (ax - bx)
590 : * => t * L = R
591 : *
592 : * Therefore we can reject any intersection (under the criteria for
593 : * valid intersection events) if:
594 : * L^R < 0 => t < 0, or
595 : * L<R => t > 1
596 : *
597 : * (where top/bottom must at least extend to the line endpoints).
598 : *
599 : * A similar substitution can be performed for s, yielding:
600 : * s * (ady*bdx - bdy*adx) = ady * (ax - bx) - adx * (ay - by)
601 : */
602 0 : R = det32_64 (dx2, dy2,
603 0 : b->edge.line.p1.x - a->edge.line.p1.x,
604 0 : b->edge.line.p1.y - a->edge.line.p1.y);
605 0 : if (_cairo_int64_negative (den_det)) {
606 0 : if (_cairo_int64_ge (den_det, R))
607 0 : return FALSE;
608 : } else {
609 0 : if (_cairo_int64_le (den_det, R))
610 0 : return FALSE;
611 : }
612 :
613 0 : R = det32_64 (dy1, dx1,
614 0 : a->edge.line.p1.y - b->edge.line.p1.y,
615 0 : a->edge.line.p1.x - b->edge.line.p1.x);
616 0 : if (_cairo_int64_negative (den_det)) {
617 0 : if (_cairo_int64_ge (den_det, R))
618 0 : return FALSE;
619 : } else {
620 0 : if (_cairo_int64_le (den_det, R))
621 0 : return FALSE;
622 : }
623 :
624 : /* We now know that the two lines should intersect within range. */
625 :
626 0 : a_det = det32_64 (a->edge.line.p1.x, a->edge.line.p1.y,
627 : a->edge.line.p2.x, a->edge.line.p2.y);
628 0 : b_det = det32_64 (b->edge.line.p1.x, b->edge.line.p1.y,
629 : b->edge.line.p2.x, b->edge.line.p2.y);
630 :
631 : /* x = det (a_det, dx1, b_det, dx2) / den_det */
632 0 : qr = _cairo_int_96by64_32x64_divrem (det64x32_128 (a_det, dx1,
633 : b_det, dx2),
634 : den_det);
635 0 : if (_cairo_int64_eq (qr.rem, den_det))
636 0 : return FALSE;
637 : #if 0
638 : intersection->x.exactness = _cairo_int64_is_zero (qr.rem) ? EXACT : INEXACT;
639 : #else
640 0 : intersection->x.exactness = EXACT;
641 0 : if (! _cairo_int64_is_zero (qr.rem)) {
642 0 : if (_cairo_int64_negative (den_det) ^ _cairo_int64_negative (qr.rem))
643 0 : qr.rem = _cairo_int64_negate (qr.rem);
644 0 : qr.rem = _cairo_int64_mul (qr.rem, _cairo_int32_to_int64 (2));
645 0 : if (_cairo_int64_ge (qr.rem, den_det)) {
646 0 : qr.quo = _cairo_int64_add (qr.quo,
647 : _cairo_int32_to_int64 (_cairo_int64_negative (qr.quo) ? -1 : 1));
648 : } else
649 0 : intersection->x.exactness = INEXACT;
650 : }
651 : #endif
652 0 : intersection->x.ordinate = _cairo_int64_to_int32 (qr.quo);
653 :
654 : /* y = det (a_det, dy1, b_det, dy2) / den_det */
655 0 : qr = _cairo_int_96by64_32x64_divrem (det64x32_128 (a_det, dy1,
656 : b_det, dy2),
657 : den_det);
658 0 : if (_cairo_int64_eq (qr.rem, den_det))
659 0 : return FALSE;
660 : #if 0
661 : intersection->y.exactness = _cairo_int64_is_zero (qr.rem) ? EXACT : INEXACT;
662 : #else
663 0 : intersection->y.exactness = EXACT;
664 0 : if (! _cairo_int64_is_zero (qr.rem)) {
665 : /* compute ceiling away from zero */
666 0 : qr.quo = _cairo_int64_add (qr.quo,
667 : _cairo_int32_to_int64 (_cairo_int64_negative (qr.quo) ? -1 : 1));
668 0 : intersection->y.exactness = INEXACT;
669 : }
670 : #endif
671 0 : intersection->y.ordinate = _cairo_int64_to_int32 (qr.quo);
672 :
673 0 : return TRUE;
674 : }
675 :
676 : static int
677 0 : bo_intersect_ordinate_32_compare (int32_t a, int32_t b, int exactness)
678 : {
679 : int cmp;
680 :
681 : /* First compare the quotient */
682 0 : cmp = a - b;
683 0 : if (cmp)
684 0 : return cmp;
685 :
686 : /* With quotient identical, if remainder is 0 then compare equal */
687 : /* Otherwise, the non-zero remainder makes a > b */
688 0 : return -(INEXACT == exactness);
689 : }
690 :
691 : /* Does the given edge contain the given point. The point must already
692 : * be known to be contained within the line determined by the edge,
693 : * (most likely the point results from an intersection of this edge
694 : * with another).
695 : *
696 : * If we had exact arithmetic, then this function would simply be a
697 : * matter of examining whether the y value of the point lies within
698 : * the range of y values of the edge. But since intersection points
699 : * are not exact due to being rounded to the nearest integer within
700 : * the available precision, we must also examine the x value of the
701 : * point.
702 : *
703 : * The definition of "contains" here is that the given intersection
704 : * point will be seen by the sweep line after the start event for the
705 : * given edge and before the stop event for the edge. See the comments
706 : * in the implementation for more details.
707 : */
708 : static cairo_bool_t
709 0 : bo_edge_contains_intersect_point (const edge_t *edge,
710 : cairo_bo_intersect_point_t *point)
711 : {
712 : int cmp_top, cmp_bottom;
713 :
714 : /* XXX: When running the actual algorithm, we don't actually need to
715 : * compare against edge->top at all here, since any intersection above
716 : * top is eliminated early via a slope comparison. We're leaving these
717 : * here for now only for the sake of the quadratic-time intersection
718 : * finder which needs them.
719 : */
720 :
721 0 : cmp_top = bo_intersect_ordinate_32_compare (point->y.ordinate,
722 : edge->edge.top,
723 0 : point->y.exactness);
724 0 : if (cmp_top < 0)
725 0 : return FALSE;
726 :
727 0 : cmp_bottom = bo_intersect_ordinate_32_compare (point->y.ordinate,
728 : edge->edge.bottom,
729 0 : point->y.exactness);
730 0 : if (cmp_bottom > 0)
731 0 : return FALSE;
732 :
733 0 : if (cmp_top > 0 && cmp_bottom < 0)
734 0 : return TRUE;
735 :
736 : /* At this stage, the point lies on the same y value as either
737 : * edge->top or edge->bottom, so we have to examine the x value in
738 : * order to properly determine containment. */
739 :
740 : /* If the y value of the point is the same as the y value of the
741 : * top of the edge, then the x value of the point must be greater
742 : * to be considered as inside the edge. Similarly, if the y value
743 : * of the point is the same as the y value of the bottom of the
744 : * edge, then the x value of the point must be less to be
745 : * considered as inside. */
746 :
747 0 : if (cmp_top == 0) {
748 : cairo_fixed_t top_x;
749 :
750 0 : top_x = line_compute_intersection_x_for_y (&edge->edge.line,
751 : edge->edge.top);
752 0 : return bo_intersect_ordinate_32_compare (top_x, point->x.ordinate, point->x.exactness) < 0;
753 : } else { /* cmp_bottom == 0 */
754 : cairo_fixed_t bot_x;
755 :
756 0 : bot_x = line_compute_intersection_x_for_y (&edge->edge.line,
757 : edge->edge.bottom);
758 0 : return bo_intersect_ordinate_32_compare (point->x.ordinate, bot_x, point->x.exactness) < 0;
759 : }
760 : }
761 :
762 : static cairo_bool_t
763 0 : edge_intersect (const edge_t *a,
764 : const edge_t *b,
765 : cairo_point_t *intersection)
766 : {
767 : cairo_bo_intersect_point_t quorem;
768 :
769 0 : if (! intersect_lines (a, b, &quorem))
770 0 : return FALSE;
771 :
772 0 : if (a->edge.top != a->edge.line.p1.y || a->edge.bottom != a->edge.line.p2.y) {
773 0 : if (! bo_edge_contains_intersect_point (a, &quorem))
774 0 : return FALSE;
775 : }
776 :
777 0 : if (b->edge.top != b->edge.line.p1.y || b->edge.bottom != b->edge.line.p2.y) {
778 0 : if (! bo_edge_contains_intersect_point (b, &quorem))
779 0 : return FALSE;
780 : }
781 :
782 : /* Now that we've correctly compared the intersection point and
783 : * determined that it lies within the edge, then we know that we
784 : * no longer need any more bits of storage for the intersection
785 : * than we do for our edge coordinates. We also no longer need the
786 : * remainder from the division. */
787 0 : intersection->x = quorem.x.ordinate;
788 0 : intersection->y = quorem.y.ordinate;
789 :
790 0 : return TRUE;
791 : }
792 :
793 : static inline int
794 0 : event_compare (const event_t *a, const event_t *b)
795 : {
796 0 : return a->y - b->y;
797 : }
798 :
799 : static void
800 0 : pqueue_init (pqueue_t *pq)
801 : {
802 0 : pq->max_size = ARRAY_LENGTH (pq->elements_embedded);
803 0 : pq->size = 0;
804 :
805 0 : pq->elements = pq->elements_embedded;
806 0 : }
807 :
808 : static void
809 0 : pqueue_fini (pqueue_t *pq)
810 : {
811 0 : if (pq->elements != pq->elements_embedded)
812 0 : free (pq->elements);
813 0 : }
814 :
815 : static cairo_bool_t
816 0 : pqueue_grow (pqueue_t *pq)
817 : {
818 : event_t **new_elements;
819 0 : pq->max_size *= 2;
820 :
821 0 : if (pq->elements == pq->elements_embedded) {
822 0 : new_elements = _cairo_malloc_ab (pq->max_size,
823 : sizeof (event_t *));
824 0 : if (unlikely (new_elements == NULL))
825 0 : return FALSE;
826 :
827 0 : memcpy (new_elements, pq->elements_embedded,
828 : sizeof (pq->elements_embedded));
829 : } else {
830 0 : new_elements = _cairo_realloc_ab (pq->elements,
831 : pq->max_size,
832 : sizeof (event_t *));
833 0 : if (unlikely (new_elements == NULL))
834 0 : return FALSE;
835 : }
836 :
837 0 : pq->elements = new_elements;
838 0 : return TRUE;
839 : }
840 :
841 : static inline void
842 0 : pqueue_push (sweep_line_t *sweep_line, event_t *event)
843 : {
844 : event_t **elements;
845 : int i, parent;
846 :
847 0 : if (unlikely (sweep_line->queue.pq.size + 1 == sweep_line->queue.pq.max_size)) {
848 0 : if (unlikely (! pqueue_grow (&sweep_line->queue.pq))) {
849 0 : longjmp (sweep_line->unwind,
850 0 : _cairo_error (CAIRO_STATUS_NO_MEMORY));
851 : }
852 : }
853 :
854 0 : elements = sweep_line->queue.pq.elements;
855 0 : for (i = ++sweep_line->queue.pq.size;
856 0 : i != PQ_FIRST_ENTRY &&
857 0 : event_compare (event,
858 0 : elements[parent = PQ_PARENT_INDEX (i)]) < 0;
859 0 : i = parent)
860 : {
861 0 : elements[i] = elements[parent];
862 : }
863 :
864 0 : elements[i] = event;
865 0 : }
866 :
867 : static inline void
868 0 : pqueue_pop (pqueue_t *pq)
869 : {
870 0 : event_t **elements = pq->elements;
871 : event_t *tail;
872 : int child, i;
873 :
874 0 : tail = elements[pq->size--];
875 0 : if (pq->size == 0) {
876 0 : elements[PQ_FIRST_ENTRY] = NULL;
877 0 : return;
878 : }
879 :
880 0 : for (i = PQ_FIRST_ENTRY;
881 0 : (child = PQ_LEFT_CHILD_INDEX (i)) <= pq->size;
882 0 : i = child)
883 : {
884 0 : if (child != pq->size &&
885 0 : event_compare (elements[child+1],
886 0 : elements[child]) < 0)
887 : {
888 0 : child++;
889 : }
890 :
891 0 : if (event_compare (elements[child], tail) >= 0)
892 0 : break;
893 :
894 0 : elements[i] = elements[child];
895 : }
896 0 : elements[i] = tail;
897 : }
898 :
899 : static inline void
900 0 : event_insert (sweep_line_t *sweep_line,
901 : event_type_t type,
902 : edge_t *e1,
903 : edge_t *e2,
904 : cairo_fixed_t y)
905 : {
906 : queue_event_t *event;
907 :
908 0 : event = _cairo_freepool_alloc (&sweep_line->queue.pool);
909 0 : if (unlikely (event == NULL)) {
910 0 : longjmp (sweep_line->unwind,
911 0 : _cairo_error (CAIRO_STATUS_NO_MEMORY));
912 : }
913 :
914 0 : event->y = y;
915 0 : event->type = type;
916 0 : event->e1 = e1;
917 0 : event->e2 = e2;
918 :
919 0 : pqueue_push (sweep_line, (event_t *) event);
920 0 : }
921 :
922 : static void
923 0 : event_delete (sweep_line_t *sweep_line,
924 : event_t *event)
925 : {
926 0 : _cairo_freepool_free (&sweep_line->queue.pool, event);
927 0 : }
928 :
929 : static inline event_t *
930 0 : event_next (sweep_line_t *sweep_line)
931 : {
932 : event_t *event, *cmp;
933 :
934 0 : event = sweep_line->queue.pq.elements[PQ_FIRST_ENTRY];
935 0 : cmp = *sweep_line->queue.start_events;
936 0 : if (event == NULL ||
937 0 : (cmp != NULL && event_compare (cmp, event) < 0))
938 : {
939 0 : event = cmp;
940 0 : sweep_line->queue.start_events++;
941 : }
942 : else
943 : {
944 0 : pqueue_pop (&sweep_line->queue.pq);
945 : }
946 :
947 0 : return event;
948 : }
949 :
950 0 : CAIRO_COMBSORT_DECLARE (start_event_sort, event_t *, event_compare)
951 :
952 : static inline void
953 0 : event_insert_stop (sweep_line_t *sweep_line,
954 : edge_t *edge)
955 : {
956 0 : event_insert (sweep_line,
957 : EVENT_TYPE_STOP,
958 : edge, NULL,
959 : edge->edge.bottom);
960 0 : }
961 :
962 : static inline void
963 0 : event_insert_if_intersect_below_current_y (sweep_line_t *sweep_line,
964 : edge_t *left,
965 : edge_t *right)
966 : {
967 : cairo_point_t intersection;
968 :
969 : /* start points intersect */
970 0 : if (left->edge.line.p1.x == right->edge.line.p1.x &&
971 0 : left->edge.line.p1.y == right->edge.line.p1.y)
972 : {
973 0 : return;
974 : }
975 :
976 : /* end points intersect, process DELETE events first */
977 0 : if (left->edge.line.p2.x == right->edge.line.p2.x &&
978 0 : left->edge.line.p2.y == right->edge.line.p2.y)
979 : {
980 0 : return;
981 : }
982 :
983 0 : if (slope_compare (left, right) <= 0)
984 0 : return;
985 :
986 0 : if (! edge_intersect (left, right, &intersection))
987 0 : return;
988 :
989 0 : event_insert (sweep_line,
990 : EVENT_TYPE_INTERSECTION,
991 : left, right,
992 : intersection.y);
993 : }
994 :
995 : static inline edge_t *
996 0 : link_to_edge (cairo_list_t *link)
997 : {
998 0 : return (edge_t *) link;
999 : }
1000 :
1001 : static void
1002 0 : sweep_line_insert (sweep_line_t *sweep_line,
1003 : edge_t *edge)
1004 : {
1005 : cairo_list_t *pos;
1006 0 : cairo_fixed_t y = sweep_line->current_subrow;
1007 :
1008 0 : pos = sweep_line->insert_cursor;
1009 0 : if (pos == &sweep_line->active)
1010 0 : pos = sweep_line->active.next;
1011 0 : if (pos != &sweep_line->active) {
1012 : int cmp;
1013 :
1014 0 : cmp = sweep_line_compare_edges (link_to_edge (pos),
1015 : edge,
1016 : y);
1017 0 : if (cmp < 0) {
1018 0 : while (pos->next != &sweep_line->active &&
1019 0 : sweep_line_compare_edges (link_to_edge (pos->next),
1020 : edge,
1021 : y) < 0)
1022 : {
1023 0 : pos = pos->next;
1024 : }
1025 0 : } else if (cmp > 0) {
1026 : do {
1027 0 : pos = pos->prev;
1028 0 : } while (pos != &sweep_line->active &&
1029 0 : sweep_line_compare_edges (link_to_edge (pos),
1030 : edge,
1031 0 : y) > 0);
1032 : }
1033 : }
1034 0 : cairo_list_add (&edge->link, pos);
1035 0 : sweep_line->insert_cursor = &edge->link;
1036 0 : }
1037 :
1038 : inline static void
1039 0 : coverage_rewind (struct coverage *cells)
1040 : {
1041 0 : cells->cursor = &cells->head;
1042 0 : }
1043 :
1044 : static void
1045 0 : coverage_init (struct coverage *cells)
1046 : {
1047 0 : _cairo_freepool_init (&cells->pool,
1048 : sizeof (struct cell));
1049 0 : cells->head.prev = NULL;
1050 0 : cells->head.next = &cells->tail;
1051 0 : cells->head.x = INT_MIN;
1052 0 : cells->tail.prev = &cells->head;
1053 0 : cells->tail.next = NULL;
1054 0 : cells->tail.x = INT_MAX;
1055 0 : cells->count = 0;
1056 0 : coverage_rewind (cells);
1057 0 : }
1058 :
1059 : static void
1060 0 : coverage_fini (struct coverage *cells)
1061 : {
1062 0 : _cairo_freepool_fini (&cells->pool);
1063 0 : }
1064 :
1065 : inline static void
1066 0 : coverage_reset (struct coverage *cells)
1067 : {
1068 0 : cells->head.next = &cells->tail;
1069 0 : cells->tail.prev = &cells->head;
1070 0 : cells->count = 0;
1071 0 : _cairo_freepool_reset (&cells->pool);
1072 0 : coverage_rewind (cells);
1073 0 : }
1074 :
1075 : inline static struct cell *
1076 0 : coverage_alloc (sweep_line_t *sweep_line,
1077 : struct cell *tail,
1078 : int x)
1079 : {
1080 : struct cell *cell;
1081 :
1082 0 : cell = _cairo_freepool_alloc (&sweep_line->coverage.pool);
1083 0 : if (unlikely (NULL == cell)) {
1084 0 : longjmp (sweep_line->unwind,
1085 0 : _cairo_error (CAIRO_STATUS_NO_MEMORY));
1086 : }
1087 :
1088 0 : tail->prev->next = cell;
1089 0 : cell->prev = tail->prev;
1090 0 : cell->next = tail;
1091 0 : tail->prev = cell;
1092 0 : cell->x = x;
1093 0 : cell->uncovered_area = 0;
1094 0 : cell->covered_height = 0;
1095 0 : sweep_line->coverage.count++;
1096 0 : return cell;
1097 : }
1098 :
1099 : inline static struct cell *
1100 0 : coverage_find (sweep_line_t *sweep_line, int x)
1101 : {
1102 : struct cell *cell;
1103 :
1104 0 : cell = sweep_line->coverage.cursor;
1105 0 : if (unlikely (cell->x > x)) {
1106 : do {
1107 0 : if (cell->prev->x < x)
1108 0 : break;
1109 0 : cell = cell->prev;
1110 : } while (TRUE);
1111 : } else {
1112 0 : if (cell->x == x)
1113 0 : return cell;
1114 :
1115 : do {
1116 0 : UNROLL3({
1117 : cell = cell->next;
1118 : if (cell->x >= x)
1119 : break;
1120 : });
1121 : } while (TRUE);
1122 : }
1123 :
1124 0 : if (cell->x != x)
1125 0 : cell = coverage_alloc (sweep_line, cell, x);
1126 :
1127 0 : return sweep_line->coverage.cursor = cell;
1128 : }
1129 :
1130 : static void
1131 0 : coverage_render_cells (sweep_line_t *sweep_line,
1132 : cairo_fixed_t left, cairo_fixed_t right,
1133 : cairo_fixed_t y1, cairo_fixed_t y2,
1134 : int sign)
1135 : {
1136 : int fx1, fx2;
1137 : int ix1, ix2;
1138 : int dx, dy;
1139 :
1140 : /* Orient the edge left-to-right. */
1141 0 : dx = right - left;
1142 0 : if (dx >= 0) {
1143 0 : ix1 = _cairo_fixed_integer_part (left);
1144 0 : fx1 = _cairo_fixed_fractional_part (left);
1145 :
1146 0 : ix2 = _cairo_fixed_integer_part (right);
1147 0 : fx2 = _cairo_fixed_fractional_part (right);
1148 :
1149 0 : dy = y2 - y1;
1150 : } else {
1151 0 : ix1 = _cairo_fixed_integer_part (right);
1152 0 : fx1 = _cairo_fixed_fractional_part (right);
1153 :
1154 0 : ix2 = _cairo_fixed_integer_part (left);
1155 0 : fx2 = _cairo_fixed_fractional_part (left);
1156 :
1157 0 : dx = -dx;
1158 0 : sign = -sign;
1159 0 : dy = y1 - y2;
1160 0 : y1 = y2 - dy;
1161 0 : y2 = y1 + dy;
1162 : }
1163 :
1164 : /* Add coverage for all pixels [ix1,ix2] on this row crossed
1165 : * by the edge. */
1166 : {
1167 0 : struct quorem y = floored_divrem ((STEP_X - fx1)*dy, dx);
1168 : struct cell *cell;
1169 :
1170 0 : cell = sweep_line->coverage.cursor;
1171 0 : if (cell->x != ix1) {
1172 0 : if (unlikely (cell->x > ix1)) {
1173 : do {
1174 0 : if (cell->prev->x < ix1)
1175 0 : break;
1176 0 : cell = cell->prev;
1177 : } while (TRUE);
1178 : } else do {
1179 0 : UNROLL3({
1180 : if (cell->x >= ix1)
1181 : break;
1182 : cell = cell->next;
1183 : });
1184 : } while (TRUE);
1185 :
1186 0 : if (cell->x != ix1)
1187 0 : cell = coverage_alloc (sweep_line, cell, ix1);
1188 : }
1189 :
1190 0 : cell->uncovered_area += sign * y.quo * (STEP_X + fx1);
1191 0 : cell->covered_height += sign * y.quo;
1192 0 : y.quo += y1;
1193 :
1194 0 : cell = cell->next;
1195 0 : if (cell->x != ++ix1)
1196 0 : cell = coverage_alloc (sweep_line, cell, ix1);
1197 0 : if (ix1 < ix2) {
1198 0 : struct quorem dydx_full = floored_divrem (STEP_X*dy, dx);
1199 :
1200 : do {
1201 0 : cairo_fixed_t y_skip = dydx_full.quo;
1202 0 : y.rem += dydx_full.rem;
1203 0 : if (y.rem >= dx) {
1204 0 : ++y_skip;
1205 0 : y.rem -= dx;
1206 : }
1207 :
1208 0 : y.quo += y_skip;
1209 :
1210 0 : y_skip *= sign;
1211 0 : cell->covered_height += y_skip;
1212 0 : cell->uncovered_area += y_skip*STEP_X;
1213 :
1214 0 : cell = cell->next;
1215 0 : if (cell->x != ++ix1)
1216 0 : cell = coverage_alloc (sweep_line, cell, ix1);
1217 0 : } while (ix1 != ix2);
1218 : }
1219 0 : cell->uncovered_area += sign*(y2 - y.quo)*fx2;
1220 0 : cell->covered_height += sign*(y2 - y.quo);
1221 0 : sweep_line->coverage.cursor = cell;
1222 : }
1223 0 : }
1224 :
1225 : inline static void
1226 0 : full_inc_edge (edge_t *edge)
1227 : {
1228 0 : edge->x.quo += edge->dxdy_full.quo;
1229 0 : edge->x.rem += edge->dxdy_full.rem;
1230 0 : if (edge->x.rem >= 0) {
1231 0 : ++edge->x.quo;
1232 0 : edge->x.rem -= edge->dy;
1233 : }
1234 0 : }
1235 :
1236 : static void
1237 0 : full_add_edge (sweep_line_t *sweep_line, edge_t *edge, int sign)
1238 : {
1239 : struct cell *cell;
1240 : cairo_fixed_t x1, x2;
1241 : int ix1, ix2;
1242 : int frac;
1243 :
1244 0 : edge->current_sign = sign;
1245 :
1246 0 : ix1 = _cairo_fixed_integer_part (edge->x.quo);
1247 :
1248 0 : if (edge->vertical) {
1249 0 : frac = _cairo_fixed_fractional_part (edge->x.quo);
1250 0 : cell = coverage_find (sweep_line, ix1);
1251 0 : cell->covered_height += sign * STEP_Y;
1252 0 : cell->uncovered_area += sign * 2 * frac * STEP_Y;
1253 0 : return;
1254 : }
1255 :
1256 0 : x1 = edge->x.quo;
1257 0 : full_inc_edge (edge);
1258 0 : x2 = edge->x.quo;
1259 :
1260 0 : ix2 = _cairo_fixed_integer_part (edge->x.quo);
1261 :
1262 : /* Edge is entirely within a column? */
1263 0 : if (likely (ix1 == ix2)) {
1264 0 : frac = _cairo_fixed_fractional_part (x1) +
1265 0 : _cairo_fixed_fractional_part (x2);
1266 0 : cell = coverage_find (sweep_line, ix1);
1267 0 : cell->covered_height += sign * STEP_Y;
1268 0 : cell->uncovered_area += sign * frac * STEP_Y;
1269 0 : return;
1270 : }
1271 :
1272 0 : coverage_render_cells (sweep_line, x1, x2, 0, STEP_Y, sign);
1273 : }
1274 :
1275 : static void
1276 0 : full_nonzero (sweep_line_t *sweep_line)
1277 : {
1278 : cairo_list_t *pos;
1279 :
1280 0 : sweep_line->is_vertical = TRUE;
1281 0 : pos = sweep_line->active.next;
1282 : do {
1283 0 : edge_t *left = link_to_edge (pos), *right;
1284 0 : int winding = left->edge.dir;
1285 :
1286 0 : sweep_line->is_vertical &= left->vertical;
1287 :
1288 0 : pos = left->link.next;
1289 : do {
1290 0 : if (unlikely (pos == &sweep_line->active)) {
1291 0 : full_add_edge (sweep_line, left, +1);
1292 0 : return;
1293 : }
1294 :
1295 0 : right = link_to_edge (pos);
1296 0 : pos = pos->next;
1297 0 : sweep_line->is_vertical &= right->vertical;
1298 :
1299 0 : winding += right->edge.dir;
1300 0 : if (0 == winding) {
1301 0 : if (pos == &sweep_line->active ||
1302 0 : link_to_edge (pos)->x.quo != right->x.quo)
1303 : {
1304 : break;
1305 : }
1306 : }
1307 :
1308 0 : if (! right->vertical)
1309 0 : full_inc_edge (right);
1310 : } while (TRUE);
1311 :
1312 0 : full_add_edge (sweep_line, left, +1);
1313 0 : full_add_edge (sweep_line, right, -1);
1314 0 : } while (pos != &sweep_line->active);
1315 : }
1316 :
1317 : static void
1318 0 : full_evenodd (sweep_line_t *sweep_line)
1319 : {
1320 : cairo_list_t *pos;
1321 :
1322 0 : sweep_line->is_vertical = TRUE;
1323 0 : pos = sweep_line->active.next;
1324 : do {
1325 0 : edge_t *left = link_to_edge (pos), *right;
1326 0 : int winding = 0;
1327 :
1328 0 : sweep_line->is_vertical &= left->vertical;
1329 :
1330 0 : pos = left->link.next;
1331 : do {
1332 0 : if (pos == &sweep_line->active) {
1333 0 : full_add_edge (sweep_line, left, +1);
1334 0 : return;
1335 : }
1336 :
1337 0 : right = link_to_edge (pos);
1338 0 : pos = pos->next;
1339 0 : sweep_line->is_vertical &= right->vertical;
1340 :
1341 0 : if (++winding & 1) {
1342 0 : if (pos == &sweep_line->active ||
1343 0 : link_to_edge (pos)->x.quo != right->x.quo)
1344 : {
1345 : break;
1346 : }
1347 : }
1348 :
1349 0 : if (! right->vertical)
1350 0 : full_inc_edge (right);
1351 : } while (TRUE);
1352 :
1353 0 : full_add_edge (sweep_line, left, +1);
1354 0 : full_add_edge (sweep_line, right, -1);
1355 0 : } while (pos != &sweep_line->active);
1356 : }
1357 :
1358 : static void
1359 0 : render_rows (cairo_botor_scan_converter_t *self,
1360 : sweep_line_t *sweep_line,
1361 : int y, int height,
1362 : cairo_span_renderer_t *renderer)
1363 : {
1364 : cairo_half_open_span_t spans_stack[CAIRO_STACK_ARRAY_LENGTH (cairo_half_open_span_t)];
1365 0 : cairo_half_open_span_t *spans = spans_stack;
1366 : struct cell *cell;
1367 : int prev_x, cover;
1368 : int num_spans;
1369 : cairo_status_t status;
1370 :
1371 0 : if (unlikely (sweep_line->coverage.count == 0)) {
1372 0 : status = renderer->render_rows (renderer, y, height, NULL, 0);
1373 0 : if (unlikely (status))
1374 0 : longjmp (sweep_line->unwind, status);
1375 0 : return;
1376 : }
1377 :
1378 : /* Allocate enough spans for the row. */
1379 :
1380 0 : num_spans = 2*sweep_line->coverage.count+2;
1381 0 : if (unlikely (num_spans > ARRAY_LENGTH (spans_stack))) {
1382 0 : spans = _cairo_malloc_ab (num_spans, sizeof (cairo_half_open_span_t));
1383 0 : if (unlikely (spans == NULL)) {
1384 0 : longjmp (sweep_line->unwind,
1385 0 : _cairo_error (CAIRO_STATUS_NO_MEMORY));
1386 : }
1387 : }
1388 :
1389 : /* Form the spans from the coverage and areas. */
1390 0 : num_spans = 0;
1391 0 : prev_x = self->xmin;
1392 0 : cover = 0;
1393 0 : cell = sweep_line->coverage.head.next;
1394 : do {
1395 0 : int x = cell->x;
1396 : int area;
1397 :
1398 0 : if (x > prev_x) {
1399 0 : spans[num_spans].x = prev_x;
1400 0 : spans[num_spans].coverage = AREA_TO_ALPHA (cover);
1401 0 : ++num_spans;
1402 : }
1403 :
1404 0 : cover += cell->covered_height*STEP_X*2;
1405 0 : area = cover - cell->uncovered_area;
1406 :
1407 0 : spans[num_spans].x = x;
1408 0 : spans[num_spans].coverage = AREA_TO_ALPHA (area);
1409 0 : ++num_spans;
1410 :
1411 0 : prev_x = x + 1;
1412 0 : } while ((cell = cell->next) != &sweep_line->coverage.tail);
1413 :
1414 0 : if (prev_x <= self->xmax) {
1415 0 : spans[num_spans].x = prev_x;
1416 0 : spans[num_spans].coverage = AREA_TO_ALPHA (cover);
1417 0 : ++num_spans;
1418 : }
1419 :
1420 0 : if (cover && prev_x < self->xmax) {
1421 0 : spans[num_spans].x = self->xmax;
1422 0 : spans[num_spans].coverage = 0;
1423 0 : ++num_spans;
1424 : }
1425 :
1426 0 : status = renderer->render_rows (renderer, y, height, spans, num_spans);
1427 :
1428 0 : if (unlikely (spans != spans_stack))
1429 0 : free (spans);
1430 :
1431 0 : coverage_reset (&sweep_line->coverage);
1432 :
1433 0 : if (unlikely (status))
1434 0 : longjmp (sweep_line->unwind, status);
1435 : }
1436 :
1437 : static void
1438 0 : full_repeat (sweep_line_t *sweep)
1439 : {
1440 : edge_t *edge;
1441 :
1442 0 : cairo_list_foreach_entry (edge, edge_t, &sweep->active, link) {
1443 0 : if (edge->current_sign)
1444 0 : full_add_edge (sweep, edge, edge->current_sign);
1445 0 : else if (! edge->vertical)
1446 0 : full_inc_edge (edge);
1447 : }
1448 0 : }
1449 :
1450 : static void
1451 0 : full_reset (sweep_line_t *sweep)
1452 : {
1453 : edge_t *edge;
1454 :
1455 0 : cairo_list_foreach_entry (edge, edge_t, &sweep->active, link)
1456 0 : edge->current_sign = 0;
1457 0 : }
1458 :
1459 : static void
1460 0 : full_step (cairo_botor_scan_converter_t *self,
1461 : sweep_line_t *sweep_line,
1462 : cairo_fixed_t row,
1463 : cairo_span_renderer_t *renderer)
1464 : {
1465 : int top, bottom;
1466 :
1467 0 : top = _cairo_fixed_integer_part (sweep_line->current_row);
1468 0 : bottom = _cairo_fixed_integer_part (row);
1469 0 : if (cairo_list_is_empty (&sweep_line->active)) {
1470 : cairo_status_t status;
1471 :
1472 0 : status = renderer->render_rows (renderer, top, bottom - top, NULL, 0);
1473 0 : if (unlikely (status))
1474 0 : longjmp (sweep_line->unwind, status);
1475 :
1476 0 : return;
1477 : }
1478 :
1479 0 : if (self->fill_rule == CAIRO_FILL_RULE_WINDING)
1480 0 : full_nonzero (sweep_line);
1481 : else
1482 0 : full_evenodd (sweep_line);
1483 :
1484 0 : if (sweep_line->is_vertical || bottom == top + 1) {
1485 0 : render_rows (self, sweep_line, top, bottom - top, renderer);
1486 0 : full_reset (sweep_line);
1487 0 : return;
1488 : }
1489 :
1490 0 : render_rows (self, sweep_line, top++, 1, renderer);
1491 : do {
1492 0 : full_repeat (sweep_line);
1493 0 : render_rows (self, sweep_line, top, 1, renderer);
1494 0 : } while (++top != bottom);
1495 :
1496 0 : full_reset (sweep_line);
1497 : }
1498 :
1499 : cairo_always_inline static void
1500 : sub_inc_edge (edge_t *edge,
1501 : cairo_fixed_t height)
1502 : {
1503 0 : if (height == 1) {
1504 0 : edge->x.quo += edge->dxdy.quo;
1505 0 : edge->x.rem += edge->dxdy.rem;
1506 0 : if (edge->x.rem >= 0) {
1507 0 : ++edge->x.quo;
1508 0 : edge->x.rem -= edge->dy;
1509 : }
1510 : } else {
1511 0 : edge->x.quo += height * edge->dxdy.quo;
1512 0 : edge->x.rem += height * edge->dxdy.rem;
1513 0 : if (edge->x.rem >= 0) {
1514 0 : int carry = edge->x.rem / edge->dy + 1;
1515 0 : edge->x.quo += carry;
1516 0 : edge->x.rem -= carry * edge->dy;
1517 : }
1518 : }
1519 : }
1520 :
1521 : static void
1522 0 : sub_add_run (sweep_line_t *sweep_line, edge_t *edge, int y, int sign)
1523 : {
1524 : struct run *run;
1525 :
1526 0 : run = _cairo_freepool_alloc (&sweep_line->runs);
1527 0 : if (unlikely (run == NULL))
1528 0 : longjmp (sweep_line->unwind, _cairo_error (CAIRO_STATUS_NO_MEMORY));
1529 :
1530 0 : run->y = y;
1531 0 : run->sign = sign;
1532 0 : run->next = edge->runs;
1533 0 : edge->runs = run;
1534 :
1535 0 : edge->current_sign = sign;
1536 0 : }
1537 :
1538 : inline static cairo_bool_t
1539 0 : edges_coincident (edge_t *left, edge_t *right, cairo_fixed_t y)
1540 : {
1541 : /* XXX is compare_x_for_y() worth executing during sub steps? */
1542 0 : return line_equal (&left->edge.line, &right->edge.line);
1543 : //edges_compare_x_for_y (&left->edge, &right->edge, y) >= 0;
1544 : }
1545 :
1546 : static void
1547 0 : sub_nonzero (sweep_line_t *sweep_line)
1548 : {
1549 0 : cairo_fixed_t y = sweep_line->current_subrow;
1550 0 : cairo_fixed_t fy = _cairo_fixed_fractional_part (y);
1551 : cairo_list_t *pos;
1552 :
1553 0 : pos = sweep_line->active.next;
1554 : do {
1555 0 : edge_t *left = link_to_edge (pos), *right;
1556 0 : int winding = left->edge.dir;
1557 :
1558 0 : pos = left->link.next;
1559 : do {
1560 0 : if (unlikely (pos == &sweep_line->active)) {
1561 0 : if (left->current_sign != +1)
1562 0 : sub_add_run (sweep_line, left, fy, +1);
1563 0 : return;
1564 : }
1565 :
1566 0 : right = link_to_edge (pos);
1567 0 : pos = pos->next;
1568 :
1569 0 : winding += right->edge.dir;
1570 0 : if (0 == winding) {
1571 0 : if (pos == &sweep_line->active ||
1572 0 : ! edges_coincident (right, link_to_edge (pos), y))
1573 : {
1574 : break;
1575 : }
1576 : }
1577 :
1578 0 : if (right->current_sign)
1579 0 : sub_add_run (sweep_line, right, fy, 0);
1580 : } while (TRUE);
1581 :
1582 0 : if (left->current_sign != +1)
1583 0 : sub_add_run (sweep_line, left, fy, +1);
1584 0 : if (right->current_sign != -1)
1585 0 : sub_add_run (sweep_line, right, fy, -1);
1586 0 : } while (pos != &sweep_line->active);
1587 : }
1588 :
1589 : static void
1590 0 : sub_evenodd (sweep_line_t *sweep_line)
1591 : {
1592 0 : cairo_fixed_t y = sweep_line->current_subrow;
1593 0 : cairo_fixed_t fy = _cairo_fixed_fractional_part (y);
1594 : cairo_list_t *pos;
1595 :
1596 0 : pos = sweep_line->active.next;
1597 : do {
1598 0 : edge_t *left = link_to_edge (pos), *right;
1599 0 : int winding = 0;
1600 :
1601 0 : pos = left->link.next;
1602 : do {
1603 0 : if (unlikely (pos == &sweep_line->active)) {
1604 0 : if (left->current_sign != +1)
1605 0 : sub_add_run (sweep_line, left, fy, +1);
1606 0 : return;
1607 : }
1608 :
1609 0 : right = link_to_edge (pos);
1610 0 : pos = pos->next;
1611 :
1612 0 : if (++winding & 1) {
1613 0 : if (pos == &sweep_line->active ||
1614 0 : ! edges_coincident (right, link_to_edge (pos), y))
1615 : {
1616 : break;
1617 : }
1618 : }
1619 :
1620 0 : if (right->current_sign)
1621 0 : sub_add_run (sweep_line, right, fy, 0);
1622 : } while (TRUE);
1623 :
1624 0 : if (left->current_sign != +1)
1625 0 : sub_add_run (sweep_line, left, fy, +1);
1626 0 : if (right->current_sign != -1)
1627 0 : sub_add_run (sweep_line, right, fy, -1);
1628 0 : } while (pos != &sweep_line->active);
1629 : }
1630 :
1631 : cairo_always_inline static void
1632 : sub_step (cairo_botor_scan_converter_t *self,
1633 : sweep_line_t *sweep_line)
1634 : {
1635 0 : if (cairo_list_is_empty (&sweep_line->active))
1636 : return;
1637 :
1638 0 : if (self->fill_rule == CAIRO_FILL_RULE_WINDING)
1639 0 : sub_nonzero (sweep_line);
1640 : else
1641 0 : sub_evenodd (sweep_line);
1642 : }
1643 :
1644 : static void
1645 0 : coverage_render_runs (sweep_line_t *sweep, edge_t *edge,
1646 : cairo_fixed_t y1, cairo_fixed_t y2)
1647 : {
1648 : struct run tail;
1649 0 : struct run *run = &tail;
1650 :
1651 0 : tail.next = NULL;
1652 0 : tail.y = y2;
1653 :
1654 : /* Order the runs top->bottom */
1655 0 : while (edge->runs) {
1656 : struct run *r;
1657 :
1658 0 : r = edge->runs;
1659 0 : edge->runs = r->next;
1660 0 : r->next = run;
1661 0 : run = r;
1662 : }
1663 :
1664 0 : if (run->y > y1)
1665 0 : sub_inc_edge (edge, run->y - y1);
1666 :
1667 : do {
1668 : cairo_fixed_t x1, x2;
1669 :
1670 0 : y1 = run->y;
1671 0 : y2 = run->next->y;
1672 :
1673 0 : x1 = edge->x.quo;
1674 0 : if (y2 - y1 == STEP_Y)
1675 0 : full_inc_edge (edge);
1676 : else
1677 0 : sub_inc_edge (edge, y2 - y1);
1678 0 : x2 = edge->x.quo;
1679 :
1680 0 : if (run->sign) {
1681 : int ix1, ix2;
1682 :
1683 0 : ix1 = _cairo_fixed_integer_part (x1);
1684 0 : ix2 = _cairo_fixed_integer_part (x2);
1685 :
1686 : /* Edge is entirely within a column? */
1687 0 : if (likely (ix1 == ix2)) {
1688 : struct cell *cell;
1689 : int frac;
1690 :
1691 0 : frac = _cairo_fixed_fractional_part (x1) +
1692 0 : _cairo_fixed_fractional_part (x2);
1693 0 : cell = coverage_find (sweep, ix1);
1694 0 : cell->covered_height += run->sign * (y2 - y1);
1695 0 : cell->uncovered_area += run->sign * (y2 - y1) * frac;
1696 : } else {
1697 0 : coverage_render_cells (sweep, x1, x2, y1, y2, run->sign);
1698 : }
1699 : }
1700 :
1701 0 : run = run->next;
1702 0 : } while (run->next != NULL);
1703 0 : }
1704 :
1705 : static void
1706 0 : coverage_render_vertical_runs (sweep_line_t *sweep, edge_t *edge, cairo_fixed_t y2)
1707 : {
1708 : struct cell *cell;
1709 : struct run *run;
1710 0 : int height = 0;
1711 :
1712 0 : for (run = edge->runs; run != NULL; run = run->next) {
1713 0 : if (run->sign)
1714 0 : height += run->sign * (y2 - run->y);
1715 0 : y2 = run->y;
1716 : }
1717 :
1718 0 : cell = coverage_find (sweep, _cairo_fixed_integer_part (edge->x.quo));
1719 0 : cell->covered_height += height;
1720 0 : cell->uncovered_area += 2 * _cairo_fixed_fractional_part (edge->x.quo) * height;
1721 0 : }
1722 :
1723 : cairo_always_inline static void
1724 : sub_emit (cairo_botor_scan_converter_t *self,
1725 : sweep_line_t *sweep,
1726 : cairo_span_renderer_t *renderer)
1727 : {
1728 : edge_t *edge;
1729 :
1730 : sub_step (self, sweep);
1731 :
1732 : /* convert the runs into coverages */
1733 :
1734 0 : cairo_list_foreach_entry (edge, edge_t, &sweep->active, link) {
1735 0 : if (edge->runs == NULL) {
1736 0 : if (! edge->vertical) {
1737 0 : if (edge->flags & START) {
1738 0 : sub_inc_edge (edge,
1739 0 : STEP_Y - _cairo_fixed_fractional_part (edge->edge.top));
1740 0 : edge->flags &= ~START;
1741 : } else
1742 0 : full_inc_edge (edge);
1743 : }
1744 : } else {
1745 0 : if (edge->vertical) {
1746 0 : coverage_render_vertical_runs (sweep, edge, STEP_Y);
1747 : } else {
1748 0 : int y1 = 0;
1749 0 : if (edge->flags & START) {
1750 0 : y1 = _cairo_fixed_fractional_part (edge->edge.top);
1751 0 : edge->flags &= ~START;
1752 : }
1753 0 : coverage_render_runs (sweep, edge, y1, STEP_Y);
1754 : }
1755 : }
1756 0 : edge->current_sign = 0;
1757 0 : edge->runs = NULL;
1758 : }
1759 :
1760 0 : cairo_list_foreach_entry (edge, edge_t, &sweep->stopped, link) {
1761 0 : int y2 = _cairo_fixed_fractional_part (edge->edge.bottom);
1762 0 : if (edge->vertical) {
1763 0 : coverage_render_vertical_runs (sweep, edge, y2);
1764 : } else {
1765 0 : int y1 = 0;
1766 0 : if (edge->flags & START)
1767 0 : y1 = _cairo_fixed_fractional_part (edge->edge.top);
1768 0 : coverage_render_runs (sweep, edge, y1, y2);
1769 : }
1770 : }
1771 0 : cairo_list_init (&sweep->stopped);
1772 :
1773 0 : _cairo_freepool_reset (&sweep->runs);
1774 :
1775 0 : render_rows (self, sweep,
1776 : _cairo_fixed_integer_part (sweep->current_row), 1,
1777 : renderer);
1778 : }
1779 :
1780 : static void
1781 0 : sweep_line_init (sweep_line_t *sweep_line,
1782 : event_t **start_events,
1783 : int num_events)
1784 : {
1785 0 : cairo_list_init (&sweep_line->active);
1786 0 : cairo_list_init (&sweep_line->stopped);
1787 0 : sweep_line->insert_cursor = &sweep_line->active;
1788 :
1789 0 : sweep_line->current_row = INT32_MIN;
1790 0 : sweep_line->current_subrow = INT32_MIN;
1791 :
1792 0 : coverage_init (&sweep_line->coverage);
1793 0 : _cairo_freepool_init (&sweep_line->runs, sizeof (struct run));
1794 :
1795 0 : start_event_sort (start_events, num_events);
1796 0 : start_events[num_events] = NULL;
1797 :
1798 0 : sweep_line->queue.start_events = start_events;
1799 :
1800 0 : _cairo_freepool_init (&sweep_line->queue.pool,
1801 : sizeof (queue_event_t));
1802 0 : pqueue_init (&sweep_line->queue.pq);
1803 0 : sweep_line->queue.pq.elements[PQ_FIRST_ENTRY] = NULL;
1804 0 : }
1805 :
1806 : static void
1807 0 : sweep_line_delete (sweep_line_t *sweep_line,
1808 : edge_t *edge)
1809 : {
1810 0 : if (sweep_line->insert_cursor == &edge->link)
1811 0 : sweep_line->insert_cursor = edge->link.prev;
1812 :
1813 0 : cairo_list_del (&edge->link);
1814 0 : if (edge->runs)
1815 0 : cairo_list_add_tail (&edge->link, &sweep_line->stopped);
1816 0 : edge->flags |= STOP;
1817 0 : }
1818 :
1819 : static void
1820 0 : sweep_line_swap (sweep_line_t *sweep_line,
1821 : edge_t *left,
1822 : edge_t *right)
1823 : {
1824 0 : right->link.prev = left->link.prev;
1825 0 : left->link.next = right->link.next;
1826 0 : right->link.next = &left->link;
1827 0 : left->link.prev = &right->link;
1828 0 : left->link.next->prev = &left->link;
1829 0 : right->link.prev->next = &right->link;
1830 0 : }
1831 :
1832 : static void
1833 0 : sweep_line_fini (sweep_line_t *sweep_line)
1834 : {
1835 0 : pqueue_fini (&sweep_line->queue.pq);
1836 0 : _cairo_freepool_fini (&sweep_line->queue.pool);
1837 0 : coverage_fini (&sweep_line->coverage);
1838 0 : _cairo_freepool_fini (&sweep_line->runs);
1839 0 : }
1840 :
1841 : static cairo_status_t
1842 0 : botor_generate (cairo_botor_scan_converter_t *self,
1843 : event_t **start_events,
1844 : cairo_span_renderer_t *renderer)
1845 : {
1846 : cairo_status_t status;
1847 : sweep_line_t sweep_line;
1848 : cairo_fixed_t ybot;
1849 : event_t *event;
1850 : cairo_list_t *left, *right;
1851 : edge_t *e1, *e2;
1852 : int bottom;
1853 :
1854 0 : sweep_line_init (&sweep_line, start_events, self->num_edges);
1855 0 : if ((status = setjmp (sweep_line.unwind)))
1856 0 : goto unwind;
1857 :
1858 0 : ybot = self->extents.p2.y;
1859 0 : sweep_line.current_subrow = self->extents.p1.y;
1860 0 : sweep_line.current_row = _cairo_fixed_floor (self->extents.p1.y);
1861 0 : event = *sweep_line.queue.start_events++;
1862 : do {
1863 : /* Can we process a full step in one go? */
1864 0 : if (event->y >= sweep_line.current_row + STEP_Y) {
1865 0 : bottom = _cairo_fixed_floor (event->y);
1866 0 : full_step (self, &sweep_line, bottom, renderer);
1867 0 : sweep_line.current_row = bottom;
1868 0 : sweep_line.current_subrow = bottom;
1869 : }
1870 :
1871 : do {
1872 0 : if (event->y > sweep_line.current_subrow) {
1873 : sub_step (self, &sweep_line);
1874 0 : sweep_line.current_subrow = event->y;
1875 : }
1876 :
1877 : do {
1878 : /* Update the active list using Bentley-Ottmann */
1879 0 : switch (event->type) {
1880 : case EVENT_TYPE_START:
1881 0 : e1 = ((start_event_t *) event)->edge;
1882 :
1883 0 : sweep_line_insert (&sweep_line, e1);
1884 0 : event_insert_stop (&sweep_line, e1);
1885 :
1886 0 : left = e1->link.prev;
1887 0 : right = e1->link.next;
1888 :
1889 0 : if (left != &sweep_line.active) {
1890 0 : event_insert_if_intersect_below_current_y (&sweep_line,
1891 : link_to_edge (left), e1);
1892 : }
1893 :
1894 0 : if (right != &sweep_line.active) {
1895 0 : event_insert_if_intersect_below_current_y (&sweep_line,
1896 : e1, link_to_edge (right));
1897 : }
1898 :
1899 0 : break;
1900 :
1901 : case EVENT_TYPE_STOP:
1902 0 : e1 = ((queue_event_t *) event)->e1;
1903 0 : event_delete (&sweep_line, event);
1904 :
1905 0 : left = e1->link.prev;
1906 0 : right = e1->link.next;
1907 :
1908 0 : sweep_line_delete (&sweep_line, e1);
1909 :
1910 0 : if (left != &sweep_line.active &&
1911 : right != &sweep_line.active)
1912 : {
1913 0 : event_insert_if_intersect_below_current_y (&sweep_line,
1914 : link_to_edge (left),
1915 : link_to_edge (right));
1916 : }
1917 :
1918 0 : break;
1919 :
1920 : case EVENT_TYPE_INTERSECTION:
1921 0 : e1 = ((queue_event_t *) event)->e1;
1922 0 : e2 = ((queue_event_t *) event)->e2;
1923 :
1924 0 : event_delete (&sweep_line, event);
1925 0 : if (e1->flags & STOP)
1926 0 : break;
1927 0 : if (e2->flags & STOP)
1928 0 : break;
1929 :
1930 : /* skip this intersection if its edges are not adjacent */
1931 0 : if (&e2->link != e1->link.next)
1932 0 : break;
1933 :
1934 0 : left = e1->link.prev;
1935 0 : right = e2->link.next;
1936 :
1937 0 : sweep_line_swap (&sweep_line, e1, e2);
1938 :
1939 : /* after the swap e2 is left of e1 */
1940 0 : if (left != &sweep_line.active) {
1941 0 : event_insert_if_intersect_below_current_y (&sweep_line,
1942 : link_to_edge (left), e2);
1943 : }
1944 :
1945 0 : if (right != &sweep_line.active) {
1946 0 : event_insert_if_intersect_below_current_y (&sweep_line,
1947 : e1, link_to_edge (right));
1948 : }
1949 :
1950 0 : break;
1951 : }
1952 :
1953 0 : event = event_next (&sweep_line);
1954 0 : if (event == NULL)
1955 0 : goto end;
1956 0 : } while (event->y == sweep_line.current_subrow);
1957 0 : } while (event->y < sweep_line.current_row + STEP_Y);
1958 :
1959 0 : bottom = sweep_line.current_row + STEP_Y;
1960 : sub_emit (self, &sweep_line, renderer);
1961 0 : sweep_line.current_subrow = bottom;
1962 0 : sweep_line.current_row = sweep_line.current_subrow;
1963 : } while (TRUE);
1964 :
1965 : end:
1966 : /* flush any partial spans */
1967 0 : if (sweep_line.current_subrow != sweep_line.current_row) {
1968 : sub_emit (self, &sweep_line, renderer);
1969 0 : sweep_line.current_row += STEP_Y;
1970 0 : sweep_line.current_subrow = sweep_line.current_row;
1971 : }
1972 : /* clear the rest */
1973 0 : if (sweep_line.current_subrow < ybot) {
1974 0 : bottom = _cairo_fixed_integer_part (sweep_line.current_row);
1975 0 : status = renderer->render_rows (renderer,
1976 0 : bottom, _cairo_fixed_integer_ceil (ybot) - bottom,
1977 : NULL, 0);
1978 : }
1979 :
1980 : unwind:
1981 0 : sweep_line_fini (&sweep_line);
1982 :
1983 0 : return status;
1984 : }
1985 :
1986 : static cairo_status_t
1987 0 : _cairo_botor_scan_converter_generate (void *converter,
1988 : cairo_span_renderer_t *renderer)
1989 : {
1990 0 : cairo_botor_scan_converter_t *self = converter;
1991 : start_event_t stack_events[CAIRO_STACK_ARRAY_LENGTH (start_event_t)];
1992 : start_event_t *events;
1993 : event_t *stack_event_ptrs[ARRAY_LENGTH (stack_events) + 1];
1994 : event_t **event_ptrs;
1995 : struct _cairo_botor_scan_converter_chunk *chunk;
1996 : cairo_status_t status;
1997 : int num_events;
1998 : int i, j;
1999 :
2000 0 : num_events = self->num_edges;
2001 0 : if (unlikely (0 == num_events)) {
2002 0 : return renderer->render_rows (renderer,
2003 : _cairo_fixed_integer_floor (self->extents.p1.y),
2004 0 : _cairo_fixed_integer_ceil (self->extents.p2.y) -
2005 0 : _cairo_fixed_integer_floor (self->extents.p1.y),
2006 : NULL, 0);
2007 : }
2008 :
2009 0 : events = stack_events;
2010 0 : event_ptrs = stack_event_ptrs;
2011 0 : if (unlikely (num_events >= ARRAY_LENGTH (stack_events))) {
2012 0 : events = _cairo_malloc_ab_plus_c (num_events,
2013 : sizeof (start_event_t) + sizeof (event_t *),
2014 : sizeof (event_t *));
2015 0 : if (unlikely (events == NULL))
2016 0 : return _cairo_error (CAIRO_STATUS_NO_MEMORY);
2017 :
2018 0 : event_ptrs = (event_t **) (events + num_events);
2019 : }
2020 :
2021 0 : j = 0;
2022 0 : for (chunk = &self->chunks; chunk != NULL; chunk = chunk->next) {
2023 : edge_t *edge;
2024 :
2025 0 : edge = chunk->base;
2026 0 : for (i = 0; i < chunk->count; i++) {
2027 0 : event_ptrs[j] = (event_t *) &events[j];
2028 :
2029 0 : events[j].y = edge->edge.top;
2030 0 : events[j].type = EVENT_TYPE_START;
2031 0 : events[j].edge = edge;
2032 :
2033 0 : edge++, j++;
2034 : }
2035 : }
2036 :
2037 0 : status = botor_generate (self, event_ptrs, renderer);
2038 :
2039 0 : if (events != stack_events)
2040 0 : free (events);
2041 :
2042 0 : return status;
2043 : }
2044 :
2045 : static edge_t *
2046 0 : botor_allocate_edge (cairo_botor_scan_converter_t *self)
2047 : {
2048 : struct _cairo_botor_scan_converter_chunk *chunk;
2049 :
2050 0 : chunk = self->tail;
2051 0 : if (chunk->count == chunk->size) {
2052 : int size;
2053 :
2054 0 : size = chunk->size * 2;
2055 0 : chunk->next = _cairo_malloc_ab_plus_c (size,
2056 : sizeof (edge_t),
2057 : sizeof (struct _cairo_botor_scan_converter_chunk));
2058 0 : if (unlikely (chunk->next == NULL))
2059 0 : return NULL;
2060 :
2061 0 : chunk = chunk->next;
2062 0 : chunk->next = NULL;
2063 0 : chunk->count = 0;
2064 0 : chunk->size = size;
2065 0 : chunk->base = chunk + 1;
2066 0 : self->tail = chunk;
2067 : }
2068 :
2069 0 : return (edge_t *) chunk->base + chunk->count++;
2070 : }
2071 :
2072 : static cairo_status_t
2073 0 : botor_add_edge (cairo_botor_scan_converter_t *self,
2074 : const cairo_edge_t *edge)
2075 : {
2076 : edge_t *e;
2077 : cairo_fixed_t dx, dy;
2078 :
2079 0 : e = botor_allocate_edge (self);
2080 0 : if (unlikely (e == NULL))
2081 0 : return _cairo_error (CAIRO_STATUS_NO_MEMORY);
2082 :
2083 0 : cairo_list_init (&e->link);
2084 0 : e->edge = *edge;
2085 :
2086 0 : dx = edge->line.p2.x - edge->line.p1.x;
2087 0 : dy = edge->line.p2.y - edge->line.p1.y;
2088 0 : e->dy = dy;
2089 :
2090 0 : if (dx == 0) {
2091 0 : e->vertical = TRUE;
2092 0 : e->x.quo = edge->line.p1.x;
2093 0 : e->x.rem = 0;
2094 0 : e->dxdy.quo = 0;
2095 0 : e->dxdy.rem = 0;
2096 0 : e->dxdy_full.quo = 0;
2097 0 : e->dxdy_full.rem = 0;
2098 : } else {
2099 0 : e->vertical = FALSE;
2100 0 : e->dxdy = floored_divrem (dx, dy);
2101 0 : if (edge->top == edge->line.p1.y) {
2102 0 : e->x.quo = edge->line.p1.x;
2103 0 : e->x.rem = 0;
2104 : } else {
2105 0 : e->x = floored_muldivrem (edge->top - edge->line.p1.y,
2106 : dx, dy);
2107 0 : e->x.quo += edge->line.p1.x;
2108 : }
2109 :
2110 0 : if (_cairo_fixed_integer_part (edge->bottom) - _cairo_fixed_integer_part (edge->top) > 1) {
2111 0 : e->dxdy_full = floored_muldivrem (STEP_Y, dx, dy);
2112 : } else {
2113 0 : e->dxdy_full.quo = 0;
2114 0 : e->dxdy_full.rem = 0;
2115 : }
2116 : }
2117 :
2118 0 : e->x.rem = -e->dy;
2119 0 : e->current_sign = 0;
2120 0 : e->runs = NULL;
2121 0 : e->flags = START;
2122 :
2123 0 : self->num_edges++;
2124 :
2125 0 : return CAIRO_STATUS_SUCCESS;
2126 : }
2127 :
2128 : static cairo_status_t
2129 0 : _cairo_botor_scan_converter_add_edge (void *converter,
2130 : const cairo_point_t *p1,
2131 : const cairo_point_t *p2,
2132 : int top, int bottom,
2133 : int dir)
2134 : {
2135 0 : cairo_botor_scan_converter_t *self = converter;
2136 : cairo_edge_t edge;
2137 :
2138 0 : edge.line.p1 = *p1;
2139 0 : edge.line.p2 = *p2;
2140 0 : edge.top = top;
2141 0 : edge.bottom = bottom;
2142 0 : edge.dir = dir;
2143 :
2144 0 : return botor_add_edge (self, &edge);
2145 : }
2146 :
2147 : static cairo_status_t
2148 0 : _cairo_botor_scan_converter_add_polygon (void *converter,
2149 : const cairo_polygon_t *polygon)
2150 : {
2151 0 : cairo_botor_scan_converter_t *self = converter;
2152 : cairo_status_t status;
2153 : int i;
2154 :
2155 0 : for (i = 0; i < polygon->num_edges; i++) {
2156 0 : status = botor_add_edge (self, &polygon->edges[i]);
2157 0 : if (unlikely (status))
2158 0 : return status;
2159 : }
2160 :
2161 0 : return CAIRO_STATUS_SUCCESS;
2162 : }
2163 :
2164 : static void
2165 0 : _cairo_botor_scan_converter_destroy (void *converter)
2166 : {
2167 0 : cairo_botor_scan_converter_t *self = converter;
2168 : struct _cairo_botor_scan_converter_chunk *chunk, *next;
2169 :
2170 0 : for (chunk = self->chunks.next; chunk != NULL; chunk = next) {
2171 0 : next = chunk->next;
2172 0 : free (chunk);
2173 : }
2174 0 : }
2175 :
2176 : void
2177 0 : _cairo_botor_scan_converter_init (cairo_botor_scan_converter_t *self,
2178 : const cairo_box_t *extents,
2179 : cairo_fill_rule_t fill_rule)
2180 : {
2181 0 : self->base.destroy = _cairo_botor_scan_converter_destroy;
2182 0 : self->base.add_edge = _cairo_botor_scan_converter_add_edge;
2183 0 : self->base.add_polygon = _cairo_botor_scan_converter_add_polygon;
2184 0 : self->base.generate = _cairo_botor_scan_converter_generate;
2185 :
2186 0 : self->extents = *extents;
2187 0 : self->fill_rule = fill_rule;
2188 :
2189 0 : self->xmin = _cairo_fixed_integer_floor (extents->p1.x);
2190 0 : self->xmax = _cairo_fixed_integer_ceil (extents->p2.x);
2191 :
2192 0 : self->chunks.base = self->buf;
2193 0 : self->chunks.next = NULL;
2194 0 : self->chunks.count = 0;
2195 0 : self->chunks.size = sizeof (self->buf) / sizeof (edge_t);
2196 0 : self->tail = &self->chunks;
2197 :
2198 0 : self->num_edges = 0;
2199 0 : }
|
