158
165
trap->right = *right;
169
_cairo_traps_add_clipped_trap (cairo_traps_t *traps,
170
cairo_fixed_t _top, cairo_fixed_t _bottom,
171
cairo_line_t *_left, cairo_line_t *_right)
173
/* Note: With the goofy trapezoid specification, (where an
174
* arbitrary two points on the lines can specified for the left
175
* and right edges), these limit checks would not work in
176
* general. For example, one can imagine a trapezoid entirely
177
* within the limits, but with two points used to specify the left
178
* edge entirely to the right of the limits. Fortunately, for our
179
* purposes, cairo will never generate such a crazy
180
* trapezoid. Instead, cairo always uses for its points the
181
* extreme positions of the edge that are visible on at least some
182
* trapezoid. With this constraint, it's impossible for both
183
* points to be outside the limits while the relevant edge is
184
* entirely inside the limits.
186
if (traps->num_limits) {
187
const cairo_box_t *b = &traps->bounds;
188
cairo_fixed_t top = _top, bottom = _bottom;
189
cairo_line_t left = *_left, right = *_right;
191
/* Trivially reject if trapezoid is entirely to the right or
192
* to the left of the limits. */
193
if (left.p1.x >= b->p2.x && left.p2.x >= b->p2.x)
196
if (right.p1.x <= b->p1.x && right.p2.x <= b->p1.x)
199
/* And reject if the trapezoid is entirely above or below */
200
if (top >= b->p2.y || bottom <= b->p1.y)
203
/* Otherwise, clip the trapezoid to the limits. We only clip
204
* where an edge is entirely outside the limits. If we wanted
205
* to be more clever, we could handle cases where a trapezoid
206
* edge intersects the edge of the limits, but that would
207
* require slicing this trapezoid into multiple trapezoids,
208
* and I'm not sure the effort would be worth it. */
212
if (bottom > b->p2.y)
215
if (left.p1.x <= b->p1.x && left.p2.x <= b->p1.x)
216
left.p1.x = left.p2.x = b->p1.x;
218
if (right.p1.x >= b->p2.x && right.p2.x >= b->p2.x)
219
right.p1.x = right.p2.x = b->p2.x;
221
/* Trivial discards for empty trapezoids that are likely to
222
* be produced by our tessellators (most notably convex_quad
223
* when given a simple rectangle).
228
/* cheap colinearity check */
229
if (right.p1.x <= left.p1.x && right.p1.y == left.p1.y &&
230
right.p2.x <= left.p2.x && right.p2.y == left.p2.y)
233
_cairo_traps_add_trap (traps, top, bottom, &left, &right);
235
_cairo_traps_add_trap (traps, _top, _bottom, _left, _right);
239
_compare_point_fixed_by_y (const void *av, const void *bv)
241
const cairo_point_t *a = av, *b = bv;
242
int ret = a->y - b->y;
249
_cairo_traps_tessellate_convex_quad (cairo_traps_t *traps,
250
const cairo_point_t q[4])
254
cairo_slope_t ab, ad;
255
cairo_bool_t b_left_of_d;
259
/* Choose a as a point with minimal y */
261
for (i = 1; i < 4; i++)
262
if (_compare_point_fixed_by_y (&q[i], &q[a]) < 0)
265
/* b and d are adjacent to a, while c is opposite */
270
/* Choose between b and d so that b.y is less than d.y */
271
if (_compare_point_fixed_by_y (&q[d], &q[b]) < 0) {
276
/* Without freedom left to choose anything else, we have four
277
* cases to tessellate.
279
* First, we have to determine the Y-axis sort of the four
280
* vertices, (either abcd or abdc). After that we need to detemine
281
* which edges will be "left" and which will be "right" in the
282
* resulting trapezoids. This can be determined by computing a
283
* slope comparison of ab and ad to determine if b is left of d or
286
* Note that "left of" here is in the sense of which edges should
287
* be the left vs. right edges of the trapezoid. In particular, b
288
* left of d does *not* mean that b.x is less than d.x.
290
* This should hopefully be made clear in the lame ASCII art
291
* below. Since the same slope comparison is used in all cases, we
292
* compute it before testing for the Y-value sort. */
294
/* Note: If a == b then the ab slope doesn't give us any
295
* information. In that case, we can replace it with the ac (or
296
* equivalenly the bc) slope which gives us exactly the same
297
* information we need. At worst the names of the identifiers ab
298
* and b_left_of_d are inaccurate in this case, (would be ac, and
300
if (q[a].x == q[b].x && q[a].y == q[b].y)
301
_cairo_slope_init (&ab, &q[a], &q[c]);
303
_cairo_slope_init (&ab, &q[a], &q[b]);
305
_cairo_slope_init (&ad, &q[a], &q[d]);
307
b_left_of_d = _cairo_slope_compare (&ab, &ad) > 0;
309
if (q[c].y <= q[d].y) {
311
/* Y-sort is abcd and b is left of d, (slope(ab) > slope (ad))
315
* / / /| |\ a.y b.y ab ad
317
* / / | | \ \ b.y c.y bc ad
319
* | / \| \ \ c.y d.y cd ad
322
left.p1 = q[a]; left.p2 = q[b];
323
right.p1 = q[a]; right.p2 = q[d];
324
_cairo_traps_add_clipped_trap (traps, q[a].y, q[b].y, &left, &right);
325
left.p1 = q[b]; left.p2 = q[c];
326
_cairo_traps_add_clipped_trap (traps, q[b].y, q[c].y, &left, &right);
327
left.p1 = q[c]; left.p2 = q[d];
328
_cairo_traps_add_clipped_trap (traps, q[c].y, q[d].y, &left, &right);
330
/* Y-sort is abcd and b is right of d, (slope(ab) <= slope (ad))
333
* /| |\ \ \ a.y b.y ad ab
335
* / / | | \ \ b.y c.y ad bc
337
* / / |/ \ | c.y d.y ad cd
340
left.p1 = q[a]; left.p2 = q[d];
341
right.p1 = q[a]; right.p2 = q[b];
342
_cairo_traps_add_clipped_trap (traps, q[a].y, q[b].y, &left, &right);
343
right.p1 = q[b]; right.p2 = q[c];
344
_cairo_traps_add_clipped_trap (traps, q[b].y, q[c].y, &left, &right);
345
right.p1 = q[c]; right.p2 = q[d];
346
_cairo_traps_add_clipped_trap (traps, q[c].y, q[d].y, &left, &right);
350
/* Y-sort is abdc and b is left of d, (slope (ab) > slope (ad))
353
* // / \ |\ a.y b.y ab ad
355
* / / \ \ \ \ b.y d.y bc ad
357
* // \ / \| d.y c.y bc dc
360
left.p1 = q[a]; left.p2 = q[b];
361
right.p1 = q[a]; right.p2 = q[d];
362
_cairo_traps_add_clipped_trap (traps, q[a].y, q[b].y, &left, &right);
363
left.p1 = q[b]; left.p2 = q[c];
364
_cairo_traps_add_clipped_trap (traps, q[b].y, q[d].y, &left, &right);
365
right.p1 = q[d]; right.p2 = q[c];
366
_cairo_traps_add_clipped_trap (traps, q[d].y, q[c].y, &left, &right);
368
/* Y-sort is abdc and b is right of d, (slope (ab) <= slope (ad))
371
* /| / \ \\ a.y b.y ad ab
373
* / / / / \ \ b.y d.y ad bc
375
* |/ \ / \\ d.y c.y dc bc
378
left.p1 = q[a]; left.p2 = q[d];
379
right.p1 = q[a]; right.p2 = q[b];
380
_cairo_traps_add_clipped_trap (traps, q[a].y, q[b].y, &left, &right);
381
right.p1 = q[b]; right.p2 = q[c];
382
_cairo_traps_add_clipped_trap (traps, q[b].y, q[d].y, &left, &right);
383
left.p1 = q[d]; left.p2 = q[c];
384
_cairo_traps_add_clipped_trap (traps, q[d].y, q[c].y, &left, &right);
389
/* A triangle is simply a degenerate case of a convex
390
* quadrilateral. We would not benefit from having any distinct
391
* implementation of triangle vs. quadrilateral tessellation here. */
393
_cairo_traps_tessellate_triangle (cairo_traps_t *traps,
394
const cairo_point_t t[3])
396
cairo_point_t quad[4];
403
_cairo_traps_tessellate_convex_quad (traps, quad);
162
408
* _cairo_traps_init_boxes:
163
409
* @traps: a #cairo_traps_t
added
removed
src/cairo-traps.c
