[cairo-commit] 3 commits - src/cairo-traps.c test/.gitignore test/Makefile.am test/radial-gradient.c test/skew-extreme.c test/skew-extreme-ref.png

Carl Worth cworth at kemper.freedesktop.org
Wed Mar 14 15:07:07 PDT 2007


 src/cairo-traps.c         |  101 +++++++++++++++++++++---------------
 test/.gitignore           |    1 
 test/Makefile.am          |    2 
 test/radial-gradient.c    |    3 -
 test/skew-extreme-ref.png |binary
 test/skew-extreme.c       |  126 ++++++++++++++++++++++++++++++++++++++++++++++
 6 files changed, 188 insertions(+), 45 deletions(-)

New commits:
diff-tree 1f3a5b4e1283cc0e55f7ea6baca6d0fe67fd14b1 (from 0a6ae06c35d99e5e8397c58ee94291e7ee45eb4e)
Author: Carl Worth <cworth at cworth.org>
Date:   Tue Mar 13 17:42:39 2007 -0700

    Fix bugs in _cairo_traps_tessellate_convex_quad
    
    The previous code was not handling all cases correctly, (yes,
    even something as simple as a quadrilateral can exhibit a
    remarkably large number of different cases when tessellation
    is attempted).
    
    This fix now introduces slope comparison which handles several
    cases that were mis-handled with the previous implementation which
    only used independent sorting of the X and Y values of the
    coordinates.
    
    This fixes the skew-extreme test case and the bug reported here:
    
    	Skew transforms were broken by the cairo update in December
    	https://bugzilla.mozilla.org/show_bug.cgi?id=373632

