Back to index

lightning-sunbird  0.9+nobinonly
cairo-path-stroke.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 typedef struct cairo_stroker {
00042     cairo_gstate_t *gstate;
00043     cairo_traps_t *traps;
00044 
00045     int has_current_point;
00046     cairo_point_t current_point;
00047     cairo_point_t first_point;
00048 
00049     int has_current_face;
00050     cairo_stroke_face_t current_face;
00051 
00052     int has_first_face;
00053     cairo_stroke_face_t first_face;
00054 
00055     int dashed;
00056     int dash_index;
00057     int dash_on;
00058     double dash_remain;
00059 } cairo_stroker_t;
00060 
00061 /* private functions */
00062 static void
00063 _cairo_stroker_init (cairo_stroker_t *stroker, cairo_gstate_t *gstate, cairo_traps_t *traps);
00064 
00065 static void
00066 _cairo_stroker_fini (cairo_stroker_t *stroker);
00067 
00068 static cairo_status_t
00069 _cairo_stroker_move_to (void *closure, cairo_point_t *point);
00070 
00071 static cairo_status_t
00072 _cairo_stroker_line_to (void *closure, cairo_point_t *point);
00073 
00074 static cairo_status_t
00075 _cairo_stroker_line_to_dashed (void *closure, cairo_point_t *point);
00076 
00077 static cairo_status_t
00078 _cairo_stroker_curve_to (void *closure,
00079                       cairo_point_t *b,
00080                       cairo_point_t *c,
00081                       cairo_point_t *d);
00082 
00083 static cairo_status_t
00084 _cairo_stroker_curve_to_dashed (void *closure,
00085                             cairo_point_t *b,
00086                             cairo_point_t *c,
00087                             cairo_point_t *d);
00088 
00089 static cairo_status_t
00090 _cairo_stroker_close_path (void *closure);
00091 
00092 static void
00093 _translate_point (cairo_point_t *point, cairo_point_t *offset);
00094 
00095 static int
00096 _cairo_stroker_face_clockwise (cairo_stroke_face_t *in, cairo_stroke_face_t *out);
00097 
00098 static cairo_status_t
00099 _cairo_stroker_join (cairo_stroker_t *stroker, cairo_stroke_face_t *in, cairo_stroke_face_t *out);
00100 
00101 static void
00102 _cairo_stroker_start_dash (cairo_stroker_t *stroker)
00103 {
00104     cairo_gstate_t *gstate = stroker->gstate;
00105     double offset;
00106     int       on = 1;
00107     int       i = 0;
00108 
00109     offset = gstate->dash_offset;
00110     while (offset >= gstate->dash[i]) {
00111        offset -= gstate->dash[i];
00112        on = 1-on;
00113        if (++i == gstate->num_dashes)
00114            i = 0;
00115     }
00116     stroker->dashed = 1;
00117     stroker->dash_index = i;
00118     stroker->dash_on = on;
00119     stroker->dash_remain = gstate->dash[i] - offset;
00120 }
00121 
00122 static void
00123 _cairo_stroker_step_dash (cairo_stroker_t *stroker, double step)
00124 {
00125     cairo_gstate_t *gstate = stroker->gstate;
00126     stroker->dash_remain -= step;
00127     if (stroker->dash_remain <= 0) {
00128        stroker->dash_index++;
00129        if (stroker->dash_index == gstate->num_dashes)
00130            stroker->dash_index = 0;
00131        stroker->dash_on = 1-stroker->dash_on;
00132        stroker->dash_remain = gstate->dash[stroker->dash_index];
00133     }
00134 }
00135 
00136 static void
00137 _cairo_stroker_init (cairo_stroker_t *stroker, cairo_gstate_t *gstate, cairo_traps_t *traps)
00138 {
00139     stroker->gstate = gstate;
00140     stroker->traps = traps;
00141 
00142     stroker->has_current_point = 0;
00143     stroker->has_current_face = 0;
00144     stroker->has_first_face = 0;
00145 
00146     if (gstate->dash)
00147        _cairo_stroker_start_dash (stroker);
00148     else
00149        stroker->dashed = 0;
00150 }
00151 
00152 static void
00153 _cairo_stroker_fini (cairo_stroker_t *stroker)
00154 {
00155     /* nothing to do here */
00156 }
00157 
00158 static void
00159 _translate_point (cairo_point_t *point, cairo_point_t *offset)
00160 {
00161     point->x += offset->x;
00162     point->y += offset->y;
00163 }
00164 
00165 static int
00166 _cairo_stroker_face_clockwise (cairo_stroke_face_t *in, cairo_stroke_face_t *out)
00167 {
00168     cairo_slope_t in_slope, out_slope;
00169 
00170     _cairo_slope_init (&in_slope, &in->point, &in->cw);
00171     _cairo_slope_init (&out_slope, &out->point, &out->cw);
00172 
00173     return _cairo_slope_clockwise (&in_slope, &out_slope);
00174 }
00175 
00176 static cairo_status_t
00177 _cairo_stroker_join (cairo_stroker_t *stroker, cairo_stroke_face_t *in, cairo_stroke_face_t *out)
00178 {
00179     cairo_status_t   status;
00180     cairo_gstate_t   *gstate = stroker->gstate;
00181     int              clockwise = _cairo_stroker_face_clockwise (out, in);
00182     cairo_point_t    *inpt, *outpt;
00183 
00184     if (in->cw.x == out->cw.x
00185        && in->cw.y == out->cw.y
00186        && in->ccw.x == out->ccw.x
00187        && in->ccw.y == out->ccw.y) {
00188        return CAIRO_STATUS_SUCCESS;
00189     }
00190 
00191     if (clockwise) {
00192        inpt = &in->ccw;
00193        outpt = &out->ccw;
00194     } else {
00195        inpt = &in->cw;
00196        outpt = &out->cw;
00197     }
00198 
00199     switch (gstate->line_join) {
00200     case CAIRO_LINE_JOIN_ROUND: {
00201        int i;
00202        int start, step, stop;
00203        cairo_point_t tri[3];
00204        cairo_pen_t *pen = &gstate->pen_regular;
00205 
00206        tri[0] = in->point;
00207        if (clockwise) {
00208            _cairo_pen_find_active_ccw_vertex_index (pen, &in->dev_vector, &start);
00209            step = -1;
00210            _cairo_pen_find_active_ccw_vertex_index (pen, &out->dev_vector, &stop);
00211        } else {
00212            _cairo_pen_find_active_cw_vertex_index (pen, &in->dev_vector, &start);
00213            step = +1;
00214            _cairo_pen_find_active_cw_vertex_index (pen, &out->dev_vector, &stop);
00215        }
00216 
00217        i = start;
00218        tri[1] = *inpt;
00219        while (i != stop) {
00220            tri[2] = in->point;
00221            _translate_point (&tri[2], &pen->vertices[i].point);
00222            _cairo_traps_tessellate_triangle (stroker->traps, tri);
00223            tri[1] = tri[2];
00224            i += step;
00225            if (i < 0)
00226               i = pen->num_vertices - 1;
00227            if (i >= pen->num_vertices)
00228               i = 0;
00229        }
00230 
00231        tri[2] = *outpt;
00232 
00233        return _cairo_traps_tessellate_triangle (stroker->traps, tri);
00234     }
00235     case CAIRO_LINE_JOIN_MITER:
00236     default: {
00237        /* dot product of incoming slope vector with outgoing slope vector */
00238        double in_dot_out = ((-in->usr_vector.x * out->usr_vector.x)+
00239                            (-in->usr_vector.y * out->usr_vector.y));
00240        double ml = gstate->miter_limit;
00241 
00242        /*
00243         * Check the miter limit -- lines meeting at an acute angle
00244         * can generate long miters, the limit converts them to bevel
00245         *
00246         * We want to know when the miter is within the miter limit.
00247         * That's straightforward to specify:
00248         *
00249         *     secant (psi / 2) <= ml
00250         *
00251         * where psi is the angle between in and out
00252         *
00253         *                          secant(psi/2) = 1/sin(psi/2)
00254         *     1/sin(psi/2) <= ml
00255         *     1 <= ml sin(psi/2)
00256         *     1 <= ml² sin²(psi/2)
00257         *     2 <= ml² 2 sin²(psi/2)
00258         *                          2·sin²(psi/2) = 1-cos(psi)
00259         *     2 <= ml² (1-cos(psi))
00260         *
00261         *                          in · out = |in| |out| cos (psi)
00262         *
00263         * in and out are both unit vectors, so:
00264         *
00265         *                          in · out = cos (psi)
00266         *
00267         *     2 <= ml² (1 - in · out)
00268         *      
00269         */
00270        if (2 <= ml * ml * (1 - in_dot_out)) {
00271            double           x1, y1, x2, y2;
00272            double           mx, my;
00273            double           dx1, dx2, dy1, dy2;
00274            cairo_polygon_t  polygon;
00275            cairo_point_t    outer;
00276 
00277            /* 
00278             * we've got the points already transformed to device
00279             * space, but need to do some computation with them and
00280             * also need to transform the slope from user space to
00281             * device space
00282             */
00283            /* outer point of incoming line face */
00284            x1 = _cairo_fixed_to_double (inpt->x);
00285            y1 = _cairo_fixed_to_double (inpt->y);
00286            dx1 = in->usr_vector.x;
00287            dy1 = in->usr_vector.y;
00288            cairo_matrix_transform_distance (&gstate->ctm, &dx1, &dy1);
00289            
00290            /* outer point of outgoing line face */
00291            x2 = _cairo_fixed_to_double (outpt->x);
00292            y2 = _cairo_fixed_to_double (outpt->y);
00293            dx2 = out->usr_vector.x;
00294            dy2 = out->usr_vector.y;
00295            cairo_matrix_transform_distance (&gstate->ctm, &dx2, &dy2);
00296            
00297            /*
00298             * Compute the location of the outer corner of the miter.
00299             * That's pretty easy -- just the intersection of the two
00300             * outer edges.  We've got slopes and points on each
00301             * of those edges.  Compute my directly, then compute
00302             * mx by using the edge with the larger dy; that avoids
00303             * dividing by values close to zero.
00304             */
00305            my = (((x2 - x1) * dy1 * dy2 - y2 * dx2 * dy1 + y1 * dx1 * dy2) /
00306                 (dx1 * dy2 - dx2 * dy1));
00307            if (fabs (dy1) >= fabs (dy2))
00308               mx = (my - y1) * dx1 / dy1 + x1;
00309            else
00310               mx = (my - y2) * dx2 / dy2 + x2;
00311            
00312            /*
00313             * Draw the quadrilateral
00314             */
00315            outer.x = _cairo_fixed_from_double (mx);
00316            outer.y = _cairo_fixed_from_double (my);
00317            _cairo_polygon_init (&polygon);
00318            _cairo_polygon_move_to (&polygon, &in->point);
00319            _cairo_polygon_line_to (&polygon, inpt);
00320            _cairo_polygon_line_to (&polygon, &outer);
00321            _cairo_polygon_line_to (&polygon, outpt);
00322            _cairo_polygon_close (&polygon);
00323            status = _cairo_traps_tessellate_polygon (stroker->traps,
00324                                                 &polygon,
00325                                                 CAIRO_FILL_RULE_WINDING);
00326            _cairo_polygon_fini (&polygon);
00327 
00328            return status;
00329        }
00330        /* fall through ... */
00331     }
00332     case CAIRO_LINE_JOIN_BEVEL: {
00333        cairo_point_t tri[3];
00334        tri[0] = in->point;
00335        tri[1] = *inpt;
00336        tri[2] = *outpt;
00337 
00338        return _cairo_traps_tessellate_triangle (stroker->traps, tri);
00339     }
00340     }
00341 }
00342 
00343 static cairo_status_t
00344 _cairo_stroker_add_cap (cairo_stroker_t *stroker, cairo_stroke_face_t *f)
00345 {
00346     cairo_status_t       status;
00347     cairo_gstate_t       *gstate = stroker->gstate;
00348 
00349     if (gstate->line_cap == CAIRO_LINE_CAP_BUTT)
00350        return CAIRO_STATUS_SUCCESS;
00351     
00352     switch (gstate->line_cap) {
00353     case CAIRO_LINE_CAP_ROUND: {
00354        int i;
00355        int start, stop;
00356        cairo_slope_t slope;
00357        cairo_point_t tri[3];
00358        cairo_pen_t *pen = &gstate->pen_regular;
00359 
00360        slope = f->dev_vector;
00361        _cairo_pen_find_active_cw_vertex_index (pen, &slope, &start);
00362        slope.dx = -slope.dx;
00363        slope.dy = -slope.dy;
00364        _cairo_pen_find_active_cw_vertex_index (pen, &slope, &stop);
00365 
00366        tri[0] = f->point;
00367        tri[1] = f->cw;
00368        for (i=start; i != stop; i = (i+1) % pen->num_vertices) {
00369            tri[2] = f->point;
00370            _translate_point (&tri[2], &pen->vertices[i].point);
00371            _cairo_traps_tessellate_triangle (stroker->traps, tri);
00372            tri[1] = tri[2];
00373        }
00374        tri[2] = f->ccw;
00375 
00376        return _cairo_traps_tessellate_triangle (stroker->traps, tri);
00377     }
00378     case CAIRO_LINE_CAP_SQUARE: {
00379        double dx, dy;
00380        cairo_slope_t fvector;
00381        cairo_point_t occw, ocw;
00382        cairo_polygon_t      polygon;
00383 
00384        dx = f->usr_vector.x;
00385        dy = f->usr_vector.y;
00386        dx *= gstate->line_width / 2.0;
00387        dy *= gstate->line_width / 2.0;
00388        cairo_matrix_transform_distance (&gstate->ctm, &dx, &dy);
00389        fvector.dx = _cairo_fixed_from_double (dx);
00390        fvector.dy = _cairo_fixed_from_double (dy);
00391        occw.x = f->ccw.x + fvector.dx;
00392        occw.y = f->ccw.y + fvector.dy;
00393        ocw.x = f->cw.x + fvector.dx;
00394        ocw.y = f->cw.y + fvector.dy;
00395 
00396        _cairo_polygon_init (&polygon);
00397        _cairo_polygon_move_to (&polygon, &f->cw);
00398        _cairo_polygon_line_to (&polygon, &ocw);
00399        _cairo_polygon_line_to (&polygon, &occw);
00400        _cairo_polygon_line_to (&polygon, &f->ccw);
00401        _cairo_polygon_close (&polygon);
00402 
00403        status = _cairo_traps_tessellate_polygon (stroker->traps, &polygon, CAIRO_FILL_RULE_WINDING);
00404        _cairo_polygon_fini (&polygon);
00405 
00406        return status;
00407     }
00408     case CAIRO_LINE_CAP_BUTT:
00409     default:
00410        return CAIRO_STATUS_SUCCESS;
00411     }
00412 }
00413 
00414 static cairo_status_t
00415 _cairo_stroker_add_leading_cap (cairo_stroker_t     *stroker,
00416                             cairo_stroke_face_t *face)
00417 {
00418     cairo_stroke_face_t reversed;
00419     cairo_point_t t;
00420 
00421     reversed = *face;
00422 
00423     /* The initial cap needs an outward facing vector. Reverse everything */
00424     reversed.usr_vector.x = -reversed.usr_vector.x;
00425     reversed.usr_vector.y = -reversed.usr_vector.y;
00426     reversed.dev_vector.dx = -reversed.dev_vector.dx;
00427     reversed.dev_vector.dy = -reversed.dev_vector.dy;
00428     t = reversed.cw;
00429     reversed.cw = reversed.ccw;
00430     reversed.ccw = t;
00431 
00432     return _cairo_stroker_add_cap (stroker, &reversed);
00433 }
00434 
00435 static cairo_status_t
00436 _cairo_stroker_add_trailing_cap (cairo_stroker_t     *stroker,
00437                              cairo_stroke_face_t *face)
00438 {
00439     return _cairo_stroker_add_cap (stroker, face);
00440 }
00441 
00442 static cairo_status_t
00443 _cairo_stroker_add_caps (cairo_stroker_t *stroker)
00444 {
00445     cairo_status_t status;
00446 
00447     if (stroker->has_first_face) {
00448        status = _cairo_stroker_add_leading_cap (stroker, &stroker->first_face);
00449        if (status)
00450            return status;
00451     }
00452 
00453     if (stroker->has_current_face) {
00454        status = _cairo_stroker_add_trailing_cap (stroker, &stroker->current_face);
00455        if (status)
00456            return status;
00457     }
00458 
00459     return CAIRO_STATUS_SUCCESS;
00460 }
00461 
00462 static void
00463 _compute_face (cairo_point_t *point, cairo_slope_t *slope, cairo_gstate_t *gstate, cairo_stroke_face_t *face)
00464 {
00465     double mag, det;
00466     double line_dx, line_dy;
00467     double face_dx, face_dy;
00468     cairo_point_double_t usr_vector;
00469     cairo_point_t offset_ccw, offset_cw;
00470 
00471     line_dx = _cairo_fixed_to_double (slope->dx);
00472     line_dy = _cairo_fixed_to_double (slope->dy);
00473 
00474     /* faces are normal in user space, not device space */
00475     cairo_matrix_transform_distance (&gstate->ctm_inverse, &line_dx, &line_dy);
00476 
00477     mag = sqrt (line_dx * line_dx + line_dy * line_dy);
00478     if (mag == 0) {
00479        /* XXX: Can't compute other face points. Do we want a tag in the face for this case? */
00480        return;
00481     }
00482 
00483     /* normalize to unit length */
00484     line_dx /= mag;
00485     line_dy /= mag;
00486 
00487     usr_vector.x = line_dx;
00488     usr_vector.y = line_dy;
00489 
00490     /* 
00491      * rotate to get a line_width/2 vector along the face, note that
00492      * the vector must be rotated the right direction in device space,
00493      * but by 90° in user space. So, the rotation depends on
00494      * whether the ctm reflects or not, and that can be determined
00495      * by looking at the determinant of the matrix.
00496      */
00497     _cairo_matrix_compute_determinant (&gstate->ctm, &det);
00498     if (det >= 0)
00499     {
00500        face_dx = - line_dy * (gstate->line_width / 2.0);
00501        face_dy = line_dx * (gstate->line_width / 2.0);
00502     }
00503     else
00504     {
00505        face_dx = line_dy * (gstate->line_width / 2.0);
00506        face_dy = - line_dx * (gstate->line_width / 2.0);
00507     }
00508 
00509     /* back to device space */
00510     cairo_matrix_transform_distance (&gstate->ctm, &face_dx, &face_dy);
00511 
00512     offset_ccw.x = _cairo_fixed_from_double (face_dx);
00513     offset_ccw.y = _cairo_fixed_from_double (face_dy);
00514     offset_cw.x = -offset_ccw.x;
00515     offset_cw.y = -offset_ccw.y;
00516 
00517     face->ccw = *point;
00518     _translate_point (&face->ccw, &offset_ccw);
00519 
00520     face->point = *point;
00521 
00522     face->cw = *point;
00523     _translate_point (&face->cw, &offset_cw);
00524 
00525     face->usr_vector.x = usr_vector.x;
00526     face->usr_vector.y = usr_vector.y;
00527 
00528     face->dev_vector = *slope;
00529 }
00530 
00531 static cairo_status_t
00532 _cairo_stroker_add_sub_edge (cairo_stroker_t *stroker, cairo_point_t *p1, cairo_point_t *p2,
00533                           cairo_stroke_face_t *start, cairo_stroke_face_t *end)
00534 {
00535     cairo_status_t status;
00536     cairo_gstate_t *gstate = stroker->gstate;
00537     cairo_polygon_t polygon;
00538     cairo_slope_t slope;
00539 
00540     if (p1->x == p2->x && p1->y == p2->y) {
00541        /* XXX: Need to rethink how this case should be handled, (both
00542            here and in _compute_face). The key behavior is that
00543            degenerate paths should draw as much as possible. */
00544        return CAIRO_STATUS_SUCCESS;
00545     }
00546 
00547     _cairo_slope_init (&slope, p1, p2);
00548     _compute_face (p1, &slope, gstate, start);
00549 
00550     /* XXX: This could be optimized slightly by not calling
00551        _compute_face again but rather  translating the relevant
00552        fields from start. */
00553     _compute_face (p2, &slope, gstate, end);
00554 
00555     /* XXX: I should really check the return value of the
00556        move_to/line_to functions here to catch out of memory
00557        conditions. But since that would be ugly, I'd prefer to add a
00558        status flag to the polygon object that I could check only once
00559        at then end of this sequence, (like we do with cairo_t
00560        already). */
00561     _cairo_polygon_init (&polygon);
00562     _cairo_polygon_move_to (&polygon, &start->cw);
00563     _cairo_polygon_line_to (&polygon, &start->ccw);
00564     _cairo_polygon_line_to (&polygon, &end->ccw);
00565     _cairo_polygon_line_to (&polygon, &end->cw);
00566     _cairo_polygon_close (&polygon);
00567 
00568     /* XXX: We can't use tessellate_rectangle as the matrix may have
00569        skewed this into a non-rectangular shape. Perhaps it would be
00570        worth checking the matrix for skew so that the common case
00571        could use the faster tessellate_rectangle rather than
00572        tessellate_polygon? */
00573     status = _cairo_traps_tessellate_polygon (stroker->traps,
00574                                          &polygon, CAIRO_FILL_RULE_WINDING);
00575 
00576     _cairo_polygon_fini (&polygon);
00577 
00578     return status;
00579 }
00580 
00581 static cairo_status_t
00582 _cairo_stroker_move_to (void *closure, cairo_point_t *point)
00583 {
00584     cairo_status_t status;
00585     cairo_stroker_t *stroker = closure;
00586 
00587     status = _cairo_stroker_add_caps (stroker);
00588     if (status)
00589        return status;
00590 
00591     stroker->first_point = *point;
00592     stroker->current_point = *point;
00593     stroker->has_current_point = 1;
00594 
00595     stroker->has_first_face = 0;
00596     stroker->has_current_face = 0;
00597 
00598     return CAIRO_STATUS_SUCCESS;
00599 }
00600 
00601 static cairo_status_t
00602 _cairo_stroker_line_to (void *closure, cairo_point_t *point)
00603 {
00604     cairo_status_t status;
00605     cairo_stroker_t *stroker = closure;
00606     cairo_stroke_face_t start, end;
00607     cairo_point_t *p1 = &stroker->current_point;
00608     cairo_point_t *p2 = point;
00609 
00610     if (!stroker->has_current_point)
00611        return _cairo_stroker_move_to (stroker, point);
00612 
00613     if (p1->x == p2->x && p1->y == p2->y) {
00614        /* XXX: Need to rethink how this case should be handled, (both
00615            here and in cairo_stroker_add_sub_edge and in _compute_face). The
00616            key behavior is that degenerate paths should draw as much
00617            as possible. */
00618        return CAIRO_STATUS_SUCCESS;
00619     }
00620     
00621     status = _cairo_stroker_add_sub_edge (stroker, p1, p2, &start, &end);
00622     if (status)
00623        return status;
00624 
00625     if (stroker->has_current_face) {
00626        status = _cairo_stroker_join (stroker, &stroker->current_face, &start);
00627        if (status)
00628            return status;
00629     } else {
00630        if (!stroker->has_first_face) {
00631            stroker->first_face = start;
00632            stroker->has_first_face = 1;
00633        }
00634     }
00635     stroker->current_face = end;
00636     stroker->has_current_face = 1;
00637 
00638     stroker->current_point = *point;
00639 
00640     return CAIRO_STATUS_SUCCESS;
00641 }
00642 
00643 /*
00644  * Dashed lines.  Cap each dash end, join around turns when on
00645  */
00646 static cairo_status_t
00647 _cairo_stroker_line_to_dashed (void *closure, cairo_point_t *point)
00648 {
00649     cairo_status_t status = CAIRO_STATUS_SUCCESS;
00650     cairo_stroker_t *stroker = closure;
00651     cairo_gstate_t *gstate = stroker->gstate;
00652     double mag, remain, tmp;
00653     double dx, dy;
00654     double dx2, dy2;
00655     cairo_point_t fd1, fd2;
00656     int first = 1;
00657     cairo_stroke_face_t sub_start, sub_end;
00658     cairo_point_t *p1 = &stroker->current_point;
00659     cairo_point_t *p2 = point;
00660 
00661     if (!stroker->has_current_point)
00662        return _cairo_stroker_move_to (stroker, point);
00663     
00664     dx = _cairo_fixed_to_double (p2->x - p1->x);
00665     dy = _cairo_fixed_to_double (p2->y - p1->y);
00666 
00667     cairo_matrix_transform_distance (&gstate->ctm_inverse, &dx, &dy);
00668 
00669     mag = sqrt (dx *dx + dy * dy);
00670     remain = mag;
00671     fd1 = *p1;
00672     while (remain) {
00673        tmp = stroker->dash_remain;
00674        if (tmp > remain)
00675            tmp = remain;
00676        remain -= tmp;
00677         dx2 = dx * (mag - remain)/mag;
00678        dy2 = dy * (mag - remain)/mag;
00679        cairo_matrix_transform_distance (&gstate->ctm, &dx2, &dy2);
00680        fd2.x = _cairo_fixed_from_double (dx2);
00681        fd2.y = _cairo_fixed_from_double (dy2);
00682        fd2.x += p1->x;
00683        fd2.y += p1->y;
00684        /*
00685         * XXX simplify this case analysis
00686         */
00687        if (stroker->dash_on) {
00688            status = _cairo_stroker_add_sub_edge (stroker, &fd1, &fd2, &sub_start, &sub_end);
00689            if (status)
00690               return status;
00691            if (!first) {
00692               /*
00693                * Not first dash in this segment, cap start
00694                */
00695               status = _cairo_stroker_add_leading_cap (stroker, &sub_start);
00696               if (status)
00697                   return status;
00698            } else {
00699               /*
00700                * First in this segment, join to any current_face, else
00701                * if at start of sub-path, mark position, else
00702                * cap
00703                */
00704               if (stroker->has_current_face) {
00705                   status = _cairo_stroker_join (stroker, &stroker->current_face, &sub_start);
00706                   if (status)
00707                      return status;
00708               } else {
00709                   if (!stroker->has_first_face) {
00710                      stroker->first_face = sub_start;
00711                      stroker->has_first_face = 1;
00712                   } else {
00713                      status = _cairo_stroker_add_leading_cap (stroker, &sub_start);
00714                      if (status)
00715                          return status;
00716                   }
00717               }
00718            }
00719            if (remain) {
00720               /*
00721                * Cap if not at end of segment
00722                */
00723               status = _cairo_stroker_add_trailing_cap (stroker, &sub_end);
00724               if (status)
00725                   return status;
00726            } else {
00727               /*
00728                * Mark previous line face and fix up next time
00729                * through
00730                */
00731               stroker->current_face = sub_end;
00732               stroker->has_current_face = 1;
00733            }
00734        } else {
00735            /*
00736             * If starting with off dash, check previous face
00737             * and cap if necessary
00738             */
00739            if (first) {
00740               if (stroker->has_current_face) {
00741                   status = _cairo_stroker_add_trailing_cap (stroker, &stroker->current_face);
00742                   if (status)
00743                      return status;
00744               }
00745            }
00746            if (!remain)
00747               stroker->has_current_face = 0;
00748        }
00749        _cairo_stroker_step_dash (stroker, tmp);
00750        fd1 = fd2;
00751        first = 0;
00752     }
00753 
00754     stroker->current_point = *point;
00755 
00756     return status;
00757 }
00758 
00759 static cairo_status_t
00760 _cairo_stroker_curve_to (void *closure,
00761                       cairo_point_t *b,
00762                       cairo_point_t *c,
00763                       cairo_point_t *d)
00764 {
00765     cairo_status_t status = CAIRO_STATUS_SUCCESS;
00766     cairo_stroker_t *stroker = closure;
00767     cairo_gstate_t *gstate = stroker->gstate;
00768     cairo_spline_t spline;
00769     cairo_pen_t pen;
00770     cairo_stroke_face_t start, end;
00771     cairo_point_t extra_points[4];
00772     cairo_point_t *a = &stroker->current_point;
00773 
00774     status = _cairo_spline_init (&spline, a, b, c, d);
00775     if (status == CAIRO_INT_STATUS_DEGENERATE)
00776        return CAIRO_STATUS_SUCCESS;
00777 
00778     status = _cairo_pen_init_copy (&pen, &gstate->pen_regular);
00779     if (status)
00780        goto CLEANUP_SPLINE;
00781 
00782     _compute_face (a, &spline.initial_slope, gstate, &start);
00783     _compute_face (d, &spline.final_slope, gstate, &end);
00784 
00785     if (stroker->has_current_face) {
00786        status = _cairo_stroker_join (stroker, &stroker->current_face, &start);
00787        if (status)
00788            return status;
00789     } else {
00790        if (!stroker->has_first_face) {
00791            stroker->first_face = start;
00792            stroker->has_first_face = 1;
00793        }
00794     }
00795     stroker->current_face = end;
00796     stroker->has_current_face = 1;
00797     
00798     extra_points[0] = start.cw;
00799     extra_points[0].x -= start.point.x;
00800     extra_points[0].y -= start.point.y;
00801     extra_points[1] = start.ccw;
00802     extra_points[1].x -= start.point.x;
00803     extra_points[1].y -= start.point.y;
00804     extra_points[2] = end.cw;
00805     extra_points[2].x -= end.point.x;
00806     extra_points[2].y -= end.point.y;
00807     extra_points[3] = end.ccw;
00808     extra_points[3].x -= end.point.x;
00809     extra_points[3].y -= end.point.y;
00810     
00811     status = _cairo_pen_add_points (&pen, extra_points, 4);
00812     if (status)
00813        goto CLEANUP_PEN;
00814 
00815     status = _cairo_pen_stroke_spline (&pen, &spline, gstate->tolerance, stroker->traps);
00816     if (status)
00817        goto CLEANUP_PEN;
00818 
00819   CLEANUP_PEN:
00820     _cairo_pen_fini (&pen);
00821   CLEANUP_SPLINE:
00822     _cairo_spline_fini (&spline);
00823 
00824     stroker->current_point = *d;
00825 
00826     return status;
00827 }
00828 
00829 /* We're using two different algorithms here for dashed and un-dashed
00830  * splines. The dashed alogorithm uses the existing line dashing
00831  * code. It's linear in path length, but gets subtly wrong results for
00832  * self-intersecting paths (an outstanding but for self-intersecting
00833  * non-curved paths as well). The non-dashed algorithm tessellates a
00834  * single polygon for the whole curve. It handles the
00835  * self-intersecting problem, but it's (unsurprisingly) not O(n) and
00836  * more significantly, it doesn't yet handle dashes.
00837  *
00838  * The only reason we're doing split algortihms here is to
00839  * minimize the impact of fixing the splines-aren't-dashed bug for
00840  * 1.0.2. Long-term the right answer is to rewrite the whole pile
00841  * of stroking code so that the entire result is computed as a
00842  * single polygon that is tessellated, (that is, stroking can be
00843  * built on top of filling). That will solve the self-intersecting
00844  * problem. It will also increase the importance of implementing
00845  * an efficient and more robust tessellator.
00846  */
00847 static cairo_status_t
00848 _cairo_stroker_curve_to_dashed (void *closure,
00849                             cairo_point_t *b,
00850                             cairo_point_t *c,
00851                             cairo_point_t *d)
00852 {
00853     cairo_status_t status = CAIRO_STATUS_SUCCESS;
00854     cairo_stroker_t *stroker = closure;
00855     cairo_gstate_t *gstate = stroker->gstate;
00856     cairo_spline_t spline;
00857     cairo_point_t *a = &stroker->current_point;
00858     cairo_line_join_t line_join_save;
00859     int i;
00860 
00861     status = _cairo_spline_init (&spline, a, b, c, d);
00862     if (status == CAIRO_INT_STATUS_DEGENERATE)
00863        return CAIRO_STATUS_SUCCESS;
00864 
00865     /* If the line width is so small that the pen is reduced to a
00866        single point, then we have nothing to do. */
00867     if (gstate->pen_regular.num_vertices <= 1)
00868        goto CLEANUP_SPLINE;
00869 
00870     /* Temporarily modify the gstate to use round joins to guarantee
00871      * smooth stroked curves. */
00872     line_join_save = gstate->line_join;
00873     gstate->line_join = CAIRO_LINE_JOIN_ROUND;
00874 
00875     status = _cairo_spline_decompose (&spline, gstate->tolerance);
00876     if (status)
00877        goto CLEANUP_GSTATE;
00878 
00879     for (i = 1; i < spline.num_points; i++) {
00880        if (stroker->dashed)
00881            status = _cairo_stroker_line_to_dashed (stroker, &spline.points[i]);
00882        else
00883            status = _cairo_stroker_line_to (stroker, &spline.points[i]);
00884        if (status)
00885            break;
00886     }
00887 
00888   CLEANUP_GSTATE:
00889     gstate->line_join = line_join_save;
00890 
00891   CLEANUP_SPLINE:
00892     _cairo_spline_fini (&spline);
00893 
00894     return status;
00895 }
00896 
00897 static cairo_status_t
00898 _cairo_stroker_close_path (void *closure)
00899 {
00900     cairo_status_t status;
00901     cairo_stroker_t *stroker = closure;
00902 
00903     if (stroker->has_current_point) {
00904        if (stroker->dashed)
00905            status = _cairo_stroker_line_to_dashed (stroker, &stroker->first_point);
00906        else
00907            status = _cairo_stroker_line_to (stroker, &stroker->first_point);
00908        if (status)
00909            return status;
00910     }
00911 
00912     if (stroker->has_first_face && stroker->has_current_face) {
00913        status = _cairo_stroker_join (stroker, &stroker->current_face, &stroker->first_face);
00914        if (status)
00915            return status;
00916     }
00917 
00918     stroker->has_first_face = 0;
00919     stroker->has_current_face = 0;
00920     stroker->has_current_point = 0;
00921 
00922     return CAIRO_STATUS_SUCCESS;
00923 }
00924 
00925 cairo_status_t
00926 _cairo_path_fixed_stroke_to_traps (cairo_path_fixed_t *path,
00927                                cairo_gstate_t     *gstate,
00928                                cairo_traps_t      *traps)
00929 {
00930     cairo_status_t status = CAIRO_STATUS_SUCCESS;
00931     cairo_stroker_t stroker;
00932 
00933     _cairo_stroker_init (&stroker, gstate, traps);
00934 
00935     if (gstate->dash)
00936        status = _cairo_path_fixed_interpret (path,
00937                                          CAIRO_DIRECTION_FORWARD,
00938                                          _cairo_stroker_move_to,
00939                                          _cairo_stroker_line_to_dashed,
00940                                          _cairo_stroker_curve_to_dashed,
00941                                          _cairo_stroker_close_path,
00942                                          &stroker);
00943     else
00944        status = _cairo_path_fixed_interpret (path,
00945                                          CAIRO_DIRECTION_FORWARD,
00946                                          _cairo_stroker_move_to,
00947                                          _cairo_stroker_line_to,
00948                                          _cairo_stroker_curve_to,
00949                                          _cairo_stroker_close_path,
00950                                          &stroker);
00951     if (status)
00952        goto BAIL;
00953 
00954     status = _cairo_stroker_add_caps (&stroker);
00955 
00956 BAIL:
00957     _cairo_stroker_fini (&stroker);
00958 
00959     return status;
00960 }