Line data Source code
1 : /*
2 : * Copyright © 2004 Carl Worth
3 : * Copyright © 2006 Red Hat, Inc.
4 : * Copyright © 2008 Chris Wilson
5 : *
6 : * This library is free software; you can redistribute it and/or
7 : * modify it either under the terms of the GNU Lesser General Public
8 : * License version 2.1 as published by the Free Software Foundation
9 : * (the "LGPL") or, at your option, under the terms of the Mozilla
10 : * Public License Version 1.1 (the "MPL"). If you do not alter this
11 : * notice, a recipient may use your version of this file under either
12 : * the MPL or the LGPL.
13 : *
14 : * You should have received a copy of the LGPL along with this library
15 : * in the file COPYING-LGPL-2.1; if not, write to the Free Software
16 : * Foundation, Inc., 51 Franklin Street, Suite 500, Boston, MA 02110-1335, USA
17 : * You should have received a copy of the MPL along with this library
18 : * in the file COPYING-MPL-1.1
19 : *
20 : * The contents of this file are subject to the Mozilla Public License
21 : * Version 1.1 (the "License"); you may not use this file except in
22 : * compliance with the License. You may obtain a copy of the License at
23 : * http://www.mozilla.org/MPL/
24 : *
25 : * This software is distributed on an "AS IS" basis, WITHOUT WARRANTY
26 : * OF ANY KIND, either express or implied. See the LGPL or the MPL for
27 : * the specific language governing rights and limitations.
28 : *
29 : * The Original Code is the cairo graphics library.
30 : *
31 : * The Initial Developer of the Original Code is Carl Worth
32 : *
33 : * Contributor(s):
34 : * Carl D. Worth <cworth@cworth.org>
35 : * Chris Wilson <chris@chris-wilson.co.uk>
36 : */
37 :
38 : /* Provide definitions for standalone compilation */
39 : #include "cairoint.h"
40 :
41 : #include "cairo-boxes-private.h"
42 : #include "cairo-combsort-private.h"
43 : #include "cairo-error-private.h"
44 :
45 : typedef struct _cairo_bo_edge cairo_bo_edge_t;
46 : typedef struct _cairo_bo_trap cairo_bo_trap_t;
47 :
48 : /* A deferred trapezoid of an edge */
49 : struct _cairo_bo_trap {
50 : cairo_bo_edge_t *right;
51 : int32_t top;
52 : };
53 :
54 : struct _cairo_bo_edge {
55 : cairo_edge_t edge;
56 : cairo_bo_edge_t *prev;
57 : cairo_bo_edge_t *next;
58 : cairo_bo_trap_t deferred_trap;
59 : };
60 :
61 : typedef enum {
62 : CAIRO_BO_EVENT_TYPE_START,
63 : CAIRO_BO_EVENT_TYPE_STOP
64 : } cairo_bo_event_type_t;
65 :
66 : typedef struct _cairo_bo_event {
67 : cairo_bo_event_type_t type;
68 : cairo_point_t point;
69 : cairo_bo_edge_t *edge;
70 : } cairo_bo_event_t;
71 :
72 : typedef struct _cairo_bo_sweep_line {
73 : cairo_bo_event_t **events;
74 : cairo_bo_edge_t *head;
75 : cairo_bo_edge_t *stopped;
76 : int32_t current_y;
77 : cairo_bo_edge_t *current_edge;
78 : } cairo_bo_sweep_line_t;
79 :
80 : static inline int
81 0 : _cairo_point_compare (const cairo_point_t *a,
82 : const cairo_point_t *b)
83 : {
84 : int cmp;
85 :
86 0 : cmp = a->y - b->y;
87 0 : if (likely (cmp))
88 0 : return cmp;
89 :
90 0 : return a->x - b->x;
91 : }
92 :
93 : static inline int
94 0 : _cairo_bo_edge_compare (const cairo_bo_edge_t *a,
95 : const cairo_bo_edge_t *b)
96 : {
97 : int cmp;
98 :
99 0 : cmp = a->edge.line.p1.x - b->edge.line.p1.x;
100 0 : if (likely (cmp))
101 0 : return cmp;
102 :
103 0 : return b->edge.bottom - a->edge.bottom;
104 : }
105 :
106 : static inline int
107 0 : cairo_bo_event_compare (const cairo_bo_event_t *a,
108 : const cairo_bo_event_t *b)
109 : {
110 : int cmp;
111 :
112 0 : cmp = _cairo_point_compare (&a->point, &b->point);
113 0 : if (likely (cmp))
114 0 : return cmp;
115 :
116 0 : cmp = a->type - b->type;
117 0 : if (cmp)
118 0 : return cmp;
119 :
120 0 : return a - b;
121 : }
122 :
123 : static inline cairo_bo_event_t *
124 0 : _cairo_bo_event_dequeue (cairo_bo_sweep_line_t *sweep_line)
125 : {
126 0 : return *sweep_line->events++;
127 : }
128 :
129 0 : CAIRO_COMBSORT_DECLARE (_cairo_bo_event_queue_sort,
130 : cairo_bo_event_t *,
131 : cairo_bo_event_compare)
132 :
133 : static void
134 0 : _cairo_bo_sweep_line_init (cairo_bo_sweep_line_t *sweep_line,
135 : cairo_bo_event_t **events,
136 : int num_events)
137 : {
138 0 : _cairo_bo_event_queue_sort (events, num_events);
139 0 : events[num_events] = NULL;
140 0 : sweep_line->events = events;
141 :
142 0 : sweep_line->head = NULL;
143 0 : sweep_line->current_y = INT32_MIN;
144 0 : sweep_line->current_edge = NULL;
145 0 : }
146 :
147 : static void
148 0 : _cairo_bo_sweep_line_insert (cairo_bo_sweep_line_t *sweep_line,
149 : cairo_bo_edge_t *edge)
150 : {
151 0 : if (sweep_line->current_edge != NULL) {
152 : cairo_bo_edge_t *prev, *next;
153 : int cmp;
154 :
155 0 : cmp = _cairo_bo_edge_compare (sweep_line->current_edge, edge);
156 0 : if (cmp < 0) {
157 0 : prev = sweep_line->current_edge;
158 0 : next = prev->next;
159 0 : while (next != NULL && _cairo_bo_edge_compare (next, edge) < 0)
160 0 : prev = next, next = prev->next;
161 :
162 0 : prev->next = edge;
163 0 : edge->prev = prev;
164 0 : edge->next = next;
165 0 : if (next != NULL)
166 0 : next->prev = edge;
167 0 : } else if (cmp > 0) {
168 0 : next = sweep_line->current_edge;
169 0 : prev = next->prev;
170 0 : while (prev != NULL && _cairo_bo_edge_compare (prev, edge) > 0)
171 0 : next = prev, prev = next->prev;
172 :
173 0 : next->prev = edge;
174 0 : edge->next = next;
175 0 : edge->prev = prev;
176 0 : if (prev != NULL)
177 0 : prev->next = edge;
178 : else
179 0 : sweep_line->head = edge;
180 : } else {
181 0 : prev = sweep_line->current_edge;
182 0 : edge->prev = prev;
183 0 : edge->next = prev->next;
184 0 : if (prev->next != NULL)
185 0 : prev->next->prev = edge;
186 0 : prev->next = edge;
187 : }
188 : } else {
189 0 : sweep_line->head = edge;
190 : }
191 :
192 0 : sweep_line->current_edge = edge;
193 0 : }
194 :
195 : static void
196 0 : _cairo_bo_sweep_line_delete (cairo_bo_sweep_line_t *sweep_line,
197 : cairo_bo_edge_t *edge)
198 : {
199 0 : if (edge->prev != NULL)
200 0 : edge->prev->next = edge->next;
201 : else
202 0 : sweep_line->head = edge->next;
203 :
204 0 : if (edge->next != NULL)
205 0 : edge->next->prev = edge->prev;
206 :
207 0 : if (sweep_line->current_edge == edge)
208 0 : sweep_line->current_edge = edge->prev ? edge->prev : edge->next;
209 0 : }
210 :
211 : static inline cairo_bool_t
212 0 : edges_collinear (const cairo_bo_edge_t *a, const cairo_bo_edge_t *b)
213 : {
214 0 : return a->edge.line.p1.x == b->edge.line.p1.x;
215 : }
216 :
217 : static cairo_status_t
218 0 : _cairo_bo_edge_end_trap (cairo_bo_edge_t *left,
219 : int32_t bot,
220 : cairo_bool_t do_traps,
221 : void *container)
222 : {
223 0 : cairo_bo_trap_t *trap = &left->deferred_trap;
224 0 : cairo_status_t status = CAIRO_STATUS_SUCCESS;
225 :
226 : /* Only emit (trivial) non-degenerate trapezoids with positive height. */
227 0 : if (likely (trap->top < bot)) {
228 0 : if (do_traps) {
229 0 : _cairo_traps_add_trap (container,
230 : trap->top, bot,
231 0 : &left->edge.line, &trap->right->edge.line);
232 0 : status = _cairo_traps_status ((cairo_traps_t *) container);
233 : } else {
234 : cairo_box_t box;
235 :
236 0 : box.p1.x = left->edge.line.p1.x;
237 0 : box.p1.y = trap->top;
238 0 : box.p2.x = trap->right->edge.line.p1.x;
239 0 : box.p2.y = bot;
240 0 : status = _cairo_boxes_add (container, &box);
241 : }
242 : }
243 :
244 0 : trap->right = NULL;
245 :
246 0 : return status;
247 : }
248 :
249 : /* Start a new trapezoid at the given top y coordinate, whose edges
250 : * are `edge' and `edge->next'. If `edge' already has a trapezoid,
251 : * then either add it to the traps in `traps', if the trapezoid's
252 : * right edge differs from `edge->next', or do nothing if the new
253 : * trapezoid would be a continuation of the existing one. */
254 : static inline cairo_status_t
255 0 : _cairo_bo_edge_start_or_continue_trap (cairo_bo_edge_t *left,
256 : cairo_bo_edge_t *right,
257 : int top,
258 : cairo_bool_t do_traps,
259 : void *container)
260 : {
261 : cairo_status_t status;
262 :
263 0 : if (left->deferred_trap.right == right)
264 0 : return CAIRO_STATUS_SUCCESS;
265 :
266 0 : if (left->deferred_trap.right != NULL) {
267 0 : if (right != NULL && edges_collinear (left->deferred_trap.right, right))
268 : {
269 : /* continuation on right, so just swap edges */
270 0 : left->deferred_trap.right = right;
271 0 : return CAIRO_STATUS_SUCCESS;
272 : }
273 :
274 0 : status = _cairo_bo_edge_end_trap (left, top, do_traps, container);
275 0 : if (unlikely (status))
276 0 : return status;
277 : }
278 :
279 0 : if (right != NULL && ! edges_collinear (left, right)) {
280 0 : left->deferred_trap.top = top;
281 0 : left->deferred_trap.right = right;
282 : }
283 :
284 0 : return CAIRO_STATUS_SUCCESS;
285 : }
286 :
287 : static inline cairo_status_t
288 0 : _active_edges_to_traps (cairo_bo_edge_t *left,
289 : int32_t top,
290 : cairo_fill_rule_t fill_rule,
291 : cairo_bool_t do_traps,
292 : void *container)
293 : {
294 : cairo_bo_edge_t *right;
295 : cairo_status_t status;
296 :
297 0 : if (fill_rule == CAIRO_FILL_RULE_WINDING) {
298 0 : while (left != NULL) {
299 : int in_out;
300 :
301 : /* Greedily search for the closing edge, so that we generate the
302 : * maximal span width with the minimal number of trapezoids.
303 : */
304 0 : in_out = left->edge.dir;
305 :
306 : /* Check if there is a co-linear edge with an existing trap */
307 0 : right = left->next;
308 0 : if (left->deferred_trap.right == NULL) {
309 0 : while (right != NULL && right->deferred_trap.right == NULL)
310 0 : right = right->next;
311 :
312 0 : if (right != NULL && edges_collinear (left, right)) {
313 : /* continuation on left */
314 0 : left->deferred_trap = right->deferred_trap;
315 0 : right->deferred_trap.right = NULL;
316 : }
317 : }
318 :
319 : /* End all subsumed traps */
320 0 : right = left->next;
321 0 : while (right != NULL) {
322 0 : if (right->deferred_trap.right != NULL) {
323 0 : status = _cairo_bo_edge_end_trap (right, top, do_traps, container);
324 0 : if (unlikely (status))
325 0 : return status;
326 : }
327 :
328 0 : in_out += right->edge.dir;
329 0 : if (in_out == 0) {
330 : /* skip co-linear edges */
331 0 : if (right->next == NULL ||
332 0 : ! edges_collinear (right, right->next))
333 : {
334 : break;
335 : }
336 : }
337 :
338 0 : right = right->next;
339 : }
340 :
341 0 : status = _cairo_bo_edge_start_or_continue_trap (left, right, top,
342 : do_traps, container);
343 0 : if (unlikely (status))
344 0 : return status;
345 :
346 0 : left = right;
347 0 : if (left != NULL)
348 0 : left = left->next;
349 : }
350 : } else {
351 0 : while (left != NULL) {
352 0 : int in_out = 0;
353 :
354 0 : right = left->next;
355 0 : while (right != NULL) {
356 0 : if (right->deferred_trap.right != NULL) {
357 0 : status = _cairo_bo_edge_end_trap (right, top, do_traps, container);
358 0 : if (unlikely (status))
359 0 : return status;
360 : }
361 :
362 0 : if ((in_out++ & 1) == 0) {
363 : cairo_bo_edge_t *next;
364 0 : cairo_bool_t skip = FALSE;
365 :
366 : /* skip co-linear edges */
367 0 : next = right->next;
368 0 : if (next != NULL)
369 0 : skip = edges_collinear (right, next);
370 :
371 0 : if (! skip)
372 0 : break;
373 : }
374 :
375 0 : right = right->next;
376 : }
377 :
378 0 : status = _cairo_bo_edge_start_or_continue_trap (left, right, top,
379 : do_traps, container);
380 0 : if (unlikely (status))
381 0 : return status;
382 :
383 0 : left = right;
384 0 : if (left != NULL)
385 0 : left = left->next;
386 : }
387 : }
388 :
389 0 : return CAIRO_STATUS_SUCCESS;
390 : }
391 :
392 : static cairo_status_t
393 0 : _cairo_bentley_ottmann_tessellate_rectilinear (cairo_bo_event_t **start_events,
394 : int num_events,
395 : cairo_fill_rule_t fill_rule,
396 : cairo_bool_t do_traps,
397 : void *container)
398 : {
399 : cairo_bo_sweep_line_t sweep_line;
400 : cairo_bo_event_t *event;
401 : cairo_status_t status;
402 :
403 0 : _cairo_bo_sweep_line_init (&sweep_line, start_events, num_events);
404 :
405 0 : while ((event = _cairo_bo_event_dequeue (&sweep_line))) {
406 0 : if (event->point.y != sweep_line.current_y) {
407 0 : status = _active_edges_to_traps (sweep_line.head,
408 : sweep_line.current_y,
409 : fill_rule, do_traps, container);
410 0 : if (unlikely (status))
411 0 : return status;
412 :
413 0 : sweep_line.current_y = event->point.y;
414 : }
415 :
416 0 : switch (event->type) {
417 : case CAIRO_BO_EVENT_TYPE_START:
418 0 : _cairo_bo_sweep_line_insert (&sweep_line, event->edge);
419 0 : break;
420 :
421 : case CAIRO_BO_EVENT_TYPE_STOP:
422 0 : _cairo_bo_sweep_line_delete (&sweep_line, event->edge);
423 :
424 0 : if (event->edge->deferred_trap.right != NULL) {
425 0 : status = _cairo_bo_edge_end_trap (event->edge,
426 : sweep_line.current_y,
427 : do_traps, container);
428 0 : if (unlikely (status))
429 0 : return status;
430 : }
431 :
432 0 : break;
433 : }
434 : }
435 :
436 0 : return CAIRO_STATUS_SUCCESS;
437 : }
438 :
439 : cairo_status_t
440 0 : _cairo_bentley_ottmann_tessellate_rectilinear_polygon (cairo_traps_t *traps,
441 : const cairo_polygon_t *polygon,
442 : cairo_fill_rule_t fill_rule)
443 : {
444 : cairo_status_t status;
445 : cairo_bo_event_t stack_events[CAIRO_STACK_ARRAY_LENGTH (cairo_bo_event_t)];
446 : cairo_bo_event_t *events;
447 : cairo_bo_event_t *stack_event_ptrs[ARRAY_LENGTH (stack_events) + 1];
448 : cairo_bo_event_t **event_ptrs;
449 : cairo_bo_edge_t stack_edges[ARRAY_LENGTH (stack_events)];
450 : cairo_bo_edge_t *edges;
451 : int num_events;
452 : int i, j;
453 :
454 0 : if (unlikely (polygon->num_edges == 0))
455 0 : return CAIRO_STATUS_SUCCESS;
456 :
457 0 : num_events = 2 * polygon->num_edges;
458 :
459 0 : events = stack_events;
460 0 : event_ptrs = stack_event_ptrs;
461 0 : edges = stack_edges;
462 0 : if (num_events > ARRAY_LENGTH (stack_events)) {
463 0 : events = _cairo_malloc_ab_plus_c (num_events,
464 : sizeof (cairo_bo_event_t) +
465 : sizeof (cairo_bo_edge_t) +
466 : sizeof (cairo_bo_event_t *),
467 : sizeof (cairo_bo_event_t *));
468 0 : if (unlikely (events == NULL))
469 0 : return _cairo_error (CAIRO_STATUS_NO_MEMORY);
470 :
471 0 : event_ptrs = (cairo_bo_event_t **) (events + num_events);
472 0 : edges = (cairo_bo_edge_t *) (event_ptrs + num_events + 1);
473 : }
474 :
475 0 : for (i = j = 0; i < polygon->num_edges; i++) {
476 0 : edges[i].edge = polygon->edges[i];
477 0 : edges[i].deferred_trap.right = NULL;
478 0 : edges[i].prev = NULL;
479 0 : edges[i].next = NULL;
480 :
481 0 : event_ptrs[j] = &events[j];
482 0 : events[j].type = CAIRO_BO_EVENT_TYPE_START;
483 0 : events[j].point.y = polygon->edges[i].top;
484 0 : events[j].point.x = polygon->edges[i].line.p1.x;
485 0 : events[j].edge = &edges[i];
486 0 : j++;
487 :
488 0 : event_ptrs[j] = &events[j];
489 0 : events[j].type = CAIRO_BO_EVENT_TYPE_STOP;
490 0 : events[j].point.y = polygon->edges[i].bottom;
491 0 : events[j].point.x = polygon->edges[i].line.p1.x;
492 0 : events[j].edge = &edges[i];
493 0 : j++;
494 : }
495 :
496 0 : status = _cairo_bentley_ottmann_tessellate_rectilinear (event_ptrs, j,
497 : fill_rule,
498 : TRUE, traps);
499 0 : if (events != stack_events)
500 0 : free (events);
501 :
502 0 : traps->is_rectilinear = TRUE;
503 :
504 0 : return status;
505 : }
506 :
507 : cairo_status_t
508 0 : _cairo_bentley_ottmann_tessellate_rectilinear_polygon_to_boxes (const cairo_polygon_t *polygon,
509 : cairo_fill_rule_t fill_rule,
510 : cairo_boxes_t *boxes)
511 : {
512 : cairo_status_t status;
513 : cairo_bo_event_t stack_events[CAIRO_STACK_ARRAY_LENGTH (cairo_bo_event_t)];
514 : cairo_bo_event_t *events;
515 : cairo_bo_event_t *stack_event_ptrs[ARRAY_LENGTH (stack_events) + 1];
516 : cairo_bo_event_t **event_ptrs;
517 : cairo_bo_edge_t stack_edges[ARRAY_LENGTH (stack_events)];
518 : cairo_bo_edge_t *edges;
519 : int num_events;
520 : int i, j;
521 :
522 0 : if (unlikely (polygon->num_edges == 0))
523 0 : return CAIRO_STATUS_SUCCESS;
524 :
525 0 : num_events = 2 * polygon->num_edges;
526 :
527 0 : events = stack_events;
528 0 : event_ptrs = stack_event_ptrs;
529 0 : edges = stack_edges;
530 0 : if (num_events > ARRAY_LENGTH (stack_events)) {
531 0 : events = _cairo_malloc_ab_plus_c (num_events,
532 : sizeof (cairo_bo_event_t) +
533 : sizeof (cairo_bo_edge_t) +
534 : sizeof (cairo_bo_event_t *),
535 : sizeof (cairo_bo_event_t *));
536 0 : if (unlikely (events == NULL))
537 0 : return _cairo_error (CAIRO_STATUS_NO_MEMORY);
538 :
539 0 : event_ptrs = (cairo_bo_event_t **) (events + num_events);
540 0 : edges = (cairo_bo_edge_t *) (event_ptrs + num_events + 1);
541 : }
542 :
543 0 : for (i = j = 0; i < polygon->num_edges; i++) {
544 0 : edges[i].edge = polygon->edges[i];
545 0 : edges[i].deferred_trap.right = NULL;
546 0 : edges[i].prev = NULL;
547 0 : edges[i].next = NULL;
548 :
549 0 : event_ptrs[j] = &events[j];
550 0 : events[j].type = CAIRO_BO_EVENT_TYPE_START;
551 0 : events[j].point.y = polygon->edges[i].top;
552 0 : events[j].point.x = polygon->edges[i].line.p1.x;
553 0 : events[j].edge = &edges[i];
554 0 : j++;
555 :
556 0 : event_ptrs[j] = &events[j];
557 0 : events[j].type = CAIRO_BO_EVENT_TYPE_STOP;
558 0 : events[j].point.y = polygon->edges[i].bottom;
559 0 : events[j].point.x = polygon->edges[i].line.p1.x;
560 0 : events[j].edge = &edges[i];
561 0 : j++;
562 : }
563 :
564 0 : status = _cairo_bentley_ottmann_tessellate_rectilinear (event_ptrs, j,
565 : fill_rule,
566 : FALSE, boxes);
567 0 : if (events != stack_events)
568 0 : free (events);
569 :
570 0 : return status;
571 : }
572 :
573 : cairo_status_t
574 0 : _cairo_bentley_ottmann_tessellate_rectilinear_traps (cairo_traps_t *traps,
575 : cairo_fill_rule_t fill_rule)
576 : {
577 : cairo_bo_event_t stack_events[CAIRO_STACK_ARRAY_LENGTH (cairo_bo_event_t)];
578 : cairo_bo_event_t *events;
579 : cairo_bo_event_t *stack_event_ptrs[ARRAY_LENGTH (stack_events) + 1];
580 : cairo_bo_event_t **event_ptrs;
581 : cairo_bo_edge_t stack_edges[ARRAY_LENGTH (stack_events)];
582 : cairo_bo_edge_t *edges;
583 : cairo_status_t status;
584 : int i, j, k;
585 :
586 0 : if (unlikely (traps->num_traps == 0))
587 0 : return CAIRO_STATUS_SUCCESS;
588 :
589 0 : assert (traps->is_rectilinear);
590 :
591 0 : i = 4 * traps->num_traps;
592 :
593 0 : events = stack_events;
594 0 : event_ptrs = stack_event_ptrs;
595 0 : edges = stack_edges;
596 0 : if (i > ARRAY_LENGTH (stack_events)) {
597 0 : events = _cairo_malloc_ab_plus_c (i,
598 : sizeof (cairo_bo_event_t) +
599 : sizeof (cairo_bo_edge_t) +
600 : sizeof (cairo_bo_event_t *),
601 : sizeof (cairo_bo_event_t *));
602 0 : if (unlikely (events == NULL))
603 0 : return _cairo_error (CAIRO_STATUS_NO_MEMORY);
604 :
605 0 : event_ptrs = (cairo_bo_event_t **) (events + i);
606 0 : edges = (cairo_bo_edge_t *) (event_ptrs + i + 1);
607 : }
608 :
609 0 : for (i = j = k = 0; i < traps->num_traps; i++) {
610 0 : edges[k].edge.top = traps->traps[i].top;
611 0 : edges[k].edge.bottom = traps->traps[i].bottom;
612 0 : edges[k].edge.line = traps->traps[i].left;
613 0 : edges[k].edge.dir = 1;
614 0 : edges[k].deferred_trap.right = NULL;
615 0 : edges[k].prev = NULL;
616 0 : edges[k].next = NULL;
617 :
618 0 : event_ptrs[j] = &events[j];
619 0 : events[j].type = CAIRO_BO_EVENT_TYPE_START;
620 0 : events[j].point.y = traps->traps[i].top;
621 0 : events[j].point.x = traps->traps[i].left.p1.x;
622 0 : events[j].edge = &edges[k];
623 0 : j++;
624 :
625 0 : event_ptrs[j] = &events[j];
626 0 : events[j].type = CAIRO_BO_EVENT_TYPE_STOP;
627 0 : events[j].point.y = traps->traps[i].bottom;
628 0 : events[j].point.x = traps->traps[i].left.p1.x;
629 0 : events[j].edge = &edges[k];
630 0 : j++;
631 0 : k++;
632 :
633 0 : edges[k].edge.top = traps->traps[i].top;
634 0 : edges[k].edge.bottom = traps->traps[i].bottom;
635 0 : edges[k].edge.line = traps->traps[i].right;
636 0 : edges[k].edge.dir = -1;
637 0 : edges[k].deferred_trap.right = NULL;
638 0 : edges[k].prev = NULL;
639 0 : edges[k].next = NULL;
640 :
641 0 : event_ptrs[j] = &events[j];
642 0 : events[j].type = CAIRO_BO_EVENT_TYPE_START;
643 0 : events[j].point.y = traps->traps[i].top;
644 0 : events[j].point.x = traps->traps[i].right.p1.x;
645 0 : events[j].edge = &edges[k];
646 0 : j++;
647 :
648 0 : event_ptrs[j] = &events[j];
649 0 : events[j].type = CAIRO_BO_EVENT_TYPE_STOP;
650 0 : events[j].point.y = traps->traps[i].bottom;
651 0 : events[j].point.x = traps->traps[i].right.p1.x;
652 0 : events[j].edge = &edges[k];
653 0 : j++;
654 0 : k++;
655 : }
656 :
657 0 : _cairo_traps_clear (traps);
658 0 : status = _cairo_bentley_ottmann_tessellate_rectilinear (event_ptrs, j,
659 : fill_rule,
660 : TRUE, traps);
661 0 : traps->is_rectilinear = TRUE;
662 :
663 0 : if (events != stack_events)
664 0 : free (events);
665 :
666 0 : return status;
667 : }
|