Back to index

lightning-sunbird  0.9+nobinonly
cairo-pen.c
Go to the documentation of this file.
00001 /* cairo - a vector graphics library with display and print output
00002  *
00003  * Copyright © 2002 University of Southern California
00004  *
00005  * This library is free software; you can redistribute it and/or
00006  * modify it either under the terms of the GNU Lesser General Public
00007  * License version 2.1 as published by the Free Software Foundation
00008  * (the "LGPL") or, at your option, under the terms of the Mozilla
00009  * Public License Version 1.1 (the "MPL"). If you do not alter this
00010  * notice, a recipient may use your version of this file under either
00011  * the MPL or the LGPL.
00012  *
00013  * You should have received a copy of the LGPL along with this library
00014  * in the file COPYING-LGPL-2.1; if not, write to the Free Software
00015  * Foundation, Inc., 59 Temple Place, Suite 330, Boston, MA 02111-1307 USA
00016  * You should have received a copy of the MPL along with this library
00017  * in the file COPYING-MPL-1.1
00018  *
00019  * The contents of this file are subject to the Mozilla Public License
00020  * Version 1.1 (the "License"); you may not use this file except in
00021  * compliance with the License. You may obtain a copy of the License at
00022  * http://www.mozilla.org/MPL/
00023  *
00024  * This software is distributed on an "AS IS" basis, WITHOUT WARRANTY
00025  * OF ANY KIND, either express or implied. See the LGPL or the MPL for
00026  * the specific language governing rights and limitations.
00027  *
00028  * The Original Code is the cairo graphics library.
00029  *
00030  * The Initial Developer of the Original Code is University of Southern
00031  * California.
00032  *
00033  * Contributor(s):
00034  *     Carl D. Worth <cworth@cworth.org>
00035  */
00036 
00037 #include "cairoint.h"
00038 
00039 #include "cairo-gstate-private.h"
00040 
00041 #define PEN_MAX_VERTICES 0xffff
00042 
00043 static int
00044 _cairo_pen_vertices_needed (double tolerance, double radius, cairo_matrix_t *matrix);
00045 
00046 static void
00047 _cairo_pen_compute_slopes (cairo_pen_t *pen);
00048 
00049 static cairo_status_t
00050 _cairo_pen_stroke_spline_half (cairo_pen_t *pen, cairo_spline_t *spline, cairo_direction_t dir, cairo_polygon_t *polygon);
00051 
00052 cairo_status_t
00053 _cairo_pen_init_empty (cairo_pen_t *pen)
00054 {
00055     pen->radius = 0;
00056     pen->tolerance = 0;
00057     pen->vertices = NULL;
00058     pen->num_vertices = 0;
00059 
00060     return CAIRO_STATUS_SUCCESS;
00061 }
00062 
00063 cairo_status_t
00064 _cairo_pen_init (cairo_pen_t *pen, double radius, cairo_gstate_t *gstate)
00065 {
00066     int i;
00067     int reflect;
00068     double  det;
00069 
00070     if (pen->num_vertices) {
00071        /* XXX: It would be nice to notice that the pen is already properly constructed.
00072           However, this test would also have to account for possible changes in the transformation
00073           matrix.
00074           if (pen->radius == radius && pen->tolerance == tolerance)
00075           return CAIRO_STATUS_SUCCESS;
00076        */
00077        _cairo_pen_fini (pen);
00078     }
00079 
00080     pen->radius = radius;
00081     pen->tolerance = gstate->tolerance;
00082 
00083     _cairo_matrix_compute_determinant (&gstate->ctm, &det);
00084     if (det >= 0) {
00085        reflect = 0;
00086     } else {
00087        reflect = 1;
00088     }
00089 
00090     pen->num_vertices = _cairo_pen_vertices_needed (gstate->tolerance,
00091                                               radius,
00092                                               &gstate->ctm);
00093 
00094     if ((pen->num_vertices <= 0) || (pen->num_vertices > PEN_MAX_VERTICES)) {
00095        pen->num_vertices = 0;
00096        return CAIRO_STATUS_NO_MEMORY;
00097     }
00098 
00099     pen->vertices = malloc (pen->num_vertices * sizeof (cairo_pen_vertex_t));
00100     if (pen->vertices == NULL) {
00101        pen->num_vertices = 0;
00102        return CAIRO_STATUS_NO_MEMORY;
00103     }
00104 
00105     /*
00106      * Compute pen coordinates.  To generate the right ellipse, compute points around
00107      * a circle in user space and transform them to device space.  To get a consistent
00108      * orientation in device space, flip the pen if the transformation matrix
00109      * is reflecting
00110      */
00111     for (i=0; i < pen->num_vertices; i++) {
00112        double theta = 2 * M_PI * i / (double) pen->num_vertices;
00113        double dx = radius * cos (reflect ? -theta : theta);
00114        double dy = radius * sin (reflect ? -theta : theta);
00115        cairo_pen_vertex_t *v = &pen->vertices[i];
00116        cairo_matrix_transform_distance (&gstate->ctm, &dx, &dy);
00117        v->point.x = _cairo_fixed_from_double (dx);
00118        v->point.y = _cairo_fixed_from_double (dy);
00119     }
00120 
00121     _cairo_pen_compute_slopes (pen);
00122 
00123     return CAIRO_STATUS_SUCCESS;
00124 }
00125 
00126 void
00127 _cairo_pen_fini (cairo_pen_t *pen)
00128 {
00129     free (pen->vertices);
00130     pen->vertices = NULL;
00131 
00132     _cairo_pen_init_empty (pen);
00133 }
00134 
00135 cairo_status_t
00136 _cairo_pen_init_copy (cairo_pen_t *pen, cairo_pen_t *other)
00137 {
00138     *pen = *other;
00139 
00140     if (pen->num_vertices) {
00141        pen->vertices = malloc (pen->num_vertices * sizeof (cairo_pen_vertex_t));
00142        if (pen->vertices == NULL) {
00143            pen->num_vertices = 0;
00144            return CAIRO_STATUS_NO_MEMORY;
00145        }
00146        memcpy (pen->vertices, other->vertices, pen->num_vertices * sizeof (cairo_pen_vertex_t));
00147     }
00148 
00149     return CAIRO_STATUS_SUCCESS;
00150 }
00151 
00152 cairo_status_t
00153 _cairo_pen_add_points (cairo_pen_t *pen, cairo_point_t *point, int num_points)
00154 {
00155     cairo_pen_vertex_t *vertices;
00156     int num_vertices;
00157     int i;
00158 
00159     if (num_points <= 0 || num_points > PEN_MAX_VERTICES)
00160        return CAIRO_STATUS_NO_MEMORY;
00161 
00162     if (pen->num_vertices < 0 || pen->num_vertices > PEN_MAX_VERTICES)
00163        return CAIRO_STATUS_NO_MEMORY;
00164 
00165     num_vertices = pen->num_vertices + num_points;
00166 
00167     if (num_vertices > PEN_MAX_VERTICES)
00168        return CAIRO_STATUS_NO_MEMORY;
00169 
00170     vertices = realloc (pen->vertices, num_vertices * sizeof (cairo_pen_vertex_t));
00171     if (vertices == NULL)
00172        return CAIRO_STATUS_NO_MEMORY;
00173 
00174     pen->vertices = vertices;
00175     pen->num_vertices = num_vertices;
00176 
00177     /* initialize new vertices */
00178     for (i=0; i < num_points; i++)
00179        pen->vertices[pen->num_vertices-num_points+i].point = point[i];
00180 
00181     _cairo_hull_compute (pen->vertices, &pen->num_vertices);
00182 
00183     _cairo_pen_compute_slopes (pen);
00184 
00185     return CAIRO_STATUS_SUCCESS;
00186 }
00187 
00188 /*
00189 The circular pen in user space is transformed into an ellipse in
00190 device space.
00191 
00192 We construct the pen by computing points along the circumference
00193 using equally spaced angles.
00194 
00195 We show that this approximation to the ellipse has maximum error at the
00196 major axis of the ellipse.  
00197 
00198 Set
00199 
00200            M = major axis length
00201            m = minor axis length
00202 
00203 Align 'M' along the X axis and 'm' along the Y axis and draw
00204 an ellipse parameterized by angle 't':
00205 
00206            x = M cos t                    y = m sin t
00207 
00208 Perturb t by ± d and compute two new points (x+,y+), (x-,y-).
00209 The distance from the average of these two points to (x,y) represents
00210 the maximum error in approximating the ellipse with a polygon formed
00211 from vertices 2∆ radians apart.
00212 
00213            x+ = M cos (t+∆)             y+ = m sin (t+∆)
00214            x- = M cos (t-∆)             y- = m sin (t-∆)
00215 
00216 Now compute the approximation error, E:
00217 
00218        Ex = (x - (x+ + x-) / 2)
00219        Ex = (M cos(t) - (Mcos(t+∆) + Mcos(t-∆))/2)
00220           = M (cos(t) - (cos(t)cos(∆) + sin(t)sin(∆) +
00221                        cos(t)cos(∆) - sin(t)sin(∆))/2)
00222           = M(cos(t) - cos(t)cos(∆))
00223           = M cos(t) (1 - cos(∆))
00224 
00225        Ey = y - (y+ - y-) / 2
00226           = m sin (t) - (m sin(t+∆) + m sin(t-∆)) / 2
00227           = m (sin(t) - (sin(t)cos(∆) + cos(t)sin(∆) +
00228                        sin(t)cos(∆) - cos(t)sin(∆))/2)
00229           = m (sin(t) - sin(t)cos(∆))
00230           = m sin(t) (1 - cos(∆))
00231 
00232        E² = Ex² + Ey²
00233           = (M cos(t) (1 - cos (∆)))² + (m sin(t) (1-cos(∆)))²
00234           = (1 - cos(∆))² (M² cos²(t) + m² sin²(t))
00235           = (1 - cos(∆))² ((m² + M² - m²) cos² (t) + m² sin²(t))
00236           = (1 - cos(∆))² (M² - m²) cos² (t) + (1 - cos(∆))² m²
00237 
00238 Find the extremum by differentiation wrt t and setting that to zero
00239 
00240 ∂(E²)/∂(t) = (1-cos(∆))² (M² - m²) (-2 cos(t) sin(t))
00241 
00242          0 = 2 cos (t) sin (t)
00243         0 = sin (2t)
00244         t = nπ
00245 
00246 Which is to say that the maximum and minimum errors occur on the
00247 axes of the ellipse at 0 and π radians:
00248 
00249        E²(0) = (1-cos(∆))² (M² - m²) + (1-cos(∆))² m²
00250              = (1-cos(∆))² M²
00251        E²(π) = (1-cos(∆))² m²
00252 
00253 maximum error = M (1-cos(∆))
00254 minimum error = m (1-cos(∆))
00255 
00256 We must make maximum error ≤ tolerance, so compute the ∆ needed:
00257 
00258            tolerance = M (1-cos(∆))
00259        tolerance / M = 1 - cos (∆)
00260               cos(∆) = 1 - tolerance/M
00261                     ∆ = acos (1 - tolerance / M);
00262 
00263 Remembering that ∆ is half of our angle between vertices,
00264 the number of vertices is then
00265 
00266              vertices = ceil(2π/2∆).
00267                       = ceil(π/∆).
00268 
00269 Note that this also equation works for M == m (a circle) as it
00270 doesn't matter where on the circle the error is computed.
00271 */
00272 
00273 static int
00274 _cairo_pen_vertices_needed (double     tolerance,
00275                          double        radius,
00276                          cairo_matrix_t  *matrix)
00277 {
00278     /* 
00279      * the pen is a circle that gets transformed to an ellipse by matrix.
00280      * compute major axis length for a pen with the specified radius.
00281      * we don't need the minor axis length.
00282      */
00283     
00284     double  major_axis = _cairo_matrix_transformed_circle_major_axis(matrix, radius);
00285 
00286     /*
00287      * compute number of vertices needed
00288      */
00289     int           num_vertices;
00290     
00291     /* Where tolerance / M is > 1, we use 4 points */
00292     if (tolerance >= major_axis) {
00293        num_vertices = 4;
00294     } else {
00295        double delta = acos (1 - tolerance / major_axis);
00296        num_vertices = ceil (M_PI / delta);
00297        
00298        /* number of vertices must be even */
00299        if (num_vertices % 2)
00300            num_vertices++;
00301     }
00302     return num_vertices;
00303 }
00304 
00305 static void
00306 _cairo_pen_compute_slopes (cairo_pen_t *pen)
00307 {
00308     int i, i_prev;
00309     cairo_pen_vertex_t *prev, *v, *next;
00310 
00311     for (i=0, i_prev = pen->num_vertices - 1;
00312         i < pen->num_vertices;
00313         i_prev = i++) {
00314        prev = &pen->vertices[i_prev];
00315        v = &pen->vertices[i];
00316        next = &pen->vertices[(i + 1) % pen->num_vertices];
00317 
00318        _cairo_slope_init (&v->slope_cw, &prev->point, &v->point);
00319        _cairo_slope_init (&v->slope_ccw, &v->point, &next->point);
00320     }
00321 }
00322 /*
00323  * Find active pen vertex for clockwise edge of stroke at the given slope.
00324  *
00325  * NOTE: The behavior of this function is sensitive to the sense of
00326  * the inequality within _cairo_slope_clockwise/_cairo_slope_counter_clockwise.
00327  *
00328  * The issue is that the slope_ccw member of one pen vertex will be
00329  * equivalent to the slope_cw member of the next pen vertex in a
00330  * counterclockwise order. However, for this function, we care
00331  * strongly about which vertex is returned.
00332  */
00333 cairo_status_t
00334 _cairo_pen_find_active_cw_vertex_index (cairo_pen_t *pen,
00335                                    cairo_slope_t *slope,
00336                                    int *active)
00337 {
00338     int i;
00339 
00340     for (i=0; i < pen->num_vertices; i++) {
00341        if (_cairo_slope_clockwise (slope, &pen->vertices[i].slope_ccw)
00342            && _cairo_slope_counter_clockwise (slope, &pen->vertices[i].slope_cw))
00343            break;
00344     }
00345 
00346     *active = i;
00347 
00348     return CAIRO_STATUS_SUCCESS;
00349 }
00350 
00351 /* Find active pen vertex for counterclockwise edge of stroke at the given slope.
00352  *
00353  * NOTE: The behavior of this function is sensitive to the sense of
00354  * the inequality within _cairo_slope_clockwise/_cairo_slope_counter_clockwise.
00355  */
00356 cairo_status_t
00357 _cairo_pen_find_active_ccw_vertex_index (cairo_pen_t *pen,
00358                                     cairo_slope_t *slope,
00359                                     int *active)
00360 {
00361     int i;
00362     cairo_slope_t slope_reverse;
00363 
00364     slope_reverse = *slope;
00365     slope_reverse.dx = -slope_reverse.dx;
00366     slope_reverse.dy = -slope_reverse.dy;
00367 
00368     for (i=pen->num_vertices-1; i >= 0; i--) {
00369        if (_cairo_slope_counter_clockwise (&pen->vertices[i].slope_ccw, &slope_reverse)
00370            && _cairo_slope_clockwise (&pen->vertices[i].slope_cw, &slope_reverse))
00371            break;
00372     }
00373 
00374     *active = i;
00375 
00376     return CAIRO_STATUS_SUCCESS;
00377 }
00378 
00379 static cairo_status_t
00380 _cairo_pen_stroke_spline_half (cairo_pen_t *pen,
00381                             cairo_spline_t *spline,
00382                             cairo_direction_t dir,
00383                             cairo_polygon_t *polygon)
00384 {
00385     int i;
00386     cairo_status_t status;
00387     int start, stop, step;
00388     int active = 0;
00389     cairo_point_t hull_point;
00390     cairo_slope_t slope, initial_slope, final_slope;
00391     cairo_point_t *point = spline->points;
00392     int num_points = spline->num_points;
00393 
00394     if (dir == CAIRO_DIRECTION_FORWARD) {
00395        start = 0;
00396        stop = num_points;
00397        step = 1;
00398        initial_slope = spline->initial_slope;
00399        final_slope = spline->final_slope;
00400     } else {
00401        start = num_points - 1;
00402        stop = -1;
00403        step = -1;
00404        initial_slope = spline->final_slope;
00405        initial_slope.dx = -initial_slope.dx;
00406        initial_slope.dy = -initial_slope.dy;
00407        final_slope = spline->initial_slope;
00408        final_slope.dx = -final_slope.dx; 
00409        final_slope.dy = -final_slope.dy; 
00410     }
00411 
00412     _cairo_pen_find_active_cw_vertex_index (pen, &initial_slope, &active);
00413 
00414     i = start;
00415     while (i != stop) {
00416        hull_point.x = point[i].x + pen->vertices[active].point.x;
00417        hull_point.y = point[i].y + pen->vertices[active].point.y;
00418        status = _cairo_polygon_line_to (polygon, &hull_point);
00419        if (status)
00420            return status;
00421 
00422        if (i + step == stop)
00423            slope = final_slope;
00424        else
00425            _cairo_slope_init (&slope, &point[i], &point[i+step]);
00426        if (_cairo_slope_counter_clockwise (&slope, &pen->vertices[active].slope_ccw)) {
00427            if (++active == pen->num_vertices)
00428               active = 0;
00429        } else if (_cairo_slope_clockwise (&slope, &pen->vertices[active].slope_cw)) {
00430            if (--active == -1)
00431               active = pen->num_vertices - 1;
00432        } else {
00433            i += step;
00434        }
00435     }
00436 
00437     return CAIRO_STATUS_SUCCESS;
00438 }
00439 
00440 /* Compute outline of a given spline using the pen.
00441    The trapezoids needed to fill that outline will be added to traps
00442 */
00443 cairo_status_t
00444 _cairo_pen_stroke_spline (cairo_pen_t            *pen,
00445                        cairo_spline_t     *spline,
00446                        double             tolerance,
00447                        cairo_traps_t             *traps)
00448 {
00449     cairo_status_t status;
00450     cairo_polygon_t polygon;
00451 
00452     /* If the line width is so small that the pen is reduced to a
00453        single point, then we have nothing to do. */
00454     if (pen->num_vertices <= 1)
00455        return CAIRO_STATUS_SUCCESS;
00456 
00457     _cairo_polygon_init (&polygon);
00458 
00459     status = _cairo_spline_decompose (spline, tolerance);
00460     if (status)
00461        return status;
00462 
00463     status = _cairo_pen_stroke_spline_half (pen, spline, CAIRO_DIRECTION_FORWARD, &polygon);
00464     if (status)
00465        return status;
00466 
00467     status = _cairo_pen_stroke_spline_half (pen, spline, CAIRO_DIRECTION_REVERSE, &polygon);
00468     if (status)
00469        return status;
00470 
00471     _cairo_polygon_close (&polygon);
00472     _cairo_traps_tessellate_polygon (traps, &polygon, CAIRO_FILL_RULE_WINDING);
00473     _cairo_polygon_fini (&polygon);
00474     
00475     return CAIRO_STATUS_SUCCESS;
00476 }