Clip area optimisations for displaylist case:

First, we add clipping rects to clipping functions. Various functions
(the ones that handle clipping) are now additionally passed a rectangle
that represents an additional bound for this clip in device space
(i.e. it has already been mapped through the current ctm).

Next, when constructing the displaylist, keep track of the bounding box
for the contents of each clip.

While writing the list, on every node we add, we add the bbox for that
node to the enclosing clips content bbox (if there is an enclosing clip).
When we pop a clip, write back to the corresponding push to update
the bbox.

This means if we get large clip regions, with only small areas used within
them, we will only do the slow blending for those small areas.

Finally, we fix a calculation in fz_bound_path which was incorrectly
accounting for mitrelimits. This was showing up in testing on page 630
of the PDF reference v1.7.

6 files changed, 128 insertions, 23 deletions

diff --git a/fitz/base_geometry.c b/fitz/base_geometry.c
index 302ef966..00a85c9b 100644
--- a/fitz/base_geometry.c
+++ b/fitz/base_geometry.c
@@ -160,6 +160,36 @@ fz_round_rect(fz_rect f)
 	return i;
 }
 
+fz_rect
+fz_intersect_rect(fz_rect a, fz_rect b)
+{
+	fz_rect r;
+	if (fz_is_infinite_rect(a)) return b;
+	if (fz_is_infinite_rect(b)) return a;
+	if (fz_is_empty_rect(a)) return fz_empty_rect;
+	if (fz_is_empty_rect(b)) return fz_empty_rect;
+	r.x0 = MAX(a.x0, b.x0);
+	r.y0 = MAX(a.y0, b.y0);
+	r.x1 = MIN(a.x1, b.x1);
+	r.y1 = MIN(a.y1, b.y1);
+	return (r.x1 < r.x0 || r.y1 < r.y0) ? fz_empty_rect : r;
+}
+
+fz_rect
+fz_union_rect(fz_rect a, fz_rect b)
+{
+	fz_rect r;
+	if (fz_is_infinite_rect(a)) return a;
+	if (fz_is_infinite_rect(b)) return b;
+	if (fz_is_empty_rect(a)) return b;
+	if (fz_is_empty_rect(b)) return a;
+	r.x0 = MIN(a.x0, b.x0);
+	r.y0 = MIN(a.y0, b.y0);
+	r.x1 = MAX(a.x1, b.x1);
+	r.y1 = MAX(a.y1, b.y1);
+	return r;
+}
+
 fz_bbox
 fz_intersect_bbox(fz_bbox a, fz_bbox b)
 {
diff --git a/fitz/dev_list.c b/fitz/dev_list.c
index eeb4e485..44528d8b 100644
--- a/fitz/dev_list.c
+++ b/fitz/dev_list.c
@@ -2,6 +2,8 @@
 
 typedef struct fz_display_node_s fz_display_node;
 
+#define STACK_SIZE 96
+
 typedef enum fz_display_command_e
 {
 	FZ_CMD_FILL_PATH,
@@ -50,6 +52,13 @@ struct fz_display_list_s
 {
 	fz_display_node *first;
 	fz_display_node *last;
+
+	int top;
+	struct {
+		fz_rect *update;
+		fz_rect rect;
+	} stack[STACK_SIZE];
+	int tiled;
 };
 
 enum { ISOLATED = 1, KNOCKOUT = 2 };
@@ -98,6 +107,54 @@ fz_clone_stroke_state(fz_stroke_state *stroke)
 static void
 fz_append_display_node(fz_display_list *list, fz_display_node *node)
 {
+	switch (node->cmd) {
+	case FZ_CMD_CLIP_PATH:
+	case FZ_CMD_CLIP_STROKE_PATH:
+	case FZ_CMD_CLIP_IMAGE_MASK:
+		list->stack[list->top].update = &node->rect;
+		list->stack[list->top].rect = fz_empty_rect;
+		list->top++;
+		break;
+	case FZ_CMD_CLIP_TEXT:
+	case FZ_CMD_CLIP_STROKE_TEXT:
+		list->stack[list->top].update = NULL;
+		list->stack[list->top].rect = fz_empty_rect;
+		list->top++;
+		break;
+	case FZ_CMD_BEGIN_TILE:
+		list->tiled++;
+		if (list->top > 0) {
+			list->stack[list->top-1].rect = fz_infinite_rect;
+		}
+		break;
+	case FZ_CMD_END_TILE:
+		list->tiled--;
+		break;
+	case FZ_CMD_END_GROUP:
+		break;
+	case FZ_CMD_POP_CLIP:
+		if (list->top > 0) {
+			fz_rect *update;
+			list->top--;
+			update = list->stack[list->top].update;
+			if (list->tiled == 0) {
+				if (update != NULL) {
+					*update = fz_intersect_rect(*update, list->stack[list->top].rect);
+					node->rect = *update;
+				} else {
+					node->rect = list->stack[list->top].rect;
+				}
+			} else {
+				node->rect = fz_infinite_rect;
+			}
+		}
+		/*@fallthrough@*/
+	default:
+		if ((list->top > 0) && (list->tiled == 0)) {
+			list->stack[list->top-1].rect = fz_union_rect(list->stack[list->top-1].rect, node->rect);
+		}
+		break;
+	}
 	if (!list->first)
 	{
 		list->first = node;
@@ -177,22 +234,26 @@ fz_list_stroke_path(void *user, fz_path *path, fz_stroke_state *stroke, fz_matri
 }
 
 static void
-fz_list_clip_path(void *user, fz_path *path, int even_odd, fz_matrix ctm)
+fz_list_clip_path(void *user, fz_path *path, fz_rect *rect, int even_odd, fz_matrix ctm)
 {
 	fz_display_node *node;
 	node = fz_new_display_node(FZ_CMD_CLIP_PATH, ctm, NULL, NULL, 0);
 	node->rect = fz_bound_path(path, NULL, ctm);
+	if (rect != NULL)
+		node->rect = fz_intersect_rect(node->rect, *rect);
 	node->item.path = fz_clone_path(path);
 	node->flag = even_odd;
 	fz_append_display_node(user, node);
 }
 
 static void
-fz_list_clip_stroke_path(void *user, fz_path *path, fz_stroke_state *stroke, fz_matrix ctm)
+fz_list_clip_stroke_path(void *user, fz_path *path, fz_rect *rect, fz_stroke_state *stroke, fz_matrix ctm)
 {
 	fz_display_node *node;
 	node = fz_new_display_node(FZ_CMD_CLIP_STROKE_PATH, ctm, NULL, NULL, 0);
 	node->rect = fz_bound_path(path, stroke, ctm);
+	if (rect != NULL)
+		node->rect = fz_intersect_rect(node->rect, *rect);
 	node->item.path = fz_clone_path(path);
 	node->stroke = fz_clone_stroke_state(stroke);
 	fz_append_display_node(user, node);
@@ -261,7 +322,6 @@ fz_list_pop_clip(void *user)
 {
 	fz_display_node *node;
 	node = fz_new_display_node(FZ_CMD_POP_CLIP, fz_identity, NULL, NULL, 0);
-	/* TODO: scan back for matching pushclip and calculate bbox of contents */
 	fz_append_display_node(user, node);
 }
 
@@ -297,11 +357,13 @@ fz_list_fill_image_mask(void *user, fz_pixmap *image, fz_matrix ctm,
 }
 
 static void
-fz_list_clip_image_mask(void *user, fz_pixmap *image, fz_matrix ctm)
+fz_list_clip_image_mask(void *user, fz_pixmap *image, fz_rect *rect, fz_matrix ctm)
 {
 	fz_display_node *node;
 	node = fz_new_display_node(FZ_CMD_CLIP_IMAGE_MASK, ctm, NULL, NULL, 0);
 	node->rect = fz_transform_rect(ctm, fz_unit_rect);
+	if (rect != NULL)
+		node->rect = fz_intersect_rect(node->rect, *rect);
 	node->item.image = fz_keep_pixmap(image);
 	fz_append_display_node(user, node);
 }
@@ -407,6 +469,8 @@ fz_new_display_list(void)
 	fz_display_list *list = fz_malloc(sizeof(fz_display_list));
 	list->first = NULL;
 	list->last = NULL;
+	list->top = 0;
+	list->tiled = 0;
 	return list;
 }
 
@@ -499,11 +563,17 @@ visible:
 				node->colorspace, node->color, node->alpha);
 			break;
 		case FZ_CMD_CLIP_PATH:
-			fz_clip_path(dev, node->item.path, node->flag, ctm);
+		{
+			fz_rect trect = fz_transform_rect(top_ctm, node->rect);
+			fz_clip_path(dev, node->item.path, &trect, node->flag, ctm);
 			break;
+		}
 		case FZ_CMD_CLIP_STROKE_PATH:
-			fz_clip_stroke_path(dev, node->item.path, node->stroke, ctm);
+		{
+			fz_rect trect = fz_transform_rect(top_ctm, node->rect);
+			fz_clip_stroke_path(dev, node->item.path, &trect, node->stroke, ctm);
 			break;
+		}
 		case FZ_CMD_FILL_TEXT:
 			fz_fill_text(dev, node->item.text, ctm,
 				node->colorspace, node->color, node->alpha);
@@ -532,8 +602,11 @@ visible:
 				node->colorspace, node->color, node->alpha);
 			break;
 		case FZ_CMD_CLIP_IMAGE_MASK:
-			fz_clip_image_mask(dev, node->item.image, ctm);
+		{
+			fz_rect trect = fz_transform_rect(top_ctm, node->rect);
+			fz_clip_image_mask(dev, node->item.image, &trect, ctm);
 			break;
+		}
 		case FZ_CMD_POP_CLIP:
 			fz_pop_clip(dev);
 			break;
diff --git a/fitz/dev_null.c b/fitz/dev_null.c
index f81b330c..4d40ef73 100644
--- a/fitz/dev_null.c
+++ b/fitz/dev_null.c
@@ -35,17 +35,17 @@ fz_stroke_path(fz_device *dev, fz_path *path, fz_stroke_state *stroke, fz_matrix
 }
 
 void
-fz_clip_path(fz_device *dev, fz_path *path, int even_odd, fz_matrix ctm)
+fz_clip_path(fz_device *dev, fz_path *path, fz_rect *rect, int even_odd, fz_matrix ctm)
 {
 	if (dev->clip_path)
-		dev->clip_path(dev->user, path, even_odd, ctm);
+		dev->clip_path(dev->user, path, rect, even_odd, ctm);
 }
 
 void
-fz_clip_stroke_path(fz_device *dev, fz_path *path, fz_stroke_state *stroke, fz_matrix ctm)
+fz_clip_stroke_path(fz_device *dev, fz_path *path, fz_rect *rect, fz_stroke_state *stroke, fz_matrix ctm)
 {
 	if (dev->clip_stroke_path)
-		dev->clip_stroke_path(dev->user, path, stroke, ctm);
+		dev->clip_stroke_path(dev->user, path, rect, stroke, ctm);
 }
 
 void
@@ -115,10 +115,10 @@ fz_fill_image_mask(fz_device *dev, fz_pixmap *image, fz_matrix ctm,
 }
 
 void
-fz_clip_image_mask(fz_device *dev, fz_pixmap *image, fz_matrix ctm)
+fz_clip_image_mask(fz_device *dev, fz_pixmap *image, fz_rect *rect, fz_matrix ctm)
 {
 	if (dev->clip_image_mask)
-		dev->clip_image_mask(dev->user, image, ctm);
+		dev->clip_image_mask(dev->user, image, rect, ctm);
 }
 
 void
diff --git a/fitz/dev_trace.c b/fitz/dev_trace.c
index 9e6853b8..06f749f9 100644
--- a/fitz/dev_trace.c
+++ b/fitz/dev_trace.c
@@ -105,7 +105,7 @@ fz_trace_stroke_path(void *user, fz_path *path, fz_stroke_state *stroke, fz_matr
 }
 
 static void
-fz_trace_clip_path(void *user, fz_path *path, int even_odd, fz_matrix ctm)
+fz_trace_clip_path(void *user, fz_path *path, fz_rect *rect, int even_odd, fz_matrix ctm)
 {
 	printf("<clip_path ");
 	if (even_odd)
@@ -119,7 +119,7 @@ fz_trace_clip_path(void *user, fz_path *path, int even_odd, fz_matrix ctm)
 }
 
 static void
-fz_trace_clip_stroke_path(void *user, fz_path *path, fz_stroke_state *stroke, fz_matrix ctm)
+fz_trace_clip_stroke_path(void *user, fz_path *path, fz_rect *rect, fz_stroke_state *stroke, fz_matrix ctm)
 {
 	printf("<clip_stroke_path ");
 	fz_trace_matrix(ctm);
@@ -210,7 +210,7 @@ fz_colorspace *colorspace, float *color, float alpha)
 }
 
 static void
-fz_trace_clip_image_mask(void *user, fz_pixmap *image, fz_matrix ctm)
+fz_trace_clip_image_mask(void *user, fz_pixmap *image, fz_rect *rect, fz_matrix ctm)
 {
 	printf("<clip_image_mask ");
 	fz_trace_matrix(ctm);
diff --git a/fitz/fitz.h b/fitz/fitz.h
index 381ae919..5bc22f4e 100644
--- a/fitz/fitz.h
+++ b/fitz/fitz.h
@@ -264,7 +264,9 @@ float fz_matrix_expansion(fz_matrix m);
 
 fz_bbox fz_round_rect(fz_rect r);
 fz_bbox fz_intersect_bbox(fz_bbox a, fz_bbox b);
+fz_rect fz_intersect_rect(fz_rect a, fz_rect b);
 fz_bbox fz_union_bbox(fz_bbox a, fz_bbox b);
+fz_rect fz_union_rect(fz_rect a, fz_rect b);
 
 fz_point fz_transform_point(fz_matrix m, fz_point p);
 fz_point fz_transform_vector(fz_matrix m, fz_point p);
@@ -954,8 +956,8 @@ struct fz_device_s
 
 	void (*fill_path)(void *, fz_path *, int even_odd, fz_matrix, fz_colorspace *, float *color, float alpha);
 	void (*stroke_path)(void *, fz_path *, fz_stroke_state *, fz_matrix, fz_colorspace *, float *color, float alpha);
-	void (*clip_path)(void *, fz_path *, int even_odd, fz_matrix);
-	void (*clip_stroke_path)(void *, fz_path *, fz_stroke_state *, fz_matrix);
+	void (*clip_path)(void *, fz_path *, fz_rect *rect, int even_odd, fz_matrix);
+	void (*clip_stroke_path)(void *, fz_path *, fz_rect *rect, fz_stroke_state *, fz_matrix);
 
 	void (*fill_text)(void *, fz_text *, fz_matrix, fz_colorspace *, float *color, float alpha);
 	void (*stroke_text)(void *, fz_text *, fz_stroke_state *, fz_matrix, fz_colorspace *, float *color, float alpha);
@@ -966,7 +968,7 @@ struct fz_device_s
 	void (*fill_shade)(void *, fz_shade *shd, fz_matrix ctm, float alpha);
 	void (*fill_image)(void *, fz_pixmap *img, fz_matrix ctm, float alpha);
 	void (*fill_image_mask)(void *, fz_pixmap *img, fz_matrix ctm, fz_colorspace *, float *color, float alpha);
-	void (*clip_image_mask)(void *, fz_pixmap *img, fz_matrix ctm);
+	void (*clip_image_mask)(void *, fz_pixmap *img, fz_rect *rect, fz_matrix ctm);
 
 	void (*pop_clip)(void *);
 
@@ -981,8 +983,8 @@ struct fz_device_s
 
 void fz_fill_path(fz_device *dev, fz_path *path, int even_odd, fz_matrix ctm, fz_colorspace *colorspace, float *color, float alpha);
 void fz_stroke_path(fz_device *dev, fz_path *path, fz_stroke_state *stroke, fz_matrix ctm, fz_colorspace *colorspace, float *color, float alpha);
-void fz_clip_path(fz_device *dev, fz_path *path, int even_odd, fz_matrix ctm);
-void fz_clip_stroke_path(fz_device *dev, fz_path *path, fz_stroke_state *stroke, fz_matrix ctm);
+void fz_clip_path(fz_device *dev, fz_path *path, fz_rect *rect, int even_odd, fz_matrix ctm);
+void fz_clip_stroke_path(fz_device *dev, fz_path *path, fz_rect *rect, fz_stroke_state *stroke, fz_matrix ctm);
 void fz_fill_text(fz_device *dev, fz_text *text, fz_matrix ctm, fz_colorspace *colorspace, float *color, float alpha);
 void fz_stroke_text(fz_device *dev, fz_text *text, fz_stroke_state *stroke, fz_matrix ctm, fz_colorspace *colorspace, float *color, float alpha);
 void fz_clip_text(fz_device *dev, fz_text *text, fz_matrix ctm, int accumulate);
@@ -992,7 +994,7 @@ void fz_pop_clip(fz_device *dev);
 void fz_fill_shade(fz_device *dev, fz_shade *shade, fz_matrix ctm, float alpha);
 void fz_fill_image(fz_device *dev, fz_pixmap *image, fz_matrix ctm, float alpha);
 void fz_fill_image_mask(fz_device *dev, fz_pixmap *image, fz_matrix ctm, fz_colorspace *colorspace, float *color, float alpha);
-void fz_clip_image_mask(fz_device *dev, fz_pixmap *image, fz_matrix ctm);
+void fz_clip_image_mask(fz_device *dev, fz_pixmap *image, fz_rect *rect, fz_matrix ctm);
 void fz_begin_mask(fz_device *dev, fz_rect area, int luminosity, fz_colorspace *colorspace, float *bc);
 void fz_end_mask(fz_device *dev);
 void fz_begin_group(fz_device *dev, fz_rect area, int isolated, int knockout, int blendmode, float alpha);
diff --git a/fitz/res_path.c b/fitz/res_path.c
index 4959754b..b9eb1ee3 100644
--- a/fitz/res_path.c
+++ b/fitz/res_path.c
@@ -158,7 +158,7 @@ fz_bound_path(fz_path *path, fz_stroke_state *stroke, fz_matrix ctm)
 
 	if (stroke)
 	{
-		float miterlength = sinf(stroke->miterlimit * 0.5f);
+		float miterlength = stroke->miterlimit;
 		float linewidth = stroke->linewidth;
 		float expand = MAX(miterlength, linewidth) * 0.5f;
 		r.x0 -= expand;