[cairo-commit] 3 commits - doc/public src/cairo-path-stroke.c

Carl Worth cworth at kemper.freedesktop.org
Tue Oct 30 08:20:40 PDT 2007


 doc/public/tmpl/cairo-ps.sgml          |   53 ++++++++++++++
 doc/public/tmpl/cairo-surface.sgml     |   19 +++++
 doc/public/tmpl/cairo-win32-fonts.sgml |   10 ++
 doc/public/tmpl/cairo-win32.sgml       |    9 ++
 src/cairo-path-stroke.c                |  119 ++++++++++++++++++++++++++++++---
 5 files changed, 202 insertions(+), 8 deletions(-)

New commits:
commit 00d701ff7de68609aa8cec7871d93b27a108fd14
Author: Carl Worth <cworth at cworth.org>
Date:   Mon Oct 29 17:55:28 2007 -0700

    Limit miters for small angles
    
    This fixes the current failure get-path-extents, which is a
    demonstration of the following bug:
    
    	cairo_stroke_extents() gives wrong result for arcs in some cases
    	https://bugs.freedesktop.org/show_bug.cgi?id=7245
    
    Many thanks to Michael Urman whose review of early versions of
    this work found a fatal mistake in my algebra.

diff --git a/src/cairo-path-stroke.c b/src/cairo-path-stroke.c
index 5555a6c..fb12f15 100644
--- a/src/cairo-path-stroke.c
+++ b/src/cairo-path-stroke.c
@@ -272,6 +272,9 @@ _cairo_stroker_join (cairo_stroker_t *stroker, cairo_stroke_face_t *in, cairo_st
 	double	in_dot_out = ((-in->usr_vector.x * out->usr_vector.x)+
 			      (-in->usr_vector.y * out->usr_vector.y));
 	double	ml = stroker->style->miter_limit;
+	double tolerance_squared = stroker->tolerance * stroker->tolerance;
+	double line_width_squared = (stroker->style->line_width *
+				     stroker->style->line_width);
 
 	/* Check the miter limit -- lines meeting at an acute angle
 	 * can generate long miters, the limit converts them to bevel
@@ -329,8 +332,79 @@ _cairo_stroker_join (cairo_stroker_t *stroker, cairo_stroke_face_t *in, cairo_st
 	 *
 	 *	2 <= ml² (1 - in · out)
 	 *
+	 *
+	 * That gives us the condition to avoid generating miters that
+	 * are too large from angles that are too large. But we also
+	 * need to avoid generating miters when the angle is very small.
+	 *
+	 * The miter formed from a tiny angle is also tiny, so the
+	 * miter limit is not a concern. But with a tiny angle we will
+	 * be computing the intersection of two lines that are very
+	 * near parallel. Also, the limits of the fixed-point grid on
+	 * the input face coordinates mean that the resulting
+	 * intersection could be wildly wrong. (See the
+	 * get-path-extents test case for a call to cairo_arc that
+	 * results in two problematic faces.)
+	 *
+	 * Fortunately we can also derive an expression for when using
+	 * a bevel join instead of a miter will introduce an error no
+	 * larger than the tolerance. Consider the same join from
+	 * before but with the miter now chopped off and replaced with
+	 * a bevel join. The drawing is zoomed in a bit again, the
+	 * point marked as '*' is the center of the stroke---the point
+	 * where the two line segments of interest intersect:
+	 *
+	 *    ----- .
+	 *    ^     ..
+	 *    |     . .
+	 *    |     .  .
+	 *   1/2    .   .
+	 *  miter   .    .         |
+	 *  length  .     .        |
+	 *    |     .______.    ___v___
+	 *    |     |     . \   1/2 bevel
+	 *    v     |  .     \   width
+	 *    ----  *         \ -------
+	 *	    |          \   ^
+	 *
+	 *
+	 * The length of interest here is the vertical length of the
+	 * miter that is eliminated. It's length can be obtained by
+	 * starting with 1/2 the miter length and the subtracting off
+	 * the vertical length that is included by the bevel join,
+	 * (here termed 1/2 bevel width). To determine this new bevel
+	 * width, we have a small right triangle shown, the hypotenuse
+	 * of which has a length of 1/2 the line width, and the small
+	 * angle at the upper right of the figure is psi/2.
+	 *
+	 * So we have:
+	 *
+	 *	sin (psi/2) = (bevel_width / 2) / (line_width / 2)
+	 *
+	 * And we can determine when the miter is required by
+	 * calculating when the eliminated portion of the miter is
+	 * greater than the tolerance:
+	 *
+	 *	(miter_length / 2) - (bevel_width / 2) > tolerance
+	 *
+	 * Substituting in the above expressions for miter_length and
+	 * bevel_width:
+	 *
+	 *	(line_width/2) / sin (psi/2) - (line_width/2) * sin (psi/2) > tolerance
+	 *	1 / sin(psi/2) - sin (psi/2) > 2 * tolerance / line_width
+	 *	1 / sin²(psi/2) -2 +  sin²(psi/2) > 4 * (tolerance/line_width)²
+	 *
+	 * Use identity: sin²(psi/2) = (1-cos(psi))/2
+
+	 *	2/(1 - cos(psi)) - 2 + (1-cos(psi))/2 > 4 * (tolerance/line_width)²
+	 *	4/(1 - cos(psi)) - 4 + (1-cos(psi)) > 8 * (tolerance/line_width)²
+	 *	4/(1 - cos(psi)) + (1-cos(psi)) > 8 * ((tolerance/line_width)² + 0.5)
 	 */
-	if (2 <= ml * ml * (1 - in_dot_out)) {
+	if ((2 <= ml * ml * (1 - in_dot_out)) &&
+	    ((8 * (tolerance_squared / line_width_squared + 0.5)) <
+	     4 / (1 - in_dot_out) + (1 - in_dot_out))
+	    )
+	{
 	    double		x1, y1, x2, y2;
 	    double		mx, my;
 	    double		dx1, dx2, dy1, dy2;
commit 9bf0a640d203a880cae5c6a8bf3602344d03cb68
Author: Carl Worth <cworth at cworth.org>
Date:   Mon Oct 29 16:24:13 2007 -0700

    Add figure illustrating derivation of miter limit
    
    And use sin in the first place rather than the more awkward
    secant.

diff --git a/src/cairo-path-stroke.c b/src/cairo-path-stroke.c
index a2fed55..5555a6c 100644
--- a/src/cairo-path-stroke.c
+++ b/src/cairo-path-stroke.c
@@ -273,18 +273,47 @@ _cairo_stroker_join (cairo_stroker_t *stroker, cairo_stroke_face_t *in, cairo_st
 			      (-in->usr_vector.y * out->usr_vector.y));
 	double	ml = stroker->style->miter_limit;
 
-	/*
-	 * Check the miter limit -- lines meeting at an acute angle
+	/* Check the miter limit -- lines meeting at an acute angle
 	 * can generate long miters, the limit converts them to bevel
 	 *
-	 * We want to know when the miter is within the miter limit.
-	 * That's straightforward to specify:
+	 * Consider the miter join formed when two line segments
+	 * meet at an angle psi:
 	 *
-	 *	secant (psi / 2) <= ml
+	 *	   /.\
+	 *	  /. .\
+	 *	 /./ \.\
+	 *	/./psi\.\
 	 *
-	 * where psi is the angle between in and out
+	 * We can zoom in on the right half of that to see:
+	 *
+	 *	    |\
+	 *	    | \ psi/2
+	 *	    |  \
+	 *	    |   \
+	 *	    |    \
+	 *	    |     \
+	 * 	  miter    \
+	 *	 length     \
+	 *	    |        \
+	 *	    |        .\
+	 *	    |    .     \
+	 *	    |.   line   \
+	 *	     \    width  \
+	 *	      \           \
+	 *
+	 *
+	 * The right triangle in that figure, (the line-width side is
+	 * shown faintly with three '.' characters), gives us the
+	 * following expression relating miter length, angle and line
+	 * width:
+	 *
+	 *	1 /sin (psi/2) = miter_length / line_width
+	 *
+	 * The right-hand side of this relationship is the same ratio
+	 * in which the miter limit (ml) is expressed. We want to know
+	 * when the miter length is within the miter limit. That is
+	 * when the following condition holds:
 	 *
-	 *				secant(psi/2) = 1/sin(psi/2)
 	 *	1/sin(psi/2) <= ml
 	 *	1 <= ml sin(psi/2)
 	 *	1 <= ml² sin²(psi/2)
commit abeba1e69be3d4500107f10e50e1f0e7cae8c78f
Author: Carl Worth <cworth at cworth.org>
Date:   Mon Oct 29 16:22:15 2007 -0700

    Annoying churn of sgml templates

diff --git a/doc/public/tmpl/cairo-ps.sgml b/doc/public/tmpl/cairo-ps.sgml
index d3b36a7..3cf66be 100644
--- a/doc/public/tmpl/cairo-ps.sgml
+++ b/doc/public/tmpl/cairo-ps.sgml
@@ -40,6 +40,59 @@ Rendering PostScript documents
 @Returns: 
 
 
+<!-- ##### FUNCTION cairo_ps_surface_restrict_to_level ##### -->
+<para>
+
+</para>
+
+ at surface: 
+ at level: 
+
+
+<!-- ##### ENUM cairo_ps_level_t ##### -->
+<para>
+
+</para>
+
+ at CAIRO_PS_LEVEL_2: 
+ at CAIRO_PS_LEVEL_3: 
+
+<!-- ##### FUNCTION cairo_ps_get_levels ##### -->
+<para>
+
+</para>
+
+ at levels: 
+ at num_levels: 
+
+
+<!-- ##### FUNCTION cairo_ps_level_to_string ##### -->
+<para>
+
+</para>
+
+ at level: 
+ at Returns: 
+
+
+<!-- ##### FUNCTION cairo_ps_surface_set_eps ##### -->
+<para>
+
+</para>
+
+ at surface: 
+ at eps: 
+
+
+<!-- ##### FUNCTION cairo_ps_surface_get_eps ##### -->
+<para>
+
+</para>
+
+ at surface: 
+ at Returns: 
+
+
 <!-- ##### FUNCTION cairo_ps_surface_set_size ##### -->
 <para>
 
diff --git a/doc/public/tmpl/cairo-surface.sgml b/doc/public/tmpl/cairo-surface.sgml
index 15929f3..b230791 100644
--- a/doc/public/tmpl/cairo-surface.sgml
+++ b/doc/public/tmpl/cairo-surface.sgml
@@ -171,6 +171,7 @@ Base class for surfaces
 @CAIRO_SURFACE_TYPE_DIRECTFB: 
 @CAIRO_SURFACE_TYPE_SVG: 
 @CAIRO_SURFACE_TYPE_OS2: 
+ at CAIRO_SURFACE_TYPE_WIN32_PRINTING: 
 
 <!-- ##### FUNCTION cairo_surface_get_type ##### -->
 <para>
@@ -212,3 +213,21 @@ Base class for surfaces
 @Returns: 
 
 
+<!-- ##### FUNCTION cairo_surface_copy_page ##### -->
+<para>
+
+</para>
+
+ at surface: 
+ at Returns: 
+
+
+<!-- ##### FUNCTION cairo_surface_show_page ##### -->
+<para>
+
+</para>
+
+ at surface: 
+ at Returns: 
+
+
diff --git a/doc/public/tmpl/cairo-win32-fonts.sgml b/doc/public/tmpl/cairo-win32-fonts.sgml
index bc2aad8..5581e01 100644
--- a/doc/public/tmpl/cairo-win32-fonts.sgml
+++ b/doc/public/tmpl/cairo-win32-fonts.sgml
@@ -35,6 +35,16 @@ Font support for Microsoft Windows
 @Returns: 
 
 
+<!-- ##### FUNCTION cairo_win32_font_face_create_for_logfontw_hfont ##### -->
+<para>
+
+</para>
+
+ at logfont: 
+ at font: 
+ at Returns: 
+
+
 <!-- ##### FUNCTION cairo_win32_scaled_font_select_font ##### -->
 <para>
 
diff --git a/doc/public/tmpl/cairo-win32.sgml b/doc/public/tmpl/cairo-win32.sgml
index 4e5dd34..fb03d83 100644
--- a/doc/public/tmpl/cairo-win32.sgml
+++ b/doc/public/tmpl/cairo-win32.sgml
@@ -49,6 +49,15 @@ Microsoft Windows surface support
 @Returns: 
 
 
+<!-- ##### FUNCTION cairo_win32_printing_surface_create ##### -->
+<para>
+
+</para>
+
+ at hdc: 
+ at Returns: 
+
+
 <!-- ##### FUNCTION cairo_win32_surface_get_dc ##### -->
 <para>
 


More information about the cairo-commit mailing list