[18255] | 1 | /* Libart_LGPL - library of basic graphic primitives |
---|
| 2 | * Copyright (C) 1998-2000 Raph Levien |
---|
| 3 | * |
---|
| 4 | * This library is free software; you can redistribute it and/or |
---|
| 5 | * modify it under the terms of the GNU Library General Public |
---|
| 6 | * License as published by the Free Software Foundation; either |
---|
| 7 | * version 2 of the License, or (at your option) any later version. |
---|
| 8 | * |
---|
| 9 | * This library is distributed in the hope that it will be useful, |
---|
| 10 | * but WITHOUT ANY WARRANTY; without even the implied warranty of |
---|
| 11 | * MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the GNU |
---|
| 12 | * Library General Public License for more details. |
---|
| 13 | * |
---|
| 14 | * You should have received a copy of the GNU Library General Public |
---|
| 15 | * License along with this library; if not, write to the |
---|
| 16 | * Free Software Foundation, Inc., 59 Temple Place - Suite 330, |
---|
| 17 | * Boston, MA 02111-1307, USA. |
---|
| 18 | */ |
---|
| 19 | |
---|
| 20 | |
---|
| 21 | #include "config.h" |
---|
| 22 | #include "art_svp_vpath_stroke.h" |
---|
| 23 | |
---|
| 24 | #include <stdlib.h> |
---|
| 25 | #include <math.h> |
---|
| 26 | |
---|
| 27 | #include "art_misc.h" |
---|
| 28 | |
---|
| 29 | #include "art_vpath.h" |
---|
| 30 | #include "art_svp.h" |
---|
| 31 | #ifdef ART_USE_NEW_INTERSECTOR |
---|
| 32 | #include "art_svp_intersect.h" |
---|
| 33 | #else |
---|
| 34 | #include "art_svp_wind.h" |
---|
| 35 | #endif |
---|
| 36 | #include "art_svp_vpath.h" |
---|
| 37 | |
---|
| 38 | #define EPSILON 1e-6 |
---|
| 39 | #define EPSILON_2 1e-12 |
---|
| 40 | |
---|
| 41 | #define yes_OPTIMIZE_INNER |
---|
| 42 | |
---|
| 43 | /* Render an arc segment starting at (xc + x0, yc + y0) to (xc + x1, |
---|
| 44 | yc + y1), centered at (xc, yc), and with given radius. Both x0^2 + |
---|
| 45 | y0^2 and x1^2 + y1^2 should be equal to radius^2. |
---|
| 46 | |
---|
| 47 | A positive value of radius means curve to the left, negative means |
---|
| 48 | curve to the right. |
---|
| 49 | */ |
---|
| 50 | static void |
---|
| 51 | art_svp_vpath_stroke_arc (ArtVpath **p_vpath, int *pn, int *pn_max, |
---|
| 52 | double xc, double yc, |
---|
| 53 | double x0, double y0, |
---|
| 54 | double x1, double y1, |
---|
| 55 | double radius, |
---|
| 56 | double flatness) |
---|
| 57 | { |
---|
| 58 | double theta; |
---|
| 59 | double th_0, th_1; |
---|
| 60 | int n_pts; |
---|
| 61 | int i; |
---|
| 62 | double aradius; |
---|
| 63 | |
---|
| 64 | aradius = fabs (radius); |
---|
| 65 | theta = 2 * M_SQRT2 * sqrt (flatness / aradius); |
---|
| 66 | th_0 = atan2 (y0, x0); |
---|
| 67 | th_1 = atan2 (y1, x1); |
---|
| 68 | if (radius > 0) |
---|
| 69 | { |
---|
| 70 | /* curve to the left */ |
---|
| 71 | if (th_0 < th_1) th_0 += M_PI * 2; |
---|
| 72 | n_pts = ceil ((th_0 - th_1) / theta); |
---|
| 73 | } |
---|
| 74 | else |
---|
| 75 | { |
---|
| 76 | /* curve to the right */ |
---|
| 77 | if (th_1 < th_0) th_1 += M_PI * 2; |
---|
| 78 | n_pts = ceil ((th_1 - th_0) / theta); |
---|
| 79 | } |
---|
| 80 | #ifdef VERBOSE |
---|
| 81 | printf ("start %f %f; th_0 = %f, th_1 = %f, r = %f, theta = %f\n", x0, y0, th_0, th_1, radius, theta); |
---|
| 82 | #endif |
---|
| 83 | art_vpath_add_point (p_vpath, pn, pn_max, |
---|
| 84 | ART_LINETO, xc + x0, yc + y0); |
---|
| 85 | for (i = 1; i < n_pts; i++) |
---|
| 86 | { |
---|
| 87 | theta = th_0 + (th_1 - th_0) * i / n_pts; |
---|
| 88 | art_vpath_add_point (p_vpath, pn, pn_max, |
---|
| 89 | ART_LINETO, xc + cos (theta) * aradius, |
---|
| 90 | yc + sin (theta) * aradius); |
---|
| 91 | #ifdef VERBOSE |
---|
| 92 | printf ("mid %f %f\n", cos (theta) * radius, sin (theta) * radius); |
---|
| 93 | #endif |
---|
| 94 | } |
---|
| 95 | art_vpath_add_point (p_vpath, pn, pn_max, |
---|
| 96 | ART_LINETO, xc + x1, yc + y1); |
---|
| 97 | #ifdef VERBOSE |
---|
| 98 | printf ("end %f %f\n", x1, y1); |
---|
| 99 | #endif |
---|
| 100 | } |
---|
| 101 | |
---|
| 102 | /* Assume that forw and rev are at point i0. Bring them to i1, |
---|
| 103 | joining with the vector i1 - i2. |
---|
| 104 | |
---|
| 105 | This used to be true, but isn't now that the stroke_raw code is |
---|
| 106 | filtering out (near)zero length vectors: {It so happens that all |
---|
| 107 | invocations of this function maintain the precondition i1 = i0 + 1, |
---|
| 108 | so we could decrease the number of arguments by one. We haven't |
---|
| 109 | done that here, though.} |
---|
| 110 | |
---|
| 111 | forw is to the line's right and rev is to its left. |
---|
| 112 | |
---|
| 113 | Precondition: no zero-length vectors, otherwise a divide by |
---|
| 114 | zero will happen. */ |
---|
| 115 | static void |
---|
| 116 | render_seg (ArtVpath **p_forw, int *pn_forw, int *pn_forw_max, |
---|
| 117 | ArtVpath **p_rev, int *pn_rev, int *pn_rev_max, |
---|
| 118 | ArtVpath *vpath, int i0, int i1, int i2, |
---|
| 119 | ArtPathStrokeJoinType join, |
---|
| 120 | double line_width, double miter_limit, double flatness) |
---|
| 121 | { |
---|
| 122 | double dx0, dy0; |
---|
| 123 | double dx1, dy1; |
---|
| 124 | double dlx0, dly0; |
---|
| 125 | double dlx1, dly1; |
---|
| 126 | double dmx, dmy; |
---|
| 127 | double dmr2; |
---|
| 128 | double scale; |
---|
| 129 | double cross; |
---|
| 130 | |
---|
| 131 | #ifdef VERBOSE |
---|
| 132 | printf ("join style = %d\n", join); |
---|
| 133 | #endif |
---|
| 134 | |
---|
| 135 | /* The vectors of the lines from i0 to i1 and i1 to i2. */ |
---|
| 136 | dx0 = vpath[i1].x - vpath[i0].x; |
---|
| 137 | dy0 = vpath[i1].y - vpath[i0].y; |
---|
| 138 | |
---|
| 139 | dx1 = vpath[i2].x - vpath[i1].x; |
---|
| 140 | dy1 = vpath[i2].y - vpath[i1].y; |
---|
| 141 | |
---|
| 142 | /* Set dl[xy]0 to the vector from i0 to i1, rotated counterclockwise |
---|
| 143 | 90 degrees, and scaled to the length of line_width. */ |
---|
| 144 | scale = line_width / sqrt (dx0 * dx0 + dy0 * dy0); |
---|
| 145 | dlx0 = dy0 * scale; |
---|
| 146 | dly0 = -dx0 * scale; |
---|
| 147 | |
---|
| 148 | /* Set dl[xy]1 to the vector from i1 to i2, rotated counterclockwise |
---|
| 149 | 90 degrees, and scaled to the length of line_width. */ |
---|
| 150 | scale = line_width / sqrt (dx1 * dx1 + dy1 * dy1); |
---|
| 151 | dlx1 = dy1 * scale; |
---|
| 152 | dly1 = -dx1 * scale; |
---|
| 153 | |
---|
| 154 | #ifdef VERBOSE |
---|
| 155 | printf ("%% render_seg: (%g, %g) - (%g, %g) - (%g, %g)\n", |
---|
| 156 | vpath[i0].x, vpath[i0].y, |
---|
| 157 | vpath[i1].x, vpath[i1].y, |
---|
| 158 | vpath[i2].x, vpath[i2].y); |
---|
| 159 | |
---|
| 160 | printf ("%% render_seg: d[xy]0 = (%g, %g), dl[xy]0 = (%g, %g)\n", |
---|
| 161 | dx0, dy0, dlx0, dly0); |
---|
| 162 | |
---|
| 163 | printf ("%% render_seg: d[xy]1 = (%g, %g), dl[xy]1 = (%g, %g)\n", |
---|
| 164 | dx1, dy1, dlx1, dly1); |
---|
| 165 | #endif |
---|
| 166 | |
---|
| 167 | /* now, forw's last point is expected to be colinear along d[xy]0 |
---|
| 168 | to point i0 - dl[xy]0, and rev with i0 + dl[xy]0. */ |
---|
| 169 | |
---|
| 170 | /* positive for positive area (i.e. left turn) */ |
---|
| 171 | cross = dx1 * dy0 - dx0 * dy1; |
---|
| 172 | |
---|
| 173 | dmx = (dlx0 + dlx1) * 0.5; |
---|
| 174 | dmy = (dly0 + dly1) * 0.5; |
---|
| 175 | dmr2 = dmx * dmx + dmy * dmy; |
---|
| 176 | |
---|
| 177 | if (join == ART_PATH_STROKE_JOIN_MITER && |
---|
| 178 | dmr2 * miter_limit * miter_limit < line_width * line_width) |
---|
| 179 | join = ART_PATH_STROKE_JOIN_BEVEL; |
---|
| 180 | |
---|
| 181 | /* the case when dmr2 is zero or very small bothers me |
---|
[20812] | 182 | (i.e. near a 180 degree angle) |
---|
| 183 | ALEX: So, we avoid the optimization when dmr2 is very small. This should |
---|
| 184 | be safe since dmx/y is only used in optimization and in MITER case, and MITER |
---|
| 185 | should be converted to BEVEL when dmr2 is very small. */ |
---|
| 186 | if (dmr2 > EPSILON_2) |
---|
| 187 | { |
---|
| 188 | scale = line_width * line_width / dmr2; |
---|
| 189 | dmx *= scale; |
---|
| 190 | dmy *= scale; |
---|
| 191 | } |
---|
[18255] | 192 | |
---|
| 193 | if (cross * cross < EPSILON_2 && dx0 * dx1 + dy0 * dy1 >= 0) |
---|
| 194 | { |
---|
| 195 | /* going straight */ |
---|
| 196 | #ifdef VERBOSE |
---|
| 197 | printf ("%% render_seg: straight\n"); |
---|
| 198 | #endif |
---|
| 199 | art_vpath_add_point (p_forw, pn_forw, pn_forw_max, |
---|
| 200 | ART_LINETO, vpath[i1].x - dlx0, vpath[i1].y - dly0); |
---|
| 201 | art_vpath_add_point (p_rev, pn_rev, pn_rev_max, |
---|
| 202 | ART_LINETO, vpath[i1].x + dlx0, vpath[i1].y + dly0); |
---|
| 203 | } |
---|
| 204 | else if (cross > 0) |
---|
| 205 | { |
---|
| 206 | /* left turn, forw is outside and rev is inside */ |
---|
| 207 | |
---|
| 208 | #ifdef VERBOSE |
---|
| 209 | printf ("%% render_seg: left\n"); |
---|
| 210 | #endif |
---|
| 211 | if ( |
---|
| 212 | #ifdef NO_OPTIMIZE_INNER |
---|
| 213 | 0 && |
---|
| 214 | #endif |
---|
[20812] | 215 | (dmr2 > EPSILON_2) && |
---|
[18255] | 216 | /* check that i1 + dm[xy] is inside i0-i1 rectangle */ |
---|
| 217 | (dx0 + dmx) * dx0 + (dy0 + dmy) * dy0 > 0 && |
---|
| 218 | /* and that i1 + dm[xy] is inside i1-i2 rectangle */ |
---|
| 219 | ((dx1 - dmx) * dx1 + (dy1 - dmy) * dy1 > 0) |
---|
| 220 | #ifdef PEDANTIC_INNER |
---|
| 221 | && |
---|
| 222 | /* check that i1 + dl[xy]1 is inside i0-i1 rectangle */ |
---|
| 223 | (dx0 + dlx1) * dx0 + (dy0 + dly1) * dy0 > 0 && |
---|
| 224 | /* and that i1 + dl[xy]0 is inside i1-i2 rectangle */ |
---|
| 225 | ((dx1 - dlx0) * dx1 + (dy1 - dly0) * dy1 > 0) |
---|
| 226 | #endif |
---|
| 227 | ) |
---|
| 228 | { |
---|
| 229 | /* can safely add single intersection point */ |
---|
| 230 | art_vpath_add_point (p_rev, pn_rev, pn_rev_max, |
---|
| 231 | ART_LINETO, vpath[i1].x + dmx, vpath[i1].y + dmy); |
---|
| 232 | } |
---|
| 233 | else |
---|
| 234 | { |
---|
| 235 | /* need to loop-de-loop the inside */ |
---|
| 236 | art_vpath_add_point (p_rev, pn_rev, pn_rev_max, |
---|
| 237 | ART_LINETO, vpath[i1].x + dlx0, vpath[i1].y + dly0); |
---|
| 238 | art_vpath_add_point (p_rev, pn_rev, pn_rev_max, |
---|
| 239 | ART_LINETO, vpath[i1].x, vpath[i1].y); |
---|
| 240 | art_vpath_add_point (p_rev, pn_rev, pn_rev_max, |
---|
| 241 | ART_LINETO, vpath[i1].x + dlx1, vpath[i1].y + dly1); |
---|
| 242 | } |
---|
| 243 | |
---|
| 244 | if (join == ART_PATH_STROKE_JOIN_BEVEL) |
---|
| 245 | { |
---|
| 246 | /* bevel */ |
---|
| 247 | art_vpath_add_point (p_forw, pn_forw, pn_forw_max, |
---|
| 248 | ART_LINETO, vpath[i1].x - dlx0, vpath[i1].y - dly0); |
---|
| 249 | art_vpath_add_point (p_forw, pn_forw, pn_forw_max, |
---|
| 250 | ART_LINETO, vpath[i1].x - dlx1, vpath[i1].y - dly1); |
---|
| 251 | } |
---|
| 252 | else if (join == ART_PATH_STROKE_JOIN_MITER) |
---|
| 253 | { |
---|
| 254 | art_vpath_add_point (p_forw, pn_forw, pn_forw_max, |
---|
| 255 | ART_LINETO, vpath[i1].x - dmx, vpath[i1].y - dmy); |
---|
| 256 | } |
---|
| 257 | else if (join == ART_PATH_STROKE_JOIN_ROUND) |
---|
| 258 | art_svp_vpath_stroke_arc (p_forw, pn_forw, pn_forw_max, |
---|
| 259 | vpath[i1].x, vpath[i1].y, |
---|
| 260 | -dlx0, -dly0, |
---|
| 261 | -dlx1, -dly1, |
---|
| 262 | line_width, |
---|
| 263 | flatness); |
---|
| 264 | } |
---|
| 265 | else |
---|
| 266 | { |
---|
| 267 | /* right turn, rev is outside and forw is inside */ |
---|
| 268 | #ifdef VERBOSE |
---|
| 269 | printf ("%% render_seg: right\n"); |
---|
| 270 | #endif |
---|
| 271 | |
---|
| 272 | if ( |
---|
| 273 | #ifdef NO_OPTIMIZE_INNER |
---|
| 274 | 0 && |
---|
| 275 | #endif |
---|
[20812] | 276 | (dmr2 > EPSILON_2) && |
---|
[18255] | 277 | /* check that i1 - dm[xy] is inside i0-i1 rectangle */ |
---|
| 278 | (dx0 - dmx) * dx0 + (dy0 - dmy) * dy0 > 0 && |
---|
| 279 | /* and that i1 - dm[xy] is inside i1-i2 rectangle */ |
---|
| 280 | ((dx1 + dmx) * dx1 + (dy1 + dmy) * dy1 > 0) |
---|
| 281 | #ifdef PEDANTIC_INNER |
---|
| 282 | && |
---|
| 283 | /* check that i1 - dl[xy]1 is inside i0-i1 rectangle */ |
---|
| 284 | (dx0 - dlx1) * dx0 + (dy0 - dly1) * dy0 > 0 && |
---|
| 285 | /* and that i1 - dl[xy]0 is inside i1-i2 rectangle */ |
---|
| 286 | ((dx1 + dlx0) * dx1 + (dy1 + dly0) * dy1 > 0) |
---|
| 287 | #endif |
---|
| 288 | ) |
---|
| 289 | { |
---|
| 290 | /* can safely add single intersection point */ |
---|
| 291 | art_vpath_add_point (p_forw, pn_forw, pn_forw_max, |
---|
| 292 | ART_LINETO, vpath[i1].x - dmx, vpath[i1].y - dmy); |
---|
| 293 | } |
---|
| 294 | else |
---|
| 295 | { |
---|
| 296 | /* need to loop-de-loop the inside */ |
---|
| 297 | art_vpath_add_point (p_forw, pn_forw, pn_forw_max, |
---|
| 298 | ART_LINETO, vpath[i1].x - dlx0, vpath[i1].y - dly0); |
---|
| 299 | art_vpath_add_point (p_forw, pn_forw, pn_forw_max, |
---|
| 300 | ART_LINETO, vpath[i1].x, vpath[i1].y); |
---|
| 301 | art_vpath_add_point (p_forw, pn_forw, pn_forw_max, |
---|
| 302 | ART_LINETO, vpath[i1].x - dlx1, vpath[i1].y - dly1); |
---|
| 303 | } |
---|
| 304 | |
---|
| 305 | if (join == ART_PATH_STROKE_JOIN_BEVEL) |
---|
| 306 | { |
---|
| 307 | /* bevel */ |
---|
| 308 | art_vpath_add_point (p_rev, pn_rev, pn_rev_max, |
---|
| 309 | ART_LINETO, vpath[i1].x + dlx0, vpath[i1].y + dly0); |
---|
| 310 | art_vpath_add_point (p_rev, pn_rev, pn_rev_max, |
---|
| 311 | ART_LINETO, vpath[i1].x + dlx1, vpath[i1].y + dly1); |
---|
| 312 | } |
---|
| 313 | else if (join == ART_PATH_STROKE_JOIN_MITER) |
---|
| 314 | { |
---|
| 315 | art_vpath_add_point (p_rev, pn_rev, pn_rev_max, |
---|
| 316 | ART_LINETO, vpath[i1].x + dmx, vpath[i1].y + dmy); |
---|
| 317 | } |
---|
| 318 | else if (join == ART_PATH_STROKE_JOIN_ROUND) |
---|
| 319 | art_svp_vpath_stroke_arc (p_rev, pn_rev, pn_rev_max, |
---|
| 320 | vpath[i1].x, vpath[i1].y, |
---|
| 321 | dlx0, dly0, |
---|
| 322 | dlx1, dly1, |
---|
| 323 | -line_width, |
---|
| 324 | flatness); |
---|
| 325 | |
---|
| 326 | } |
---|
| 327 | } |
---|
| 328 | |
---|
| 329 | /* caps i1, under the assumption of a vector from i0 */ |
---|
| 330 | static void |
---|
| 331 | render_cap (ArtVpath **p_result, int *pn_result, int *pn_result_max, |
---|
| 332 | ArtVpath *vpath, int i0, int i1, |
---|
| 333 | ArtPathStrokeCapType cap, double line_width, double flatness) |
---|
| 334 | { |
---|
| 335 | double dx0, dy0; |
---|
| 336 | double dlx0, dly0; |
---|
| 337 | double scale; |
---|
| 338 | int n_pts; |
---|
| 339 | int i; |
---|
| 340 | |
---|
| 341 | dx0 = vpath[i1].x - vpath[i0].x; |
---|
| 342 | dy0 = vpath[i1].y - vpath[i0].y; |
---|
| 343 | |
---|
| 344 | /* Set dl[xy]0 to the vector from i0 to i1, rotated counterclockwise |
---|
| 345 | 90 degrees, and scaled to the length of line_width. */ |
---|
| 346 | scale = line_width / sqrt (dx0 * dx0 + dy0 * dy0); |
---|
| 347 | dlx0 = dy0 * scale; |
---|
| 348 | dly0 = -dx0 * scale; |
---|
| 349 | |
---|
| 350 | #ifdef VERBOSE |
---|
| 351 | printf ("cap style = %d\n", cap); |
---|
| 352 | #endif |
---|
| 353 | |
---|
| 354 | switch (cap) |
---|
| 355 | { |
---|
| 356 | case ART_PATH_STROKE_CAP_BUTT: |
---|
| 357 | art_vpath_add_point (p_result, pn_result, pn_result_max, |
---|
| 358 | ART_LINETO, vpath[i1].x - dlx0, vpath[i1].y - dly0); |
---|
| 359 | art_vpath_add_point (p_result, pn_result, pn_result_max, |
---|
| 360 | ART_LINETO, vpath[i1].x + dlx0, vpath[i1].y + dly0); |
---|
| 361 | break; |
---|
| 362 | case ART_PATH_STROKE_CAP_ROUND: |
---|
| 363 | n_pts = ceil (M_PI / (2.0 * M_SQRT2 * sqrt (flatness / line_width))); |
---|
| 364 | art_vpath_add_point (p_result, pn_result, pn_result_max, |
---|
| 365 | ART_LINETO, vpath[i1].x - dlx0, vpath[i1].y - dly0); |
---|
| 366 | for (i = 1; i < n_pts; i++) |
---|
| 367 | { |
---|
| 368 | double theta, c_th, s_th; |
---|
| 369 | |
---|
| 370 | theta = M_PI * i / n_pts; |
---|
| 371 | c_th = cos (theta); |
---|
| 372 | s_th = sin (theta); |
---|
| 373 | art_vpath_add_point (p_result, pn_result, pn_result_max, |
---|
| 374 | ART_LINETO, |
---|
| 375 | vpath[i1].x - dlx0 * c_th - dly0 * s_th, |
---|
| 376 | vpath[i1].y - dly0 * c_th + dlx0 * s_th); |
---|
| 377 | } |
---|
| 378 | art_vpath_add_point (p_result, pn_result, pn_result_max, |
---|
| 379 | ART_LINETO, vpath[i1].x + dlx0, vpath[i1].y + dly0); |
---|
| 380 | break; |
---|
| 381 | case ART_PATH_STROKE_CAP_SQUARE: |
---|
| 382 | art_vpath_add_point (p_result, pn_result, pn_result_max, |
---|
| 383 | ART_LINETO, |
---|
| 384 | vpath[i1].x - dlx0 - dly0, |
---|
| 385 | vpath[i1].y - dly0 + dlx0); |
---|
| 386 | art_vpath_add_point (p_result, pn_result, pn_result_max, |
---|
| 387 | ART_LINETO, |
---|
| 388 | vpath[i1].x + dlx0 - dly0, |
---|
| 389 | vpath[i1].y + dly0 + dlx0); |
---|
| 390 | break; |
---|
| 391 | } |
---|
| 392 | } |
---|
| 393 | |
---|
| 394 | /** |
---|
| 395 | * art_svp_from_vpath_raw: Stroke a vector path, raw version |
---|
| 396 | * @vpath: #ArtVPath to stroke. |
---|
| 397 | * @join: Join style. |
---|
| 398 | * @cap: Cap style. |
---|
| 399 | * @line_width: Width of stroke. |
---|
| 400 | * @miter_limit: Miter limit. |
---|
| 401 | * @flatness: Flatness. |
---|
| 402 | * |
---|
| 403 | * Exactly the same as art_svp_vpath_stroke(), except that the resulting |
---|
| 404 | * stroke outline may self-intersect and have regions of winding number |
---|
| 405 | * greater than 1. |
---|
| 406 | * |
---|
| 407 | * Return value: Resulting raw stroked outline in svp format. |
---|
| 408 | **/ |
---|
| 409 | ArtVpath * |
---|
| 410 | art_svp_vpath_stroke_raw (ArtVpath *vpath, |
---|
| 411 | ArtPathStrokeJoinType join, |
---|
| 412 | ArtPathStrokeCapType cap, |
---|
| 413 | double line_width, |
---|
| 414 | double miter_limit, |
---|
| 415 | double flatness) |
---|
| 416 | { |
---|
| 417 | int begin_idx, end_idx; |
---|
| 418 | int i; |
---|
| 419 | ArtVpath *forw, *rev; |
---|
| 420 | int n_forw, n_rev; |
---|
| 421 | int n_forw_max, n_rev_max; |
---|
| 422 | ArtVpath *result; |
---|
| 423 | int n_result, n_result_max; |
---|
| 424 | double half_lw = 0.5 * line_width; |
---|
| 425 | int closed; |
---|
| 426 | int last, this, next, second; |
---|
| 427 | double dx, dy; |
---|
| 428 | |
---|
| 429 | n_forw_max = 16; |
---|
| 430 | forw = art_new (ArtVpath, n_forw_max); |
---|
| 431 | |
---|
| 432 | n_rev_max = 16; |
---|
| 433 | rev = art_new (ArtVpath, n_rev_max); |
---|
| 434 | |
---|
| 435 | n_result = 0; |
---|
| 436 | n_result_max = 16; |
---|
| 437 | result = art_new (ArtVpath, n_result_max); |
---|
| 438 | |
---|
| 439 | for (begin_idx = 0; vpath[begin_idx].code != ART_END; begin_idx = end_idx) |
---|
| 440 | { |
---|
| 441 | n_forw = 0; |
---|
| 442 | n_rev = 0; |
---|
| 443 | |
---|
| 444 | closed = (vpath[begin_idx].code == ART_MOVETO); |
---|
| 445 | |
---|
| 446 | /* we don't know what the first point joins with until we get to the |
---|
| 447 | last point and see if it's closed. So we start with the second |
---|
| 448 | line in the path. |
---|
| 449 | |
---|
| 450 | Note: this is not strictly true (we now know it's closed from |
---|
| 451 | the opening pathcode), but why fix code that isn't broken? |
---|
| 452 | */ |
---|
| 453 | |
---|
| 454 | this = begin_idx; |
---|
| 455 | /* skip over identical points at the beginning of the subpath */ |
---|
| 456 | for (i = this + 1; vpath[i].code == ART_LINETO; i++) |
---|
| 457 | { |
---|
| 458 | dx = vpath[i].x - vpath[this].x; |
---|
| 459 | dy = vpath[i].y - vpath[this].y; |
---|
| 460 | if (dx * dx + dy * dy > EPSILON_2) |
---|
| 461 | break; |
---|
| 462 | } |
---|
| 463 | next = i; |
---|
| 464 | second = next; |
---|
| 465 | |
---|
| 466 | /* invariant: this doesn't coincide with next */ |
---|
| 467 | while (vpath[next].code == ART_LINETO) |
---|
| 468 | { |
---|
| 469 | last = this; |
---|
| 470 | this = next; |
---|
| 471 | /* skip over identical points after the beginning of the subpath */ |
---|
| 472 | for (i = this + 1; vpath[i].code == ART_LINETO; i++) |
---|
| 473 | { |
---|
| 474 | dx = vpath[i].x - vpath[this].x; |
---|
| 475 | dy = vpath[i].y - vpath[this].y; |
---|
| 476 | if (dx * dx + dy * dy > EPSILON_2) |
---|
| 477 | break; |
---|
| 478 | } |
---|
| 479 | next = i; |
---|
| 480 | if (vpath[next].code != ART_LINETO) |
---|
| 481 | { |
---|
| 482 | /* reached end of path */ |
---|
| 483 | /* make "closed" detection conform to PostScript |
---|
| 484 | semantics (i.e. explicit closepath code rather than |
---|
| 485 | just the fact that end of the path is the beginning) */ |
---|
| 486 | if (closed && |
---|
| 487 | vpath[this].x == vpath[begin_idx].x && |
---|
| 488 | vpath[this].y == vpath[begin_idx].y) |
---|
| 489 | { |
---|
| 490 | int j; |
---|
| 491 | |
---|
| 492 | /* path is closed, render join to beginning */ |
---|
| 493 | render_seg (&forw, &n_forw, &n_forw_max, |
---|
| 494 | &rev, &n_rev, &n_rev_max, |
---|
| 495 | vpath, last, this, second, |
---|
| 496 | join, half_lw, miter_limit, flatness); |
---|
| 497 | |
---|
| 498 | #ifdef VERBOSE |
---|
| 499 | printf ("%% forw %d, rev %d\n", n_forw, n_rev); |
---|
| 500 | #endif |
---|
| 501 | /* do forward path */ |
---|
| 502 | art_vpath_add_point (&result, &n_result, &n_result_max, |
---|
| 503 | ART_MOVETO, forw[n_forw - 1].x, |
---|
| 504 | forw[n_forw - 1].y); |
---|
| 505 | for (j = 0; j < n_forw; j++) |
---|
| 506 | art_vpath_add_point (&result, &n_result, &n_result_max, |
---|
| 507 | ART_LINETO, forw[j].x, |
---|
| 508 | forw[j].y); |
---|
| 509 | |
---|
| 510 | /* do reverse path, reversed */ |
---|
| 511 | art_vpath_add_point (&result, &n_result, &n_result_max, |
---|
| 512 | ART_MOVETO, rev[0].x, |
---|
| 513 | rev[0].y); |
---|
| 514 | for (j = n_rev - 1; j >= 0; j--) |
---|
| 515 | art_vpath_add_point (&result, &n_result, &n_result_max, |
---|
| 516 | ART_LINETO, rev[j].x, |
---|
| 517 | rev[j].y); |
---|
| 518 | } |
---|
| 519 | else |
---|
| 520 | { |
---|
| 521 | /* path is open */ |
---|
| 522 | int j; |
---|
| 523 | |
---|
| 524 | /* add to forw rather than result to ensure that |
---|
| 525 | forw has at least one point. */ |
---|
| 526 | render_cap (&forw, &n_forw, &n_forw_max, |
---|
| 527 | vpath, last, this, |
---|
| 528 | cap, half_lw, flatness); |
---|
| 529 | art_vpath_add_point (&result, &n_result, &n_result_max, |
---|
| 530 | ART_MOVETO, forw[0].x, |
---|
| 531 | forw[0].y); |
---|
| 532 | for (j = 1; j < n_forw; j++) |
---|
| 533 | art_vpath_add_point (&result, &n_result, &n_result_max, |
---|
| 534 | ART_LINETO, forw[j].x, |
---|
| 535 | forw[j].y); |
---|
| 536 | for (j = n_rev - 1; j >= 0; j--) |
---|
| 537 | art_vpath_add_point (&result, &n_result, &n_result_max, |
---|
| 538 | ART_LINETO, rev[j].x, |
---|
| 539 | rev[j].y); |
---|
| 540 | render_cap (&result, &n_result, &n_result_max, |
---|
| 541 | vpath, second, begin_idx, |
---|
| 542 | cap, half_lw, flatness); |
---|
| 543 | art_vpath_add_point (&result, &n_result, &n_result_max, |
---|
| 544 | ART_LINETO, forw[0].x, |
---|
| 545 | forw[0].y); |
---|
| 546 | } |
---|
| 547 | } |
---|
| 548 | else |
---|
| 549 | render_seg (&forw, &n_forw, &n_forw_max, |
---|
| 550 | &rev, &n_rev, &n_rev_max, |
---|
| 551 | vpath, last, this, next, |
---|
| 552 | join, half_lw, miter_limit, flatness); |
---|
| 553 | } |
---|
| 554 | end_idx = next; |
---|
| 555 | } |
---|
| 556 | |
---|
| 557 | art_free (forw); |
---|
| 558 | art_free (rev); |
---|
| 559 | #ifdef VERBOSE |
---|
| 560 | printf ("%% n_result = %d\n", n_result); |
---|
| 561 | #endif |
---|
| 562 | art_vpath_add_point (&result, &n_result, &n_result_max, ART_END, 0, 0); |
---|
| 563 | return result; |
---|
| 564 | } |
---|
| 565 | |
---|
| 566 | #define noVERBOSE |
---|
| 567 | |
---|
| 568 | #ifdef VERBOSE |
---|
| 569 | |
---|
| 570 | #define XOFF 50 |
---|
| 571 | #define YOFF 700 |
---|
| 572 | |
---|
| 573 | static void |
---|
| 574 | print_ps_vpath (ArtVpath *vpath) |
---|
| 575 | { |
---|
| 576 | int i; |
---|
| 577 | |
---|
| 578 | for (i = 0; vpath[i].code != ART_END; i++) |
---|
| 579 | { |
---|
| 580 | switch (vpath[i].code) |
---|
| 581 | { |
---|
| 582 | case ART_MOVETO: |
---|
| 583 | printf ("%g %g moveto\n", XOFF + vpath[i].x, YOFF - vpath[i].y); |
---|
| 584 | break; |
---|
| 585 | case ART_LINETO: |
---|
| 586 | printf ("%g %g lineto\n", XOFF + vpath[i].x, YOFF - vpath[i].y); |
---|
| 587 | break; |
---|
| 588 | default: |
---|
| 589 | break; |
---|
| 590 | } |
---|
| 591 | } |
---|
| 592 | printf ("stroke showpage\n"); |
---|
| 593 | } |
---|
| 594 | |
---|
| 595 | static void |
---|
| 596 | print_ps_svp (ArtSVP *vpath) |
---|
| 597 | { |
---|
| 598 | int i, j; |
---|
| 599 | |
---|
| 600 | printf ("%% begin\n"); |
---|
| 601 | for (i = 0; i < vpath->n_segs; i++) |
---|
| 602 | { |
---|
| 603 | printf ("%g setgray\n", vpath->segs[i].dir ? 0.7 : 0); |
---|
| 604 | for (j = 0; j < vpath->segs[i].n_points; j++) |
---|
| 605 | { |
---|
| 606 | printf ("%g %g %s\n", |
---|
| 607 | XOFF + vpath->segs[i].points[j].x, |
---|
| 608 | YOFF - vpath->segs[i].points[j].y, |
---|
| 609 | j ? "lineto" : "moveto"); |
---|
| 610 | } |
---|
| 611 | printf ("stroke\n"); |
---|
| 612 | } |
---|
| 613 | |
---|
| 614 | printf ("showpage\n"); |
---|
| 615 | } |
---|
| 616 | #endif |
---|
| 617 | |
---|
| 618 | /* Render a vector path into a stroked outline. |
---|
| 619 | |
---|
| 620 | Status of this routine: |
---|
| 621 | |
---|
| 622 | Basic correctness: Only miter and bevel line joins are implemented, |
---|
| 623 | and only butt line caps. Otherwise, seems to be fine. |
---|
| 624 | |
---|
| 625 | Numerical stability: We cheat (adding random perturbation). Thus, |
---|
| 626 | it seems very likely that no numerical stability problems will be |
---|
| 627 | seen in practice. |
---|
| 628 | |
---|
| 629 | Speed: Should be pretty good. |
---|
| 630 | |
---|
| 631 | Precision: The perturbation fuzzes the coordinates slightly, |
---|
| 632 | but not enough to be visible. */ |
---|
| 633 | /** |
---|
| 634 | * art_svp_vpath_stroke: Stroke a vector path. |
---|
| 635 | * @vpath: #ArtVPath to stroke. |
---|
| 636 | * @join: Join style. |
---|
| 637 | * @cap: Cap style. |
---|
| 638 | * @line_width: Width of stroke. |
---|
| 639 | * @miter_limit: Miter limit. |
---|
| 640 | * @flatness: Flatness. |
---|
| 641 | * |
---|
| 642 | * Computes an svp representing the stroked outline of @vpath. The |
---|
| 643 | * width of the stroked line is @line_width. |
---|
| 644 | * |
---|
| 645 | * Lines are joined according to the @join rule. Possible values are |
---|
| 646 | * ART_PATH_STROKE_JOIN_MITER (for mitered joins), |
---|
| 647 | * ART_PATH_STROKE_JOIN_ROUND (for round joins), and |
---|
| 648 | * ART_PATH_STROKE_JOIN_BEVEL (for bevelled joins). The mitered join |
---|
| 649 | * is converted to a bevelled join if the miter would extend to a |
---|
| 650 | * distance of more than @miter_limit * @line_width from the actual |
---|
| 651 | * join point. |
---|
| 652 | * |
---|
| 653 | * If there are open subpaths, the ends of these subpaths are capped |
---|
| 654 | * according to the @cap rule. Possible values are |
---|
| 655 | * ART_PATH_STROKE_CAP_BUTT (squared cap, extends exactly to end |
---|
| 656 | * point), ART_PATH_STROKE_CAP_ROUND (rounded half-circle centered at |
---|
| 657 | * the end point), and ART_PATH_STROKE_CAP_SQUARE (squared cap, |
---|
| 658 | * extending half @line_width past the end point). |
---|
| 659 | * |
---|
| 660 | * The @flatness parameter controls the accuracy of the rendering. It |
---|
| 661 | * is most important for determining the number of points to use to |
---|
| 662 | * approximate circular arcs for round lines and joins. In general, the |
---|
| 663 | * resulting vector path will be within @flatness pixels of the "ideal" |
---|
| 664 | * path containing actual circular arcs. I reserve the right to use |
---|
| 665 | * the @flatness parameter to convert bevelled joins to miters for very |
---|
| 666 | * small turn angles, as this would reduce the number of points in the |
---|
| 667 | * resulting outline path. |
---|
| 668 | * |
---|
| 669 | * The resulting path is "clean" with respect to self-intersections, i.e. |
---|
| 670 | * the winding number is 0 or 1 at each point. |
---|
| 671 | * |
---|
| 672 | * Return value: Resulting stroked outline in svp format. |
---|
| 673 | **/ |
---|
| 674 | ArtSVP * |
---|
| 675 | art_svp_vpath_stroke (ArtVpath *vpath, |
---|
| 676 | ArtPathStrokeJoinType join, |
---|
| 677 | ArtPathStrokeCapType cap, |
---|
| 678 | double line_width, |
---|
| 679 | double miter_limit, |
---|
| 680 | double flatness) |
---|
| 681 | { |
---|
| 682 | #ifdef ART_USE_NEW_INTERSECTOR |
---|
| 683 | ArtVpath *vpath_stroke; |
---|
| 684 | ArtSVP *svp, *svp2; |
---|
| 685 | ArtSvpWriter *swr; |
---|
| 686 | |
---|
| 687 | vpath_stroke = art_svp_vpath_stroke_raw (vpath, join, cap, |
---|
| 688 | line_width, miter_limit, flatness); |
---|
| 689 | #ifdef VERBOSE |
---|
| 690 | print_ps_vpath (vpath_stroke); |
---|
| 691 | #endif |
---|
| 692 | svp = art_svp_from_vpath (vpath_stroke); |
---|
| 693 | #ifdef VERBOSE |
---|
| 694 | print_ps_svp (svp); |
---|
| 695 | #endif |
---|
| 696 | art_free (vpath_stroke); |
---|
| 697 | |
---|
| 698 | swr = art_svp_writer_rewind_new (ART_WIND_RULE_NONZERO); |
---|
| 699 | art_svp_intersector (svp, swr); |
---|
| 700 | |
---|
| 701 | svp2 = art_svp_writer_rewind_reap (swr); |
---|
| 702 | #ifdef VERBOSE |
---|
| 703 | print_ps_svp (svp2); |
---|
| 704 | #endif |
---|
| 705 | art_svp_free (svp); |
---|
| 706 | return svp2; |
---|
| 707 | #else |
---|
| 708 | ArtVpath *vpath_stroke, *vpath2; |
---|
| 709 | ArtSVP *svp, *svp2, *svp3; |
---|
| 710 | |
---|
| 711 | vpath_stroke = art_svp_vpath_stroke_raw (vpath, join, cap, |
---|
| 712 | line_width, miter_limit, flatness); |
---|
| 713 | #ifdef VERBOSE |
---|
| 714 | print_ps_vpath (vpath_stroke); |
---|
| 715 | #endif |
---|
| 716 | vpath2 = art_vpath_perturb (vpath_stroke); |
---|
| 717 | #ifdef VERBOSE |
---|
| 718 | print_ps_vpath (vpath2); |
---|
| 719 | #endif |
---|
| 720 | art_free (vpath_stroke); |
---|
| 721 | svp = art_svp_from_vpath (vpath2); |
---|
| 722 | #ifdef VERBOSE |
---|
| 723 | print_ps_svp (svp); |
---|
| 724 | #endif |
---|
| 725 | art_free (vpath2); |
---|
| 726 | svp2 = art_svp_uncross (svp); |
---|
| 727 | #ifdef VERBOSE |
---|
| 728 | print_ps_svp (svp2); |
---|
| 729 | #endif |
---|
| 730 | art_svp_free (svp); |
---|
| 731 | svp3 = art_svp_rewind_uncrossed (svp2, ART_WIND_RULE_NONZERO); |
---|
| 732 | #ifdef VERBOSE |
---|
| 733 | print_ps_svp (svp3); |
---|
| 734 | #endif |
---|
| 735 | art_svp_free (svp2); |
---|
| 736 | |
---|
| 737 | return svp3; |
---|
| 738 | #endif |
---|
| 739 | } |
---|