[polygon] Amalgamate collinear edges

Combine sequential collinear edges into a single edge, this benefits
immensely by feeding fewer edges into either the tessellator or spans.

2 files changed, 54 insertions, 7 deletions

diff --git a/src/cairo-polygon.c b/src/cairo-polygon.c
index ac4d0945f..a8addff2e 100644
--- a/src/cairo-polygon.c
+++ b/src/cairo-polygon.c
@@ -49,6 +49,7 @@ _cairo_polygon_init (cairo_polygon_t *polygon)
     polygon->edges_size = ARRAY_LENGTH (polygon->edges_embedded);
 
     polygon->has_current_point = FALSE;
+    polygon->has_current_edge = FALSE;
     polygon->has_limits = FALSE;
 
     polygon->extents.p1.x = polygon->extents.p1.y = INT32_MAX;
@@ -357,6 +358,13 @@ void
 _cairo_polygon_move_to (cairo_polygon_t *polygon,
 			const cairo_point_t *point)
 {
+    if (polygon->has_current_edge) {
+	_cairo_polygon_add_edge (polygon,
+				 &polygon->last_point,
+				 &polygon->current_point);
+	polygon->has_current_edge = FALSE;
+    }
+
     if (! polygon->has_current_point) {
 	polygon->first_point = *point;
 	polygon->has_current_point = TRUE;
@@ -369,20 +377,56 @@ void
 _cairo_polygon_line_to (cairo_polygon_t *polygon,
 			const cairo_point_t *point)
 {
-    if (polygon->has_current_point)
-	_cairo_polygon_add_edge (polygon, &polygon->current_point, point);
+    /* squash collinear edges */
+    if (polygon->has_current_edge) {
+	if (polygon->current_point.x != point->x ||
+	    polygon->current_point.y != point->y)
+	{
+	    cairo_slope_t this;
+
+	    _cairo_slope_init (&this, &polygon->current_point, point);
+	    if (_cairo_slope_equal (&polygon->current_edge, &this)) {
+		polygon->current_point = *point;
+		return;
+	    }
+
+	    _cairo_polygon_add_edge (polygon,
+				     &polygon->last_point,
+				     &polygon->current_point);
+
+	    polygon->last_point = polygon->current_point;
+	    polygon->current_edge = this;
+	}
+    } else if (polygon->has_current_point) {
+	if (polygon->current_point.x != point->x ||
+	    polygon->current_point.y != point->y)
+	{
+	    polygon->last_point = polygon->current_point;
+	    _cairo_slope_init (&polygon->current_edge,
+			       &polygon->last_point,
+			       point);
+	    polygon->has_current_edge = TRUE;
+	}
+    } else {
+	polygon->first_point = *point;
+	polygon->has_current_point = TRUE;
+    }
 
-    _cairo_polygon_move_to (polygon, point);
+    polygon->current_point = *point;
 }
 
 void
 _cairo_polygon_close (cairo_polygon_t *polygon)
 {
     if (polygon->has_current_point) {
-	_cairo_polygon_add_edge (polygon,
-				 &polygon->current_point,
-				 &polygon->first_point);
-
+	_cairo_polygon_line_to (polygon, &polygon->first_point);
 	polygon->has_current_point = FALSE;
     }
+
+    if (polygon->has_current_edge) {
+	_cairo_polygon_add_edge (polygon,
+				 &polygon->last_point,
+				 &polygon->current_point);
+	polygon->has_current_edge = FALSE;
+    }
 }
diff --git a/src/cairo-types-private.h b/src/cairo-types-private.h
index fa7067852..1e1f823d8 100644
--- a/src/cairo-types-private.h
+++ b/src/cairo-types-private.h
@@ -247,8 +247,11 @@ typedef struct _cairo_polygon {
     cairo_status_t status;
 
     cairo_point_t first_point;
+    cairo_point_t last_point;
     cairo_point_t current_point;
+    cairo_slope_t current_edge;
     cairo_bool_t has_current_point;
+    cairo_bool_t has_current_edge;
 
     cairo_box_t extents;
     cairo_box_t limits;