[cairo-commit] 3 commits - src/cairo-polygon-reduce.c src/cairo-spans-compositor.c src/cairo-tor-scan-converter.c
Chris Wilson
ickle at kemper.freedesktop.org
Fri Jun 8 09:27:14 PDT 2012
src/cairo-polygon-reduce.c | 157 +++++++++++++----------------------------
src/cairo-spans-compositor.c | 2
src/cairo-tor-scan-converter.c | 9 +-
3 files changed, 60 insertions(+), 108 deletions(-)
New commits:
commit f228769dfe5a8b5d73c49a41e95e31ed73a77fb3
Author: Chris Wilson <chris at chris-wilson.co.uk>
Date: Fri Jun 8 17:22:41 2012 +0100
polygon-reduce: Reduce broken stopped-edge continuation
This is hopefully a lesser used path and the attempted optimisation to
continue a stopped edge with a colinear stopped edge highly unlikely and
lost in the noise of the general inefficiency of the routine. As it was
broken, rather than attempt to rectify the "optimisation" remove it.
Reported-by: Evangelos Foutras <evangelos at foutrelis.com>
Bugzilla: https://bugs.freedesktop.org/show_bug.cgi?id=50852
Signed-off-by: Chris Wilson <chris at chris-wilson.co.uk>
diff --git a/src/cairo-polygon-reduce.c b/src/cairo-polygon-reduce.c
index 8758070..ea457fe 100644
--- a/src/cairo-polygon-reduce.c
+++ b/src/cairo-polygon-reduce.c
@@ -42,6 +42,8 @@
#include "cairo-freelist-private.h"
#include "cairo-combsort-inline.h"
+#define DEBUG_POLYGON 0
+
typedef cairo_point_t cairo_bo_point32_t;
typedef struct _cairo_bo_intersect_ordinate {
@@ -114,7 +116,6 @@ typedef struct _cairo_bo_event_queue {
typedef struct _cairo_bo_sweep_line {
cairo_bo_edge_t *head;
- cairo_bo_edge_t *stopped;
int32_t current_y;
cairo_bo_edge_t *current_edge;
} cairo_bo_sweep_line_t;
@@ -476,8 +477,8 @@ edges_compare_x_for_y (const cairo_bo_edge_t *a,
static inline int
_line_equal (const cairo_line_t *a, const cairo_line_t *b)
{
- return a->p1.x == b->p1.x && a->p1.y == b->p1.y &&
- a->p2.x == b->p2.x && a->p2.y == b->p2.y;
+ return (a->p1.x == b->p1.x && a->p1.y == b->p1.y &&
+ a->p2.x == b->p2.x && a->p2.y == b->p2.y);
}
static int
@@ -1024,7 +1025,6 @@ static void
_cairo_bo_sweep_line_init (cairo_bo_sweep_line_t *sweep_line)
{
sweep_line->head = NULL;
- sweep_line->stopped = NULL;
sweep_line->current_y = INT32_MIN;
sweep_line->current_edge = NULL;
}
@@ -1139,6 +1139,8 @@ edges_colinear (const cairo_bo_edge_t *a, const cairo_bo_edge_t *b)
*/
if (a->edge.line.p1.y == b->edge.line.p1.y) {
return a->edge.line.p1.x == b->edge.line.p1.x;
+ } else if (a->edge.line.p2.y == b->edge.line.p2.y) {
+ return a->edge.line.p2.x == b->edge.line.p2.x;
} else if (a->edge.line.p1.y < b->edge.line.p1.y) {
return edge_compare_for_y_against_x (b,
a->edge.line.p1.y,
@@ -1205,82 +1207,48 @@ _active_edges_to_polygon (cairo_bo_edge_t *left,
cairo_polygon_t *polygon)
{
cairo_bo_edge_t *right;
+ unsigned int mask;
- if (fill_rule == CAIRO_FILL_RULE_WINDING) {
- while (left != NULL) {
- int in_out = left->edge.dir;
-
- right = left->next;
- if (left->deferred.right == NULL) {
- while (right != NULL && right->deferred.right == NULL)
- right = right->next;
-
- if (right != NULL && edges_colinear (left, right)) {
- /* continuation on left */
- left->deferred = right->deferred;
- right->deferred.right = NULL;
- }
- }
-
- right = left->next;
- while (right != NULL) {
- if (right->deferred.right != NULL)
- _cairo_bo_edge_end (right, top, polygon);
-
- in_out += right->edge.dir;
- if (in_out == 0) {
- cairo_bo_edge_t *next;
- cairo_bool_t skip = FALSE;
-
- /* skip co-linear edges */
- next = right->next;
- if (next != NULL)
- skip = edges_colinear (right, next);
+ if (fill_rule == CAIRO_FILL_RULE_WINDING)
+ mask = ~0;
+ else
+ mask = 1;
- if (! skip)
- break;
- }
+ while (left != NULL) {
+ int in_out = left->edge.dir;
+ right = left->next;
+ if (left->deferred.right == NULL) {
+ while (right != NULL && right->deferred.right == NULL)
right = right->next;
- }
-
- _cairo_bo_edge_start_or_continue (left, right, top, polygon);
- left = right;
- if (left != NULL)
- left = left->next;
+ if (right != NULL && edges_colinear (left, right)) {
+ /* continuation on left */
+ left->deferred = right->deferred;
+ right->deferred.right = NULL;
+ }
}
- } else {
- while (left != NULL) {
- int in_out = 0;
- right = left->next;
- while (right != NULL) {
- if (right->deferred.right != NULL)
- _cairo_bo_edge_end (right, top, polygon);
+ right = left->next;
+ while (right != NULL) {
+ if (right->deferred.right != NULL)
+ _cairo_bo_edge_end (right, top, polygon);
- if ((in_out++ & 1) == 0) {
- cairo_bo_edge_t *next;
- cairo_bool_t skip = FALSE;
-
- /* skip co-linear edges */
- next = right->next;
- if (next != NULL)
- skip = edges_colinear (right, next);
-
- if (! skip)
- break;
- }
-
- right = right->next;
+ in_out += right->edge.dir;
+ if ((in_out & mask) == 0) {
+ /* skip co-linear edges */
+ if (right->next == NULL || !edges_colinear (right, right->next))
+ break;
}
- _cairo_bo_edge_start_or_continue (left, right, top, polygon);
-
- left = right;
- if (left != NULL)
- left = left->next;
+ right = right->next;
}
+
+ _cairo_bo_edge_start_or_continue (left, right, top, polygon);
+
+ left = right;
+ if (left != NULL)
+ left = left->next;
}
}
@@ -1303,12 +1271,6 @@ _cairo_bentley_ottmann_tessellate_bo_edges (cairo_bo_event_t **start_events,
while ((event = _cairo_bo_event_dequeue (&event_queue))) {
if (event->point.y != sweep_line.current_y) {
- for (e1 = sweep_line.stopped; e1; e1 = e1->next) {
- if (e1->deferred.right != NULL)
- _cairo_bo_edge_end (e1, e1->edge.bottom, polygon);
- }
- sweep_line.stopped = NULL;
-
_active_edges_to_polygon (sweep_line.head,
sweep_line.current_y,
fill_rule, polygon);
@@ -1328,23 +1290,6 @@ _cairo_bentley_ottmann_tessellate_bo_edges (cairo_bo_event_t **start_events,
if (unlikely (status))
goto unwind;
- /* check to see if this is a continuation of a stopped edge */
- /* XXX change to an infinitesimal lengthening rule */
- for (left = sweep_line.stopped; left; left = left->next) {
- if (e1->edge.top <= left->edge.bottom &&
- edges_colinear (e1, left))
- {
- e1->deferred = left->deferred;
- if (left->prev != NULL)
- left->prev = left->next;
- else
- sweep_line.stopped = left->next;
- if (left->next != NULL)
- left->next->prev = left->prev;
- break;
- }
- }
-
left = e1->prev;
right = e1->next;
@@ -1371,14 +1316,8 @@ _cairo_bentley_ottmann_tessellate_bo_edges (cairo_bo_event_t **start_events,
_cairo_bo_sweep_line_delete (&sweep_line, e1);
- /* first, check to see if we have a continuation via a fresh edge */
- if (e1->deferred.right != NULL) {
- e1->next = sweep_line.stopped;
- if (sweep_line.stopped != NULL)
- sweep_line.stopped->prev = e1;
- sweep_line.stopped = e1;
- e1->prev = NULL;
- }
+ if (e1->deferred.right != NULL)
+ _cairo_bo_edge_end (e1, e1->edge.bottom, polygon);
if (left != NULL && right != NULL) {
status = _cairo_bo_event_queue_insert_if_intersect_below_current_y (&event_queue, left, right);
@@ -1420,10 +1359,6 @@ _cairo_bentley_ottmann_tessellate_bo_edges (cairo_bo_event_t **start_events,
}
}
- for (e1 = sweep_line.stopped; e1; e1 = e1->next) {
- if (e1->deferred.right != NULL)
- _cairo_bo_edge_end (e1, e1->edge.bottom, polygon);
- }
unwind:
_cairo_bo_event_queue_fini (&event_queue);
@@ -1447,6 +1382,12 @@ _cairo_polygon_reduce (cairo_polygon_t *polygon,
if (unlikely (0 == num_events))
return CAIRO_STATUS_SUCCESS;
+ if (DEBUG_POLYGON) {
+ FILE *file = fopen ("reduce_in.txt", "w");
+ _cairo_debug_print_polygon (file, polygon);
+ fclose (file);
+ }
+
events = stack_events;
event_ptrs = stack_event_ptrs;
if (num_events > ARRAY_LENGTH (stack_events)) {
@@ -1482,10 +1423,16 @@ _cairo_polygon_reduce (cairo_polygon_t *polygon,
num_events,
fill_rule,
polygon);
- polygon->num_limits = num_limits;
+ polygon->num_limits = num_limits;
if (events != stack_events)
free (events);
+ if (DEBUG_POLYGON) {
+ FILE *file = fopen ("reduce_out.txt", "w");
+ _cairo_debug_print_polygon (file, polygon);
+ fclose (file);
+ }
+
return status;
}
commit fc501fd6b5c378006cd8970c1dd30ee753817b6d
Author: Chris Wilson <chris at chris-wilson.co.uk>
Date: Fri Jun 8 17:22:17 2012 +0100
tor-scan-converter: Always recompute min-height following edge removal
Signed-off-by: Chris Wilson <chris at chris-wilson.co.uk>
diff --git a/src/cairo-tor-scan-converter.c b/src/cairo-tor-scan-converter.c
index 099b50b..8233260 100644
--- a/src/cairo-tor-scan-converter.c
+++ b/src/cairo-tor-scan-converter.c
@@ -1300,6 +1300,7 @@ sub_row (struct active_list *active,
pos->next = edge;
} else
prev_x = edge->x.quo;
+ active->min_height = -1;
} else {
edge->prev->next = next;
next->prev = edge->prev;
@@ -1318,12 +1319,13 @@ sub_row (struct active_list *active,
}
}
-inline static void dec (struct edge *e, int h)
+inline static void dec (struct active_list *a, struct edge *e, int h)
{
e->height_left -= h;
if (e->height_left == 0) {
e->prev->next = e->next;
e->next->prev = e->prev;
+ a->min_height = -1;
}
}
@@ -1350,12 +1352,12 @@ full_row (struct active_list *active,
struct edge *right;
int winding;
- dec (left, GRID_Y);
+ dec (active, left, GRID_Y);
winding = left->dir;
right = left->next;
do {
- dec (right, GRID_Y);
+ dec (active, right, GRID_Y);
winding += right->dir;
if ((winding & mask) == 0 && right->next->x.quo != right->x.quo)
@@ -1525,6 +1527,7 @@ step_edges (struct active_list *active, int count)
if (! edge->height_left) {
edge->prev->next = edge->next;
edge->next->prev = edge->prev;
+ active->min_height = -1;
}
}
}
commit 1bc696a8fda55ee75139f7d0123d348bbd96d2af
Author: Chris Wilson <chris at chris-wilson.co.uk>
Date: Fri Jun 8 17:20:32 2012 +0100
spans-compositor: After polygon intersection the fill rule is always non-zero
As it turns out due to the rules of polygon intersection, there is never
any overlapping spans so the choice is arbitrary. However, lets be
consistent with the rest of the code.
Signed-off-by: Chris Wilson <chris at chris-wilson.co.uk>
diff --git a/src/cairo-spans-compositor.c b/src/cairo-spans-compositor.c
index 6cc9a7b..602d6a6 100644
--- a/src/cairo-spans-compositor.c
+++ b/src/cairo-spans-compositor.c
@@ -934,6 +934,8 @@ clip_and_composite_polygon (const cairo_spans_compositor_t *compositor,
status = trim_extents_to_polygon (extents, polygon);
if (unlikely (status))
return status;
+
+ fill_rule = CAIRO_FILL_RULE_WINDING;
} else {
_cairo_polygon_fini (&clipper);
}
More information about the cairo-commit
mailing list