Fix (filling) : Very long lines sometimes painted in a wrong direction.

DETAILS :

Debugged with CET 11-14.PS : (next 3E9 dup moveto 1 dup lto fini) .

A fixed overflow happened in gxstroke.c .
To work around it we subdivide long segments into 2 parts
before applying the stroking algorithm.

1. The hew function gx_path_has_long_segments checks for long segments.
2. The function gx_path_copy_reducing now breaks long segments into 2 parts.
3. gxstroke.c is changed to apply (1) and (2).
4. Note that (2) also affects the filling algorithm,
   rather it is not related to the test case.
   It had problems with long segments also,
   at least gx_default_fill_trapezoid must not be called with
   very long setgments, because it computes coordinate differences.

EXPECTED DIFFERENCES :

None.

git-svn-id: http://svn.ghostscript.com/ghostscript/trunk@7213 a1074d23-0009-0410-80fe-cf8c14f379e6

5 files changed, 89 insertions, 1 deletions

diff --git a/gs/src/gxpath.h b/gs/src/gxpath.h
index 410c2c934..06a45d3e2 100644
--- a/gs/src/gxpath.h
+++ b/gs/src/gxpath.h
@@ -195,6 +195,7 @@ bool gx_path_has_curves(const gx_path *),
     gx_path_is_void(const gx_path *),	/* no segments */
     gx_path_is_null(const gx_path *),	/* nothing at all */
     gx_path__check_curves(const gx_path * ppath, gx_path_copy_options options, fixed fixed_flat);
