diff options
Diffstat (limited to 'libart_lgpl/art_svp_vpath_stroke.c')
| -rw-r--r-- | libart_lgpl/art_svp_vpath_stroke.c | 617 |
1 files changed, 0 insertions, 617 deletions
diff --git a/libart_lgpl/art_svp_vpath_stroke.c b/libart_lgpl/art_svp_vpath_stroke.c deleted file mode 100644 index c231048103..0000000000 --- a/libart_lgpl/art_svp_vpath_stroke.c +++ /dev/null @@ -1,617 +0,0 @@ -/* Libart_LGPL - library of basic graphic primitives - * Copyright (C) 1998-2000 Raph Levien - * - * This library is free software; you can redistribute it and/or - * modify it under the terms of the GNU Library General Public - * License as published by the Free Software Foundation; either - * version 2 of the License, or (at your option) any later version. - * - * This library is distributed in the hope that it will be useful, - * but WITHOUT ANY WARRANTY; without even the implied warranty of - * MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the GNU - * Library General Public License for more details. - * - * You should have received a copy of the GNU Library General Public - * License along with this library; if not, write to the - * Free Software Foundation, Inc., 59 Temple Place - Suite 330, - * Boston, MA 02111-1307, USA. - */ - -#include "config.h" -#include "art_svp_vpath_stroke.h" - -#include <stdlib.h> -#include <math.h> - -#include "art_misc.h" - -#include "art_vpath.h" -#include "art_svp.h" -#ifdef ART_USE_NEW_INTERSECTOR -#include "art_svp_intersect.h" -#else -#include "art_svp_wind.h" -#endif -#include "art_svp_vpath.h" - -#define EPSILON 1e-6 -#define EPSILON_2 1e-12 - -#define yes_OPTIMIZE_INNER - -/* Render an arc segment starting at (xc + x0, yc + y0) to (xc + x1, - yc + y1), centered at (xc, yc), and with given radius. Both x0^2 + - y0^2 and x1^2 + y1^2 should be equal to radius^2. - - A positive value of radius means curve to the left, negative means - curve to the right. -*/ -static void -art_svp_vpath_stroke_arc (ArtVpath **p_vpath, gint *pn, gint *pn_max, - gdouble xc, gdouble yc, - gdouble x0, gdouble y0, - gdouble x1, gdouble y1, - gdouble radius, - gdouble flatness) -{ - gdouble theta; - gdouble th_0, th_1; - gint n_pts; - gint i; - gdouble aradius; - - aradius = fabs (radius); - theta = 2 * M_SQRT2 * sqrt (flatness / aradius); - th_0 = atan2 (y0, x0); - th_1 = atan2 (y1, x1); - if (radius > 0) - { - /* curve to the left */ - if (th_0 < th_1) th_0 += M_PI * 2; - n_pts = ceil ((th_0 - th_1) / theta); - } - else - { - /* curve to the right */ - if (th_1 < th_0) th_1 += M_PI * 2; - n_pts = ceil ((th_1 - th_0) / theta); - } - art_vpath_add_point (p_vpath, pn, pn_max, - ART_LINETO, xc + x0, yc + y0); - for (i = 1; i < n_pts; i++) - { - theta = th_0 + (th_1 - th_0) * i / n_pts; - art_vpath_add_point (p_vpath, pn, pn_max, - ART_LINETO, xc + cos (theta) * aradius, - yc + sin (theta) * aradius); - } - art_vpath_add_point (p_vpath, pn, pn_max, - ART_LINETO, xc + x1, yc + y1); -} - -/* Assume that forw and rev are at point i0. Bring them to i1, - joining with the vector i1 - i2. - - This used to be true, but isn't now that the stroke_raw code is - filtering out (near)zero length vectors: {It so happens that all - invocations of this function maintain the precondition i1 = i0 + 1, - so we could decrease the number of arguments by one. We haven't - done that here, though.} - - forw is to the line's right and rev is to its left. - - Precondition: no zero-length vectors, otherwise a divide by - zero will happen. */ -static void -render_seg (ArtVpath **p_forw, gint *pn_forw, gint *pn_forw_max, - ArtVpath **p_rev, gint *pn_rev, gint *pn_rev_max, - ArtVpath *vpath, gint i0, gint i1, gint i2, - ArtPathStrokeJoinType join, - gdouble line_width, gdouble miter_limit, gdouble flatness) -{ - gdouble dx0, dy0; - gdouble dx1, dy1; - gdouble dlx0, dly0; - gdouble dlx1, dly1; - gdouble dmx, dmy; - gdouble dmr2; - gdouble scale; - gdouble cross; - - /* The vectors of the lines from i0 to i1 and i1 to i2. */ - dx0 = vpath[i1].x - vpath[i0].x; - dy0 = vpath[i1].y - vpath[i0].y; - - dx1 = vpath[i2].x - vpath[i1].x; - dy1 = vpath[i2].y - vpath[i1].y; - - /* Set dl[xy]0 to the vector from i0 to i1, rotated counterclockwise - 90 degrees, and scaled to the length of line_width. */ - scale = line_width / sqrt (dx0 * dx0 + dy0 * dy0); - dlx0 = dy0 * scale; - dly0 = -dx0 * scale; - - /* Set dl[xy]1 to the vector from i1 to i2, rotated counterclockwise - 90 degrees, and scaled to the length of line_width. */ - scale = line_width / sqrt (dx1 * dx1 + dy1 * dy1); - dlx1 = dy1 * scale; - dly1 = -dx1 * scale; - - /* now, forw's last point is expected to be colinear along d[xy]0 - to point i0 - dl[xy]0, and rev with i0 + dl[xy]0. */ - - /* positive for positive area (i.e. left turn) */ - cross = dx1 * dy0 - dx0 * dy1; - - dmx = (dlx0 + dlx1) * 0.5; - dmy = (dly0 + dly1) * 0.5; - dmr2 = dmx * dmx + dmy * dmy; - - if (join == ART_PATH_STROKE_JOIN_MITER && - dmr2 * miter_limit * miter_limit < line_width * line_width) - join = ART_PATH_STROKE_JOIN_BEVEL; - - /* the case when dmr2 is zero or very small bothers me - (i.e. near a 180 degree angle) - ALEX: So, we avoid the optimization when dmr2 is very small. This should - be safe since dmx/y is only used in optimization and in MITER case, and MITER - should be converted to BEVEL when dmr2 is very small. */ - if (dmr2 > EPSILON_2) - { - scale = line_width * line_width / dmr2; - dmx *= scale; - dmy *= scale; - } - - if (cross * cross < EPSILON_2 && dx0 * dx1 + dy0 * dy1 >= 0) - { - /* going straight */ - art_vpath_add_point (p_forw, pn_forw, pn_forw_max, - ART_LINETO, vpath[i1].x - dlx0, vpath[i1].y - dly0); - art_vpath_add_point (p_rev, pn_rev, pn_rev_max, - ART_LINETO, vpath[i1].x + dlx0, vpath[i1].y + dly0); - } - else if (cross > 0) - { - /* left turn, forw is outside and rev is inside */ - - if ( -#ifdef NO_OPTIMIZE_INNER - 0 && -#endif - (dmr2 > EPSILON_2) && - /* check that i1 + dm[xy] is inside i0-i1 rectangle */ - (dx0 + dmx) * dx0 + (dy0 + dmy) * dy0 > 0 && - /* and that i1 + dm[xy] is inside i1-i2 rectangle */ - ((dx1 - dmx) * dx1 + (dy1 - dmy) * dy1 > 0) -#ifdef PEDANTIC_INNER - && - /* check that i1 + dl[xy]1 is inside i0-i1 rectangle */ - (dx0 + dlx1) * dx0 + (dy0 + dly1) * dy0 > 0 && - /* and that i1 + dl[xy]0 is inside i1-i2 rectangle */ - ((dx1 - dlx0) * dx1 + (dy1 - dly0) * dy1 > 0) -#endif - ) - { - /* can safely add single intersection point */ - art_vpath_add_point (p_rev, pn_rev, pn_rev_max, - ART_LINETO, vpath[i1].x + dmx, vpath[i1].y + dmy); - } - else - { - /* need to loop-de-loop the inside */ - art_vpath_add_point (p_rev, pn_rev, pn_rev_max, - ART_LINETO, vpath[i1].x + dlx0, vpath[i1].y + dly0); - art_vpath_add_point (p_rev, pn_rev, pn_rev_max, - ART_LINETO, vpath[i1].x, vpath[i1].y); - art_vpath_add_point (p_rev, pn_rev, pn_rev_max, - ART_LINETO, vpath[i1].x + dlx1, vpath[i1].y + dly1); - } - - if (join == ART_PATH_STROKE_JOIN_BEVEL) - { - /* bevel */ - art_vpath_add_point (p_forw, pn_forw, pn_forw_max, - ART_LINETO, vpath[i1].x - dlx0, vpath[i1].y - dly0); - art_vpath_add_point (p_forw, pn_forw, pn_forw_max, - ART_LINETO, vpath[i1].x - dlx1, vpath[i1].y - dly1); - } - else if (join == ART_PATH_STROKE_JOIN_MITER) - { - art_vpath_add_point (p_forw, pn_forw, pn_forw_max, - ART_LINETO, vpath[i1].x - dmx, vpath[i1].y - dmy); - } - else if (join == ART_PATH_STROKE_JOIN_ROUND) - art_svp_vpath_stroke_arc (p_forw, pn_forw, pn_forw_max, - vpath[i1].x, vpath[i1].y, - -dlx0, -dly0, - -dlx1, -dly1, - line_width, - flatness); - } - else - { - /* right turn, rev is outside and forw is inside */ - - if ( -#ifdef NO_OPTIMIZE_INNER - 0 && -#endif - (dmr2 > EPSILON_2) && - /* check that i1 - dm[xy] is inside i0-i1 rectangle */ - (dx0 - dmx) * dx0 + (dy0 - dmy) * dy0 > 0 && - /* and that i1 - dm[xy] is inside i1-i2 rectangle */ - ((dx1 + dmx) * dx1 + (dy1 + dmy) * dy1 > 0) -#ifdef PEDANTIC_INNER - && - /* check that i1 - dl[xy]1 is inside i0-i1 rectangle */ - (dx0 - dlx1) * dx0 + (dy0 - dly1) * dy0 > 0 && - /* and that i1 - dl[xy]0 is inside i1-i2 rectangle */ - ((dx1 + dlx0) * dx1 + (dy1 + dly0) * dy1 > 0) -#endif - ) - { - /* can safely add single intersection point */ - art_vpath_add_point (p_forw, pn_forw, pn_forw_max, - ART_LINETO, vpath[i1].x - dmx, vpath[i1].y - dmy); - } - else - { - /* need to loop-de-loop the inside */ - art_vpath_add_point (p_forw, pn_forw, pn_forw_max, - ART_LINETO, vpath[i1].x - dlx0, vpath[i1].y - dly0); - art_vpath_add_point (p_forw, pn_forw, pn_forw_max, - ART_LINETO, vpath[i1].x, vpath[i1].y); - art_vpath_add_point (p_forw, pn_forw, pn_forw_max, - ART_LINETO, vpath[i1].x - dlx1, vpath[i1].y - dly1); - } - - if (join == ART_PATH_STROKE_JOIN_BEVEL) - { - /* bevel */ - art_vpath_add_point (p_rev, pn_rev, pn_rev_max, - ART_LINETO, vpath[i1].x + dlx0, vpath[i1].y + dly0); - art_vpath_add_point (p_rev, pn_rev, pn_rev_max, - ART_LINETO, vpath[i1].x + dlx1, vpath[i1].y + dly1); - } - else if (join == ART_PATH_STROKE_JOIN_MITER) - { - art_vpath_add_point (p_rev, pn_rev, pn_rev_max, - ART_LINETO, vpath[i1].x + dmx, vpath[i1].y + dmy); - } - else if (join == ART_PATH_STROKE_JOIN_ROUND) - art_svp_vpath_stroke_arc (p_rev, pn_rev, pn_rev_max, - vpath[i1].x, vpath[i1].y, - dlx0, dly0, - dlx1, dly1, - -line_width, - flatness); - - } -} - -/* caps i1, under the assumption of a vector from i0 */ -static void -render_cap (ArtVpath **p_result, gint *pn_result, gint *pn_result_max, - ArtVpath *vpath, gint i0, gint i1, - ArtPathStrokeCapType cap, gdouble line_width, gdouble flatness) -{ - gdouble dx0, dy0; - gdouble dlx0, dly0; - gdouble scale; - gint n_pts; - gint i; - - dx0 = vpath[i1].x - vpath[i0].x; - dy0 = vpath[i1].y - vpath[i0].y; - - /* Set dl[xy]0 to the vector from i0 to i1, rotated counterclockwise - 90 degrees, and scaled to the length of line_width. */ - scale = line_width / sqrt (dx0 * dx0 + dy0 * dy0); - dlx0 = dy0 * scale; - dly0 = -dx0 * scale; - - switch (cap) - { - case ART_PATH_STROKE_CAP_BUTT: - art_vpath_add_point (p_result, pn_result, pn_result_max, - ART_LINETO, vpath[i1].x - dlx0, vpath[i1].y - dly0); - art_vpath_add_point (p_result, pn_result, pn_result_max, - ART_LINETO, vpath[i1].x + dlx0, vpath[i1].y + dly0); - break; - case ART_PATH_STROKE_CAP_ROUND: - n_pts = ceil (M_PI / (2.0 * M_SQRT2 * sqrt (flatness / line_width))); - art_vpath_add_point (p_result, pn_result, pn_result_max, - ART_LINETO, vpath[i1].x - dlx0, vpath[i1].y - dly0); - for (i = 1; i < n_pts; i++) - { - gdouble theta, c_th, s_th; - - theta = M_PI * i / n_pts; - c_th = cos (theta); - s_th = sin (theta); - art_vpath_add_point (p_result, pn_result, pn_result_max, - ART_LINETO, - vpath[i1].x - dlx0 * c_th - dly0 * s_th, - vpath[i1].y - dly0 * c_th + dlx0 * s_th); - } - art_vpath_add_point (p_result, pn_result, pn_result_max, - ART_LINETO, vpath[i1].x + dlx0, vpath[i1].y + dly0); - break; - case ART_PATH_STROKE_CAP_SQUARE: - art_vpath_add_point (p_result, pn_result, pn_result_max, - ART_LINETO, - vpath[i1].x - dlx0 - dly0, - vpath[i1].y - dly0 + dlx0); - art_vpath_add_point (p_result, pn_result, pn_result_max, - ART_LINETO, - vpath[i1].x + dlx0 - dly0, - vpath[i1].y + dly0 + dlx0); - break; - } -} - -/** - * art_svp_from_vpath_raw: Stroke a vector path, raw version - * @vpath: #ArtVPath to stroke. - * @join: Join style. - * @cap: Cap style. - * @line_width: Width of stroke. - * @miter_limit: Miter limit. - * @flatness: Flatness. - * - * Exactly the same as art_svp_vpath_stroke(), except that the resulting - * stroke outline may self-intersect and have regions of winding number - * greater than 1. - * - * Return value: Resulting raw stroked outline in svp format. - **/ -ArtVpath * -art_svp_vpath_stroke_raw (ArtVpath *vpath, - ArtPathStrokeJoinType join, - ArtPathStrokeCapType cap, - gdouble line_width, - gdouble miter_limit, - gdouble flatness) -{ - gint begin_idx, end_idx; - gint i; - ArtVpath *forw, *rev; - gint n_forw, n_rev; - gint n_forw_max, n_rev_max; - ArtVpath *result; - gint n_result, n_result_max; - gdouble half_lw = 0.5 * line_width; - gint closed; - gint last, this, next, second; - gdouble dx, dy; - - n_forw_max = 16; - forw = art_new (ArtVpath, n_forw_max); - - n_rev_max = 16; - rev = art_new (ArtVpath, n_rev_max); - - n_result = 0; - n_result_max = 16; - result = art_new (ArtVpath, n_result_max); - - for (begin_idx = 0; vpath[begin_idx].code != ART_END; begin_idx = end_idx) - { - n_forw = 0; - n_rev = 0; - - closed = (vpath[begin_idx].code == ART_MOVETO); - - /* we don't know what the first point joins with until we get to the - last point and see if it's closed. So we start with the second - line in the path. - - Note: this is not strictly true (we now know it's closed from - the opening pathcode), but why fix code that isn't broken? - */ - - this = begin_idx; - /* skip over identical points at the beginning of the subpath */ - for (i = this + 1; vpath[i].code == ART_LINETO; i++) - { - dx = vpath[i].x - vpath[this].x; - dy = vpath[i].y - vpath[this].y; - if (dx * dx + dy * dy > EPSILON_2) - break; - } - next = i; - second = next; - - /* invariant: this doesn't coincide with next */ - while (vpath[next].code == ART_LINETO) - { - last = this; - this = next; - /* skip over identical points after the beginning of the subpath */ - for (i = this + 1; vpath[i].code == ART_LINETO; i++) - { - dx = vpath[i].x - vpath[this].x; - dy = vpath[i].y - vpath[this].y; - if (dx * dx + dy * dy > EPSILON_2) - break; - } - next = i; - if (vpath[next].code != ART_LINETO) - { - /* reached end of path */ - /* make "closed" detection conform to PostScript - semantics (i.e. explicit closepath code rather than - just the fact that end of the path is the beginning) */ - if (closed && - vpath[this].x == vpath[begin_idx].x && - vpath[this].y == vpath[begin_idx].y) - { - gint j; - - /* path is closed, render join to beginning */ - render_seg (&forw, &n_forw, &n_forw_max, - &rev, &n_rev, &n_rev_max, - vpath, last, this, second, - join, half_lw, miter_limit, flatness); - - /* do forward path */ - art_vpath_add_point (&result, &n_result, &n_result_max, - ART_MOVETO, forw[n_forw - 1].x, - forw[n_forw - 1].y); - for (j = 0; j < n_forw; j++) - art_vpath_add_point (&result, &n_result, &n_result_max, - ART_LINETO, forw[j].x, - forw[j].y); - - /* do reverse path, reversed */ - art_vpath_add_point (&result, &n_result, &n_result_max, - ART_MOVETO, rev[0].x, - rev[0].y); - for (j = n_rev - 1; j >= 0; j--) - art_vpath_add_point (&result, &n_result, &n_result_max, - ART_LINETO, rev[j].x, - rev[j].y); - } - else - { - /* path is open */ - gint j; - - /* add to forw rather than result to ensure that - forw has at least one point. */ - render_cap (&forw, &n_forw, &n_forw_max, - vpath, last, this, - cap, half_lw, flatness); - art_vpath_add_point (&result, &n_result, &n_result_max, - ART_MOVETO, forw[0].x, - forw[0].y); - for (j = 1; j < n_forw; j++) - art_vpath_add_point (&result, &n_result, &n_result_max, - ART_LINETO, forw[j].x, - forw[j].y); - for (j = n_rev - 1; j >= 0; j--) - art_vpath_add_point (&result, &n_result, &n_result_max, - ART_LINETO, rev[j].x, - rev[j].y); - render_cap (&result, &n_result, &n_result_max, - vpath, second, begin_idx, - cap, half_lw, flatness); - art_vpath_add_point (&result, &n_result, &n_result_max, - ART_LINETO, forw[0].x, - forw[0].y); - } - } - else - render_seg (&forw, &n_forw, &n_forw_max, - &rev, &n_rev, &n_rev_max, - vpath, last, this, next, - join, half_lw, miter_limit, flatness); - } - end_idx = next; - } - - art_free (forw); - art_free (rev); - art_vpath_add_point (&result, &n_result, &n_result_max, ART_END, 0, 0); - return result; -} - -/* Render a vector path into a stroked outline. - - Status of this routine: - - Basic correctness: Only miter and bevel line joins are implemented, - and only butt line caps. Otherwise, seems to be fine. - - Numerical stability: We cheat (adding random perturbation). Thus, - it seems very likely that no numerical stability problems will be - seen in practice. - - Speed: Should be pretty good. - - Precision: The perturbation fuzzes the coordinates slightly, - but not enough to be visible. */ -/** - * art_svp_vpath_stroke: Stroke a vector path. - * @vpath: #ArtVPath to stroke. - * @join: Join style. - * @cap: Cap style. - * @line_width: Width of stroke. - * @miter_limit: Miter limit. - * @flatness: Flatness. - * - * Computes an svp representing the stroked outline of @vpath. The - * width of the stroked line is @line_width. - * - * Lines are joined according to the @join rule. Possible values are - * ART_PATH_STROKE_JOIN_MITER (for mitered joins), - * ART_PATH_STROKE_JOIN_ROUND (for round joins), and - * ART_PATH_STROKE_JOIN_BEVEL (for bevelled joins). The mitered join - * is converted to a bevelled join if the miter would extend to a - * distance of more than @miter_limit * @line_width from the actual - * join point. - * - * If there are open subpaths, the ends of these subpaths are capped - * according to the @cap rule. Possible values are - * ART_PATH_STROKE_CAP_BUTT (squared cap, extends exactly to end - * point), ART_PATH_STROKE_CAP_ROUND (rounded half-circle centered at - * the end point), and ART_PATH_STROKE_CAP_SQUARE (squared cap, - * extending half @line_width past the end point). - * - * The @flatness parameter controls the accuracy of the rendering. It - * is most important for determining the number of points to use to - * approximate circular arcs for round lines and joins. In general, the - * resulting vector path will be within @flatness pixels of the "ideal" - * path containing actual circular arcs. I reserve the right to use - * the @flatness parameter to convert bevelled joins to miters for very - * small turn angles, as this would reduce the number of points in the - * resulting outline path. - * - * The resulting path is "clean" with respect to self-intersections, i.e. - * the winding number is 0 or 1 at each point. - * - * Return value: Resulting stroked outline in svp format. - **/ -ArtSVP * -art_svp_vpath_stroke (ArtVpath *vpath, - ArtPathStrokeJoinType join, - ArtPathStrokeCapType cap, - gdouble line_width, - gdouble miter_limit, - gdouble flatness) -{ -#ifdef ART_USE_NEW_INTERSECTOR - ArtVpath *vpath_stroke; - ArtSVP *svp, *svp2; - ArtSvpWriter *swr; - - vpath_stroke = art_svp_vpath_stroke_raw (vpath, join, cap, - line_width, miter_limit, flatness); - svp = art_svp_from_vpath (vpath_stroke); - art_free (vpath_stroke); - - swr = art_svp_writer_rewind_new (ART_WIND_RULE_NONZERO); - art_svp_intersector (svp, swr); - - svp2 = art_svp_writer_rewind_reap (swr); - art_svp_free (svp); - return svp2; -#else - ArtVpath *vpath_stroke, *vpath2; - ArtSVP *svp, *svp2, *svp3; - - vpath_stroke = art_svp_vpath_stroke_raw (vpath, join, cap, - line_width, miter_limit, flatness); - vpath2 = art_vpath_perturb (vpath_stroke); - art_free (vpath_stroke); - svp = art_svp_from_vpath (vpath2); - art_free (vpath2); - svp2 = art_svp_uncross (svp); - art_svp_free (svp); - svp3 = art_svp_rewind_uncrossed (svp2, ART_WIND_RULE_NONZERO); - art_svp_free (svp2); - - return svp3; -#endif -} |