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-inline.h"
43
#include "cairo-error-private.h"
44
#include "cairo-traps-private.h"
45

            
46
typedef struct _cairo_bo_edge cairo_bo_edge_t;
47
typedef struct _cairo_bo_trap cairo_bo_trap_t;
48

            
49
/* A deferred trapezoid of an edge */
50
struct _cairo_bo_trap {
51
    cairo_bo_edge_t *right;
52
    int32_t top;
53
};
54

            
55
struct _cairo_bo_edge {
56
    cairo_edge_t edge;
57
    cairo_bo_edge_t *prev;
58
    cairo_bo_edge_t *next;
59
    cairo_bo_trap_t deferred_trap;
60
};
61

            
62
typedef enum {
63
    CAIRO_BO_EVENT_TYPE_START,
64
    CAIRO_BO_EVENT_TYPE_STOP
65
} cairo_bo_event_type_t;
66

            
67
typedef struct _cairo_bo_event {
68
    cairo_bo_event_type_t type;
69
    cairo_point_t point;
70
    cairo_bo_edge_t *edge;
71
} cairo_bo_event_t;
72

            
73
typedef struct _cairo_bo_sweep_line {
74
    cairo_bo_event_t **events;
75
    cairo_bo_edge_t *head;
76
    cairo_bo_edge_t *stopped;
77
    int32_t current_y;
78
    cairo_bo_edge_t *current_edge;
79
} cairo_bo_sweep_line_t;
80

            
81
static inline int
82
13832316
_cairo_point_compare (const cairo_point_t *a,
83
		      const cairo_point_t *b)
84
{
85
    int cmp;
86

            
87
13832316
    cmp = a->y - b->y;
88
13832316
    if (likely (cmp))
89
11556903
	return cmp;
90

            
91
2275413
    return a->x - b->x;
92
}
93

            
94
static inline int
95
3465027
_cairo_bo_edge_compare (const cairo_bo_edge_t	*a,
96
			const cairo_bo_edge_t	*b)
97
{
98
    int cmp;
99

            
100
3465027
    cmp = a->edge.line.p1.x - b->edge.line.p1.x;
101
3465027
    if (likely (cmp))
102
3465024
	return cmp;
103

            
104
3
    return b->edge.bottom - a->edge.bottom;
105
}
106

            
107
static inline int
108
13832316
cairo_bo_event_compare (const cairo_bo_event_t *a,
109
			const cairo_bo_event_t *b)
110
{
111
    int cmp;
112

            
113
13832316
    cmp = _cairo_point_compare (&a->point, &b->point);
114
13832316
    if (likely (cmp))
115
13832301
	return cmp;
116

            
117
15
    cmp = a->type - b->type;
118
15
    if (cmp)
119
	return cmp;
120

            
121
15
    return a - b;
122
}
123

            
124
static inline cairo_bo_event_t *
125
367401
_cairo_bo_event_dequeue (cairo_bo_sweep_line_t *sweep_line)
126
{
127
367401
    return *sweep_line->events++;
128
}
129

            
130
13832811
CAIRO_COMBSORT_DECLARE (_cairo_bo_event_queue_sort,
131
			cairo_bo_event_t *,
132
			cairo_bo_event_compare)
133

            
134
static void
135
33
_cairo_bo_sweep_line_init (cairo_bo_sweep_line_t *sweep_line,
136
			   cairo_bo_event_t	**events,
137
			   int			  num_events)
138
{
139
33
    _cairo_bo_event_queue_sort (events, num_events);
140
33
    events[num_events] = NULL;
141
33
    sweep_line->events = events;
142

            
143
33
    sweep_line->head = NULL;
144
33
    sweep_line->current_y = INT32_MIN;
145
33
    sweep_line->current_edge = NULL;
146
33
}
147

            
148
static void
149
183684
_cairo_bo_sweep_line_insert (cairo_bo_sweep_line_t	*sweep_line,
150
			     cairo_bo_edge_t		*edge)
