| 1 | /* Copyright (C) 1989, 1992 Aladdin Enterprises. All rights reserved. |
| 2 | Distributed by Free Software Foundation, Inc. |
| 3 | |
| 4 | This file is part of Ghostscript. |
| 5 | |
| 6 | Ghostscript is distributed in the hope that it will be useful, but |
| 7 | WITHOUT ANY WARRANTY. No author or distributor accepts responsibility |
| 8 | to anyone for the consequences of using it or for whether it serves any |
| 9 | particular purpose or works at all, unless he says so in writing. Refer |
| 10 | to the Ghostscript General Public License for full details. |
| 11 | |
| 12 | Everyone is granted permission to copy, modify and redistribute |
| 13 | Ghostscript, but only under the conditions described in the Ghostscript |
| 14 | General Public License. A copy of this license is supposed to have been |
| 15 | given to you along with Ghostscript so you can know your rights and |
| 16 | responsibilities. It should be in a file named COPYING. Among other |
| 17 | things, the copyright notice and this notice must be preserved on all |
| 18 | copies. */ |
| 19 | |
| 20 | /* gspath.c */ |
| 21 | /* Path construction routines for Ghostscript library */ |
| 22 | #include "math_.h" |
| 23 | #include "gx.h" |
| 24 | #include "gserrors.h" |
| 25 | #include "gxfixed.h" |
| 26 | #include "gxmatrix.h" |
| 27 | #include "gxpath.h" |
| 28 | #include "gzstate.h" |
| 29 | |
| 30 | /* Conversion parameters */ |
| 31 | #define degrees_to_radians (M_PI / 180.0) |
| 32 | |
| 33 | /* ------ Miscellaneous ------ */ |
| 34 | |
| 35 | int |
| 36 | gs_newpath(gs_state *pgs) |
| 37 | { gx_path_release(pgs->path); |
| 38 | gx_path_init(pgs->path, &pgs->memory_procs); |
| 39 | return 0; |
| 40 | } |
| 41 | |
| 42 | int |
| 43 | gs_closepath(gs_state *pgs) |
| 44 | { return gx_path_close_subpath(pgs->path); |
| 45 | } |
| 46 | |
| 47 | int |
| 48 | gs_upmergepath(gs_state *pgs) |
| 49 | { return gx_path_add_path(pgs->saved->path, pgs->path); |
| 50 | } |
| 51 | |
| 52 | /* ------ Points and lines ------ */ |
| 53 | |
| 54 | int |
| 55 | gs_currentpoint(const gs_state *pgs, gs_point *ppt) |
| 56 | { gs_fixed_point pt; |
| 57 | int code = gx_path_current_point(pgs->path, &pt); |
| 58 | if ( code < 0 ) return code; |
| 59 | return gs_itransform(pgs, fixed2float(pt.x), fixed2float(pt.y), ppt); |
| 60 | } |
| 61 | |
| 62 | int |
| 63 | gs_moveto(gs_state *pgs, floatp x, floatp y) |
| 64 | { int code; |
| 65 | gs_fixed_point pt; |
| 66 | if ( (code = gs_point_transform2fixed(&pgs->ctm, x, y, &pt)) >= 0 ) |
| 67 | code = gx_path_add_point(pgs->path, pt.x, pt.y); |
| 68 | return code; |
| 69 | } |
| 70 | |
| 71 | int |
| 72 | gs_rmoveto(gs_state *pgs, floatp x, floatp y) |
| 73 | { int code; |
| 74 | gs_fixed_point dpt; |
| 75 | if ( (code = gs_distance_transform2fixed(&pgs->ctm, x, y, &dpt)) >= 0 ) |
| 76 | code = gx_path_add_relative_point(pgs->path, dpt.x, dpt.y); |
| 77 | return code; |
| 78 | } |
| 79 | |
| 80 | int |
| 81 | gs_lineto(gs_state *pgs, floatp x, floatp y) |
| 82 | { int code; |
| 83 | gs_fixed_point pt; |
| 84 | if ( (code = gs_point_transform2fixed(&pgs->ctm, x, y, &pt)) >= 0 ) |
| 85 | code = gx_path_add_line(pgs->path, pt.x, pt.y); |
| 86 | return code; |
| 87 | } |
| 88 | |
| 89 | int |
| 90 | gs_rlineto(gs_state *pgs, floatp x, floatp y) |
| 91 | { gs_fixed_point cpt, dpt; |
| 92 | int code = gx_path_current_point(pgs->path, &cpt); |
| 93 | if ( code < 0 ) return code; |
| 94 | if ( (code = gs_distance_transform2fixed(&pgs->ctm, x, y, &dpt)) >= 0 ) |
| 95 | code = gx_path_add_line(pgs->path, cpt.x + dpt.x, cpt.y + dpt.y); |
| 96 | return code; |
| 97 | } |
| 98 | |
| 99 | /* ------ Arcs ------ */ |
| 100 | |
| 101 | /* Forward declarations */ |
| 102 | private int arc_either(P7(gs_state *, |
| 103 | floatp, floatp, floatp, floatp, floatp, int)); |
| 104 | private int arc_add(P9(gs_state *, |
| 105 | floatp, floatp, floatp, floatp, floatp, floatp, floatp, int)); |
| 106 | |
| 107 | int |
| 108 | gs_arc(gs_state *pgs, |
| 109 | floatp xc, floatp yc, floatp r, floatp ang1, floatp ang2) |
| 110 | { return arc_either(pgs, xc, yc, r, ang1, ang2, 0); |
| 111 | } |
| 112 | |
| 113 | int |
| 114 | gs_arcn(gs_state *pgs, |
| 115 | floatp xc, floatp yc, floatp r, floatp ang1, floatp ang2) |
| 116 | { return arc_either(pgs, xc, yc, r, ang1, ang2, 1); |
| 117 | } |
| 118 | |
| 119 | private int |
| 120 | arc_either(gs_state *pgs, |
| 121 | floatp axc, floatp ayc, floatp arad, floatp aang1, floatp aang2, |
| 122 | int clockwise) |
| 123 | { float ar = arad; |
| 124 | fixed ang1 = float2fixed(aang1), ang2 = float2fixed(aang2), adiff; |
| 125 | float ang1r; |
| 126 | float x0, y0, sin0, cos0; |
| 127 | float x3r, y3r; |
| 128 | int first = 1; |
| 129 | int code; |
| 130 | if ( ar < 0 ) |
| 131 | { ang1 += int2fixed(180); |
| 132 | ang2 += int2fixed(180); |
| 133 | ar = - ar; |
| 134 | } |
| 135 | #define fixed90 int2fixed(90) |
| 136 | #define fixed360 int2fixed(360) |
| 137 | /* Don't reduce the arc by multiples of 360 degrees: */ |
| 138 | /* this could lead to incorrect winding numbers. */ |
| 139 | if ( ang1 != ang2 ) |
| 140 | { if ( clockwise ) |
| 141 | { while ( ang2 >= ang1 ) ang1 += fixed360; |
| 142 | } |
| 143 | else |
| 144 | { while ( ang2 <= ang1 ) ang2 += fixed360; |
| 145 | } |
| 146 | } |
| 147 | ang1r = fixed2float(ang1 % fixed360) * degrees_to_radians; |
| 148 | sin0 = ar * sin(ang1r), cos0 = ar * cos(ang1r); |
| 149 | x0 = axc + cos0, y0 = ayc + sin0; |
| 150 | if ( clockwise ) |
| 151 | { /* Quadrant reduction */ |
| 152 | while ( (adiff = ang2 - ang1) < -fixed90 ) |
| 153 | { float w = sin0; sin0 = -cos0; cos0 = w; |
| 154 | x3r = axc + cos0, y3r = ayc + sin0; |
| 155 | code = arc_add(pgs, ar, x0, y0, x3r, y3r, |
| 156 | (x0 + cos0), |
| 157 | (y0 + sin0), |
| 158 | first); |
| 159 | if ( code < 0 ) return code; |
| 160 | x0 = x3r, y0 = y3r; |
| 161 | ang1 -= fixed90; |
| 162 | first = 0; |
| 163 | } |
| 164 | } |
| 165 | else |
| 166 | { /* Quadrant reduction */ |
| 167 | while ( (adiff = ang2 - ang1) > fixed90 ) |
| 168 | { float w = cos0; cos0 = -sin0; sin0 = w; |
| 169 | x3r = axc + cos0, y3r = ayc + sin0; |
| 170 | code = arc_add(pgs, ar, x0, y0, x3r, y3r, |
| 171 | (x0 + cos0), |
| 172 | (y0 + sin0), |
| 173 | first); |
| 174 | if ( code < 0 ) return code; |
| 175 | x0 = x3r, y0 = y3r; |
| 176 | ang1 += fixed90; |
| 177 | first = 0; |
| 178 | } |
| 179 | } |
| 180 | /* Compute the intersection of the tangents. */ |
| 181 | { double trad = tan(fixed2float(adiff) * (degrees_to_radians / 2)); |
| 182 | float ang2r = fixed2float(ang2) * degrees_to_radians; |
| 183 | code = arc_add(pgs, ar, x0, y0, |
| 184 | (axc + ar * cos(ang2r)), |
| 185 | (ayc + ar * sin(ang2r)), |
| 186 | (x0 - trad * sin0), |
| 187 | (y0 + trad * cos0), |
| 188 | first); |
| 189 | } |
| 190 | return code; |
| 191 | } |
| 192 | |
| 193 | int |
| 194 | gs_arcto(gs_state *pgs, |
| 195 | floatp ax1, floatp ay1, floatp ax2, floatp ay2, floatp arad, |
| 196 | float *retxy) /* float retxy[4] */ |
| 197 | { float xt0, yt0, xt2, yt2; |
| 198 | gs_point up0; |
| 199 | #define ax0 up0.x |
| 200 | #define ay0 up0.y |
| 201 | int code; |
| 202 | if ( arad < 0 ) |
| 203 | return_error(gs_error_undefinedresult); |
| 204 | /* Transform the current point back into user coordinates */ |
| 205 | if ( (code = gs_currentpoint(pgs, &up0)) < 0 ) return code; |
| 206 | { /* Now we have to compute the tangent points. */ |
| 207 | /* Basically, the idea is to compute the tangent */ |
| 208 | /* of the bisector by using tan(x+y) and tan(z/2) */ |
| 209 | /* formulas, without ever using any trig. */ |
| 210 | float dx0 = ax0 - ax1, dy0 = ay0 - ay1; |
| 211 | float dx2 = ax2 - ax1, dy2 = ay2 - ay1; |
| 212 | /* Compute the squared lengths from p1 to p0 and p2. */ |
| 213 | double sql0 = dx0 * dx0 + dy0 * dy0; |
| 214 | double sql2 = dx2 * dx2 + dy2 * dy2; |
| 215 | /* Compute the distance from p1 to the tangent points. */ |
| 216 | /* This is the only hairy part. */ |
| 217 | double num = dy0 * dx2 - dy2 * dx0; |
| 218 | double denom = sqrt(sql0 * sql2) - (dx0 * dx2 + dy0 * dy2); |
| 219 | /* Check for collinear points. */ |
| 220 | if ( fabs(num) < 1.0e-6 || fabs(denom) < 1.0e-6 ) |
| 221 | { gs_fixed_point pt; |
| 222 | code = gs_point_transform2fixed(&pgs->ctm, ax1, ay1, &pt); |
| 223 | if ( code >= 0 ) code = gx_path_add_line(pgs->path, pt.x, pt.y); |
| 224 | xt0 = xt2 = ax1; |
| 225 | yt0 = yt2 = ay1; |
| 226 | } |
| 227 | else /* not collinear */ |
| 228 | { double dist = fabs(arad * num / denom); |
| 229 | double l0 = dist / sqrt(sql0), l2 = dist / sqrt(sql2); |
| 230 | xt0 = ax1 + dx0 * l0; |
| 231 | yt0 = ay1 + dy0 * l0; |
| 232 | xt2 = ax1 + dx2 * l2; |
| 233 | yt2 = ay1 + dy2 * l2; |
| 234 | code = arc_add(pgs, arad, xt0, yt0, xt2, yt2, ax1, ay1, 1); |
| 235 | } |
| 236 | } |
| 237 | if ( retxy != 0 ) |
| 238 | { retxy[0] = xt0; |
| 239 | retxy[1] = yt0; |
| 240 | retxy[2] = xt2; |
| 241 | retxy[3] = yt2; |
| 242 | } |
| 243 | return code; |
| 244 | } |
| 245 | |
| 246 | /* Internal routine for adding an arc to the path. */ |
| 247 | private int |
| 248 | arc_add(gs_state *pgs, |
| 249 | floatp r, floatp x0, floatp y0, floatp x3, floatp y3, floatp xt, floatp yt, |
| 250 | int first) |
| 251 | { gx_path *path = pgs->path; |
| 252 | floatp dx = xt - x0, dy = yt - y0; |
| 253 | floatp fraction; |
| 254 | gs_fixed_point p0, p3, pt, cpt; |
| 255 | int code; |
| 256 | /* Compute the fraction coefficient for the curve. */ |
| 257 | /* See gx_path_add_arc for details. */ |
| 258 | if ( fabs(r) < 1.0e-4 ) /* almost zero radius */ |
| 259 | { fraction = 0.0; |
| 260 | } |
| 261 | else |
| 262 | { double ratio2 = (dx * dx + dy * dy) / (r * r); |
| 263 | fraction = (4.0/3.0) / (1 + sqrt(1 + ratio2)); |
| 264 | } |
| 265 | #ifdef DEBUG |
| 266 | if ( gs_debug['r'] ) |
| 267 | dprintf7("[r]Arc f=%f p0=(%f,%f) pt=(%f,%f) p3=(%f,%f) first=%d\n", |
| 268 | x0, y0, xt, yt, x3, y3, first); |
| 269 | #endif |
| 270 | if ( (code = gs_point_transform2fixed(&pgs->ctm, x0, y0, &p0)) < 0 || |
| 271 | (code = gs_point_transform2fixed(&pgs->ctm, x3, y3, &p3)) < 0 || |
| 272 | (code = gs_point_transform2fixed(&pgs->ctm, xt, yt, &pt)) < 0 || |
| 273 | (first && (code = (gx_path_current_point(path, &cpt) >= 0 ? |
| 274 | gx_path_add_line(path, p0.x, p0.y) : |
| 275 | gx_path_add_point(path, p0.x, p0.y))) < 0) |
| 276 | ) |
| 277 | return code; |
| 278 | return gx_path_add_arc(path, p0.x, p0.y, p3.x, p3.y, pt.x, pt.y, fraction); |
| 279 | } |
| 280 | |
| 281 | /* ------ Curves ------ */ |
| 282 | |
| 283 | int |
| 284 | gs_curveto(gs_state *pgs, |
| 285 | floatp x1, floatp y1, floatp x2, floatp y2, floatp x3, floatp y3) |
| 286 | { gs_fixed_point p1, p2, p3; |
| 287 | int code; |
| 288 | if ( (code = gs_point_transform2fixed(&pgs->ctm, x1, y1, &p1)) < 0 || |
| 289 | (code = gs_point_transform2fixed(&pgs->ctm, x2, y2, &p2)) < 0 || |
| 290 | (code = gs_point_transform2fixed(&pgs->ctm, x3, y3, &p3)) < 0 |
| 291 | ) return code; |
| 292 | return gx_path_add_curve(pgs->path, |
| 293 | p1.x, p1.y, p2.x, p2.y, p3.x, p3.y); |
| 294 | } |
| 295 | |
| 296 | int |
| 297 | gs_rcurveto(gs_state *pgs, |
| 298 | floatp dx1, floatp dy1, floatp dx2, floatp dy2, floatp dx3, floatp dy3) |
| 299 | { gs_fixed_point pt, p1, p2, p3; |
| 300 | int code = gx_path_current_point(pgs->path, &pt); |
| 301 | if ( code < 0 ) return code; |
| 302 | if ( (code = gs_distance_transform2fixed(&pgs->ctm, dx1, dy1, &p1)) < 0 || |
| 303 | (code = gs_distance_transform2fixed(&pgs->ctm, dx2, dy2, &p2)) < 0 || |
| 304 | (code = gs_distance_transform2fixed(&pgs->ctm, dx3, dy3, &p3)) < 0 |
| 305 | ) return code; |
| 306 | return gx_path_add_curve(pgs->path, |
| 307 | pt.x + p1.x, pt.y + p1.y, |
| 308 | pt.x + p2.x, pt.y + p2.y, |
| 309 | pt.x + p3.x, pt.y + p3.y); |
| 310 | } |