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-bentley-ottmann.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-combsort-inline.h"
42 #include "cairo-error-private.h"
43 #include "cairo-freelist-private.h"
44 #include "cairo-line-inline.h"
45 #include "cairo-traps-private.h"
46 
47 #define DEBUG_PRINT_STATE 0
48 #define DEBUG_EVENTS 0
49 #define DEBUG_TRAPS 0
50 
52 
55  enum { EXACT, INEXACT } exactness;
57 
58 typedef struct _cairo_bo_intersect_point {
62 
63 typedef struct _cairo_bo_edge cairo_bo_edge_t;
64 typedef struct _cairo_bo_trap cairo_bo_trap_t;
65 
66 /* A deferred trapezoid of an edge */
67 struct _cairo_bo_trap {
69  int32_t top;
70 };
71 
72 struct _cairo_bo_edge {
78 };
79 
80 /* the parent is always given by index/2 */
81 #define PQ_PARENT_INDEX(i) ((i) >> 1)
82 #define PQ_FIRST_ENTRY 1
83 
84 /* left and right children are index * 2 and (index * 2) +1 respectively */
85 #define PQ_LEFT_CHILD_INDEX(i) ((i) << 1)
86 
87 typedef enum {
92 
93 typedef struct _cairo_bo_event {
97 
98 typedef struct _cairo_bo_start_event {
103 
104 typedef struct _cairo_bo_queue_event {
110 
111 typedef struct _pqueue {
113 
117 
118 typedef struct _cairo_bo_event_queue {
123 
124 typedef struct _cairo_bo_sweep_line {
130 
131 #if DEBUG_TRAPS
132 static void
133 dump_traps (cairo_traps_t *traps, const char *filename)
134 {
135  FILE *file;
137  int n;
138 
139  if (getenv ("CAIRO_DEBUG_TRAPS") == NULL)
140  return;
141 
142 #if 0
143  if (traps->has_limits) {
144  printf ("%s: limits=(%d, %d, %d, %d)\n",
145  filename,
146  traps->limits.p1.x, traps->limits.p1.y,
147  traps->limits.p2.x, traps->limits.p2.y);
148  }
149 #endif
150  _cairo_traps_extents (traps, &extents);
151  printf ("%s: extents=(%d, %d, %d, %d)\n",
152  filename,
153  extents.p1.x, extents.p1.y,
154  extents.p2.x, extents.p2.y);
155 
156  file = fopen (filename, "a");
157  if (file != NULL) {
158  for (n = 0; n < traps->num_traps; n++) {
159  fprintf (file, "%d %d L:(%d, %d), (%d, %d) R:(%d, %d), (%d, %d)\n",
160  traps->traps[n].top,
161  traps->traps[n].bottom,
162  traps->traps[n].left.p1.x,
163  traps->traps[n].left.p1.y,
164  traps->traps[n].left.p2.x,
165  traps->traps[n].left.p2.y,
166  traps->traps[n].right.p1.x,
167  traps->traps[n].right.p1.y,
168  traps->traps[n].right.p2.x,
169  traps->traps[n].right.p2.y);
170  }
171  fprintf (file, "\n");
172  fclose (file);
173  }
174 }
175 
176 static void
177 dump_edges (cairo_bo_start_event_t *events,
178  int num_edges,
179  const char *filename)
180 {
181  FILE *file;
182  int n;
183 
184  if (getenv ("CAIRO_DEBUG_TRAPS") == NULL)
185  return;
186 
187  file = fopen (filename, "a");
188  if (file != NULL) {
189  for (n = 0; n < num_edges; n++) {
190  fprintf (file, "(%d, %d), (%d, %d) %d %d %d\n",
191  events[n].edge.edge.line.p1.x,
192  events[n].edge.edge.line.p1.y,
193  events[n].edge.edge.line.p2.x,
194  events[n].edge.edge.line.p2.y,
195  events[n].edge.edge.top,
196  events[n].edge.edge.bottom,
197  events[n].edge.edge.dir);
198  }
199  fprintf (file, "\n");
200  fclose (file);
201  }
202 }
203 #endif
204 
205 static cairo_fixed_t
208 {
209  cairo_fixed_t x, dy;
210 
211  if (y == line->p1.y)
212  return line->p1.x;
213  if (y == line->p2.y)
214  return line->p2.x;
215 
216  x = line->p1.x;
217  dy = line->p2.y - line->p1.y;
218  if (dy != 0) {
219  x += _cairo_fixed_mul_div_floor (y - line->p1.y,
220  line->p2.x - line->p1.x,
221  dy);
222  }
223 
224  return x;
225 }
226 
227 static inline int
229  cairo_bo_point32_t const *b)
230 {
231  int cmp;
232 
233  cmp = a->y - b->y;
234  if (cmp)
235  return cmp;
236 
237  return a->x - b->x;
238 }
239 
240 /* Compare the slope of a to the slope of b, returning 1, 0, -1 if the
241  * slope a is respectively greater than, equal to, or less than the
242  * slope of b.
243  *
244  * For each edge, consider the direction vector formed from:
245  *
246  * top -> bottom
247  *
248  * which is:
249  *
250  * (dx, dy) = (line.p2.x - line.p1.x, line.p2.y - line.p1.y)
251  *
252  * We then define the slope of each edge as dx/dy, (which is the
253  * inverse of the slope typically used in math instruction). We never
254  * compute a slope directly as the value approaches infinity, but we
255  * can derive a slope comparison without division as follows, (where
256  * the ? represents our compare operator).
257  *
258  * 1. slope(a) ? slope(b)
259  * 2. adx/ady ? bdx/bdy
260  * 3. (adx * bdy) ? (bdx * ady)
261  *
262  * Note that from step 2 to step 3 there is no change needed in the
263  * sign of the result since both ady and bdy are guaranteed to be
264  * greater than or equal to 0.
265  *
266  * When using this slope comparison to sort edges, some care is needed
267  * when interpreting the results. Since the slope compare operates on
268  * distance vectors from top to bottom it gives a correct left to
269  * right sort for edges that have a common top point, (such as two
270  * edges with start events at the same location). On the other hand,
271  * the sense of the result will be exactly reversed for two edges that
272  * have a common stop point.
273  */
274 static inline int
276  const cairo_bo_edge_t *b)
277 {
278  /* XXX: We're assuming here that dx and dy will still fit in 32
279  * bits. That's not true in general as there could be overflow. We
280  * should prevent that before the tessellation algorithm
281  * begins.
282  */
283  int32_t adx = a->edge.line.p2.x - a->edge.line.p1.x;
284  int32_t bdx = b->edge.line.p2.x - b->edge.line.p1.x;
285 
286  /* Since the dy's are all positive by construction we can fast
287  * path several common cases.
288  */
289 
290  /* First check for vertical lines. */
291  if (adx == 0)
292  return -bdx;
293  if (bdx == 0)
294  return adx;
295 
296  /* Then where the two edges point in different directions wrt x. */
297  if ((adx ^ bdx) < 0)
298  return adx;
299 
300  /* Finally we actually need to do the general comparison. */
301  {
302  int32_t ady = a->edge.line.p2.y - a->edge.line.p1.y;
303  int32_t bdy = b->edge.line.p2.y - b->edge.line.p1.y;
304  cairo_int64_t adx_bdy = _cairo_int32x32_64_mul (adx, bdy);
305  cairo_int64_t bdx_ady = _cairo_int32x32_64_mul (bdx, ady);
306 
307  return _cairo_int64_cmp (adx_bdy, bdx_ady);
308  }
309 }
310 
311 
312 /*
313  * We need to compare the x-coordinate of a line for a particular y wrt to a
314  * given x, without loss of precision.
315  *
316  * The x-coordinate along an edge for a given y is:
317  * X = A_x + (Y - A_y) * A_dx / A_dy
318  *
319  * So the inequality we wish to test is:
320  * A_x + (Y - A_y) * A_dx / A_dy ∘ X
321  * where ∘ is our inequality operator.
322  *
323  * By construction, we know that A_dy (and (Y - A_y)) are
324  * all positive, so we can rearrange it thus without causing a sign change:
325  * (Y - A_y) * A_dx ∘ (X - A_x) * A_dy
326  *
327  * Given the assumption that all the deltas fit within 32 bits, we can compute
328  * this comparison directly using 64 bit arithmetic.
329  *
330  * See the similar discussion for _slope_compare() and
331  * edges_compare_x_for_y_general().
332  */
333 static int
335  int32_t y,
336  int32_t x)
337 {
338  int32_t adx, ady;
339  int32_t dx, dy;
340  cairo_int64_t L, R;
341 
342  if (x < a->edge.line.p1.x && x < a->edge.line.p2.x)
343  return 1;
344  if (x > a->edge.line.p1.x && x > a->edge.line.p2.x)
345  return -1;
346 
347  adx = a->edge.line.p2.x - a->edge.line.p1.x;
348  dx = x - a->edge.line.p1.x;
349 
350  if (adx == 0)
351  return -dx;
352  if (dx == 0 || (adx ^ dx) < 0)
353  return adx;
354 
355  dy = y - a->edge.line.p1.y;
356  ady = a->edge.line.p2.y - a->edge.line.p1.y;
357 
358  L = _cairo_int32x32_64_mul (dy, adx);
359  R = _cairo_int32x32_64_mul (dx, ady);
360 
361  return _cairo_int64_cmp (L, R);
362 }
363 
364 static inline int
366  const cairo_bo_edge_t *a,
367  const cairo_bo_edge_t *b)
368 {
369  int cmp;
370 
371  cmp = cairo_lines_compare_at_y (&a->edge.line,
372  &b->edge.line,
373  sweep_line->current_y);
374  if (cmp)
375  return cmp;
376 
377  /* We've got two collinear edges now. */
378  return b->edge.bottom - a->edge.bottom;
379 }
380 
381 static inline cairo_int64_t
383  int32_t c, int32_t d)
384 {
385  /* det = a * d - b * c */
388 }
389 
390 static inline cairo_int128_t
393 {
394  /* det = a * d - b * c */
397 }
398 
399 /* Compute the intersection of two lines as defined by two edges. The
400  * result is provided as a coordinate pair of 128-bit integers.
401  *
402  * Returns %CAIRO_BO_STATUS_INTERSECTION if there is an intersection or
403  * %CAIRO_BO_STATUS_PARALLEL if the two lines are exactly parallel.
404  */
405 static cairo_bool_t
409 {
410  cairo_int64_t a_det, b_det;
411 
412  /* XXX: We're assuming here that dx and dy will still fit in 32
413  * bits. That's not true in general as there could be overflow. We
414  * should prevent that before the tessellation algorithm begins.
415  * What we're doing to mitigate this is to perform clamping in
416  * cairo_bo_tessellate_polygon().
417  */
418  int32_t dx1 = a->edge.line.p1.x - a->edge.line.p2.x;
419  int32_t dy1 = a->edge.line.p1.y - a->edge.line.p2.y;
420 
421  int32_t dx2 = b->edge.line.p1.x - b->edge.line.p2.x;
422  int32_t dy2 = b->edge.line.p1.y - b->edge.line.p2.y;
423 
424  cairo_int64_t den_det;
426  cairo_quorem64_t qr;
427 
428  den_det = det32_64 (dx1, dy1, dx2, dy2);
429 
430  /* Q: Can we determine that the lines do not intersect (within range)
431  * much more cheaply than computing the intersection point i.e. by
432  * avoiding the division?
433  *
434  * X = ax + t * adx = bx + s * bdx;
435  * Y = ay + t * ady = by + s * bdy;
436  * ∴ t * (ady*bdx - bdy*adx) = bdx * (by - ay) + bdy * (ax - bx)
437  * => t * L = R
438  *
439  * Therefore we can reject any intersection (under the criteria for
440  * valid intersection events) if:
441  * L^R < 0 => t < 0, or
442  * L<R => t > 1
443  *
444  * (where top/bottom must at least extend to the line endpoints).
445  *
446  * A similar substitution can be performed for s, yielding:
447  * s * (ady*bdx - bdy*adx) = ady * (ax - bx) - adx * (ay - by)
448  */
449  R = det32_64 (dx2, dy2,
450  b->edge.line.p1.x - a->edge.line.p1.x,
451  b->edge.line.p1.y - a->edge.line.p1.y);
452  if (_cairo_int64_negative (den_det)) {
453  if (_cairo_int64_ge (den_det, R))
454  return FALSE;
455  } else {
456  if (_cairo_int64_le (den_det, R))
457  return FALSE;
458  }
459 
460  R = det32_64 (dy1, dx1,
461  a->edge.line.p1.y - b->edge.line.p1.y,
462  a->edge.line.p1.x - b->edge.line.p1.x);
463  if (_cairo_int64_negative (den_det)) {
464  if (_cairo_int64_ge (den_det, R))
465  return FALSE;
466  } else {
467  if (_cairo_int64_le (den_det, R))
468  return FALSE;
469  }
470 
471  /* We now know that the two lines should intersect within range. */
472 
473  a_det = det32_64 (a->edge.line.p1.x, a->edge.line.p1.y,
474  a->edge.line.p2.x, a->edge.line.p2.y);
475  b_det = det32_64 (b->edge.line.p1.x, b->edge.line.p1.y,
476  b->edge.line.p2.x, b->edge.line.p2.y);
477 
478  /* x = det (a_det, dx1, b_det, dx2) / den_det */
480  b_det, dx2),
481  den_det);
482  if (_cairo_int64_eq (qr.rem, den_det))
483  return FALSE;
484 #if 0
485  intersection->x.exactness = _cairo_int64_is_zero (qr.rem) ? EXACT : INEXACT;
486 #else
487  intersection->x.exactness = EXACT;
488  if (! _cairo_int64_is_zero (qr.rem)) {
489  if (_cairo_int64_negative (den_det) ^ _cairo_int64_negative (qr.rem))
490  qr.rem = _cairo_int64_negate (qr.rem);
492  if (_cairo_int64_ge (qr.rem, den_det)) {
493  qr.quo = _cairo_int64_add (qr.quo,
495  } else
496  intersection->x.exactness = INEXACT;
497  }
498 #endif
499  intersection->x.ordinate = _cairo_int64_to_int32 (qr.quo);
500 
501  /* y = det (a_det, dy1, b_det, dy2) / den_det */
503  b_det, dy2),
504  den_det);
505  if (_cairo_int64_eq (qr.rem, den_det))
506  return FALSE;
507 #if 0
508  intersection->y.exactness = _cairo_int64_is_zero (qr.rem) ? EXACT : INEXACT;
509 #else
510  intersection->y.exactness = EXACT;
511  if (! _cairo_int64_is_zero (qr.rem)) {
512  if (_cairo_int64_negative (den_det) ^ _cairo_int64_negative (qr.rem))
513  qr.rem = _cairo_int64_negate (qr.rem);
515  if (_cairo_int64_ge (qr.rem, den_det)) {
516  qr.quo = _cairo_int64_add (qr.quo,
518  } else
519  intersection->y.exactness = INEXACT;
520  }
521 #endif
522  intersection->y.ordinate = _cairo_int64_to_int32 (qr.quo);
523 
524  return TRUE;
525 }
526 
527 static int
529  int32_t b)
530 {
531  /* First compare the quotient */
532  if (a.ordinate > b)
533  return +1;
534  if (a.ordinate < b)
535  return -1;
536  /* With quotient identical, if remainder is 0 then compare equal */
537  /* Otherwise, the non-zero remainder makes a > b */
538  return INEXACT == a.exactness;
539 }
540 
541 /* Does the given edge contain the given point. The point must already
542  * be known to be contained within the line determined by the edge,
543  * (most likely the point results from an intersection of this edge
544  * with another).
545  *
546  * If we had exact arithmetic, then this function would simply be a
547  * matter of examining whether the y value of the point lies within
548  * the range of y values of the edge. But since intersection points
549  * are not exact due to being rounded to the nearest integer within
550  * the available precision, we must also examine the x value of the
551  * point.
552  *
553  * The definition of "contains" here is that the given intersection
554  * point will be seen by the sweep line after the start event for the
555  * given edge and before the stop event for the edge. See the comments
556  * in the implementation for more details.
557  */
558 static cairo_bool_t
561 {
562  int cmp_top, cmp_bottom;
563 
564  /* XXX: When running the actual algorithm, we don't actually need to
565  * compare against edge->top at all here, since any intersection above
566  * top is eliminated early via a slope comparison. We're leaving these
567  * here for now only for the sake of the quadratic-time intersection
568  * finder which needs them.
569  */
570 
572  edge->edge.top);
574  edge->edge.bottom);
575 
576  if (cmp_top < 0 || cmp_bottom > 0)
577  {
578  return FALSE;
579  }
580 
581  if (cmp_top > 0 && cmp_bottom < 0)
582  {
583  return TRUE;
584  }
585 
586  /* At this stage, the point lies on the same y value as either
587  * edge->top or edge->bottom, so we have to examine the x value in
588  * order to properly determine containment. */
589 
590  /* If the y value of the point is the same as the y value of the
591  * top of the edge, then the x value of the point must be greater
592  * to be considered as inside the edge. Similarly, if the y value
593  * of the point is the same as the y value of the bottom of the
594  * edge, then the x value of the point must be less to be
595  * considered as inside. */
596 
597  if (cmp_top == 0) {
598  cairo_fixed_t top_x;
599 
601  edge->edge.top);
602  return _cairo_bo_intersect_ordinate_32_compare (point->x, top_x) > 0;
603  } else { /* cmp_bottom == 0 */
604  cairo_fixed_t bot_x;
605 
607  edge->edge.bottom);
608  return _cairo_bo_intersect_ordinate_32_compare (point->x, bot_x) < 0;
609  }
610 }
611 
612 /* Compute the intersection of two edges. The result is provided as a
613  * coordinate pair of 128-bit integers.
614  *
615  * Returns %CAIRO_BO_STATUS_INTERSECTION if there is an intersection
616  * that is within both edges, %CAIRO_BO_STATUS_NO_INTERSECTION if the
617  * intersection of the lines defined by the edges occurs outside of
618  * one or both edges, and %CAIRO_BO_STATUS_PARALLEL if the two edges
619  * are exactly parallel.
620  *
621  * Note that when determining if a candidate intersection is "inside"
622  * an edge, we consider both the infinitesimal shortening and the
623  * infinitesimal tilt rules described by John Hobby. Specifically, if
624  * the intersection is exactly the same as an edge point, it is
625  * effectively outside (no intersection is returned). Also, if the
626  * intersection point has the same
627  */
628 static cairo_bool_t
632 {
634 
635  if (! intersect_lines (a, b, &quorem))
636  return FALSE;
637 
639  return FALSE;
640 
642  return FALSE;
643 
644  /* Now that we've correctly compared the intersection point and
645  * determined that it lies within the edge, then we know that we
646  * no longer need any more bits of storage for the intersection
647  * than we do for our edge coordinates. We also no longer need the
648  * remainder from the division. */
649  intersection->x = quorem.x.ordinate;
650  intersection->y = quorem.y.ordinate;
651 
652  return TRUE;
653 }
654 
655 static inline int
657  const cairo_bo_event_t *b)
658 {
659  int cmp;
660 
661  cmp = _cairo_bo_point32_compare (&a->point, &b->point);
662  if (cmp)
663  return cmp;
664 
665  cmp = a->type - b->type;
666  if (cmp)
667  return cmp;
668 
669  return a - b;
670 }
671 
672 static inline void
674 {
676  pq->size = 0;
677 
678  pq->elements = pq->elements_embedded;
679 }
680 
681 static inline void
683 {
684  if (pq->elements != pq->elements_embedded)
685  free (pq->elements);
686 }
687 
688 static cairo_status_t
690 {
691  cairo_bo_event_t **new_elements;
692  pq->max_size *= 2;
693 
694  if (pq->elements == pq->elements_embedded) {
695  new_elements = _cairo_malloc_ab (pq->max_size,
697  if (unlikely (new_elements == NULL))
699 
700  memcpy (new_elements, pq->elements_embedded,
701  sizeof (pq->elements_embedded));
702  } else {
703  new_elements = _cairo_realloc_ab (pq->elements,
704  pq->max_size,
706  if (unlikely (new_elements == NULL))
708  }
709 
710  pq->elements = new_elements;
711  return CAIRO_STATUS_SUCCESS;
712 }
713 
714 static inline cairo_status_t
716 {
718  int i, parent;
719 
720  if (unlikely (pq->size + 1 == pq->max_size)) {
722 
723  status = _pqueue_grow (pq);
724  if (unlikely (status))
725  return status;
726  }
727 
728  elements = pq->elements;
729 
730  for (i = ++pq->size;
731  i != PQ_FIRST_ENTRY &&
732  cairo_bo_event_compare (event,
733  elements[parent = PQ_PARENT_INDEX (i)]) < 0;
734  i = parent)
735  {
737  }
738 
739  elements[i] = event;
740 
741  return CAIRO_STATUS_SUCCESS;
742 }
743 
744 static inline void
746 {
749  int child, i;
750 
751  tail = elements[pq->size--];
752  if (pq->size == 0) {
754  return;
755  }
756 
757  for (i = PQ_FIRST_ENTRY;
758  (child = PQ_LEFT_CHILD_INDEX (i)) <= pq->size;
759  i = child)
760  {
761  if (child != pq->size &&
763  elements[child]) < 0)
764  {
765  child++;
766  }
767 
769  break;
770 
771  elements[i] = elements[child];
772  }
773  elements[i] = tail;
774 }
775 
776 static inline cairo_status_t
779  cairo_bo_edge_t *e1,
780  cairo_bo_edge_t *e2,
781  const cairo_point_t *point)
782 {
783  cairo_bo_queue_event_t *event;
784 
785  event = _cairo_freepool_alloc (&queue->pool);
786  if (unlikely (event == NULL))
788 
789  event->type = type;
790  event->e1 = e1;
791  event->e2 = e2;
792  event->point = *point;
793 
794  return _pqueue_push (&queue->pqueue, (cairo_bo_event_t *) event);
795 }
796 
797 static void
799  cairo_bo_event_t *event)
800 {
801  _cairo_freepool_free (&queue->pool, event);
802 }
803 
804 static cairo_bo_event_t *
806 {
807  cairo_bo_event_t *event, *cmp;
808 
809  event = event_queue->pqueue.elements[PQ_FIRST_ENTRY];
810  cmp = *event_queue->start_events;
811  if (event == NULL ||
812  (cmp != NULL && cairo_bo_event_compare (cmp, event) < 0))
813  {
814  event = cmp;
815  event_queue->start_events++;
816  }
817  else
818  {
819  _pqueue_pop (&event_queue->pqueue);
820  }
821 
822  return event;
823 }
824 
828 
829 static void
831  cairo_bo_event_t **start_events,
832  int num_events)
833 {
834  event_queue->start_events = start_events;
835 
836  _cairo_freepool_init (&event_queue->pool,
838  _pqueue_init (&event_queue->pqueue);
839  event_queue->pqueue.elements[PQ_FIRST_ENTRY] = NULL;
840 }
841 
842 static cairo_status_t
845 {
847 
848  point.y = edge->edge.bottom;
850  point.y);
851  return _cairo_bo_event_queue_insert (event_queue,
853  edge, NULL,
854  &point);
855 }
856 
857 static void
859 {
860  _pqueue_fini (&event_queue->pqueue);
861  _cairo_freepool_fini (&event_queue->pool);
862 }
863 
864 static inline cairo_status_t
868 {
870 
871  if (MAX (left->edge.line.p1.x, left->edge.line.p2.x) <=
872  MIN (right->edge.line.p1.x, right->edge.line.p2.x))
873  return CAIRO_STATUS_SUCCESS;
874 
875  if (cairo_lines_equal (&left->edge.line, &right->edge.line))
876  return CAIRO_STATUS_SUCCESS;
877 
878  /* The names "left" and "right" here are correct descriptions of
879  * the order of the two edges within the active edge list. So if a
880  * slope comparison also puts left less than right, then we know
881  * that the intersection of these two segments has already
882  * occurred before the current sweep line position. */
883  if (_slope_compare (left, right) <= 0)
884  return CAIRO_STATUS_SUCCESS;
885 
887  return CAIRO_STATUS_SUCCESS;
888 
889  return _cairo_bo_event_queue_insert (event_queue,
891  left, right,
892  &intersection);
893 }
894 
895 static void
897 {
898  sweep_line->head = NULL;
899  sweep_line->stopped = NULL;
900  sweep_line->current_y = INT32_MIN;
901  sweep_line->current_edge = NULL;
902 }
903 
904 static void
907 {
908  if (sweep_line->current_edge != NULL) {
910  int cmp;
911 
913  sweep_line->current_edge,
914  edge);
915  if (cmp < 0) {
916  prev = sweep_line->current_edge;
917  next = prev->next;
918  while (next != NULL &&
920  next, edge) < 0)
921  {
922  prev = next, next = prev->next;
923  }
924 
925  prev->next = edge;
926  edge->prev = prev;
927  edge->next = next;
928  if (next != NULL)
929  next->prev = edge;
930  } else if (cmp > 0) {
931  next = sweep_line->current_edge;
932  prev = next->prev;
933  while (prev != NULL &&
935  prev, edge) > 0)
936  {
937  next = prev, prev = next->prev;
938  }
939 
940  next->prev = edge;
941  edge->next = next;
942  edge->prev = prev;
943  if (prev != NULL)
944  prev->next = edge;
945  else
946  sweep_line->head = edge;
947  } else {
948  prev = sweep_line->current_edge;
949  edge->prev = prev;
950  edge->next = prev->next;
951  if (prev->next != NULL)
952  prev->next->prev = edge;
953  prev->next = edge;
954  }
955  } else {
956  sweep_line->head = edge;
957  edge->next = NULL;
958  }
959 
960  sweep_line->current_edge = edge;
961 }
962 
963 static void
966 {
967  if (edge->prev != NULL)
968  edge->prev->next = edge->next;
969  else
970  sweep_line->head = edge->next;
971 
972  if (edge->next != NULL)
973  edge->next->prev = edge->prev;
974 
975  if (sweep_line->current_edge == edge)
976  sweep_line->current_edge = edge->prev ? edge->prev : edge->next;
977 }
978 
979 static void
983 {
984  if (left->prev != NULL)
985  left->prev->next = right;
986  else
987  sweep_line->head = right;
988 
989  if (right->next != NULL)
990  right->next->prev = left;
991 
992  left->next = right->next;
993  right->next = left;
994 
995  right->prev = left->prev;
996  left->prev = right;
997 }
998 
999 #if DEBUG_PRINT_STATE
1000 static void
1001 _cairo_bo_edge_print (cairo_bo_edge_t *edge)
1002 {
1003  printf ("(0x%x, 0x%x)-(0x%x, 0x%x)",
1004  edge->edge.line.p1.x, edge->edge.line.p1.y,
1005  edge->edge.line.p2.x, edge->edge.line.p2.y);
1006 }
1007 
1008 static void
1009 _cairo_bo_event_print (cairo_bo_event_t *event)
1010 {
1011  switch (event->type) {
1013  printf ("Start: ");
1014  break;
1016  printf ("Stop: ");
1017  break;
1019  printf ("Intersection: ");
1020  break;
1021  }
1022  printf ("(%d, %d)\t", event->point.x, event->point.y);
1023  _cairo_bo_edge_print (event->e1);
1024  if (event->type == CAIRO_BO_EVENT_TYPE_INTERSECTION) {
1025  printf (" X ");
1026  _cairo_bo_edge_print (event->e2);
1027  }
1028  printf ("\n");
1029 }
1030 
1031 static void
1032 _cairo_bo_event_queue_print (cairo_bo_event_queue_t *event_queue)
1033 {
1034  /* XXX: fixme to print the start/stop array too. */
1035  printf ("Event queue:\n");
1036 }
1037 
1038 static void
1039 _cairo_bo_sweep_line_print (cairo_bo_sweep_line_t *sweep_line)
1040 {
1043 
1044  printf ("Sweep line from edge list: ");
1045  first = TRUE;
1046  for (edge = sweep_line->head;
1047  edge;
1048  edge = edge->next)
1049  {
1050  if (!first)
1051  printf (", ");
1052  _cairo_bo_edge_print (edge);
1053  first = FALSE;
1054  }
1055  printf ("\n");
1056 }
1057 
1058 static void
1059 print_state (const char *msg,
1060  cairo_bo_event_t *event,
1061  cairo_bo_event_queue_t *event_queue,
1062  cairo_bo_sweep_line_t *sweep_line)
1063 {
1064  printf ("%s ", msg);
1065  _cairo_bo_event_print (event);
1066  _cairo_bo_event_queue_print (event_queue);
1067  _cairo_bo_sweep_line_print (sweep_line);
1068  printf ("\n");
1069 }
1070 #endif
1071 
1072 #if DEBUG_EVENTS
1073 static void CAIRO_PRINTF_FORMAT (1, 2)
1074 event_log (const char *fmt, ...)
1075 {
1076  FILE *file;
1077 
1078  if (getenv ("CAIRO_DEBUG_EVENTS") == NULL)
1079  return;
1080 
1081  file = fopen ("bo-events.txt", "a");
1082  if (file != NULL) {
1083  va_list ap;
1084 
1085  va_start (ap, fmt);
1086  vfprintf (file, fmt, ap);
1087  va_end (ap);
1088 
1089  fclose (file);
1090  }
1091 }
1092 #endif
1093 
1094 #define HAS_COLINEAR(a, b) ((cairo_bo_edge_t *)(((uintptr_t)(a))&~1) == (b))
1095 #define IS_COLINEAR(e) (((uintptr_t)(e))&1)
1096 #define MARK_COLINEAR(e, v) ((cairo_bo_edge_t *)(((uintptr_t)(e))|(v)))
1097 
1098 static inline cairo_bool_t
1100 {
1101  unsigned p;
1102 
1103  if (HAS_COLINEAR(a->colinear, b))
1104  return IS_COLINEAR(a->colinear);
1105 
1106  if (HAS_COLINEAR(b->colinear, a)) {
1107  p = IS_COLINEAR(b->colinear);
1108  a->colinear = MARK_COLINEAR(b, p);
1109  return p;
1110  }
1111 
1112  p = 0;
1113  p |= (a->edge.line.p1.x == b->edge.line.p1.x) << 0;
1114  p |= (a->edge.line.p1.y == b->edge.line.p1.y) << 1;
1115  p |= (a->edge.line.p2.x == b->edge.line.p2.x) << 3;
1116  p |= (a->edge.line.p2.y == b->edge.line.p2.y) << 4;
1117  if (p == ((1 << 0) | (1 << 1) | (1 << 3) | (1 << 4))) {
1118  a->colinear = MARK_COLINEAR(b, 1);
1119  return TRUE;
1120  }
1121 
1122  if (_slope_compare (a, b)) {
1123  a->colinear = MARK_COLINEAR(b, 0);
1124  return FALSE;
1125  }
1126 
1127  /* The choice of y is not truly arbitrary since we must guarantee that it
1128  * is greater than the start of either line.
1129  */
1130  if (p != 0) {
1131  /* colinear if either end-point are coincident */
1132  p = (((p >> 1) & p) & 5) != 0;
1133  } else if (a->edge.line.p1.y < b->edge.line.p1.y) {
1135  a->edge.line.p1.y,
1136  a->edge.line.p1.x) == 0;
1137  } else {
1139  b->edge.line.p1.y,
1140  b->edge.line.p1.x) == 0;
1141  }
1142 
1143  a->colinear = MARK_COLINEAR(b, p);
1144  return p;
1145 }
1146 
1147 /* Adds the trapezoid, if any, of the left edge to the #cairo_traps_t */
1148 static void
1150  int32_t bot,
1151  cairo_traps_t *traps)
1152 {
1153  cairo_bo_trap_t *trap = &left->deferred_trap;
1154 
1155  /* Only emit (trivial) non-degenerate trapezoids with positive height. */
1156  if (likely (trap->top < bot)) {
1157  _cairo_traps_add_trap (traps,
1158  trap->top, bot,
1159  &left->edge.line, &trap->right->edge.line);
1160 
1161 #if DEBUG_PRINT_STATE
1162  printf ("Deferred trap: left=(%x, %x)-(%x,%x) "
1163  "right=(%x,%x)-(%x,%x) top=%x, bot=%x\n",
1164  left->edge.line.p1.x, left->edge.line.p1.y,
1165  left->edge.line.p2.x, left->edge.line.p2.y,
1166  trap->right->edge.line.p1.x, trap->right->edge.line.p1.y,
1167  trap->right->edge.line.p2.x, trap->right->edge.line.p2.y,
1168  trap->top, bot);
1169 #endif
1170 #if DEBUG_EVENTS
1171  event_log ("end trap: %lu %lu %d %d\n",
1172  (long) left,
1173  (long) trap->right,
1174  trap->top,
1175  bot);
1176 #endif
1177  }
1178 
1179  trap->right = NULL;
1180 }
1181 
1182 
1183 /* Start a new trapezoid at the given top y coordinate, whose edges
1184  * are `edge' and `edge->next'. If `edge' already has a trapezoid,
1185  * then either add it to the traps in `traps', if the trapezoid's
1186  * right edge differs from `edge->next', or do nothing if the new
1187  * trapezoid would be a continuation of the existing one. */
1188 static inline void
1191  int top,
1192  cairo_traps_t *traps)
1193 {
1194  if (left->deferred_trap.right == right)
1195  return;
1196 
1197  assert (right);
1198  if (left->deferred_trap.right != NULL) {
1199  if (edges_colinear (left->deferred_trap.right, right))
1200  {
1201  /* continuation on right, so just swap edges */
1202  left->deferred_trap.right = right;
1203  return;
1204  }
1205 
1206  _cairo_bo_edge_end_trap (left, top, traps);
1207  }
1208 
1209  if (! edges_colinear (left, right)) {
1210  left->deferred_trap.top = top;
1211  left->deferred_trap.right = right;
1212 
1213 #if DEBUG_EVENTS
1214  event_log ("begin trap: %lu %lu %d\n",
1215  (long) left,
1216  (long) right,
1217  top);
1218 #endif
1219  }
1220 }
1221 
1222 static inline void
1224  int32_t top,
1225  unsigned mask,
1226  cairo_traps_t *traps)
1227 {
1229  int in_out;
1230 
1231 
1232 #if DEBUG_PRINT_STATE
1233  printf ("Processing active edges for %x\n", top);
1234 #endif
1235 
1236  in_out = 0;
1237  left = pos;
1238  while (pos != NULL) {
1239  if (pos != left && pos->deferred_trap.right) {
1240  /* XXX It shouldn't be possible to here with 2 deferred traps
1241  * on colinear edges... See bug-bo-rictoz.
1242  */
1243  if (left->deferred_trap.right == NULL &&
1244  edges_colinear (left, pos))
1245  {
1246  /* continuation on left */
1247  left->deferred_trap = pos->deferred_trap;
1248  pos->deferred_trap.right = NULL;
1249  }
1250  else
1251  {
1252  _cairo_bo_edge_end_trap (pos, top, traps);
1253  }
1254  }
1255 
1256  in_out += pos->edge.dir;
1257  if ((in_out & mask) == 0) {
1258  /* skip co-linear edges */
1259  if (pos->next == NULL || ! edges_colinear (pos, pos->next)) {
1261  left = pos->next;
1262  }
1263  }
1264 
1265  pos = pos->next;
1266  }
1267 }
1268 
1269 /* Execute a single pass of the Bentley-Ottmann algorithm on edges,
1270  * generating trapezoids according to the fill_rule and appending them
1271  * to traps. */
1272 static cairo_status_t
1274  int num_events,
1275  unsigned fill_rule,
1276  cairo_traps_t *traps,
1277  int *num_intersections)
1278 {
1280  int intersection_count = 0;
1281  cairo_bo_event_queue_t event_queue;
1282  cairo_bo_sweep_line_t sweep_line;
1283  cairo_bo_event_t *event;
1285  cairo_bo_edge_t *e1, *e2;
1286 
1287  /* convert the fill_rule into a winding mask */
1288  if (fill_rule == CAIRO_FILL_RULE_WINDING)
1289  fill_rule = (unsigned) -1;
1290  else
1291  fill_rule = 1;
1292 
1293 #if DEBUG_EVENTS
1294  {
1295  int i;
1296 
1297  for (i = 0; i < num_events; i++) {
1298  cairo_bo_start_event_t *event =
1299  ((cairo_bo_start_event_t **) start_events)[i];
1300  event_log ("edge: %lu (%d, %d) (%d, %d) (%d, %d) %d\n",
1301  (long) &events[i].edge,
1302  event->edge.edge.line.p1.x,
1303  event->edge.edge.line.p1.y,
1304  event->edge.edge.line.p2.x,
1305  event->edge.edge.line.p2.y,
1306  event->edge.top,
1307  event->edge.bottom,
1308  event->edge.edge.dir);
1309  }
1310  }
1311 #endif
1312 
1313  _cairo_bo_event_queue_init (&event_queue, start_events, num_events);
1314  _cairo_bo_sweep_line_init (&sweep_line);
1315 
1316  while ((event = _cairo_bo_event_dequeue (&event_queue))) {
1317  if (event->point.y != sweep_line.current_y) {
1318  for (e1 = sweep_line.stopped; e1; e1 = e1->next) {
1319  if (e1->deferred_trap.right != NULL) {
1321  e1->edge.bottom,
1322  traps);
1323  }
1324  }
1325  sweep_line.stopped = NULL;
1326 
1327  _active_edges_to_traps (sweep_line.head,
1328  sweep_line.current_y,
1329  fill_rule, traps);
1330 
1331  sweep_line.current_y = event->point.y;
1332  }
1333 
1334 #if DEBUG_EVENTS
1335  event_log ("event: %d (%ld, %ld) %lu, %lu\n",
1336  event->type,
1337  (long) event->point.x,
1338  (long) event->point.y,
1339  (long) event->e1,
1340  (long) event->e2);
1341 #endif
1342 
1343  switch (event->type) {
1345  e1 = &((cairo_bo_start_event_t *) event)->edge;
1346 
1347  _cairo_bo_sweep_line_insert (&sweep_line, e1);
1348 
1349  status = _cairo_bo_event_queue_insert_stop (&event_queue, e1);
1350  if (unlikely (status))
1351  goto unwind;
1352 
1353  /* check to see if this is a continuation of a stopped edge */
1354  /* XXX change to an infinitesimal lengthening rule */
1355  for (left = sweep_line.stopped; left; left = left->next) {
1356  if (e1->edge.top <= left->edge.bottom &&
1357  edges_colinear (e1, left))
1358  {
1359  e1->deferred_trap = left->deferred_trap;
1360  if (left->prev != NULL)
1361  left->prev = left->next;
1362  else
1363  sweep_line.stopped = left->next;
1364  if (left->next != NULL)
1365  left->next->prev = left->prev;
1366  break;
1367  }
1368  }
1369 
1370  left = e1->prev;
1371  right = e1->next;
1372 
1373  if (left != NULL) {
1375  if (unlikely (status))
1376  goto unwind;
1377  }
1378 
1379  if (right != NULL) {
1381  if (unlikely (status))
1382  goto unwind;
1383  }
1384 
1385  break;
1386 
1388  e1 = ((cairo_bo_queue_event_t *) event)->e1;
1389  _cairo_bo_event_queue_delete (&event_queue, event);
1390 
1391  left = e1->prev;
1392  right = e1->next;
1393 
1394  _cairo_bo_sweep_line_delete (&sweep_line, e1);
1395 
1396  /* first, check to see if we have a continuation via a fresh edge */
1397  if (e1->deferred_trap.right != NULL) {
1398  e1->next = sweep_line.stopped;
1399  if (sweep_line.stopped != NULL)
1400  sweep_line.stopped->prev = e1;
1401  sweep_line.stopped = e1;
1402  e1->prev = NULL;
1403  }
1404 
1405  if (left != NULL && right != NULL) {
1407  if (unlikely (status))
1408  goto unwind;
1409  }
1410 
1411  break;
1412 
1414  e1 = ((cairo_bo_queue_event_t *) event)->e1;
1415  e2 = ((cairo_bo_queue_event_t *) event)->e2;
1416  _cairo_bo_event_queue_delete (&event_queue, event);
1417 
1418  /* skip this intersection if its edges are not adjacent */
1419  if (e2 != e1->next)
1420  break;
1421 
1422  intersection_count++;
1423 
1424  left = e1->prev;
1425  right = e2->next;
1426 
1427  _cairo_bo_sweep_line_swap (&sweep_line, e1, e2);
1428 
1429  /* after the swap e2 is left of e1 */
1430 
1431  if (left != NULL) {
1433  if (unlikely (status))
1434  goto unwind;
1435  }
1436 
1437  if (right != NULL) {
1439  if (unlikely (status))
1440  goto unwind;
1441  }
1442 
1443  break;
1444  }
1445  }
1446 
1447  *num_intersections = intersection_count;
1448  for (e1 = sweep_line.stopped; e1; e1 = e1->next) {
1449  if (e1->deferred_trap.right != NULL) {
1450  _cairo_bo_edge_end_trap (e1, e1->edge.bottom, traps);
1451  }
1452  }
1453  status = traps->status;
1454  unwind:
1455  _cairo_bo_event_queue_fini (&event_queue);
1456 
1457 #if DEBUG_EVENTS
1458  event_log ("\n");
1459 #endif
1460 
1461  return status;
1462 }
1463 
1466  const cairo_polygon_t *polygon,
1467  cairo_fill_rule_t fill_rule)
1468 {
1469  int intersections;
1471  cairo_bo_start_event_t *events;
1472  cairo_bo_event_t *stack_event_ptrs[ARRAY_LENGTH (stack_events) + 1];
1473  cairo_bo_event_t **event_ptrs;
1474  cairo_bo_start_event_t *stack_event_y[64];
1475  cairo_bo_start_event_t **event_y = NULL;
1476  int i, num_events, y, ymin, ymax;
1478 
1479  num_events = polygon->num_edges;
1480  if (unlikely (0 == num_events))
1481  return CAIRO_STATUS_SUCCESS;
1482 
1483  if (polygon->num_limits) {
1484  ymin = _cairo_fixed_integer_floor (polygon->limit.p1.y);
1485  ymax = _cairo_fixed_integer_ceil (polygon->limit.p2.y) - ymin;
1486 
1487  if (ymax > 64) {
1488  event_y = _cairo_malloc_ab(sizeof (cairo_bo_event_t*), ymax);
1489  if (unlikely (event_y == NULL))
1491  } else {
1492  event_y = stack_event_y;
1493  }
1494  memset (event_y, 0, ymax * sizeof(cairo_bo_event_t *));
1495  }
1496 
1497  events = stack_events;
1498  event_ptrs = stack_event_ptrs;
1499  if (num_events > ARRAY_LENGTH (stack_events)) {
1500  events = _cairo_malloc_ab_plus_c (num_events,
1501  sizeof (cairo_bo_start_event_t) +
1502  sizeof (cairo_bo_event_t *),
1503  sizeof (cairo_bo_event_t *));
1504  if (unlikely (events == NULL)) {
1505  if (event_y != stack_event_y)
1506  free (event_y);
1508  }
1509 
1510  event_ptrs = (cairo_bo_event_t **) (events + num_events);
1511  }
1512 
1513  for (i = 0; i < num_events; i++) {
1514  events[i].type = CAIRO_BO_EVENT_TYPE_START;
1515  events[i].point.y = polygon->edges[i].top;
1516  events[i].point.x =
1518  events[i].point.y);
1519 
1520  events[i].edge.edge = polygon->edges[i];
1521  events[i].edge.deferred_trap.right = NULL;
1522  events[i].edge.prev = NULL;
1523  events[i].edge.next = NULL;
1524  events[i].edge.colinear = NULL;
1525 
1526  if (event_y) {
1527  y = _cairo_fixed_integer_floor (events[i].point.y) - ymin;
1528  events[i].edge.next = (cairo_bo_edge_t *) event_y[y];
1529  event_y[y] = (cairo_bo_start_event_t *) &events[i];
1530  } else
1531  event_ptrs[i] = (cairo_bo_event_t *) &events[i];
1532  }
1533 
1534  if (event_y) {
1535  for (y = i = 0; y < ymax && i < num_events; y++) {
1537  int j = i;
1538  for (e = event_y[y]; e; e = (cairo_bo_start_event_t *)e->edge.next)
1539  event_ptrs[i++] = (cairo_bo_event_t *) e;
1540  if (i > j + 1)
1541  _cairo_bo_event_queue_sort (event_ptrs+j, i-j);
1542  }
1543  if (event_y != stack_event_y)
1544  free (event_y);
1545  } else
1546  _cairo_bo_event_queue_sort (event_ptrs, i);
1547  event_ptrs[i] = NULL;
1548 
1549 #if DEBUG_TRAPS
1550  dump_edges (events, num_events, "bo-polygon-edges.txt");
1551 #endif
1552 
1553  /* XXX: This would be the convenient place to throw in multiple
1554  * passes of the Bentley-Ottmann algorithm. It would merely
1555  * require storing the results of each pass into a temporary
1556  * cairo_traps_t. */
1557  status = _cairo_bentley_ottmann_tessellate_bo_edges (event_ptrs, num_events,
1558  fill_rule, traps,
1559  &intersections);
1560 #if DEBUG_TRAPS
1561  dump_traps (traps, "bo-polygon-out.txt");
1562 #endif
1563 
1564  if (events != stack_events)
1565  free (events);
1566 
1567  return status;
1568 }
1569 
1572  cairo_fill_rule_t fill_rule)
1573 {
1576  int i;
1577 
1578  if (unlikely (0 == traps->num_traps))
1579  return CAIRO_STATUS_SUCCESS;
1580 
1581 #if DEBUG_TRAPS
1582  dump_traps (traps, "bo-traps-in.txt");
1583 #endif
1584 
1585  _cairo_polygon_init (&polygon, traps->limits, traps->num_limits);
1586 
1587  for (i = 0; i < traps->num_traps; i++) {
1589  &traps->traps[i].left,
1590  traps->traps[i].top,
1591  traps->traps[i].bottom,
1592  1);
1593  if (unlikely (status))
1594  goto CLEANUP;
1595 
1597  &traps->traps[i].right,
1598  traps->traps[i].top,
1599  traps->traps[i].bottom,
1600  -1);
1601  if (unlikely (status))
1602  goto CLEANUP;
1603  }
1604 
1605  _cairo_traps_clear (traps);
1607  &polygon,
1608  fill_rule);
1609 
1610 #if DEBUG_TRAPS
1611  dump_traps (traps, "bo-traps-out.txt");
1612 #endif
1613 
1614  CLEANUP:
1616 
1617  return status;
1618 }
1619 
1620 #if 0
1621 static cairo_bool_t
1622 edges_have_an_intersection_quadratic (cairo_bo_edge_t *edges,
1623  int num_edges)
1624 
1625 {
1626  int i, j;
1627  cairo_bo_edge_t *a, *b;
1629 
1630  /* We must not be given any upside-down edges. */
1631  for (i = 0; i < num_edges; i++) {
1632  assert (_cairo_bo_point32_compare (&edges[i].top, &edges[i].bottom) < 0);
1633  edges[i].line.p1.x <<= CAIRO_BO_GUARD_BITS;
1634  edges[i].line.p1.y <<= CAIRO_BO_GUARD_BITS;
1635  edges[i].line.p2.x <<= CAIRO_BO_GUARD_BITS;
1636  edges[i].line.p2.y <<= CAIRO_BO_GUARD_BITS;
1637  }
1638 
1639  for (i = 0; i < num_edges; i++) {
1640  for (j = 0; j < num_edges; j++) {
1641  if (i == j)
1642  continue;
1643 
1644  a = &edges[i];
1645  b = &edges[j];
1646 
1648  continue;
1649 
1650  printf ("Found intersection (%d,%d) between (%d,%d)-(%d,%d) and (%d,%d)-(%d,%d)\n",
1651  intersection.x,
1652  intersection.y,
1653  a->line.p1.x, a->line.p1.y,
1654  a->line.p2.x, a->line.p2.y,
1655  b->line.p1.x, b->line.p1.y,
1656  b->line.p2.x, b->line.p2.y);
1657 
1658  return TRUE;
1659  }
1660  }
1661  return FALSE;
1662 }
1663 
1664 #define TEST_MAX_EDGES 10
1665 
1666 typedef struct test {
1667  const char *name;
1668  const char *description;
1669  int num_edges;
1670  cairo_bo_edge_t edges[TEST_MAX_EDGES];
1671 } test_t;
1672 
1673 static test_t
1674 tests[] = {
1675  {
1676  "3 near misses",
1677  "3 edges all intersecting very close to each other",
1678  3,
1679  {
1680  { { 4, 2}, {0, 0}, { 9, 9}, NULL, NULL },
1681  { { 7, 2}, {0, 0}, { 2, 3}, NULL, NULL },
1682  { { 5, 2}, {0, 0}, { 1, 7}, NULL, NULL }
1683  }
1684  },
1685  {
1686  "inconsistent data",
1687  "Derived from random testing---was leading to skip list and edge list disagreeing.",
1688  2,
1689  {
1690  { { 2, 3}, {0, 0}, { 8, 9}, NULL, NULL },
1691  { { 2, 3}, {0, 0}, { 6, 7}, NULL, NULL }
1692  }
1693  },
1694  {
1695  "failed sort",
1696  "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?",
1697  3,
1698  {
1699  { { 6, 2}, {0, 0}, { 6, 5}, NULL, NULL },
1700  { { 3, 5}, {0, 0}, { 5, 6}, NULL, NULL },
1701  { { 9, 2}, {0, 0}, { 5, 6}, NULL, NULL },
1702  }
1703  },
1704  {
1705  "minimal-intersection",
1706  "Intersection of a two from among the smallest possible edges.",
1707  2,
1708  {
1709  { { 0, 0}, {0, 0}, { 1, 1}, NULL, NULL },
1710  { { 1, 0}, {0, 0}, { 0, 1}, NULL, NULL }
1711  }
1712  },
1713  {
1714  "simple",
1715  "A simple intersection of two edges at an integer (2,2).",
1716  2,
1717  {
1718  { { 1, 1}, {0, 0}, { 3, 3}, NULL, NULL },
1719  { { 2, 1}, {0, 0}, { 2, 3}, NULL, NULL }
1720  }
1721  },
1722  {
1723  "bend-to-horizontal",
1724  "With intersection truncation one edge bends to horizontal",
1725  2,
1726  {
1727  { { 9, 1}, {0, 0}, {3, 7}, NULL, NULL },
1728  { { 3, 5}, {0, 0}, {9, 9}, NULL, NULL }
1729  }
1730  }
1731 };
1732 
1733 /*
1734  {
1735  "endpoint",
1736  "An intersection that occurs at the endpoint of a segment.",
1737  {
1738  { { 4, 6}, { 5, 6}, NULL, { { NULL }} },
1739  { { 4, 5}, { 5, 7}, NULL, { { NULL }} },
1740  { { 0, 0}, { 0, 0}, NULL, { { NULL }} },
1741  }
1742  }
1743  {
1744  name = "overlapping",
1745  desc = "Parallel segments that share an endpoint, with different slopes.",
1746  edges = {
1747  { top = { x = 2, y = 0}, bottom = { x = 1, y = 1}},
1748  { top = { x = 2, y = 0}, bottom = { x = 0, y = 2}},
1749  { top = { x = 0, y = 3}, bottom = { x = 1, y = 3}},
1750  { top = { x = 0, y = 3}, bottom = { x = 2, y = 3}},
1751  { top = { x = 0, y = 4}, bottom = { x = 0, y = 6}},
1752  { top = { x = 0, y = 5}, bottom = { x = 0, y = 6}}
1753  }
1754  },
1755  {
1756  name = "hobby_stage_3",
1757  desc = "A particularly tricky part of the 3rd stage of the 'hobby' test below.",
1758  edges = {
1759  { top = { x = -1, y = -2}, bottom = { x = 4, y = 2}},
1760  { top = { x = 5, y = 3}, bottom = { x = 9, y = 5}},
1761  { top = { x = 5, y = 3}, bottom = { x = 6, y = 3}},
1762  }
1763  },
1764  {
1765  name = "hobby",
1766  desc = "Example from John Hobby's paper. Requires 3 passes of the iterative algorithm.",
1767  edges = {
1768  { top = { x = 0, y = 0}, bottom = { x = 9, y = 5}},
1769  { top = { x = 0, y = 0}, bottom = { x = 13, y = 6}},
1770  { top = { x = -1, y = -2}, bottom = { x = 9, y = 5}}
1771  }
1772  },
1773  {
1774  name = "slope",
1775  desc = "Edges with same start/stop points but different slopes",
1776  edges = {
1777  { top = { x = 4, y = 1}, bottom = { x = 6, y = 3}},
1778  { top = { x = 4, y = 1}, bottom = { x = 2, y = 3}},
1779  { top = { x = 2, y = 4}, bottom = { x = 4, y = 6}},
1780  { top = { x = 6, y = 4}, bottom = { x = 4, y = 6}}
1781  }
1782  },
1783  {
1784  name = "horizontal",
1785  desc = "Test of a horizontal edge",
1786  edges = {
1787  { top = { x = 1, y = 1}, bottom = { x = 6, y = 6}},
1788  { top = { x = 2, y = 3}, bottom = { x = 5, y = 3}}
1789  }
1790  },
1791  {
1792  name = "vertical",
1793  desc = "Test of a vertical edge",
1794  edges = {
1795  { top = { x = 5, y = 1}, bottom = { x = 5, y = 7}},
1796  { top = { x = 2, y = 4}, bottom = { x = 8, y = 5}}
1797  }
1798  },
1799  {
1800  name = "congruent",
1801  desc = "Two overlapping edges with the same slope",
1802  edges = {
1803  { top = { x = 5, y = 1}, bottom = { x = 5, y = 7}},
1804  { top = { x = 5, y = 2}, bottom = { x = 5, y = 6}},
1805  { top = { x = 2, y = 4}, bottom = { x = 8, y = 5}}
1806  }
1807  },
1808  {
1809  name = "multi",
1810  desc = "Several segments with a common intersection point",
1811  edges = {
1812  { top = { x = 1, y = 2}, bottom = { x = 5, y = 4} },
1813  { top = { x = 1, y = 1}, bottom = { x = 5, y = 5} },
1814  { top = { x = 2, y = 1}, bottom = { x = 4, y = 5} },
1815  { top = { x = 4, y = 1}, bottom = { x = 2, y = 5} },
1816  { top = { x = 5, y = 1}, bottom = { x = 1, y = 5} },
1817  { top = { x = 5, y = 2}, bottom = { x = 1, y = 4} }
1818  }
1819  }
1820 };
1821 */
1822 
1823 static int
1824 run_test (const char *test_name,
1825  cairo_bo_edge_t *test_edges,
1826  int num_edges)
1827 {
1828  int i, intersections, passes;
1829  cairo_bo_edge_t *edges;
1830  cairo_array_t intersected_edges;
1831 
1832  printf ("Testing: %s\n", test_name);
1833 
1834  _cairo_array_init (&intersected_edges, sizeof (cairo_bo_edge_t));
1835 
1836  intersections = _cairo_bentley_ottmann_intersect_edges (test_edges, num_edges, &intersected_edges);
1837  if (intersections)
1838  printf ("Pass 1 found %d intersections:\n", intersections);
1839 
1840 
1841  /* XXX: Multi-pass Bentley-Ottmmann. Preferable would be to add a
1842  * pass of Hobby's tolerance-square algorithm instead. */
1843  passes = 1;
1844  while (intersections) {
1845  int num_edges = _cairo_array_num_elements (&intersected_edges);
1846  passes++;
1847  edges = _cairo_malloc_ab (num_edges, sizeof (cairo_bo_edge_t));
1848  assert (edges != NULL);
1849  memcpy (edges, _cairo_array_index (&intersected_edges, 0), num_edges * sizeof (cairo_bo_edge_t));
1850  _cairo_array_fini (&intersected_edges);
1851  _cairo_array_init (&intersected_edges, sizeof (cairo_bo_edge_t));
1852  intersections = _cairo_bentley_ottmann_intersect_edges (edges, num_edges, &intersected_edges);
1853  free (edges);
1854 
1855  if (intersections){
1856  printf ("Pass %d found %d remaining intersections:\n", passes, intersections);
1857  } else {
1858  if (passes > 3)
1859  for (i = 0; i < passes; i++)
1860  printf ("*");
1861  printf ("No remainining intersections found after pass %d\n", passes);
1862  }
1863  }
1864 
1865  if (edges_have_an_intersection_quadratic (_cairo_array_index (&intersected_edges, 0),
1866  _cairo_array_num_elements (&intersected_edges)))
1867  printf ("*** FAIL ***\n");
1868  else
1869  printf ("PASS\n");
1870 
1871  _cairo_array_fini (&intersected_edges);
1872 
1873  return 0;
1874 }
1875 
1876 #define MAX_RANDOM 300
1877 
1878 int
1879 main (void)
1880 {
1881  char random_name[] = "random-XX";
1882  cairo_bo_edge_t random_edges[MAX_RANDOM], *edge;
1883  unsigned int i, num_random;
1884  test_t *test;
1885 
1886  for (i = 0; i < ARRAY_LENGTH (tests); i++) {
1887  test = &tests[i];
1888  run_test (test->name, test->edges, test->num_edges);
1889  }
1890 
1891  for (num_random = 0; num_random < MAX_RANDOM; num_random++) {
1892  srand (0);
1893  for (i = 0; i < num_random; i++) {
1894  do {
1895  edge = &random_edges[i];
1896  edge->line.p1.x = (int32_t) (10.0 * (rand() / (RAND_MAX + 1.0)));
1897  edge->line.p1.y = (int32_t) (10.0 * (rand() / (RAND_MAX + 1.0)));
1898  edge->line.p2.x = (int32_t) (10.0 * (rand() / (RAND_MAX + 1.0)));
1899  edge->line.p2.y = (int32_t) (10.0 * (rand() / (RAND_MAX + 1.0)));
1900  if (edge->line.p1.y > edge->line.p2.y) {
1901  int32_t tmp = edge->line.p1.y;
1902  edge->line.p1.y = edge->line.p2.y;
1903  edge->line.p2.y = tmp;
1904  }
1905  } while (edge->line.p1.y == edge->line.p2.y);
1906  }
1907 
1908  sprintf (random_name, "random-%02d", num_random);
1909 
1910  run_test (random_name, random_edges, num_random);
1911  }
1912 
1913  return 0;
1914 }
1915 #endif
#define type(a)
Definition: aptex-macros.h:171
#define name
#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
void _cairo_array_fini(cairo_array_t *array)
Definition: cairo-array.c:75
unsigned int _cairo_array_num_elements(const cairo_array_t *array)
Definition: cairo-array.c:338
void * _cairo_array_index(cairo_array_t *array, unsigned int index)
Definition: cairo-array.c:166
void _cairo_array_init(cairo_array_t *array, unsigned int element_size)
Definition: cairo-array.c:58
#define dump_traps(traps, filename)
cairo_point_t cairo_bo_point32_t
static void _pqueue_init(pqueue_t *pq)
struct _cairo_bo_intersect_point cairo_bo_intersect_point_t
static cairo_int64_t det32_64(int32_t a, int32_t b, int32_t c, int32_t d)
cairo_status_t _cairo_bentley_ottmann_tessellate_polygon(cairo_traps_t *traps, const cairo_polygon_t *polygon, cairo_fill_rule_t fill_rule)
#define IS_COLINEAR(e)
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 _cairo_bo_event_queue_insert_stop(cairo_bo_event_queue_t *event_queue, cairo_bo_edge_t *edge)
static void _pqueue_pop(pqueue_t *pq)
#define MARK_COLINEAR(e, v)
static void _cairo_bo_sweep_line_swap(cairo_bo_sweep_line_t *sweep_line, cairo_bo_edge_t *left, cairo_bo_edge_t *right)
struct _pqueue pqueue_t
struct _cairo_bo_queue_event cairo_bo_queue_event_t
static void _cairo_bo_event_queue_delete(cairo_bo_event_queue_t *queue, cairo_bo_event_t *event)
struct _cairo_bo_start_event cairo_bo_start_event_t
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)
struct _cairo_bo_event cairo_bo_event_t
static void _cairo_bo_sweep_line_init(cairo_bo_sweep_line_t *sweep_line)
static int _cairo_bo_point32_compare(cairo_bo_point32_t const *a, cairo_bo_point32_t const *b)
struct _cairo_bo_sweep_line cairo_bo_sweep_line_t
struct _cairo_bo_intersect_ordinate cairo_bo_intersect_ordinate_t
static cairo_bool_t _cairo_bo_edge_intersect(cairo_bo_edge_t *a, cairo_bo_edge_t *b, cairo_bo_point32_t *intersection)
cairo_bo_event_type_t
@ CAIRO_BO_EVENT_TYPE_START
@ CAIRO_BO_EVENT_TYPE_STOP
@ CAIRO_BO_EVENT_TYPE_INTERSECTION
static cairo_status_t _cairo_bentley_ottmann_tessellate_bo_edges(cairo_bo_event_t **start_events, int num_events, unsigned fill_rule, cairo_traps_t *traps, int *num_intersections)
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 int _cairo_bo_sweep_line_compare_edges(const cairo_bo_sweep_line_t *sweep_line, const cairo_bo_edge_t *a, const cairo_bo_edge_t *b)
static void _cairo_bo_sweep_line_insert(cairo_bo_sweep_line_t *sweep_line, cairo_bo_edge_t *edge)
static void _cairo_bo_event_queue_sort(cairo_bo_event_t **base, unsigned int nmemb)
#define HAS_COLINEAR(a, b)
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_point_t *point)
static void _cairo_bo_edge_end_trap(cairo_bo_edge_t *left, int32_t bot, cairo_traps_t *traps)
static void _active_edges_to_traps(cairo_bo_edge_t *pos, int32_t top, unsigned mask, cairo_traps_t *traps)
struct _cairo_bo_event_queue cairo_bo_event_queue_t
static cairo_status_t _cairo_bo_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)
#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 _slope_compare(const cairo_bo_edge_t *a, const cairo_bo_edge_t *b)
static void _pqueue_fini(pqueue_t *pq)
static void _cairo_bo_edge_start_or_continue_trap(cairo_bo_edge_t *left, cairo_bo_edge_t *right, int top, cairo_traps_t *traps)
static void _cairo_bo_event_queue_fini(cairo_bo_event_queue_t *event_queue)
cairo_status_t _cairo_bentley_ottmann_tessellate_traps(cairo_traps_t *traps, cairo_fill_rule_t fill_rule)
static cairo_bool_t edges_colinear(cairo_bo_edge_t *a, const cairo_bo_edge_t *b)
static int _cairo_bo_intersect_ordinate_32_compare(cairo_bo_intersect_ordinate_t a, int32_t b)
static cairo_bo_event_t * _cairo_bo_event_dequeue(cairo_bo_event_queue_t *event_queue)
#define CAIRO_COMBSORT_DECLARE(NAME, TYPE, CMP)
#define CAIRO_PRINTF_FORMAT(fmt_index, va_index)
#define CAIRO_STACK_ARRAY_LENGTH(T)
cairo_status_t _cairo_error(cairo_status_t status)
Definition: cairo-error.c:65
static int _cairo_fixed_integer_floor(cairo_fixed_t f)
static cairo_fixed_t _cairo_fixed_mul_div_floor(cairo_fixed_t a, cairo_fixed_t b, cairo_fixed_t c)
static int _cairo_fixed_integer_ceil(cairo_fixed_t f)
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)
static int cairo_lines_equal(const cairo_line_t *a, const cairo_line_t *b)
int cairo_lines_compare_at_y(const cairo_line_t *a, const cairo_line_t *b, int y)
Definition: cairo-line.c:281
#define _cairo_realloc_ab(ptr, a, size)
#define _cairo_malloc_ab(a, size)
#define _cairo_malloc_ab_plus_c(a, size, c)
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)
void _cairo_traps_add_trap(cairo_traps_t *traps, cairo_fixed_t top, cairo_fixed_t bottom, const cairo_line_t *left, const cairo_line_t *right)
Definition: cairo-traps.c:151
void _cairo_traps_extents(const cairo_traps_t *traps, cairo_box_t *extents)
Definition: cairo-traps.c:742
void _cairo_traps_clear(cairo_traps_t *traps)
Definition: cairo-traps.c:98
#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_to_int32(a)
#define _cairo_int64_mul(a, b)
int _cairo_int64_cmp(cairo_int64_t a, cairo_int64_t b)
#define _cairo_int64_negative(a)
#define _cairo_int64_ge(a, b)
cairo_int64_t _cairo_int32_to_int64(int32_t i)
#define _cairo_int64x32_128_mul(a, 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)
#define _cairo_int64_add(a, 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
#define n
Definition: t4ht.c:1290
#define b
Definition: jpegint.h:372
#define ap
@ FALSE
Definition: dd.h:101
@ TRUE
Definition: dd.h:102
#define free(a)
Definition: decNumber.cpp:310
static const char description[]
Definition: drvwmf.cpp:127
#define fopen
Definition: xxstdio.h:21
int printf()
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 MIN(a, b)
Definition: jpegint.h:269
#define MAX(a, b)
Definition: jpegint.h:267
#define NULL
Definition: ftobjs.h:61
small capitals from c petite p
Definition: afcover.h:72
small capitals from c petite p scientific i
Definition: afcover.h:80
sizeof(AF_ModuleRec)
#define const
Definition: ftzconf.h:91
kerning y
Definition: ttdriver.c:212
@ right
Definition: annotate.c:15
int int double double double char double char * top
Definition: gdfx.h:19
int int double double double char double char char * bottom
Definition: gdfx.h:20
#define INT32_MIN
Definition: stdint.h:136
signed int int32_t
Definition: stdint.h:77
char * getenv()
#define srand(x)
Definition: mem.h:48
#define rand()
Definition: mem.h:49
#define fclose
Definition: debug.h:100
#define fprintf
Definition: mendex.h:64
#define test
Definition: tie.c:129
#define sprintf
Definition: snprintf.c:44
const int * pos
Definition: combiners.h:905
float x
Definition: cordic.py:15
char * filename[256]
Definition: pbmtopk.c:46
static int32_t first
Definition: ppagelist.c:29
bstring c int memset(void *s, int c, int length)
#define status
#define mask(n)
Definition: lbitlib.c:93
#define parent(a, t)
Definition: interp.c:105
test
Definition: parser.c:257
static void(* trap)(void)
Definition: memory.c:38
lft_cell * left
Definition: routines.h:73
ShellFileEnvironment e
Definition: sh6.c:388
#define int32_t
Definition: stdint.in.h:167
cairo_bo_edge_t * colinear
cairo_bo_event_t ** start_events
enum _cairo_bo_intersect_ordinate::@435 exactness
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_status_t status
cairo_trapezoid_t * traps
const cairo_box_t * limits
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: texview.c:48
Definition: mpost.c:238
double y
Definition: mpost.c:239
double x
Definition: mpost.c:239
struct edge * edges
#define FILE
Definition: t1stdio.h:34
int j
Definition: t4ht.c:1589
char * file
Definition: t4ht.c:931
char fmt[256]
Definition: tex4ht.c:3925
@ R
Definition: ubidiimp.h:46
@ L
Definition: ubidiimp.h:45
#define va_start(pvar)
Definition: varargs.h:30
#define va_end(pvar)
Definition: varargs.h:38
char * va_list
Definition: varargs.h:22
#define main
Definition: xmain.c:31