Bug 692805: BBox rounding issues

Currently all conversions from rect to bbox are done using a single
function, fz_round_rect. This causes problems, as sometimes we want
'round, allowing for slight calculation errors' and sometimes we
want 'round slavishly to ensure we have a bbox that covers the rect'.

We therefore split these 2 cases into 2 separate functions;
fz_round_rect is kept, meaning "round outwards allowing for slight
errors", and fz_bbox_covering_rect is added to mean "give us the
smallest bbox that is guaranteed to cover rect".

No regressions seen.

5 files changed, 48 insertions, 13 deletions

diff --git a/fitz/base_geometry.c b/fitz/base_geometry.c
index 84134179..4d83e8c2 100644
--- a/fitz/base_geometry.c
+++ b/fitz/base_geometry.c
@@ -170,15 +170,30 @@ const fz_bbox fz_infinite_bbox = { 1, 1, -1, -1 };
 const fz_bbox fz_empty_bbox = { 0, 0, 0, 0 };
 const fz_bbox fz_unit_bbox = { 0, 0, 1, 1 };
 
+#define SAFE_INT(f) ((f > INT_MAX) ? INT_MAX : ((f < INT_MIN) ? INT_MIN : (int)f))
+fz_bbox
+fz_bbox_covering_rect(fz_rect f)
+{
+	fz_bbox i;
+	f.x0 = floorf(f.x0);
+	f.y0 = floorf(f.y0);
+	f.x1 = ceilf(f.x1);
+	f.y1 = ceilf(f.y1);
+	i.x0 = SAFE_INT(f.x0);
+	i.y0 = SAFE_INT(f.y0);
+	i.x1 = SAFE_INT(f.x1);
+	i.y1 = SAFE_INT(f.y1);
+	return i;
+}
+
 fz_bbox
 fz_round_rect(fz_rect f)
 {
 	fz_bbox i;
-	f.x0 = floorf(f.x0 + FLT_EPSILON);
-	f.y0 = floorf(f.y0 + FLT_EPSILON);
-	f.x1 = ceilf(f.x1 - FLT_EPSILON);
-	f.y1 = ceilf(f.y1 - FLT_EPSILON);
-#define SAFE_INT(f) ((f > INT_MAX) ? INT_MAX : ((f < INT_MIN) ? INT_MIN : (int)f))
+	f.x0 = floorf(f.x0 + 0.001);
+	f.y0 = floorf(f.y0 + 0.001);
+	f.x1 = ceilf(f.x1 - 0.001);
+	f.y1 = ceilf(f.y1 - 0.001);
 	i.x0 = SAFE_INT(f.x0);
 	i.y0 = SAFE_INT(f.y0);
 	i.x1 = SAFE_INT(f.x1);
diff --git a/fitz/dev_bbox.c b/fitz/dev_bbox.c
index 163780d0..87cb4dca 100644
--- a/fitz/dev_bbox.c
+++ b/fitz/dev_bbox.c
@@ -7,7 +7,7 @@ fz_bbox_fill_path(fz_device *dev, fz_path *path, int even_odd, fz_matrix ctm,
 	fz_colorspace *colorspace, float *color, float alpha)
 {
 	fz_bbox *result = dev->user;
-	fz_bbox bbox = fz_round_rect(fz_bound_path(dev->ctx, path, NULL, ctm));
+	fz_bbox bbox = fz_bbox_covering_rect(fz_bound_path(dev->ctx, path, NULL, ctm));
 	*result = fz_union_bbox(*result, bbox);
 }
 
@@ -16,7 +16,7 @@ fz_bbox_stroke_path(fz_device *dev, fz_path *path, fz_stroke_state *stroke, fz_m
 	fz_colorspace *colorspace, float *color, float alpha)
 {
 	fz_bbox *result = dev->user;
-	fz_bbox bbox = fz_round_rect(fz_bound_path(dev->ctx, path, stroke, ctm));
+	fz_bbox bbox = fz_bbox_covering_rect(fz_bound_path(dev->ctx, path, stroke, ctm));
 	*result = fz_union_bbox(*result, bbox);
 }
 
@@ -25,7 +25,7 @@ fz_bbox_fill_text(fz_device *dev, fz_text *text, fz_matrix ctm,
 	fz_colorspace *colorspace, float *color, float alpha)
 {
 	fz_bbox *result = dev->user;
-	fz_bbox bbox = fz_round_rect(fz_bound_text(dev->ctx, text, ctm));
+	fz_bbox bbox = fz_bbox_covering_rect(fz_bound_text(dev->ctx, text, ctm));
 	*result = fz_union_bbox(*result, bbox);
 }
 
@@ -34,7 +34,7 @@ fz_bbox_stroke_text(fz_device *dev, fz_text *text, fz_stroke_state *stroke, fz_m
 	fz_colorspace *colorspace, float *color, float alpha)
 {
 	fz_bbox *result = dev->user;
-	fz_bbox bbox = fz_round_rect(fz_bound_text(dev->ctx, text, ctm));
+	fz_bbox bbox = fz_bbox_covering_rect(fz_bound_text(dev->ctx, text, ctm));
 	*result = fz_union_bbox(*result, bbox);
 }
 
@@ -42,7 +42,7 @@ static void
 fz_bbox_fill_shade(fz_device *dev, fz_shade *shade, fz_matrix ctm, float alpha)
 {
 	fz_bbox *result = dev->user;
-	fz_bbox bbox = fz_round_rect(fz_bound_shade(dev->ctx, shade, ctm));
+	fz_bbox bbox = fz_bbox_covering_rect(fz_bound_shade(dev->ctx, shade, ctm));
 	*result = fz_union_bbox(*result, bbox);
 }
 
@@ -50,7 +50,7 @@ static void
 fz_bbox_fill_image(fz_device *dev, fz_image *image, fz_matrix ctm, float alpha)
 {
 	fz_bbox *result = dev->user;
-	fz_bbox bbox = fz_round_rect(fz_transform_rect(ctm, fz_unit_rect));
+	fz_bbox bbox = fz_bbox_covering_rect(fz_transform_rect(ctm, fz_unit_rect));
 	*result = fz_union_bbox(*result, bbox);
 }
 
diff --git a/fitz/dev_list.c b/fitz/dev_list.c
index f0cfdeb5..1ca8bf98 100644
--- a/fitz/dev_list.c
+++ b/fitz/dev_list.c
@@ -618,7 +618,7 @@ fz_run_display_list(fz_display_list *list, fz_device *dev, fz_matrix top_ctm, fz
 		}
 		else
 		{
-			bbox = fz_round_rect(fz_transform_rect(top_ctm, node->rect));
+			bbox = fz_bbox_covering_rect(fz_transform_rect(top_ctm, node->rect));
 			bbox = fz_intersect_bbox(bbox, scissor);
 			empty = fz_is_empty_bbox(bbox);
 		}
diff --git a/fitz/fitz.h b/fitz/fitz.h
index 66993e4e..55af47a0 100644
--- a/fitz/fitz.h
+++ b/fitz/fitz.h
@@ -791,6 +791,20 @@ int fz_is_rectilinear(fz_matrix m);
 float fz_matrix_expansion(fz_matrix m); /* sumatrapdf */
 
 /*
+	fz_bbox_covering_rect: Convert a rect into the minimal bounding box
+	that covers the rectangle.
+
+	Coordinates in a bounding box are integers, so rounding of the
+	rects coordinates takes place. The top left corner is rounded
+	upwards and left while the bottom right corner is rounded
+	downwards and to the right. Overflows or underflowing
+	coordinates are clamped to INT_MIN/INT_MAX.
+
+	Does not throw exceptions.
+*/
+fz_bbox fz_bbox_covering_rect(fz_rect rect);
+
+/*
 	fz_round_rect: Convert a rect into a bounding box.
 
 	Coordinates in a bounding box are integers, so rounding of the
@@ -799,6 +813,12 @@ float fz_matrix_expansion(fz_matrix m); /* sumatrapdf */
 	downwards and to the right. Overflows or underflowing
 	coordinates are clamped to INT_MIN/INT_MAX.
 
+	This differs from fz_bbox_covering_rect, in that fz_bbox_covering_rect
+	slavishly follows the numbers (i.e any slight over/under calculations
+	can cause whole extra pixels to be added). fz_round_rect
+	allows for a small amount of rounding error when calculating
+	the bbox.
+
 	Does not throw exceptions.
 */
 fz_bbox fz_round_rect(fz_rect rect);
diff --git a/fitz/res_font.c b/fitz/res_font.c
index 6e1b63be..ca76fcfe 100644
--- a/fitz/res_font.c
+++ b/fitz/res_font.c
@@ -751,7 +751,7 @@ fz_render_t3_glyph(fz_context *ctx, fz_font *font, int gid, fz_matrix trm, fz_co
 		model = NULL; /* Treat as masked */
 	}
 
-	bbox = fz_round_rect(fz_bound_glyph(ctx, font, gid, trm));
+	bbox = fz_bbox_covering_rect(fz_bound_glyph(ctx, font, gid, trm));
 	bbox.x0--;
 	bbox.y0--;
 	bbox.x1++;