151
{
152
183684
    if (sweep_line->current_edge != NULL) {
153
	cairo_bo_edge_t *prev, *next;
154
	int cmp;
155

            
156
183300
	cmp = _cairo_bo_edge_compare (sweep_line->current_edge, edge);
157
183300
	if (cmp < 0) {
158
150021
	    prev = sweep_line->current_edge;
159
150021
	    next = prev->next;
160
1646523
	    while (next != NULL && _cairo_bo_edge_compare (next, edge) < 0)
161
1496502
		prev = next, next = prev->next;
162

            
163
150021
	    prev->next = edge;
164
150021
	    edge->prev = prev;
165
150021
	    edge->next = next;
166
150021
	    if (next != NULL)
167
146112
		next->prev = edge;
168
33279
	} else if (cmp > 0) {
169
33276
	    next = sweep_line->current_edge;
170
33276
	    prev = next->prev;
171
1646466
	    while (prev != NULL && _cairo_bo_edge_compare (prev, edge) > 0)
172
1613190
		next = prev, prev = next->prev;
173

            
174
33276
	    next->prev = edge;
175
33276
	    edge->next = next;
176
33276
	    edge->prev = prev;
177
33276
	    if (prev != NULL)
178
25923
		prev->next = edge;
179
	    else
180
7353
		sweep_line->head = edge;
181
	} else {
182
3
	    prev = sweep_line->current_edge;
183
3
	    edge->prev = prev;
184
3
	    edge->next = prev->next;
185
3
	    if (prev->next != NULL)
186
		prev->next->prev = edge;
187
3
	    prev->next = edge;
188
	}
189
    } else {
190
384
	sweep_line->head = edge;
191
    }
192

            
193
183684
    sweep_line->current_edge = edge;
194
183684
}
195

            
196
static void
197
183684
_cairo_bo_sweep_line_delete (cairo_bo_sweep_line_t	*sweep_line,
198
			     cairo_bo_edge_t	*edge)
199
{
200
183684
    if (edge->prev != NULL)
201
163863
	edge->prev->next = edge->next;
202
    else
203
19821
	sweep_line->head = edge->next;
204

            
205
183684
    if (edge->next != NULL)
206
183285
	edge->next->prev = edge->prev;
207

            
208
183684
    if (sweep_line->current_edge == edge)
209
7689
	sweep_line->current_edge = edge->prev ? edge->prev : edge->next;
210
183684
}
211

            
212
static inline cairo_bool_t
213
9581454
edges_collinear (const cairo_bo_edge_t *a, const cairo_bo_edge_t *b)
214
{
215
9581454
    return a->edge.line.p1.x == b->edge.line.p1.x;
216
}
217

            
218
static cairo_status_t
219
91863
_cairo_bo_edge_end_trap (cairo_bo_edge_t	*left,
220
			 int32_t		 bot,
221
			 cairo_bool_t		 do_traps,
222
			 void			*container)
223
{
224
91863
    cairo_bo_trap_t *trap = &left->deferred_trap;
225
91863
    cairo_status_t status = CAIRO_STATUS_SUCCESS;
226

            
227
    /* Only emit (trivial) non-degenerate trapezoids with positive height. */
228
91863
    if (likely (trap->top < bot)) {
229
91863
	if (do_traps) {
230
	    _cairo_traps_add_trap (container,
231
				   trap->top, bot,
232
				   &left->edge.line, &trap->right->edge.line);
233
	    status =  _cairo_traps_status ((cairo_traps_t *) container);
234
	} else {
235
	    cairo_box_t box;
236

            
237
91863
	    box.p1.x = left->edge.line.p1.x;
238
91863
	    box.p1.y = trap->top;
239
91863
	    box.p2.x = trap->right->edge.line.p1.x;
240
91863
	    box.p2.y = bot;
241
91863
	    status = _cairo_boxes_add (container, CAIRO_ANTIALIAS_DEFAULT, &box);
242
	}
243
    }
244

            
245
91863
    trap->right = NULL;
246

            
247
91863
    return status;
248
}
249

            
250
/* Start a new trapezoid at the given top y coordinate, whose edges
251
 * are `edge' and `edge->next'. If `edge' already has a trapezoid,
252
 * then either add it to the traps in `traps', if the trapezoid's
253
 * right edge differs from `edge->next', or do nothing if the new
254
 * trapezoid would be a continuation of the existing one. */
255
static inline cairo_status_t
256
9476475
_cairo_bo_edge_start_or_continue_trap (cairo_bo_edge_t	*left,
257
				       cairo_bo_edge_t  *right,
258
				       int               top,
259
				       cairo_bool_t	 do_traps,
260
				       void		*container)
