w32tex
About: TeX Live provides a comprehensive TeX system including all the major TeX-related programs, macro packages, and fonts that are free software. Windows sources.
  Fossies Dox: w32tex-src.tar.xz  ("unofficial" and yet experimental doxygen-generated source code documentation)  

cairo-polygon-intersect.c
Go to the documentation of this file.
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-inline.h"
44 
45 
46 typedef struct _cairo_bo_intersect_ordinate {
48  enum { EXCESS = -1, EXACT = 0, DEFAULT = 1 } approx;
50 
51 typedef struct _cairo_bo_intersect_point {
55 
56 typedef struct _cairo_bo_edge cairo_bo_edge_t;
57 
58 typedef struct _cairo_bo_deferred {
60  int32_t top;
62 
63 struct _cairo_bo_edge {
64  int a_or_b;
69 };
70 
71 /* the parent is always given by index/2 */
72 #define PQ_PARENT_INDEX(i) ((i) >> 1)
73 #define PQ_FIRST_ENTRY 1
74 
75 /* left and right children are index * 2 and (index * 2) +1 respectively */
76 #define PQ_LEFT_CHILD_INDEX(i) ((i) << 1)
77 
78 typedef enum {
83 
84 typedef struct _cairo_bo_event {
88 
89 typedef struct _cairo_bo_start_event {
94 
95 typedef struct _cairo_bo_queue_event {
101 
102 typedef struct _pqueue {
103  int size, max_size;
104 
108 
109 typedef struct _cairo_bo_event_queue {
114 
115 typedef struct _cairo_bo_sweep_line {
120 
121 static cairo_fixed_t
124 {
125  cairo_fixed_t x, dy;
126 
127  if (y == line->p1.y)
128  return line->p1.x;
129  if (y == line->p2.y)
130  return line->p2.x;
131 
132  x = line->p1.x;
133  dy = line->p2.y - line->p1.y;
134  if (dy != 0) {
135  x += _cairo_fixed_mul_div_floor (y - line->p1.y,
136  line->p2.x - line->p1.x,
137  dy);
138  }
139 
140  return x;
141 }
142 
143 static inline int
146 {
147  int cmp;
148 
149  cmp = a->y.ordinate - b->y.ordinate;
150  if (cmp)
151  return cmp;
152 
153  cmp = a->y.approx - b->y.approx;
154  if (cmp)
155  return cmp;
156 
157  return a->x.ordinate - b->x.ordinate;
158 }
159 
160 /* Compare the slope of a to the slope of b, returning 1, 0, -1 if the
161  * slope a is respectively greater than, equal to, or less than the
162  * slope of b.
163  *
164  * For each edge, consider the direction vector formed from:
165  *
166  * top -> bottom
167  *
168  * which is:
169  *
170  * (dx, dy) = (line.p2.x - line.p1.x, line.p2.y - line.p1.y)
171  *
172  * We then define the slope of each edge as dx/dy, (which is the
173  * inverse of the slope typically used in math instruction). We never
174  * compute a slope directly as the value approaches infinity, but we
175  * can derive a slope comparison without division as follows, (where
176  * the ? represents our compare operator).
177  *
178  * 1. slope(a) ? slope(b)
179  * 2. adx/ady ? bdx/bdy
180  * 3. (adx * bdy) ? (bdx * ady)
181  *
182  * Note that from step 2 to step 3 there is no change needed in the
183  * sign of the result since both ady and bdy are guaranteed to be
184  * greater than or equal to 0.
185  *
186  * When using this slope comparison to sort edges, some care is needed
187  * when interpreting the results. Since the slope compare operates on
188  * distance vectors from top to bottom it gives a correct left to
189  * right sort for edges that have a common top point, (such as two
190  * edges with start events at the same location). On the other hand,
191  * the sense of the result will be exactly reversed for two edges that
192  * have a common stop point.
193  */
194 static inline int
196  const cairo_bo_edge_t *b)
197 {
198  /* XXX: We're assuming here that dx and dy will still fit in 32
199  * bits. That's not true in general as there could be overflow. We
200  * should prevent that before the tessellation algorithm
201  * begins.
202  */
203  int32_t adx = a->edge.line.p2.x - a->edge.line.p1.x;
204  int32_t bdx = b->edge.line.p2.x - b->edge.line.p1.x;
205 
206  /* Since the dy's are all positive by construction we can fast
207  * path several common cases.
208  */
209 
210  /* First check for vertical lines. */
211  if (adx == 0)
212  return -bdx;
213  if (bdx == 0)
214  return adx;
215 
216  /* Then where the two edges point in different directions wrt x. */
217  if ((adx ^ bdx) < 0)
218  return adx;
219 
220  /* Finally we actually need to do the general comparison. */
221  {
222  int32_t ady = a->edge.line.p2.y - a->edge.line.p1.y;
223  int32_t bdy = b->edge.line.p2.y - b->edge.line.p1.y;
224  cairo_int64_t adx_bdy = _cairo_int32x32_64_mul (adx, bdy);
225  cairo_int64_t bdx_ady = _cairo_int32x32_64_mul (bdx, ady);
226 
227  return _cairo_int64_cmp (adx_bdy, bdx_ady);
228  }
229 }
230 
231 /*
232  * We need to compare the x-coordinates of a pair of lines for a particular y,
233  * without loss of precision.
234  *
235  * The x-coordinate along an edge for a given y is:
236  * X = A_x + (Y - A_y) * A_dx / A_dy
237  *
238  * So the inequality we wish to test is:
239  * A_x + (Y - A_y) * A_dx / A_dy ∘ B_x + (Y - B_y) * B_dx / B_dy,
240  * where ∘ is our inequality operator.
241  *
242  * By construction, we know that A_dy and B_dy (and (Y - A_y), (Y - B_y)) are
243  * all positive, so we can rearrange it thus without causing a sign change:
244  * A_dy * B_dy * (A_x - B_x) ∘ (Y - B_y) * B_dx * A_dy
245  * - (Y - A_y) * A_dx * B_dy
246  *
247  * Given the assumption that all the deltas fit within 32 bits, we can compute
248  * this comparison directly using 128 bit arithmetic. For certain, but common,
249  * input we can reduce this down to a single 32 bit compare by inspecting the
250  * deltas.
251  *
252  * (And put the burden of the work on developing fast 128 bit ops, which are
253  * required throughout the tessellator.)
254  *
255  * See the similar discussion for _slope_compare().
256  */
257 static int
259  const cairo_bo_edge_t *b,
260  int32_t y)
261 {
262  /* XXX: We're assuming here that dx and dy will still fit in 32
263  * bits. That's not true in general as there could be overflow. We
264  * should prevent that before the tessellation algorithm
265  * begins.
266  */
267  int32_t dx;
268  int32_t adx, ady;
269  int32_t bdx, bdy;
270  enum {
271  HAVE_NONE = 0x0,
272  HAVE_DX = 0x1,
273  HAVE_ADX = 0x2,
274  HAVE_DX_ADX = HAVE_DX | HAVE_ADX,
275  HAVE_BDX = 0x4,
276  HAVE_DX_BDX = HAVE_DX | HAVE_BDX,
277  HAVE_ADX_BDX = HAVE_ADX | HAVE_BDX,
278  HAVE_ALL = HAVE_DX | HAVE_ADX | HAVE_BDX
279  } have_dx_adx_bdx = HAVE_ALL;
280 
281  /* don't bother solving for abscissa if the edges' bounding boxes
282  * can be used to order them. */
283  {
284  int32_t amin, amax;
285  int32_t bmin, bmax;
286  if (a->edge.line.p1.x < a->edge.line.p2.x) {
287  amin = a->edge.line.p1.x;
288  amax = a->edge.line.p2.x;
289  } else {
290  amin = a->edge.line.p2.x;
291  amax = a->edge.line.p1.x;
292  }
293  if (b->edge.line.p1.x < b->edge.line.p2.x) {
294  bmin = b->edge.line.p1.x;
295  bmax = b->edge.line.p2.x;
296  } else {
297  bmin = b->edge.line.p2.x;
298  bmax = b->edge.line.p1.x;
299  }
300  if (amax < bmin) return -1;
301  if (amin > bmax) return +1;
302  }
303 
304  ady = a->edge.line.p2.y - a->edge.line.p1.y;
305  adx = a->edge.line.p2.x - a->edge.line.p1.x;
306  if (adx == 0)
307  have_dx_adx_bdx &= ~~HAVE_ADX;
308 
309  bdy = b->edge.line.p2.y - b->edge.line.p1.y;
310  bdx = b->edge.line.p2.x - b->edge.line.p1.x;
311  if (bdx == 0)
312  have_dx_adx_bdx &= ~~HAVE_BDX;
313 
314  dx = a->edge.line.p1.x - b->edge.line.p1.x;
315  if (dx == 0)
316  have_dx_adx_bdx &= ~~HAVE_DX;
317 
318 #define L _cairo_int64x32_128_mul (_cairo_int32x32_64_mul (ady, bdy), dx)
319 #define A _cairo_int64x32_128_mul (_cairo_int32x32_64_mul (adx, bdy), y - a->edge.line.p1.y)
320 #define B _cairo_int64x32_128_mul (_cairo_int32x32_64_mul (bdx, ady), y - b->edge.line.p1.y)
321  switch (have_dx_adx_bdx) {
322  default:
323  case HAVE_NONE:
324  return 0;
325  case HAVE_DX:
326  /* A_dy * B_dy * (A_x - B_x) ∘ 0 */
327  return dx; /* ady * bdy is positive definite */
328  case HAVE_ADX:
329  /* 0 ∘ - (Y - A_y) * A_dx * B_dy */
330  return adx; /* bdy * (y - a->top.y) is positive definite */
331  case HAVE_BDX:
332  /* 0 ∘ (Y - B_y) * B_dx * A_dy */
333  return -bdx; /* ady * (y - b->top.y) is positive definite */
334  case HAVE_ADX_BDX:
335  /* 0 ∘ (Y - B_y) * B_dx * A_dy - (Y - A_y) * A_dx * B_dy */
336  if ((adx ^ bdx) < 0) {
337  return adx;
338  } else if (a->edge.line.p1.y == b->edge.line.p1.y) { /* common origin */
339  cairo_int64_t adx_bdy, bdx_ady;
340 
341  /* ∴ A_dx * B_dy ∘ B_dx * A_dy */
342 
343  adx_bdy = _cairo_int32x32_64_mul (adx, bdy);
344  bdx_ady = _cairo_int32x32_64_mul (bdx, ady);
345 
346  return _cairo_int64_cmp (adx_bdy, bdx_ady);
347  } else
348  return _cairo_int128_cmp (A, B);
349  case HAVE_DX_ADX:
350  /* A_dy * (A_x - B_x) ∘ - (Y - A_y) * A_dx */
351  if ((-adx ^ dx) < 0) {
352  return dx;
353  } else {
354  cairo_int64_t ady_dx, dy_adx;
355 
356  ady_dx = _cairo_int32x32_64_mul (ady, dx);
357  dy_adx = _cairo_int32x32_64_mul (a->edge.line.p1.y - y, adx);
358 
359  return _cairo_int64_cmp (ady_dx, dy_adx);
360  }
361  case HAVE_DX_BDX:
362  /* B_dy * (A_x - B_x) ∘ (Y - B_y) * B_dx */
363  if ((bdx ^ dx) < 0) {
364  return dx;
365  } else {
366  cairo_int64_t bdy_dx, dy_bdx;
367 
368  bdy_dx = _cairo_int32x32_64_mul (bdy, dx);
369  dy_bdx = _cairo_int32x32_64_mul (y - b->edge.line.p1.y, bdx);
370 
371  return _cairo_int64_cmp (bdy_dx, dy_bdx);
372  }
373  case HAVE_ALL:
374  /* XXX try comparing (a->edge.line.p2.x - b->edge.line.p2.x) et al */
375  return _cairo_int128_cmp (L, _cairo_int128_sub (B, A));
376  }
377 #undef B
378 #undef A
379 #undef L
380 }
381 
382 /*
383  * We need to compare the x-coordinate of a line for a particular y wrt to a
384  * given x, without loss of precision.
385  *
386  * The x-coordinate along an edge for a given y is:
387  * X = A_x + (Y - A_y) * A_dx / A_dy
388  *
389  * So the inequality we wish to test is:
390  * A_x + (Y - A_y) * A_dx / A_dy ∘ X
391  * where ∘ is our inequality operator.
392  *
393  * By construction, we know that A_dy (and (Y - A_y)) are
394  * all positive, so we can rearrange it thus without causing a sign change:
395  * (Y - A_y) * A_dx ∘ (X - A_x) * A_dy
396  *
397  * Given the assumption that all the deltas fit within 32 bits, we can compute
398  * this comparison directly using 64 bit arithmetic.
399  *
400  * See the similar discussion for _slope_compare() and
401  * edges_compare_x_for_y_general().
402  */
403 static int
405  int32_t y,
406  int32_t x)
407 {
408  int32_t adx, ady;
409  int32_t dx, dy;
410  cairo_int64_t L, R;
411 
412  if (x < a->edge.line.p1.x && x < a->edge.line.p2.x)
413  return 1;
414  if (x > a->edge.line.p1.x && x > a->edge.line.p2.x)
415  return -1;
416 
417  adx = a->edge.line.p2.x - a->edge.line.p1.x;
418  dx = x - a->edge.line.p1.x;
419 
420  if (adx == 0)
421  return -dx;
422  if (dx == 0 || (adx ^ dx) < 0)
423  return adx;
424 
425  dy = y - a->edge.line.p1.y;
426  ady = a->edge.line.p2.y - a->edge.line.p1.y;
427 
428  L = _cairo_int32x32_64_mul (dy, adx);
429  R = _cairo_int32x32_64_mul (dx, ady);
430 
431  return _cairo_int64_cmp (L, R);
432 }
433 
434 static int
436  const cairo_bo_edge_t *b,
437  int32_t y)
438 {
439  /* If the sweep-line is currently on an end-point of a line,
440  * then we know its precise x value (and considering that we often need to
441  * compare events at end-points, this happens frequently enough to warrant
442  * special casing).
443  */
444  enum {
445  HAVE_NEITHER = 0x0,
446  HAVE_AX = 0x1,
447  HAVE_BX = 0x2,
448  HAVE_BOTH = HAVE_AX | HAVE_BX
449  } have_ax_bx = HAVE_BOTH;
450  int32_t ax = 0, bx = 0;
451 
452  if (y == a->edge.line.p1.y)
453  ax = a->edge.line.p1.x;
454  else if (y == a->edge.line.p2.y)
455  ax = a->edge.line.p2.x;
456  else
457  have_ax_bx &= ~~HAVE_AX;
458 
459  if (y == b->edge.line.p1.y)
460  bx = b->edge.line.p1.x;
461  else if (y == b->edge.line.p2.y)
462  bx = b->edge.line.p2.x;
463  else
464  have_ax_bx &= ~~HAVE_BX;
465 
466  switch (have_ax_bx) {
467  default:
468  case HAVE_NEITHER:
469  return edges_compare_x_for_y_general (a, b, y);
470  case HAVE_AX:
471  return -edge_compare_for_y_against_x (b, y, ax);
472  case HAVE_BX:
473  return edge_compare_for_y_against_x (a, y, bx);
474  case HAVE_BOTH:
475  return ax - bx;
476  }
477 }
478 
479 static inline int
481 {
482  return a->p1.x == b->p1.x && a->p1.y == b->p1.y &&
483  a->p2.x == b->p2.x && a->p2.y == b->p2.y;
484 }
485 
486 static int
488  const cairo_bo_edge_t *a,
489  const cairo_bo_edge_t *b)
490 {
491  int cmp;
492 
493  /* compare the edges if not identical */
494  if (! _line_equal (&a->edge.line, &b->edge.line)) {
495  cmp = edges_compare_x_for_y (a, b, sweep_line->current_y);
496  if (cmp)
497  return cmp;
498 
499  /* The two edges intersect exactly at y, so fall back on slope
500  * comparison. We know that this compare_edges function will be
501  * called only when starting a new edge, (not when stopping an
502  * edge), so we don't have to worry about conditionally inverting
503  * the sense of _slope_compare. */
504  cmp = _slope_compare (a, b);
505  if (cmp)
506  return cmp;
507  }
508 
509  /* We've got two collinear edges now. */
510  return b->edge.bottom - a->edge.bottom;
511 }
512 
513 static inline cairo_int64_t
515  int32_t c, int32_t d)
516 {
517  /* det = a * d - b * c */
520 }
521 
522 static inline cairo_int128_t
525 {
526  /* det = a * d - b * c */
529 }
530 
531 static inline cairo_bo_intersect_ordinate_t
534 {
536  int32_t quo = d.quo;
538 
539  /* assert (! _cairo_int64_negative (den));*/
540 
541  if (_cairo_int64_lt (drem_2, _cairo_int64_negate (den))) {
542  quo -= 1;
543  drem_2 = _cairo_int64_negate (drem_2);
544  } else if (_cairo_int64_le (den, drem_2)) {
545  quo += 1;
546  drem_2 = _cairo_int64_negate (drem_2);
547  }
548 
549  ordinate.ordinate = quo;
550  ordinate.approx = _cairo_int64_is_zero (drem_2) ? EXACT : _cairo_int64_negative (drem_2) ? EXCESS : DEFAULT;
551 
552  return ordinate;
553 }
554 
555 /* Compute the intersection of two lines as defined by two edges. The
556  * result is provided as a coordinate pair of 128-bit integers.
557  *
558  * Returns %CAIRO_BO_STATUS_INTERSECTION if there is an intersection or
559  * %CAIRO_BO_STATUS_PARALLEL if the two lines are exactly parallel.
560  */
561 static cairo_bool_t
565 {
566  cairo_int64_t a_det, b_det;
567 
568  /* XXX: We're assuming here that dx and dy will still fit in 32
569  * bits. That's not true in general as there could be overflow. We
570  * should prevent that before the tessellation algorithm begins.
571  * What we're doing to mitigate this is to perform clamping in
572  * cairo_bo_tessellate_polygon().
573  */
574  int32_t dx1 = a->edge.line.p1.x - a->edge.line.p2.x;
575  int32_t dy1 = a->edge.line.p1.y - a->edge.line.p2.y;
576 
577  int32_t dx2 = b->edge.line.p1.x - b->edge.line.p2.x;
578  int32_t dy2 = b->edge.line.p1.y - b->edge.line.p2.y;
579 
580  cairo_int64_t den_det;
582  cairo_quorem64_t qr;
583 
584  den_det = det32_64 (dx1, dy1, dx2, dy2);
585 
586  /* Q: Can we determine that the lines do not intersect (within range)
587  * much more cheaply than computing the intersection point i.e. by
588  * avoiding the division?
589  *
590  * X = ax + t * adx = bx + s * bdx;
591  * Y = ay + t * ady = by + s * bdy;
592  * ∴ t * (ady*bdx - bdy*adx) = bdx * (by - ay) + bdy * (ax - bx)
593  * => t * L = R
594  *
595  * Therefore we can reject any intersection (under the criteria for
596  * valid intersection events) if:
597  * L^R < 0 => t < 0, or
598  * L<R => t > 1
599  *
600  * (where top/bottom must at least extend to the line endpoints).
601  *
602  * A similar substitution can be performed for s, yielding:
603  * s * (ady*bdx - bdy*adx) = ady * (ax - bx) - adx * (ay - by)
604  */
605  R = det32_64 (dx2, dy2,
606  b->edge.line.p1.x - a->edge.line.p1.x,
607  b->edge.line.p1.y - a->edge.line.p1.y);
608  if (_cairo_int64_le (den_det, R))
609  return FALSE;
610 
611  R = det32_64 (dy1, dx1,
612  a->edge.line.p1.y - b->edge.line.p1.y,
613  a->edge.line.p1.x - b->edge.line.p1.x);
614  if (_cairo_int64_le (den_det, R))
615  return FALSE;
616 
617  /* We now know that the two lines should intersect within range. */
618 
619  a_det = det32_64 (a->edge.line.p1.x, a->edge.line.p1.y,
620  a->edge.line.p2.x, a->edge.line.p2.y);
621  b_det = det32_64 (b->edge.line.p1.x, b->edge.line.p1.y,
622  b->edge.line.p2.x, b->edge.line.p2.y);
623 
624  /* x = det (a_det, dx1, b_det, dx2) / den_det */
626  b_det, dx2),
627  den_det);
628  if (_cairo_int64_eq (qr.rem, den_det))
629  return FALSE;
630 
631  intersection->x = round_to_nearest (qr, den_det);
632 
633  /* y = det (a_det, dy1, b_det, dy2) / den_det */
635  b_det, dy2),
636  den_det);
637  if (_cairo_int64_eq (qr.rem, den_det))
638  return FALSE;
639 
640  intersection->y = round_to_nearest (qr, den_det);
641 
642  return TRUE;
643 }
644 
645 static int
647  int32_t b)
648 {
649  /* First compare the quotient */
650  if (a.ordinate > b)
651  return +1;
652  if (a.ordinate < b)
653  return -1;
654 
655  return a.approx; /* == EXCESS ? -1 : a.approx == EXACT ? 0 : 1;*/
656 }
657 
658 /* Does the given edge contain the given point. The point must already
659  * be known to be contained within the line determined by the edge,
660  * (most likely the point results from an intersection of this edge
661  * with another).
662  *
663  * If we had exact arithmetic, then this function would simply be a
664  * matter of examining whether the y value of the point lies within
665  * the range of y values of the edge. But since intersection points
666  * are not exact due to being rounded to the nearest integer within
667  * the available precision, we must also examine the x value of the
668  * point.
669  *
670  * The definition of "contains" here is that the given intersection
671  * point will be seen by the sweep line after the start event for the
672  * given edge and before the stop event for the edge. See the comments
673  * in the implementation for more details.
674  */
675 static cairo_bool_t
678 {
680  edge->edge.bottom) < 0;
681 }
682 
683 /* Compute the intersection of two edges. The result is provided as a
684  * coordinate pair of 128-bit integers.
685  *
686  * Returns %CAIRO_BO_STATUS_INTERSECTION if there is an intersection
687  * that is within both edges, %CAIRO_BO_STATUS_NO_INTERSECTION if the
688  * intersection of the lines defined by the edges occurs outside of
689  * one or both edges, and %CAIRO_BO_STATUS_PARALLEL if the two edges
690  * are exactly parallel.
691  *
692  * Note that when determining if a candidate intersection is "inside"
693  * an edge, we consider both the infinitesimal shortening and the
694  * infinitesimal tilt rules described by John Hobby. Specifically, if
695  * the intersection is exactly the same as an edge point, it is
696  * effectively outside (no intersection is returned). Also, if the
697  * intersection point has the same
698  */
699 static cairo_bool_t
703 {
704  if (! intersect_lines (a, b, intersection))
705  return FALSE;
706 
708  return FALSE;
709 
711  return FALSE;
712 
713  return TRUE;
714 }
715 
716 static inline int
718  const cairo_bo_event_t *b)
719 {
720  int cmp;
721 
722  cmp = _cairo_bo_point32_compare (&a->point, &b->point);
723  if (cmp)
724  return cmp;
725 
726  cmp = a->type - b->type;
727  if (cmp)
728  return cmp;
729 
730  return a < b ? -1 : a == b ? 0 : 1;
731 }
732 
733 static inline void
735 {
737  pq->size = 0;
738 
739  pq->elements = pq->elements_embedded;
740 }
741 
742 static inline void
744 {
745  if (pq->elements != pq->elements_embedded)
746  free (pq->elements);
747 }
748 
749 static cairo_status_t
751 {
752  cairo_bo_event_t **new_elements;
753  pq->max_size *= 2;
754 
755  if (pq->elements == pq->elements_embedded) {
756  new_elements = _cairo_malloc_ab (pq->max_size,
758  if (unlikely (new_elements == NULL))
760 
761  memcpy (new_elements, pq->elements_embedded,
762  sizeof (pq->elements_embedded));
763  } else {
764  new_elements = _cairo_realloc_ab (pq->elements,
765  pq->max_size,
767  if (unlikely (new_elements == NULL))
769  }
770 
771  pq->elements = new_elements;
772  return CAIRO_STATUS_SUCCESS;
773 }
774 
775 static inline cairo_status_t
777 {
779  int i, parent;
780 
781  if (unlikely (pq->size + 1 == pq->max_size)) {
783 
784  status = _pqueue_grow (pq);
785  if (unlikely (status))
786  return status;
787  }
788 
789  elements = pq->elements;
790 
791  for (i = ++pq->size;
792  i != PQ_FIRST_ENTRY &&
793  cairo_bo_event_compare (event,
794  elements[parent = PQ_PARENT_INDEX (i)]) < 0;
795  i = parent)
796  {
798  }
799 
800  elements[i] = event;
801 
802  return CAIRO_STATUS_SUCCESS;
803 }
804 
805 static inline void
807 {
810  int child, i;
811 
812  tail = elements[pq->size--];
813  if (pq->size == 0) {
815  return;
816  }
817 
818  for (i = PQ_FIRST_ENTRY;
819  (child = PQ_LEFT_CHILD_INDEX (i)) <= pq->size;
820  i = child)
821  {
822  if (child != pq->size &&
824  elements[child]) < 0)
825  {
826  child++;
827  }
828 
830  break;
831 
832  elements[i] = elements[child];
833  }
834  elements[i] = tail;
835 }
836 
837 static inline cairo_status_t
840  cairo_bo_edge_t *e1,
841  cairo_bo_edge_t *e2,
843 {
844  cairo_bo_queue_event_t *event;
845 
846  event = _cairo_freepool_alloc (&queue->pool);
847  if (unlikely (event == NULL))
849 
850  event->type = type;
851  event->e1 = e1;
852  event->e2 = e2;
853  event->point = *point;
854 
855  return _pqueue_push (&queue->pqueue, (cairo_bo_event_t *) event);
856 }
857 
858 static void
860  cairo_bo_event_t *event)
861 {
862  _cairo_freepool_free (&queue->pool, event);
863 }
864 
865 static cairo_bo_event_t *
867 {
868  cairo_bo_event_t *event, *cmp;
869 
870  event = event_queue->pqueue.elements[PQ_FIRST_ENTRY];
871  cmp = *event_queue->start_events;
872  if (event == NULL ||
873  (cmp != NULL && cairo_bo_event_compare (cmp, event) < 0))
874  {
875  event = cmp;
876  event_queue->start_events++;
877  }
878  else
879  {
880  _pqueue_pop (&event_queue->pqueue);
881  }
882 
883  return event;
884 }
885 
889 
890 static void
892  cairo_bo_event_t **start_events,
893  int num_events)
894 {
895  _cairo_bo_event_queue_sort (start_events, num_events);
896  start_events[num_events] = NULL;
897 
898  event_queue->start_events = start_events;
899 
900  _cairo_freepool_init (&event_queue->pool,
902  _pqueue_init (&event_queue->pqueue);
903  event_queue->pqueue.elements[PQ_FIRST_ENTRY] = NULL;
904 }
905 
906 static cairo_status_t
909 {
911 
912  point.y.ordinate = edge->edge.bottom;
913  point.y.approx = EXACT;
915  point.y.ordinate);
916  point.x.approx = EXACT;
917 
918  return _cairo_bo_event_queue_insert (event_queue,
920  edge, NULL,
921  &point);
922 }
923 
924 static void
926 {
927  _pqueue_fini (&event_queue->pqueue);
928  _cairo_freepool_fini (&event_queue->pool);
929 }
930 
931 static inline cairo_status_t
935 {
937 
938  if (_line_equal (&left->edge.line, &right->edge.line))
939  return CAIRO_STATUS_SUCCESS;
940 
941  /* The names "left" and "right" here are correct descriptions of
942  * the order of the two edges within the active edge list. So if a
943  * slope comparison also puts left less than right, then we know
944  * that the intersection of these two segments has already
945  * occurred before the current sweep line position. */
946  if (_slope_compare (left, right) <= 0)
947  return CAIRO_STATUS_SUCCESS;
948 
950  return CAIRO_STATUS_SUCCESS;
951 
952  return _cairo_bo_event_queue_insert (event_queue,
954  left, right,
955  &intersection);
956 }
957 
958 static void
960 {
961  sweep_line->head = NULL;
962  sweep_line->current_y = INT32_MIN;
963  sweep_line->current_edge = NULL;
964 }
965 
966 static cairo_status_t
969 {
970  if (sweep_line->current_edge != NULL) {
972  int cmp;
973 
975  sweep_line->current_edge,
976  edge);
977  if (cmp < 0) {
978  prev = sweep_line->current_edge;
979  next = prev->next;
980  while (next != NULL &&
982  next, edge) < 0)
983  {
984  prev = next, next = prev->next;
985  }
986 
987  prev->next = edge;
988  edge->prev = prev;
989  edge->next = next;
990  if (next != NULL)
991  next->prev = edge;
992  } else if (cmp > 0) {
993  next = sweep_line->current_edge;
994  prev = next->prev;
995  while (prev != NULL &&
997  prev, edge) > 0)
998  {
999  next = prev, prev = next->prev;
1000  }
1001 
1002  next->prev = edge;
1003  edge->next = next;
1004  edge->prev = prev;
1005  if (prev != NULL)
1006  prev->next = edge;
1007  else
1008  sweep_line->head = edge;
1009  } else {
1010  prev = sweep_line->current_edge;
1011  edge->prev = prev;
1012  edge->next = prev->next;
1013  if (prev->next != NULL)
1014  prev->next->prev = edge;
1015  prev->next = edge;
1016  }
1017  } else {
1018  sweep_line->head = edge;
1019  }
1020 
1021  sweep_line->current_edge = edge;
1022 
1023  return CAIRO_STATUS_SUCCESS;
1024 }
1025 
1026 static void
1029 {
1030  if (edge->prev != NULL)
1031  edge->prev->next = edge->next;
1032  else
1033  sweep_line->head = edge->next;
1034 
1035  if (edge->next != NULL)
1036  edge->next->prev = edge->prev;
1037 
1038  if (sweep_line->current_edge == edge)
1039  sweep_line->current_edge = edge->prev ? edge->prev : edge->next;
1040 }
1041 
1042 static void
1046 {
1047  if (left->prev != NULL)
1048  left->prev->next = right;
1049  else
1050  sweep_line->head = right;
1051 
1052  if (right->next != NULL)
1053  right->next->prev = left;
1054 
1055  left->next = right->next;
1056  right->next = left;
1057 
1058  right->prev = left->prev;
1059  left->prev = right;
1060 }
1061 
1062 static inline cairo_bool_t
1064 {
1065  if (_line_equal (&a->edge.line, &b->edge.line))
1066  return TRUE;
1067 
1068  if (_slope_compare (a, b))
1069  return FALSE;
1070 
1071  /* The choice of y is not truly arbitrary since we must guarantee that it
1072  * is greater than the start of either line.
1073  */
1074  if (a->edge.line.p1.y == b->edge.line.p1.y) {
1075  return a->edge.line.p1.x == b->edge.line.p1.x;
1076  } else if (a->edge.line.p1.y < b->edge.line.p1.y) {
1078  a->edge.line.p1.y,
1079  a->edge.line.p1.x) == 0;
1080  } else {
1082  b->edge.line.p1.y,
1083  b->edge.line.p1.x) == 0;
1084  }
1085 }
1086 
1087 static void
1089  int32_t bot,
1091 {
1092  cairo_bo_deferred_t *l = &left->deferred;
1093  cairo_bo_edge_t *right = l->other;
1094 
1095  assert(right->deferred.other == NULL);
1096  if (likely (l->top < bot)) {
1097  _cairo_polygon_add_line (polygon, &left->edge.line, l->top, bot, 1);
1098  _cairo_polygon_add_line (polygon, &right->edge.line, l->top, bot, -1);
1099  }
1100 
1101  l->other = NULL;
1102 }
1103 
1104 static inline void
1107  int top,
1109 {
1110  assert (right != NULL);
1111  assert (right->deferred.other == NULL);
1112 
1113  if (left->deferred.other == right)
1114  return;
1115 
1116  if (left->deferred.other != NULL) {
1117  if (edges_colinear (left->deferred.other, right)) {
1118  cairo_bo_edge_t *old = left->deferred.other;
1119 
1120  /* continuation on right, extend right to cover both */
1121  assert (old->deferred.other == NULL);
1122  assert (old->edge.line.p2.y > old->edge.line.p1.y);
1123 
1124  if (old->edge.line.p1.y < right->edge.line.p1.y)
1125  right->edge.line.p1 = old->edge.line.p1;
1126  if (old->edge.line.p2.y > right->edge.line.p2.y)
1127  right->edge.line.p2 = old->edge.line.p2;
1128  left->deferred.other = right;
1129  return;
1130  }
1131 
1132  edges_end (left, top, polygon);
1133  }
1134 
1135  if (! edges_colinear (left, right)) {
1136  left->deferred.top = top;
1137  left->deferred.other = right;
1138  }
1139 }
1140 
1141 #define is_zero(w) ((w)[0] == 0 || (w)[1] == 0)
1142 
1143 static inline void
1145  int32_t top,
1147 {
1149  int winding[2] = {0, 0};
1150 
1151  /* Yes, this is naive. Consider this a placeholder. */
1152 
1153  while (left != NULL) {
1154  assert (is_zero (winding));
1155 
1156  do {
1157  winding[left->a_or_b] += left->edge.dir;
1158  if (! is_zero (winding))
1159  break;
1160 
1161  if unlikely ((left->deferred.other))
1162  edges_end (left, top, polygon);
1163 
1164  left = left->next;
1165  if (! left)
1166  return;
1167  } while (1);
1168 
1169  right = left->next;
1170  do {
1171  if unlikely ((right->deferred.other))
1172  edges_end (right, top, polygon);
1173 
1174  winding[right->a_or_b] += right->edge.dir;
1175  if (is_zero (winding)) {
1176  if (right->next == NULL ||
1177  ! edges_colinear (right, right->next))
1178  break;
1179  }
1180 
1181  right = right->next;
1182  } while (1);
1183 
1185 
1186  left = right->next;
1187  }
1188 }
1189 
1190 static cairo_status_t
1192  int num_events,
1194 {
1195  cairo_status_t status = CAIRO_STATUS_SUCCESS; /* silence compiler */
1196  cairo_bo_event_queue_t event_queue;
1197  cairo_bo_sweep_line_t sweep_line;
1198  cairo_bo_event_t *event;
1200  cairo_bo_edge_t *e1, *e2;
1201 
1202  _cairo_bo_event_queue_init (&event_queue, start_events, num_events);
1203  _cairo_bo_sweep_line_init (&sweep_line);
1204 
1205  while ((event = _cairo_bo_event_dequeue (&event_queue))) {
1206  if (event->point.y.ordinate != sweep_line.current_y) {
1207  active_edges (sweep_line.head,
1208  sweep_line.current_y,
1209  polygon);
1210  sweep_line.current_y = event->point.y.ordinate;
1211  }
1212 
1213  switch (event->type) {
1215  e1 = &((cairo_bo_start_event_t *) event)->edge;
1216 
1217  status = sweep_line_insert (&sweep_line, e1);
1218  if (unlikely (status))
1219  goto unwind;
1220 
1221  status = event_queue_insert_stop (&event_queue, e1);
1222  if (unlikely (status))
1223  goto unwind;
1224 
1225  left = e1->prev;
1226  right = e1->next;
1227 
1228  if (left != NULL) {
1230  if (unlikely (status))
1231  goto unwind;
1232  }
1233 
1234  if (right != NULL) {
1236  if (unlikely (status))
1237  goto unwind;
1238  }
1239 
1240  break;
1241 
1243  e1 = ((cairo_bo_queue_event_t *) event)->e1;
1244  _cairo_bo_event_queue_delete (&event_queue, event);
1245 
1246  if (e1->deferred.other)
1247  edges_end (e1, sweep_line.current_y, polygon);
1248 
1249  left = e1->prev;
1250  right = e1->next;
1251 
1252  _cairo_bo_sweep_line_delete (&sweep_line, e1);
1253 
1254  if (left != NULL && right != NULL) {
1256  if (unlikely (status))
1257  goto unwind;
1258  }
1259 
1260  break;
1261 
1263  e1 = ((cairo_bo_queue_event_t *) event)->e1;
1264  e2 = ((cairo_bo_queue_event_t *) event)->e2;
1265  _cairo_bo_event_queue_delete (&event_queue, event);
1266 
1267  /* skip this intersection if its edges are not adjacent */
1268  if (e2 != e1->next)
1269  break;
1270 
1271  if (e1->deferred.other)
1272  edges_end (e1, sweep_line.current_y, polygon);
1273  if (e2->deferred.other)
1274  edges_end (e2, sweep_line.current_y, polygon);
1275 
1276  left = e1->prev;
1277  right = e2->next;
1278 
1279  _cairo_bo_sweep_line_swap (&sweep_line, e1, e2);
1280 
1281  /* after the swap e2 is left of e1 */
1282 
1283  if (left != NULL) {
1285  if (unlikely (status))
1286  goto unwind;
1287  }
1288 
1289  if (right != NULL) {
1291  if (unlikely (status))
1292  goto unwind;
1293  }
1294 
1295  break;
1296  }
1297  }
1298 
1299  unwind:
1300  _cairo_bo_event_queue_fini (&event_queue);
1301 
1302  return status;
1303 }
1304 
1307  cairo_polygon_t *b, int winding_b)
1308 {
1311  cairo_bo_start_event_t *events;
1312  cairo_bo_event_t *stack_event_ptrs[ARRAY_LENGTH (stack_events) + 1];
1313  cairo_bo_event_t **event_ptrs;
1314  int num_events;
1315  int i, j;
1316 
1317  /* XXX lazy */
1318  if (winding_a != CAIRO_FILL_RULE_WINDING) {
1319  status = _cairo_polygon_reduce (a, winding_a);
1320  if (unlikely (status))
1321  return status;
1322  }
1323 
1324  if (winding_b != CAIRO_FILL_RULE_WINDING) {
1325  status = _cairo_polygon_reduce (b, winding_b);
1326  if (unlikely (status))
1327  return status;
1328  }
1329 
1330  if (unlikely (0 == a->num_edges))
1331  return CAIRO_STATUS_SUCCESS;
1332 
1333  if (unlikely (0 == b->num_edges)) {
1334  a->num_edges = 0;
1335  return CAIRO_STATUS_SUCCESS;
1336  }
1337 
1338  events = stack_events;
1339  event_ptrs = stack_event_ptrs;
1340  num_events = a->num_edges + b->num_edges;
1341  if (num_events > ARRAY_LENGTH (stack_events)) {
1342  events = _cairo_malloc_ab_plus_c (num_events,
1343  sizeof (cairo_bo_start_event_t) +
1344  sizeof (cairo_bo_event_t *),
1345  sizeof (cairo_bo_event_t *));
1346  if (unlikely (events == NULL))
1348 
1349  event_ptrs = (cairo_bo_event_t **) (events + num_events);
1350  }
1351 
1352  j = 0;
1353  for (i = 0; i < a->num_edges; i++) {
1354  event_ptrs[j] = (cairo_bo_event_t *) &events[j];
1355 
1356  events[j].type = CAIRO_BO_EVENT_TYPE_START;
1357  events[j].point.y.ordinate = a->edges[i].top;
1358  events[j].point.y.approx = EXACT;
1359  events[j].point.x.ordinate =
1360  _line_compute_intersection_x_for_y (&a->edges[i].line,
1361  events[j].point.y.ordinate);
1362  events[j].point.x.approx = EXACT;
1363 
1364  events[j].edge.a_or_b = 0;
1365  events[j].edge.edge = a->edges[i];
1366  events[j].edge.deferred.other = NULL;
1367  events[j].edge.prev = NULL;
1368  events[j].edge.next = NULL;
1369  j++;
1370  }
1371 
1372  for (i = 0; i < b->num_edges; i++) {
1373  event_ptrs[j] = (cairo_bo_event_t *) &events[j];
1374 
1375  events[j].type = CAIRO_BO_EVENT_TYPE_START;
1376  events[j].point.y.ordinate = b->edges[i].top;
1377  events[j].point.y.approx = EXACT;
1378  events[j].point.x.ordinate =
1379  _line_compute_intersection_x_for_y (&b->edges[i].line,
1380  events[j].point.y.ordinate);
1381  events[j].point.x.approx = EXACT;
1382 
1383  events[j].edge.a_or_b = 1;
1384  events[j].edge.edge = b->edges[i];
1385  events[j].edge.deferred.other = NULL;
1386  events[j].edge.prev = NULL;
1387  events[j].edge.next = NULL;
1388  j++;
1389  }
1390  assert (j == num_events);
1391 
1392 #if 0
1393  {
1394  FILE *file = fopen ("clip_a.txt", "w");
1396  fclose (file);
1397  }
1398  {
1399  FILE *file = fopen ("clip_b.txt", "w");
1401  fclose (file);
1402  }
1403 #endif
1404 
1405  a->num_edges = 0;
1406  status = intersection_sweep (event_ptrs, num_events, a);
1407  if (events != stack_events)
1408  free (events);
1409 
1410 #if 0
1411  {
1412  FILE *file = fopen ("clip_result.txt", "w");
1414  fclose (file);
1415  }
1416 #endif
1417 
1418  return status;
1419 }
1420 
1423  cairo_fill_rule_t *winding,
1424  cairo_box_t *boxes,
1425  int num_boxes)
1426 {
1429  int n;
1430 
1431  if (num_boxes == 0) {
1432  polygon->num_edges = 0;
1433  return CAIRO_STATUS_SUCCESS;
1434  }
1435 
1436  for (n = 0; n < num_boxes; n++) {
1437  if (polygon->extents.p1.x >= boxes[n].p1.x &&
1438  polygon->extents.p2.x <= boxes[n].p2.x &&
1439  polygon->extents.p1.y >= boxes[n].p1.y &&
1440  polygon->extents.p2.y <= boxes[n].p2.y)
1441  {
1442  return CAIRO_STATUS_SUCCESS;
1443  }
1444  }
1445 
1446  _cairo_polygon_init (&b, NULL, 0);
1447  for (n = 0; n < num_boxes; n++) {
1448  if (boxes[n].p2.x > polygon->extents.p1.x &&
1449  boxes[n].p1.x < polygon->extents.p2.x &&
1450  boxes[n].p2.y > polygon->extents.p1.y &&
1451  boxes[n].p1.y < polygon->extents.p2.y)
1452  {
1453  cairo_point_t p1, p2;
1454 
1455  p1.y = boxes[n].p1.y;
1456  p2.y = boxes[n].p2.y;
1457 
1458  p2.x = p1.x = boxes[n].p1.x;
1460 
1461  p2.x = p1.x = boxes[n].p2.x;
1463  }
1464  }
1465 
1469 
1470  *winding = CAIRO_FILL_RULE_WINDING;
1471  return status;
1472 }
#define type(a)
Definition: aptex-macros.h:171
#define next(a)
Definition: aptex-macros.h:924
#define tail
Definition: aptex-macros.h:514
int cmp(const void *p, const void *q)
Definition: bkmk2uni.c:1611
char * p2
Definition: bmpfont.h:62
char * p1
Definition: bmpfont.h:62
#define CAIRO_COMBSORT_DECLARE(NAME, TYPE, CMP)
#define CAIRO_STACK_ARRAY_LENGTH(T)
void _cairo_debug_print_polygon(FILE *stream, cairo_polygon_t *polygon)
Definition: cairo-debug.c:271
cairo_status_t _cairo_error(cairo_status_t status)
Definition: cairo-error.c:65
static cairo_fixed_t _cairo_fixed_mul_div_floor(cairo_fixed_t a, cairo_fixed_t b, cairo_fixed_t c)
int32_t cairo_fixed_t
void _cairo_freepool_fini(cairo_freepool_t *freepool)
static void _cairo_freepool_free(cairo_freepool_t *freepool, void *ptr)
static void * _cairo_freepool_alloc(cairo_freepool_t *freepool)
void _cairo_freepool_init(cairo_freepool_t *freepool, unsigned nodesize)
#define _cairo_realloc_ab(ptr, a, size)
#define _cairo_malloc_ab(a, size)
#define _cairo_malloc_ab_plus_c(a, size, c)
struct _cairo_bo_intersect_point cairo_bo_intersect_point_t
struct _cairo_bo_deferred cairo_bo_deferred_t
struct _pqueue pqueue_t
struct _cairo_bo_queue_event cairo_bo_queue_event_t
struct _cairo_bo_start_event cairo_bo_start_event_t
struct _cairo_bo_event cairo_bo_event_t
struct _cairo_bo_sweep_line cairo_bo_sweep_line_t
struct _cairo_bo_intersect_ordinate cairo_bo_intersect_ordinate_t
cairo_bo_event_type_t
@ CAIRO_BO_EVENT_TYPE_START
@ CAIRO_BO_EVENT_TYPE_STOP
@ CAIRO_BO_EVENT_TYPE_INTERSECTION
cairo_status_t _cairo_polygon_intersect(cairo_polygon_t *a, int winding_a, cairo_polygon_t *b, int winding_b)
struct _cairo_bo_event_queue cairo_bo_event_queue_t
cairo_status_t _cairo_polygon_intersect_with_boxes(cairo_polygon_t *polygon, cairo_fill_rule_t *winding, cairo_box_t *boxes, int num_boxes)
cairo_status_t _cairo_polygon_reduce(cairo_polygon_t *polygon, cairo_fill_rule_t fill_rule)
void _cairo_polygon_init(cairo_polygon_t *polygon, const cairo_box_t *limits, int num_limits)
cairo_status_t _cairo_polygon_add_line(cairo_polygon_t *polygon, const cairo_line_t *line, int top, int bottom, int dir)
void _cairo_polygon_fini(cairo_polygon_t *polygon)
cairo_status_t _cairo_polygon_add_external_edge(void *polygon, const cairo_point_t *p1, const cairo_point_t *p2)
int _cairo_int64_lt(cairo_int64_t a, cairo_int64_t b)
#define _cairo_int64_negate(a)
cairo_quorem64_t _cairo_int_96by64_32x64_divrem(cairo_int128_t num, cairo_int64_t den)
#define _cairo_int64_sub(a, b)
#define _cairo_int64_is_zero(a)
#define _cairo_int64_mul(a, b)
int _cairo_int64_cmp(cairo_int64_t a, cairo_int64_t b)
#define _cairo_int64_negative(a)
cairo_int64_t _cairo_int32_to_int64(int32_t i)
#define _cairo_int64x32_128_mul(a, b)
int _cairo_int128_cmp(cairo_int128_t a, cairo_int128_t b)
#define _cairo_int128_sub(a, b)
#define _cairo_int64_le(a, b)
#define _cairo_int64_eq(a, b)
cairo_int64_t _cairo_int32x32_64_mul(int32_t a, int32_t b)
enum _cairo_fill_rule cairo_fill_rule_t
int cairo_bool_t
Definition: cairo.h:107
@ CAIRO_STATUS_SUCCESS
Definition: cairo.h:315
@ CAIRO_STATUS_NO_MEMORY
Definition: cairo.h:317
enum _cairo_status cairo_status_t
@ CAIRO_FILL_RULE_WINDING
Definition: cairo.h:754
#define ARRAY_LENGTH(__array)
Definition: cairoint.h:137
static void _pqueue_init(pqueue_t *pq)
static cairo_int64_t det32_64(int32_t a, int32_t b, int32_t c, int32_t d)
static void active_edges(cairo_bo_edge_t *left, int32_t top, cairo_polygon_t *polygon)
#define B
Definition: gensi.hpp:249
static int edge_compare_for_y_against_x(const cairo_bo_edge_t *a, int32_t y, int32_t x)
static cairo_status_t _pqueue_push(pqueue_t *pq, cairo_bo_event_t *event)
#define PQ_LEFT_CHILD_INDEX(i)
static cairo_status_t event_queue_insert_if_intersect_below_current_y(cairo_bo_event_queue_t *event_queue, cairo_bo_edge_t *left, cairo_bo_edge_t *right)
static void _pqueue_pop(pqueue_t *pq)
static void _cairo_bo_sweep_line_swap(cairo_bo_sweep_line_t *sweep_line, cairo_bo_edge_t *left, cairo_bo_edge_t *right)
static void _cairo_bo_event_queue_delete(cairo_bo_event_queue_t *queue, cairo_bo_event_t *event)
static int cairo_bo_event_compare(const cairo_bo_event_t *a, const cairo_bo_event_t *b)
static cairo_bool_t _cairo_bo_edge_contains_intersect_point(cairo_bo_edge_t *edge, cairo_bo_intersect_point_t *point)
static cairo_bool_t intersect_lines(cairo_bo_edge_t *a, cairo_bo_edge_t *b, cairo_bo_intersect_point_t *intersection)
static cairo_int128_t det64x32_128(cairo_int64_t a, int32_t b, cairo_int64_t c, int32_t d)
static cairo_status_t _pqueue_grow(pqueue_t *pq)
static cairo_bool_t edges_colinear(const cairo_bo_edge_t *a, const cairo_bo_edge_t *b)
static void _cairo_bo_sweep_line_init(cairo_bo_sweep_line_t *sweep_line)
static int edges_compare_x_for_y(const cairo_bo_edge_t *a, const cairo_bo_edge_t *b, int32_t y)
static cairo_fixed_t _line_compute_intersection_x_for_y(const cairo_line_t *line, cairo_fixed_t y)
static void _cairo_bo_sweep_line_delete(cairo_bo_sweep_line_t *sweep_line, cairo_bo_edge_t *edge)
static cairo_bo_intersect_ordinate_t round_to_nearest(cairo_quorem64_t d, cairo_int64_t den)
static cairo_status_t sweep_line_insert(cairo_bo_sweep_line_t *sweep_line, cairo_bo_edge_t *edge)
#define A
static void _cairo_bo_event_queue_sort(cairo_bo_event_t **base, unsigned int nmemb)
static cairo_status_t intersection_sweep(cairo_bo_event_t **start_events, int num_events, cairo_polygon_t *polygon)
#define L
static cairo_status_t event_queue_insert_stop(cairo_bo_event_queue_t *event_queue, cairo_bo_edge_t *edge)
#define PQ_FIRST_ENTRY
#define PQ_PARENT_INDEX(i)
static void _cairo_bo_event_queue_init(cairo_bo_event_queue_t *event_queue, cairo_bo_event_t **start_events, int num_events)
static int _line_equal(const cairo_line_t *a, const cairo_line_t *b)
static int _slope_compare(const cairo_bo_edge_t *a, const cairo_bo_edge_t *b)
static void _pqueue_fini(pqueue_t *pq)
static int edges_compare_x_for_y_general(const cairo_bo_edge_t *a, const cairo_bo_edge_t *b, int32_t y)
static void _cairo_bo_event_queue_fini(cairo_bo_event_queue_t *event_queue)
static int _cairo_bo_sweep_line_compare_edges(cairo_bo_sweep_line_t *sweep_line, const cairo_bo_edge_t *a, const cairo_bo_edge_t *b)
static int _cairo_bo_point32_compare(cairo_bo_intersect_point_t const *a, cairo_bo_intersect_point_t const *b)
static void edges_end(cairo_bo_edge_t *left, int32_t bot, cairo_polygon_t *polygon)
static int _cairo_bo_intersect_ordinate_32_compare(cairo_bo_intersect_ordinate_t a, int32_t b)
static void edges_start_or_continue(cairo_bo_edge_t *left, cairo_bo_edge_t *right, int top, cairo_polygon_t *polygon)
static cairo_status_t _cairo_bo_event_queue_insert(cairo_bo_event_queue_t *queue, cairo_bo_event_type_t type, cairo_bo_edge_t *e1, cairo_bo_edge_t *e2, const cairo_bo_intersect_point_t *point)
#define is_zero(w)
static cairo_bool_t _cairo_bo_edge_intersect(cairo_bo_edge_t *a, cairo_bo_edge_t *b, cairo_bo_intersect_point_t *intersection)
static cairo_bo_event_t * _cairo_bo_event_dequeue(cairo_bo_event_queue_t *event_queue)
#define n
Definition: t4ht.c:1290
#define b
Definition: jpegint.h:372
@ FALSE
Definition: dd.h:101
@ TRUE
Definition: dd.h:102
#define free(a)
Definition: decNumber.cpp:310
#define fopen
Definition: xxstdio.h:21
static gregorio_element ** elements
static FIELD_PTR prev
Definition: genind.c:36
#define c(n)
Definition: gpos-common.c:150
#define a(n)
Definition: gpos-common.c:148
#define d(n)
Definition: gpos-common.c:151
#define memcpy(d, s, n)
Definition: gsftopk.c:64
assert(pcxLoadImage24((char *)((void *) 0), fp, pinfo, hdr))
#define likely(x)
Definition: jbig2arith.cc:115
#define unlikely(x)
Definition: jbig2arith.cc:116
#define NULL
Definition: ftobjs.h:61
small capitals from c petite p scientific i
Definition: afcover.h:80
sizeof(AF_ModuleRec)
kerning y
Definition: ttdriver.c:212
@ right
Definition: annotate.c:15
int int double double double char double char * top
Definition: gdfx.h:19
#define INT32_MIN
Definition: stdint.h:136
signed int int32_t
Definition: stdint.h:77
int den
Definition: dvi.c:19
#define fclose
Definition: debug.h:100
float x
Definition: cordic.py:15
#define status
#define DEFAULT
#define parent(a, t)
Definition: interp.c:105
lft_cell * left
Definition: routines.h:73
cairo_bo_deferred_t deferred
cairo_bo_event_t ** start_events
enum _cairo_bo_intersect_ordinate::@454 approx
cairo_bo_intersect_ordinate_t x
cairo_bo_intersect_ordinate_t y
cairo_bo_event_type_t type
cairo_bo_event_type_t type
cairo_line_t line
cairo_point_t p2
cairo_point_t p1
cairo_bo_event_t * elements_embedded[1024]
cairo_bo_event_t ** elements
Definition: job.h:44
struct quorem x
struct edge * prev
cairo_edge_t edge
struct edge * next
Definition: filedef.h:30
Definition: bdf.c:133
Definition: mpost.c:238
double y
Definition: mpost.c:239
double x
Definition: mpost.c:239
#define FILE
Definition: t1stdio.h:34
int j
Definition: t4ht.c:1589
@ R
Definition: ubidiimp.h:46