[clip] Use geometric clipping for unaligned clips

For the simple cases where the clip is an unaligned box (or boxes), apply
the clip directly to the geometry and avoid having to use an intermediate
clip-mask.

1 files changed, 23 insertions, 262 deletions

diff --git a/src/cairo-bentley-ottmann.c b/src/cairo-bentley-ottmann.c
index 99f4655d7..cb508f518 100644
--- a/src/cairo-bentley-ottmann.c
+++ b/src/cairo-bentley-ottmann.c
@@ -216,28 +216,6 @@ _line_compute_intersection_x_for_y (const cairo_line_t *line,
     return x;
 }
 
-static cairo_fixed_t
-_line_compute_intersection_y_for_x (const cairo_line_t *line,
-				    cairo_fixed_t x)
-{
-    cairo_fixed_t y, dx;
-
-    if (x == line->p1.x)
-	return line->p1.y;
-    if (x == line->p2.x)
-	return line->p2.y;
-
-    y = line->p1.y;
-    dx = line->p2.x - line->p1.x;
-    if (dx != 0) {
-	y += _cairo_fixed_mul_div_floor (x - line->p1.x,
-					 line->p2.y - line->p1.y,
-					 dx);
-    }
-
-    return y;
-}
-
 static inline int
 _cairo_bo_point32_compare (cairo_bo_point32_t const *a,
 			   cairo_bo_point32_t const *b)
@@ -1801,217 +1779,12 @@ _cairo_bentley_ottmann_tessellate_polygon (cairo_traps_t	 *traps,
     return status;
 }
 
