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