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