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 © 2009 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-combsort-private.h"
42
#include "cairo-list-private.h"
43
 
44
typedef struct _cairo_bo_rectangle cairo_bo_rectangle_t;
45
typedef struct _cairo_bo_edge cairo_bo_edge_t;
46
 
47
/* A deferred trapezoid of an edge */
48
typedef struct _cairo_bo_trap {
49
    cairo_bo_edge_t *right;
50
    int32_t top;
51
} cairo_bo_trap_t;
52
 
53
struct _cairo_bo_edge {
54
    int x;
55
    int dir;
56
    cairo_bo_trap_t deferred_trap;
57
    cairo_list_t link;
58
};
59
 
60
struct _cairo_bo_rectangle {
61
    cairo_bo_edge_t left, right;
62
    int top, bottom;
63
};
64
 
65
/* the parent is always given by index/2 */
66
#define PQ_PARENT_INDEX(i) ((i) >> 1)
67
#define PQ_FIRST_ENTRY 1
68
 
69
/* left and right children are index * 2 and (index * 2) +1 respectively */
70
#define PQ_LEFT_CHILD_INDEX(i) ((i) << 1)
71
 
72
typedef struct _pqueue {
73
    int size, max_size;
74
 
75
    cairo_bo_rectangle_t **elements;
76
    cairo_bo_rectangle_t *elements_embedded[1024];
77
} pqueue_t;
78
 
79
typedef struct _cairo_bo_sweep_line {
80
    cairo_bo_rectangle_t **rectangles;
81
    pqueue_t stop;
82
    cairo_list_t sweep;
83
    cairo_list_t *current_left, *current_right;
84
    int32_t current_y;
85
    int32_t last_y;
86
} cairo_bo_sweep_line_t;
87
 
88
#define DEBUG_TRAPS 0
89
 
90
#if DEBUG_TRAPS
91
static void
92
dump_traps (cairo_traps_t *traps, const char *filename)
93
{
94
    FILE *file;
95
    int n;
96
 
97
    if (getenv ("CAIRO_DEBUG_TRAPS") == NULL)
98
        return;
99
 
100
    file = fopen (filename, "a");
101
    if (file != NULL) {
102
        for (n = 0; n < traps->num_traps; n++) {
103
            fprintf (file, "%d %d L:(%d, %d), (%d, %d) R:(%d, %d), (%d, %d)\n",
104
                     traps->traps[n].top,
105
                     traps->traps[n].bottom,
106
                     traps->traps[n].left.p1.x,
107
                     traps->traps[n].left.p1.y,
108
                     traps->traps[n].left.p2.x,
109
                     traps->traps[n].left.p2.y,
110
                     traps->traps[n].right.p1.x,
111
                     traps->traps[n].right.p1.y,
112
                     traps->traps[n].right.p2.x,
113
                     traps->traps[n].right.p2.y);
114
        }
115
        fprintf (file, "\n");
116
        fclose (file);
117
    }
118
}
119
#else
120
#define dump_traps(traps, filename)
121
#endif
122
 
123
static inline int
124
cairo_bo_rectangle_compare_start (const cairo_bo_rectangle_t *a,
125
                                  const cairo_bo_rectangle_t *b)
126
{
127
    return a->top - b->top;
128
}
129
 
130
static inline int
131
_cairo_bo_rectangle_compare_stop (const cairo_bo_rectangle_t *a,
132
                                  const cairo_bo_rectangle_t *b)
133
{
134
    return a->bottom - b->bottom;
135
}
136
 
137
static inline void
138
_pqueue_init (pqueue_t *pq)
139
{
140
    pq->max_size = ARRAY_LENGTH (pq->elements_embedded);
141
    pq->size = 0;
142
 
143
    pq->elements = pq->elements_embedded;
144
    pq->elements[PQ_FIRST_ENTRY] = NULL;
145
}
146
 
147
static inline void
148
_pqueue_fini (pqueue_t *pq)
149
{
150
    if (pq->elements != pq->elements_embedded)
151
        free (pq->elements);
152
}
153
 
