1 /* Copyright (C) 2001-2019 Artifex Software, Inc. 2 All Rights Reserved. 3 4 This software is provided AS-IS with no warranty, either express or 5 implied. 6 7 This software is distributed under license and may not be copied, 8 modified or distributed except as expressly authorized under the terms 9 of the license contained in the file LICENSE in this distribution. 10 11 Refer to licensing information at http://www.artifex.com or contact 12 Artifex Software, Inc., 1305 Grant Avenue - Suite 200, Novato, 13 CA 94945, U.S.A., +1(415)492-9861, for further information. 14 */ 15 16 17 /* Structure and internal procedure definitions for paths */ 18 /* Requires gxfixed.h */ 19 20 #ifndef gzpath_INCLUDED 21 # define gzpath_INCLUDED 22 23 #include "gxpath.h" 24 #include "gsmatrix.h" 25 #include "gsrefct.h" 26 #include "gsstype.h" /* for extern_st */ 27 28 /* 29 * Paths are represented as a linked list of line or curve segments, 30 * similar to what pathforall reports. 31 */ 32 33 /* 34 * Define path segment types: segment start, line, or Bezier curve. 35 * We have a special type for the line added by closepath. 36 */ 37 typedef enum { 38 s_start, 39 s_line, 40 s_line_close, 41 s_curve, 42 s_dash, /* only for internal use of the stroking algorithm */ 43 s_gap 44 } segment_type; 45 46 /* Define the common structure for all segments. */ 47 #define segment_common\ 48 segment *prev;\ 49 segment *next;\ 50 ushort /*segment_type*/ type;\ 51 ushort /*segment_notes*/ notes;\ 52 gs_fixed_point pt; /* initial point for starts, */\ 53 /* final point for others */ 54 55 /* Forward declarations for structure types */ 56 typedef struct segment_s segment; 57 58 typedef struct subpath_s subpath; 59 60 /* 61 * Define a generic segment. This is never instantiated, 62 * but we define a descriptor anyway for the benefit of subclasses. 63 */ 64 struct segment_s { 65 segment_common 66 }; 67 68 #define private_st_segment() /* in gxpath.c */\ 69 gs_private_st_ptrs2(st_segment, struct segment_s, "segment",\ 70 segment_enum_ptrs, segment_reloc_ptrs, prev, next) 71 72 /* Line segments have no special data. */ 73 typedef struct { 74 segment_common 75 } line_segment; 76 77 #define private_st_line() /* in gxpath.c */\ 78 gs_private_st_suffix_add0(st_line, line_segment, "line",\ 79 line_enum_ptrs, line_reloc_ptrs, st_segment) 80 81 /* Dash segments (only for internal use of the stroking algorithm). */ 82 typedef struct { 83 segment_common 84 gs_fixed_point tangent; 85 } dash_segment; 86 87 #define private_st_dash() /* in gxpath.c */\ 88 gs_private_st_suffix_add0(st_dash, dash_segment, "dash",\ 89 dash_enum_ptrs, dash_reloc_ptrs, st_segment) 90 91 /* Line_close segments are for the lines appended by closepath. */ 92 /* They point back to the subpath being closed. */ 93 typedef struct { 94 segment_common 95 subpath * sub; 96 } line_close_segment; 97 98 #define private_st_line_close() /* in gxpath.c */\ 99 gs_private_st_suffix_add1(st_line_close, line_close_segment, "close",\ 100 close_enum_ptrs, close_reloc_ptrs, st_segment, sub) 101 102 /* 103 * We use two different representations for curve segments: one defined by 104 * two endpoints (p0, p3) and two control points (p1, p2), and one defined 105 * by two sets of parametric cubic coefficients (ax ... dy). Here is how 106 * they are related (v = x or y). We spell out some multiplies by 3 for 107 * the benefit of compilers too simple to optimize this. 108 */ 109 #define curve_points_to_coefficients(v0, v1, v2, v3, a, b, c, t01, t12)\ 110 (/*d = (v0),*/\ 111 t01 = (v1) - (v0), c = (t01 << 1) + t01,\ 112 t12 = (v2) - (v1), b = (t12 << 1) + t12 - c,\ 113 a = (v3) - b - c - (v0)) 114 /* 115 * or conversely 116 */ 117 #define curve_coefficients_to_points(a, b, c, d, v1, v2, v3)\ 118 (/*v0 = (d),*/\ 119 v1 = (d) + ((c) / 3),\ 120 v2 = v1 + (((b) + (c)) / 3),\ 121 v3 = (a) + (b) + (c) + (d)) 122 123 /* Curve segments store the control points. */ 124 typedef struct { 125 segment_common 126 gs_fixed_point p1, p2; 127 } curve_segment; 128 129 #define private_st_curve() /* in gxpath.c */\ 130 gs_private_st_suffix_add0_local(st_curve, curve_segment, "curve",\ 131 segment_enum_ptrs, segment_reloc_ptrs, st_segment) 132 133 /* 134 * Define a start segment. This serves as the head of a subpath. 135 * The closer is only used temporarily when filling, 136 * to close an open subpath. 137 */ 138 struct subpath_s { 139 segment_common 140 segment * last; /* last segment of subpath, */ 141 /* points back to here if empty */ 142 int curve_count; /* # of curves */ 143 line_close_segment closer; 144 char /*bool */ is_closed; /* true if subpath is closed */ 145 }; 146 147 #define private_st_subpath() /* in gxpath.c */\ 148 gs_private_st_suffix_add1(st_subpath, subpath, "subpath",\ 149 subpath_enum_ptrs, subpath_reloc_ptrs, st_segment, last) 150 151 /* Test whether a subpath is a rectangle; if so, also return */ 152 /* the start of the next subpath. */ 153 gx_path_rectangular_type 154 gx_subpath_is_rectangular(const subpath * pstart, gs_fixed_rect * pbox, 155 const subpath ** ppnext); 156 157 #define gx_subpath_is_rectangle(pstart, pbox, ppnext)\ 158 (gx_subpath_is_rectangular(pstart, pbox, ppnext) != prt_none) 159 160 /* Curve manipulation */ 161 162 /* Return the smallest value k such that 2^k segments will approximate */ 163 /* the curve to within the desired flatness. */ 164 int gx_curve_log2_samples(fixed, fixed, const curve_segment *, fixed); 165 166 /* 167 * If necessary, find the values of t (never more than 2) which split the 168 * curve into monotonic parts. Return the number of split points. 169 */ 170 int gx_curve_monotonic_points(fixed, fixed, fixed, fixed, double[2]); 171 172 /* Monotonize a curve, by splitting it if necessary. */ 173 int gx_curve_monotonize(gx_path * ppath, const curve_segment * pc); 174 175 /* Flatten a partial curve by sampling (internal procedure). */ 176 int gx_subdivide_curve(gx_path *, int, curve_segment *, segment_notes); 177 /* 178 * Define the maximum number of points for sampling if we want accurate 179 * rasterizing. 2^(k_sample_max*3)-1 must fit into a uint with a bit 180 * to spare; also, we must be able to compute 1/2^(3*k) by table lookup. 181 */ 182 #define k_sample_max min((size_of(int) * 8 - 1) / 3, 10) 183 184 /* 185 * The path state flags reflect the most recent operation on the path 186 * as follows: 187 * Operation position_valid subpath_open is_drawing 188 * newpath no no no 189 * moveto yes yes no 190 * lineto/curveto yes yes yes 191 * closepath yes no no 192 * If position_valid is true, outside_range reflects whether the most 193 * recent operation went outside of the representable coordinate range. 194 * If this is the case, the corresponding member of position (x and/or y) 195 * is min_fixed or max_fixed, and outside_position is the true position. 196 */ 197 /* 198 */ 199 typedef enum { 200 /* Individual flags. These may be or'ed together, per above. */ 201 psf_position_valid = 1, 202 psf_subpath_open = 2, 203 psf_is_drawing = 4, 204 psf_outside_range = 8, 205 /* Values stored by path building operations. */ 206 psf_last_newpath = 0, 207 psf_last_moveto = psf_position_valid | psf_subpath_open, 208 psf_last_draw = psf_position_valid | psf_subpath_open | psf_is_drawing, 209 psf_last_closepath = psf_position_valid 210 } gx_path_state_flags; 211 212 /* 213 * Individual tests 214 */ 215 #define path_position_valid(ppath)\ 216 (((ppath)->state_flags & psf_position_valid) != 0) 217 #define path_subpath_open(ppath)\ 218 (((ppath)->state_flags & psf_subpath_open) != 0) 219 #define path_is_drawing(ppath)\ 220 (((ppath)->state_flags & psf_is_drawing) != 0) 221 #define path_outside_range(ppath)\ 222 (((ppath)->state_flags & psf_outside_range) != 0) 223 /* 224 * Composite tests 225 */ 226 #define path_last_is_moveto(ppath)\ 227 (((ppath)->state_flags & ~psf_outside_range) == psf_last_moveto) 228 #define path_position_in_range(ppath)\ 229 (((ppath)->state_flags & (psf_position_valid + psf_outside_range)) ==\ 230 psf_position_valid) 231 #define path_start_outside_range(ppath)\ 232 ((ppath)->state_flags != 0 &&\ 233 ((ppath)->start_flags & psf_outside_range) != 0) 234 /* 235 * Updating operations 236 */ 237 #define path_update_newpath(ppath)\ 238 ((ppath)->state_flags = psf_last_newpath) 239 #define path_update_moveto(ppath)\ 240 ((ppath)->state_flags = (ppath)->start_flags = psf_last_moveto) 241 #define path_update_draw(ppath)\ 242 ((ppath)->state_flags = psf_last_draw) 243 #define path_update_closepath(ppath)\ 244 ((ppath)->state_flags = psf_last_closepath) 245 246 /* 247 * In order to be able to reclaim path segments at the right time, we need 248 * to reference-count them. To minimize disruption, we would like to do 249 * this by creating a structure (gx_path_segments) consisting of only a 250 * reference count that counts the number of paths that share the same 251 * segments. (Logically, we should put the segments themselves -- 252 * first/last_subpath, subpath/curve_count -- in this object, but that would 253 * cause too much disruption to existing code.) However, we need to put at 254 * least first_subpath and current_subpath in this structure so that we can 255 * free the segments when the reference count becomes zero. 256 */ 257 typedef struct gx_path_segments_s { 258 rc_header rc; 259 struct psc_ { 260 subpath *subpath_first; 261 subpath *subpath_current; 262 } contents; 263 } gx_path_segments; 264 265 #define private_st_path_segments() /* in gxpath.c */\ 266 gs_private_st_ptrs2(st_path_segments, gx_path_segments, "path segments",\ 267 path_segments_enum_ptrs, path_segments_reloc_ptrs,\ 268 contents.subpath_first, contents.subpath_current) 269 270 /* Record how a path was allocated, so freeing will do the right thing. */ 271 typedef enum { 272 path_allocated_on_stack, /* on stack */ 273 path_allocated_contained, /* inside another object */ 274 path_allocated_on_heap /* on the heap */ 275 } gx_path_allocation_t; 276 277 /* 278 * Define virtual path interface functions. 279 * This is a minimal set of functions required by 280 * Type 1,2, TrueType interpreters. 281 */ 282 typedef struct gx_path_procs_s { 283 int (*add_point)(gx_path *, fixed, fixed); 284 int (*add_line)(gx_path *, fixed, fixed, segment_notes); 285 int (*add_gap)(gx_path *, fixed, fixed, segment_notes); 286 int (*add_curve)(gx_path *, fixed, fixed, fixed, fixed, fixed, fixed, segment_notes); 287 int (*close_subpath)(gx_path *, segment_notes); 288 byte (*state_flags)(gx_path *, byte); 289 } gx_path_procs; 290 291 /* Here is the actual structure of a path. */ 292 struct gx_path_s { 293 /* 294 * In order to be able to have temporary paths allocated entirely 295 * on the stack, we include a segments structure within the path, 296 * used only for this purpose. In order to avoid having the 297 * path's segments pointer point into the middle of an object, 298 * the segments structure must come first. 299 * 300 * Note that since local_segments is used only for temporary paths 301 * on the stack, and not for path structures in allocated memory, 302 * we don't declare any pointers in it for the GC. (As it happens, 303 * there aren't any such pointers at the moment, but this could 304 * change.) 305 */ 306 gx_path_segments local_segments; 307 gs_memory_t *memory; 308 gx_path_allocation_t allocation; /* how this path was allocated */ 309 gx_path_segments *segments; 310 segment *last_charpath_segment; /* Used only by pdfwrite at present, 311 * last segment added by a charpath operation 312 */ 313 gs_fixed_rect bbox; /* bounding box (in device space) */ 314 segment *box_last; /* bbox incorporates segments */ 315 /* up to & including this one */ 316 #define first_subpath segments->contents.subpath_first /* (hack) */ 317 #define current_subpath segments->contents.subpath_current /* (ditto) */ 318 /* 319 * Note: because of bugs in the AIX 4.3.1 xlc compiler, the byte-valued 320 * members must not be the last ones in the structure. 321 */ 322 byte /*gx_path_state_flags*/ start_flags; /* flags of moveto */ 323 byte /*gx_path_state_flags*/ state_flags; /* (see above) */ 324 byte /*bool*/ bbox_set; /* true if setbbox is in effect */ 325 byte /*bool*/ bbox_accurate;/* true if bbox is accurate */ 326 int subpath_count; 327 int curve_count; 328 gs_fixed_point position; /* current position */ 329 gx_path_procs *procs; 330 }; 331 332 /* st_path should be static, but it's needed for the clip_path subclass. */ 333 extern_st(st_path); 334 #define public_st_path() /* in gxpath.c */\ 335 gs_public_st_ptrs3(st_path, gx_path, "path",\ 336 path_enum_ptrs, path_reloc_ptrs, segments, box_last, last_charpath_segment) 337 #define st_path_max_ptrs 3 338 339 /* Path enumeration structure */ 340 struct gs_path_enum_s { 341 gs_memory_t *memory; 342 gs_matrix mat; /* CTM for inverse-transforming points */ 343 const segment *pseg; 344 const gx_path *path; /* path being enumerated */ 345 gx_path *copied_path; /* if the path was copied, this is the */ 346 /* the same as path, to be released */ 347 /* when done enumerating */ 348 bool moveto_done; /* have we reported a final moveto yet? */ 349 segment_notes notes; /* notes from most recent segment */ 350 }; 351 352 /* We export st_path_enum only so that st_cpath_enum can subclass it. */ 353 extern_st(st_path_enum); 354 #define public_st_path_enum() /* in gxpath2.c */\ 355 gs_public_st_ptrs3(st_path_enum, gs_path_enum, "gs_path_enum",\ 356 path_enum_enum_ptrs, path_enum_reloc_ptrs, pseg, path, copied_path) 357 358 /* Inline path accessors. */ 359 #define gx_path_has_curves_inline(ppath)\ 360 ((ppath)->curve_count != 0) 361 #define gx_path_has_curves(ppath)\ 362 gx_path_has_curves_inline(ppath) 363 #define gx_path_is_void_inline(ppath)\ 364 ((ppath)->segments != 0 && (ppath)->first_subpath == 0) 365 #define gx_path_is_void(ppath)\ 366 gx_path_is_void_inline(ppath) 367 #define gx_path_subpath_count(ppath)\ 368 ((ppath)->subpath_count) 369 #define gx_path_is_shared(ppath)\ 370 ((ppath)->segments != 0 && (ppath)->segments->rc.ref_count > 1) 371 372 /* Macros equivalent to a few heavily used procedures. */ 373 /* Be aware that these macros may evaluate arguments more than once. */ 374 #define gx_path_current_point_inline(pgs,ppt)\ 375 ( !pgs->current_point_valid ? gs_note_error(gs_error_nocurrentpoint) :\ 376 ((ppt)->x = float2fixed_rounded(pgs->current_point.x), \ 377 (ppt)->y = float2fixed_rounded(pgs->current_point.y), 0) ) 378 379 /* An iterator of flattened segments for a minotonic curve. */ 380 typedef struct gx_flattened_iterator_s gx_flattened_iterator; 381 struct gx_flattened_iterator_s { 382 /* private : */ 383 fixed x0, y0, x3, y3; 384 fixed cx, bx, ax, cy, by, ay; 385 fixed x, y; 386 uint i, k; 387 uint rmask; /* M-1 */ 388 fixed idx, idy, id2x, id2y, id3x, id3y; /* I */ 389 uint rx, ry, rdx, rdy, rd2x, rd2y, rd3x, rd3y; /* R */ 390 /* public : */ 391 bool curve; 392 fixed lx0, ly0, lx1, ly1; 393 }; 394 395 bool gx_flattened_iterator__init(gx_flattened_iterator *this, 396 fixed x0, fixed y0, const curve_segment *pc, int k); 397 bool gx_flattened_iterator__init_line(gx_flattened_iterator *this, 398 fixed x0, fixed y0, fixed x1, fixed y1); 399 void gx_flattened_iterator__switch_to_backscan(gx_flattened_iterator *this, bool not_first); 400 int gx_flattened_iterator__next(gx_flattened_iterator *this); 401 int gx_flattened_iterator__prev(gx_flattened_iterator *this); 402 403 bool curve_coeffs_ranged(fixed x0, fixed x1, fixed x2, fixed x3, 404 fixed y0, fixed y1, fixed y2, fixed y3, 405 fixed *ax, fixed *bx, fixed *cx, 406 fixed *ay, fixed *by, fixed *cy, 407 int k); 408 409 bool gx_check_fixed_diff_overflow(fixed v0, fixed v1); 410 bool gx_check_fixed_sum_overflow(fixed v0, fixed v1); 411 412 #endif /* gzpath_INCLUDED */ 413