xref: /plan9/sys/src/cmd/gs/src/gzpath.h (revision 593dc095aefb2a85c828727bbfa9da139a49bdf4)
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