+    gx_path_has_long_segments(const gx_path * ppath);
 typedef enum {
     prt_none = 0,
     prt_open = 1,		/* only 3 sides */
diff --git a/gs/src/gxpcopy.c b/gs/src/gxpcopy.c
index ef7d95188..79f34b317 100644
--- a/gs/src/gxpcopy.c
+++ b/gs/src/gxpcopy.c
@@ -26,6 +26,35 @@
 /* Forward declarations */
 private void adjust_point_to_tangent(segment *, const segment *,
 				     const gs_fixed_point *);
+
+private inline int
+break_line_if_long(gx_path *ppath, const segment *pseg)
+{
+    fixed x0 = ppath->position.x;
+    fixed y0 = ppath->position.y;
+
+    if (gx_check_fixed_diff_overflow(pseg->pt.x, x0) ||
+	gx_check_fixed_diff_overflow(pseg->pt.y, y0)) {
+	fixed x, y;
+
+	if (gx_check_fixed_sum_overflow(pseg->pt.x, x0))
+	    x = (pseg->pt.x >> 1) + (x0 >> 1);
+	else
+	    x = (pseg->pt.x + x0) >> 1;
+	if (gx_check_fixed_sum_overflow(pseg->pt.y, y0))
+	    y = (pseg->pt.y >> 1) + (y0 >> 1);
+	else
+	    y = (pseg->pt.y + y0) >> 1;
+	return gx_path_add_line_notes(ppath, x, y, pseg->notes);
+	/* WARNING: Stringly speaking, the next half segment must get
+	   the sn_not_first flag. We don't bother, because that flag 
+	   has no important meaning with colinear segments.
+	 */
+    }
+    return 0;
+}
+
+
 /* Copy a path, optionally flattening or monotonizing it. */
 /* If the copy fails, free the new path. */
 int
@@ -177,6 +206,9 @@ gx_path_copy_reducing(const gx_path *ppath_old, gx_path *ppath,
 		    break;
 		}
 	    case s_line:
+		code = break_line_if_long(ppath, pseg);
+		if (code < 0)
+		    break;
 		code = gx_path_add_line_notes(ppath,
 				       pseg->pt.x, pseg->pt.y, pseg->notes);
 		vd_lineto(pseg->pt.x, pseg->pt.y);
@@ -190,6 +222,9 @@ gx_path_copy_reducing(const gx_path *ppath_old, gx_path *ppath,
 		    break;
 		}
 	    case s_line_close:
+		code = break_line_if_long(ppath, pseg);
+		if (code < 0)
+		    break;
 		code = gx_path_close_subpath(ppath);
 		vd_closepath;
 		break;
@@ -303,6 +338,11 @@ gx_path__check_curves(const gx_path * ppath, gx_path_copy_options options, fixed
 			pseg = psub->last;
 		}
 		break;
+	    case s_line:
+		if (gx_check_fixed_diff_overflow(pseg->pt.x, pt0.x) ||
+		    gx_check_fixed_diff_overflow(pseg->pt.y, pt0.y))
+		    return true;
+		break;
 	    case s_curve:
 		{
 		    const curve_segment *pc = (const curve_segment *)pseg;
@@ -339,6 +379,35 @@ gx_path__check_curves(const gx_path * ppath, gx_path_copy_options options, fixed
     return true;
 }
 
+/* Test whether a path is free of long segments. */
+/* WARNING : This function checks the distance between
+ * the starting point and the ending point of a segment.
+ * When they are not too far, a curve nevertheless may be too long.
+ * Don't worry about it here, because we assume
+ * this function is never called with paths which have curves.
+ */
+bool
+gx_path_has_long_segments(const gx_path * ppath)
+{
+    const segment *pseg = (const segment *)(ppath->first_subpath);
+    gs_fixed_point pt0;
+
+    while (pseg) {
+	switch (pseg->type) {
+	    case s_start:
+		break;
+	    default:
+		if (gx_check_fixed_diff_overflow(pseg->pt.x, pt0.x) ||
+		    gx_check_fixed_diff_overflow(pseg->pt.y, pt0.y))
+		    return true;
+		break;
+	}
+	pt0 = pseg->pt;
+	pseg = pseg->next;
+    }
+    return false;
+}
+
 /* Monotonize a curve, by splitting it if necessary. */
 /* In the worst case, this could split the curve into 9 pieces. */
 int
diff --git a/gs/src/gxpflat.c b/gs/src/gxpflat.c
index 96578f0d4..fc8e04be8 100644
--- a/gs/src/gxpflat.c
+++ b/gs/src/gxpflat.c
@@ -278,6 +278,20 @@ check_diff_overflow(fixed v0, fixed v1)
     return false;
 }
 
+bool
+gx_check_fixed_diff_overflow(fixed v0, fixed v1)
+{
+    return check_diff_overflow(v0, v1);
+}
+bool
+gx_check_fixed_sum_overflow(fixed v0, fixed v1)
+{
+    /* We assume that clamp_point_aux have been applied to v1,
+       thus -v alweays exists.
+     */
+    return check_diff_overflow(v0, -v1);
+}
+
 /*  Initialize the iterator with a line. */
 bool
 gx_flattened_iterator__init_line(gx_flattened_iterator *this, 
diff --git a/gs/src/gxstroke.c b/gs/src/gxstroke.c
index b128e52e3..da53b6482 100644
--- a/gs/src/gxstroke.c
+++ b/gs/src/gxstroke.c
@@ -503,7 +503,8 @@ gx_stroke_path_only_aux(gx_path * ppath, gx_path * to_path, gx_device * pdev,
 	device_dot_length *= fabs(pmat->xy) + fabs(pmat->yy);
     }
     /* Start by flattening the path.  We should do this on-the-fly.... */
-    if (!gx_path_has_curves(ppath)) {	/* don't need to flatten */
+    if (!gx_path_has_curves(ppath) && !gx_path_has_long_segments(ppath)) {	
+	/* don't need to flatten */
 	if (!ppath->first_subpath)
 	    return 0;
 	spath = ppath;
diff --git a/gs/src/gzpath.h b/gs/src/gzpath.h
index b3db33ee6..88e2d2300 100644
--- a/gs/src/gzpath.h
+++ b/gs/src/gzpath.h
@@ -403,4 +403,7 @@ bool curve_coeffs_ranged(fixed x0, fixed x1, fixed x2, fixed x3,
 		    fixed *ay, fixed *by, fixed *cy, 
 		    int k);
 
+bool gx_check_fixed_diff_overflow(fixed v0, fixed v1);
+bool gx_check_fixed_sum_overflow(fixed v0, fixed v1);
+
 #endif /* gzpath_INCLUDED */