154
static cairo_status_t
155
_pqueue_grow (pqueue_t *pq)
156
{
157
    cairo_bo_rectangle_t **new_elements;
158
    pq->max_size *= 2;
159
 
160
    if (pq->elements == pq->elements_embedded) {
161
        new_elements = _cairo_malloc_ab (pq->max_size,
162
                                         sizeof (cairo_bo_rectangle_t *));
163
        if (unlikely (new_elements == NULL))
164
            return _cairo_error (CAIRO_STATUS_NO_MEMORY);
165
 
166
        memcpy (new_elements, pq->elements_embedded,
167
                sizeof (pq->elements_embedded));
168
    } else {
169
        new_elements = _cairo_realloc_ab (pq->elements,
170
                                          pq->max_size,
171
                                          sizeof (cairo_bo_rectangle_t *));
172
        if (unlikely (new_elements == NULL))
173
            return _cairo_error (CAIRO_STATUS_NO_MEMORY);
174
    }
175
 
176
    pq->elements = new_elements;
177
    return CAIRO_STATUS_SUCCESS;
178
}
179
 
180
static inline cairo_status_t
181
_pqueue_push (pqueue_t *pq, cairo_bo_rectangle_t *rectangle)
182
{
183
    cairo_bo_rectangle_t **elements;
184
    int i, parent;
185
 
186
    if (unlikely (pq->size + 1 == pq->max_size)) {
187
        cairo_status_t status;
188
 
189
        status = _pqueue_grow (pq);
190
        if (unlikely (status))
191
            return status;
192
    }
193
 
194
    elements = pq->elements;
195
 
196
    for (i = ++pq->size;
197
         i != PQ_FIRST_ENTRY &&
198
         _cairo_bo_rectangle_compare_stop (rectangle,
199
                                           elements[parent = PQ_PARENT_INDEX (i)]) < 0;
200
         i = parent)
201
    {
202
        elements[i] = elements[parent];
203
    }
204
 
205
    elements[i] = rectangle;
206
 
207
    return CAIRO_STATUS_SUCCESS;
208
}
209
 
210
static inline void
211
_pqueue_pop (pqueue_t *pq)
212
{
213
    cairo_bo_rectangle_t **elements = pq->elements;
214
    cairo_bo_rectangle_t *tail;
215
    int child, i;
216
 
217
    tail = elements[pq->size--];
218
    if (pq->size == 0) {
219
        elements[PQ_FIRST_ENTRY] = NULL;
220
        return;
221
    }
222
 
223
    for (i = PQ_FIRST_ENTRY;
224
         (child = PQ_LEFT_CHILD_INDEX (i)) <= pq->size;
225
         i = child)
226
    {
227
        if (child != pq->size &&
228
            _cairo_bo_rectangle_compare_stop (elements[child+1],
229
                                              elements[child]) < 0)
230
        {
231
            child++;
232
        }
233
 
234
        if (_cairo_bo_rectangle_compare_stop (elements[child], tail) >= 0)
235
            break;
236
 
237
        elements[i] = elements[child];
238
    }
239
    elements[i] = tail;
240
}
241
 
242
static inline cairo_bo_rectangle_t *
243
_cairo_bo_rectangle_pop_start (cairo_bo_sweep_line_t *sweep_line)
244
{
245
    return *sweep_line->rectangles++;
246
}
247
 
248
static inline cairo_bo_rectangle_t *
249
_cairo_bo_rectangle_peek_stop (cairo_bo_sweep_line_t *sweep_line)
250
{
251
    return sweep_line->stop.elements[PQ_FIRST_ENTRY];
252
}
253
 
254
CAIRO_COMBSORT_DECLARE (_cairo_bo_rectangle_sort,
255
                        cairo_bo_rectangle_t *,
256
                        cairo_bo_rectangle_compare_start)
257
 
258
static void
259
_cairo_bo_sweep_line_init (cairo_bo_sweep_line_t *sweep_line,
260
                           cairo_bo_rectangle_t **rectangles,
261
                           int                    num_rectangles)
262
{
263
    _cairo_bo_rectangle_sort (rectangles, num_rectangles);
264
    rectangles[num_rectangles] = NULL;
265
    sweep_line->rectangles = rectangles;
266
 
267
    cairo_list_init (&sweep_line->sweep);
268
    sweep_line->current_left = &sweep_line->sweep;
269
    sweep_line->current_right = &sweep_line->sweep;
270
    sweep_line->current_y = INT32_MIN;
271
    sweep_line->last_y = INT32_MIN;
272
 
273
    _pqueue_init (&sweep_line->stop);
274
}
275
 
276
static void
277
_cairo_bo_sweep_line_fini (cairo_bo_sweep_line_t *sweep_line)
278
{
279
    _pqueue_fini (&sweep_line->stop);
280
}
281
 
