[cairo] [PATCH 1/2] stroke: Fix large line widths for fallback stroke shaper
Martin Robinson
mrobinson at igalia.com
Tue Mar 12 15:16:01 PDT 2013
Fix the test case line-width-tolerance for the fallback stroke shaper.
Instead of drawing quads between spline points, draw triangle based on
the actual spline edges. This roughly follows the approach of the
tristrip and polygonal shapers.
This commit also replaces the fixed point
_lines_intersect_or_are_coincident with slower, floating point
intersection code. _lines_intersect_or_are_coincident was faultily
trying to skip doing an actual division.
---
src/cairo-fixed-private.h | 34 +++++++++++++++++
src/cairo-path-fixed.c | 55 ++++-----------------------
src/cairo-path-stroke.c | 91 ++++++++++++++++++++++++++++++++++++++++-----
3 files changed, 123 insertions(+), 57 deletions(-)
diff --git a/src/cairo-fixed-private.h b/src/cairo-fixed-private.h
index b6cc6be..352ca39 100644
--- a/src/cairo-fixed-private.h
+++ b/src/cairo-fixed-private.h
@@ -352,6 +352,40 @@ _cairo_edge_compute_intersection_x_for_y (const cairo_point_t *p1,
return x;
}
+/* Intersect two segments based on the algorithm described at
+ * http://paulbourke.net/geometry/pointlineplane/. This implementation
+ * uses floating point math. */
+static inline cairo_bool_t
+_slow_segment_intersection (const cairo_point_t *seg1_p1,
+ const cairo_point_t *seg1_p2,
+ const cairo_point_t *seg2_p1,
+ const cairo_point_t *seg2_p2,
+ cairo_point_t *intersection)
+{
+ double denominator, u_a, u_b;
+ double seg1_dx, seg1_dy, seg2_dx, seg2_dy, seg_start_dx, seg_start_dy;
+
+ seg1_dx = _cairo_fixed_to_double (seg1_p2->x - seg1_p1->x);
+ seg1_dy = _cairo_fixed_to_double (seg1_p2->y - seg1_p1->y);
+ seg2_dx = _cairo_fixed_to_double (seg2_p2->x - seg2_p1->x);
+ seg2_dy = _cairo_fixed_to_double (seg2_p2->y - seg2_p1->y);
+ denominator = (seg2_dy * seg1_dx) - (seg2_dx * seg1_dy);
+ if (denominator == 0)
+ return FALSE;
+
+ seg_start_dx = _cairo_fixed_to_double (seg1_p1->x - seg2_p1->x);
+ seg_start_dy = _cairo_fixed_to_double (seg1_p1->y - seg2_p1->y);
+ u_a = ((seg2_dx * seg_start_dy) - (seg2_dy * seg_start_dx)) / denominator;
+ u_b = ((seg1_dx * seg_start_dy) - (seg1_dy * seg_start_dx)) / denominator;
+
+ if (u_a <= 0 || u_a >= 1 || u_b <= 0 || u_b >= 1)
+ return FALSE;
+
+ intersection->x = seg1_p1->x + _cairo_fixed_from_double ((u_a * seg1_dx));
+ intersection->y = seg1_p1->y + _cairo_fixed_from_double ((u_a * seg1_dy));
+ return TRUE;
+}
+
#else
# error Please define multiplication and other operands for your fixed-point type size
#endif
diff --git a/src/cairo-path-fixed.c b/src/cairo-path-fixed.c
index 10a6515..08852a9 100644
--- a/src/cairo-path-fixed.c
+++ b/src/cairo-path-fixed.c
@@ -1299,54 +1299,11 @@ _cairo_path_fixed_is_box (const cairo_path_fixed_t *path,
return FALSE;
}
-/* Determine whether two lines A->B and C->D intersect based on the
- * algorithm described here: http://paulbourke.net/geometry/lineline2d/ */
-static inline cairo_bool_t
-_lines_intersect_or_are_coincident (cairo_point_t a,
- cairo_point_t b,
- cairo_point_t c,
- cairo_point_t d)
-{
- cairo_int64_t numerator_a, numerator_b, denominator;
-
- denominator = _cairo_int64_sub (_cairo_int32x32_64_mul (d.y - c.y, b.x - a.x),
- _cairo_int32x32_64_mul (d.x - c.x, b.y - a.y));
- numerator_a = _cairo_int64_sub (_cairo_int32x32_64_mul (d.x - c.x, a.y - c.y),
- _cairo_int32x32_64_mul (d.y - c.y, a.x - c.x));
- numerator_b = _cairo_int64_sub (_cairo_int32x32_64_mul (b.x - a.x, a.y - c.y),
- _cairo_int32x32_64_mul (b.y - a.y, a.x - c.x));
-
- if (_cairo_int64_is_zero (denominator)) {
- /* If the denominator and numerators are both zero,
- * the lines are coincident. */
- if (_cairo_int64_is_zero (numerator_a) && _cairo_int64_is_zero (numerator_b))
- return TRUE;
-
- /* Otherwise, a zero denominator indicates the lines are
- * parallel and never intersect. */
- return FALSE;
- }
-
- /* If either division would produce a number between 0 and 1, i.e.
- * the numerator is smaller than the denominator and their signs are
- * the same, then the lines intersect. */
- if (_cairo_int64_lt (numerator_a, denominator) &&
- ! (_cairo_int64_negative (numerator_a) ^ _cairo_int64_negative(denominator))) {
- return TRUE;
- }
-
- if (_cairo_int64_lt (numerator_b, denominator) &&
- ! (_cairo_int64_negative (numerator_b) ^ _cairo_int64_negative(denominator))) {
- return TRUE;
- }
-
- return FALSE;
-}
-
cairo_bool_t
_cairo_path_fixed_is_simple_quad (const cairo_path_fixed_t *path)
{
const cairo_point_t *points;
+ cairo_point_t intersection;
if (! _path_is_quad (path))
return FALSE;
@@ -1355,12 +1312,14 @@ _cairo_path_fixed_is_simple_quad (const cairo_path_fixed_t *path)
if (_points_form_rect (points))
return TRUE;
- if (_lines_intersect_or_are_coincident (points[0], points[1],
- points[3], points[2]))
+ if (_slow_segment_intersection (&points[0], &points[1],
+ &points[3], &points[2],
+ &intersection))
return FALSE;
- if (_lines_intersect_or_are_coincident (points[0], points[3],
- points[1], points[2]))
+ if (_slow_segment_intersection (&points[0], &points[3],
+ &points[1], &points[2],
+ &intersection))
return FALSE;
return TRUE;
diff --git a/src/cairo-path-stroke.c b/src/cairo-path-stroke.c
index cd6b3a2..7d99f7f 100644
--- a/src/cairo-path-stroke.c
+++ b/src/cairo-path-stroke.c
@@ -761,9 +761,12 @@ _compute_normalized_device_slope (double *dx, double *dy,
}
static void
-_compute_face (const cairo_point_t *point, cairo_slope_t *dev_slope,
- double slope_dx, double slope_dy,
- cairo_stroker_t *stroker, cairo_stroke_face_t *face)
+_compute_face (const cairo_point_t *point,
+ const cairo_slope_t *dev_slope,
+ double slope_dx,
+ double slope_dy,
+ cairo_stroker_t *stroker,
+ cairo_stroke_face_t *face)
{
double face_dx, face_dy;
cairo_point_t offset_ccw, offset_cw;
@@ -979,6 +982,68 @@ _cairo_stroker_line_to (void *closure,
return CAIRO_STATUS_SUCCESS;
}
+static cairo_status_t
+_cairo_stroker_spline_to (void *closure,
+ const cairo_point_t *point,
+ const cairo_slope_t *tangent)
+{
+ cairo_stroker_t *stroker = closure;
+ cairo_stroke_face_t new_face;
+ double slope_dx, slope_dy;
+ cairo_point_t points[3];
+ cairo_point_t intersect_point;
+
+ stroker->has_initial_sub_path = TRUE;
+
+ if (stroker->current_point.x == point->x &&
+ stroker->current_point.y == point->y)
+ return CAIRO_STATUS_SUCCESS;
+
+ slope_dx = _cairo_fixed_to_double (tangent->dx);
+ slope_dy = _cairo_fixed_to_double (tangent->dy);
+
+ if (! _compute_normalized_device_slope (&slope_dx, &slope_dy,
+ stroker->ctm_inverse, NULL))
+ return CAIRO_STATUS_SUCCESS;
+
+ _compute_face (point, tangent,
+ slope_dx, slope_dy,
+ stroker, &new_face);
+
+ assert (stroker->has_current_face);
+
+ if (_slow_segment_intersection (&stroker->current_face.cw,
+ &stroker->current_face.ccw,
+ &new_face.cw,
+ &new_face.ccw,
+ &intersect_point)) {
+ points[0] = stroker->current_face.ccw;
+ points[1] = new_face.ccw;
+ points[2] = intersect_point;
+ stroker->add_triangle (stroker->closure, points);
+
+ points[0] = stroker->current_face.cw;
+ points[1] = new_face.cw;
+ stroker->add_triangle (stroker->closure, points);
+ } else {
+ points[0] = stroker->current_face.ccw;
+ points[1] = stroker->current_face.cw;
+ points[2] = new_face.cw;
+ stroker->add_triangle (stroker->closure, points);
+
+ points[0] = stroker->current_face.ccw;
+ points[1] = new_face.cw;
+ points[2] = new_face.ccw;
+ stroker->add_triangle (stroker->closure, points);
+ }
+
+ stroker->current_face = new_face;
+ stroker->has_current_face = TRUE;
+ stroker->current_point = *point;
+
+ return CAIRO_STATUS_SUCCESS;
+}
+
/*
* Dashed lines. Cap each dash end, join around turns when on
*/
@@ -1123,7 +1188,6 @@ _cairo_stroker_line_to_dashed (void *closure,
return CAIRO_STATUS_SUCCESS;
}
-
static cairo_status_t
_cairo_stroker_curve_to (void *closure,
const cairo_point_t *b,
@@ -1135,18 +1199,27 @@ _cairo_stroker_curve_to (void *closure,
cairo_line_join_t line_join_save;
cairo_stroke_face_t face;
double slope_dx, slope_dy;
- cairo_path_fixed_line_to_func_t *line_to;
+ cairo_spline_add_point_func_t line_to;
+ cairo_spline_add_point_func_t spline_to;
cairo_status_t status = CAIRO_STATUS_SUCCESS;
line_to = stroker->dash.dashed ?
- _cairo_stroker_line_to_dashed :
- _cairo_stroker_line_to;
+ (cairo_spline_add_point_func_t) _cairo_stroker_line_to_dashed :
+ (cairo_spline_add_point_func_t) _cairo_stroker_line_to;
+
+ /* spline_to is only capable of rendering non-degenerate splines. */
+ spline_to = stroker->dash.dashed ?
+ (cairo_spline_add_point_func_t) _cairo_stroker_line_to_dashed :
+ (cairo_spline_add_point_func_t) _cairo_stroker_spline_to;
if (! _cairo_spline_init (&spline,
- (cairo_spline_add_point_func_t)line_to, stroker,
+ spline_to,
+ stroker,
&stroker->current_point, b, c, d))
{
- return line_to (closure, d);
+ cairo_slope_t fallback_slope;
+ _cairo_slope_init (&fallback_slope, &stroker->current_point, d);
+ return line_to (closure, d, &fallback_slope);
}
/* If the line width is so small that the pen is reduced to a
--
1.7.10.4
More information about the cairo
mailing list