1
/* -*- Mode: c; tab-width: 8; c-basic-offset: 4; indent-tabs-mode: t; -*- */
3
* Copyright © 2002 Keith Packard
4
* Copyright © 2007 Red Hat, Inc.
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.
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., 59 Temple Place, Suite 330, Boston, MA 02111-1307 USA
17
* You should have received a copy of the MPL along with this library
18
* in the file COPYING-MPL-1.1
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/
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.
29
* The Original Code is the cairo graphics library.
31
* The Initial Developer of the Original Code is Keith Packard
34
* Keith R. Packard <keithp@keithp.com>
35
* Carl D. Worth <cworth@cworth.org>
37
* 2002-07-15: Converted from XRenderCompositeDoublePoly to #cairo_trap_t. Carl D. Worth
42
/* private functions */
45
_compare_point_fixed_by_y (const void *av, const void *bv);
48
_cairo_traps_init (cairo_traps_t *traps)
50
traps->status = CAIRO_STATUS_SUCCESS;
54
traps->traps_size = ARRAY_LENGTH (traps->traps_embedded);
55
traps->traps = traps->traps_embedded;
56
traps->extents.p1.x = traps->extents.p1.y = INT32_MAX;
57
traps->extents.p2.x = traps->extents.p2.y = INT32_MIN;
59
traps->has_limits = FALSE;
63
_cairo_traps_limit (cairo_traps_t *traps,
66
traps->has_limits = TRUE;
68
traps->limits = *limits;
72
_cairo_traps_get_limit (cairo_traps_t *traps,
75
*limits = traps->limits;
76
return traps->has_limits;
80
_cairo_traps_clear (cairo_traps_t *traps)
82
traps->status = CAIRO_STATUS_SUCCESS;
88
_cairo_traps_fini (cairo_traps_t *traps)
90
if (traps->traps != traps->traps_embedded)
95
* _cairo_traps_init_box:
96
* @traps: a #cairo_traps_t
97
* @box: a box that will be converted to a single trapezoid
100
* Initializes a #cairo_traps_t to contain a single rectangular
104
_cairo_traps_init_box (cairo_traps_t *traps,
105
const cairo_box_t *box)
107
_cairo_traps_init (traps);
109
assert (traps->traps_size >= 1);
111
traps->num_traps = 1;
113
traps->traps[0].top = box->p1.y;
114
traps->traps[0].bottom = box->p2.y;
115
traps->traps[0].left.p1 = box->p1;
116
traps->traps[0].left.p2.x = box->p1.x;
117
traps->traps[0].left.p2.y = box->p2.y;
118
traps->traps[0].right.p1.x = box->p2.x;
119
traps->traps[0].right.p1.y = box->p1.y;
120
traps->traps[0].right.p2 = box->p2;
122
traps->extents = *box;
125
/* make room for at least one more trap */
127
_cairo_traps_grow (cairo_traps_t *traps)
129
cairo_trapezoid_t *new_traps;
130
int new_size = 2 * MAX (traps->traps_size, 16);
132
if (traps->traps == traps->traps_embedded) {
133
new_traps = _cairo_malloc_ab (new_size, sizeof (cairo_trapezoid_t));
134
if (new_traps != NULL)
135
memcpy (new_traps, traps->traps, sizeof (traps->traps_embedded));
137
new_traps = _cairo_realloc_ab (traps->traps,
138
new_size, sizeof (cairo_trapezoid_t));
141
if (new_traps == NULL) {
142
traps->status = _cairo_error (CAIRO_STATUS_NO_MEMORY);
146
traps->traps = new_traps;
147
traps->traps_size = new_size;
152
_cairo_traps_add_trap (cairo_traps_t *traps,
153
cairo_fixed_t top, cairo_fixed_t bottom,
154
cairo_line_t *left, cairo_line_t *right)
156
cairo_trapezoid_t *trap;
158
/* Note: With the goofy trapezoid specification, (where an
159
* arbitrary two points on the lines can specified for the left
160
* and right edges), these limit checks would not work in
161
* general. For example, one can imagine a trapezoid entirely
162
* within the limits, but with two points used to specify the left
163
* edge entirely to the right of the limits. Fortunately, for our
164
* purposes, cairo will never generate such a crazy
165
* trapezoid. Instead, cairo always uses for its points the
166
* extreme positions of the edge that are visible on at least some
167
* trapezoid. With this constraint, it's impossible for both
168
* points to be outside the limits while the relevant edge is
169
* entirely inside the limits.
171
if (traps->has_limits) {
172
/* Trivially reject if trapezoid is entirely to the right or
173
* to the left of the limits. */
174
if (left->p1.x >= traps->limits.p2.x &&
175
left->p2.x >= traps->limits.p2.x)
180
if (right->p1.x <= traps->limits.p1.x &&
181
right->p2.x <= traps->limits.p1.x)
186
/* And reject if the trapezoid is entirely above or below */
187
if (top > traps->limits.p2.y || bottom < traps->limits.p1.y)
190
/* Otherwise, clip the trapezoid to the limits. We only clip
191
* where an edge is entirely outside the limits. If we wanted
192
* to be more clever, we could handle cases where a trapezoid
193
* edge intersects the edge of the limits, but that would
194
* require slicing this trapezoid into multiple trapezoids,
195
* and I'm not sure the effort would be worth it. */
196
if (top < traps->limits.p1.y)
197
top = traps->limits.p1.y;
199
if (bottom > traps->limits.p2.y)
200
bottom = traps->limits.p2.y;
202
if (left->p1.x <= traps->limits.p1.x &&
203
left->p2.x <= traps->limits.p1.x)
205
left->p1.x = traps->limits.p1.x;
206
left->p2.x = traps->limits.p1.x;
209
if (right->p1.x >= traps->limits.p2.x &&
210
right->p2.x >= traps->limits.p2.x)
212
right->p1.x = traps->limits.p2.x;
213
right->p2.x = traps->limits.p2.x;
221
if (traps->num_traps == traps->traps_size) {
222
if (! _cairo_traps_grow (traps))
226
trap = &traps->traps[traps->num_traps];
228
trap->bottom = bottom;
230
trap->right = *right;
232
if (top < traps->extents.p1.y)
233
traps->extents.p1.y = top;
234
if (bottom > traps->extents.p2.y)
235
traps->extents.p2.y = bottom;
237
* This isn't generally accurate, but it is close enough for
238
* this purpose. Assuming that the left and right segments always
239
* contain the trapezoid vertical extents, these compares will
240
* yield a containing box. Assuming that the points all come from
241
* the same figure which will eventually be completely drawn, then
242
* the compares will yield the correct overall extents
244
if (left->p1.x < traps->extents.p1.x)
245
traps->extents.p1.x = left->p1.x;
246
if (left->p2.x < traps->extents.p1.x)
247
traps->extents.p1.x = left->p2.x;
249
if (right->p1.x > traps->extents.p2.x)
250
traps->extents.p2.x = right->p1.x;
251
if (right->p2.x > traps->extents.p2.x)
252
traps->extents.p2.x = right->p2.x;
258
_compare_point_fixed_by_y (const void *av, const void *bv)
260
const cairo_point_t *a = av, *b = bv;
262
int ret = a->y - b->y;
270
_cairo_traps_translate (cairo_traps_t *traps, int x, int y)
272
cairo_fixed_t xoff, yoff;
273
cairo_trapezoid_t *t;
276
/* Ugh. The cairo_composite/(Render) interface doesn't allow
277
an offset for the trapezoids. Need to manually shift all
278
the coordinates to align with the offset origin of the
279
intermediate surface. */
281
xoff = _cairo_fixed_from_int (x);
282
yoff = _cairo_fixed_from_int (y);
284
for (i = 0, t = traps->traps; i < traps->num_traps; i++, t++) {
287
t->left.p1.x += xoff;
288
t->left.p1.y += yoff;
289
t->left.p2.x += xoff;
290
t->left.p2.y += yoff;
291
t->right.p1.x += xoff;
292
t->right.p1.y += yoff;
293
t->right.p2.x += xoff;
294
t->right.p2.y += yoff;
299
_cairo_trapezoid_array_translate_and_scale (cairo_trapezoid_t *offset_traps,
300
cairo_trapezoid_t *src_traps,
302
double tx, double ty,
303
double sx, double sy)
306
cairo_fixed_t xoff = _cairo_fixed_from_double (tx);
307
cairo_fixed_t yoff = _cairo_fixed_from_double (ty);
309
if (sx == 1.0 && sy == 1.0) {
310
for (i = 0; i < num_traps; i++) {
311
offset_traps[i].top = src_traps[i].top + yoff;
312
offset_traps[i].bottom = src_traps[i].bottom + yoff;
313
offset_traps[i].left.p1.x = src_traps[i].left.p1.x + xoff;
314
offset_traps[i].left.p1.y = src_traps[i].left.p1.y + yoff;
315
offset_traps[i].left.p2.x = src_traps[i].left.p2.x + xoff;
316
offset_traps[i].left.p2.y = src_traps[i].left.p2.y + yoff;
317
offset_traps[i].right.p1.x = src_traps[i].right.p1.x + xoff;
318
offset_traps[i].right.p1.y = src_traps[i].right.p1.y + yoff;
319
offset_traps[i].right.p2.x = src_traps[i].right.p2.x + xoff;
320
offset_traps[i].right.p2.y = src_traps[i].right.p2.y + yoff;
323
cairo_fixed_t xsc = _cairo_fixed_from_double (sx);
324
cairo_fixed_t ysc = _cairo_fixed_from_double (sy);
326
for (i = 0; i < num_traps; i++) {
327
offset_traps[i].top = _cairo_fixed_mul (src_traps[i].top + yoff, ysc);
328
offset_traps[i].bottom = _cairo_fixed_mul (src_traps[i].bottom + yoff, ysc);
329
offset_traps[i].left.p1.x = _cairo_fixed_mul (src_traps[i].left.p1.x + xoff, xsc);
330
offset_traps[i].left.p1.y = _cairo_fixed_mul (src_traps[i].left.p1.y + yoff, ysc);
331
offset_traps[i].left.p2.x = _cairo_fixed_mul (src_traps[i].left.p2.x + xoff, xsc);
332
offset_traps[i].left.p2.y = _cairo_fixed_mul (src_traps[i].left.p2.y + yoff, ysc);
333
offset_traps[i].right.p1.x = _cairo_fixed_mul (src_traps[i].right.p1.x + xoff, xsc);
334
offset_traps[i].right.p1.y = _cairo_fixed_mul (src_traps[i].right.p1.y + yoff, ysc);
335
offset_traps[i].right.p2.x = _cairo_fixed_mul (src_traps[i].right.p2.x + xoff, xsc);
336
offset_traps[i].right.p2.y = _cairo_fixed_mul (src_traps[i].right.p2.y + yoff, ysc);
341
/* A triangle is simply a degenerate case of a convex
342
* quadrilateral. We would not benefit from having any distinct
343
* implementation of triangle vs. quadrilateral tessellation here. */
345
_cairo_traps_tessellate_triangle (cairo_traps_t *traps,
346
const cairo_point_t t[3])
348
cairo_point_t quad[4];
355
return _cairo_traps_tessellate_convex_quad (traps, quad);
359
_cairo_traps_tessellate_rectangle (cairo_traps_t *traps,
360
const cairo_point_t *top_left,
361
const cairo_point_t *bottom_right)
366
left.p1.x = left.p2.x = top_left->x;
367
left.p1.y = right.p1.y = top_left->y;
368
right.p1.x = right.p2.x = bottom_right->x;
369
left.p2.y = right.p2.y = bottom_right->y;
371
_cairo_traps_add_trap (traps, top_left->y, bottom_right->y, &left, &right);
373
return traps->status;
377
_cairo_traps_tessellate_convex_quad (cairo_traps_t *traps,
378
const cairo_point_t q[4])
382
cairo_slope_t ab, ad;
383
cairo_bool_t b_left_of_d;
387
/* Choose a as a point with minimal y */
389
for (i = 1; i < 4; i++)
390
if (_compare_point_fixed_by_y (&q[i], &q[a]) < 0)
393
/* b and d are adjacent to a, while c is opposite */
398
/* Choose between b and d so that b.y is less than d.y */
399
if (_compare_point_fixed_by_y (&q[d], &q[b]) < 0) {
404
/* Without freedom left to choose anything else, we have four
405
* cases to tessellate.
407
* First, we have to determine the Y-axis sort of the four
408
* vertices, (either abcd or abdc). After that we need to detemine
409
* which edges will be "left" and which will be "right" in the
410
* resulting trapezoids. This can be determined by computing a
411
* slope comparison of ab and ad to determine if b is left of d or
414
* Note that "left of" here is in the sense of which edges should
415
* be the left vs. right edges of the trapezoid. In particular, b
416
* left of d does *not* mean that b.x is less than d.x.
418
* This should hopefully be made clear in the lame ASCII art
419
* below. Since the same slope comparison is used in all cases, we
420
* compute it before testing for the Y-value sort. */
422
/* Note: If a == b then the ab slope doesn't give us any
423
* information. In that case, we can replace it with the ac (or
424
* equivalenly the bc) slope which gives us exactly the same
425
* information we need. At worst the names of the identifiers ab
426
* and b_left_of_d are inaccurate in this case, (would be ac, and
428
if (q[a].x == q[b].x && q[a].y == q[b].y)
429
_cairo_slope_init (&ab, &q[a], &q[c]);
431
_cairo_slope_init (&ab, &q[a], &q[b]);
433
_cairo_slope_init (&ad, &q[a], &q[d]);
435
b_left_of_d = (_cairo_slope_compare (&ab, &ad) > 0);
437
if (q[c].y <= q[d].y) {
439
/* Y-sort is abcd and b is left of d, (slope(ab) > slope (ad))
443
* / / /| |\ a.y b.y ab ad
445
* / / | | \ \ b.y c.y bc ad
447
* | / \| \ \ c.y d.y cd ad
450
left.p1 = q[a]; left.p2 = q[b];
451
right.p1 = q[a]; right.p2 = q[d];
452
_cairo_traps_add_trap (traps, q[a].y, q[b].y, &left, &right);
453
left.p1 = q[b]; left.p2 = q[c];
454
_cairo_traps_add_trap (traps, q[b].y, q[c].y, &left, &right);
455
left.p1 = q[c]; left.p2 = q[d];
456
_cairo_traps_add_trap (traps, q[c].y, q[d].y, &left, &right);
458
/* Y-sort is abcd and b is right of d, (slope(ab) <= slope (ad))
461
* /| |\ \ \ a.y b.y ad ab
463
* / / | | \ \ b.y c.y ad bc
465
* / / |/ \ | c.y d.y ad cd
468
left.p1 = q[a]; left.p2 = q[d];
469
right.p1 = q[a]; right.p2 = q[b];
470
_cairo_traps_add_trap (traps, q[a].y, q[b].y, &left, &right);
471
right.p1 = q[b]; right.p2 = q[c];
472
_cairo_traps_add_trap (traps, q[b].y, q[c].y, &left, &right);
473
right.p1 = q[c]; right.p2 = q[d];
474
_cairo_traps_add_trap (traps, q[c].y, q[d].y, &left, &right);
478
/* Y-sort is abdc and b is left of d, (slope (ab) > slope (ad))
481
* // / \ |\ a.y b.y ab ad
483
* / / \ \ \ \ b.y d.y bc ad
485
* // \ / \| d.y c.y bc dc
488
left.p1 = q[a]; left.p2 = q[b];
489
right.p1 = q[a]; right.p2 = q[d];
490
_cairo_traps_add_trap (traps, q[a].y, q[b].y, &left, &right);
491
left.p1 = q[b]; left.p2 = q[c];
492
_cairo_traps_add_trap (traps, q[b].y, q[d].y, &left, &right);
493
right.p1 = q[d]; right.p2 = q[c];
494
_cairo_traps_add_trap (traps, q[d].y, q[c].y, &left, &right);
496
/* Y-sort is abdc and b is right of d, (slope (ab) <= slope (ad))
499
* /| / \ \\ a.y b.y ad ab
501
* / / / / \ \ b.y d.y ad bc
503
* |/ \ / \\ d.y c.y dc bc
506
left.p1 = q[a]; left.p2 = q[d];
507
right.p1 = q[a]; right.p2 = q[b];
508
_cairo_traps_add_trap (traps, q[a].y, q[b].y, &left, &right);
509
right.p1 = q[b]; right.p2 = q[c];
510
_cairo_traps_add_trap (traps, q[b].y, q[d].y, &left, &right);
511
left.p1 = q[d]; left.p2 = q[c];
512
_cairo_traps_add_trap (traps, q[d].y, q[c].y, &left, &right);
516
return traps->status;
520
_cairo_trap_contains (cairo_trapezoid_t *t, cairo_point_t *pt)
522
cairo_slope_t slope_left, slope_pt, slope_right;
526
if (t->bottom < pt->y)
529
_cairo_slope_init (&slope_left, &t->left.p1, &t->left.p2);
530
_cairo_slope_init (&slope_pt, &t->left.p1, pt);
532
if (_cairo_slope_compare (&slope_left, &slope_pt) < 0)
535
_cairo_slope_init (&slope_right, &t->right.p1, &t->right.p2);
536
_cairo_slope_init (&slope_pt, &t->right.p1, pt);
538
if (_cairo_slope_compare (&slope_pt, &slope_right) < 0)
545
_cairo_traps_contain (const cairo_traps_t *traps,
551
point.x = _cairo_fixed_from_double (x);
552
point.y = _cairo_fixed_from_double (y);
554
for (i = 0; i < traps->num_traps; i++) {
555
if (_cairo_trap_contains (&traps->traps[i], &point))
563
_cairo_traps_extents (const cairo_traps_t *traps,
564
cairo_box_t *extents)
566
if (traps->num_traps == 0) {
567
extents->p1.x = extents->p1.y = _cairo_fixed_from_int (0);
568
extents->p2.x = extents->p2.y = _cairo_fixed_from_int (0);
570
*extents = traps->extents;
571
if (traps->has_limits) {
572
/* clip the traps to the imposed limits */
573
if (extents->p1.x < traps->limits.p1.x)
574
extents->p1.x = traps->limits.p1.x;
575
if (extents->p2.x > traps->limits.p2.x)
576
extents->p2.x = traps->limits.p2.x;
578
if (extents->p1.y < traps->limits.p1.y)
579
extents->p1.y = traps->limits.p1.y;
580
if (extents->p2.y > traps->limits.p2.y)
581
extents->p2.y = traps->limits.p2.y;
587
* _cairo_traps_extract_region:
588
* @traps: a #cairo_traps_t
589
* @region: a #cairo_region_t
591
* Determines if a set of trapezoids are exactly representable as a
592
* cairo region. If so, the passed-in region is initialized to
593
* the area representing the given traps. It should be finalized
594
* with _cairo_region_fini(). If not, %CAIRO_INT_STATUS_UNSUPPORTED
597
* Return value: %CAIRO_STATUS_SUCCESS, %CAIRO_INT_STATUS_UNSUPPORTED
598
* or %CAIRO_STATUS_NO_MEMORY
601
_cairo_traps_extract_region (const cairo_traps_t *traps,
602
cairo_region_t *region)
604
cairo_box_int_t stack_boxes[CAIRO_STACK_ARRAY_LENGTH (cairo_box_int_t)];
605
cairo_box_int_t *boxes = stack_boxes;
607
cairo_int_status_t status;
609
for (i = 0; i < traps->num_traps; i++)
610
if (!(traps->traps[i].left.p1.x == traps->traps[i].left.p2.x
611
&& traps->traps[i].right.p1.x == traps->traps[i].right.p2.x
612
&& _cairo_fixed_is_integer(traps->traps[i].top)
613
&& _cairo_fixed_is_integer(traps->traps[i].bottom)
614
&& _cairo_fixed_is_integer(traps->traps[i].left.p1.x)
615
&& _cairo_fixed_is_integer(traps->traps[i].right.p1.x))) {
616
return CAIRO_INT_STATUS_UNSUPPORTED;
619
if (traps->num_traps > ARRAY_LENGTH(stack_boxes)) {
620
boxes = _cairo_malloc_ab (traps->num_traps, sizeof(cairo_box_int_t));
623
return _cairo_error (CAIRO_STATUS_NO_MEMORY);
628
for (i = 0; i < traps->num_traps; i++) {
629
int x1 = _cairo_fixed_integer_part(traps->traps[i].left.p1.x);
630
int y1 = _cairo_fixed_integer_part(traps->traps[i].top);
631
int x2 = _cairo_fixed_integer_part(traps->traps[i].right.p1.x);
632
int y2 = _cairo_fixed_integer_part(traps->traps[i].bottom);
634
/* XXX: Sometimes we get degenerate trapezoids from the tesellator;
637
if (x1 == x2 || y1 == y2)
640
boxes[box_count].p1.x = x1;
641
boxes[box_count].p1.y = y1;
642
boxes[box_count].p2.x = x2;
643
boxes[box_count].p2.y = y2;
648
status = _cairo_region_init_boxes (region, boxes, box_count);
650
if (boxes != stack_boxes)
654
_cairo_region_fini (region);
659
/* moves trap points such that they become the actual corners of the trapezoid */
661
_sanitize_trap (cairo_trapezoid_t *t)
663
cairo_trapezoid_t s = *t;
665
#define FIX(lr, tb, p) \
666
if (t->lr.p.y != t->tb) { \
667
t->lr.p.x = s.lr.p2.x + _cairo_fixed_mul_div (s.lr.p1.x - s.lr.p2.x, s.tb - s.lr.p2.y, s.lr.p1.y - s.lr.p2.y); \
671
FIX (left, bottom, p2);
672
FIX (right, top, p1);
673
FIX (right, bottom, p2);
676
cairo_private cairo_status_t
677
_cairo_traps_path (const cairo_traps_t *traps,
678
cairo_path_fixed_t *path)
682
for (i = 0; i < traps->num_traps; i++) {
683
cairo_status_t status;
684
cairo_trapezoid_t trap = traps->traps[i];
686
if (trap.top == trap.bottom)
689
_sanitize_trap (&trap);
691
status = _cairo_path_fixed_move_to (path, trap.left.p1.x, trap.top);
692
if (status) return status;
693
status = _cairo_path_fixed_line_to (path, trap.right.p1.x, trap.top);
694
if (status) return status;
695
status = _cairo_path_fixed_line_to (path, trap.right.p2.x, trap.bottom);
696
if (status) return status;
697
status = _cairo_path_fixed_line_to (path, trap.left.p2.x, trap.bottom);
698
if (status) return status;
699
status = _cairo_path_fixed_close_path (path);
700
if (status) return status;
703
return CAIRO_STATUS_SUCCESS;
added
removed
cairo/src/cairo-traps.c
