[cairo-commit] 8 commits - src/cairo-bentley-ottmann.c
test/fill-degenerate-sort-order.c
test/fill-degenerate-sort-order-ref.png
test/fill-degenerate-sort-order-rgb24-ref.png
test/fill-missed-stop.c test/fill-missed-stop-ps-argb32-ref.png
test/fill-missed-stop-ref.png test/fill-missed-stop-rgb24-ref.png
test/in-fill-empty-trapezoid.c test/in-fill-empty-trapezoid-ref.png
test/in-fill-empty-trapezoid-rgb24-ref.png test/Makefile.am
M. Joonas Pihlaja
joonas at kemper.freedesktop.org
Tue Dec 5 20:15:10 PST 2006
src/cairo-bentley-ottmann.c | 262 ++++++++++++++++++--------
test/Makefile.am | 10
test/fill-degenerate-sort-order-ref.png |binary
test/fill-degenerate-sort-order-rgb24-ref.png |binary
test/fill-degenerate-sort-order.c | 110 ++++++++++
test/fill-missed-stop-ps-argb32-ref.png |binary
test/fill-missed-stop-ref.png |binary
test/fill-missed-stop-rgb24-ref.png |binary
test/fill-missed-stop.c | 89 ++++++++
test/in-fill-empty-trapezoid-ref.png |binary
test/in-fill-empty-trapezoid-rgb24-ref.png |binary
test/in-fill-empty-trapezoid.c | 89 ++++++++
12 files changed, 484 insertions(+), 76 deletions(-)
New commits:
diff-tree d0eff3919646e8a4c9981c349e33060fdb27c94e (from f8ba74917296be226f7a957ad1a26685bb6d846c)
Author: M Joonas Pihlaja <jpihlaja at cc.helsinki.fi>
Date: Wed Dec 6 05:53:53 2006 +0200
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.
Cleaned up as per
http://lists.freedesktop.org/archives/cairo/2006-December/008806.html
diff --git a/src/cairo-bentley-ottmann.c b/src/cairo-bentley-ottmann.c
index a0d6502..a0cd4a6 100644
--- a/src/cairo-bentley-ottmann.c
+++ b/src/cairo-bentley-ottmann.c
@@ -39,12 +39,6 @@
#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;
typedef struct _cairo_bo_point128 {
@@ -77,8 +71,8 @@ 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. */
+ /* These form the closed bounding box of the original input
+ * points. */
cairo_fixed_t xmin;
cairo_fixed_t ymin;
cairo_fixed_t xmax;
@@ -252,7 +246,6 @@ edge_x_for_y (cairo_bo_edge_t *edge,
}
/* edge->top.x + (y - edge->top.y) * dx / dy */
- /* Multiplication followed by division means the guard bits cancel out. */
numerator = _cairo_int32x32_64_mul ((y - edge->top.y), dx);
quorem = _cairo_int64_divrem (numerator, dy);
quorem.quo += edge->top.x;
@@ -488,14 +481,12 @@ det32_64 (int32_t a,
cairo_int64_t bc;
/* det = a * d - b * c */
- ad = _cairo_int64_rsa (_cairo_int32x32_64_mul (a, d), CAIRO_BO_GUARD_BITS);
- bc = _cairo_int64_rsa (_cairo_int32x32_64_mul (b, c), CAIRO_BO_GUARD_BITS);
+ ad = _cairo_int32x32_64_mul (a, d);
+ bc = _cairo_int32x32_64_mul (b, c);
return _cairo_int64_sub (ad, bc);
}
-/* We don't shift right by CAIRO_BO_GUARD_BITS here, anticipating a
- * subsequent division. */
static inline cairo_int128_t
det64_128 (cairo_int64_t a,
cairo_int64_t b,
@@ -527,8 +518,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;
@@ -542,8 +534,6 @@ intersect_lines (cairo_bo_edge_t *a,
if (_cairo_int64_eq (den_det, 0))
return CAIRO_BO_STATUS_PARALLEL;
- /* The expansion of guard bits in this multiplication is left to
- * be reduced again by the subsequent division. */
a_det = det32_64 (a->top.x, a->top.y,
a->bottom.x, a->bottom.y);
b_det = det32_64 (b->top.x, b->top.y,
@@ -1080,8 +1070,8 @@ _cairo_bo_edge_end_trap (cairo_bo_edge_t
if (right->bottom.y < bot)
bot = right->bottom.y;
- fixed_top = _cairo_bo_strip_guard_bits (trap->top);
- fixed_bot = _cairo_bo_strip_guard_bits (bot);
+ fixed_top = trap->top;
+ fixed_bot = bot;
/* Only emit trapezoids with positive height. */
if (fixed_top < fixed_bot) {
@@ -1091,14 +1081,14 @@ _cairo_bo_edge_end_trap (cairo_bo_edge_t
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;
+ left_top.x = left->top.x + xmin;
+ left_top.y = left->top.y + ymin;
+ right_top.x = right->top.x + xmin;
+ right_top.y = right->top.y + ymin;
+ left_bot.x = left->bottom.x + xmin;
+ left_bot.y = left->bottom.y + ymin;
+ right_bot.x = right->bottom.x + xmin;
+ right_bot.y = right->bottom.y + ymin;
/* Avoid emitting the trapezoid if it is obviously degenerate.
* TODO: need a real collinearity test here for the cases
@@ -1274,16 +1264,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 +1407,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)
@@ -1436,52 +1417,80 @@ _cairo_bentley_ottmann_tessellate_polygo
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. */
+ /* Figure out the bounding box of the input coordinates and
+ * validate that we're not given invalid polygon edges. */
for (i = 0; i < polygon->num_edges; i++) {
- 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);
+ 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;
+ /* The tessellation functions currently assume that no line
+ * segment extends more than 2^31-1 in either dimension. We
+ * guarantee this by offsetting the internal coordinates to the
+ * range [0,2^31-1], and clamping to 2^31-1 if a coordinate
+ * exceeds the range (and yes, this generates an incorrect
+ * result). First we have to clamp the bounding box itself. */
+ /* XXX: Rather than changing the input values, a better approach
+ * would be to detect out-of-bounds input and return a
+ * CAIRO_STATUS_OVERFLOW value to the user. */
+ if (xmax - xmin < 0)
+ xmax = xmin + 0x7FFFFFFF;
+ if (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 clamped bounding box. */
+ 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;
+
+ if (top.y == bot.y) {
+ /* Clamping might have produced horizontal edges. Ignore
+ * those. */
+ continue;
+ }
+ assert (top.y < bot.y &&
+ "BUG: clamping the input range flipped the "
+ "orientation of an edge");
+
+ edge->top.x = top.x;
+ edge->top.y = top.y;
+ edge->bottom.x = bot.x;
+ edge->bottom.y = bot.y;
/* 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);
diff-tree f8ba74917296be226f7a957ad1a26685bb6d846c (from 633c51b4426f5405db0eac5edb81651b7e1491ef)
Author: M Joonas Pihlaja <jpihlaja at cc.helsinki.fi>
Date: Tue Dec 5 22:56:22 2006 +0200
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.
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-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 @@ _cairo_bentley_ottmann_tessellate_bo_edg
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 @@ _cairo_bentley_ottmann_tessellate_bo_edg
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);
diff-tree 633c51b4426f5405db0eac5edb81651b7e1491ef (from e6c8febca7a24f6cf4138a25c96a36e4e7721a92)
Author: M Joonas Pihlaja <jpihlaja at cc.helsinki.fi>
Date: Tue Dec 5 21:55:50 2006 +0200
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.
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);
diff-tree e6c8febca7a24f6cf4138a25c96a36e4e7721a92 (from 614117e487f36c66f2a479c96e1cb4daef625608)
Author: M Joonas Pihlaja <jpihlaja at cc.helsinki.fi>
Date: Tue Dec 5 21:38:25 2006 +0200
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.
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;
diff-tree 614117e487f36c66f2a479c96e1cb4daef625608 (from 48b42efcfee470a1224d6ad0646525964ac640c6)
Author: M Joonas Pihlaja <jpihlaja at cc.helsinki.fi>
Date: Tue Dec 5 21:31:23 2006 +0200
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.
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
diff-tree 48b42efcfee470a1224d6ad0646525964ac640c6 (from e94e0a1ca262ef67b527b13a5e9691ad42a43204)
Author: M Joonas Pihlaja <jpihlaja at cc.helsinki.fi>
Date: Tue Dec 5 13:02:47 2006 +0200
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.
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);
+}
diff-tree e94e0a1ca262ef67b527b13a5e9691ad42a43204 (from 00d7b6acdd263f7b46ea98c4a5b777fc93a65be5)
Author: M Joonas Pihlaja <jpihlaja at cc.helsinki.fi>
Date: Tue Dec 5 12:20:17 2006 +0200
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.
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);
+}
diff-tree 00d7b6acdd263f7b46ea98c4a5b777fc93a65be5 (from c92f23caa549651a05863ecda19c55c112350528)
Author: M Joonas Pihlaja <jpihlaja at cc.helsinki.fi>
Date: Tue Dec 5 11:21:14 2006 +0200
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.
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);
+}
More information about the cairo-commit
mailing list