282
static inline cairo_bo_edge_t *
283
link_to_edge (cairo_list_t *elt)
284
{
285
    return cairo_container_of (elt, cairo_bo_edge_t, link);
286
}
287
 
288
static cairo_status_t
289
_cairo_bo_edge_end_trap (cairo_bo_edge_t        *left,
290
                         int32_t                 bot,
291
                         cairo_traps_t          *traps)
292
{
293
    cairo_bo_trap_t *trap = &left->deferred_trap;
294
 
295
    /* Only emit (trivial) non-degenerate trapezoids with positive height. */
296
    if (likely (trap->top < bot)) {
297
        cairo_line_t _left = {
298
            { left->x, trap->top },
299
            { left->x, bot },
300
        }, _right = {
301
            { trap->right->x, trap->top },
302
            { trap->right->x, bot },
303
        };
304
        _cairo_traps_add_trap (traps, trap->top, bot, &_left, &_right);
305
    }
306
 
307
    trap->right = NULL;
308
 
309
    return _cairo_traps_status (traps);
310
}
311
 
312
/* Start a new trapezoid at the given top y coordinate, whose edges
313
 * are `edge' and `edge->next'. If `edge' already has a trapezoid,
314
 * then either add it to the traps in `traps', if the trapezoid's
315
 * right edge differs from `edge->next', or do nothing if the new
316
 * trapezoid would be a continuation of the existing one. */
317
static inline cairo_status_t
318
_cairo_bo_edge_start_or_continue_trap (cairo_bo_edge_t      *left,
319
                                       cairo_bo_edge_t      *right,
320
                                       int                   top,
321
                                       cairo_traps_t        *traps)
322
{
323
    cairo_status_t status;
324
 
325
    if (left->deferred_trap.right == right)
326
        return CAIRO_STATUS_SUCCESS;
327
 
328
    if (left->deferred_trap.right != NULL) {
329
        if (right != NULL && left->deferred_trap.right->x == right->x) {
330
            /* continuation on right, so just swap edges */
331
            left->deferred_trap.right = right;
332
            return CAIRO_STATUS_SUCCESS;
333
        }
334
 
335
        status = _cairo_bo_edge_end_trap (left, top, traps);
336
        if (unlikely (status))
337
            return status;
338
    }
339
 
340
    if (right != NULL && left->x != right->x) {
341
        left->deferred_trap.top = top;
342
        left->deferred_trap.right = right;
343
    }
344
 
345
    return CAIRO_STATUS_SUCCESS;
346
}
347
 
348
static inline cairo_status_t
349
_active_edges_to_traps (cairo_bo_sweep_line_t   *sweep,
350
                        cairo_fill_rule_t        fill_rule,
351
                        cairo_traps_t           *traps)
