[cairo-commit] 5 commits - configure.ac src/cairo-gstate.c src/cairoint.h src/cairo-path-in-fill.c src/cairo-png.c src/Makefile.sources test/in-fill-trapezoid.c test/pdf2png.c
Chris Wilson
ickle at kemper.freedesktop.org
Wed Nov 5 16:32:56 PST 2008
configure.ac | 6 -
src/Makefile.sources | 1
src/cairo-gstate.c | 30 -----
src/cairo-path-in-fill.c | 264 +++++++++++++++++++++++++++++++++++++++++++++++
src/cairo-png.c | 14 ++
src/cairoint.h | 9 +
test/in-fill-trapezoid.c | 56 +++++++++
test/pdf2png.c | 32 +++--
8 files changed, 372 insertions(+), 40 deletions(-)
New commits:
commit f5965cb7d6559e051c2581fe446d0b9f40427eb2
Author: Chris Wilson <chris at chris-wilson.co.uk>
Date: Wed Nov 5 23:48:52 2008 +0000
[in-fill] Avoid tessellation by counting number of edge crossing to -∞
Benjamin Otte reports that in one particular benchmark cairo_in_fill() is
a hotspot in the profile. Currently we tessellate the entire path and then
search for a containing trapezoid. This is very expensive compared to the
simple method of counting the number of edge crossing between the point of
interest and x=-∞. For example, this speeds tessellate-256 up by almost 3
orders of magnitude.
diff --git a/src/Makefile.sources b/src/Makefile.sources
index 6a0e93b..0b44bbf 100644
--- a/src/Makefile.sources
+++ b/src/Makefile.sources
@@ -122,6 +122,7 @@ cairo_sources = \
cairo-path.c \
cairo-path-fill.c \
cairo-path-fixed.c \
+ cairo-path-in-fill.c \
cairo-path-stroke.c \
cairo-pattern.c \
cairo-pen.c \
diff --git a/src/cairo-gstate.c b/src/cairo-gstate.c
index 5b8c87d..1d532c7 100644
--- a/src/cairo-gstate.c
+++ b/src/cairo-gstate.c
@@ -1071,33 +1071,13 @@ _cairo_gstate_in_fill (cairo_gstate_t *gstate,
double y,
cairo_bool_t *inside_ret)
{
- cairo_status_t status;
- cairo_box_t limit;
- cairo_traps_t traps;
-
_cairo_gstate_user_to_backend (gstate, &x, &y);
- limit.p1.x = _cairo_fixed_from_double (x) - 1;
- limit.p1.y = _cairo_fixed_from_double (y) - 1;
- limit.p2.x = limit.p1.x + 2;
- limit.p2.y = limit.p1.y + 2;
-
- _cairo_traps_init (&traps);
- _cairo_traps_limit (&traps, &limit);
-
- status = _cairo_path_fixed_fill_to_traps (path,
- gstate->fill_rule,
- gstate->tolerance,
- &traps);
- if (status)
- goto BAIL;
-
- *inside_ret = _cairo_traps_contain (&traps, x, y);
-
-BAIL:
- _cairo_traps_fini (&traps);
-
- return status;
+ return _cairo_path_fixed_in_fill (path,
+ gstate->fill_rule,
+ gstate->tolerance,
+ x, y,
+ inside_ret);
}
cairo_status_t
diff --git a/src/cairo-path-in-fill.c b/src/cairo-path-in-fill.c
new file mode 100644
index 0000000..8bfc9d8
--- /dev/null
+++ b/src/cairo-path-in-fill.c
@@ -0,0 +1,264 @@
+/* cairo - a vector graphics library with display and print output
+ *
+ * Copyright © 2008 Chris Wilson
+ *
+ * This library is free software; you can redistribute it and/or
+ * modify it either under the terms of the GNU Lesser General Public
+ * License version 2.1 as published by the Free Software Foundation
+ * (the "LGPL") or, at your option, under the terms of the Mozilla
+ * Public License Version 1.1 (the "MPL"). If you do not alter this
+ * notice, a recipient may use your version of this file under either
+ * the MPL or the LGPL.
+ *
+ * You should have received a copy of the LGPL along with this library
+ * in the file COPYING-LGPL-2.1; if not, write to the Free Software
+ * Foundation, Inc., 59 Temple Place, Suite 330, Boston, MA 02111-1307 USA
+ * You should have received a copy of the MPL along with this library
+ * in the file COPYING-MPL-1.1
+ *
+ * The contents of this file are subject to the Mozilla Public License
+ * Version 1.1 (the "License"); you may not use this file except in
+ * compliance with the License. You may obtain a copy of the License at
+ * http://www.mozilla.org/MPL/
+ *
+ * This software is distributed on an "AS IS" basis, WITHOUT WARRANTY
+ * OF ANY KIND, either express or implied. See the LGPL or the MPL for
+ * the specific language governing rights and limitations.
+ *
+ * The Original Code is the cairo graphics library.
+ *
+ * The Initial Developer of the Original Code is Chris Wilson.
+ *
+ * Contributor(s):
+ * Chris Wilson <chris at chris-wilson.co.uk>
+ */
+
+#include "cairoint.h"
+#include "cairo-path-fixed-private.h"
+
+typedef struct cairo_in_fill {
+ double tolerance;
+ int winding;
+
+ cairo_fixed_t x, y;
+
+ cairo_bool_t has_current_point;
+ cairo_point_t current_point;
+ cairo_point_t first_point;
+} cairo_in_fill_t;
+
+static void
+_cairo_in_fill_init (cairo_in_fill_t *in_fill,
+ double tolerance,
+ double x,
+ double y)
+{
+ in_fill->winding = 0;
+ in_fill->tolerance = tolerance;
+
+ in_fill->x = _cairo_fixed_from_double (x);
+ in_fill->y = _cairo_fixed_from_double (y);
+
+ in_fill->has_current_point = FALSE;
+ in_fill->current_point.x = 0;
+ in_fill->current_point.y = 0;
+}
+
+static void
+_cairo_in_fill_fini (cairo_in_fill_t *in_fill)
+{
+}
+
+static int
+edge_compare_for_y_against_x (const cairo_point_t *p1,
+ const cairo_point_t *p2,
+ cairo_fixed_t y,
+ cairo_fixed_t x)
+{
+ cairo_fixed_t adx, ady;
+ cairo_fixed_t dx, dy;
+ cairo_int64_t L, R;
+
+ adx = p2->x - p1->x;
+ dx = x - p1->x;
+
+ if (adx == 0)
+ return -dx;
+ if ((adx ^ dx) < 0)
+ return adx;
+
+ dy = y - p1->y;
+ ady = p2->y - p1->y;
+
+ L = _cairo_int32x32_64_mul (dy, adx);
+ R = _cairo_int32x32_64_mul (dx, ady);
+
+ return _cairo_int64_cmp (L, R);
+}
+
+static void
+_cairo_in_fill_add_edge (cairo_in_fill_t *in_fill,
+ const cairo_point_t *p1,
+ const cairo_point_t *p2)
+{
+ int dir;
+
+ /* count the number of edge crossing to -∞ */
+
+ dir = 1;
+ if (p2->y < p1->y) {
+ const cairo_point_t *tmp;
+
+ tmp = p1;
+ p1 = p2;
+ p2 = tmp;
+
+ dir = -1;
+ }
+
+ /* edge is entirely above or below, note the shortening rule */
+ if (p2->y <= in_fill->y || p1->y > in_fill->y)
+ return;
+
+ /* edge lies wholly to the right */
+ if (p1->x > in_fill->x && p2->x > in_fill->x)
+ return;
+
+ if ((p1->x <= in_fill->x && p2->x <= in_fill->x) ||
+ edge_compare_for_y_against_x (p1, p2, in_fill->x, in_fill->y) <= 0)
+ {
+ in_fill->winding += dir;
+ }
+}
+
+static cairo_status_t
+_cairo_in_fill_move_to (void *closure, cairo_point_t *point)
+{
+ cairo_in_fill_t *in_fill = closure;
+
+ if (! in_fill->has_current_point)
+ in_fill->first_point = *point;
+
+ in_fill->current_point = *point;
+ in_fill->has_current_point = TRUE;
+
+ return CAIRO_STATUS_SUCCESS;
+}
+
+static cairo_status_t
+_cairo_in_fill_line_to (void *closure, cairo_point_t *point)
+{
+ cairo_in_fill_t *in_fill = closure;
+
+ if (in_fill->has_current_point)
+ _cairo_in_fill_add_edge (in_fill, &in_fill->current_point, point);
+
+ return _cairo_in_fill_move_to (in_fill, point);
+}
+
+static cairo_status_t
+_cairo_in_fill_curve_to (void *closure,
+ cairo_point_t *b,
+ cairo_point_t *c,
+ cairo_point_t *d)
+{
+ cairo_in_fill_t *in_fill = closure;
+ cairo_spline_t spline;
+ cairo_fixed_t top, bot, left;
+ cairo_status_t status;
+ int i;
+
+ /* first reject based on bbox */
+ bot = top = in_fill->current_point.y;
+ if (b->y < top) top = b->y;
+ if (b->y > bot) bot = b->y;
+ if (c->y < top) top = c->y;
+ if (c->y > bot) bot = c->y;
+ if (d->y < top) top = d->y;
+ if (d->y > bot) bot = d->y;
+ if (bot < in_fill->y || top > in_fill->y)
+ return CAIRO_STATUS_SUCCESS;
+
+ left = in_fill->current_point.x;
+ if (b->x < left) left = b->x;
+ if (c->x < left) left = c->x;
+ if (d->x < left) left = d->x;
+ if (left > in_fill->x)
+ return CAIRO_STATUS_SUCCESS;
+
+ /* XXX Investigate direct inspection of the inflections? */
+ status = _cairo_spline_init (&spline, &in_fill->current_point, b, c, d);
+ if (status == CAIRO_INT_STATUS_DEGENERATE)
+ return CAIRO_STATUS_SUCCESS;
+
+ status = _cairo_spline_decompose (&spline, in_fill->tolerance);
+ if (status)
+ goto CLEANUP_SPLINE;
+
+ for (i = 1; i < spline.num_points; i++)
+ _cairo_in_fill_line_to (in_fill, &spline.points[i]);
+
+ CLEANUP_SPLINE:
+ _cairo_spline_fini (&spline);
+
+ return status;
+}
+
+static cairo_status_t
+_cairo_in_fill_close_path (void *closure)
+{
+ cairo_in_fill_t *in_fill = closure;
+
+ if (in_fill->has_current_point) {
+ _cairo_in_fill_add_edge (in_fill,
+ &in_fill->current_point,
+ &in_fill->first_point);
+
+ in_fill->has_current_point = FALSE;
+ }
+
+ return CAIRO_STATUS_SUCCESS;
+}
+
+cairo_status_t
+_cairo_path_fixed_in_fill (cairo_path_fixed_t *path,
+ cairo_fill_rule_t fill_rule,
+ double tolerance,
+ double x,
+ double y,
+ cairo_bool_t *is_inside)
+{
+ cairo_in_fill_t in_fill;
+ cairo_status_t status;
+
+ _cairo_in_fill_init (&in_fill, tolerance, x, y);
+
+ status = _cairo_path_fixed_interpret (path,
+ CAIRO_DIRECTION_FORWARD,
+ _cairo_in_fill_move_to,
+ _cairo_in_fill_line_to,
+ _cairo_in_fill_curve_to,
+ _cairo_in_fill_close_path,
+ &in_fill);
+ if (status)
+ goto BAIL;
+
+ switch (fill_rule) {
+ case CAIRO_FILL_RULE_EVEN_ODD:
+ *is_inside = in_fill.winding & 1;
+ break;
+ case CAIRO_FILL_RULE_WINDING:
+ *is_inside = in_fill.winding != 0;
+ break;
+ default:
+ ASSERT_NOT_REACHED;
+ *is_inside = FALSE;
+ break;
+ }
+
+ status = CAIRO_STATUS_SUCCESS;
+
+BAIL:
+ _cairo_in_fill_fini (&in_fill);
+ return status;
+}
diff --git a/src/cairoint.h b/src/cairoint.h
index 63fefd7..fb8bf18 100644
--- a/src/cairoint.h
+++ b/src/cairoint.h
@@ -1522,6 +1522,15 @@ cairo_private cairo_bool_t
_cairo_path_fixed_is_rectangle (cairo_path_fixed_t *path,
cairo_box_t *box);
+/* cairo-path-in-fill.c */
+cairo_private cairo_status_t
+_cairo_path_fixed_in_fill (cairo_path_fixed_t *path,
+ cairo_fill_rule_t fill_rule,
+ double tolerance,
+ double x,
+ double y,
+ cairo_bool_t *is_inside);
+
/* cairo-path-fill.c */
cairo_private cairo_status_t
_cairo_path_fixed_fill_to_traps (cairo_path_fixed_t *path,
commit 0ac98461597420d3dfe52e405c6b3322d32f4854
Author: Chris Wilson <chris at chris-wilson.co.uk>
Date: Thu Nov 6 00:04:11 2008 +0000
[test] Add WINDING variants to in-fill test
Check cairo_in_fill() with some WINDING tests as well as the current
EVEN_ODD.
diff --git a/test/in-fill-trapezoid.c b/test/in-fill-trapezoid.c
index 6ff2fef..f38f97d 100644
--- a/test/in-fill-trapezoid.c
+++ b/test/in-fill-trapezoid.c
@@ -68,6 +68,62 @@ draw (cairo_t *cr, int width, int height)
ret = CAIRO_TEST_FAILURE;
}
+
+ cairo_set_fill_rule (cr, CAIRO_FILL_RULE_WINDING);
+
+ /* simple rectangle */
+ cairo_new_path (cr);
+ cairo_rectangle (cr, -10, -10, 20, 20);
+ if (! cairo_in_fill (cr, 0, 0)) {
+ cairo_test_log (ctx, "Error: Failed to find point inside rectangle\n");
+ ret = CAIRO_TEST_FAILURE;
+ }
+
+ /* simple circle */
+ cairo_new_path (cr);
+ cairo_arc (cr, 0, 0, 10, 0, 2 * M_PI);
+ if (! cairo_in_fill (cr, 0, 0)) {
+ cairo_test_log (ctx, "Error: Failed to find point inside circle\n");
+ ret = CAIRO_TEST_FAILURE;
+ }
+
+ /* overlapping circle/rectangle */
+ cairo_new_path (cr);
+ cairo_rectangle (cr, -10, -10, 20, 20);
+ cairo_new_sub_path (cr);
+ cairo_arc (cr, 0, 0, 10, 0, 2 * M_PI);
+ if (! cairo_in_fill (cr, 0, 0)) {
+ cairo_test_log (ctx, "Error: Failed to find point inside circle+rectangle\n");
+ ret = CAIRO_TEST_FAILURE;
+ }
+
+ /* holey rectangle */
+ cairo_new_path (cr);
+ cairo_rectangle (cr, -10, -10, 20, 20);
+ cairo_rectangle (cr, 5, -5, -10, 10);
+ if (cairo_in_fill (cr, 0, 0)) {
+ cairo_test_log (ctx, "Error: Found an unexpected point inside rectangular hole\n");
+ ret = CAIRO_TEST_FAILURE;
+ }
+
+ /* holey circle */
+ cairo_new_path (cr);
+ cairo_arc (cr, 0, 0, 10, 0, 2 * M_PI);
+ cairo_arc_negative (cr, 0, 0, 5, 0, -2 * M_PI);
+ if (cairo_in_fill (cr, 0, 0)) {
+ cairo_test_log (ctx, "Error: Found an unexpected point inside circular hole\n");
+ ret = CAIRO_TEST_FAILURE;
+ }
+
+ /* not a holey circle */
+ cairo_new_path (cr);
+ cairo_arc (cr, 0, 0, 10, 0, 2 * M_PI);
+ cairo_arc (cr, 0, 0, 5, 0, 2 * M_PI);
+ if (! cairo_in_fill (cr, 0, 0)) {
+ cairo_test_log (ctx, "Error: Failed to find point inside two circles\n");
+ ret = CAIRO_TEST_FAILURE;
+ }
+
return ret;
}
commit 476d5daa9bfc5e9014d1b6572853d1d78ce6a6d9
Author: Chris Wilson <chris at chris-wilson.co.uk>
Date: Wed Nov 5 19:29:04 2008 +0000
[trace] Only build if we have zlib.
Use the configure check for libz and do not attempt to build the trace
unless we have zlib.
diff --git a/configure.ac b/configure.ac
index 40fb1d3..b13f34f 100644
--- a/configure.ac
+++ b/configure.ac
@@ -493,7 +493,9 @@ case $host in
;;
esac
-AM_CONDITIONAL(BUILD_TRACE, test "x$have_ld_preload" = "xyes")
+AM_CONDITIONAL(BUILD_TRACE,
+ test "x$have_ld_preload" = "xyes" \
+ -a "x$have_libz" = "xyes")
AC_CHECK_LIB(bfd, bfd_openr,
[AC_CHECK_HEADER(bfd.h, [have_bfd=yes],
commit 34564aa84a4642dceba75efdeef438be6c6896c8
Author: Chris Wilson <chris at chris-wilson.co.uk>
Date: Wed Nov 5 19:27:49 2008 +0000
[test/pdf2png] Remove dependency on GdkPixbuf
It's appears to be dropped from the current poppler trunk, so just use our
own venerable cairo_surface_write_ton_png().
diff --git a/configure.ac b/configure.ac
index 1ed086e..40fb1d3 100644
--- a/configure.ac
+++ b/configure.ac
@@ -391,7 +391,7 @@ test_pdf=no
any2ppm_pdf=no
if test "x$use_pdf" = "xyes"; then
poppler_DEPENDENCY="poppler-glib >= $POPPLER_VERSION_REQUIRED"
- PKG_CHECK_MODULES(POPPLER, $poppler_DEPENDENCY pango gtk+-2.0,
+ PKG_CHECK_MODULES(POPPLER, $poppler_DEPENDENCY,
[CAIRO_CHECK_FUNCS_WITH_FLAGS(poppler_page_render, [$POPPLER_CFLAGS], [$POPPLER_LIBS],
[test_pdf=yes; any2ppm_pdf=yes],
[AC_MSG_RESULT(no); test_pdf="no (requires $poppler_DEPENDENCY)"])],
diff --git a/test/pdf2png.c b/test/pdf2png.c
index 543a996..8471a18 100644
--- a/test/pdf2png.c
+++ b/test/pdf2png.c
@@ -36,21 +36,21 @@ int main (int argc, char *argv[])
{
PopplerDocument *document;
PopplerPage *page;
- GdkPixbuf *pixbuf;
double width, height;
- GError *error;
const char *filename = argv[1];
const char *output_filename = argv[2];
const char *page_label = argv[3];
gchar *absolute, *uri;
+ cairo_surface_t *surface;
+ cairo_t *cr;
+ cairo_status_t status;
+ GError *error = NULL;
if (argc != 4)
FAIL ("usage: pdf2png input_file.pdf output_file.png page");
g_type_init ();
- error = NULL;
-
if (g_path_is_absolute(filename)) {
absolute = g_strdup (filename);
} else {
@@ -74,16 +74,22 @@ int main (int argc, char *argv[])
poppler_page_get_size (page, &width, &height);
- pixbuf = gdk_pixbuf_new (GDK_COLORSPACE_RGB, FALSE, 8,
- width * PIXELS_PER_POINT,
- height * PIXELS_PER_POINT);
- gdk_pixbuf_fill (pixbuf, 0xffffffff);
- poppler_page_render_to_pixbuf (page, 0, 0, width , height,
- PIXELS_PER_POINT, 0, pixbuf);
+ surface = cairo_image_surface_create (CAIRO_FORMAT_RGB24, width, height);
+ cr = cairo_create (surface);
+ cairo_surface_destroy (surface);
- gdk_pixbuf_save (pixbuf, output_filename, "png", &error, NULL);
- if (error != NULL)
- FAIL (error->message);
+ cairo_set_source_rgb (cr, 1., 1., 1.);
+ cairo_paint (cr);
+
+ poppler_page_render (page, cr);
+ g_object_unref (page);
+
+ status = cairo_surface_write_to_png (cairo_get_target (cr),
+ output_filename);
+ cairo_destroy (cr);
+
+ if (status)
+ FAIL (cairo_status_to_string (status));
return 0;
}
commit 564d64a1323c5cbcde2dd9365ac790fe8aa1c5a6
Author: Chris Wilson <chris at chris-wilson.co.uk>
Date: Wed Nov 5 18:47:34 2008 +0000
[png] Complete the idempotent read_png() -> write_png()
Write out the original PNG mime-data if attached to the surface during
cairo_surface_write_to_png(). Similar to how the compressed alternate
representations are handled by the other backends.
Note: by automatically attaching and using the mime-data in preference to
the image data, we break the read_from_png(); draw(); write_to_png()
cycle.
diff --git a/src/cairo-png.c b/src/cairo-png.c
index b4aeb08..a130ba2 100644
--- a/src/cairo-png.c
+++ b/src/cairo-png.c
@@ -148,6 +148,8 @@ write_png (cairo_surface_t *surface,
png_info *info;
png_byte **volatile rows = NULL;
png_color_16 white;
+ const unsigned char *mime_data;
+ unsigned int mime_data_length;
int png_color_type;
int depth;
@@ -196,6 +198,18 @@ write_png (cairo_surface_t *surface,
png_set_write_fn (png, closure, write_func, png_simple_output_flush_fn);
+ /* XXX This is very questionable.
+ * This breaks the read_from_png(); draw(); write_to_png(); cycle, but
+ * that is affected by mime-data in general. OTOH, by using mime-data
+ * here we are consistent with the other backends.
+ */
+ cairo_surface_get_mime_data (surface, CAIRO_MIME_TYPE_PNG,
+ &mime_data, &mime_data_length);
+ if (mime_data != NULL) {
+ write_func (png, (png_bytep) mime_data, mime_data_length);
+ goto BAIL3;
+ }
+
switch (image->format) {
case CAIRO_FORMAT_ARGB32:
depth = 8;
More information about the cairo-commit
mailing list