261
{
262
    cairo_status_t status;
263

            
264
9476475
    if (left->deferred_trap.right == right)
265
9384609
	return CAIRO_STATUS_SUCCESS;
266

            
267
91866
    if (left->deferred_trap.right != NULL) {
268
18
	if (right != NULL && edges_collinear (left->deferred_trap.right, right))
269
	{
270
	    /* continuation on right, so just swap edges */
271
	    left->deferred_trap.right = right;
272
	    return CAIRO_STATUS_SUCCESS;
273
	}
274

            
275
18
	status = _cairo_bo_edge_end_trap (left, top, do_traps, container);
276
18
	if (unlikely (status))
277
	    return status;
278
    }
279

            
280
91866
    if (right != NULL && ! edges_collinear (left, right)) {
281
91863
	left->deferred_trap.top = top;
282
91863
	left->deferred_trap.right = right;
283
    }
284

            
285
91866
    return CAIRO_STATUS_SUCCESS;
286
}
287

            
288
static inline cairo_status_t
289
76977
_active_edges_to_traps (cairo_bo_edge_t		*left,
290
			int32_t			 top,
291
			cairo_fill_rule_t	 fill_rule,
292
			cairo_bool_t		 do_traps,
293
			void			*container)
294
{
295
    cairo_bo_edge_t *right;
296
    cairo_status_t status;
297

            
298
76977
    if (fill_rule == CAIRO_FILL_RULE_WINDING) {
299
9553419
	while (left != NULL) {
300
	    int in_out;
301

            
302
	    /* Greedily search for the closing edge, so that we generate the
303
	     * maximal span width with the minimal number of trapezoids.
304
	     */
305
9476457
	    in_out = left->edge.dir;
306

            
307
	    /* Check if there is a co-linear edge with an existing trap */
308
9476457
	    right = left->next;
309
9476457
	    if (left->deferred_trap.right == NULL) {
310
208209
		while (right != NULL && right->deferred_trap.right == NULL)
311
116376
		    right = right->next;
312

            
313
91833
		if (right != NULL && edges_collinear (left, right)) {
314
		    /* continuation on left */
315
		    left->deferred_trap = right->deferred_trap;
316
		    right->deferred_trap.right = NULL;
317
		}
318
	    }
319

            
320
	    /* End all subsumed traps */
321
9476457
	    right = left->next;
322
9476463
	    while (right != NULL) {
323
9476463
		if (right->deferred_trap.right != NULL) {
324
3
		    status = _cairo_bo_edge_end_trap (right, top, do_traps, container);
325
3
		    if (unlikely (status))
326
			return status;
327
		}
328

            
329
9476463
		in_out += right->edge.dir;
330
9476463
		if (in_out == 0) {
331
		    /* skip co-linear edges */
332
18876333
		    if (right->next == NULL ||
333
9399876
			! edges_collinear (right, right->next))
334
		    {
335
			break;
336
		    }
337
		}
338

            
339
6
		right = right->next;
340
	    }
341

            
342
9476457
	    status = _cairo_bo_edge_start_or_continue_trap (left, right, top,
343
							    do_traps, container);
344
9476457
	    if (unlikely (status))
345
		return status;
346

            
347
9476457
	    left = right;
348
9476457
	    if (left != NULL)
349
9476457
		left = left->next;
350
	}
351
    } else {
352
33
	while (left != NULL) {
353
18
	    int in_out = 0;
354

            
355
18
	    right = left->next;
356
18
	    while (right != NULL) {
357
18
		if (right->deferred_trap.right != NULL) {
358
6
		    status = _cairo_bo_edge_end_trap (right, top, do_traps, container);
359
6
		    if (unlikely (status))
360
			return status;
361
		}
362

            
363
18
		if ((in_out++ & 1) == 0) {
364
		    cairo_bo_edge_t *next;
365
18
		    cairo_bool_t skip = FALSE;
366

            
367
		    /* skip co-linear edges */
368
18
		    next = right->next;
369
18
		    if (next != NULL)
370
6
			skip = edges_collinear (right, next);
371

            
372
18
		    if (! skip)
373
18
			break;
374
		}
375

            
376
		right = right->next;
377
	    }
378

            
379
18
	    status = _cairo_bo_edge_start_or_continue_trap (left, right, top,
380
							    do_traps, container);
381
18
	    if (unlikely (status))
382
		return status;
383

            
384
18
	    left = right;
385
18
	    if (left != NULL)
386
18
		left = left->next;
387
	}
388
    }
389

            
390
76977
    return CAIRO_STATUS_SUCCESS;
391
}
392

            
393
static cairo_status_t
394
33
_cairo_bentley_ottmann_tessellate_rectilinear (cairo_bo_event_t   **start_events,
395
					       int			 num_events,
396
					       cairo_fill_rule_t	 fill_rule,
397
					       cairo_bool_t		 do_traps,
398
					       void			*container)
