Eliminate self-intersecting strokes.

We refactor the surface fallbacks to convert full strokes and fills to the
intermediate polygon representation (as opposed to before where we
returned the trapezoidal representation). This allow greater flexibility
to choose how then to rasterize the polygon. Where possible we use the
local spans rasteriser for its increased performance, but still have the
option to use the tessellator instead (for example, with the current
Render protocol which does not yet have a polygon image).

In order to accommodate this, the spans interface is tweaked to accept
whole polygons instead of a path and the tessellator is tweaked for speed.

Performance Impact
==================

...
Still measuring, expecting some severe regressions.
...

1 files changed, 49 insertions, 3 deletions

diff --git a/src/cairo-fixed-private.h b/src/cairo-fixed-private.h
index 630f0327c..e3add4aec 100644
--- a/src/cairo-fixed-private.h
+++ b/src/cairo-fixed-private.h
@@ -226,15 +226,61 @@ _cairo_fixed_mul (cairo_fixed_t a, cairo_fixed_t b)
     return _cairo_int64_to_int32(_cairo_int64_rsl (temp, CAIRO_FIXED_FRAC_BITS));
 }
 
-/* computes a * b / c */
+/* computes round (a * b / c) */
 static inline cairo_fixed_t
 _cairo_fixed_mul_div (cairo_fixed_t a, cairo_fixed_t b, cairo_fixed_t c)
 {
     cairo_int64_t ab  = _cairo_int32x32_64_mul (a, b);
     cairo_int64_t c64 = _cairo_int32_to_int64 (c);
-    cairo_int64_t quo = _cairo_int64_divrem (ab, c64).quo;
+    return _cairo_int64_to_int32 (_cairo_int64_divrem (ab, c64).quo);
+}
+
+/* computes floor (a * b / c) */
+static inline cairo_fixed_t
+_cairo_fixed_mul_div_floor (cairo_fixed_t a, cairo_fixed_t b, cairo_fixed_t c)
+{
+    return _cairo_int64_32_div (_cairo_int32x32_64_mul (a, b), c);
+}
+
+
+static inline cairo_fixed_t
+_cairo_edge_compute_intersection_y_for_x (const cairo_point_t *p1,
+					  const cairo_point_t *p2,
+					  cairo_fixed_t x)
+{
+    cairo_fixed_t y, dx;
+
+    if (x == p1->x)
+	return p1->y;
+    if (x == p2->x)
+	return p2->y;
 
-    return _cairo_int64_to_int32(quo);
+    y = p1->y;
+    dx = p2->x - p1->x;
+    if (dx != 0)
+	y += _cairo_fixed_mul_div_floor (x - p1->x, p2->y - p1->y, dx);
+
+    return y;
+}
+
+static inline cairo_fixed_t
+_cairo_edge_compute_intersection_x_for_y (const cairo_point_t *p1,
+					  const cairo_point_t *p2,
+					  cairo_fixed_t y)
+{
+    cairo_fixed_t x, dy;
+
+    if (y == p1->y)
+	return p1->x;
+    if (y == p2->y)
+	return p2->x;
+
+    x = p1->x;
+    dy = p2->y - p1->y;
+    if (dy != 0)
+	x += _cairo_fixed_mul_div_floor (y - p1->y, p2->x - p1->x, dy);
+
+    return x;
 }
 
 #else