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