diff --git a/src/cairo-traps.c b/src/cairo-traps.c
index b767db8..33e6447 100644
--- a/src/cairo-traps.c
+++ b/src/cairo-traps.c
@@ -380,6 +380,8 @@ _cairo_traps_tessellate_convex_quad (cai
 {
     int a, b, c, d;
     int i;
+    cairo_slope_t ab, ad;
+    cairo_bool_t b_left_of_d;
 
     /* Choose a as a point with minimal y */
     a = 0;
@@ -399,24 +401,39 @@ _cairo_traps_tessellate_convex_quad (cai
     }
 
     /* Without freedom left to choose anything else, we have four
-     * cases to tessellate which we can distinguish by comparing c.y
-     * to d.y and then by comparing b.x to d.x. And then for any of
-     * these cases there is a trivial way to emit three
-     * trapezoids. The 4 cases and their trapezoids are described and
-     * implemented below:
-     */
-    if (q[c].y < q[d].y) {
-	if (q[b].x < q[d].x) {
-	    /* c.y < d.y && b.x < d.x
+     * cases to tessellate.
+     *
+     * First, we have to determine the Y-axis sort of the four
+     * vertices, (either abcd or abdc). After that we need to detemine
+     * which edges will be "left" and which will be "right" in the
+     * resulting trapezoids. This can be determined by computing a
+     * slope comparison of ab and ad to determine if b is left of d or
+     * not.
+     *
+     * Note that "left of" here is in the sense of which edges should
+     * be the left vs. right edges of the trapezoid. In particular, b
+     * left of d does *not* mean that b.x is less than d.x.
+     *
+     * This should hopefully be made clear in the lame ASCII art
+     * below. Since the same slope comparison is used in all cases, we
+     * compute it before testing for the Y-value sort. */
+    _cairo_slope_init (&ab, &q[a], &q[b]);
+    _cairo_slope_init (&ad, &q[a], &q[d]);
+
+    b_left_of_d = (_cairo_slope_compare (&ab, &ad) > 0);
+
+    if (q[c].y <= q[d].y) {
+	if (b_left_of_d) {
+	    /* Y-sort is abcd and b is left of d, (slope(ab) > slope (ad))
 	     *
-	     *           top bot left right
-	     *   a
-	     *  / |      a.y b.y  ab   ad
-	     * b  |
-	     * |  |      b.y c.y  bc   ad
-	     * c  |
-	     *  \ |      c.y d.y  cd   ad
-	     *   d
+	     *                      top bot left right
+	     *        _a  a  a
+	     *      / /  /|  |\      a.y b.y  ab   ad
+	     *     b /  b |  b \
+	     *    / /   | |   \ \    b.y c.y  bc   ad
+	     *   c /    c |    c \
+	     *  | /      \|     \ \  c.y d.y  cd   ad
+	     *  d         d       d
 	     */
 	    _cairo_traps_add_trap_from_points (traps,
 					       q[a].y, q[b].y,
@@ -428,15 +445,15 @@ _cairo_traps_tessellate_convex_quad (cai
 					       q[c].y, q[d].y,
 					       q[c], q[d], q[a], q[d]);
 	} else {
-	    /* c.y < d.y && b.x >= d.x
+	    /* Y-sort is abcd and b is right of d, (slope(ab) <= slope (ad))
 	     *
-	     *  a
-	     * | \       a.y b.y  ad  ab
-	     * |  b
-	     * |  |      b.y c.y  ad  bc
-	     * |  c
-	     * | /       c.y d.y  ad  cd
-	     *  d
+	     *       a  a  a_
+	     *      /|  |\  \ \     a.y b.y  ad  ab
+	     *     / b  | b  \ b
+	     *    / /   | |   \ \   b.y c.y  ad  bc
+	     *   / c    | c    \ c
+	     *  / /     |/      \ | c.y d.y  ad  cd
+	     *  d       d         d
 	     */
 	    _cairo_traps_add_trap_from_points (traps,
 					       q[a].y, q[b].y,
@@ -449,16 +466,16 @@ _cairo_traps_tessellate_convex_quad (cai
 					       q[a], q[d], q[c], q[d]);
 	}
     } else {
-	if (q[b].x < q[d].x) {
-	    /* c.y >= d.y && b.x < d.x
+	if (b_left_of_d) {
+	    /* Y-sort is abdc and b is left of d, (slope (ab) > slope (ad))
 	     *
-	     *   a
-	     *  / \      a.y b.y  ab  ad
-	     * b   \
-	     *  \   \    b.y d.y  bc  ad
-	     *   \   d
-	     *    \ /    d.y c.y  bc  dc
-	     *     c
+	     *        a   a     a
+	     *       //  / \    |\     a.y b.y  ab  ad
+	     *     /b/  b   \   b \
+	     *    / /    \   \   \ \   b.y d.y  bc  ad
+	     *   /d/      \   d   \ d
+	     *  //         \ /     \|  d.y c.y  bc  dc
+	     *  c           c       c
 	     */
 	    _cairo_traps_add_trap_from_points (traps,
 					       q[a].y, q[b].y,
@@ -470,15 +487,15 @@ _cairo_traps_tessellate_convex_quad (cai
 					       q[d].y, q[c].y,
 					       q[b], q[c], q[d], q[c]);
 	} else {
-	    /* c.y >= d.y && b.x >= d.x
+	    /* Y-sort is abdc and b is right of d, (slope (ab) <= slope (ad))
 	     *
-	     *     a
-	     *    / \    a.y b.y  ad  ab
-	     *   /   b
-	     *  /   /    b.y d.y  ad  bc
-	     * d   /
-	     *  \ /      d.y c.y  dc  bc
-	     *   c
+	     *      a     a   a
+	     *     /|    / \  \\       a.y b.y  ad  ab
+	     *    / b   /   b  \b\
+	     *   / /   /   /    \ \    b.y d.y  ad  bc
+	     *  d /   d   /	 \d\
+	     *  |/     \ /         \\  d.y c.y  dc  bc
+	     *  c       c	   c
 	     */
 	    _cairo_traps_add_trap_from_points (traps,
 					       q[a].y, q[b].y,
diff-tree 0a6ae06c35d99e5e8397c58ee94291e7ee45eb4e (from 40b6d8842e1bcb5fbb3a7dffd0c05b7d3bf6cc6b)
Author: Carl Worth <cworth at cworth.org>
Date:   Tue Mar 13 17:39:48 2007 -0700

    Add new skew-extreme test case.
    
    This test currently fails, demonstrating the bug reported here:
    
    	Skew transforms were broken by the cairo update in December
    	https://bugzilla.mozilla.org/show_bug.cgi?id=373632

diff --git a/test/.gitignore b/test/.gitignore
index e514f5d..6c4adfc 100644
--- a/test/.gitignore
+++ b/test/.gitignore
@@ -121,6 +121,7 @@ self-intersecting
 set-source
 show-glyphs-many
 show-text-current-point
+skew-extreme
 source-clip
 source-clip-scale
 source-surface-scale-paint
diff --git a/test/Makefile.am b/test/Makefile.am
index 05f3620..54928cf 100644
--- a/test/Makefile.am
+++ b/test/Makefile.am
@@ -85,6 +85,7 @@ self-copy			\
 self-intersecting		\
 set-source			\
 show-text-current-point		\
+skew-extreme			\
 source-clip			\
 source-clip-scale		\
 source-surface-scale-paint	\
diff --git a/test/skew-extreme-ref.png b/test/skew-extreme-ref.png
new file mode 100644
index 0000000..1408395
Binary files /dev/null and b/test/skew-extreme-ref.png differ
diff --git a/test/skew-extreme.c b/test/skew-extreme.c
new file mode 100644
index 0000000..919937b
--- /dev/null
+++ b/test/skew-extreme.c
@@ -0,0 +1,126 @@
+/*
+ * Copyright © 2007 Red Hat, Inc.
+ *
+ * Permission is hereby granted, free of charge, to any person
+ * obtaining a copy of this software and associated documentation
+ * files (the "Software"), to deal in the Software without
+ * restriction, including without limitation the rights to use, copy,
+ * modify, merge, publish, distribute, sublicense, and/or sell copies
+ * of the Software, and to permit persons to whom the Software is
+ * furnished to do so, subject to the following conditions:
+ *
+ * The above copyright notice and this permission notice shall be
+ * included in all copies or substantial portions of the Software.
+ *
+ * THE SOFTWARE IS PROVIDED "AS IS", WITHOUT WARRANTY OF ANY KIND,
+ * EXPRESS OR IMPLIED, INCLUDING BUT NOT LIMITED TO THE WARRANTIES OF
+ * MERCHANTABILITY, FITNESS FOR A PARTICULAR PURPOSE AND
+ * NONINFRINGEMENT. IN NO EVENT SHALL THE AUTHORS OR COPYRIGHT HOLDERS
+ * BE LIABLE FOR ANY CLAIM, DAMAGES OR OTHER LIABILITY, WHETHER IN AN
+ * ACTION OF CONTRACT, TORT OR OTHERWISE, ARISING FROM, OUT OF OR IN
+ * CONNECTION WITH THE SOFTWARE OR THE USE OR OTHER DEALINGS IN THE
+ * SOFTWARE.
+ *
+ * Author: Carl Worth <cworth at cworth.org>
+ */
+
+#include "cairo-test.h"
+
+/* This test case is designed to exercise the following bug:
+ *
+ *	Skew transforms were broken by the cairo update in December
+ *	https://bugzilla.mozilla.org/show_bug.cgi?id=373632
+ *
+ * What's happening is that the rectangle is being skewed into the
+ * following shape:
+ *
+ * a__b
+ *  \ \
+ *   \ \
+ *    \ \
+ *     \ \
+ *      \ \
+ *      d\_\c
+ *
+ * and the bug is that _cairo_traps_tessellate_convex_quad is
+ * comparing b.x as less then d.x and therfore determining that the bc
+ * edge is left of the ad edge. The fix is simply to compare c.x to
+ * d.x instead of b.x to d.x .
+ */
+
+#define PAD		2
+#define LINE_WIDTH	10
+#define LINE_LENGTH	(2 * LINE_WIDTH)
+#define SKEW_FACTOR	5.0
+#define WIDTH		(PAD + (LINE_LENGTH * SKEW_FACTOR) + LINE_WIDTH + PAD)
+#define HEIGHT		(PAD + LINE_WIDTH + (LINE_LENGTH * SKEW_FACTOR) + LINE_WIDTH + PAD)
+
+static cairo_test_draw_function_t draw;
+
+cairo_test_t test = {
+    "skew-extreme",
+    "Test cases of extreme skew.",
+    WIDTH, HEIGHT,
+    draw
+};
+
+static cairo_test_status_t
+draw (cairo_t *cr, int width, int height)
+{
+    /* We draw in the default black, so paint white first. */
+    cairo_save (cr);
+    cairo_set_source_rgb (cr, 1.0, 1.0, 1.0); /* white */
+    cairo_paint (cr);
+    cairo_restore (cr);
+
+    cairo_translate (cr, PAD, PAD);
+
+    cairo_set_line_width (cr, LINE_WIDTH);
+    cairo_set_line_cap (cr, CAIRO_LINE_CAP_BUTT);
+
+    cairo_save (cr);
+    {
+	cairo_matrix_t skew_x = {
+	    1.0, 0.0,
+	    SKEW_FACTOR, 1.0,
+	    0.0, 0.0
+	};
+
+	cairo_translate (cr, LINE_WIDTH / 2.0, 0.0);
+
+	cairo_transform (cr, &skew_x);
+
+	cairo_move_to (cr, 0.0, 0.0);
+	cairo_line_to (cr, 0.0, LINE_LENGTH);
+	cairo_stroke (cr);
+    }
+    cairo_restore (cr);
+
+    cairo_translate (cr, 0.0, LINE_WIDTH);
+
+    cairo_save (cr);
+    {
+	cairo_matrix_t skew_y = {
+	    1.0, SKEW_FACTOR,
+	    0.0, 1.0,
+	    0.0, 0.0
+	};
+
+	cairo_translate (cr, 0.0, LINE_WIDTH / 2.0);
+
+	cairo_transform (cr, &skew_y);
+
+	cairo_move_to (cr, 0.0, 0.0);
+	cairo_line_to (cr, LINE_LENGTH, 0.0);
+	cairo_stroke (cr);
+    }
+    cairo_restore (cr);
+
+    return CAIRO_TEST_SUCCESS;
+}
+
+int
+main (void)
+{
+    return cairo_test (&test);
+}
diff-tree 40b6d8842e1bcb5fbb3a7dffd0c05b7d3bf6cc6b (from e803e2e69ba02a1db316c97eb9a8d386709380e2)
Author: Carl Worth <cworth at cworth.org>
Date:   Tue Mar 13 13:07:42 2007 -0700

    Remove radial-gradient test from XFAIL list
    
    This test has not been failing since the fix in:
    
    	772edc9133d41dfd667ae5915dfa6ace0bcbfd0d
    
    So get rid of the '1 unexpected passes' complaint.

diff --git a/test/Makefile.am b/test/Makefile.am
index ea4787c..05f3620 100644
--- a/test/Makefile.am
+++ b/test/Makefile.am
@@ -409,7 +409,6 @@ extend-pad			\
 filter-nearest-offset		\
 ft-text-vertical-layout-type1	\
 long-lines			\
-radial-gradient			\
 self-intersecting		\
 surface-pattern			\
 surface-pattern-scale-down	\
diff --git a/test/radial-gradient.c b/test/radial-gradient.c
index d78c430..1207943 100644
--- a/test/radial-gradient.c
+++ b/test/radial-gradient.c
@@ -36,8 +36,7 @@ static cairo_test_draw_function_t draw;
 
 cairo_test_t test = {
     "radial-gradient",
-    "Simple test of radial gradients"
-    "\nCurrently failing EXTEND_REFLECT with non-zero inner radius for SVG backend",
+    "Simple test of radial gradients",
     WIDTH, HEIGHT,
     draw
 };


More information about the cairo-commit mailing list