352
{
353
    int top = sweep->current_y;
354
    cairo_list_t *pos = &sweep->sweep;
355
    cairo_status_t status;
356
 
357
    if (sweep->last_y == sweep->current_y)
358
        return CAIRO_STATUS_SUCCESS;
359
 
360
    if (fill_rule == CAIRO_FILL_RULE_WINDING) {
361
        do {
362
            cairo_bo_edge_t *left, *right;
363
            int in_out;
364
 
365
            pos = pos->next;
366
            if (pos == &sweep->sweep)
367
                break;
368
 
369
            left = link_to_edge (pos);
370
            in_out = left->dir;
371
 
372
            /* Check if there is a co-linear edge with an existing trap */
373
            if (left->deferred_trap.right == NULL) {
374
                right = link_to_edge (pos->next);
375
                while (unlikely (right->x == left->x)) {
376
                    if (right->deferred_trap.right != NULL) {
377
                        /* continuation on left */
378
                        left->deferred_trap = right->deferred_trap;
379
                        right->deferred_trap.right = NULL;
380
                        break;
381
                    }
382
 
383
                    right = link_to_edge (right->link.next);
384
                }
385
            }
386
 
387
            /* Greedily search for the closing edge, so that we generate the
388
             * maximal span width with the minimal number of trapezoids.
389
             */
390
 
391
            right = link_to_edge (left->link.next);
392
            do {
393
                /* End all subsumed traps */
394
                if (right->deferred_trap.right != NULL) {
395
                    status = _cairo_bo_edge_end_trap (right, top, traps);
396
                    if (unlikely (status))
397
                        return status;
398
                }
399
 
400
                in_out += right->dir;
401
                if (in_out == 0) {
402
                    /* skip co-linear edges */
403
                    if (likely (right->link.next == &sweep->sweep ||
404
                                right->x != link_to_edge (right->link.next)->x))
405
                    {
406
                        break;
407
                    }
408
                }
409
 
410
                right = link_to_edge (right->link.next);
411
            } while (TRUE);
412
 
413
            status = _cairo_bo_edge_start_or_continue_trap (left, right,
414
                                                            top, traps);
415
            if (unlikely (status))
416
                return status;
417
 
418
            pos = &right->link;
419
        } while (TRUE);
420
    } else {
421
        cairo_bo_edge_t *left, *right;
422
        do {
423
            int in_out = 0;
424
 
425
            pos = pos->next;
426
            if (pos == &sweep->sweep)
427
                break;
428
 
429
            left = link_to_edge (pos);
430
 
431
            pos = pos->next;
432
            do {
433
                right = link_to_edge (pos);
434
                if (right->deferred_trap.right != NULL) {
435
                    status = _cairo_bo_edge_end_trap (right, top, traps);
436
                    if (unlikely (status))
437
                        return status;
438
                }
439
 
440
                if ((in_out++ & 1) == 0) {
441
                    cairo_list_t *next;
442
                    cairo_bool_t skip = FALSE;
443
 
444
                    /* skip co-linear edges */
445
                    next = pos->next;
446
                    if (next != &sweep->sweep)
447
                        skip = right->x == link_to_edge (next)->x;
448
 
449
                    if (! skip)
450
                        break;
451
                }
452
                pos = pos->next;
453
            } while (TRUE);
454
 
455
            right = pos == &sweep->sweep ? NULL : link_to_edge (pos);
456
            status = _cairo_bo_edge_start_or_continue_trap (left, right,
457
                                                            top, traps);
458
            if (unlikely (status))
459
                return status;
460
        } while (right != NULL);
461
    }
462
 
463
    sweep->last_y = sweep->current_y;
464
    return CAIRO_STATUS_SUCCESS;
465
}
466
 
467
static inline cairo_status_t
468
_cairo_bo_sweep_line_delete_edge (cairo_bo_sweep_line_t *sweep_line,
469
                                  cairo_bo_edge_t *edge,
470
                                  cairo_traps_t *traps)
471
{
472
    if (edge->deferred_trap.right != NULL) {
473
        cairo_bo_edge_t *next = link_to_edge (edge->link.next);
474
        if (&next->link != &sweep_line->sweep && next->x == edge->x) {
475
            next->deferred_trap = edge->deferred_trap;
476
        } else {
477
            cairo_status_t status;
478
 
479
            status = _cairo_bo_edge_end_trap (edge,
480
                                              sweep_line->current_y,
481
                                              traps);
482
            if (unlikely (status))
483
                return status;
484
        }
485
    }
486
 
487
    if (sweep_line->current_left == &edge->link)
488
        sweep_line->current_left = edge->link.prev;
489
 
490
    if (sweep_line->current_right == &edge->link)
491
        sweep_line->current_right = edge->link.next;
492
 
493
    cairo_list_del (&edge->link);
494
 
495
    return CAIRO_STATUS_SUCCESS;
496
}
497
 
498
static inline cairo_status_t
499
_cairo_bo_sweep_line_delete (cairo_bo_sweep_line_t      *sweep_line,
500
                             cairo_bo_rectangle_t       *rectangle,
501
                             cairo_fill_rule_t           fill_rule,
502
                             cairo_traps_t              *traps)
503
{
504
    cairo_status_t status;
505
 
506
    if (rectangle->bottom != sweep_line->current_y) {
507
        status = _active_edges_to_traps (sweep_line, fill_rule, traps);
508
        if (unlikely (status))
509
            return status;
510
 
511
        sweep_line->current_y = rectangle->bottom;
512
    }
513
 
514
    status = _cairo_bo_sweep_line_delete_edge (sweep_line,
515
                                               &rectangle->left,
516
                                               traps);
517
    if (unlikely (status))
518
        return status;
519
 
520
    status = _cairo_bo_sweep_line_delete_edge (sweep_line,
521
                                               &rectangle->right,
522
                                               traps);
523
    if (unlikely (status))
524
        return status;
525
 
526
    _pqueue_pop (&sweep_line->stop);
527
    return CAIRO_STATUS_SUCCESS;
528
}
529
 
