[cairo] Tessellator regressions
M Joonas Pihlaja
jpihlaja at cc.helsinki.fi
Tue Dec 5 16:38:26 PST 2006
Hi,
Attached are test cases and patches for fixing regressions in the
tessellator. They should fix most issues found so far, with the
notable exception of the elusive 32nd bit in input coordinates.
Namely, the tessellator code currently assumes that vector deltas
may be computed in 32 bit signed integers, but there's no
guarantee that this is actually the case.
To mitigate this, one of the patches offsets the input
coordinates to be in the non-negative range for the duration of
the tessellation. It clamps the bounding box to have width and
height at most 2^31, and all points outside the clamped bounding
box get projected to the nearest edge. This results in bad
rendering at large zooms, but at least there should be no more
deaths on assertions in the tessellator. (Not that that's much
better when there's bad rendering going on instead... but meh.)
I think it's possible to rework the arithmetic in the tessellator
to avoid this, perhaps with 64 bit internal coordinates, or by
dealing with the signs of differences separately. Or, as
suggested by Carl on #cairo, we could add a new status code to
indicate tessellator failure in the case of input coordinates
being too large.
Cheers,
Joonas
[1] dys should actually be guaranteed to be non-negative always
due to the preconditions of the tessellator, but we do it anyway.
-------------- next part --------------
From 7291742184610bde1b1cde0fd6458fbf87194823 Mon Sep 17 00:00:00 2001
From: M Joonas Pihlaja <jpihlaja at cc.helsinki.fi>
Date: Tue, 5 Dec 2006 11:21:14 +0200
Subject: [PATCH] test: tessellator event comparator test case for degenerate edges.
There's currently a regression bug in the tessellation code from
switching to the new tessellator. The bug is caused by
confusion in the comparator used to order events when there are
degenerate edges. This test is derived from the zrusin-another
performance test case.
---
test/Makefile.am | 3 +
test/fill-degenerate-sort-order-ref.png | Bin
test/fill-degenerate-sort-order-rgb24-ref.png | Bin
test/fill-degenerate-sort-order.c | 110 +++++++++++++++++++++++++
4 files changed, 113 insertions(+), 0 deletions(-)
diff --git a/test/Makefile.am b/test/Makefile.am
index 8033ce8..ef35852 100644
--- a/test/Makefile.am
+++ b/test/Makefile.am
@@ -32,6 +32,7 @@ extend-reflect \
fill-and-stroke \
fill-and-stroke-alpha \
fill-and-stroke-alpha-add \
+fill-degenerate-sort-order \
fill-rule \
filter-nearest-offset \
font-face-get-type \
@@ -216,6 +217,8 @@ fill-and-stroke-ps-argb32-ref.png \
fill-and-stroke-alpha-ref.png \
fill-and-stroke-alpha-svg-ref.png \
fill-and-stroke-alpha-add-ref.png \
+fill-degenerate-sort-order-ref.png \
+fill-degenerate-sort-order-rgb24-ref.png \
fill-rule-ref.png \
fill-rule-rgb24-ref.png \
fill-rule-ps-argb32-ref.png \
diff --git a/test/fill-degenerate-sort-order-ref.png b/test/fill-degenerate-sort-order-ref.png
new file mode 100644
index 0000000..ca1f575
Binary files /dev/null and b/test/fill-degenerate-sort-order-ref.png differ
diff --git a/test/fill-degenerate-sort-order-rgb24-ref.png b/test/fill-degenerate-sort-order-rgb24-ref.png
new file mode 100644
index 0000000..999a09a
Binary files /dev/null and b/test/fill-degenerate-sort-order-rgb24-ref.png differ
diff --git a/test/fill-degenerate-sort-order.c b/test/fill-degenerate-sort-order.c
new file mode 100644
index 0000000..72c7a22
--- /dev/null
+++ b/test/fill-degenerate-sort-order.c
@@ -0,0 +1,110 @@
+/*
+ * Copyright ?? 2006 M Joonas Pihlaja
+ *
+ * Permission to use, copy, modify, distribute, and sell this software
+ * and its documentation for any purpose is hereby granted without
+ * fee, provided that the above copyright notice appear in all copies
+ * and that both that copyright notice and this permission notice
+ * appear in supporting documentation, and that the name of Joonas Pihlaja
+ * not be used in advertising or publicity pertaining to distribution
+ * of the software without specific, written prior permission.
+ * Joonas Pihlaja makes no representations about the suitability of this
+ * software for any purpose. It is provided "as is" without express
+ * or implied warranty.
+ *
+ * JOONAS PIHLAJA DISCLAIMS ALL WARRANTIES WITH REGARD TO THIS SOFTWARE,
+ * INCLUDING ALL IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS, IN
+ * NO EVENT SHALL JOONAS PIHLAJA BE LIABLE FOR ANY SPECIAL, INDIRECT OR
+ * CONSEQUENTIAL DAMAGES OR ANY DAMAGES WHATSOEVER RESULTING FROM LOSS
+ * OF USE, DATA OR PROFITS, WHETHER IN AN ACTION OF CONTRACT,
+ * NEGLIGENCE OR OTHER TORTIOUS ACTION, ARISING OUT OF OR IN
+ * CONNECTION WITH THE USE OR PERFORMANCE OF THIS SOFTWARE.
+ *
+ * Author: M Joonas Pihlaja <jpihlaja at cc.helsinki.fi>
+ */
+
+/* Bug history
+ *
+ * 2006-12-05 M Joonas Pihlaja <jpihlaja at cc.helsinki.fi>
+ *
+ * There's currently a regression bug in the tessellation code from
+ * switching to the "new tessellator". The bug is caused by
+ * confusion in the comparator used to order events when there are
+ * degenerate edges.
+ */
+
+#include "cairo-test.h"
+
+static cairo_test_draw_function_t draw;
+
+cairo_test_t test = {
+ "fill-degenerate-sort-order",
+ "Tests the tessellator's event comparator with degenerate input",
+ 190, 120,
+ draw
+};
+
+/* Derived from zrusin's "another" polygon in the performance suite. */
+static cairo_test_status_t
+draw (cairo_t *cr_orig, int width, int height)
+{
+ /* XXX: I wanted to be able to simply fill the nasty path to the
+ * surface and then use a reference image to catch bugs, but the
+ * renderer used when testing the postscript backend gets the
+ * degeneracy wrong, thus leading to an (unfixable?) test case
+ * failure. Are external renderer bugs our bugs too? Instead,
+ * tessellate the polygon and render to the surface the results of
+ * point sampling the tessellated path. If there would be a way
+ * to XFAIL only some backends we could do that for the .ps
+ * backend only. */
+ int x,y;
+ int sample_stride;
+ cairo_surface_t *surf = cairo_image_surface_create (CAIRO_FORMAT_ARGB32, width, height);
+ cairo_t *cr = cairo_create (surf);
+ cairo_set_source_rgb (cr_orig, 1, 0, 0);
+
+ /* The polygon uses (43,103) as its "base point". Closed
+ * subpaths are simulated by going from the base point to the
+ * subpath's first point, doing the subpath, and returning to the
+ * base point. The moving to and from the base point causes
+ * degenerate edges which shouldn't result in anything visible. */
+ cairo_move_to (cr, 43, 103);
+
+ /* First subpath. */
+ cairo_line_to (cr, 91, 101);
+ cairo_line_to (cr, 0, 112);
+ cairo_line_to (cr, 60, 0);
+ cairo_line_to (cr, 91, 101);
+
+ cairo_line_to (cr, 43, 103);
+
+ /* Second subpath. */
+ cairo_line_to (cr, 176, 110);
+ cairo_line_to (cr, 116, 100);
+ cairo_line_to (cr, 176, 0);
+ cairo_line_to (cr, 176, 110);
+
+ cairo_close_path (cr);
+
+ /* Point sample the tessellated path. The x and y starting offsets
+ * are chosen to hit the nasty bits while still being able to do a
+ * relatively sparse sampling. */
+ sample_stride = 4;
+ for (y = 0; y < height; y += sample_stride) {
+ for (x = 0; x < width; x += sample_stride) {
+ if (cairo_in_fill (cr, x, y)) {
+ cairo_rectangle(cr_orig, x, y, sample_stride, sample_stride);
+ cairo_fill (cr_orig);
+ }
+ }
+ }
+ cairo_destroy (cr);
+ cairo_surface_destroy (surf);
+ return CAIRO_TEST_SUCCESS;
+}
+
+int
+main (void)
+{
+ return cairo_test (&test);
+}
--
1.4.1.1
-------------- next part --------------
From 06c2afa6babcc3b0e4de8e318dd73a8bafa3d2c7 Mon Sep 17 00:00:00 2001
From: M Joonas Pihlaja <jpihlaja at cc.helsinki.fi>
Date: Tue, 5 Dec 2006 12:20:17 +0200
Subject: [PATCH] test: check if cairo_in_fill() is reporting false positives for empty trapezoids.
cairo_in_fill() may report true if a query point lands on an edge of an
empty trapezoid.
---
test/Makefile.am | 3 +
test/in-fill-empty-trapezoid-ref.png | Bin
test/in-fill-empty-trapezoid-rgb24-ref.png | Bin
test/in-fill-empty-trapezoid.c | 89 ++++++++++++++++++++++++++++
4 files changed, 92 insertions(+), 0 deletions(-)
diff --git a/test/Makefile.am b/test/Makefile.am
index ef35852..b063a17 100644
--- a/test/Makefile.am
+++ b/test/Makefile.am
@@ -44,6 +44,7 @@ get-group-target \
get-path-extents \
gradient-alpha \
infinite-join \
+in-fill-empty-trapezoid \
leaky-dash \
leaky-polygon \
line-width \
@@ -238,6 +239,8 @@ glyph-cache-pressure-ps-argb32-ref.png
glyph-cache-pressure-svg-ref.png \
gradient-alpha-ref.png \
gradient-alpha-rgb24-ref.png \
+in-fill-empty-trapezoid-ref.png \
+in-fill-empty-trapezoid-rgb24-ref.png \
infinite-join-ref.png \
infinite-join-ps-argb32-ref.png \
leaky-dash-ref.png \
diff --git a/test/in-fill-empty-trapezoid-ref.png b/test/in-fill-empty-trapezoid-ref.png
new file mode 100644
index 0000000..60ae617
Binary files /dev/null and b/test/in-fill-empty-trapezoid-ref.png differ
diff --git a/test/in-fill-empty-trapezoid-rgb24-ref.png b/test/in-fill-empty-trapezoid-rgb24-ref.png
new file mode 100644
index 0000000..ef08ebb
Binary files /dev/null and b/test/in-fill-empty-trapezoid-rgb24-ref.png differ
diff --git a/test/in-fill-empty-trapezoid.c b/test/in-fill-empty-trapezoid.c
new file mode 100644
index 0000000..2999ec5
--- /dev/null
+++ b/test/in-fill-empty-trapezoid.c
@@ -0,0 +1,89 @@
+/*
+ * Copyright ?? 2006 M Joonas Pihlaja
+ *
+ * Permission to use, copy, modify, distribute, and sell this software
+ * and its documentation for any purpose is hereby granted without
+ * fee, provided that the above copyright notice appear in all copies
+ * and that both that copyright notice and this permission notice
+ * appear in supporting documentation, and that the name of Joonas Pihlaja
+ * not be used in advertising or publicity pertaining to distribution
+ * of the software without specific, written prior permission.
+ * Joonas Pihlaja makes no representations about the suitability of this
+ * software for any purpose. It is provided "as is" without express
+ * or implied warranty.
+ *
+ * JOONAS PIHLAJA DISCLAIMS ALL WARRANTIES WITH REGARD TO THIS SOFTWARE,
+ * INCLUDING ALL IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS, IN
+ * NO EVENT SHALL JOONAS PIHLAJA BE LIABLE FOR ANY SPECIAL, INDIRECT OR
+ * CONSEQUENTIAL DAMAGES OR ANY DAMAGES WHATSOEVER RESULTING FROM LOSS
+ * OF USE, DATA OR PROFITS, WHETHER IN AN ACTION OF CONTRACT,
+ * NEGLIGENCE OR OTHER TORTIOUS ACTION, ARISING OUT OF OR IN
+ * CONNECTION WITH THE USE OR PERFORMANCE OF THIS SOFTWARE.
+ *
+ * Author: M Joonas Pihlaja <jpihlaja at cc.helsinki.fi>
+ */
+
+/* Bug history
+ *
+ * 2006-12-05 M Joonas Pihlaja <jpihlaja at cc.helsinki.fi>
+ *
+ * The cairo_in_fill () function can sometimes produce false
+ * positives when the tessellator produces empty trapezoids
+ * and the query point lands exactly on a trapezoid edge.
+ */
+
+#include "cairo-test.h"
+
+static cairo_test_draw_function_t draw;
+
+cairo_test_t test = {
+ "in-fill-empty-trapezoid",
+ "Tests that the tessellator doesn't produce obviously empty trapezoids",
+ 10, 10,
+ draw
+};
+
+static cairo_test_status_t
+draw (cairo_t *cr_orig, int width, int height)
+{
+ int x,y;
+ cairo_surface_t *surf = cairo_image_surface_create (CAIRO_FORMAT_ARGB32, width, height);
+ cairo_t *cr = cairo_create (surf);
+ cairo_set_source_rgb (cr_orig, 1, 0, 0);
+
+ /* Empty horizontal trapezoid. */
+ cairo_move_to (cr, 0, height/3);
+ cairo_line_to (cr, width, height/3);
+ cairo_close_path (cr);
+
+ /* Empty non-horizontal trapezoid #1. */
+ cairo_move_to (cr, 0, 0);
+ cairo_line_to (cr, width, height/2);
+ cairo_close_path (cr);
+
+ /* Empty non-horizontal trapezoid #2 intersecting #1. */
+ cairo_move_to (cr, 0, height/2);
+ cairo_line_to (cr, width, 0);
+ cairo_close_path (cr);
+
+ /* Point sample the tessellated path. The x and y starting offsets
+ * are chosen to hit the nasty bits while still being able to do a
+ * relatively sparse sampling. */
+ for (y = 0; y < height; y++) {
+ for (x = 0; x < width; x++) {
+ if (cairo_in_fill (cr, x, y)) {
+ cairo_rectangle(cr_orig, x, y, 1, 1);
+ cairo_fill (cr_orig);
+ }
+ }
+ }
+ cairo_destroy (cr);
+ cairo_surface_destroy (surf);
+ return CAIRO_TEST_SUCCESS;
+}
+
+int
+main (void)
+{
+ return cairo_test (&test);
+}
--
1.4.1.1
-------------- next part --------------
From a8837a0262026ffa7fd3f4729acb3a37d1b87b84 Mon Sep 17 00:00:00 2001
From: M Joonas Pihlaja <jpihlaja at cc.helsinki.fi>
Date: Tue, 5 Dec 2006 13:02:47 +0200
Subject: [PATCH] test: check for tessellator regression from missed stop events
The new tessellator contains a regression where stop events
that aren't followed by start events sometimes cause the
trapezoid to the left of an edge to be too high.
---
test/Makefile.am | 4 +
test/fill-missed-stop-ps-argb32-ref.png | Bin
test/fill-missed-stop-ref.png | Bin
test/fill-missed-stop-rgb24-ref.png | Bin
test/fill-missed-stop.c | 89 +++++++++++++++++++++++++++++++
5 files changed, 93 insertions(+), 0 deletions(-)
diff --git a/test/Makefile.am b/test/Makefile.am
index b063a17..0d11895 100644
--- a/test/Makefile.am
+++ b/test/Makefile.am
@@ -33,6 +33,7 @@ fill-and-stroke \
fill-and-stroke-alpha \
fill-and-stroke-alpha-add \
fill-degenerate-sort-order \
+fill-missed-stop \
fill-rule \
filter-nearest-offset \
font-face-get-type \
@@ -220,6 +221,9 @@ fill-and-stroke-alpha-svg-ref.png \
fill-and-stroke-alpha-add-ref.png \
fill-degenerate-sort-order-ref.png \
fill-degenerate-sort-order-rgb24-ref.png \
+fill-missed-stop-ref.png \
+fill-missed-stop-rgb24-ref.png \
+fill-missed-stop-ps-argb32-ref.png \
fill-rule-ref.png \
fill-rule-rgb24-ref.png \
fill-rule-ps-argb32-ref.png \
diff --git a/test/fill-missed-stop-ps-argb32-ref.png b/test/fill-missed-stop-ps-argb32-ref.png
new file mode 100644
index 0000000..b94a708
Binary files /dev/null and b/test/fill-missed-stop-ps-argb32-ref.png differ
diff --git a/test/fill-missed-stop-ref.png b/test/fill-missed-stop-ref.png
new file mode 100644
index 0000000..241d725
Binary files /dev/null and b/test/fill-missed-stop-ref.png differ
diff --git a/test/fill-missed-stop-rgb24-ref.png b/test/fill-missed-stop-rgb24-ref.png
new file mode 100644
index 0000000..4f9b381
Binary files /dev/null and b/test/fill-missed-stop-rgb24-ref.png differ
diff --git a/test/fill-missed-stop.c b/test/fill-missed-stop.c
new file mode 100644
index 0000000..cdf9ba5
--- /dev/null
+++ b/test/fill-missed-stop.c
@@ -0,0 +1,89 @@
+/*
+ * Copyright ?? 2006 M Joonas Pihlaja
+ *
+ * Permission to use, copy, modify, distribute, and sell this software
+ * and its documentation for any purpose is hereby granted without
+ * fee, provided that the above copyright notice appear in all copies
+ * and that both that copyright notice and this permission notice
+ * appear in supporting documentation, and that the name of Joonas Pihlaja
+ * not be used in advertising or publicity pertaining to distribution
+ * of the software without specific, written prior permission.
+ * Joonas Pihlaja makes no representations about the suitability of this
+ * software for any purpose. It is provided "as is" without express
+ * or implied warranty.
+ *
+ * JOONAS PIHLAJA DISCLAIMS ALL WARRANTIES WITH REGARD TO THIS SOFTWARE,
+ * INCLUDING ALL IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS, IN
+ * NO EVENT SHALL JOONAS PIHLAJA BE LIABLE FOR ANY SPECIAL, INDIRECT OR
+ * CONSEQUENTIAL DAMAGES OR ANY DAMAGES WHATSOEVER RESULTING FROM LOSS
+ * OF USE, DATA OR PROFITS, WHETHER IN AN ACTION OF CONTRACT,
+ * NEGLIGENCE OR OTHER TORTIOUS ACTION, ARISING OUT OF OR IN
+ * CONNECTION WITH THE USE OR PERFORMANCE OF THIS SOFTWARE.
+ *
+ * Author: M Joonas Pihlaja <jpihlaja at cc.helsinki.fi>
+ */
+
+/* Bug history
+ *
+ * 2006-12-05 M Joonas Pihlaja <jpihlaja at cc.helsinki.fi>
+ *
+ * The tessellator has a regression where a trapezoid may continue
+ * below the end of a polygon edge (i.e. the bottom of the trapezoid
+ * is miscomputed.) This can only happen if the right edge of a
+ * trapezoid stops earlier than the left edge and there is no start
+ * event at the end point of the right edge.
+ */
+
+#include "cairo-test.h"
+
+static cairo_test_draw_function_t draw;
+#define SIZE 50
+
+cairo_test_t test = {
+ "fill-missed-stop",
+ "Tests that the tessellator doesn't miss stop events when generating trapezoids",
+ SIZE+3, SIZE+3,
+ draw
+};
+
+static cairo_test_status_t
+draw (cairo_t *cr, int width, int height)
+{
+ cairo_set_source_rgb (cr, 1, 0, 0);
+
+ cairo_translate (cr, 1, 1);
+
+ /* What it should look like, with # marking the filled areas:
+ *
+ * |\ |\
+ * |#\ |#\
+ * |##\__|##\
+ * \#|
+ * \|
+ *
+ * What it looke like with the bug, when the rightmost edge's end
+ * is missed:
+ *
+ * |\ |\
+ * |#\ |#\
+ * |##\__|##\
+ * \#####|
+ * \####|
+ */
+
+ cairo_move_to (cr, 0, 0);
+ cairo_line_to (cr, SIZE/2, SIZE);
+ cairo_line_to (cr, SIZE/2, 0);
+ cairo_line_to (cr, SIZE, SIZE/2);
+ cairo_line_to (cr, 0, SIZE/2);
+ cairo_close_path (cr);
+ cairo_fill (cr);
+
+ return CAIRO_TEST_SUCCESS;
+}
+
+int
+main (void)
+{
+ return cairo_test (&test);
+}
--
1.4.1.1
-------------- next part --------------
From 5bf6f3ceefb264477603259a7c6fb368235518b4 Mon Sep 17 00:00:00 2001
From: M Joonas Pihlaja <jpihlaja at cc.helsinki.fi>
Date: Tue, 5 Dec 2006 21:31:23 +0200
Subject: [PATCH] tessellator bug fix: fill-degenerate-sort-order
Fixes the regression fill-degenerate-sort-order, where
confusion arises in the event order for collinear edges.
Also fixes (or at least hides) the issues with zrusin-another
sometimes generating different trapezoids depending on the
state of the random number generator in cairo-skiplist.c.
---
src/cairo-bentley-ottmann.c | 40 +++++++++++++++++++++++++++++-----------
1 files changed, 29 insertions(+), 11 deletions(-)
diff --git a/src/cairo-bentley-ottmann.c b/src/cairo-bentley-ottmann.c
index 2c0f98c..284e247 100644
--- a/src/cairo-bentley-ottmann.c
+++ b/src/cairo-bentley-ottmann.c
@@ -393,15 +393,20 @@ cairo_bo_event_compare (cairo_bo_event_t
return - cmp;
}
- /* As a final discrimination, look at the opposite point. This
- * leaves ambiguities only for identical edges.
- */
- if (a->type == CAIRO_BO_EVENT_TYPE_START)
- return _cairo_bo_point32_compare (&b->e1->bottom,
- &a->e1->bottom);
- else if (a->type == CAIRO_BO_EVENT_TYPE_STOP)
- return _cairo_bo_point32_compare (&a->e1->top,
- &b->e1->top);
+ /* Next look at the opposite point. This leaves ambiguities only
+ * for identical edges. */
+ if (a->type == CAIRO_BO_EVENT_TYPE_START) {
+ cmp = _cairo_bo_point32_compare (&b->e1->bottom,
+ &a->e1->bottom);
+ if (cmp)
+ return cmp;
+ }
+ else if (a->type == CAIRO_BO_EVENT_TYPE_STOP) {
+ cmp = _cairo_bo_point32_compare (&a->e1->top,
+ &b->e1->top);
+ if (cmp)
+ return cmp;
+ }
else { /* CAIRO_BO_EVENT_TYPE_INTERSECT */
/* For two intersection events at the identical point, we
* don't care what order they sort in, but we do care that we
@@ -416,8 +421,21 @@ cairo_bo_event_compare (cairo_bo_event_t
cmp = _cairo_bo_point32_compare (&a->e1->top, &b->e1->top);
if (cmp)
return cmp;
- return _cairo_bo_point32_compare (&a->e1->bottom, &b->e1->bottom);
- }
+ cmp = _cairo_bo_point32_compare (&a->e1->bottom, &b->e1->bottom);
+ if (cmp)
+ return cmp;
+ }
+
+ /* Discrimination based on the edge pointers. */
+ if (a->e1 < b->e1)
+ return -1;
+ if (a->e1 > b->e1)
+ return +1;
+ if (a->e2 < b->e2)
+ return -1;
+ if (a->e2 > b->e2)
+ return +1;
+ return 0;
}
static inline int
--
1.4.1.1
-------------- next part --------------
From 92fbb491e41f31dc3dc19157d6611824335cfd63 Mon Sep 17 00:00:00 2001
From: M Joonas Pihlaja <jpihlaja at cc.helsinki.fi>
Date: Tue, 5 Dec 2006 21:38:25 +0200
Subject: [PATCH] tessellator bug fix: fill-missed-stop
Fixes the regression exhibited by the test fill-missed-stop,
where the tessellator would sometimes extend a trapezoid
too far below the end of the right edge.
---
src/cairo-bentley-ottmann.c | 8 +++++++-
1 files changed, 7 insertions(+), 1 deletions(-)
diff --git a/src/cairo-bentley-ottmann.c b/src/cairo-bentley-ottmann.c
index 284e247..5d521b8 100644
--- a/src/cairo-bentley-ottmann.c
+++ b/src/cairo-bentley-ottmann.c
@@ -1064,15 +1064,21 @@ _cairo_bo_edge_end_trap (cairo_bo_edge_t
cairo_fixed_t fixed_top, fixed_bot;
cairo_status_t status = CAIRO_STATUS_SUCCESS;
cairo_bo_trap_t *trap = left->deferred_trap;
+ cairo_bo_edge_t *right;
if (!trap)
return CAIRO_STATUS_SUCCESS;
+ /* If the right edge of the trapezoid stopped earlier than the
+ * left edge, then cut the trapezoid bottom early. */
+ right = trap->right;
+ if (right->bottom.y < bot)
+ bot = right->bottom.y;
+
fixed_top = trap->top >> CAIRO_BO_GUARD_BITS;
fixed_bot = bot >> CAIRO_BO_GUARD_BITS;
if (fixed_top < fixed_bot) {
- cairo_bo_edge_t *right = trap->right;
cairo_point_t left_top, left_bot, right_top, right_bot;
left_top.x = left->top.x >> CAIRO_BO_GUARD_BITS;
--
1.4.1.1
-------------- next part --------------
From 35d8c8c1816779ff39c6236ee1bdb2b79b46ea26 Mon Sep 17 00:00:00 2001
From: M Joonas Pihlaja <jpihlaja at cc.helsinki.fi>
Date: Tue, 5 Dec 2006 21:55:50 +0200
Subject: [PATCH] tessellator bug fix: in-fill-empty-trapezoid
The cairo_in_fill() function sometimes gives false positives
when it samples a point on the edge of an empty trapezoid.
This patch alleviates the bug (but doesn't fix it completely),
for the common(?) case where the left and right edges of the
empty trapezoid have equal top and bottom points.
---
src/cairo-bentley-ottmann.c | 31 +++++++++++++++++++++----------
1 files changed, 21 insertions(+), 10 deletions(-)
diff --git a/src/cairo-bentley-ottmann.c b/src/cairo-bentley-ottmann.c
index 5d521b8..3767fdf 100644
--- a/src/cairo-bentley-ottmann.c
+++ b/src/cairo-bentley-ottmann.c
@@ -1078,6 +1078,7 @@ _cairo_bo_edge_end_trap (cairo_bo_edge_t
fixed_top = trap->top >> CAIRO_BO_GUARD_BITS;
fixed_bot = bot >> CAIRO_BO_GUARD_BITS;
+ /* Only emit trapezoids with positive height. */
if (fixed_top < fixed_bot) {
cairo_point_t left_top, left_bot, right_top, right_bot;
@@ -1090,19 +1091,29 @@ _cairo_bo_edge_end_trap (cairo_bo_edge_t
right_bot.x = right->bottom.x >> CAIRO_BO_GUARD_BITS;
right_bot.y = right->bottom.y >> CAIRO_BO_GUARD_BITS;
- status = _cairo_traps_add_trap_from_points (bo_traps->traps,
- fixed_top,
- fixed_bot,
- left_top, left_bot,
- right_top, right_bot);
+ /* Avoid emitting the trapezoid if it is obviously degenerate.
+ * TODO: need a real collinearity test here for the cases
+ * where the trapezoid is degenerate, yet the top and bottom
+ * coordinates aren't equal. */
+ if (left_top.x != right_top.x ||
+ left_top.y != right_top.y ||
+ left_bot.x != right_bot.x ||
+ left_bot.y != right_bot.y)
+ {
+ status = _cairo_traps_add_trap_from_points (bo_traps->traps,
+ fixed_top,
+ fixed_bot,
+ left_top, left_bot,
+ right_top, right_bot);
#if DEBUG_PRINT_STATE
- printf ("Deferred trap: left=(%08x, %08x)-(%08x,%08x) "
- "right=(%08x,%08x)-(%08x,%08x) top=%08x, bot=%08x\n",
- left->top.x, left->top.y, left->bottom.x, left->bottom.y,
- right->top.x, right->top.y, right->bottom.x, right->bottom.y,
- trap->top, bot);
+ printf ("Deferred trap: left=(%08x, %08x)-(%08x,%08x) "
+ "right=(%08x,%08x)-(%08x,%08x) top=%08x, bot=%08x\n",
+ left->top.x, left->top.y, left->bottom.x, left->bottom.y,
+ right->top.x, right->top.y, right->bottom.x, right->bottom.y,
+ trap->top, bot);
#endif
+ }
}
_cairo_freelist_free (&bo_traps->freelist, trap);
--
1.4.1.1
-------------- next part --------------
From ff2118375af9830cca35108779314692acc503a0 Mon Sep 17 00:00:00 2001
From: M Joonas Pihlaja <jpihlaja at cc.helsinki.fi>
Date: Tue, 5 Dec 2006 22:56:22 +0200
Subject: [PATCH] tessellator: offset working coordinates to be nonnegative
This patch improves the translation invariance of the tessellator
by offsetting all input coordinates to be nonnegative and paves
the way for future optimisations using the coordinate range.
Also changes the assertions to make sure that it is safe to add
the guard bits. This needs to be changed to do something sensible
about input coordinates that are too large instead of croaking.
The plan is to steal the guard bits from the least significant
instead of the most significant user bits, and having all coordinates
nonnegative will make the rounding involved there easier.
---
src/cairo-bentley-ottmann.c | 126 +++++++++++++++++++++++++++++++++----------
1 files changed, 96 insertions(+), 30 deletions(-)
diff --git a/src/cairo-bentley-ottmann.c b/src/cairo-bentley-ottmann.c
index 3767fdf..a0d6502 100644
--- a/src/cairo-bentley-ottmann.c
+++ b/src/cairo-bentley-ottmann.c
@@ -40,6 +40,10 @@ #include "cairo-skiplist-private.h"
#include "cairo-freelist-private.h"
#define CAIRO_BO_GUARD_BITS 2
+#define CAIRO_BO_GUARD_UNITY (1 << CAIRO_BO_GUARD_BITS)
+#define CAIRO_BO_GUARD_HALF (CAIRO_BO_GUARD_UNITY / 2)
+#define _cairo_bo_add_guard_bits(x) ((x) * CAIRO_BO_GUARD_UNITY)
+#define _cairo_bo_strip_guard_bits(x) ((x) / CAIRO_BO_GUARD_UNITY)
typedef cairo_point_t cairo_bo_point32_t;
@@ -72,6 +76,13 @@ struct _cairo_bo_trap {
struct _cairo_bo_traps {
cairo_traps_t *traps;
cairo_freelist_t freelist;
+
+ /* These form the extent of the original input points without any
+ * guard bits. */
+ cairo_fixed_t xmin;
+ cairo_fixed_t ymin;
+ cairo_fixed_t xmax;
+ cairo_fixed_t ymax;
};
struct _cairo_bo_edge {
@@ -765,12 +776,6 @@ _cairo_bo_event_queue_init (cairo_bo_eve
sorted_event_ptrs[2*i] = &events[2*i];
sorted_event_ptrs[2*i+1] = &events[2*i+1];
- /* We must not be given horizontal edges. */
- assert (edges[i].top.y != edges[i].bottom.y);
-
- /* We also must not be given any upside-down edges. */
- assert (_cairo_bo_point32_compare (&edges[i].top, &edges[i].bottom) < 0);
-
/* Initialize "middle" to top */
edges[i].middle = edges[i].top;
@@ -1075,21 +1080,25 @@ _cairo_bo_edge_end_trap (cairo_bo_edge_t
if (right->bottom.y < bot)
bot = right->bottom.y;
- fixed_top = trap->top >> CAIRO_BO_GUARD_BITS;
- fixed_bot = bot >> CAIRO_BO_GUARD_BITS;
+ fixed_top = _cairo_bo_strip_guard_bits (trap->top);
+ fixed_bot = _cairo_bo_strip_guard_bits (bot);
/* Only emit trapezoids with positive height. */
if (fixed_top < fixed_bot) {
cairo_point_t left_top, left_bot, right_top, right_bot;
-
- left_top.x = left->top.x >> CAIRO_BO_GUARD_BITS;
- left_top.y = left->top.y >> CAIRO_BO_GUARD_BITS;
- right_top.x = right->top.x >> CAIRO_BO_GUARD_BITS;
- right_top.y = right->top.y >> CAIRO_BO_GUARD_BITS;
- left_bot.x = left->bottom.x >> CAIRO_BO_GUARD_BITS;
- left_bot.y = left->bottom.y >> CAIRO_BO_GUARD_BITS;
- right_bot.x = right->bottom.x >> CAIRO_BO_GUARD_BITS;
- right_bot.y = right->bottom.y >> CAIRO_BO_GUARD_BITS;
+ cairo_fixed_t xmin = bo_traps->xmin;
+ cairo_fixed_t ymin = bo_traps->ymin;
+ fixed_top += ymin;
+ fixed_bot += ymin;
+
+ left_top.x = _cairo_bo_strip_guard_bits (left->top.x) + xmin;
+ left_top.y = _cairo_bo_strip_guard_bits (left->top.y) + ymin;
+ right_top.x = _cairo_bo_strip_guard_bits (right->top.x) + xmin;
+ right_top.y = _cairo_bo_strip_guard_bits (right->top.y) + ymin;
+ left_bot.x = _cairo_bo_strip_guard_bits (left->bottom.x) + xmin;
+ left_bot.y = _cairo_bo_strip_guard_bits (left->bottom.y) + ymin;
+ right_bot.x = _cairo_bo_strip_guard_bits (right->bottom.x) + xmin;
+ right_bot.y = _cairo_bo_strip_guard_bits (right->bottom.y) + ymin;
/* Avoid emitting the trapezoid if it is obviously degenerate.
* TODO: need a real collinearity test here for the cases
@@ -1154,10 +1163,18 @@ _cairo_bo_edge_start_or_continue_trap (c
static void
_cairo_bo_traps_init (cairo_bo_traps_t *bo_traps,
- cairo_traps_t *traps)
+ cairo_traps_t *traps,
+ cairo_fixed_t xmin,
+ cairo_fixed_t ymin,
+ cairo_fixed_t xmax,
+ cairo_fixed_t ymax)
{
bo_traps->traps = traps;
_cairo_freelist_init (&bo_traps->freelist, sizeof(cairo_bo_trap_t));
+ bo_traps->xmin = xmin;
+ bo_traps->ymin = ymin;
+ bo_traps->xmax = xmax;
+ bo_traps->ymax = ymax;
}
static void
@@ -1196,7 +1213,6 @@ _cairo_bo_sweep_line_validate (cairo_bo_
static cairo_status_t
_active_edges_to_traps (cairo_bo_edge_t *head,
int32_t top,
- int32_t bottom,
cairo_fill_rule_t fill_rule,
cairo_bo_traps_t *bo_traps)
{
@@ -1242,6 +1258,10 @@ _cairo_bentley_ottmann_tessellate_bo_edg
int num_edges,
cairo_fill_rule_t fill_rule,
cairo_traps_t *traps,
+ cairo_fixed_t xmin,
+ cairo_fixed_t ymin,
+ cairo_fixed_t xmax,
+ cairo_fixed_t ymax,
int *num_intersections)
{
cairo_status_t status = CAIRO_STATUS_SUCCESS;
@@ -1258,16 +1278,15 @@ _cairo_bentley_ottmann_tessellate_bo_edg
for (i = 0; i < num_edges; i++) {
edge = &edges[i];
- edge->top.x <<= CAIRO_BO_GUARD_BITS;
- edge->top.y <<= CAIRO_BO_GUARD_BITS;
- edge->middle = edge->top;
- edge->bottom.x <<= CAIRO_BO_GUARD_BITS;
- edge->bottom.y <<= CAIRO_BO_GUARD_BITS;
+ edge->top.x = _cairo_bo_add_guard_bits (edge->top.x);
+ edge->top.y = _cairo_bo_add_guard_bits (edge->top.y);
+ edge->bottom.x = _cairo_bo_add_guard_bits (edge->bottom.x);
+ edge->bottom.y = _cairo_bo_add_guard_bits (edge->bottom.y);
}
_cairo_bo_event_queue_init (&event_queue, edges, num_edges);
_cairo_bo_sweep_line_init (&sweep_line);
- _cairo_bo_traps_init (&bo_traps, traps);
+ _cairo_bo_traps_init (&bo_traps, traps, xmin, ymin, xmax, ymax);
#if DEBUG_PRINT_STATE
print_state ("After initializing", &event_queue, &sweep_line);
@@ -1281,7 +1300,7 @@ #endif
if (event->point.y != sweep_line.current_y) {
status = _active_edges_to_traps (sweep_line.head,
- sweep_line.current_y, event->point.y,
+ sweep_line.current_y,
fill_rule, &bo_traps);
if (status)
goto unwind;
@@ -1385,6 +1404,17 @@ #endif
return status;
}
+static void
+update_minmax(cairo_fixed_t *inout_min,
+ cairo_fixed_t *inout_max,
+ cairo_fixed_t v)
+{
+ if (v < *inout_min)
+ *inout_min = v;
+ if (v > *inout_max)
+ *inout_max = v;
+}
+
cairo_status_t
_cairo_bentley_ottmann_tessellate_polygon (cairo_traps_t *traps,
cairo_polygon_t *polygon,
@@ -1393,16 +1423,35 @@ _cairo_bentley_ottmann_tessellate_polygo
int intersections;
cairo_status_t status;
cairo_bo_edge_t *edges;
+ cairo_fixed_t xmin = 0x7FFFFFFF;
+ cairo_fixed_t ymin = 0x7FFFFFFF;
+ cairo_fixed_t xmax = -0x80000000;
+ cairo_fixed_t ymax = -0x80000000;
int i;
+ if (0 == polygon->num_edges)
+ return CAIRO_STATUS_SUCCESS;
+
edges = malloc (polygon->num_edges * sizeof (cairo_bo_edge_t));
if (edges == NULL)
return CAIRO_STATUS_NO_MEMORY;
+ /* Figure out the bounding box of input coordinates and validate
+ * that we're not given invalid polygon edges. */
for (i = 0; i < polygon->num_edges; i++) {
- edges[i].top = polygon->edges[i].edge.p1;
- edges[i].middle = edges[i].top;
- edges[i].bottom = polygon->edges[i].edge.p2;
+ update_minmax(&xmin, &xmax, polygon->edges[i].edge.p1.x);
+ update_minmax(&ymin, &ymax, polygon->edges[i].edge.p1.y);
+ update_minmax(&xmin, &xmax, polygon->edges[i].edge.p2.x);
+ update_minmax(&ymin, &ymax, polygon->edges[i].edge.p2.y);
+ assert (polygon->edges[i].edge.p1.y <= polygon->edges[i].edge.p2.y &&
+ "BUG: tessellator given upside down or horizontal edges");
+ }
+
+ for (i = 0; i < polygon->num_edges; i++) {
+ edges[i].top.x = polygon->edges[i].edge.p1.x - xmin;
+ edges[i].top.y = polygon->edges[i].edge.p1.y - ymin;
+ edges[i].bottom.x = polygon->edges[i].edge.p2.x - xmin;
+ edges[i].bottom.y = polygon->edges[i].edge.p2.y - ymin;
/* XXX: The 'clockWise' name that cairo_polygon_t uses is
* totally bogus. It's really a (negated!) description of
* whether the edge is reversed. */
@@ -1411,6 +1460,21 @@ _cairo_bentley_ottmann_tessellate_polygo
edges[i].prev = NULL;
edges[i].next = NULL;
edges[i].sweep_line_elt = NULL;
+
+ /* Make sure the input coordinates aren't too large that they
+ * overflow after we later shift them to make room for the
+ * guard bits. Note that the coordinates should now all be
+ * non-negative, so as a side effect we will know that
+ * absolute values of coordinate deltas all fit in 31 bits.
+ * If the original polygon input coordinates span a >= 2^31
+ * range, we will catch that here, as then the offsetting by
+ * (xoffset,yoffset) won't have brought them into range. XXX:
+ * relies on unsigned comparison. */
+ assert ((uint32_t)edges[i].top.x < (1UL << (31-CAIRO_BO_GUARD_BITS)) &&
+ (uint32_t)edges[i].top.y < (1UL << (31-CAIRO_BO_GUARD_BITS)) &&
+ (uint32_t)edges[i].bottom.x < (1UL << (31-CAIRO_BO_GUARD_BITS)) &&
+ (uint32_t)edges[i].bottom.y < (1UL << (31-CAIRO_BO_GUARD_BITS)) &&
+ "FIXME: input coordinates to tessellator too magnificent");
}
/* XXX: This would be the convenient place to throw in multiple
@@ -1418,7 +1482,9 @@ _cairo_bentley_ottmann_tessellate_polygo
* require storing the results of each pass into a temporary
* cairo_traps_t. */
status = _cairo_bentley_ottmann_tessellate_bo_edges (edges, polygon->num_edges,
- fill_rule, traps, &intersections);
+ fill_rule, traps,
+ xmin, ymin, xmax, ymax,
+ &intersections);
free (edges);
--
1.4.1.1
-------------- next part --------------
From 169244d96768d9a0dc873c97ccfe8e863779ecc2 Mon Sep 17 00:00:00 2001
From: M Joonas Pihlaja <jpihlaja at cc.helsinki.fi>
Date: Wed, 6 Dec 2006 02:03:35 +0200
Subject: [PATCH] tessellator: input validation and guard bit removal
This patch removes the guard bits from the tessellator internal
coordinates and reworks the input validation to make sure
that the tessellator code should never die on an assert.
When the extent of a polygon exceeds a width or height of 2^31-1,
then the rightmost (resp. bottommost) points are clamped to within
2^31-1 of the leftmost (resp. topmost) point of the polygon. The
clamping produces bad rendering for really large polygons, and
needs to be fixed in a saner manner.
---
src/cairo-bentley-ottmann.c | 112 ++++++++++++++++++++++++++++---------------
1 files changed, 72 insertions(+), 40 deletions(-)
diff --git a/src/cairo-bentley-ottmann.c b/src/cairo-bentley-ottmann.c
index a0d6502..e30efd3 100644
--- a/src/cairo-bentley-ottmann.c
+++ b/src/cairo-bentley-ottmann.c
@@ -39,9 +39,18 @@ #include "cairoint.h"
#include "cairo-skiplist-private.h"
#include "cairo-freelist-private.h"
-#define CAIRO_BO_GUARD_BITS 2
+/* XXX: We're not using guard bits anymore. We "know" that the
+ * intersection coordinates are computed to within an error of one
+ * subpixel unit, with a slight bias towards the negative
+ * infinities. */
+#define CAIRO_BO_GUARD_BITS 0
#define CAIRO_BO_GUARD_UNITY (1 << CAIRO_BO_GUARD_BITS)
-#define CAIRO_BO_GUARD_HALF (CAIRO_BO_GUARD_UNITY / 2)
+#define CAIRO_BO_GUARD_MASK (CAIRO_BO_GUARD_UNITY-1)
+
+/* The arguments to these macros are always non-negative, so the
+ * rounding is consistent towards negative infinity. An alternate
+ * implementation would steal guard bits from the least significant
+ * bits instead of the most significant bits as here. */
#define _cairo_bo_add_guard_bits(x) ((x) * CAIRO_BO_GUARD_UNITY)
#define _cairo_bo_strip_guard_bits(x) ((x) / CAIRO_BO_GUARD_UNITY)
@@ -527,8 +536,9 @@ intersect_lines (cairo_bo_edge_t *a,
/* 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.
+ * should prevent that before the tessellation algorithm begins.
+ * What we're doing to mitigate this is to perform clamping in
+ * cairo_bo_tessellate_polygon().
*/
int32_t dx1 = a->top.x - a->bottom.x;
int32_t dy1 = a->top.y - a->bottom.y;
@@ -1274,16 +1284,6 @@ _cairo_bentley_ottmann_tessellate_bo_edg
cairo_bo_edge_t *left, *right;
cairo_bo_edge_t *edge1, *edge2;
- int i;
-
- for (i = 0; i < num_edges; i++) {
- edge = &edges[i];
- edge->top.x = _cairo_bo_add_guard_bits (edge->top.x);
- edge->top.y = _cairo_bo_add_guard_bits (edge->top.y);
- edge->bottom.x = _cairo_bo_add_guard_bits (edge->bottom.x);
- edge->bottom.y = _cairo_bo_add_guard_bits (edge->bottom.y);
- }
-
_cairo_bo_event_queue_init (&event_queue, edges, num_edges);
_cairo_bo_sweep_line_init (&sweep_line);
_cairo_bo_traps_init (&bo_traps, traps, xmin, ymin, xmax, ymax);
@@ -1427,6 +1427,7 @@ _cairo_bentley_ottmann_tessellate_polygo
cairo_fixed_t ymin = 0x7FFFFFFF;
cairo_fixed_t xmax = -0x80000000;
cairo_fixed_t ymax = -0x80000000;
+ int num_bo_edges;
int i;
if (0 == polygon->num_edges)
@@ -1447,41 +1448,72 @@ _cairo_bentley_ottmann_tessellate_polygo
"BUG: tessellator given upside down or horizontal edges");
}
- for (i = 0; i < polygon->num_edges; i++) {
- edges[i].top.x = polygon->edges[i].edge.p1.x - xmin;
- edges[i].top.y = polygon->edges[i].edge.p1.y - ymin;
- edges[i].bottom.x = polygon->edges[i].edge.p2.x - xmin;
- edges[i].bottom.y = polygon->edges[i].edge.p2.y - ymin;
+ /* XXX: Check that the extent of the coordinates is at most 2^31-1
+ * units high or wide. We're going to clamp the maximums to be
+ * within 2^31 of the minimums if this isn't the case. XXX: This
+ * is the wrong thing to do! */
+ if ((int32_t)(xmax - xmin) < 0)
+ xmax = xmin + 0x7FFFFFFF;
+ if ((int32_t)(ymax - ymin) < 0)
+ ymax = ymin + 0x7FFFFFFF;
+
+ for (i = 0, num_bo_edges = 0; i < polygon->num_edges; i++) {
+ cairo_bo_edge_t *edge = &edges[num_bo_edges];
+ cairo_point_t top = polygon->edges[i].edge.p1;
+ cairo_point_t bot = polygon->edges[i].edge.p2;
+
+ /* Offset coordinates into the non-negative range. */
+ top.x -= xmin;
+ top.y -= ymin;
+ bot.x -= xmin;
+ bot.y -= ymin;
+
+ /* If the coordinates are still negative, then their extent
+ * is overflowing 2^31-1. We're going to kludge it and clamp
+ * the coordinates into the desired range. XXX: This is the
+ * wrong thing to do! */
+ if (top.x < 0) top.x = xmax - xmin;
+ if (top.y < 0) top.y = ymax - ymin;
+ if (bot.x < 0) bot.x = xmax - xmin;
+ if (bot.y < 0) bot.y = ymax - ymin;
+
+ /* Now steal guard bits. */
+ edge->top.x = _cairo_bo_add_guard_bits (top.x);
+ edge->top.y = _cairo_bo_add_guard_bits (top.y);
+ edge->bottom.x = _cairo_bo_add_guard_bits (bot.x);
+ edge->bottom.y = _cairo_bo_add_guard_bits (bot.y);
+
+ /* This catches the errors due to stealing most significant
+ * bits when we have CAIRO_BO_GUARD_BITS > 0. */
+ assert (edge->top.y <= edge->bottom.y &&
+ "BUG: adding guard bits or clamping the input range "
+ "flipped the orientation of an edge");
+
+ if (edge->top.y == edge->bottom.y) {
+ /* Ignore newly horizontal edges due to adding the guard
+ * bits. (This may happen if the guard bit adding doesn't
+ * respect ordering. Currently it doesn't though, since
+ * CAIRO_BO_GUARD_BITS is zero.) */
+ continue;
+ }
+
/* XXX: The 'clockWise' name that cairo_polygon_t uses is
* totally bogus. It's really a (negated!) description of
* whether the edge is reversed. */
- edges[i].reversed = (! polygon->edges[i].clockWise);
- edges[i].deferred_trap = NULL;
- edges[i].prev = NULL;
- edges[i].next = NULL;
- edges[i].sweep_line_elt = NULL;
-
- /* Make sure the input coordinates aren't too large that they
- * overflow after we later shift them to make room for the
- * guard bits. Note that the coordinates should now all be
- * non-negative, so as a side effect we will know that
- * absolute values of coordinate deltas all fit in 31 bits.
- * If the original polygon input coordinates span a >= 2^31
- * range, we will catch that here, as then the offsetting by
- * (xoffset,yoffset) won't have brought them into range. XXX:
- * relies on unsigned comparison. */
- assert ((uint32_t)edges[i].top.x < (1UL << (31-CAIRO_BO_GUARD_BITS)) &&
- (uint32_t)edges[i].top.y < (1UL << (31-CAIRO_BO_GUARD_BITS)) &&
- (uint32_t)edges[i].bottom.x < (1UL << (31-CAIRO_BO_GUARD_BITS)) &&
- (uint32_t)edges[i].bottom.y < (1UL << (31-CAIRO_BO_GUARD_BITS)) &&
- "FIXME: input coordinates to tessellator too magnificent");
+ edge->reversed = (! polygon->edges[i].clockWise);
+ edge->deferred_trap = NULL;
+ edge->prev = NULL;
+ edge->next = NULL;
+ edge->sweep_line_elt = NULL;
+
+ num_bo_edges++;
}
/* XXX: This would be the convenient place to throw in multiple
* passes of the Bentley-Ottmann algorithm. It would merely
* require storing the results of each pass into a temporary
* cairo_traps_t. */
- status = _cairo_bentley_ottmann_tessellate_bo_edges (edges, polygon->num_edges,
+ status = _cairo_bentley_ottmann_tessellate_bo_edges (edges, num_bo_edges,
fill_rule, traps,
xmin, ymin, xmax, ymax,
&intersections);
--
1.4.1.1
More information about the cairo
mailing list