399
{
400
    cairo_bo_sweep_line_t sweep_line;
401
    cairo_bo_event_t *event;
402
    cairo_status_t status;
403

            
404
33
    _cairo_bo_sweep_line_init (&sweep_line, start_events, num_events);
405

            
406
367434
    while ((event = _cairo_bo_event_dequeue (&sweep_line))) {
407
367368
	if (event->point.y != sweep_line.current_y) {
408
76977
	    status = _active_edges_to_traps (sweep_line.head,
409
					     sweep_line.current_y,
410
					     fill_rule, do_traps, container);
411
76977
	    if (unlikely (status))
412
		return status;
413

            
414
76977
	    sweep_line.current_y = event->point.y;
415
	}
416

            
417
367368
	switch (event->type) {
418
183684
	case CAIRO_BO_EVENT_TYPE_START:
419
183684
	    _cairo_bo_sweep_line_insert (&sweep_line, event->edge);
420
183684
	    break;
421

            
422
183684
	case CAIRO_BO_EVENT_TYPE_STOP:
423
183684
	    _cairo_bo_sweep_line_delete (&sweep_line, event->edge);
424

            
425
183684
	    if (event->edge->deferred_trap.right != NULL) {
426
91836
		status = _cairo_bo_edge_end_trap (event->edge,
427
						  sweep_line.current_y,
428
						  do_traps, container);
429
91836
		if (unlikely (status))
430
		    return status;
431
	    }
432

            
433
183684
	    break;
434
	}
435
    }
436

            
437
33
    return CAIRO_STATUS_SUCCESS;
438
}
439

            
440
cairo_status_t
441
42
_cairo_bentley_ottmann_tessellate_rectilinear_polygon_to_boxes (const cairo_polygon_t *polygon,
442
								cairo_fill_rule_t	  fill_rule,
443
								cairo_boxes_t *boxes)
444
{
445
    cairo_status_t status;
446
    cairo_bo_event_t stack_events[CAIRO_STACK_ARRAY_LENGTH (cairo_bo_event_t)];
447
    cairo_bo_event_t *events;
448
    cairo_bo_event_t *stack_event_ptrs[ARRAY_LENGTH (stack_events) + 1];
449
    cairo_bo_event_t **event_ptrs;
450
    cairo_bo_edge_t stack_edges[ARRAY_LENGTH (stack_events)];
451
    cairo_bo_edge_t *edges;
452
    int num_events;
453
    int i, j;
454

            
455
42
    if (unlikely (polygon->num_edges == 0))
456
9
	return CAIRO_STATUS_SUCCESS;
457

            
458
33
    num_events = 2 * polygon->num_edges;
459

            
460
33
    events = stack_events;
461
33
    event_ptrs = stack_event_ptrs;
462
33
    edges = stack_edges;
463
33
    if (num_events > ARRAY_LENGTH (stack_events)) {
464
9
	events = _cairo_malloc_ab_plus_c (num_events,
465
					  sizeof (cairo_bo_event_t) +
466
					  sizeof (cairo_bo_edge_t) +
467
					  sizeof (cairo_bo_event_t *),
468
					  sizeof (cairo_bo_event_t *));
469
9
	if (unlikely (events == NULL))
470
	    return _cairo_error (CAIRO_STATUS_NO_MEMORY);
471

            
472
9
	event_ptrs = (cairo_bo_event_t **) (events + num_events);
473
9
	edges = (cairo_bo_edge_t *) (event_ptrs + num_events + 1);
474
    }
475

            
476
183717
    for (i = j = 0; i < polygon->num_edges; i++) {
477
183684
	edges[i].edge = polygon->edges[i];
478
183684
	edges[i].deferred_trap.right = NULL;
479
183684
	edges[i].prev = NULL;
480
183684
	edges[i].next = NULL;
481

            
482
183684
	event_ptrs[j] = &events[j];
483
183684
	events[j].type = CAIRO_BO_EVENT_TYPE_START;
484
183684
	events[j].point.y = polygon->edges[i].top;
485
183684
	events[j].point.x = polygon->edges[i].line.p1.x;
486
183684
	events[j].edge = &edges[i];
487
183684
	j++;
488

            
489
183684
	event_ptrs[j] = &events[j];
490
183684
	events[j].type = CAIRO_BO_EVENT_TYPE_STOP;
491
183684
	events[j].point.y = polygon->edges[i].bottom;
492
183684
	events[j].point.x = polygon->edges[i].line.p1.x;
493
183684
	events[j].edge = &edges[i];
494
183684
	j++;
495
    }
496

            
497
33
    status = _cairo_bentley_ottmann_tessellate_rectilinear (event_ptrs, j,
498
							    fill_rule,
499
							    FALSE, boxes);
500
33
    if (events != stack_events)
501
9
	free (events);
502

            
503
33
    return status;
504
}
505

            
506
cairo_status_t
507
_cairo_bentley_ottmann_tessellate_rectilinear_traps (cairo_traps_t *traps,
508
						     cairo_fill_rule_t fill_rule)
