2
* Copyright © 2004 Carl Worth
3
* Copyright © 2006 Red Hat, Inc.
5
* This library is free software; you can redistribute it and/or
6
* modify it either under the terms of the GNU Lesser General Public
7
* License version 2.1 as published by the Free Software Foundation
8
* (the "LGPL") or, at your option, under the terms of the Mozilla
9
* Public License Version 1.1 (the "MPL"). If you do not alter this
10
* notice, a recipient may use your version of this file under either
11
* the MPL or the LGPL.
13
* You should have received a copy of the LGPL along with this library
14
* in the file COPYING-LGPL-2.1; if not, write to the Free Software
15
* Foundation, Inc., 59 Temple Place, Suite 330, Boston, MA 02111-1307 USA
16
* You should have received a copy of the MPL along with this library
17
* in the file COPYING-MPL-1.1
19
* The contents of this file are subject to the Mozilla Public License
20
* Version 1.1 (the "License"); you may not use this file except in
21
* compliance with the License. You may obtain a copy of the License at
22
* http://www.mozilla.org/MPL/
24
* This software is distributed on an "AS IS" basis, WITHOUT WARRANTY
25
* OF ANY KIND, either express or implied. See the LGPL or the MPL for
26
* the specific language governing rights and limitations.
28
* The Original Code is the cairo graphics library.
30
* The Initial Developer of the Original Code is Carl Worth
33
* Carl D. Worth <cworth@cworth.org>
36
/* Provide definitions for standalone compilation */
39
#include "cairo-skiplist-private.h"
40
#include "cairo-freelist-private.h"
42
typedef cairo_point_t cairo_bo_point32_t;
44
typedef struct _cairo_bo_point128 {
47
} cairo_bo_point128_t;
49
typedef struct _cairo_bo_intersect_ordinate {
51
enum { EXACT, INEXACT } exactness;
52
} cairo_bo_intersect_ordinate_t;
54
typedef struct _cairo_bo_intersect_point {
55
cairo_bo_intersect_ordinate_t x;
56
cairo_bo_intersect_ordinate_t y;
57
} cairo_bo_intersect_point_t;
59
typedef struct _cairo_bo_edge cairo_bo_edge_t;
60
typedef struct _sweep_line_elt sweep_line_elt_t;
61
typedef struct _cairo_bo_trap cairo_bo_trap_t;
62
typedef struct _cairo_bo_traps cairo_bo_traps_t;
64
/* A deferred trapezoid of an edge. */
65
struct _cairo_bo_trap {
66
cairo_bo_edge_t *right;
70
struct _cairo_bo_traps {
72
cairo_freelist_t freelist;
74
/* These form the closed bounding box of the original input
82
struct _cairo_bo_edge {
83
cairo_bo_point32_t top;
84
cairo_bo_point32_t middle;
85
cairo_bo_point32_t bottom;
86
cairo_bool_t reversed;
87
cairo_bo_edge_t *prev;
88
cairo_bo_edge_t *next;
89
cairo_bo_trap_t *deferred_trap;
90
sweep_line_elt_t *sweep_line_elt;
93
struct _sweep_line_elt {
94
cairo_bo_edge_t *edge;
98
#define SKIP_ELT_TO_EDGE_ELT(elt) SKIP_LIST_ELT_TO_DATA (sweep_line_elt_t, (elt))
99
#define SKIP_ELT_TO_EDGE(elt) (SKIP_ELT_TO_EDGE_ELT (elt)->edge)
102
CAIRO_BO_STATUS_INTERSECTION,
103
CAIRO_BO_STATUS_PARALLEL,
104
CAIRO_BO_STATUS_NO_INTERSECTION
108
CAIRO_BO_EVENT_TYPE_START,
109
CAIRO_BO_EVENT_TYPE_STOP,
110
CAIRO_BO_EVENT_TYPE_INTERSECTION
111
} cairo_bo_event_type_t;
113
typedef struct _cairo_bo_event {
114
cairo_bo_event_type_t type;
117
cairo_bo_point32_t point;
121
#define SKIP_ELT_TO_EVENT(elt) SKIP_LIST_ELT_TO_DATA (cairo_bo_event_t, (elt))
123
typedef struct _cairo_bo_event_queue {
124
cairo_skip_list_t intersection_queue;
126
cairo_bo_event_t *startstop_events;
127
cairo_bo_event_t **sorted_startstop_event_ptrs;
128
unsigned next_startstop_event_index;
129
unsigned num_startstop_events;
130
} cairo_bo_event_queue_t;
132
/* This structure extends cairo_skip_list_t, which must come first. */
133
typedef struct _cairo_bo_sweep_line {
134
cairo_skip_list_t active_edges;
135
cairo_bo_edge_t *head;
136
cairo_bo_edge_t *tail;
138
} cairo_bo_sweep_line_t;
141
_cairo_bo_point32_compare (cairo_bo_point32_t const *a,
142
cairo_bo_point32_t const *b)
144
int cmp = a->y - b->y;
149
/* Compare the slope of a to the slope of b, returning 1, 0, -1 if the
150
* slope a is respectively greater than, equal to, or less than the
153
* For each edge, consider the direction vector formed from:
159
* (dx, dy) = (bottom.x - top.x, bottom.y - top.y)
161
* We then define the slope of each edge as dx/dy, (which is the
162
* inverse of the slope typically used in math instruction). We never
163
* compute a slope directly as the value approaches infinity, but we
164
* can derive a slope comparison without division as follows, (where
165
* the ? represents our compare operator).
167
* 1. slope(a) ? slope(b)
168
* 2. adx/ady ? bdx/bdy
169
* 3. (adx * bdy) ? (bdx * ady)
171
* Note that from step 2 to step 3 there is no change needed in the
172
* sign of the result since both ady and bdy are guaranteed to be
173
* greater than or equal to 0.
175
* When using this slope comparison to sort edges, some care is needed
176
* when interpreting the results. Since the slope compare operates on
177
* distance vectors from top to bottom it gives a correct left to
178
* right sort for edges that have a common top point, (such as two
179
* edges with start events at the same location). On the other hand,
180
* the sense of the result will be exactly reversed for two edges that
181
* have a common stop point.
184
_slope_compare (cairo_bo_edge_t *a,
187
/* XXX: We're assuming here that dx and dy will still fit in 32
188
* bits. That's not true in general as there could be overflow. We
189
* should prevent that before the tessellation algorithm
192
int32_t adx = a->bottom.x - a->top.x;
193
int32_t bdx = b->bottom.x - b->top.x;
195
/* Since the dy's are all positive by construction we can fast
196
* path the case where the two edges point in different directions
197
* with respect to x. */
198
if ((adx ^ bdx) < 0) {
199
return adx < 0 ? -1 : +1;
202
int32_t ady = a->bottom.y - a->top.y;
203
int32_t bdy = b->bottom.y - b->top.y;
204
int64_t adx_bdy = _cairo_int32x32_64_mul (adx, bdy);
205
int64_t bdx_ady = _cairo_int32x32_64_mul (bdx, ady);
207
/* if (adx * bdy > bdx * ady) */
208
if (_cairo_int64_gt (adx_bdy, bdx_ady))
211
/* if (adx * bdy < bdx * ady) */
212
if (_cairo_int64_lt (adx_bdy, bdx_ady))
218
static cairo_quorem64_t
219
edge_x_for_y (cairo_bo_edge_t *edge,
222
/* XXX: We're assuming here that dx and dy will still fit in 32
223
* bits. That's not true in general as there could be overflow. We
224
* should prevent that before the tessellation algorithm
227
int32_t dx = edge->bottom.x - edge->top.x;
228
int32_t dy = edge->bottom.y - edge->top.y;
230
cairo_quorem64_t quorem;
232
if (edge->middle.y == y) {
233
quorem.quo = edge->middle.x;
237
if (edge->bottom.y == y) {
238
quorem.quo = edge->bottom.x;
243
quorem.quo = _cairo_int32_to_int64 (edge->top.x);
248
/* edge->top.x + (y - edge->top.y) * dx / dy */
249
numerator = _cairo_int32x32_64_mul ((y - edge->top.y), dx);
250
quorem = _cairo_int64_divrem (numerator, dy);
251
quorem.quo += edge->top.x;
257
_cairo_bo_sweep_line_compare_edges (cairo_bo_sweep_line_t *sweep_line,
268
/* don't bother solving for abscissa if the edges' bounding boxes
269
* can be used to order them. */
273
if (a->middle.x < a->bottom.x) {
280
if (b->middle.x < b->bottom.x) {
287
if (amax < bmin) return -1;
288
if (amin > bmax) return +1;
291
ax = edge_x_for_y (a, sweep_line->current_y);
292
bx = edge_x_for_y (b, sweep_line->current_y);
295
else if (ax.quo < bx.quo)
298
/* Quotients are identical, test remainder. */
301
else if (ax.rem < bx.rem)
304
/* The two edges intersect exactly at y, so fall back on slope
305
* comparison. We know that this compare_edges function will be
306
* called only when starting a new edge, (not when stopping an
307
* edge), so we don't have to worry about conditionally inverting
308
* the sense of _slope_compare. */
309
cmp = _slope_compare (a, b);
313
/* We've got two collinear edges now. */
315
/* Since we're dealing with start events, prefer comparing top
316
* edges before bottom edges. */
317
cmp = _cairo_bo_point32_compare (&a->top, &b->top);
321
cmp = _cairo_bo_point32_compare (&a->bottom, &b->bottom);
325
/* Finally, we've got two identical edges. Let's finally
326
* discriminate by a simple pointer comparison, (which works only
327
* because we "know" the edges are all in a single array and don't
336
_sweep_line_elt_compare (void *list,
340
cairo_bo_sweep_line_t *sweep_line = list;
341
sweep_line_elt_t *edge_elt_a = a;
342
sweep_line_elt_t *edge_elt_b = b;
344
return _cairo_bo_sweep_line_compare_edges (sweep_line,
350
cairo_bo_event_compare (cairo_bo_event_t const *a,
351
cairo_bo_event_t const *b)
355
/* The major motion of the sweep line is vertical (top-to-bottom),
356
* and the minor motion is horizontal (left-to-right), dues to the
357
* infinitesimal tilt rule.
359
* Our point comparison function respects these rules.
361
cmp = _cairo_bo_point32_compare (&a->point, &b->point);
365
/* The events share a common point, so further discrimination is
366
* determined by the event type. Due to the infinitesimal
367
* shortening rule, stop events come first, then intersection
368
* events, then start events.
370
if (a->type != b->type) {
371
if (a->type == CAIRO_BO_EVENT_TYPE_STOP)
373
if (a->type == CAIRO_BO_EVENT_TYPE_START)
376
if (b->type == CAIRO_BO_EVENT_TYPE_STOP)
378
if (b->type == CAIRO_BO_EVENT_TYPE_START)
382
/* At this stage we are looking at two events of the same type at
383
* the same point. The final sort key is a slope comparison. We
384
* need a different sense for start and stop events based on the
387
* NOTE: Fortunately, we get to ignore errors in the relative
388
* ordering of intersection events. This means we don't even have
389
* to look at e2 here, nor worry about which sense of the slope
390
* comparison test is used for intersection events.
392
cmp = _slope_compare (a->e1, b->e1);
394
if (a->type == CAIRO_BO_EVENT_TYPE_START)
400
/* Next look at the opposite point. This leaves ambiguities only
401
* for identical edges. */
402
if (a->type == CAIRO_BO_EVENT_TYPE_START) {
403
cmp = _cairo_bo_point32_compare (&b->e1->bottom,
408
else if (a->type == CAIRO_BO_EVENT_TYPE_STOP) {
409
cmp = _cairo_bo_point32_compare (&a->e1->top,
414
else { /* CAIRO_BO_EVENT_TYPE_INTERSECT */
415
/* For two intersection events at the identical point, we
416
* don't care what order they sort in, but we do care that we
417
* have a stable sort. In particular intersections between
418
* different pairs of edges must never return 0. */
419
cmp = _cairo_bo_point32_compare (&a->e2->top, &b->e2->top);
422
cmp = _cairo_bo_point32_compare (&a->e2->bottom, &b->e2->bottom);
425
cmp = _cairo_bo_point32_compare (&a->e1->top, &b->e1->top);
428
cmp = _cairo_bo_point32_compare (&a->e1->bottom, &b->e1->bottom);
433
/* Discrimination based on the edge pointers. */
446
cairo_bo_event_compare_abstract (void *list,
450
cairo_bo_event_t *event_a = a;
451
cairo_bo_event_t *event_b = b;
453
return cairo_bo_event_compare (event_a, event_b);
457
cairo_bo_event_compare_pointers (void const *voida,
460
cairo_bo_event_t const * const *a = voida;
461
cairo_bo_event_t const * const *b = voidb;
463
int cmp = cairo_bo_event_compare (*a, *b);
474
static inline cairo_int64_t
483
/* det = a * d - b * c */
484
ad = _cairo_int32x32_64_mul (a, d);
485
bc = _cairo_int32x32_64_mul (b, c);
487
return _cairo_int64_sub (ad, bc);
490
static inline cairo_int128_t
491
det64_128 (cairo_int64_t a,
499
/* det = a * d - b * c */
500
ad = _cairo_int64x64_128_mul (a, d);
501
bc = _cairo_int64x64_128_mul (b, c);
503
return _cairo_int128_sub (ad, bc);
506
/* Compute the intersection of two lines as defined by two edges. The
507
* result is provided as a coordinate pair of 128-bit integers.
509
* Returns CAIRO_BO_STATUS_INTERSECTION if there is an intersection or
510
* CAIRO_BO_STATUS_PARALLEL if the two lines are exactly parallel.
512
static cairo_bo_status_t
513
intersect_lines (cairo_bo_edge_t *a,
515
cairo_bo_intersect_point_t *intersection)
517
cairo_int64_t a_det, b_det;
519
/* XXX: We're assuming here that dx and dy will still fit in 32
520
* bits. That's not true in general as there could be overflow. We
521
* should prevent that before the tessellation algorithm begins.
522
* What we're doing to mitigate this is to perform clamping in
523
* cairo_bo_tessellate_polygon().
525
int32_t dx1 = a->top.x - a->bottom.x;
526
int32_t dy1 = a->top.y - a->bottom.y;
528
int32_t dx2 = b->top.x - b->bottom.x;
529
int32_t dy2 = b->top.y - b->bottom.y;
531
cairo_int64_t den_det = det32_64 (dx1, dy1, dx2, dy2);
534
if (_cairo_int64_eq (den_det, 0))
535
return CAIRO_BO_STATUS_PARALLEL;
537
a_det = det32_64 (a->top.x, a->top.y,
538
a->bottom.x, a->bottom.y);
539
b_det = det32_64 (b->top.x, b->top.y,
540
b->bottom.x, b->bottom.y);
542
/* x = det (a_det, dx1, b_det, dx2) / den_det */
543
qr = _cairo_int_96by64_32x64_divrem (det64_128 (a_det, dx1,
546
if (_cairo_int64_eq (qr.rem,den_det))
547
return CAIRO_BO_STATUS_NO_INTERSECTION;
548
intersection->x.ordinate = qr.quo;
549
intersection->x.exactness = qr.rem ? INEXACT : EXACT;
551
/* y = det (a_det, dy1, b_det, dy2) / den_det */
552
qr = _cairo_int_96by64_32x64_divrem (det64_128 (a_det, dy1,
555
if (_cairo_int64_eq (qr.rem, den_det))
556
return CAIRO_BO_STATUS_NO_INTERSECTION;
557
intersection->y.ordinate = qr.quo;
558
intersection->y.exactness = qr.rem ? INEXACT : EXACT;
560
return CAIRO_BO_STATUS_INTERSECTION;
564
_cairo_bo_intersect_ordinate_32_compare (cairo_bo_intersect_ordinate_t a,
567
/* First compare the quotient */
572
/* With quotient identical, if remainder is 0 then compare equal */
573
/* Otherwise, the non-zero remainder makes a > b */
574
return INEXACT == a.exactness;
577
/* Does the given edge contain the given point. The point must already
578
* be known to be contained within the line determined by the edge,
579
* (most likely the point results from an intersection of this edge
582
* If we had exact arithmetic, then this function would simply be a
583
* matter of examining whether the y value of the point lies within
584
* the range of y values of the edge. But since intersection points
585
* are not exact due to being rounded to the nearest integer within
586
* the available precision, we must also examine the x value of the
589
* The definition of "contains" here is that the given intersection
590
* point will be seen by the sweep line after the start event for the
591
* given edge and before the stop event for the edge. See the comments
592
* in the implementation for more details.
595
_cairo_bo_edge_contains_intersect_point (cairo_bo_edge_t *edge,
596
cairo_bo_intersect_point_t *point)
598
int cmp_top, cmp_bottom;
600
/* XXX: When running the actual algorithm, we don't actually need to
601
* compare against edge->top at all here, since any intersection above
602
* top is eliminated early via a slope comparison. We're leaving these
603
* here for now only for the sake of the quadratic-time intersection
604
* finder which needs them.
607
cmp_top = _cairo_bo_intersect_ordinate_32_compare (point->y, edge->top.y);
608
cmp_bottom = _cairo_bo_intersect_ordinate_32_compare (point->y, edge->bottom.y);
610
if (cmp_top < 0 || cmp_bottom > 0)
615
if (cmp_top > 0 && cmp_bottom < 0)
620
/* At this stage, the point lies on the same y value as either
621
* edge->top or edge->bottom, so we have to examine the x value in
622
* order to properly determine containment. */
624
/* If the y value of the point is the same as the y value of the
625
* top of the edge, then the x value of the point must be greater
626
* to be considered as inside the edge. Similarly, if the y value
627
* of the point is the same as the y value of the bottom of the
628
* edge, then the x value of the point must be less to be
629
* considered as inside. */
632
return (_cairo_bo_intersect_ordinate_32_compare (point->x, edge->top.x) > 0);
633
else /* cmp_bottom == 0 */
634
return (_cairo_bo_intersect_ordinate_32_compare (point->x, edge->bottom.x) < 0);
637
/* Compute the intersection of two edges. The result is provided as a
638
* coordinate pair of 128-bit integers.
640
* Returns CAIRO_BO_STATUS_INTERSECTION if there is an intersection
641
* that is within both edges, CAIRO_BO_STATUS_NO_INTERSECTION if the
642
* intersection of the lines defined by the edges occurs outside of
643
* one or both edges, and CAIRO_BO_STATUS_PARALLEL if the two edges
644
* are exactly parallel.
646
* Note that when determining if a candidate intersection is "inside"
647
* an edge, we consider both the infinitesimal shortening and the
648
* infinitesimal tilt rules described by John Hobby. Specifically, if
649
* the intersection is exactly the same as an edge point, it is
650
* effectively outside (no intersection is returned). Also, if the
651
* intersection point has the same
653
static cairo_bo_status_t
654
_cairo_bo_edge_intersect (cairo_bo_edge_t *a,
656
cairo_bo_point32_t *intersection)
658
cairo_bo_status_t status;
659
cairo_bo_intersect_point_t quorem;
661
status = intersect_lines (a, b, &quorem);
665
if (! _cairo_bo_edge_contains_intersect_point (a, &quorem))
666
return CAIRO_BO_STATUS_NO_INTERSECTION;
668
if (! _cairo_bo_edge_contains_intersect_point (b, &quorem))
669
return CAIRO_BO_STATUS_NO_INTERSECTION;
671
/* Now that we've correctly compared the intersection point and
672
* determined that it lies within the edge, then we know that we
673
* no longer need any more bits of storage for the intersection
674
* than we do for our edge coordinates. We also no longer need the
675
* remainder from the division. */
676
intersection->x = quorem.x.ordinate;
677
intersection->y = quorem.y.ordinate;
679
return CAIRO_BO_STATUS_INTERSECTION;
683
_cairo_bo_event_init (cairo_bo_event_t *event,
684
cairo_bo_event_type_t type,
687
cairo_bo_point32_t point)
692
event->point = point;
696
_cairo_bo_event_queue_insert (cairo_bo_event_queue_t *queue,
697
cairo_bo_event_t *event)
699
/* Don't insert if there's already an equivalent intersection event in the queue. */
700
_cairo_skip_list_insert (&queue->intersection_queue, event,
701
event->type == CAIRO_BO_EVENT_TYPE_INTERSECTION);
705
_cairo_bo_event_queue_delete (cairo_bo_event_queue_t *queue,
706
cairo_bo_event_t *event)
708
if (CAIRO_BO_EVENT_TYPE_INTERSECTION == event->type)
709
_cairo_skip_list_delete_given ( &queue->intersection_queue, &event->elt );
712
static cairo_bo_event_t *
713
_cairo_bo_event_dequeue (cairo_bo_event_queue_t *event_queue)
715
skip_elt_t *elt = event_queue->intersection_queue.chains[0];
716
cairo_bo_event_t *intersection = elt ? SKIP_ELT_TO_EVENT (elt) : NULL;
717
cairo_bo_event_t *startstop;
719
if (event_queue->next_startstop_event_index == event_queue->num_startstop_events)
721
startstop = event_queue->sorted_startstop_event_ptrs[
722
event_queue->next_startstop_event_index];
724
if (!intersection || cairo_bo_event_compare (startstop, intersection) <= 0)
726
event_queue->next_startstop_event_index++;
732
static cairo_status_t
733
_cairo_bo_event_queue_init (cairo_bo_event_queue_t *event_queue,
734
cairo_bo_edge_t *edges,
738
cairo_bo_event_t *events, **sorted_event_ptrs;
739
unsigned num_events = 2*num_edges;
741
memset (event_queue, 0, sizeof(*event_queue));
743
_cairo_skip_list_init (&event_queue->intersection_queue,
744
cairo_bo_event_compare_abstract,
745
sizeof (cairo_bo_event_t));
747
return CAIRO_STATUS_SUCCESS;
749
/* The skip_elt_t field of a cairo_bo_event_t isn't used for start
750
* or stop events, so this allocation is safe. XXX: make the
751
* event type a union so it doesn't always contain the skip
753
events = malloc (num_events * sizeof(cairo_bo_event_t));
754
sorted_event_ptrs = malloc (num_events * sizeof(cairo_bo_event_t*));
755
if (!events || !sorted_event_ptrs) {
756
if (events) free(events);
757
if (sorted_event_ptrs) free(sorted_event_ptrs);
758
return CAIRO_STATUS_NO_MEMORY;
760
event_queue->startstop_events = events;
761
event_queue->sorted_startstop_event_ptrs = sorted_event_ptrs;
762
event_queue->num_startstop_events = (unsigned)(num_events);
763
event_queue->next_startstop_event_index = 0;
765
for (i = 0; i < num_edges; i++) {
766
sorted_event_ptrs[2*i] = &events[2*i];
767
sorted_event_ptrs[2*i+1] = &events[2*i+1];
769
/* Initialize "middle" to top */
770
edges[i].middle = edges[i].top;
772
_cairo_bo_event_init (&events[2*i],
773
CAIRO_BO_EVENT_TYPE_START,
777
_cairo_bo_event_init (&events[2*i+1],
778
CAIRO_BO_EVENT_TYPE_STOP,
783
qsort (sorted_event_ptrs, num_events,
784
sizeof(cairo_bo_event_t *),
785
cairo_bo_event_compare_pointers);
786
return CAIRO_STATUS_SUCCESS;
790
_cairo_bo_event_queue_fini (cairo_bo_event_queue_t *event_queue)
792
_cairo_skip_list_fini (&event_queue->intersection_queue);
793
if (event_queue->startstop_events)
794
free (event_queue->startstop_events);
795
if (event_queue->sorted_startstop_event_ptrs)
796
free (event_queue->sorted_startstop_event_ptrs);
800
_cairo_bo_event_queue_insert_if_intersect_below_current_y (cairo_bo_event_queue_t *event_queue,
801
cairo_bo_edge_t *left,
802
cairo_bo_edge_t *right)
804
cairo_bo_status_t status;
805
cairo_bo_point32_t intersection;
806
cairo_bo_event_t event;
808
if (left == NULL || right == NULL)
811
/* The names "left" and "right" here are correct descriptions of
812
* the order of the two edges within the active edge list. So if a
813
* slope comparison also puts left less than right, then we know
814
* that the intersection of these two segments has oalready
815
* occurred before the current sweep line position. */
816
if (_slope_compare (left, right) < 0)
819
status = _cairo_bo_edge_intersect (left, right, &intersection);
820
if (status == CAIRO_BO_STATUS_PARALLEL ||
821
status == CAIRO_BO_STATUS_NO_INTERSECTION)
826
_cairo_bo_event_init (&event,
827
CAIRO_BO_EVENT_TYPE_INTERSECTION,
831
_cairo_bo_event_queue_insert (event_queue, &event);
835
_cairo_bo_sweep_line_init (cairo_bo_sweep_line_t *sweep_line)
837
_cairo_skip_list_init (&sweep_line->active_edges,
838
_sweep_line_elt_compare,
839
sizeof (sweep_line_elt_t));
840
sweep_line->head = NULL;
841
sweep_line->tail = NULL;
842
sweep_line->current_y = 0;
846
_cairo_bo_sweep_line_fini (cairo_bo_sweep_line_t *sweep_line)
848
_cairo_skip_list_fini (&sweep_line->active_edges);
852
_cairo_bo_sweep_line_insert (cairo_bo_sweep_line_t *sweep_line,
853
cairo_bo_edge_t *edge)
855
skip_elt_t *next_elt;
856
sweep_line_elt_t *sweep_line_elt;
857
cairo_bo_edge_t **prev_of_next, **next_of_prev;
859
sweep_line_elt = _cairo_skip_list_insert (&sweep_line->active_edges, &edge,
860
1 /* unique inserts*/);
862
next_elt = sweep_line_elt->elt.next[0];
864
prev_of_next = & (SKIP_ELT_TO_EDGE (next_elt)->prev);
866
prev_of_next = &sweep_line->tail;
869
next_of_prev = &(*prev_of_next)->next;
871
next_of_prev = &sweep_line->head;
873
edge->prev = *prev_of_next;
874
edge->next = *next_of_prev;
875
*prev_of_next = edge;
876
*next_of_prev = edge;
878
edge->sweep_line_elt = sweep_line_elt;
882
_cairo_bo_sweep_line_delete (cairo_bo_sweep_line_t *sweep_line,
883
cairo_bo_edge_t *edge)
885
cairo_bo_edge_t **left_next, **right_prev;
887
_cairo_skip_list_delete_given (&sweep_line->active_edges, &edge->sweep_line_elt->elt);
889
left_next = &sweep_line->head;
891
left_next = &edge->prev->next;
893
right_prev = &sweep_line->tail;
895
right_prev = &edge->next->prev;
897
*left_next = edge->next;
898
*right_prev = edge->prev;
902
_cairo_bo_sweep_line_swap (cairo_bo_sweep_line_t *sweep_line,
903
cairo_bo_edge_t *left,
904
cairo_bo_edge_t *right)
906
sweep_line_elt_t *left_elt, *right_elt;
907
cairo_bo_edge_t **before_left, **after_right;
909
/* Within the skip list we can do the swap simply by swapping the
910
* pointers to the edge elements and leaving all of the skip list
911
* elements and pointers unchanged. */
912
left_elt = left->sweep_line_elt;
913
right_elt = SKIP_ELT_TO_EDGE_ELT (left_elt->elt.next[0]);
915
left_elt->edge = right;
916
right->sweep_line_elt = left_elt;
918
right_elt->edge = left;
919
left->sweep_line_elt = right_elt;
921
/* Within the doubly-linked list of edges, there's a bit more
922
* bookkeeping involved with the swap. */
923
before_left = &sweep_line->head;
925
before_left = &left->prev->next;
926
*before_left = right;
928
after_right = &sweep_line->tail;
930
after_right = &right->next->prev;
933
left->next = right->next;
936
right->prev = left->prev;
940
#define DEBUG_PRINT_STATE 0
941
#if DEBUG_PRINT_STATE
943
_cairo_bo_edge_print (cairo_bo_edge_t *edge)
945
printf ("(0x%x, 0x%x)-(0x%x, 0x%x)",
946
edge->top.x, edge->top.y,
947
edge->bottom.x, edge->bottom.y);
951
_cairo_bo_event_print (cairo_bo_event_t *event)
953
switch (event->type) {
954
case CAIRO_BO_EVENT_TYPE_START:
957
case CAIRO_BO_EVENT_TYPE_STOP:
960
case CAIRO_BO_EVENT_TYPE_INTERSECTION:
961
printf ("Intersection: ");
964
printf ("(%d, %d)\t", event->point.x, event->point.y);
965
_cairo_bo_edge_print (event->e1);
966
if (event->type == CAIRO_BO_EVENT_TYPE_INTERSECTION) {
968
_cairo_bo_edge_print (event->e2);
974
_cairo_bo_event_queue_print (cairo_bo_event_queue_t *event_queue)
977
/* XXX: fixme to print the start/stop array too. */
978
cairo_skip_list_t *queue = &event_queue->intersection_queue;
979
cairo_bo_event_t *event;
981
printf ("Event queue:\n");
983
for (elt = queue->chains[0];
987
event = SKIP_ELT_TO_EVENT (elt);
988
_cairo_bo_event_print (event);
993
_cairo_bo_sweep_line_print (cairo_bo_sweep_line_t *sweep_line)
995
cairo_bool_t first = TRUE;
997
cairo_bo_edge_t *edge;
999
printf ("Sweep line (reversed): ");
1001
for (edge = sweep_line->tail;
1007
_cairo_bo_edge_print (edge);
1013
printf ("Sweep line from edge list: ");
1015
for (edge = sweep_line->head;
1021
_cairo_bo_edge_print (edge);
1026
printf ("Sweep line from skip list: ");
1028
for (elt = sweep_line->active_edges.chains[0];
1034
_cairo_bo_edge_print (SKIP_ELT_TO_EDGE (elt));
1041
print_state (const char *msg,
1042
cairo_bo_event_queue_t *event_queue,
1043
cairo_bo_sweep_line_t *sweep_line)
1045
printf ("%s\n", msg);
1046
_cairo_bo_event_queue_print (event_queue);
1047
_cairo_bo_sweep_line_print (sweep_line);
1052
/* Adds the trapezoid, if any, of the left edge to the cairo_traps_t
1054
static cairo_status_t
1055
_cairo_bo_edge_end_trap (cairo_bo_edge_t *left,
1057
cairo_bo_traps_t *bo_traps)
1059
cairo_fixed_t fixed_top, fixed_bot;
1060
cairo_status_t status = CAIRO_STATUS_SUCCESS;
1061
cairo_bo_trap_t *trap = left->deferred_trap;
1062
cairo_bo_edge_t *right;
1065
return CAIRO_STATUS_SUCCESS;
1067
/* If the right edge of the trapezoid stopped earlier than the
1068
* left edge, then cut the trapezoid bottom early. */
1069
right = trap->right;
1070
if (right->bottom.y < bot)
1071
bot = right->bottom.y;
1073
fixed_top = trap->top;
1076
/* Only emit trapezoids with positive height. */
1077
if (fixed_top < fixed_bot) {
1078
cairo_point_t left_top, left_bot, right_top, right_bot;
1079
cairo_fixed_t xmin = bo_traps->xmin;
1080
cairo_fixed_t ymin = bo_traps->ymin;
1084
left_top.x = left->top.x + xmin;
1085
left_top.y = left->top.y + ymin;
1086
right_top.x = right->top.x + xmin;
1087
right_top.y = right->top.y + ymin;
1088
left_bot.x = left->bottom.x + xmin;
1089
left_bot.y = left->bottom.y + ymin;
1090
right_bot.x = right->bottom.x + xmin;
1091
right_bot.y = right->bottom.y + ymin;
1093
/* Avoid emitting the trapezoid if it is obviously degenerate.
1094
* TODO: need a real collinearity test here for the cases
1095
* where the trapezoid is degenerate, yet the top and bottom
1096
* coordinates aren't equal. */
1097
if (left_top.x != right_top.x ||
1098
left_top.y != right_top.y ||
1099
left_bot.x != right_bot.x ||
1100
left_bot.y != right_bot.y)
1102
status = _cairo_traps_add_trap_from_points (bo_traps->traps,
1106
right_top, right_bot);
1108
#if DEBUG_PRINT_STATE
1109
printf ("Deferred trap: left=(%08x, %08x)-(%08x,%08x) "
1110
"right=(%08x,%08x)-(%08x,%08x) top=%08x, bot=%08x\n",
1111
left->top.x, left->top.y, left->bottom.x, left->bottom.y,
1112
right->top.x, right->top.y, right->bottom.x, right->bottom.y,
1118
_cairo_freelist_free (&bo_traps->freelist, trap);
1119
left->deferred_trap = NULL;
1123
/* Start a new trapezoid at the given top y coordinate, whose edges
1124
* are `edge' and `edge->next'. If `edge' already has a trapezoid,
1125
* then either add it to the traps in `bo_traps', if the trapezoid's
1126
* right edge differs from `edge->next', or do nothing if the new
1127
* trapezoid would be a continuation of the existing one. */
1128
static cairo_status_t
1129
_cairo_bo_edge_start_or_continue_trap (cairo_bo_edge_t *edge,
1131
cairo_bo_traps_t *bo_traps)
1133
cairo_status_t status;
1134
cairo_bo_trap_t *trap = edge->deferred_trap;
1137
if (trap->right == edge->next) return CAIRO_STATUS_SUCCESS;
1138
status = _cairo_bo_edge_end_trap (edge, top, bo_traps);
1144
trap = edge->deferred_trap = _cairo_freelist_alloc (&bo_traps->freelist);
1145
if (!edge->deferred_trap)
1146
return CAIRO_STATUS_NO_MEMORY;
1148
trap->right = edge->next;
1151
return CAIRO_STATUS_SUCCESS;
1155
_cairo_bo_traps_init (cairo_bo_traps_t *bo_traps,
1156
cairo_traps_t *traps,
1162
bo_traps->traps = traps;
1163
_cairo_freelist_init (&bo_traps->freelist, sizeof(cairo_bo_trap_t));
1164
bo_traps->xmin = xmin;
1165
bo_traps->ymin = ymin;
1166
bo_traps->xmax = xmax;
1167
bo_traps->ymax = ymax;
1171
_cairo_bo_traps_fini (cairo_bo_traps_t *bo_traps)
1173
_cairo_freelist_fini (&bo_traps->freelist);
1177
_cairo_bo_sweep_line_validate (cairo_bo_sweep_line_t *sweep_line)
1179
cairo_bo_edge_t *edge;
1182
/* March through both the skip list's singly-linked list and the
1183
* sweep line's own list through pointers in the edges themselves
1184
* and make sure they agree at every point. */
1186
for (edge = sweep_line->head, elt = sweep_line->active_edges.chains[0];
1188
edge = edge->next, elt = elt->next[0])
1190
if (SKIP_ELT_TO_EDGE (elt) != edge) {
1191
fprintf (stderr, "*** Error: Sweep line fails to validate: Inconsistent data in the two lists.\n");
1197
fprintf (stderr, "*** Error: Sweep line fails to validate: One list ran out before the other.\n");
1203
static cairo_status_t
1204
_active_edges_to_traps (cairo_bo_edge_t *head,
1206
cairo_fill_rule_t fill_rule,
1207
cairo_bo_traps_t *bo_traps)
1209
cairo_status_t status;
1211
cairo_bo_edge_t *edge;
1213
for (edge = head; edge && edge->next; edge = edge->next) {
1214
if (fill_rule == CAIRO_FILL_RULE_WINDING) {
1220
status = _cairo_bo_edge_end_trap (edge, top, bo_traps);
1227
if ((in_out & 1) == 0) {
1228
status = _cairo_bo_edge_end_trap (edge, top, bo_traps);
1235
status = _cairo_bo_edge_start_or_continue_trap (edge, top, bo_traps);
1240
return CAIRO_STATUS_SUCCESS;
1243
/* Execute a single pass of the Bentley-Ottmann algorithm on edges,
1244
* generating trapezoids according to the fill_rule and appending them
1246
static cairo_status_t
1247
_cairo_bentley_ottmann_tessellate_bo_edges (cairo_bo_edge_t *edges,
1249
cairo_fill_rule_t fill_rule,
1250
cairo_traps_t *traps,
1255
int *num_intersections)
1257
cairo_status_t status = CAIRO_STATUS_SUCCESS;
1258
int intersection_count = 0;
1259
cairo_bo_event_queue_t event_queue;
1260
cairo_bo_sweep_line_t sweep_line;
1261
cairo_bo_traps_t bo_traps;
1262
cairo_bo_event_t *event, event_saved;
1263
cairo_bo_edge_t *edge;
1264
cairo_bo_edge_t *left, *right;
1265
cairo_bo_edge_t *edge1, *edge2;
1267
_cairo_bo_event_queue_init (&event_queue, edges, num_edges);
1268
_cairo_bo_sweep_line_init (&sweep_line);
1269
_cairo_bo_traps_init (&bo_traps, traps, xmin, ymin, xmax, ymax);
1271
#if DEBUG_PRINT_STATE
1272
print_state ("After initializing", &event_queue, &sweep_line);
1277
event = _cairo_bo_event_dequeue (&event_queue);
1281
if (event->point.y != sweep_line.current_y) {
1282
status = _active_edges_to_traps (sweep_line.head,
1283
sweep_line.current_y,
1284
fill_rule, &bo_traps);
1288
sweep_line.current_y = event->point.y;
1291
event_saved = *event;
1292
_cairo_bo_event_queue_delete (&event_queue, event);
1293
event = &event_saved;
1295
switch (event->type) {
1296
case CAIRO_BO_EVENT_TYPE_START:
1299
_cairo_bo_sweep_line_insert (&sweep_line, edge);
1300
/* Cache the insert position for use in pass 2.
1301
event->e2 = Sortlist::prev (sweep_line, edge);
1307
_cairo_bo_event_queue_insert_if_intersect_below_current_y (&event_queue, left, edge);
1309
_cairo_bo_event_queue_insert_if_intersect_below_current_y (&event_queue, edge, right);
1311
#if DEBUG_PRINT_STATE
1312
print_state ("After processing start", &event_queue, &sweep_line);
1314
_cairo_bo_sweep_line_validate (&sweep_line);
1317
case CAIRO_BO_EVENT_TYPE_STOP:
1323
_cairo_bo_sweep_line_delete (&sweep_line, edge);
1325
status = _cairo_bo_edge_end_trap (edge, edge->bottom.y, &bo_traps);
1329
_cairo_bo_event_queue_insert_if_intersect_below_current_y (&event_queue, left, right);
1331
#if DEBUG_PRINT_STATE
1332
print_state ("After processing stop", &event_queue, &sweep_line);
1334
_cairo_bo_sweep_line_validate (&sweep_line);
1337
case CAIRO_BO_EVENT_TYPE_INTERSECTION:
1341
/* skip this intersection if its edges are not adjacent */
1342
if (edge2 != edge1->next)
1345
intersection_count++;
1347
edge1->middle = event->point;
1348
edge2->middle = event->point;
1351
right = edge2->next;
1353
_cairo_bo_sweep_line_swap (&sweep_line, edge1, edge2);
1355
/* after the swap e2 is left of e1 */
1357
_cairo_bo_event_queue_insert_if_intersect_below_current_y (&event_queue,
1360
_cairo_bo_event_queue_insert_if_intersect_below_current_y (&event_queue,
1363
#if DEBUG_PRINT_STATE
1364
print_state ("After processing intersection", &event_queue, &sweep_line);
1366
_cairo_bo_sweep_line_validate (&sweep_line);
1372
*num_intersections = intersection_count;
1374
for (edge = sweep_line.head; edge; edge = edge->next) {
1375
cairo_status_t status2 = _cairo_bo_edge_end_trap (edge,
1376
sweep_line.current_y,
1381
_cairo_bo_traps_fini (&bo_traps);
1382
_cairo_bo_sweep_line_fini (&sweep_line);
1383
_cairo_bo_event_queue_fini (&event_queue);
1388
update_minmax(cairo_fixed_t *inout_min,
1389
cairo_fixed_t *inout_max,
1399
_cairo_bentley_ottmann_tessellate_polygon (cairo_traps_t *traps,
1400
cairo_polygon_t *polygon,
1401
cairo_fill_rule_t fill_rule)
1404
cairo_status_t status;
1405
cairo_bo_edge_t *edges;
1406
cairo_fixed_t xmin = 0x7FFFFFFF;
1407
cairo_fixed_t ymin = 0x7FFFFFFF;
1408
cairo_fixed_t xmax = -0x80000000;
1409
cairo_fixed_t ymax = -0x80000000;
1413
if (0 == polygon->num_edges)
1414
return CAIRO_STATUS_SUCCESS;
1416
edges = malloc (polygon->num_edges * sizeof (cairo_bo_edge_t));
1418
return CAIRO_STATUS_NO_MEMORY;
1420
/* Figure out the bounding box of the input coordinates and
1421
* validate that we're not given invalid polygon edges. */
1422
for (i = 0; i < polygon->num_edges; i++) {
1423
update_minmax (&xmin, &xmax, polygon->edges[i].edge.p1.x);
1424
update_minmax (&ymin, &ymax, polygon->edges[i].edge.p1.y);
1425
update_minmax (&xmin, &xmax, polygon->edges[i].edge.p2.x);
1426
update_minmax (&ymin, &ymax, polygon->edges[i].edge.p2.y);
1427
assert (polygon->edges[i].edge.p1.y <= polygon->edges[i].edge.p2.y &&
1428
"BUG: tessellator given upside down or horizontal edges");
1431
/* The tessellation functions currently assume that no line
1432
* segment extends more than 2^31-1 in either dimension. We
1433
* guarantee this by offsetting the internal coordinates to the
1434
* range [0,2^31-1], and clamping to 2^31-1 if a coordinate
1435
* exceeds the range (and yes, this generates an incorrect
1436
* result). First we have to clamp the bounding box itself. */
1437
/* XXX: Rather than changing the input values, a better approach
1438
* would be to detect out-of-bounds input and return a
1439
* CAIRO_STATUS_OVERFLOW value to the user. */
1440
if (xmax - xmin < 0)
1441
xmax = xmin + 0x7FFFFFFF;
1442
if (ymax - ymin < 0)
1443
ymax = ymin + 0x7FFFFFFF;
1445
for (i = 0, num_bo_edges = 0; i < polygon->num_edges; i++) {
1446
cairo_bo_edge_t *edge = &edges[num_bo_edges];
1447
cairo_point_t top = polygon->edges[i].edge.p1;
1448
cairo_point_t bot = polygon->edges[i].edge.p2;
1450
/* Offset coordinates into the non-negative range. */
1456
/* If the coordinates are still negative, then their extent is
1457
* overflowing 2^31-1. We're going to kludge it and clamp the
1458
* coordinates into the clamped bounding box. */
1459
if (top.x < 0) top.x = xmax - xmin;
1460
if (top.y < 0) top.y = ymax - ymin;
1461
if (bot.x < 0) bot.x = xmax - xmin;
1462
if (bot.y < 0) bot.y = ymax - ymin;
1464
if (top.y == bot.y) {
1465
/* Clamping might have produced horizontal edges. Ignore
1469
assert (top.y < bot.y &&
1470
"BUG: clamping the input range flipped the "
1471
"orientation of an edge");
1473
edge->top.x = top.x;
1474
edge->top.y = top.y;
1475
edge->bottom.x = bot.x;
1476
edge->bottom.y = bot.y;
1477
/* XXX: The 'clockWise' name that cairo_polygon_t uses is
1478
* totally bogus. It's really a (negated!) description of
1479
* whether the edge is reversed. */
1480
edge->reversed = (! polygon->edges[i].clockWise);
1481
edge->deferred_trap = NULL;
1484
edge->sweep_line_elt = NULL;
1489
/* XXX: This would be the convenient place to throw in multiple
1490
* passes of the Bentley-Ottmann algorithm. It would merely
1491
* require storing the results of each pass into a temporary
1493
status = _cairo_bentley_ottmann_tessellate_bo_edges (edges, num_bo_edges,
1495
xmin, ymin, xmax, ymax,
1505
edges_have_an_intersection_quadratic (cairo_bo_edge_t *edges,
1510
cairo_bo_edge_t *a, *b;
1511
cairo_bo_point32_t intersection;
1512
cairo_bo_status_t status;
1514
/* We must not be given any upside-down edges. */
1515
for (i = 0; i < num_edges; i++) {
1516
assert (_cairo_bo_point32_compare (&edges[i].top, &edges[i].bottom) < 0);
1517
edges[i].top.x <<= CAIRO_BO_GUARD_BITS;
1518
edges[i].top.y <<= CAIRO_BO_GUARD_BITS;
1519
edges[i].bottom.x <<= CAIRO_BO_GUARD_BITS;
1520
edges[i].bottom.y <<= CAIRO_BO_GUARD_BITS;
1523
for (i = 0; i < num_edges; i++) {
1524
for (j = 0; j < num_edges; j++) {
1531
status = _cairo_bo_edge_intersect (a, b, &intersection);
1532
if (status == CAIRO_BO_STATUS_PARALLEL ||
1533
status == CAIRO_BO_STATUS_NO_INTERSECTION)
1538
printf ("Found intersection (%d,%d) between (%d,%d)-(%d,%d) and (%d,%d)-(%d,%d)\n",
1542
a->bottom.x, a->bottom.y,
1544
b->bottom.x, b->bottom.y);
1552
#define TEST_MAX_EDGES 10
1554
typedef struct test {
1556
const char *description;
1558
cairo_bo_edge_t edges[TEST_MAX_EDGES];
1565
"3 edges all intersecting very close to each other",
1568
{ { 4, 2}, {0, 0}, { 9, 9}, NULL, NULL },
1569
{ { 7, 2}, {0, 0}, { 2, 3}, NULL, NULL },
1570
{ { 5, 2}, {0, 0}, { 1, 7}, NULL, NULL }
1574
"inconsistent data",
1575
"Derived from random testing---was leading to skip list and edge list disagreeing.",
1578
{ { 2, 3}, {0, 0}, { 8, 9}, NULL, NULL },
1579
{ { 2, 3}, {0, 0}, { 6, 7}, NULL, NULL }
1584
"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?",
1587
{ { 6, 2}, {0, 0}, { 6, 5}, NULL, NULL },
1588
{ { 3, 5}, {0, 0}, { 5, 6}, NULL, NULL },
1589
{ { 9, 2}, {0, 0}, { 5, 6}, NULL, NULL },
1593
"minimal-intersection",
1594
"Intersection of a two from among the smallest possible edges.",
1597
{ { 0, 0}, {0, 0}, { 1, 1}, NULL, NULL },
1598
{ { 1, 0}, {0, 0}, { 0, 1}, NULL, NULL }
1603
"A simple intersection of two edges at an integer (2,2).",
1606
{ { 1, 1}, {0, 0}, { 3, 3}, NULL, NULL },
1607
{ { 2, 1}, {0, 0}, { 2, 3}, NULL, NULL }
1611
"bend-to-horizontal",
1612
"With intersection truncation one edge bends to horizontal",
1615
{ { 9, 1}, {0, 0}, {3, 7}, NULL, NULL },
1616
{ { 3, 5}, {0, 0}, {9, 9}, NULL, NULL }
1624
"An intersection that occurs at the endpoint of a segment.",
1626
{ { 4, 6}, { 5, 6}, NULL, { { NULL }} },
1627
{ { 4, 5}, { 5, 7}, NULL, { { NULL }} },
1628
{ { 0, 0}, { 0, 0}, NULL, { { NULL }} },
1632
name = "overlapping",
1633
desc = "Parallel segments that share an endpoint, with different slopes.",
1635
{ top = { x = 2, y = 0}, bottom = { x = 1, y = 1}},
1636
{ top = { x = 2, y = 0}, bottom = { x = 0, y = 2}},
1637
{ top = { x = 0, y = 3}, bottom = { x = 1, y = 3}},
1638
{ top = { x = 0, y = 3}, bottom = { x = 2, y = 3}},
1639
{ top = { x = 0, y = 4}, bottom = { x = 0, y = 6}},
1640
{ top = { x = 0, y = 5}, bottom = { x = 0, y = 6}}
1644
name = "hobby_stage_3",
1645
desc = "A particularly tricky part of the 3rd stage of the 'hobby' test below.",
1647
{ top = { x = -1, y = -2}, bottom = { x = 4, y = 2}},
1648
{ top = { x = 5, y = 3}, bottom = { x = 9, y = 5}},
1649
{ top = { x = 5, y = 3}, bottom = { x = 6, y = 3}},
1654
desc = "Example from John Hobby's paper. Requires 3 passes of the iterative algorithm.",
1656
{ top = { x = 0, y = 0}, bottom = { x = 9, y = 5}},
1657
{ top = { x = 0, y = 0}, bottom = { x = 13, y = 6}},
1658
{ top = { x = -1, y = -2}, bottom = { x = 9, y = 5}}
1663
desc = "Edges with same start/stop points but different slopes",
1665
{ top = { x = 4, y = 1}, bottom = { x = 6, y = 3}},
1666
{ top = { x = 4, y = 1}, bottom = { x = 2, y = 3}},
1667
{ top = { x = 2, y = 4}, bottom = { x = 4, y = 6}},
1668
{ top = { x = 6, y = 4}, bottom = { x = 4, y = 6}}
1672
name = "horizontal",
1673
desc = "Test of a horizontal edge",
1675
{ top = { x = 1, y = 1}, bottom = { x = 6, y = 6}},
1676
{ top = { x = 2, y = 3}, bottom = { x = 5, y = 3}}
1681
desc = "Test of a vertical edge",
1683
{ top = { x = 5, y = 1}, bottom = { x = 5, y = 7}},
1684
{ top = { x = 2, y = 4}, bottom = { x = 8, y = 5}}
1689
desc = "Two overlapping edges with the same slope",
1691
{ top = { x = 5, y = 1}, bottom = { x = 5, y = 7}},
1692
{ top = { x = 5, y = 2}, bottom = { x = 5, y = 6}},
1693
{ top = { x = 2, y = 4}, bottom = { x = 8, y = 5}}
1698
desc = "Several segments with a common intersection point",
1700
{ top = { x = 1, y = 2}, bottom = { x = 5, y = 4} },
1701
{ top = { x = 1, y = 1}, bottom = { x = 5, y = 5} },
1702
{ top = { x = 2, y = 1}, bottom = { x = 4, y = 5} },
1703
{ top = { x = 4, y = 1}, bottom = { x = 2, y = 5} },
1704
{ top = { x = 5, y = 1}, bottom = { x = 1, y = 5} },
1705
{ top = { x = 5, y = 2}, bottom = { x = 1, y = 4} }
1712
run_test (const char *test_name,
1713
cairo_bo_edge_t *test_edges,
1716
int i, intersections, passes;
1717
cairo_bo_edge_t *edges;
1718
cairo_array_t intersected_edges;
1720
printf ("Testing: %s\n", test_name);
1722
_cairo_array_init (&intersected_edges, sizeof (cairo_bo_edge_t));
1724
intersections = _cairo_bentley_ottmann_intersect_edges (test_edges, num_edges, &intersected_edges);
1726
printf ("Pass 1 found %d intersections:\n", intersections);
1729
/* XXX: Multi-pass Bentley-Ottmmann. Preferable would be to add a
1730
* pass of Hobby's tolerance-square algorithm instead. */
1732
while (intersections) {
1733
int num_edges = _cairo_array_num_elements (&intersected_edges);
1735
edges = malloc (num_edges * sizeof (cairo_bo_edge_t));
1736
assert (edges != NULL);
1737
memcpy (edges, _cairo_array_index (&intersected_edges, 0), num_edges * sizeof (cairo_bo_edge_t));
1738
_cairo_array_fini (&intersected_edges);
1739
_cairo_array_init (&intersected_edges, sizeof (cairo_bo_edge_t));
1740
intersections = _cairo_bentley_ottmann_intersect_edges (edges, num_edges, &intersected_edges);
1744
printf ("Pass %d found %d remaining intersections:\n", passes, intersections);
1747
for (i = 0; i < passes; i++)
1749
printf ("No remainining intersections found after pass %d\n", passes);
1753
if (edges_have_an_intersection_quadratic (_cairo_array_index (&intersected_edges, 0),
1754
_cairo_array_num_elements (&intersected_edges)))
1755
printf ("*** FAIL ***\n");
1759
_cairo_array_fini (&intersected_edges);
1764
#define MAX_RANDOM 300
1769
char random_name[] = "random-XX";
1770
cairo_bo_edge_t random_edges[MAX_RANDOM], *edge;
1771
unsigned int i, num_random;
1774
for (i = 0; i < sizeof (tests) / sizeof (tests[0]); i++) {
1776
run_test (test->name, test->edges, test->num_edges);
1779
for (num_random = 0; num_random < MAX_RANDOM; num_random++) {
1781
for (i = 0; i < num_random; i++) {
1783
edge = &random_edges[i];
1784
edge->top.x = (int32_t) (10.0 * (rand() / (RAND_MAX + 1.0)));
1785
edge->top.y = (int32_t) (10.0 * (rand() / (RAND_MAX + 1.0)));
1786
edge->bottom.x = (int32_t) (10.0 * (rand() / (RAND_MAX + 1.0)));
1787
edge->bottom.y = (int32_t) (10.0 * (rand() / (RAND_MAX + 1.0)));
1788
if (edge->top.y > edge->bottom.y) {
1789
int32_t tmp = edge->top.y;
1790
edge->top.y = edge->bottom.y;
1791
edge->bottom.y = tmp;
1793
} while (edge->top.y == edge->bottom.y);
1796
sprintf (random_name, "random-%02d", num_random);
1798
run_test (random_name, random_edges, num_random);
added
removed
cairo/src/cairo-bentley-ottmann.c