530
static cairo_bool_t
531
validate_sweep_line (cairo_bo_sweep_line_t *sweep_line)
532
{
533
    int32_t last_x = INT32_MIN;
534
    cairo_bo_edge_t *edge;
535
    cairo_list_foreach_entry (edge, cairo_bo_edge_t, &sweep_line->sweep, link) {
536
        if (edge->x < last_x)
537
            return FALSE;
538
        last_x = edge->x;
539
    }
540
    return TRUE;
541
}
542
static inline cairo_status_t
543
_cairo_bo_sweep_line_insert (cairo_bo_sweep_line_t      *sweep_line,
544
                             cairo_bo_rectangle_t       *rectangle,
545
                             cairo_fill_rule_t           fill_rule,
546
                             cairo_traps_t              *traps)
547
{
548
    cairo_list_t *pos;
549
    cairo_status_t status;
550
 
551
    if (rectangle->top != sweep_line->current_y) {
552
        cairo_bo_rectangle_t *stop;
553
 
554
        stop = _cairo_bo_rectangle_peek_stop (sweep_line);
555
        while (stop != NULL && stop->bottom < rectangle->top) {
556
            status = _cairo_bo_sweep_line_delete (sweep_line, stop,
557
                                                  fill_rule, traps);
558
            if (unlikely (status))
559
                return status;
560
 
561
            stop = _cairo_bo_rectangle_peek_stop (sweep_line);
562
        }
563
 
564
        status = _active_edges_to_traps (sweep_line, fill_rule, traps);
565
        if (unlikely (status))
566
            return status;
567
 
568
        sweep_line->current_y = rectangle->top;
569
    }
570
 
571
    /* right edge */
572
    pos = sweep_line->current_right;
573
    if (pos == &sweep_line->sweep)
574
        pos = sweep_line->sweep.prev;
575
    if (pos != &sweep_line->sweep) {
576
        int cmp;
577
 
578
        cmp = link_to_edge (pos)->x - rectangle->right.x;
579
        if (cmp < 0) {
580
            while (pos->next != &sweep_line->sweep &&
581
                   link_to_edge (pos->next)->x - rectangle->right.x < 0)
582
            {
583
                pos = pos->next;
584
            }
585
        } else if (cmp > 0) {
586
            do {
587
                pos = pos->prev;
588
            } while (pos != &sweep_line->sweep &&
589
                     link_to_edge (pos)->x - rectangle->right.x > 0);
590
        }
591
 
592
        cairo_list_add (&rectangle->right.link, pos);
593
    } else {
594
        cairo_list_add_tail (&rectangle->right.link, pos);
595
    }
596
    sweep_line->current_right = &rectangle->right.link;
597
    assert (validate_sweep_line (sweep_line));
598
 
599
    /* left edge */
600
    pos = sweep_line->current_left;
601
    if (pos == &sweep_line->sweep)
602
        pos = sweep_line->sweep.next;
603
    if (pos != &sweep_line->sweep) {
604
        int cmp;
605
 
606
        if (link_to_edge (pos)->x >= rectangle->right.x) {
607
            pos = rectangle->right.link.prev;
608
            if (pos == &sweep_line->sweep)
609
                goto left_done;
610
        }
611
 
612
        cmp = link_to_edge (pos)->x - rectangle->left.x;
613
        if (cmp < 0) {
614
            while (pos->next != &sweep_line->sweep &&
615
                   link_to_edge (pos->next)->x - rectangle->left.x < 0)
616
            {
617
                pos = pos->next;
618
            }
619
        } else if (cmp > 0) {
620
            do {
621
                pos = pos->prev;
622
            } while (pos != &sweep_line->sweep &&
623
                    link_to_edge (pos)->x - rectangle->left.x > 0);
624
        }
625
    }
626
  left_done:
627
    cairo_list_add (&rectangle->left.link, pos);
628
    sweep_line->current_left = &rectangle->left.link;
629
    assert (validate_sweep_line (sweep_line));
630
 
631
    return _pqueue_push (&sweep_line->stop, rectangle);
632
}
633
 
634
static cairo_status_t
635
_cairo_bentley_ottmann_tessellate_rectangular (cairo_bo_rectangle_t     **rectangles,
636
                                               int                        num_rectangles,
637
                                               cairo_fill_rule_t          fill_rule,
638
                                               cairo_traps_t             *traps)