509
{
510
    cairo_bo_event_t stack_events[CAIRO_STACK_ARRAY_LENGTH (cairo_bo_event_t)];
511
    cairo_bo_event_t *events;
512
    cairo_bo_event_t *stack_event_ptrs[ARRAY_LENGTH (stack_events) + 1];
513
    cairo_bo_event_t **event_ptrs;
514
    cairo_bo_edge_t stack_edges[ARRAY_LENGTH (stack_events)];
515
    cairo_bo_edge_t *edges;
516
    cairo_status_t status;
517
    int i, j, k;
518

            
519
    if (unlikely (traps->num_traps == 0))
520
	return CAIRO_STATUS_SUCCESS;
521

            
522
    assert (traps->is_rectilinear);
523

            
524
    i = 4 * traps->num_traps;
525

            
526
    events = stack_events;
527
    event_ptrs = stack_event_ptrs;
528
    edges = stack_edges;
529
    if (i > ARRAY_LENGTH (stack_events)) {
530
	events = _cairo_malloc_ab_plus_c (i,
531
					  sizeof (cairo_bo_event_t) +
532
					  sizeof (cairo_bo_edge_t) +
533
					  sizeof (cairo_bo_event_t *),
534
					  sizeof (cairo_bo_event_t *));
535
	if (unlikely (events == NULL))
536
	    return _cairo_error (CAIRO_STATUS_NO_MEMORY);
537

            
538
	event_ptrs = (cairo_bo_event_t **) (events + i);
539
	edges = (cairo_bo_edge_t *) (event_ptrs + i + 1);
540
    }
541

            
542
    for (i = j = k = 0; i < traps->num_traps; i++) {
543
	edges[k].edge.top = traps->traps[i].top;
544
	edges[k].edge.bottom = traps->traps[i].bottom;
545
	edges[k].edge.line = traps->traps[i].left;
546
	edges[k].edge.dir = 1;
547
	edges[k].deferred_trap.right = NULL;
548
	edges[k].prev = NULL;
549
	edges[k].next = NULL;
550

            
551
	event_ptrs[j] = &events[j];
552
	events[j].type = CAIRO_BO_EVENT_TYPE_START;
553
	events[j].point.y = traps->traps[i].top;
554
	events[j].point.x = traps->traps[i].left.p1.x;
555
	events[j].edge = &edges[k];
556
	j++;
557

            
558
	event_ptrs[j] = &events[j];
559
	events[j].type = CAIRO_BO_EVENT_TYPE_STOP;
560
	events[j].point.y = traps->traps[i].bottom;
561
	events[j].point.x = traps->traps[i].left.p1.x;
562
	events[j].edge = &edges[k];
563
	j++;
564
	k++;
565

            
566
	edges[k].edge.top = traps->traps[i].top;
567
	edges[k].edge.bottom = traps->traps[i].bottom;
568
	edges[k].edge.line = traps->traps[i].right;
569
	edges[k].edge.dir = -1;
570
	edges[k].deferred_trap.right = NULL;
571
	edges[k].prev = NULL;
572
	edges[k].next = NULL;
573

            
574
	event_ptrs[j] = &events[j];
575
	events[j].type = CAIRO_BO_EVENT_TYPE_START;
576
	events[j].point.y = traps->traps[i].top;
577
	events[j].point.x = traps->traps[i].right.p1.x;
578
	events[j].edge = &edges[k];
579
	j++;
580

            
581
	event_ptrs[j] = &events[j];
582
	events[j].type = CAIRO_BO_EVENT_TYPE_STOP;
583
	events[j].point.y = traps->traps[i].bottom;
584
	events[j].point.x = traps->traps[i].right.p1.x;
585
	events[j].edge = &edges[k];
586
	j++;
587
	k++;
588
    }
589

            
590
    _cairo_traps_clear (traps);
591
    status = _cairo_bentley_ottmann_tessellate_rectilinear (event_ptrs, j,
592
							    fill_rule,
593
							    TRUE, traps);
594
    traps->is_rectilinear = TRUE;
595

            
596
    if (events != stack_events)
597
	free (events);
598

            
599
    return status;
600
}