[cairo-commit] 5 commits - src/cairo-bentley-ottmann.c src/cairo-traps.c src/cairo-wideint-private.h src/cairo-xlib-surface.c
Chris Wilson
ickle at kemper.freedesktop.org
Sat Oct 4 02:18:46 PDT 2008
src/cairo-bentley-ottmann.c | 103 ++++++++++++++++++++++++--------------------
src/cairo-traps.c | 13 ++++-
src/cairo-wideint-private.h | 1
src/cairo-xlib-surface.c | 39 +++++++++-------
4 files changed, 92 insertions(+), 64 deletions(-)
New commits:
commit ab23c2995356821537b9a0facdff87c339a05d2a
Author: Chris Wilson <chris at chris-wilson.co.uk>
Date: Wed Oct 1 12:18:16 2008 +0100
[tessellator] Direct comparison of result in edges_compare_x_for_y.
We need to compare the x-coordinate of a line at a for a particular y,
without loss of precision.
The x-coordinate along an edge for a given y is:
X = A_x + (Y - A_y) * A_dx / A_dy
So the inequality we wish to test is:
A_x + (Y - A_y) * A_dx / A_dy -?- B_x + (Y - B_y) * B_dx / B_dy,
where -?- is our inequality operator.
By construction we know that A_dy and B_dy (and (Y - A_y), (Y - B_y)) are
all positive, so we can rearrange it thus without causing a sign
change:
A_dy * B_dy * (A_x - B_x) -?- (Y - B_y) * B_dx * A_dy
- (Y - A_y) * A_dx * B_dy
Given the assumption that all the deltas fit within 32 bits, we can compute
this comparison directly using 128 bit arithmetic.
diff --git a/src/cairo-bentley-ottmann.c b/src/cairo-bentley-ottmann.c
index a78745d..ddcd9f0 100644
--- a/src/cairo-bentley-ottmann.c
+++ b/src/cairo-bentley-ottmann.c
@@ -219,42 +219,66 @@ _slope_compare (cairo_bo_edge_t *a,
}
}
-static cairo_quorem64_t
-edge_x_for_y (cairo_bo_edge_t *edge,
- int32_t y)
+/*
+ * We need to compare the x-coordinate of a line for a particular y,
+ * without loss of precision.
+ *
+ * The x-coordinate along an edge for a given y is:
+ * X = A_x + (Y - A_y) * A_dx / A_dy
+ *
+ * So the inequality we wish to test is:
+ * A_x + (Y - A_y) * A_dx / A_dy -?- B_x + (Y - B_y) * B_dx / B_dy,
+ * where -?- is our inequality operator.
+ *
+ * By construction, we know that A_dy and B_dy (and (Y - A_y), (Y - B_y)) are
+ * all positive, so we can rearrange it thus without causing a sign change:
+ * A_dy * B_dy * (A_x - B_x) -?- (Y - B_y) * B_dx * A_dy
+ * - (Y - A_y) * A_dx * B_dy
+ *
+ * Given the assumption that all the deltas fit within 32 bits, we can compute
+ * this comparison directly using 128 bit arithmetic.
+ *
+ * (And put the burden of the work on developing fast 128 bit ops, which are
+ * required throughout the tessellator.)
+ *
+ * See the similar discussion for _slope_compare().
+ */
+static int
+edges_compare_x_for_y (const cairo_bo_edge_t *a,
+ const cairo_bo_edge_t *b,
+ int32_t y)
{
/* XXX: We're assuming here that dx and dy will still fit in 32
* bits. That's not true in general as there could be overflow. We
* should prevent that before the tessellation algorithm
* begins.
*/
- int32_t dx = edge->bottom.x - edge->top.x;
- int32_t dy = edge->bottom.y - edge->top.y;
- int64_t numerator;
- cairo_quorem64_t quorem;
-
- if (edge->middle.y == y) {
- quorem.quo = edge->middle.x;
- quorem.rem = 0;
- return quorem;
- }
- if (edge->bottom.y == y) {
- quorem.quo = edge->bottom.x;
- quorem.rem = 0;
- return quorem;
- }
- if (dy == 0) {
- quorem.quo = _cairo_int32_to_int64 (edge->top.x);
- quorem.rem = 0;
- return quorem;
- }
+ int32_t adx, ady;
+ int32_t bdx, bdy;
+ cairo_int128_t L, R;
+
+ adx = a->bottom.x - a->top.x;
+ ady = a->bottom.y - a->top.y;
- /* edge->top.x + (y - edge->top.y) * dx / dy */
- numerator = _cairo_int32x32_64_mul ((y - edge->top.y), dx);
- quorem = _cairo_int64_divrem (numerator, dy);
- quorem.quo += edge->top.x;
+ bdx = b->bottom.x - b->top.x;
+ bdy = b->bottom.y - b->top.y;
- return quorem;
+ L = _cairo_int64x32_128_mul (_cairo_int32x32_64_mul (ady, bdy),
+ a->top.x - b->top.x);
+
+ R = _cairo_int128_sub (_cairo_int64x32_128_mul (_cairo_int32x32_64_mul (bdx,
+ ady),
+ y - b->top.y),
+ _cairo_int64x32_128_mul (_cairo_int32x32_64_mul (adx,
+ bdy),
+ y - a->top.y));
+
+ /* return _cairo_int128_cmp (L, R); */
+ if (_cairo_int128_lt (L, R))
+ return -1;
+ if (_cairo_int128_gt (L, R))
+ return 1;
+ return 0;
}
static int
@@ -262,8 +286,6 @@ _cairo_bo_sweep_line_compare_edges (cairo_bo_sweep_line_t *sweep_line,
cairo_bo_edge_t *a,
cairo_bo_edge_t *b)
{
- cairo_quorem64_t ax;
- cairo_quorem64_t bx;
int cmp;
if (a == b)
@@ -292,18 +314,9 @@ _cairo_bo_sweep_line_compare_edges (cairo_bo_sweep_line_t *sweep_line,
if (amin > bmax) return +1;
}
- ax = edge_x_for_y (a, sweep_line->current_y);
- bx = edge_x_for_y (b, sweep_line->current_y);
- if (ax.quo > bx.quo)
- return 1;
- else if (ax.quo < bx.quo)
- return -1;
-
- /* Quotients are identical, test remainder. */
- if (ax.rem > bx.rem)
- return 1;
- else if (ax.rem < bx.rem)
- return -1;
+ cmp = edges_compare_x_for_y (a, b, sweep_line->current_y);
+ if (cmp)
+ return cmp;
/* The two edges intersect exactly at y, so fall back on slope
* comparison. We know that this compare_edges function will be
diff --git a/src/cairo-wideint-private.h b/src/cairo-wideint-private.h
index 412fc00..0738042 100644
--- a/src/cairo-wideint-private.h
+++ b/src/cairo-wideint-private.h
@@ -181,6 +181,7 @@ cairo_int128_t I _cairo_int64_to_int128 (cairo_int64_t i);
#define _cairo_int128_sub(a,b) _cairo_uint128_sub(a,b)
#define _cairo_int128_mul(a,b) _cairo_uint128_mul(a,b)
cairo_int128_t I _cairo_int64x64_128_mul (cairo_int64_t a, cairo_int64_t b);
+#define _cairo_int64x32_128_mul(a, b) _cairo_int64x64_128_mul(a, _cairo_int32_to_int64(b))
#define _cairo_int128_lsl(a,b) _cairo_uint128_lsl(a,b)
#define _cairo_int128_rsl(a,b) _cairo_uint128_rsl(a,b)
#define _cairo_int128_rsa(a,b) _cairo_uint128_rsa(a,b)
commit 7db03ac68cd556c903c07a2e2f8b75ec51263d12
Author: Chris Wilson <chris at chris-wilson.co.uk>
Date: Wed Oct 1 12:34:36 2008 +0100
[tessellator] Use abort() instead of exit().
More friendly when debugging, as the debug will (by default) catch the
SIGTRAP and break at the offending test.
diff --git a/src/cairo-bentley-ottmann.c b/src/cairo-bentley-ottmann.c
index 6e46476..a78745d 100644
--- a/src/cairo-bentley-ottmann.c
+++ b/src/cairo-bentley-ottmann.c
@@ -547,7 +547,7 @@ intersect_lines (cairo_bo_edge_t *a,
qr = _cairo_int_96by64_32x64_divrem (det64_128 (a_det, dx1,
b_det, dx2),
den_det);
- if (_cairo_int64_eq (qr.rem,den_det))
+ if (_cairo_int64_eq (qr.rem, den_det))
return CAIRO_BO_STATUS_NO_INTERSECTION;
intersection->x.ordinate = qr.quo;
intersection->x.exactness = qr.rem ? INEXACT : EXACT;
@@ -1196,13 +1196,13 @@ _cairo_bo_sweep_line_validate (cairo_bo_sweep_line_t *sweep_line)
{
if (SKIP_ELT_TO_EDGE (elt) != edge) {
fprintf (stderr, "*** Error: Sweep line fails to validate: Inconsistent data in the two lists.\n");
- exit (1);
+ abort ();
}
}
if (edge || elt) {
fprintf (stderr, "*** Error: Sweep line fails to validate: One list ran out before the other.\n");
- exit (1);
+ abort ();
}
}
#endif
commit 59e569576d00e9c1cb66a77cf447c3cc3fb038e7
Author: Chris Wilson <chris at chris-wilson.co.uk>
Date: Sun Sep 28 19:04:39 2008 +0100
[traps] Discard trivially empty trapezoid.
The convex_quad tessellator (and possibly even the more general polygon
tessellator) will generate empty trapezoids when given a
rectangle which can be trivially discarded before inserting into traps.
diff --git a/src/cairo-traps.c b/src/cairo-traps.c
index 042a89e..b76e908 100644
--- a/src/cairo-traps.c
+++ b/src/cairo-traps.c
@@ -216,9 +216,16 @@ _cairo_traps_add_trap (cairo_traps_t *traps,
}
}
- if (top >= bottom) {
+ /* Trivial discards for empty trapezoids that are likely to be produced
+ * by our tessellators (most notably convex_quad when given a simple
+ * rectangle).
+ */
+ if (top >= bottom)
+ return;
+ /* cheap colinearity check */
+ if (right->p1.x <= left->p1.x && right->p1.y == left->p1.y &&
+ right->p2.x <= left->p2.x && right->p2.y == left->p2.y)
return;
- }
if (traps->num_traps == traps->traps_size) {
if (! _cairo_traps_grow (traps))
commit 7a2329e9c8afbfecb88c6c50bd63aa03ea7f9f81
Author: Chris Wilson <chris at chris-wilson.co.uk>
Date: Wed Oct 1 09:49:45 2008 +0100
[traps] Reset extents on clearing.
When clearing the array of current trapezoids, reset the extents to
infinite so that they are properly recomputed.
diff --git a/src/cairo-traps.c b/src/cairo-traps.c
index 3a38c69..042a89e 100644
--- a/src/cairo-traps.c
+++ b/src/cairo-traps.c
@@ -82,6 +82,8 @@ _cairo_traps_clear (cairo_traps_t *traps)
traps->status = CAIRO_STATUS_SUCCESS;
traps->num_traps = 0;
+ traps->extents.p1.x = traps->extents.p1.y = INT32_MAX;
+ traps->extents.p2.x = traps->extents.p2.y = INT32_MIN;
}
void
commit 8ec24a443d45b012df9b1a14b00a0b5b1c43e2ea
Author: Chris Wilson <chris at chris-wilson.co.uk>
Date: Tue Sep 30 23:19:01 2008 +0100
[xlib] Share the common conditions for starting a new xGlyphElt using a macro.
Move the predicate for starting a new glyph elt into a macro so that it
can be shared between _cairo_xlib_surface_emit_glyphs() and
_emit_glyph_chunks() without code duplication.
diff --git a/src/cairo-xlib-surface.c b/src/cairo-xlib-surface.c
index 80873b6..0b01762 100644
--- a/src/cairo-xlib-surface.c
+++ b/src/cairo-xlib-surface.c
@@ -3548,6 +3548,17 @@ typedef union {
/* compile-time assert that #cairo_xlib_glyph_t is the same size as #cairo_glyph_t */
COMPILE_TIME_ASSERT (sizeof (cairo_xlib_glyph_t) == sizeof (cairo_glyph_t));
+/* Start a new element for the first glyph,
+ * or for any glyph that has unexpected position,
+ * or if current element has too many glyphs
+ * (Xrender limits each element to 252 glyphs, we limit them to 128)
+ *
+ * These same conditions need to be mirrored between
+ * _cairo_xlib_surface_emit_glyphs and _emit_glyph_chunks
+ */
+#define _start_new_glyph_elt(count, glyph) \
+ (((count) & 127) == 0 || (glyph)->i.x || (glyph)->i.y)
+
static cairo_status_t
_emit_glyphs_chunk (cairo_xlib_surface_t *dst,
cairo_xlib_glyph_t *glyphs,
@@ -3610,19 +3621,13 @@ _emit_glyphs_chunk (cairo_xlib_surface_t *dst,
j = 0;
for (i = 0; i < num_glyphs; i++) {
- /* Start a new element for first output glyph, and for glyphs with
- * unexpected position */
- /* Start a new element for the first glyph,
+ /* Start a new element for first output glyph,
* or for any glyph that has unexpected position,
- * or if current element has too many glyphs
- * (Xrender limits each element to 252 glyphs, we limit them to 128)
+ * or if current element has too many glyphs.
*
- * Note that the first condition is redundant with the introduction
- * of the third one. Keep for clarity.
- *
- * These same conditions are mirrored in _cairo_xlib_surface_emit_glyphs
+ * These same conditions are mirrored in _cairo_xlib_surface_emit_glyphs()
*/
- if (!j || glyphs[i].i.x || glyphs[i].i.y || j % 128 == 0) {
+ if (_start_new_glyph_elt (j, &glyphs[i])) {
if (j) {
elts[nelt].nchars = n;
nelt++;
@@ -3651,6 +3656,10 @@ _emit_glyphs_chunk (cairo_xlib_surface_t *dst,
n = 0;
}
+ /* Check that we agree with _cairo_xlib_surface_emit_glyphs() on the
+ * expected number of xGlyphElts. */
+ assert (nelt == num_elts);
+
composite_text_func (dst->dpy,
_render_operator (op),
src->src_picture,
@@ -3812,15 +3821,11 @@ _cairo_xlib_surface_emit_glyphs (cairo_xlib_surface_t *dst,
/* Start a new element for the first glyph,
* or for any glyph that has unexpected position,
- * or if current element has too many glyphs
- * (Xrender limits each element to 252 glyphs, we limit them to 128)
- *
- * Note that the first condition is redundant with the introduction
- * of the third one. Keep for clarity.
+ * or if current element has too many glyphs.
*
- * These same conditions are mirrored in _emit_glyphs_chunk
+ * These same conditions are mirrored in _emit_glyphs_chunk().
*/
- if (!num_out_glyphs || glyphs[i].i.x || glyphs[i].i.y || num_out_glyphs % 128 == 0) {
+ if (_start_new_glyph_elt (num_out_glyphs, &glyphs[i])) {
num_elts++;
request_size += _cairo_sz_xGlyphElt;
}
More information about the cairo-commit
mailing list