639
{
640
    cairo_bo_sweep_line_t sweep_line;
641
    cairo_bo_rectangle_t *rectangle;
642
    cairo_status_t status = CAIRO_STATUS_SUCCESS;
643
 
644
    _cairo_bo_sweep_line_init (&sweep_line, rectangles, num_rectangles);
645
 
646
    while ((rectangle = _cairo_bo_rectangle_pop_start (&sweep_line)) != NULL) {
647
        status = _cairo_bo_sweep_line_insert (&sweep_line, rectangle,
648
                                              fill_rule, traps);
649
        if (unlikely (status))
650
            goto BAIL;
651
    }
652
 
653
    while ((rectangle = _cairo_bo_rectangle_peek_stop (&sweep_line)) != NULL) {
654
        status = _cairo_bo_sweep_line_delete (&sweep_line, rectangle,
655
                                              fill_rule, traps);
656
        if (unlikely (status))
657
            goto BAIL;
658
    }
659
 
660
BAIL:
661
    _cairo_bo_sweep_line_fini (&sweep_line);
662
    return status;
663
}
664
 
665
cairo_status_t
666
_cairo_bentley_ottmann_tessellate_rectangular_traps (cairo_traps_t *traps,
667
                                                     cairo_fill_rule_t fill_rule)
668
{
669
    cairo_bo_rectangle_t stack_rectangles[CAIRO_STACK_ARRAY_LENGTH (cairo_bo_rectangle_t)];
670
    cairo_bo_rectangle_t *rectangles;
671
    cairo_bo_rectangle_t *stack_rectangles_ptrs[ARRAY_LENGTH (stack_rectangles) + 1];
672
    cairo_bo_rectangle_t **rectangles_ptrs;
673
    cairo_status_t status;
674
    int i;
675
 
676
    if (unlikely (traps->num_traps == 0))
677
        return CAIRO_STATUS_SUCCESS;
678
 
679
    assert (traps->is_rectangular);
680
 
681
    dump_traps (traps, "bo-rects-traps-in.txt");
682
 
683
    rectangles = stack_rectangles;
684
    rectangles_ptrs = stack_rectangles_ptrs;
685
    if (traps->num_traps > ARRAY_LENGTH (stack_rectangles)) {
686
        rectangles = _cairo_malloc_ab_plus_c (traps->num_traps,
687
                                          sizeof (cairo_bo_rectangle_t) +
688
                                          sizeof (cairo_bo_rectangle_t *),
689
                                          sizeof (cairo_bo_rectangle_t *));
690
        if (unlikely (rectangles == NULL))
691
            return _cairo_error (CAIRO_STATUS_NO_MEMORY);
692
 
693
        rectangles_ptrs = (cairo_bo_rectangle_t **) (rectangles + traps->num_traps);
694
    }
695
 
696
    for (i = 0; i < traps->num_traps; i++) {
697
        if (traps->traps[i].left.p1.x < traps->traps[i].right.p1.x) {
698
            rectangles[i].left.x = traps->traps[i].left.p1.x;
699
            rectangles[i].left.dir = 1;
700
 
701
            rectangles[i].right.x = traps->traps[i].right.p1.x;
702
            rectangles[i].right.dir = -1;
703
        } else {
704
            rectangles[i].right.x = traps->traps[i].left.p1.x;
705
            rectangles[i].right.dir = 1;
706
 
707
            rectangles[i].left.x = traps->traps[i].right.p1.x;
708
            rectangles[i].left.dir = -1;
709
        }
710
 
711
        rectangles[i].left.deferred_trap.right = NULL;
712
        cairo_list_init (&rectangles[i].left.link);
713
 
714
        rectangles[i].right.deferred_trap.right = NULL;
715
        cairo_list_init (&rectangles[i].right.link);
716
 
717
        rectangles[i].top = traps->traps[i].top;
718
        rectangles[i].bottom = traps->traps[i].bottom;
719
 
720
        rectangles_ptrs[i] = &rectangles[i];
721
    }
722
 
723
    _cairo_traps_clear (traps);
724
    status = _cairo_bentley_ottmann_tessellate_rectangular (rectangles_ptrs, i,
725
                                                            fill_rule,
726
                                                            traps);
727
    traps->is_rectilinear = TRUE;
728
    traps->is_rectangular = TRUE;
729
 
730
    if (rectangles != stack_rectangles)
731
        free (rectangles);
732
 
733
    dump_traps (traps, "bo-rects-traps-out.txt");
734
 
735
 
736
    return status;
737
}