Subversion Repositories Scribus

Rev

Rev 14952 | Details | Compare with Previous | Last modification | View Log | RSS feed

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