[cairo-commit] 2 commits - src/cairo-tor-scan-converter.c
Chris Wilson
ickle at kemper.freedesktop.org
Mon Aug 8 00:19:38 PDT 2011
src/cairo-tor-scan-converter.c | 326 ++++++++++++++++++++---------------------
1 file changed, 162 insertions(+), 164 deletions(-)
New commits:
commit 2d79276c495cd0dba330575ebc11e22646242dd6
Author: Chris Wilson <chris at chris-wilson.co.uk>
Date: Sun Aug 7 21:58:28 2011 +0100
tor: Inline reverse insertion sort for handling intersections
The majority of intersections are with the nearest neighbour only, or
within a few neighbours (in a dense intersection of lines) so if walk
the active list backwards and find the new place to insert upon an
intersection it is faster than performing a mergesort afterwards.
Given enough intersections, the win is quite huge (15-20% on many-strokes).
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 dccbf57..d4aa8a6 100644
--- a/src/cairo-tor-scan-converter.c
+++ b/src/cairo-tor-scan-converter.c
@@ -354,7 +354,16 @@ struct pool {
/* A polygon edge. */
struct edge {
/* Next in y-bucket or active list. */
- struct edge *next;
+ struct edge *next, *prev;
+
+ /* Number of subsample rows remaining to scan convert of this
+ * edge. */
+ grid_scaled_y_t height_left;
+
+ /* Original sign of the edge: +1 for downwards, -1 for upwards
+ * edges. */
+ int dir;
+ int vertical;
/* Current x coordinate while the edge is on the active
* list. Initialised to the x coordinate of the top of the
@@ -376,15 +385,6 @@ struct edge {
/* y2-y1 after orienting the edge downwards. */
grid_scaled_y_t dy;
-
- /* Number of subsample rows remaining to scan convert of this
- * edge. */
- grid_scaled_y_t height_left;
-
- /* Original sign of the edge: +1 for downwards, -1 for upwards
- * edges. */
- int dir;
- int vertical;
};
/* Number of subsample rows per y-bucket. Must be GRID_Y. */
@@ -486,7 +486,7 @@ struct cell_pair {
* the x-coordinate of the intercept of the edge and the scan line. */
struct active_list {
/* Leftmost edge on the current scan line. */
- struct edge *head;
+ struct edge head, tail;
/* A lower bound on the height of the active edges is used to
* estimate how soon some active edge ends. We can't advance the
@@ -1110,7 +1110,16 @@ polygon_add_edge (struct polygon *polygon,
static void
active_list_reset (struct active_list *active)
{
- active->head = NULL;
+ active->head.vertical = 1;
+ active->head.height_left = INT_MAX;
+ active->head.x.quo = INT_MIN;
+ active->head.prev = NULL;
+ active->head.next = &active->tail;
+ active->tail.prev = &active->head;
+ active->tail.next = NULL;
+ active->tail.x.quo = INT_MAX;
+ active->tail.height_left = INT_MAX;
+ active->tail.vertical = 1;
active->min_height = 0;
}
@@ -1239,6 +1248,13 @@ sort_edges (struct edge *list,
return remaining;
}
+static struct edge *
+merge_unsorted_edges (struct edge *head, struct edge *unsorted)
+{
+ sort_edges (unsorted, UINT_MAX, &unsorted);
+ return merge_sorted_edges (head, unsorted);
+}
+
/* Test if the edges on the active list can be safely advanced by a
* full row without intersections or any edges ending. */
inline static int
@@ -1252,7 +1268,7 @@ active_list_can_step_full_row (struct active_list *active)
if (active->min_height <= 0) {
int min_height = INT_MAX;
- e = active->head;
+ e = active->head.next;
while (NULL != e) {
if (e->height_left < min_height)
min_height = e->height_left;
@@ -1266,8 +1282,7 @@ active_list_can_step_full_row (struct active_list *active)
return 0;
/* Check for intersections as no edges end during the next row. */
- e = active->head;
- while (NULL != e) {
+ for (e = active->head.next; e != &active->tail; e = e->next) {
struct quorem x = e->x;
if (! e->vertical) {
@@ -1281,7 +1296,6 @@ active_list_can_step_full_row (struct active_list *active)
return 0;
prev_x = x.quo;
- e = e->next;
}
return 1;
@@ -1291,30 +1305,36 @@ active_list_can_step_full_row (struct active_list *active)
* active_list. */
inline static void
active_list_merge_edges_from_bucket(struct active_list *active,
- struct edge *edges)
+ struct edge *edges)
{
- struct edge *tail;
- grid_scaled_y_t min_height = active->min_height;
- for (tail = edges; tail; tail = tail->next) {
- if (tail->height_left < min_height)
- min_height = tail->height_left;
- }
- active->min_height = min_height;
+ struct edge *edge, *prev;
- sort_edges (edges, UINT_MAX, &edges);
- active->head = merge_sorted_edges (active->head, edges);
+ active->head.next = merge_unsorted_edges (active->head.next, edges);
+
+ /* update links within sort? */
+ for (edge = &active->head, prev = NULL; edge; prev = edge, edge = edge->next)
+ edge->prev = prev;
}
inline static void
-polygon_fill_buckets (struct edge *edge, int y, struct edge **buckets)
+polygon_fill_buckets (struct active_list *active,
+ struct edge *edge,
+ int y,
+ struct edge **buckets)
{
+ grid_scaled_y_t min_height = active->min_height;
+
while (edge) {
struct edge *next = edge->next;
int suby = edge->ytop - y;
edge->next = buckets[suby];
buckets[suby] = edge;
+ if (edge->height_left < min_height)
+ min_height = edge->height_left;
edge = next;
}
+
+ active->min_height = min_height;
}
/* Advance the edges on the active list by one subsample row by
@@ -1322,77 +1342,69 @@ polygon_fill_buckets (struct edge *edge, int y, struct edge **buckets)
inline static void
active_list_substep_edges(struct active_list *active)
{
- struct edge **cursor = &active->head;
grid_scaled_x_t prev_x = INT_MIN;
- struct edge *unsorted = NULL;
- struct edge *edge = *cursor;
+ struct edge *edge = active->head.next;
do {
- UNROLL3({
- struct edge *next;
-
- if (NULL == edge)
- break;
-
- next = edge->next;
- if (--edge->height_left) {
- edge->x.quo += edge->dxdy.quo;
- edge->x.rem += edge->dxdy.rem;
- if (edge->x.rem >= 0) {
- ++edge->x.quo;
- edge->x.rem -= edge->dy;
- }
-
- if (edge->x.quo < prev_x) {
- *cursor = next;
- edge->next = unsorted;
- unsorted = edge;
- } else {
- prev_x = edge->x.quo;
- cursor = &edge->next;
- }
- } else {
- *cursor = next;
+ struct edge *next;
+
+ if (&active->tail == edge)
+ break;
+
+ next = edge->next;
+ if (--edge->height_left) {
+ edge->x.quo += edge->dxdy.quo;
+ edge->x.rem += edge->dxdy.rem;
+ if (edge->x.rem >= 0) {
+ ++edge->x.quo;
+ edge->x.rem -= edge->dy;
}
- edge = next;
- })
- } while (1);
- if (unsorted) {
- sort_edges (unsorted, UINT_MAX, &unsorted);
- active->head = merge_sorted_edges (active->head, unsorted);
- }
+ if (edge->x.quo < prev_x) {
+ struct edge *pos = edge->prev;
+ pos->next = next;
+ next->prev = pos;
+ do {
+ pos = pos->prev;
+ } while (edge->x.quo < pos->x.quo);
+ pos->next->prev = edge;
+ edge->next = pos->next;
+ edge->prev = pos;
+ pos->next = edge;
+ } else
+ prev_x = edge->x.quo;
+ } else {
+ edge->prev->next = next;
+ next->prev = edge->prev;
+ }
+ edge = next;
+ } while (1);
}
inline static void
apply_nonzero_fill_rule_for_subrow (struct active_list *active,
struct cell_list *coverages)
{
- struct edge *edge = active->head;
- int winding = 0;
- int xstart;
- int xend;
+ struct edge *edge = active->head.next;
cell_list_rewind (coverages);
- while (NULL != edge) {
- xstart = edge->x.quo;
- winding = edge->dir;
+ while (&active->tail != edge) {
+ int xstart = edge->x.quo;
+ int winding = edge->dir;
while (1) {
edge = edge->next;
- if (NULL == edge)
+ if (&active->tail == edge)
return cell_list_add_unbounded_subspan (coverages, xstart);
winding += edge->dir;
if (0 == winding) {
- if (edge->next == NULL || edge->next->x.quo != edge->x.quo)
+ if (edge->next->x.quo != edge->x.quo)
break;
}
}
- xend = edge->x.quo;
- cell_list_add_subspan (coverages, xstart, xend);
-
+ cell_list_add_subspan (coverages, xstart, edge->x.quo);
edge = edge->next;
}
}
@@ -1401,31 +1413,27 @@ static void
apply_evenodd_fill_rule_for_subrow (struct active_list *active,
struct cell_list *coverages)
{
- struct edge *edge = active->head;
- int xstart;
- int xend;
+ struct edge *edge = active->head.next;
cell_list_rewind (coverages);
- while (NULL != edge) {
- xstart = edge->x.quo;
+ while (&active->tail != edge) {
+ int xstart = edge->x.quo;
while (1) {
edge = edge->next;
- if (NULL == edge) {
+ if (&active->tail == edge) {
cell_list_add_unbounded_subspan (coverages, xstart);
return;
}
- if (edge->next == NULL || edge->next->x.quo != edge->x.quo)
+ if (edge->next->x.quo != edge->x.quo)
break;
edge = edge->next;
}
- xend = edge->x.quo;
- cell_list_add_subspan (coverages, xstart, xend);
-
+ cell_list_add_subspan (coverages, xstart, edge->x.quo);
edge = edge->next;
}
}
@@ -1434,41 +1442,36 @@ static void
apply_nonzero_fill_rule_and_step_edges (struct active_list *active,
struct cell_list *coverages)
{
- struct edge **cursor = &active->head;
- struct edge *left_edge;
+ struct edge *pos = active->head.next;
- left_edge = *cursor;
- while (NULL != left_edge) {
+ while (&active->tail != pos) {
+ struct edge *left_edge = pos;
struct edge *right_edge;
- int winding = left_edge->dir;
+ int winding;
left_edge->height_left -= GRID_Y;
- if (left_edge->height_left)
- cursor = &left_edge->next;
- else
- *cursor = left_edge->next;
+ if (! left_edge->height_left) {
+ left_edge->prev->next = left_edge->next;
+ left_edge->next->prev = left_edge->prev;
+ }
+ winding = left_edge->dir;
+ right_edge = left_edge->next;
while (1) {
- right_edge = *cursor;
- if (NULL == right_edge) {
+ if (&active->tail == right_edge) {
cell_list_render_edge (coverages, left_edge, +1);
return;
}
right_edge->height_left -= GRID_Y;
- if (right_edge->height_left)
- cursor = &right_edge->next;
- else
- *cursor = right_edge->next;
+ if (! right_edge->height_left) {
+ right_edge->prev->next = right_edge->next;
+ right_edge->next->prev = right_edge->prev;
+ }
winding += right_edge->dir;
- if (0 == winding) {
- if (right_edge->next == NULL ||
- right_edge->next->x.quo != right_edge->x.quo)
- {
- break;
- }
- }
+ if (0 == winding && right_edge->next->x.quo != right_edge->x.quo)
+ break;
if (! right_edge->vertical) {
right_edge->x.quo += right_edge->dxdy_full.quo;
@@ -1478,12 +1481,14 @@ apply_nonzero_fill_rule_and_step_edges (struct active_list *active,
right_edge->x.rem -= right_edge->dy;
}
}
+
+ right_edge = right_edge->next;
}
cell_list_render_edge (coverages, left_edge, +1);
cell_list_render_edge (coverages, right_edge, -1);
- left_edge = *cursor;
+ pos = right_edge->next;
}
}
@@ -1491,37 +1496,33 @@ static void
apply_evenodd_fill_rule_and_step_edges (struct active_list *active,
struct cell_list *coverages)
{
- struct edge **cursor = &active->head;
- struct edge *left_edge;
+ struct edge *pos = active->head.next;
- left_edge = *cursor;
- while (NULL != left_edge) {
+ while (&active->tail != pos) {
+ struct edge *left_edge = pos;
struct edge *right_edge;
left_edge->height_left -= GRID_Y;
- if (left_edge->height_left)
- cursor = &left_edge->next;
- else
- *cursor = left_edge->next;
+ if (! left_edge->height_left) {
+ left_edge->prev->next = left_edge->next;
+ left_edge->next->prev = left_edge->prev;
+ }
+ right_edge = left_edge->next;
while (1) {
- right_edge = *cursor;
- if (NULL == right_edge) {
+ if (&active->tail == right_edge) {
cell_list_render_edge (coverages, left_edge, +1);
return;
}
right_edge->height_left -= GRID_Y;
- if (right_edge->height_left)
- cursor = &right_edge->next;
- else
- *cursor = right_edge->next;
+ if (! right_edge->height_left) {
+ right_edge->prev->next = right_edge->next;
+ right_edge->next->prev = right_edge->prev;
+ }
- if (right_edge->next == NULL ||
- right_edge->next->x.quo != right_edge->x.quo)
- {
+ if (right_edge->next->x.quo != right_edge->x.quo)
break;
- }
if (! right_edge->vertical) {
right_edge->x.quo += right_edge->dxdy_full.quo;
@@ -1531,12 +1532,14 @@ apply_evenodd_fill_rule_and_step_edges (struct active_list *active,
right_edge->x.rem -= right_edge->dy;
}
}
+
+ right_edge = right_edge->next;
}
cell_list_render_edge (coverages, left_edge, +1);
cell_list_render_edge (coverages, right_edge, -1);
- left_edge = *cursor;
+ pos = right_edge->next;
}
}
@@ -1677,7 +1680,7 @@ active_list_is_vertical (struct active_list *active)
{
struct edge *e;
- for (e = active->head; e != NULL; e = e->next) {
+ for (e = active->head.next; e != &active->tail; e = e->next) {
if (! e->vertical)
return FALSE;
}
@@ -1688,15 +1691,17 @@ active_list_is_vertical (struct active_list *active)
static void
step_edges (struct active_list *active, int count)
{
- struct edge **cursor = &active->head;
struct edge *edge;
- for (edge = *cursor; edge != NULL; edge = *cursor) {
- edge->height_left -= GRID_Y * count;
- if (edge->height_left)
- cursor = &edge->next;
- else
- *cursor = edge->next;
+ count *= GRID_Y;
+ for (edge = active->head.next; edge != &active->tail; edge = edge->next) {
+ edge->height_left -= count;
+ if (! edge->height_left) {
+ if (edge->prev)
+ edge->prev->next = edge->next;
+ if (edge->next)
+ edge->next->prev = edge->prev;
+ }
}
}
@@ -1733,7 +1738,8 @@ glitter_scan_converter_render(
/* Determine if we can ignore this row or use the full pixel
* stepper. */
if (GRID_Y == EDGE_Y_BUCKET_HEIGHT && ! polygon->y_buckets[i]) {
- if (! active->head) {
+ if (active->head.next == &active->tail) {
+ active->min_height = INT_MAX;
for (; j < h && ! polygon->y_buckets[j]; j++)
;
GLITTER_BLIT_COVERAGES_EMPTY (i+ymin_i, j-i, xmin_i, xmax_i);
@@ -1764,7 +1770,10 @@ glitter_scan_converter_render(
} else {
int sub;
- polygon_fill_buckets (polygon->y_buckets[i], (i+ymin_i)*GRID_Y, buckets);
+ polygon_fill_buckets (active,
+ polygon->y_buckets[i],
+ (i+ymin_i)*GRID_Y,
+ buckets);
/* Subsample this row. */
for (sub = 0; sub < GRID_Y; sub++) {
@@ -1785,10 +1794,7 @@ glitter_scan_converter_render(
GLITTER_BLIT_COVERAGES(coverages, i+ymin_i, j-i, xmin_i, xmax_i);
cell_list_reset (coverages);
- if (! active->head)
- active->min_height = INT_MAX;
- else
- active->min_height -= GRID_Y;
+ active->min_height -= GRID_Y;
}
/* Clean up the coverage blitter. */
commit 221c117f5d949896e70b01150249b2111e4b2003
Author: Chris Wilson <chris at chris-wilson.co.uk>
Date: Sun Aug 7 21:05:40 2011 +0100
tor: First perform a bucket sort before merge the sub-edges from the polygon
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 954c514..dccbf57 100644
--- a/src/cairo-tor-scan-converter.c
+++ b/src/cairo-tor-scan-converter.c
@@ -1290,38 +1290,30 @@ active_list_can_step_full_row (struct active_list *active)
/* Merges edges on the given subpixel row from the polygon to the
* active_list. */
inline static void
-active_list_merge_edges_from_polygon(struct active_list *active,
- struct edge **ptail,
- grid_scaled_y_t y,
- struct polygon *polygon)
+active_list_merge_edges_from_bucket(struct active_list *active,
+ struct edge *edges)
{
- /* Split off the edges on the current subrow and merge them into
- * the active list. */
- int min_height = active->min_height;
- struct edge *subrow_edges = NULL;
- struct edge *tail = *ptail;
-
- do {
- struct edge *next = tail->next;
-
- if (y == tail->ytop) {
- tail->next = subrow_edges;
- subrow_edges = tail;
-
- if (tail->height_left < min_height)
- min_height = tail->height_left;
-
- *ptail = next;
- } else
- ptail = &tail->next;
+ struct edge *tail;
+ grid_scaled_y_t min_height = active->min_height;
+ for (tail = edges; tail; tail = tail->next) {
+ if (tail->height_left < min_height)
+ min_height = tail->height_left;
+ }
+ active->min_height = min_height;
- tail = next;
- } while (tail);
+ sort_edges (edges, UINT_MAX, &edges);
+ active->head = merge_sorted_edges (active->head, edges);
+}
- if (subrow_edges) {
- sort_edges (subrow_edges, UINT_MAX, &subrow_edges);
- active->head = merge_sorted_edges (active->head, subrow_edges);
- active->min_height = min_height;
+inline static void
+polygon_fill_buckets (struct edge *edge, int y, struct edge **buckets)
+{
+ while (edge) {
+ struct edge *next = edge->next;
+ int suby = edge->ytop - y;
+ edge->next = buckets[suby];
+ buckets[suby] = edge;
+ edge = next;
}
}
@@ -1722,6 +1714,7 @@ glitter_scan_converter_render(
struct polygon *polygon = converter->polygon;
struct cell_list *coverages = converter->coverages;
struct active_list *active = converter->active;
+ struct edge *buckets[GRID_Y] = { 0 };
xmin_i = converter->xmin / GRID_X;
xmax_i = converter->xmax / GRID_X;
@@ -1769,16 +1762,15 @@ glitter_scan_converter_render(
step_edges (active, j - (i + 1));
}
} else {
- grid_scaled_y_t suby;
+ int sub;
- /* Subsample this row. */
- for (suby = 0; suby < GRID_Y; suby++) {
- grid_scaled_y_t y = (i+ymin_i)*GRID_Y + suby;
+ polygon_fill_buckets (polygon->y_buckets[i], (i+ymin_i)*GRID_Y, buckets);
- if (polygon->y_buckets[i]) {
- active_list_merge_edges_from_polygon (active,
- &polygon->y_buckets[i], y,
- polygon);
+ /* Subsample this row. */
+ for (sub = 0; sub < GRID_Y; sub++) {
+ if (buckets[sub]) {
+ active_list_merge_edges_from_bucket (active, buckets[sub]);
+ buckets[sub] = NULL;
}
if (nonzero_fill)
More information about the cairo-commit
mailing list