Line data Source code
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
16 : * Foundation, Inc., 51 Franklin Street, Suite 500, Boston, MA 02110-1335, USA
17 : * You should have received a copy of the MPL along with this library
18 : * in the file COPYING-MPL-1.1
19 : *
20 : * The contents of this file are subject to the Mozilla Public License
21 : * Version 1.1 (the "License"); you may not use this file except in
22 : * compliance with the License. You may obtain a copy of the License at
23 : * http://www.mozilla.org/MPL/
24 : *
25 : * This software is distributed on an "AS IS" basis, WITHOUT WARRANTY
26 : * OF ANY KIND, either express or implied. See the LGPL or the MPL for
27 : * the specific language governing rights and limitations.
28 : *
29 : * The Original Code is the cairo graphics library.
30 : *
31 : * The Initial Developer of the Original Code is Carl Worth
32 : *
33 : * Contributor(s):
34 : * Carl D. Worth <cworth@cworth.org>
35 : * Chris Wilson <chris@chris-wilson.co.uk>
36 : */
37 :
38 : /* Provide definitions for standalone compilation */
39 : #include "cairoint.h"
40 :
41 : #include "cairo-boxes-private.h"
42 : #include "cairo-error-private.h"
43 : #include "cairo-combsort-private.h"
44 : #include "cairo-list-private.h"
45 :
46 : #include <setjmp.h>
47 :
48 : typedef struct _rectangle rectangle_t;
49 : typedef struct _edge edge_t;
50 :
51 : struct _edge {
52 : edge_t *next, *prev;
53 : edge_t *right;
54 : cairo_fixed_t x, top;
55 : int dir;
56 : };
57 :
58 : struct _rectangle {
59 : edge_t left, right;
60 : int32_t top, bottom;
61 : };
62 :
63 : #define UNROLL3(x) x x x
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 : rectangle_t **elements;
76 : rectangle_t *elements_embedded[1024];
77 : } pqueue_t;
78 :
79 : typedef struct _sweep_line {
80 : rectangle_t **rectangles;
81 : pqueue_t pq;
82 : edge_t head, tail;
83 : edge_t *insert_left, *insert_right;
84 : int32_t current_y;
85 : int32_t last_y;
86 :
87 : cairo_fill_rule_t fill_rule;
88 :
89 : jmp_buf unwind;
90 : } sweep_line_t;
91 :
92 : #define DEBUG_TRAPS 0
93 :
94 : #if DEBUG_TRAPS
95 : static void
96 : dump_traps (cairo_traps_t *traps, const char *filename)
97 : {
98 : FILE *file;
99 : int n;
100 :
101 : if (getenv ("CAIRO_DEBUG_TRAPS") == NULL)
102 : return;
103 :
104 : file = fopen (filename, "a");
105 : if (file != NULL) {
106 : for (n = 0; n < traps->num_traps; n++) {
107 : fprintf (file, "%d %d L:(%d, %d), (%d, %d) R:(%d, %d), (%d, %d)\n",
108 : traps->traps[n].top,
109 : traps->traps[n].bottom,
110 : traps->traps[n].left.p1.x,
111 : traps->traps[n].left.p1.y,
112 : traps->traps[n].left.p2.x,
113 : traps->traps[n].left.p2.y,
114 : traps->traps[n].right.p1.x,
115 : traps->traps[n].right.p1.y,
116 : traps->traps[n].right.p2.x,
117 : traps->traps[n].right.p2.y);
118 : }
119 : fprintf (file, "\n");
120 : fclose (file);
121 : }
122 : }
123 : #else
124 : #define dump_traps(traps, filename)
125 : #endif
126 :
127 : static inline int
128 0 : rectangle_compare_start (const rectangle_t *a,
129 : const rectangle_t *b)
130 : {
131 0 : return a->top - b->top;
132 : }
133 :
134 : static inline int
135 0 : rectangle_compare_stop (const rectangle_t *a,
136 : const rectangle_t *b)
137 : {
138 0 : return a->bottom - b->bottom;
139 : }
140 :
141 : static inline void
142 0 : pqueue_init (pqueue_t *pq)
143 : {
144 0 : pq->max_size = ARRAY_LENGTH (pq->elements_embedded);
145 0 : pq->size = 0;
146 :
147 0 : pq->elements = pq->elements_embedded;
148 0 : pq->elements[PQ_FIRST_ENTRY] = NULL;
149 0 : }
150 :
151 : static inline void
152 0 : pqueue_fini (pqueue_t *pq)
153 : {
154 0 : if (pq->elements != pq->elements_embedded)
155 0 : free (pq->elements);
156 0 : }
157 :
158 : static cairo_bool_t
159 0 : pqueue_grow (pqueue_t *pq)
160 : {
161 : rectangle_t **new_elements;
162 0 : pq->max_size *= 2;
163 :
164 0 : if (pq->elements == pq->elements_embedded) {
165 0 : new_elements = _cairo_malloc_ab (pq->max_size,
166 : sizeof (rectangle_t *));
167 0 : if (unlikely (new_elements == NULL))
168 0 : return FALSE;
169 :
170 0 : memcpy (new_elements, pq->elements_embedded,
171 : sizeof (pq->elements_embedded));
172 : } else {
173 0 : new_elements = _cairo_realloc_ab (pq->elements,
174 : pq->max_size,
175 : sizeof (rectangle_t *));
176 0 : if (unlikely (new_elements == NULL))
177 0 : return FALSE;
178 : }
179 :
180 0 : pq->elements = new_elements;
181 0 : return TRUE;
182 : }
183 :
184 : static inline void
185 0 : pqueue_push (sweep_line_t *sweep, rectangle_t *rectangle)
186 : {
187 : rectangle_t **elements;
188 : int i, parent;
189 :
190 0 : if (unlikely (sweep->pq.size + 1 == sweep->pq.max_size)) {
191 0 : if (unlikely (! pqueue_grow (&sweep->pq))) {
192 0 : longjmp (sweep->unwind,
193 0 : _cairo_error (CAIRO_STATUS_NO_MEMORY));
194 : }
195 : }
196 :
197 0 : elements = sweep->pq.elements;
198 0 : for (i = ++sweep->pq.size;
199 0 : i != PQ_FIRST_ENTRY &&
200 0 : rectangle_compare_stop (rectangle,
201 0 : elements[parent = PQ_PARENT_INDEX (i)]) < 0;
202 0 : i = parent)
203 : {
204 0 : elements[i] = elements[parent];
205 : }
206 :
207 0 : elements[i] = rectangle;
208 0 : }
209 :
210 : static inline void
211 0 : pqueue_pop (pqueue_t *pq)
212 : {
213 0 : rectangle_t **elements = pq->elements;
214 : rectangle_t *tail;
215 : int child, i;
216 :
217 0 : tail = elements[pq->size--];
218 0 : if (pq->size == 0) {
219 0 : elements[PQ_FIRST_ENTRY] = NULL;
220 0 : return;
221 : }
222 :
223 0 : for (i = PQ_FIRST_ENTRY;
224 0 : (child = PQ_LEFT_CHILD_INDEX (i)) <= pq->size;
225 0 : i = child)
226 : {
227 0 : if (child != pq->size &&
228 0 : rectangle_compare_stop (elements[child+1],
229 0 : elements[child]) < 0)
230 : {
231 0 : child++;
232 : }
233 :
234 0 : if (rectangle_compare_stop (elements[child], tail) >= 0)
235 0 : break;
236 :
237 0 : elements[i] = elements[child];
238 : }
239 0 : elements[i] = tail;
240 : }
241 :
242 : static inline rectangle_t *
243 0 : rectangle_pop_start (sweep_line_t *sweep_line)
244 : {
245 0 : return *sweep_line->rectangles++;
246 : }
247 :
248 : static inline rectangle_t *
249 0 : rectangle_peek_stop (sweep_line_t *sweep_line)
250 : {
251 0 : return sweep_line->pq.elements[PQ_FIRST_ENTRY];
252 : }
253 :
254 0 : CAIRO_COMBSORT_DECLARE (_rectangle_sort,
255 : rectangle_t *,
256 : rectangle_compare_start)
257 :
258 : static void
259 0 : sweep_line_init (sweep_line_t *sweep_line,
260 : rectangle_t **rectangles,
261 : int num_rectangles,
262 : cairo_fill_rule_t fill_rule)
263 : {
264 0 : _rectangle_sort (rectangles, num_rectangles);
265 0 : rectangles[num_rectangles] = NULL;
266 0 : sweep_line->rectangles = rectangles;
267 :
268 0 : sweep_line->head.x = INT32_MIN;
269 0 : sweep_line->head.right = NULL;
270 0 : sweep_line->head.dir = 0;
271 0 : sweep_line->head.next = &sweep_line->tail;
272 : /* we need to initialize prev so that we can check
273 : * if this edge is the left most and make sure
274 : * we always insert to the right of it, even if
275 : * our x coordinate matches */
276 0 : sweep_line->head.prev = NULL;
277 :
278 0 : sweep_line->tail.x = INT32_MAX;
279 0 : sweep_line->tail.right = NULL;
280 0 : sweep_line->tail.dir = 0;
281 0 : sweep_line->tail.prev = &sweep_line->head;
282 0 : sweep_line->tail.next = NULL;
283 :
284 0 : sweep_line->insert_left = &sweep_line->tail;
285 0 : sweep_line->insert_right = &sweep_line->tail;
286 :
287 0 : sweep_line->current_y = INT32_MIN;
288 0 : sweep_line->last_y = INT32_MIN;
289 :
290 0 : sweep_line->fill_rule = fill_rule;
291 :
292 0 : pqueue_init (&sweep_line->pq);
293 0 : }
294 :
295 : static void
296 0 : sweep_line_fini (sweep_line_t *sweep_line)
297 : {
298 0 : pqueue_fini (&sweep_line->pq);
299 0 : }
300 :
301 : static void
302 0 : edge_end_box (sweep_line_t *sweep_line,
303 : edge_t *left,
304 : int32_t bot,
305 : cairo_bool_t do_traps,
306 : void *container)
307 : {
308 0 : cairo_status_t status = CAIRO_STATUS_SUCCESS;
309 :
310 : /* Only emit (trivial) non-degenerate trapezoids with positive height. */
311 0 : if (likely (left->top < bot)) {
312 0 : if (do_traps) {
313 0 : cairo_line_t _left = {
314 0 : { left->x, left->top },
315 0 : { left->x, bot },
316 0 : }, _right = {
317 0 : { left->right->x, left->top },
318 0 : { left->right->x, bot },
319 : };
320 0 : _cairo_traps_add_trap (container, left->top, bot, &_left, &_right);
321 0 : status = _cairo_traps_status ((cairo_traps_t *) container);
322 : } else {
323 : cairo_box_t box;
324 :
325 0 : box.p1.x = left->x;
326 0 : box.p1.y = left->top;
327 0 : box.p2.x = left->right->x;
328 0 : box.p2.y = bot;
329 :
330 0 : status = _cairo_boxes_add (container, &box);
331 : }
332 : }
333 0 : if (unlikely (status))
334 0 : longjmp (sweep_line->unwind, status);
335 :
336 0 : left->right = NULL;
337 0 : }
338 :
339 : /* Start a new trapezoid at the given top y coordinate, whose edges
340 : * are `edge' and `edge->next'. If `edge' already has a trapezoid,
341 : * then either add it to the traps in `traps', if the trapezoid's
342 : * right edge differs from `edge->next', or do nothing if the new
343 : * trapezoid would be a continuation of the existing one. */
344 : static inline void
345 0 : edge_start_or_continue_box (sweep_line_t *sweep_line,
346 : edge_t *left,
347 : edge_t *right,
348 : int top,
349 : cairo_bool_t do_traps,
350 : void *container)
351 : {
352 0 : if (left->right == right)
353 0 : return;
354 :
355 0 : if (left->right != NULL) {
356 0 : if (right != NULL && left->right->x == right->x) {
357 : /* continuation on right, so just swap edges */
358 0 : left->right = right;
359 0 : return;
360 : }
361 :
362 0 : edge_end_box (sweep_line,
363 : left, top, do_traps, container);
364 : }
365 :
366 0 : if (right != NULL && left->x != right->x) {
367 0 : left->top = top;
368 0 : left->right = right;
369 : }
370 : }
371 :
372 : static inline void
373 0 : active_edges_to_traps (sweep_line_t *sweep,
374 : cairo_bool_t do_traps,
375 : void *container)
376 : {
377 0 : int top = sweep->current_y;
378 : edge_t *pos;
379 :
380 0 : if (sweep->last_y == sweep->current_y)
381 0 : return;
382 :
383 0 : pos = sweep->head.next;
384 0 : if (pos == &sweep->tail)
385 0 : return;
386 :
387 0 : if (sweep->fill_rule == CAIRO_FILL_RULE_WINDING) {
388 : do {
389 : edge_t *left, *right;
390 : int winding;
391 :
392 0 : left = pos;
393 0 : winding = left->dir;
394 :
395 0 : right = left->next;
396 :
397 : /* Check if there is a co-linear edge with an existing trap */
398 0 : if (left->right == NULL) {
399 0 : while (unlikely (right->x == left->x)) {
400 0 : winding += right->dir;
401 0 : if (right->right != NULL) {
402 : /* continuation on left */
403 0 : left->top = right->top;
404 0 : left->right = right->right;
405 0 : right->right = NULL;
406 0 : winding -= right->dir;
407 0 : break;
408 : }
409 :
410 0 : right = right->next;
411 : }
412 :
413 0 : if (winding == 0) {
414 0 : pos = right;
415 0 : continue;
416 : }
417 : }
418 :
419 : /* Greedily search for the closing edge, so that we generate the
420 : * maximal span width with the minimal number of trapezoids.
421 : */
422 :
423 : do {
424 : /* End all subsumed traps */
425 0 : if (unlikely (right->right != NULL)) {
426 0 : edge_end_box (sweep,
427 : right, top, do_traps, container);
428 : }
429 :
430 0 : winding += right->dir;
431 0 : if (winding == 0) {
432 : /* skip co-linear edges */
433 0 : if (likely (right->x != right->next->x))
434 0 : break;
435 : }
436 :
437 0 : right = right->next;
438 : } while (TRUE);
439 :
440 0 : edge_start_or_continue_box (sweep,
441 : left, right, top,
442 : do_traps, container);
443 :
444 0 : pos = right->next;
445 0 : } while (pos != &sweep->tail);
446 : } else {
447 : do {
448 0 : edge_t *right = pos->next;
449 0 : int count = 0;
450 :
451 : do {
452 : /* End all subsumed traps */
453 0 : if (unlikely (right->right != NULL)) {
454 0 : edge_end_box (sweep,
455 : right, top, do_traps, container);
456 : }
457 :
458 0 : if (++count & 1) {
459 : /* skip co-linear edges */
460 0 : if (likely (right->x != right->next->x))
461 0 : break;
462 : }
463 :
464 0 : right = right->next;
465 : } while (TRUE);
466 :
467 0 : edge_start_or_continue_box (sweep,
468 : pos, right, top,
469 : do_traps, container);
470 :
471 0 : pos = right->next;
472 0 : } while (pos != &sweep->tail);
473 : }
474 :
475 0 : sweep->last_y = sweep->current_y;
476 : }
477 :
478 : static inline void
479 0 : sweep_line_delete_edge (sweep_line_t *sweep_line,
480 : edge_t *edge,
481 : cairo_bool_t do_traps,
482 : void *container)
483 : {
484 0 : if (edge->right != NULL) {
485 0 : edge_t *next = edge->next;
486 0 : if (next->x == edge->x) {
487 0 : next->top = edge->top;
488 0 : next->right = edge->right;
489 : } else {
490 0 : edge_end_box (sweep_line,
491 : edge,
492 : sweep_line->current_y,
493 : do_traps, container);
494 : }
495 : }
496 :
497 0 : if (sweep_line->insert_left == edge)
498 0 : sweep_line->insert_left = edge->next;
499 0 : if (sweep_line->insert_right == edge)
500 0 : sweep_line->insert_right = edge->next;
501 :
502 0 : edge->prev->next = edge->next;
503 0 : edge->next->prev = edge->prev;
504 0 : }
505 :
506 : static inline cairo_bool_t
507 0 : sweep_line_delete (sweep_line_t *sweep,
508 : rectangle_t *rectangle,
509 : cairo_bool_t do_traps,
510 : void *container)
511 : {
512 : cairo_bool_t update;
513 :
514 0 : update = TRUE;
515 0 : if (sweep->fill_rule == CAIRO_FILL_RULE_WINDING &&
516 0 : rectangle->left.prev->dir == rectangle->left.dir)
517 : {
518 0 : update = rectangle->left.next != &rectangle->right;
519 : }
520 :
521 0 : sweep_line_delete_edge (sweep,
522 : &rectangle->left,
523 : do_traps, container);
524 :
525 0 : sweep_line_delete_edge (sweep,
526 : &rectangle->right,
527 : do_traps, container);
528 :
529 0 : pqueue_pop (&sweep->pq);
530 0 : return update;
531 : }
532 :
533 : static inline void
534 0 : insert_edge (edge_t *edge, edge_t *pos)
535 : {
536 0 : if (pos->x != edge->x) {
537 0 : if (pos->x > edge->x) {
538 : do {
539 0 : UNROLL3({
540 : if (pos->prev->x <= edge->x)
541 : break;
542 : pos = pos->prev;
543 : })
544 : } while (TRUE);
545 : } else {
546 : do {
547 0 : UNROLL3({
548 : pos = pos->next;
549 : if (pos->x >= edge->x)
550 : break;
551 : })
552 : } while (TRUE);
553 : }
554 : }
555 0 : if (pos->prev) {
556 0 : pos->prev->next = edge;
557 0 : edge->prev = pos->prev;
558 0 : edge->next = pos;
559 0 : pos->prev = edge;
560 : } else {
561 : /* we have edge that shares an x coordinate with the left most sentinal.
562 : * instead of inserting before pos and ruining our sentinal we insert after pos. */
563 0 : pos->next->prev = edge;
564 0 : edge->next = pos->next;
565 0 : edge->prev = pos;
566 0 : pos->next = edge;
567 : }
568 0 : }
569 :
570 : static inline cairo_bool_t
571 0 : sweep_line_insert (sweep_line_t *sweep,
572 : rectangle_t *rectangle)
573 : {
574 : edge_t *pos;
575 :
576 : /* right edge */
577 0 : pos = sweep->insert_right;
578 0 : insert_edge (&rectangle->right, pos);
579 0 : sweep->insert_right = &rectangle->right;
580 :
581 : /* left edge */
582 0 : pos = sweep->insert_left;
583 0 : if (pos->x > sweep->insert_right->x)
584 0 : pos = sweep->insert_right->prev;
585 0 : insert_edge (&rectangle->left, pos);
586 0 : sweep->insert_left = &rectangle->left;
587 :
588 0 : pqueue_push (sweep, rectangle);
589 :
590 0 : if (sweep->fill_rule == CAIRO_FILL_RULE_WINDING &&
591 0 : rectangle->left.prev->dir == rectangle->left.dir)
592 : {
593 0 : return rectangle->left.next != &rectangle->right;
594 : }
595 :
596 0 : return TRUE;
597 : }
598 :
599 : static cairo_status_t
600 0 : _cairo_bentley_ottmann_tessellate_rectangular (rectangle_t **rectangles,
601 : int num_rectangles,
602 : cairo_fill_rule_t fill_rule,
603 : cairo_bool_t do_traps,
604 : void *container)
605 : {
606 : sweep_line_t sweep_line;
607 : rectangle_t *rectangle;
608 : cairo_status_t status;
609 0 : cairo_bool_t update = FALSE;
610 :
611 0 : sweep_line_init (&sweep_line, rectangles, num_rectangles, fill_rule);
612 0 : if ((status = setjmp (sweep_line.unwind)))
613 0 : goto unwind;
614 :
615 0 : rectangle = rectangle_pop_start (&sweep_line);
616 : do {
617 0 : if (rectangle->top != sweep_line.current_y) {
618 : rectangle_t *stop;
619 :
620 0 : stop = rectangle_peek_stop (&sweep_line);
621 0 : while (stop != NULL && stop->bottom < rectangle->top) {
622 0 : if (stop->bottom != sweep_line.current_y) {
623 0 : if (update) {
624 0 : active_edges_to_traps (&sweep_line,
625 : do_traps, container);
626 0 : update = FALSE;
627 : }
628 :
629 0 : sweep_line.current_y = stop->bottom;
630 : }
631 :
632 0 : update |= sweep_line_delete (&sweep_line, stop, do_traps, container);
633 :
634 0 : stop = rectangle_peek_stop (&sweep_line);
635 : }
636 :
637 0 : if (update) {
638 0 : active_edges_to_traps (&sweep_line, do_traps, container);
639 0 : update = FALSE;
640 : }
641 :
642 0 : sweep_line.current_y = rectangle->top;
643 : }
644 :
645 0 : update |= sweep_line_insert (&sweep_line, rectangle);
646 0 : } while ((rectangle = rectangle_pop_start (&sweep_line)) != NULL);
647 :
648 0 : while ((rectangle = rectangle_peek_stop (&sweep_line)) != NULL) {
649 0 : if (rectangle->bottom != sweep_line.current_y) {
650 0 : if (update) {
651 0 : active_edges_to_traps (&sweep_line, do_traps, container);
652 0 : update = FALSE;
653 : }
654 :
655 0 : sweep_line.current_y = rectangle->bottom;
656 : }
657 :
658 0 : update |= sweep_line_delete (&sweep_line, rectangle, do_traps, container);
659 : }
660 :
661 : unwind:
662 0 : sweep_line_fini (&sweep_line);
663 0 : return status;
664 : }
665 :
666 : cairo_status_t
667 0 : _cairo_bentley_ottmann_tessellate_rectangular_traps (cairo_traps_t *traps,
668 : cairo_fill_rule_t fill_rule)
669 : {
670 : rectangle_t stack_rectangles[CAIRO_STACK_ARRAY_LENGTH (rectangle_t)];
671 : rectangle_t *rectangles;
672 : rectangle_t *stack_rectangles_ptrs[ARRAY_LENGTH (stack_rectangles) + 1];
673 : rectangle_t **rectangles_ptrs;
674 : cairo_status_t status;
675 : int i;
676 :
677 0 : assert (traps->is_rectangular);
678 :
679 0 : if (unlikely (traps->num_traps <= 1)) {
680 0 : if (traps->num_traps == 1) {
681 0 : cairo_trapezoid_t *trap = traps->traps;
682 0 : if (trap->left.p1.x > trap->right.p1.x) {
683 0 : cairo_line_t tmp = trap->left;
684 0 : trap->left = trap->right;
685 0 : trap->right = tmp;
686 : }
687 : }
688 0 : return CAIRO_STATUS_SUCCESS;
689 : }
690 :
691 : dump_traps (traps, "bo-rects-traps-in.txt");
692 :
693 0 : rectangles = stack_rectangles;
694 0 : rectangles_ptrs = stack_rectangles_ptrs;
695 0 : if (traps->num_traps > ARRAY_LENGTH (stack_rectangles)) {
696 0 : rectangles = _cairo_malloc_ab_plus_c (traps->num_traps,
697 : sizeof (rectangle_t) +
698 : sizeof (rectangle_t *),
699 : sizeof (rectangle_t *));
700 0 : if (unlikely (rectangles == NULL))
701 0 : return _cairo_error (CAIRO_STATUS_NO_MEMORY);
702 :
703 0 : rectangles_ptrs = (rectangle_t **) (rectangles + traps->num_traps);
704 : }
705 :
706 0 : for (i = 0; i < traps->num_traps; i++) {
707 0 : if (traps->traps[i].left.p1.x < traps->traps[i].right.p1.x) {
708 0 : rectangles[i].left.x = traps->traps[i].left.p1.x;
709 0 : rectangles[i].left.dir = 1;
710 :
711 0 : rectangles[i].right.x = traps->traps[i].right.p1.x;
712 0 : rectangles[i].right.dir = -1;
713 : } else {
714 0 : rectangles[i].right.x = traps->traps[i].left.p1.x;
715 0 : rectangles[i].right.dir = 1;
716 :
717 0 : rectangles[i].left.x = traps->traps[i].right.p1.x;
718 0 : rectangles[i].left.dir = -1;
719 : }
720 :
721 0 : rectangles[i].left.right = NULL;
722 0 : rectangles[i].right.right = NULL;
723 :
724 0 : rectangles[i].top = traps->traps[i].top;
725 0 : rectangles[i].bottom = traps->traps[i].bottom;
726 :
727 0 : rectangles_ptrs[i] = &rectangles[i];
728 : }
729 :
730 0 : _cairo_traps_clear (traps);
731 0 : status = _cairo_bentley_ottmann_tessellate_rectangular (rectangles_ptrs, i,
732 : fill_rule,
733 : TRUE, traps);
734 0 : traps->is_rectilinear = TRUE;
735 0 : traps->is_rectangular = TRUE;
736 :
737 0 : if (rectangles != stack_rectangles)
738 0 : free (rectangles);
739 :
740 : dump_traps (traps, "bo-rects-traps-out.txt");
741 :
742 0 : return status;
743 : }
744 :
745 : cairo_status_t
746 0 : _cairo_bentley_ottmann_tessellate_boxes (const cairo_boxes_t *in,
747 : cairo_fill_rule_t fill_rule,
748 : cairo_boxes_t *out)
749 : {
750 : rectangle_t stack_rectangles[CAIRO_STACK_ARRAY_LENGTH (rectangle_t)];
751 : rectangle_t *rectangles;
752 : rectangle_t *stack_rectangles_ptrs[ARRAY_LENGTH (stack_rectangles) + 1];
753 : rectangle_t **rectangles_ptrs;
754 : const struct _cairo_boxes_chunk *chunk;
755 : cairo_status_t status;
756 : int i, j;
757 :
758 0 : if (unlikely (in->num_boxes == 0)) {
759 0 : _cairo_boxes_clear (out);
760 0 : return CAIRO_STATUS_SUCCESS;
761 : }
762 :
763 0 : if (in->num_boxes == 1) {
764 0 : if (in == out) {
765 0 : cairo_box_t *box = &in->chunks.base[0];
766 :
767 0 : if (box->p1.x > box->p2.x) {
768 0 : cairo_fixed_t tmp = box->p1.x;
769 0 : box->p1.x = box->p2.x;
770 0 : box->p2.x = tmp;
771 : }
772 : } else {
773 0 : cairo_box_t box = in->chunks.base[0];
774 :
775 0 : if (box.p1.x > box.p2.x) {
776 0 : cairo_fixed_t tmp = box.p1.x;
777 0 : box.p1.x = box.p2.x;
778 0 : box.p2.x = tmp;
779 : }
780 :
781 0 : _cairo_boxes_clear (out);
782 0 : status = _cairo_boxes_add (out, &box);
783 0 : assert (status == CAIRO_STATUS_SUCCESS);
784 : }
785 0 : return CAIRO_STATUS_SUCCESS;
786 : }
787 :
788 0 : rectangles = stack_rectangles;
789 0 : rectangles_ptrs = stack_rectangles_ptrs;
790 0 : if (in->num_boxes > ARRAY_LENGTH (stack_rectangles)) {
791 0 : rectangles = _cairo_malloc_ab_plus_c (in->num_boxes,
792 : sizeof (rectangle_t) +
793 : sizeof (rectangle_t *),
794 : sizeof (rectangle_t *));
795 0 : if (unlikely (rectangles == NULL))
796 0 : return _cairo_error (CAIRO_STATUS_NO_MEMORY);
797 :
798 0 : rectangles_ptrs = (rectangle_t **) (rectangles + in->num_boxes);
799 : }
800 :
801 0 : j = 0;
802 0 : for (chunk = &in->chunks; chunk != NULL; chunk = chunk->next) {
803 0 : const cairo_box_t *box = chunk->base;
804 0 : for (i = 0; i < chunk->count; i++) {
805 0 : if (box[i].p1.x < box[i].p2.x) {
806 0 : rectangles[j].left.x = box[i].p1.x;
807 0 : rectangles[j].left.dir = 1;
808 :
809 0 : rectangles[j].right.x = box[i].p2.x;
810 0 : rectangles[j].right.dir = -1;
811 : } else {
812 0 : rectangles[j].right.x = box[i].p1.x;
813 0 : rectangles[j].right.dir = 1;
814 :
815 0 : rectangles[j].left.x = box[i].p2.x;
816 0 : rectangles[j].left.dir = -1;
817 : }
818 :
819 0 : rectangles[j].left.right = NULL;
820 0 : rectangles[j].right.right = NULL;
821 :
822 0 : rectangles[j].top = box[i].p1.y;
823 0 : rectangles[j].bottom = box[i].p2.y;
824 :
825 0 : rectangles_ptrs[j] = &rectangles[j];
826 0 : j++;
827 : }
828 : }
829 :
830 0 : _cairo_boxes_clear (out);
831 0 : status = _cairo_bentley_ottmann_tessellate_rectangular (rectangles_ptrs, j,
832 : fill_rule,
833 : FALSE, out);
834 0 : if (rectangles != stack_rectangles)
835 0 : free (rectangles);
836 :
837 0 : return status;
838 : }
|