-static cairo_bool_t
-_points_outside (const cairo_fixed_t *x, const cairo_box_t *limits)
-{
-    if (x[0] < limits->p1.x || x[0] > limits->p2.x)
-	return TRUE;
-    if (x[1] < limits->p1.x || x[1] > limits->p2.x)
-	return TRUE;
-    if (x[2] < limits->p1.x || x[2] > limits->p2.x)
-	return TRUE;
-    if (x[3] < limits->p1.x || x[3] > limits->p2.x)
-	return TRUE;
-
-    return FALSE;
-}
-
-static int
-_add_event (const cairo_line_t *line,
-	   int32_t top, int32_t bottom,
-	   int dir,
-	   cairo_bo_start_event_t *event)
-{
-    if (top == bottom)
-	return 0;
-
-    event->type = CAIRO_BO_EVENT_TYPE_START;
-    event->point.y = top;
-    event->point.x = _line_compute_intersection_x_for_y (line, top);
-
-    event->edge.edge.line = *line;
-    event->edge.edge.top = top;
-    event->edge.edge.bottom = bottom;
-    event->edge.edge.dir = dir;
-
-    event->edge.deferred_trap.right = NULL;
-    event->edge.prev = NULL;
-    event->edge.next = NULL;
-
-    return 1;
-}
-
-static int
-_compute_clipped_trapezoid_edges (const cairo_traps_t *traps,
-				  const cairo_trapezoid_t *t,
-				  cairo_bo_start_event_t *events)
-{
-    cairo_fixed_t x[4];
-    int num_events = 0;
-    int top, bot;
-
-    /* compute points in clockwise orientation */
-    top = t->top;
-    bot = t->bottom;
-
-    x[0] = _line_compute_intersection_x_for_y (&t->left, top);
-    x[1] = _line_compute_intersection_x_for_y (&t->right, top);
-    x[2] = _line_compute_intersection_x_for_y (&t->right, bot);
-    x[3] = _line_compute_intersection_x_for_y (&t->left, bot);
-
-    if (traps->has_limits && _points_outside (x, &traps->limits)) {
-	cairo_line_t limits[2];
-	cairo_fixed_t ly[2], ry[2];
-	cairo_fixed_t ymin, ymax;
-
-	limits[0].p1.x = traps->limits.p1.x;
-	limits[0].p1.y = traps->limits.p1.y;
-	limits[0].p2.x = traps->limits.p1.x;
-	limits[0].p2.y = traps->limits.p2.y;
-
-	limits[1].p1.x = traps->limits.p2.x;
-	limits[1].p1.y = traps->limits.p1.y;
-	limits[1].p2.x = traps->limits.p2.x;
-	limits[1].p2.y = traps->limits.p2.y;
-
-	ly[0] = _line_compute_intersection_y_for_x (&t->left,
-						    traps->limits.p1.x);
-	ymin = ymax = ly[0];
-
-	ly[1] = _line_compute_intersection_y_for_x (&t->left,
-						    traps->limits.p2.x);
-	if (ly[1] < ymin)
-	    ymin = ly[1];
-	if (ly[1] > ymax)
-	    ymax = ly[1];
-
-	ry[0] = _line_compute_intersection_y_for_x (&t->right,
-						    traps->limits.p1.x);
-	if (ry[0] < ymin)
-	    ymin = ry[0];
-	if (ry[0] > ymax)
-	    ymax = ry[0];
-
-	ry[1] = _line_compute_intersection_y_for_x (&t->right,
-						    traps->limits.p2.x);
-	if (ry[1] < ymin)
-	    ymin = ry[1];
-	if (ry[1] > ymax)
-	    ymax = ry[1];
-
-	if (ymin > top)
-	    top = ymin;
-	if (ymax < bot)
-	    bot = ymax;
-	if (top >= bot)
-	    return 0;
-
-	/* left hand side intersects */
-
-	if (x[0] <= traps->limits.p1.x && x[3] <= traps->limits.p1.x)
-	{
-	    num_events += _add_event (&limits[0], top, bot, 1,
-				      events + num_events);
-	}
-	else if (x[0] >= traps->limits.p1.x && x[3] >= traps->limits.p1.x &&
-		 x[0] <= traps->limits.p2.x && x[3] <= traps->limits.p2.x)
-	{
-	    num_events += _add_event (&t->left, top, bot, 1,
-				      events + num_events);
-	}
-	else
-	{
-	    if (ly[0] < ly[1]) {
-		if (ly[1] >= top) {
-		    if (ly[0] < top)
-			ly[0] = top;
-		    if (ly[1] > bot)
-			ly[1] = bot;
-		    num_events += _add_event (&limits[0], top, ly[0], 1,
-					    events + num_events);
-		    num_events += _add_event (&t->left, ly[0], ly[1], 1,
-					    events + num_events);
-		    num_events += _add_event (&limits[1], ly[1], bot, 1,
-					    events + num_events);
-		}
-	    } else {
-		if (ly[1] <= bot) {
-		    if (ly[1] < top)
-			ly[1] = top;
-		    if (ly[0] > bot)
-			ly[0] = bot;
-		    num_events += _add_event (&limits[1], top, ly[1], 1,
-					    events + num_events);
-		    num_events += _add_event (&t->left, ly[1], ly[0], 1,
-					    events + num_events);
-		    num_events += _add_event (&limits[0], ly[0], bot, 1,
-					    events + num_events);
-		}
-	    }
-	}
-
-	/* right hand side intersects */
-
-	if (x[1] >= traps->limits.p2.x && x[2] >= traps->limits.p2.x)
-	{
-	    num_events += _add_event (&limits[1], top, bot, -1,
-				      events + num_events);
-	}
-	else if (x[1] <= traps->limits.p2.x && x[2] <= traps->limits.p2.x &&
-		 x[1] >= traps->limits.p1.x && x[2] >= traps->limits.p1.x)
-	{
-	    num_events += _add_event (&t->right, top, bot, -1,
-				      events + num_events);
-	}
-	else
-	{
-	    if (ry[0] < ry[1]) {
-		if (ry[0] <= bot) {
-		    if (ry[0] < top)
-			ry[0] = top;
-		    if (ry[1] > bot)
-			ry[1] = bot;
-		    num_events += _add_event (&limits[0], top, ry[0], -1,
-					    events + num_events);
-		    num_events += _add_event (&t->right, ry[0], ry[1], -1,
-					    events + num_events);
-		    num_events += _add_event (&limits[1], ry[1], bot, -1,
-					    events + num_events);
-		}
-	    } else {
-		if (ry[0] >= top) {
-		    if (ry[0] > bot)
-			ry[0] = bot;
-		    if (ry[1] < top)
-			ry[1] = top;
-		    num_events += _add_event (&limits[1], top, ry[1], -1,
-					    events + num_events);
-		    num_events += _add_event (&t->right, ry[1], ry[0], -1,
-					    events + num_events);
-		    num_events += _add_event (&limits[0], ry[0], bot, -1,
-					    events + num_events);
-		}
-	    }
-	}
-    } else {
-	num_events += _add_event (&t->left, top, bot, 1, events + num_events);
-	num_events += _add_event (&t->right, top, bot, -1, events + num_events);
-    }
-
-    return num_events;
-}
-
 cairo_status_t
 _cairo_bentley_ottmann_tessellate_traps (cairo_traps_t *traps,
 					 cairo_fill_rule_t fill_rule)
 {
-    int intersections;
     cairo_status_t status;
-    cairo_bo_start_event_t stack_events[CAIRO_STACK_ARRAY_LENGTH (cairo_bo_start_event_t)];
-    cairo_bo_start_event_t *events;
-    cairo_bo_event_t *stack_event_ptrs[ARRAY_LENGTH (stack_events) + 1];
-    cairo_bo_event_t **event_ptrs;
-    int num_events;
+    cairo_polygon_t polygon;
     int i;
 
     if (unlikely (0 == traps->num_traps))
@@ -2021,50 +1794,38 @@ _cairo_bentley_ottmann_tessellate_traps (cairo_traps_t *traps,
     dump_traps (traps, "bo-traps-in.txt");
 #endif
 
-    /* we need at most 6 vertical edges to describe each clipped trapezoid */
-    i = 6 * traps->num_traps;
+    _cairo_polygon_init (&polygon);
+    _cairo_polygon_limit (&polygon, traps->limits, traps->num_limits);
 
-    events = stack_events;
-    event_ptrs = stack_event_ptrs;
-    if (i > ARRAY_LENGTH (stack_events)) {
-	events = _cairo_malloc_ab_plus_c (i,
-					  sizeof (cairo_bo_start_event_t) +
-					  sizeof (cairo_bo_event_t *),
-					  sizeof (cairo_bo_event_t *));
-	if (unlikely (events == NULL))
-	    return _cairo_error (CAIRO_STATUS_NO_MEMORY);
-
-	event_ptrs = (cairo_bo_event_t **) (events + i);
-    }
-
-    num_events = 0;
     for (i = 0; i < traps->num_traps; i++) {
-	num_events += _compute_clipped_trapezoid_edges (traps,
-							&traps->traps[i],
-							&events[num_events]);
-    }
-
-    for (i = 0; i < num_events; i++)
-	event_ptrs[i] = (cairo_bo_event_t *) &events[i];
-
+	status = _cairo_polygon_add_line (&polygon,
+					  &traps->traps[i].left,
+					  traps->traps[i].top,
+					  traps->traps[i].bottom,
+					  1);
+	if (unlikely (status))
+	    goto CLEANUP;
 
-#if DEBUG_TRAPS
-    dump_edges (events, num_events, "bo-traps-edges.txt");
-#endif
+	status = _cairo_polygon_add_line (&polygon,
+					  &traps->traps[i].right,
+					  traps->traps[i].top,
+					  traps->traps[i].bottom,
+					  -1);
+	if (unlikely (status))
+	    goto CLEANUP;
+    }
 
     _cairo_traps_clear (traps);
-    status = _cairo_bentley_ottmann_tessellate_bo_edges (event_ptrs,
-							 num_events,
-							 fill_rule,
-							 traps,
-							 &intersections);
+    status = _cairo_bentley_ottmann_tessellate_polygon (traps,
+							&polygon,
+							fill_rule);
 
 #if DEBUG_TRAPS
     dump_traps (traps, "bo-traps-out.txt");
 #endif
 
-    if (events != stack_events)
-	free (events);
+  CLEANUP:
+    _cairo_polygon_fini (&polygon);
 
     return status;
 }