1 /* Copyright (C) 1991, 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: gxcpath.c,v 1.16 2005/07/27 22:34:40 igor Exp $ */
18 /* Implementation of clipping paths, other than actual clipping */
19 #include "gx.h"
20 #include "gserrors.h"
21 #include "gsstruct.h"
22 #include "gsutil.h"
23 #include "gsline.h"
24 #include "gxdevice.h"
25 #include "gxfixed.h"
26 #include "gscoord.h" /* needs gsmatrix.h */
27 #include "gxistate.h"
28 #include "gzpath.h"
29 #include "gzcpath.h"
30 #include "gzacpath.h"
31
32 /* Forward references */
33 private void gx_clip_list_from_rectangle(gx_clip_list *, gs_fixed_rect *);
34
35 /* Other structure types */
36 public_st_clip_rect();
37 private_st_clip_list();
38 public_st_clip_path();
39 private_st_clip_rect_list();
40 public_st_device_clip();
41 private_st_cpath_enum();
42 private_st_cpath_path_list();
43
44 /* GC procedures for gx_clip_path */
45 private
46 ENUM_PTRS_WITH(clip_path_enum_ptrs, gx_clip_path *cptr) return ENUM_USING(st_path, &cptr->path, sizeof(cptr->path), index - 2);
47
48 case 0:
49 return ENUM_OBJ((cptr->rect_list == &cptr->local_list ? 0 :
50 cptr->rect_list));
51 case 1:
52 return ENUM_OBJ(cptr->path_list);
53 ENUM_PTRS_END
54 private
RELOC_PTRS_WITH(clip_path_reloc_ptrs,gx_clip_path * cptr)55 RELOC_PTRS_WITH(clip_path_reloc_ptrs, gx_clip_path *cptr)
56 {
57 if (cptr->rect_list != &cptr->local_list)
58 RELOC_VAR(cptr->rect_list);
59 RELOC_VAR(cptr->path_list);
60 RELOC_USING(st_path, &cptr->path, sizeof(gx_path));
61 }
62 RELOC_PTRS_END
63
64 /* GC procedures for gx_device_clip */
65 private
ENUM_PTRS_WITH(device_clip_enum_ptrs,gx_device_clip * cptr)66 ENUM_PTRS_WITH(device_clip_enum_ptrs, gx_device_clip *cptr)
67 {
68 if (index < st_clip_list_max_ptrs + 1)
69 return ENUM_USING(st_clip_list, &cptr->list,
70 sizeof(gx_clip_list), index - 1);
71 return ENUM_USING(st_device_forward, vptr,
72 sizeof(gx_device_forward),
73 index - (st_clip_list_max_ptrs + 1));
74 }
75 case 0:
76 ENUM_RETURN((cptr->current == &cptr->list.single ? NULL :
77 (void *)cptr->current));
78 ENUM_PTRS_END
79 private
RELOC_PTRS_WITH(device_clip_reloc_ptrs,gx_device_clip * cptr)80 RELOC_PTRS_WITH(device_clip_reloc_ptrs, gx_device_clip *cptr)
81 {
82 if (cptr->current == &cptr->list.single)
83 cptr->current = &((gx_device_clip *)RELOC_OBJ(vptr))->list.single;
84 else
85 RELOC_PTR(gx_device_clip, current);
86 RELOC_USING(st_clip_list, &cptr->list, sizeof(gx_clip_list));
87 RELOC_USING(st_device_forward, vptr, sizeof(gx_device_forward));
88 }
89 RELOC_PTRS_END
90
91 /* Define an empty clip list. */
92 private const gx_clip_list clip_list_empty = {
93 {0, 0, min_int, max_int, 0, 0},
94 0, 0, 0, 0, 0
95 };
96
97 /* ------ Clipping path memory management ------ */
98
99 private rc_free_proc(rc_free_cpath_list);
100 private rc_free_proc(rc_free_cpath_list_local);
101 private rc_free_proc(rc_free_cpath_path_list);
102
103 /*
104 * Initialize those parts of the contents of a clip path that aren't
105 * part of the path.
106 */
107 private void
cpath_init_rectangle(gx_clip_path * pcpath,gs_fixed_rect * pbox)108 cpath_init_rectangle(gx_clip_path * pcpath, gs_fixed_rect * pbox)
109 {
110 gx_clip_list_from_rectangle(&pcpath->rect_list->list, pbox);
111 pcpath->inner_box = *pbox;
112 pcpath->path_valid = false;
113 pcpath->path.bbox = *pbox;
114 gx_cpath_set_outer_box(pcpath);
115 pcpath->id = gs_next_ids(pcpath->path.memory, 1); /* path changed => change id */
116 }
117 private void
cpath_init_own_contents(gx_clip_path * pcpath)118 cpath_init_own_contents(gx_clip_path * pcpath)
119 { /* We could make null_rect static, but then it couldn't be const. */
120 gs_fixed_rect null_rect;
121
122 null_rect.p.x = null_rect.p.y = null_rect.q.x = null_rect.q.y = 0;
123 cpath_init_rectangle(pcpath, &null_rect);
124 pcpath->path_list = NULL;
125 }
126 private void
cpath_share_own_contents(gx_clip_path * pcpath,const gx_clip_path * shared)127 cpath_share_own_contents(gx_clip_path * pcpath, const gx_clip_path * shared)
128 {
129 pcpath->inner_box = shared->inner_box;
130 pcpath->path_valid = shared->path_valid;
131 pcpath->outer_box = shared->outer_box;
132 pcpath->id = shared->id;
133 }
134
135 /* Allocate only the segments of a clipping path on the heap. */
136 private int
cpath_alloc_list(gx_clip_rect_list ** prlist,gs_memory_t * mem,client_name_t cname)137 cpath_alloc_list(gx_clip_rect_list ** prlist, gs_memory_t * mem,
138 client_name_t cname)
139 {
140 rc_alloc_struct_1(*prlist, gx_clip_rect_list, &st_clip_rect_list, mem,
141 return_error(gs_error_VMerror), cname);
142 (*prlist)->rc.free = rc_free_cpath_list;
143 return 0;
144 }
145 int
gx_cpath_init_contained_shared(gx_clip_path * pcpath,const gx_clip_path * shared,gs_memory_t * mem,client_name_t cname)146 gx_cpath_init_contained_shared(gx_clip_path * pcpath,
147 const gx_clip_path * shared, gs_memory_t * mem, client_name_t cname)
148 {
149 if (shared) {
150 if (shared->path.segments == &shared->path.local_segments) {
151 lprintf1("Attempt to share (local) segments of clip path 0x%lx!\n",
152 (ulong) shared);
153 return_error(gs_error_Fatal);
154 }
155 *pcpath = *shared;
156 pcpath->path.memory = mem;
157 pcpath->path.allocation = path_allocated_contained;
158 rc_increment(pcpath->path.segments);
159 rc_increment(pcpath->rect_list);
160 rc_increment(pcpath->path_list);
161 } else {
162 int code = cpath_alloc_list(&pcpath->rect_list, mem, cname);
163
164 if (code < 0)
165 return code;
166 code = gx_path_alloc_contained(&pcpath->path, mem, cname);
167 if (code < 0) {
168 gs_free_object(mem, pcpath->rect_list, cname);
169 pcpath->rect_list = 0;
170 return code;
171 }
172 cpath_init_own_contents(pcpath);
173 }
174 return 0;
175 }
176 #define gx_cpath_alloc_contents(pcpath, shared, mem, cname)\
177 gx_cpath_init_contained_shared(pcpath, shared, mem, cname)
178
179 /* Allocate all of a clipping path on the heap. */
180 gx_clip_path *
gx_cpath_alloc_shared(const gx_clip_path * shared,gs_memory_t * mem,client_name_t cname)181 gx_cpath_alloc_shared(const gx_clip_path * shared, gs_memory_t * mem,
182 client_name_t cname)
183 {
184 gx_clip_path *pcpath =
185 gs_alloc_struct(mem, gx_clip_path, &st_clip_path, cname);
186 int code;
187
188 if (pcpath == 0)
189 return 0;
190 code = gx_cpath_alloc_contents(pcpath, shared, mem, cname);
191 if (code < 0) {
192 gs_free_object(mem, pcpath, cname);
193 return 0;
194 }
195 pcpath->path.allocation = path_allocated_on_heap;
196 return pcpath;
197 }
198
199 /* Initialize a stack-allocated clipping path. */
200 int
gx_cpath_init_local_shared(gx_clip_path * pcpath,const gx_clip_path * shared,gs_memory_t * mem)201 gx_cpath_init_local_shared(gx_clip_path * pcpath, const gx_clip_path * shared,
202 gs_memory_t * mem)
203 {
204 if (shared) {
205 if (shared->path.segments == &shared->path.local_segments) {
206 lprintf1("Attempt to share (local) segments of clip path 0x%lx!\n",
207 (ulong) shared);
208 return_error(gs_error_Fatal);
209 }
210 pcpath->path = shared->path;
211 pcpath->path.allocation = path_allocated_on_stack;
212 rc_increment(pcpath->path.segments);
213 pcpath->rect_list = shared->rect_list;
214 rc_increment(pcpath->rect_list);
215 pcpath->path_list = shared->path_list;
216 rc_increment(pcpath->path_list);
217 cpath_share_own_contents(pcpath, shared);
218 } else {
219 gx_path_init_local(&pcpath->path, mem);
220 rc_init_free(&pcpath->local_list, mem, 1, rc_free_cpath_list_local);
221 pcpath->rect_list = &pcpath->local_list;
222 cpath_init_own_contents(pcpath);
223 }
224 return 0;
225 }
226
227 /* Unshare a clipping path. */
228 int
gx_cpath_unshare(gx_clip_path * pcpath)229 gx_cpath_unshare(gx_clip_path * pcpath)
230 {
231 int code = gx_path_unshare(&pcpath->path);
232 gx_clip_rect_list *rlist = pcpath->rect_list;
233
234 if (code < 0)
235 return code;
236 if (rlist->rc.ref_count > 1) {
237 int code = cpath_alloc_list(&pcpath->rect_list, pcpath->path.memory,
238 "gx_cpath_unshare");
239
240 if (code < 0)
241 return code;
242 /* Copy the rectangle list. */
243 /**************** NYI ****************/
244 rc_decrement(rlist, "gx_cpath_unshare");
245 }
246 return code;
247 }
248
249 /* Free a clipping path. */
250 void
gx_cpath_free(gx_clip_path * pcpath,client_name_t cname)251 gx_cpath_free(gx_clip_path * pcpath, client_name_t cname)
252 {
253 rc_decrement(pcpath->rect_list, cname);
254 rc_decrement(pcpath->path_list, cname);
255 /* Clean up pointers for GC. */
256 pcpath->rect_list = 0;
257 pcpath->path_list = 0;
258 {
259 gx_path_allocation_t alloc = pcpath->path.allocation;
260
261 if (alloc == path_allocated_on_heap) {
262 pcpath->path.allocation = path_allocated_contained;
263 gx_path_free(&pcpath->path, cname);
264 gs_free_object(pcpath->path.memory, pcpath, cname);
265 } else
266 gx_path_free(&pcpath->path, cname);
267 }
268 }
269
270 /* Assign a clipping path, preserving the source. */
271 int
gx_cpath_assign_preserve(gx_clip_path * pcpto,gx_clip_path * pcpfrom)272 gx_cpath_assign_preserve(gx_clip_path * pcpto, gx_clip_path * pcpfrom)
273 {
274 int code = gx_path_assign_preserve(&pcpto->path, &pcpfrom->path);
275 gx_clip_rect_list *fromlist = pcpfrom->rect_list;
276 gx_clip_rect_list *tolist = pcpto->rect_list;
277 gx_path path;
278
279 if (code < 0)
280 return 0;
281 if (fromlist == &pcpfrom->local_list) {
282 /* We can't use pcpfrom's list object. */
283 if (tolist == &pcpto->local_list || tolist->rc.ref_count > 1) {
284 /* We can't use pcpto's list either. Allocate a new one. */
285 int code = cpath_alloc_list(&tolist, tolist->rc.memory,
286 "gx_cpath_assign");
287
288 if (code < 0)
289 return code;
290 rc_decrement(pcpto->rect_list, "gx_cpath_assign");
291 } else {
292 /* Use pcpto's list object. */
293 rc_free_cpath_list_local(tolist->rc.memory, tolist,
294 "gx_cpath_assign");
295 }
296 tolist->list = fromlist->list;
297 pcpfrom->rect_list = tolist;
298 rc_increment(tolist);
299 } else {
300 /* We can use pcpfrom's list object. */
301 rc_increment(fromlist);
302 rc_decrement(pcpto->rect_list, "gx_cpath_assign");
303 }
304 rc_increment(pcpfrom->path_list);
305 path = pcpto->path, *pcpto = *pcpfrom, pcpto->path = path;
306 return 0;
307 }
308
309 /* Assign a clipping path, releasing the source. */
310 int
gx_cpath_assign_free(gx_clip_path * pcpto,gx_clip_path * pcpfrom)311 gx_cpath_assign_free(gx_clip_path * pcpto, gx_clip_path * pcpfrom)
312 { /* For right now, just do assign + free. */
313 int code = gx_cpath_assign_preserve(pcpto, pcpfrom);
314
315 if (code < 0)
316 return 0;
317 gx_cpath_free(pcpfrom, "gx_cpath_assign_free");
318 return 0;
319 }
320
321 /* Free the clipping list when its reference count goes to zero. */
322 private void
rc_free_cpath_list_local(gs_memory_t * mem,void * vrlist,client_name_t cname)323 rc_free_cpath_list_local(gs_memory_t * mem, void *vrlist,
324 client_name_t cname)
325 {
326 gx_clip_rect_list *rlist = (gx_clip_rect_list *) vrlist;
327
328 gx_clip_list_free(&rlist->list, mem);
329 }
330 private void
rc_free_cpath_list(gs_memory_t * mem,void * vrlist,client_name_t cname)331 rc_free_cpath_list(gs_memory_t * mem, void *vrlist, client_name_t cname)
332 {
333 rc_free_cpath_list_local(mem, vrlist, cname);
334 gs_free_object(mem, vrlist, cname);
335 }
336
337 private void
rc_free_cpath_path_list(gs_memory_t * mem,void * vplist,client_name_t cname)338 rc_free_cpath_path_list(gs_memory_t * mem, void *vplist, client_name_t cname)
339 {
340 gx_cpath_path_list *plist = (gx_cpath_path_list *)vplist;
341 rc_decrement(plist->next, cname);
342 gx_path_free(&plist->path, cname);
343 gs_free_object(plist->path.memory, plist, cname);
344 }
345
346 /* Allocate a new clip path list node. The created node has a ref count
347 of 1, and "steals" the reference to next (i.e. does not increment
348 its reference count). */
349 private int
gx_cpath_path_list_new(gs_memory_t * mem,gx_clip_path * pcpath,int rule,gx_path * ppfrom,gx_cpath_path_list * next,gx_cpath_path_list ** pnew)350 gx_cpath_path_list_new(gs_memory_t *mem, gx_clip_path *pcpath, int rule,
351 gx_path *ppfrom, gx_cpath_path_list *next, gx_cpath_path_list **pnew)
352 {
353 int code;
354 client_name_t cname = "gx_cpath_path_list_new";
355 gx_cpath_path_list *pcplist = gs_alloc_struct(mem, gx_cpath_path_list,
356 &st_cpath_path_list, cname);
357
358 if (pcplist == 0)
359 return_error(gs_error_VMerror);
360 rc_init_free(pcplist, mem, 1, rc_free_cpath_path_list);
361 if (pcpath!=NULL && !pcpath->path_valid) {
362 code = gx_path_init_contained_shared(&pcplist->path, NULL, mem, cname);
363 if (code < 0)
364 return code;
365 code = gx_cpath_to_path(pcpath, &pcplist->path);
366 } else {
367 gx_path_init_local(&pcplist->path, mem);
368 code = gx_path_assign_preserve(&pcplist->path, ppfrom);
369 }
370 if (code < 0)
371 return code;
372 pcplist->next = next;
373 pcplist->rule = rule;
374 *pnew = pcplist;
375 return 0;
376 }
377
378 /* ------ Clipping path accessing ------ */
379
380 /* Return the path of a clipping path. */
381 int
gx_cpath_to_path(gx_clip_path * pcpath,gx_path * ppath)382 gx_cpath_to_path(gx_clip_path * pcpath, gx_path * ppath)
383 {
384 if (!pcpath->path_valid) {
385 /* Synthesize a path. */
386 gs_cpath_enum cenum;
387 gs_fixed_point pts[3];
388 gx_path rpath;
389 int code;
390
391 gx_path_init_local(&rpath, pcpath->path.memory);
392 gx_cpath_enum_init(&cenum, pcpath);
393 while ((code = gx_cpath_enum_next(&cenum, pts)) != 0) {
394 switch (code) {
395 case gs_pe_moveto:
396 code = gx_path_add_point(&rpath, pts[0].x, pts[0].y);
397 break;
398 case gs_pe_lineto:
399 code = gx_path_add_line_notes(&rpath, pts[0].x, pts[0].y,
400 gx_cpath_enum_notes(&cenum));
401 break;
402 case gs_pe_curveto:
403 code = gx_path_add_curve_notes(&rpath, pts[0].x, pts[0].y,
404 pts[1].x, pts[1].y,
405 pts[2].x, pts[2].y,
406 gx_cpath_enum_notes(&cenum));
407 break;
408 case gs_pe_closepath:
409 code = gx_path_close_subpath_notes(&rpath,
410 gx_cpath_enum_notes(&cenum));
411 break;
412 default:
413 if (code >= 0)
414 code = gs_note_error(gs_error_unregistered);
415 }
416 if (code < 0)
417 break;
418 }
419 if (code >= 0)
420 code = gx_path_assign_free(&pcpath->path, &rpath);
421 if (code < 0) {
422 gx_path_free(&rpath, "gx_cpath_to_path error");
423 return code;
424 }
425 pcpath->path_valid = true;
426 }
427 return gx_path_assign_preserve(ppath, &pcpath->path);
428 }
429
430 /* Return the inner and outer check rectangles for a clipping path. */
431 /* Return true iff the path is a rectangle. */
432 bool
gx_cpath_inner_box(const gx_clip_path * pcpath,gs_fixed_rect * pbox)433 gx_cpath_inner_box(const gx_clip_path * pcpath, gs_fixed_rect * pbox)
434 {
435 *pbox = pcpath->inner_box;
436 return clip_list_is_rectangle(gx_cpath_list(pcpath));
437 }
438 bool
gx_cpath_outer_box(const gx_clip_path * pcpath,gs_fixed_rect * pbox)439 gx_cpath_outer_box(const gx_clip_path * pcpath, gs_fixed_rect * pbox)
440 {
441 *pbox = pcpath->outer_box;
442 return clip_list_is_rectangle(gx_cpath_list(pcpath));
443 }
444
445 /* Test if a clipping path includes a rectangle. */
446 /* The rectangle need not be oriented correctly, i.e. x0 > x1 is OK. */
447 bool
gx_cpath_includes_rectangle(register const gx_clip_path * pcpath,fixed x0,fixed y0,fixed x1,fixed y1)448 gx_cpath_includes_rectangle(register const gx_clip_path * pcpath,
449 fixed x0, fixed y0, fixed x1, fixed y1)
450 {
451 return
452 (x0 <= x1 ?
453 (pcpath->inner_box.p.x <= x0 && x1 <= pcpath->inner_box.q.x) :
454 (pcpath->inner_box.p.x <= x1 && x0 <= pcpath->inner_box.q.x)) &&
455 (y0 <= y1 ?
456 (pcpath->inner_box.p.y <= y0 && y1 <= pcpath->inner_box.q.y) :
457 (pcpath->inner_box.p.y <= y1 && y0 <= pcpath->inner_box.q.y));
458 }
459
460 /* Set the outer clipping box to the path bounding box, */
461 /* expanded to pixel boundaries. */
462 void
gx_cpath_set_outer_box(gx_clip_path * pcpath)463 gx_cpath_set_outer_box(gx_clip_path * pcpath)
464 {
465 pcpath->outer_box.p.x = fixed_floor(pcpath->path.bbox.p.x);
466 pcpath->outer_box.p.y = fixed_floor(pcpath->path.bbox.p.y);
467 pcpath->outer_box.q.x = fixed_ceiling(pcpath->path.bbox.q.x);
468 pcpath->outer_box.q.y = fixed_ceiling(pcpath->path.bbox.q.y);
469 }
470
471 /* Return the rectangle list of a clipping path (for local use only). */
472 const gx_clip_list *
gx_cpath_list(const gx_clip_path * pcpath)473 gx_cpath_list(const gx_clip_path *pcpath)
474 {
475 return &pcpath->rect_list->list;
476 }
477 /* Internal non-const version of the same accessor. */
478 inline private gx_clip_list *
gx_cpath_list_private(gx_clip_path * pcpath)479 gx_cpath_list_private(gx_clip_path *pcpath)
480 {
481 return &pcpath->rect_list->list;
482 }
483
484
485 /* ------ Clipping path setting ------ */
486
487 /* Create a rectangular clipping path. */
488 /* The supplied rectangle may not be oriented correctly, */
489 /* but it will be oriented correctly upon return. */
490 private int
cpath_set_rectangle(gx_clip_path * pcpath,gs_fixed_rect * pbox)491 cpath_set_rectangle(gx_clip_path * pcpath, gs_fixed_rect * pbox)
492 {
493 gx_clip_rect_list *rlist = pcpath->rect_list;
494
495 if (rlist->rc.ref_count <= 1)
496 gx_clip_list_free(&rlist->list, rlist->rc.memory);
497 else {
498 int code = cpath_alloc_list(&pcpath->rect_list, pcpath->path.memory,
499 "gx_cpath_from_rectangle");
500
501 if (code < 0)
502 return code;
503 rc_decrement(rlist, "gx_cpath_from_rectangle");
504 rlist = pcpath->rect_list;
505 }
506 cpath_init_rectangle(pcpath, pbox);
507 return 0;
508 }
509 int
gx_cpath_from_rectangle(gx_clip_path * pcpath,gs_fixed_rect * pbox)510 gx_cpath_from_rectangle(gx_clip_path * pcpath, gs_fixed_rect * pbox)
511 {
512 int code = gx_path_new(&pcpath->path);
513
514 if (code < 0)
515 return code;
516 return cpath_set_rectangle(pcpath, pbox);
517 }
518 int
gx_cpath_reset(gx_clip_path * pcpath)519 gx_cpath_reset(gx_clip_path * pcpath)
520 {
521 gs_fixed_rect null_rect;
522
523 null_rect.p.x = null_rect.p.y = null_rect.q.x = null_rect.q.y = 0;
524 return gx_cpath_from_rectangle(pcpath, &null_rect);
525 }
526
527 /* If a clipping path is a rectangle, return the rectangle. */
528 const gs_fixed_rect *
cpath_is_rectangle(const gx_clip_path * pcpath)529 cpath_is_rectangle(const gx_clip_path * pcpath)
530 {
531 if (pcpath->path_valid)
532 return NULL;
533 if (pcpath->inner_box.p.x != pcpath->path.bbox.p.x ||
534 pcpath->inner_box.p.y != pcpath->path.bbox.p.y ||
535 pcpath->inner_box.q.x != pcpath->path.bbox.q.x ||
536 pcpath->inner_box.q.y != pcpath->path.bbox.q.y)
537 return NULL;
538 return &pcpath->inner_box;
539 }
540
541 /* Intersect a new clipping path with an old one. */
542 /* Flatten the new path first (in a copy) if necessary. */
543 int
gx_cpath_clip(gs_state * pgs,gx_clip_path * pcpath,gx_path * ppath_orig,int rule)544 gx_cpath_clip(gs_state *pgs, gx_clip_path *pcpath,
545 /*const*/ gx_path *ppath_orig, int rule)
546 {
547 return gx_cpath_intersect(pcpath, ppath_orig, rule,
548 (gs_imager_state *)pgs);
549 }
550 int
gx_cpath_intersect(gx_clip_path * pcpath,gx_path * ppath_orig,int rule,gs_imager_state * pis)551 gx_cpath_intersect(gx_clip_path *pcpath, /*const*/ gx_path *ppath_orig,
552 int rule, gs_imager_state *pis)
553 {
554 gx_path fpath;
555 /*const*/ gx_path *ppath = ppath_orig;
556 gs_fixed_rect old_box, new_box;
557 int code;
558
559 /* Flatten the path if necessary. */
560 if (gx_path_has_curves_inline(ppath)) {
561 gx_path_init_local(&fpath, pis->memory);
562 code = gx_path_add_flattened_accurate(ppath, &fpath,
563 gs_currentflat_inline(pis),
564 pis->accurate_curves);
565 if (code < 0)
566 return code;
567 ppath = &fpath;
568 }
569
570 if (gx_cpath_inner_box(pcpath, &old_box) &&
571 ((code = gx_path_is_rectangle(ppath, &new_box)) ||
572 gx_path_is_void(ppath))
573 ) {
574 int changed = 0;
575
576 if (!code) {
577 /* The new path is void. */
578 if (gx_path_current_point(ppath, &new_box.p) < 0) {
579 /* Use the user space origin (arbitrarily). */
580 new_box.p.x = float2fixed(pis->ctm.tx);
581 new_box.p.y = float2fixed(pis->ctm.ty);
582 }
583 new_box.q = new_box.p;
584 changed = 1;
585 } else {
586 /* Intersect the two rectangles if necessary. */
587 if (old_box.p.x > new_box.p.x)
588 new_box.p.x = old_box.p.x, ++changed;
589 if (old_box.p.y > new_box.p.y)
590 new_box.p.y = old_box.p.y, ++changed;
591 if (old_box.q.x < new_box.q.x)
592 new_box.q.x = old_box.q.x, ++changed;
593 if (old_box.q.y < new_box.q.y)
594 new_box.q.y = old_box.q.y, ++changed;
595 /* Check for a degenerate rectangle. */
596 if (new_box.q.x < new_box.p.x || new_box.q.y < new_box.p.y)
597 new_box.p = new_box.q, changed = 1;
598 }
599 if (changed == 4) {
600 /* The new box/path is the same as the old. */
601 return 0;
602 }
603 /* Release the existing path. */
604 rc_decrement(pcpath->path_list, "gx_cpath_intersect");
605 pcpath->path_list = NULL;
606 gx_path_new(&pcpath->path);
607 ppath->bbox = new_box;
608 cpath_set_rectangle(pcpath, &new_box);
609 if (changed == 0) {
610 /* The path is valid; otherwise, defer constructing it. */
611 gx_path_assign_preserve(&pcpath->path, ppath);
612 pcpath->path_valid = true;
613 }
614 } else {
615 /* New clip path is nontrivial. Intersect the slow way. */
616 gx_cpath_path_list *next = pcpath->path_list;
617 bool path_valid =
618 gx_cpath_inner_box(pcpath, &old_box) &&
619 gx_path_bbox(ppath, &new_box) >= 0 &&
620 gx_cpath_includes_rectangle(pcpath,
621 new_box.p.x, new_box.p.y,
622 new_box.q.x, new_box.q.y);
623
624 if (!path_valid && next == NULL) {
625 code = gx_cpath_path_list_new(pcpath->path.memory, pcpath, pcpath->rule,
626 &pcpath->path, NULL, &next);
627 if (code < 0)
628 goto ex;
629 }
630 code = gx_cpath_intersect_path_slow(pcpath, ppath, rule, pis);
631 if (code < 0)
632 goto ex;
633 if (path_valid) {
634 gx_path_assign_preserve(&pcpath->path, ppath_orig);
635 pcpath->path_valid = true;
636 } else {
637 code = gx_cpath_path_list_new(pcpath->path.memory, NULL, rule,
638 ppath_orig, next, &pcpath->path_list);
639 }
640 }
641 ex:
642 if (ppath != ppath_orig)
643 gx_path_free(ppath, "gx_cpath_clip");
644 return code;
645 }
646
647 /* Scale a clipping path by a power of 2. */
648 int
gx_cpath_scale_exp2_shared(gx_clip_path * pcpath,int log2_scale_x,int log2_scale_y,bool list_shared,bool segments_shared)649 gx_cpath_scale_exp2_shared(gx_clip_path * pcpath, int log2_scale_x,
650 int log2_scale_y, bool list_shared,
651 bool segments_shared)
652 {
653 int code =
654 (pcpath->path_valid ?
655 gx_path_scale_exp2_shared(&pcpath->path, log2_scale_x, log2_scale_y,
656 segments_shared) :
657 0);
658 gx_clip_list *list = gx_cpath_list_private(pcpath);
659 gx_clip_rect *pr;
660
661 if (code < 0)
662 return code;
663 /* Scale the fixed entries. */
664 gx_rect_scale_exp2(&pcpath->inner_box, log2_scale_x, log2_scale_y);
665 gx_rect_scale_exp2(&pcpath->outer_box, log2_scale_x, log2_scale_y);
666 if (!list_shared) {
667 /* Scale the clipping list. */
668 pr = list->head;
669 if (pr == 0)
670 pr = &list->single;
671 for (; pr != 0; pr = pr->next)
672 if (pr != list->head && pr != list->tail) {
673
674 #define SCALE_V(v, s)\
675 if ( pr->v != min_int && pr->v != max_int )\
676 pr->v = (s >= 0 ? pr->v << s : pr->v >> -s)
677
678 SCALE_V(xmin, log2_scale_x);
679 SCALE_V(xmax, log2_scale_x);
680 SCALE_V(ymin, log2_scale_y);
681 SCALE_V(ymax, log2_scale_y);
682 #undef SCALE_V
683 }
684 }
685 pcpath->id = gs_next_ids(pcpath->path.memory, 1); /* path changed => change id */
686 return 0;
687 }
688
689 /* ------ Clipping list routines ------ */
690
691 /* Initialize a clip list. */
692 void
gx_clip_list_init(gx_clip_list * clp)693 gx_clip_list_init(gx_clip_list * clp)
694 {
695 *clp = clip_list_empty;
696 }
697
698 /* Initialize a clip list to a rectangle. */
699 /* The supplied rectangle may not be oriented correctly, */
700 /* but it will be oriented correctly upon return. */
701 private void
gx_clip_list_from_rectangle(register gx_clip_list * clp,register gs_fixed_rect * rp)702 gx_clip_list_from_rectangle(register gx_clip_list * clp,
703 register gs_fixed_rect * rp)
704 {
705 gx_clip_list_init(clp);
706 if (rp->p.x > rp->q.x) {
707 fixed t = rp->p.x;
708
709 rp->p.x = rp->q.x;
710 rp->q.x = t;
711 }
712 if (rp->p.y > rp->q.y) {
713 fixed t = rp->p.y;
714
715 rp->p.y = rp->q.y;
716 rp->q.y = t;
717 }
718 clp->single.xmin = clp->xmin = fixed2int_var(rp->p.x);
719 clp->single.ymin = fixed2int_var(rp->p.y);
720 /* Handle degenerate rectangles specially. */
721 clp->single.xmax = clp->xmax =
722 (rp->q.x == rp->p.x ? clp->single.xmin :
723 fixed2int_var_ceiling(rp->q.x));
724 clp->single.ymax =
725 (rp->q.y == rp->p.y ? clp->single.ymin :
726 fixed2int_var_ceiling(rp->q.y));
727 clp->count = 1;
728 }
729
730 /* Start enumerating a clipping path. */
731 int
gx_cpath_enum_init(gs_cpath_enum * penum,gx_clip_path * pcpath)732 gx_cpath_enum_init(gs_cpath_enum * penum, gx_clip_path * pcpath)
733 {
734 if ((penum->using_path = pcpath->path_valid)) {
735 gx_path_enum_init(&penum->path_enum, &pcpath->path);
736 penum->rp = penum->visit = 0;
737 } else {
738 gx_path empty_path;
739 gx_clip_list *clp = gx_cpath_list_private(pcpath);
740 gx_clip_rect *head = (clp->count <= 1 ? &clp->single : clp->head);
741 gx_clip_rect *rp;
742
743 /* Initialize the pointers in the path_enum properly. */
744 gx_path_init_local(&empty_path, pcpath->path.memory);
745 gx_path_enum_init(&penum->path_enum, &empty_path);
746 penum->visit = head;
747 for (rp = head; rp != 0; rp = rp->next)
748 rp->to_visit =
749 (rp->xmin < rp->xmax && rp->ymin < rp->ymax ?
750 visit_left | visit_right : 0);
751 penum->rp = 0; /* scan will initialize */
752 penum->any_rectangles = false;
753 penum->state = cpe_scan;
754 penum->have_line = false;
755 }
756 return 0;
757 }
758
759 /* Enumerate the next segment of a clipping path. */
760 /* In general, this produces a path made up of zillions of tiny lines. */
761 int
gx_cpath_enum_next(gs_cpath_enum * penum,gs_fixed_point pts[3])762 gx_cpath_enum_next(gs_cpath_enum * penum, gs_fixed_point pts[3])
763 {
764 if (penum->using_path)
765 return gx_path_enum_next(&penum->path_enum, pts);
766 #define set_pt(xi, yi)\
767 (pts[0].x = int2fixed(xi), pts[0].y = int2fixed(yi))
768 #define set_line(xi, yi)\
769 (penum->line_end.x = (xi), penum->line_end.y = (yi), penum->have_line = true)
770 if (penum->have_line) {
771 set_pt(penum->line_end.x, penum->line_end.y);
772 penum->have_line = false;
773 return gs_pe_lineto;
774 } {
775 gx_clip_rect *visit = penum->visit;
776 gx_clip_rect *rp = penum->rp;
777 cpe_visit_t first_visit = penum->first_visit;
778 cpe_state_t state = penum->state;
779 gx_clip_rect *look;
780 int code;
781
782 switch (state) {
783
784 case cpe_scan:
785 /* Look for the start of an edge to trace. */
786 for (; visit != 0; visit = visit->next) {
787 if (visit->to_visit & visit_left) {
788 set_pt(visit->xmin, visit->ymin);
789 first_visit = visit_left;
790 state = cpe_left;
791 } else if (visit->to_visit & visit_right) {
792 set_pt(visit->xmax, visit->ymax);
793 first_visit = visit_right;
794 state = cpe_right;
795 } else
796 continue;
797 rp = visit;
798 code = gs_pe_moveto;
799 penum->any_rectangles = true;
800 goto out;
801 }
802 /* We've enumerated all the edges. */
803 state = cpe_done;
804 if (!penum->any_rectangles) {
805 /* We didn't have any rectangles. */
806 set_pt(fixed_0, fixed_0);
807 code = gs_pe_moveto;
808 break;
809 }
810 /* falls through */
811
812 case cpe_done:
813 /* All done. */
814 code = 0;
815 break;
816
817 /* We can't use the BEGIN ... END hack here: we need to be able to break. */
818 #define return_line(px, py)\
819 set_pt(px, py); code = gs_pe_lineto; break
820
821 case cpe_left:
822
823 left: /* Trace upward along a left edge. */
824 /* We're at the lower left corner of rp. */
825 rp->to_visit &= ~visit_left;
826 /* Look for an adjacent rectangle above rp. */
827 for (look = rp;
828 (look = look->next) != 0 &&
829 (look->ymin == rp->ymin ||
830 (look->ymin == rp->ymax && look->xmax <= rp->xmin));
831 );
832 /* Now we know look->ymin >= rp->ymax. */
833 if (look == 0 || look->ymin > rp->ymax ||
834 look->xmin >= rp->xmax
835 ) { /* No adjacent rectangle, switch directions. */
836 state =
837 (rp == visit && first_visit == visit_right ? cpe_close :
838 (set_line(rp->xmax, rp->ymax), cpe_right));
839 return_line(rp->xmin, rp->ymax);
840 }
841 /* We found an adjacent rectangle. */
842 /* See if it also adjoins a rectangle to the left of rp. */
843 {
844 gx_clip_rect *prev = rp->prev;
845 gx_clip_rect *cur = rp;
846
847 if (prev != 0 && prev->ymax == rp->ymax &&
848 look->xmin < prev->xmax
849 ) { /* There's an adjoining rectangle as well. */
850 /* Switch directions. */
851 rp = prev;
852 state =
853 (rp == visit && first_visit == visit_right ? cpe_close :
854 (set_line(prev->xmax, prev->ymax), cpe_right));
855 return_line(cur->xmin, cur->ymax);
856 }
857 rp = look;
858 if (rp == visit && first_visit == visit_left)
859 state = cpe_close;
860 else if (rp->xmin == cur->xmin)
861 goto left;
862 else
863 set_line(rp->xmin, rp->ymin);
864 return_line(cur->xmin, cur->ymax);
865 }
866
867 case cpe_right:
868
869 right: /* Trace downward along a right edge. */
870 /* We're at the upper right corner of rp. */
871 rp->to_visit &= ~visit_right;
872 /* Look for an adjacent rectangle below rp. */
873 for (look = rp;
874 (look = look->prev) != 0 &&
875 (look->ymax == rp->ymax ||
876 (look->ymax == rp->ymin && look->xmin >= rp->xmax));
877 );
878 /* Now we know look->ymax <= rp->ymin. */
879 if (look == 0 || look->ymax < rp->ymin ||
880 look->xmax <= rp->xmin
881 ) { /* No adjacent rectangle, switch directions. */
882 state =
883 (rp == visit && first_visit == visit_left ? cpe_close :
884 (set_line(rp->xmin, rp->ymin), cpe_left));
885 return_line(rp->xmax, rp->ymin);
886 }
887 /* We found an adjacent rectangle. */
888 /* See if it also adjoins a rectangle to the right of rp. */
889 {
890 gx_clip_rect *next = rp->next;
891 gx_clip_rect *cur = rp;
892
893 if (next != 0 && next->ymin == rp->ymin &&
894 look->xmax > next->xmin
895 ) { /* There's an adjoining rectangle as well. */
896 /* Switch directions. */
897 rp = next;
898 state =
899 (rp == visit && first_visit == visit_left ? cpe_close :
900 (set_line(next->xmin, next->ymin), cpe_left));
901 return_line(cur->xmax, cur->ymin);
902 }
903 rp = look;
904 if (rp == visit && first_visit == visit_right)
905 state = cpe_close;
906 else if (rp->xmax == cur->xmax)
907 goto right;
908 else
909 set_line(rp->xmax, rp->ymax);
910 return_line(cur->xmax, cur->ymin);
911 }
912
913 #undef return_line
914
915 case cpe_close:
916 /* We've gone all the way around an edge. */
917 code = gs_pe_closepath;
918 state = cpe_scan;
919 break;
920
921 default:
922 return_error(gs_error_unknownerror);
923 }
924
925 out: /* Store the state before exiting. */
926 penum->visit = visit;
927 penum->rp = rp;
928 penum->first_visit = first_visit;
929 penum->state = state;
930 return code;
931 }
932 #undef set_pt
933 #undef set_line
934 }
935 segment_notes
gx_cpath_enum_notes(const gs_cpath_enum * penum)936 gx_cpath_enum_notes(const gs_cpath_enum * penum)
937 {
938 return sn_none;
939 }
940
941 /* Free a clip list. */
942 void
gx_clip_list_free(gx_clip_list * clp,gs_memory_t * mem)943 gx_clip_list_free(gx_clip_list * clp, gs_memory_t * mem)
944 {
945 gx_clip_rect *rp = clp->tail;
946
947 while (rp != 0) {
948 gx_clip_rect *prev = rp->prev;
949
950 gs_free_object(mem, rp, "gx_clip_list_free");
951 rp = prev;
952 }
953 gx_clip_list_init(clp);
954 }
955
956 /* ------ Debugging printout ------ */
957
958 #ifdef DEBUG
959
960 /* Print a clipping list. */
961 private void
gx_clip_list_print(const gx_clip_list * list)962 gx_clip_list_print(const gx_clip_list *list)
963 {
964 const gx_clip_rect *pr;
965
966 dlprintf3(" list count=%d xmin=%d xmax=%d\n",
967 list->count, list->xmin, list->xmax);
968 switch (list->count) {
969 case 0:
970 pr = 0;
971 break;
972 case 1:
973 pr = &list->single;
974 break;
975 default:
976 pr = list->head;
977 }
978 for (; pr != 0; pr = pr->next)
979 dlprintf4(" rect: (%d,%d),(%d,%d)\n",
980 pr->xmin, pr->ymin, pr->xmax, pr->ymax);
981 }
982
983 /* Print a clipping path */
984 void
gx_cpath_print(const gx_clip_path * pcpath)985 gx_cpath_print(const gx_clip_path * pcpath)
986 {
987 if (pcpath->path_valid)
988 gx_path_print(&pcpath->path);
989 else
990 dlputs(" (path not valid)\n");
991 dlprintf4(" inner_box=(%g,%g),(%g,%g)\n",
992 fixed2float(pcpath->inner_box.p.x),
993 fixed2float(pcpath->inner_box.p.y),
994 fixed2float(pcpath->inner_box.q.x),
995 fixed2float(pcpath->inner_box.q.y));
996 dlprintf4(" outer_box=(%g,%g),(%g,%g)",
997 fixed2float(pcpath->outer_box.p.x),
998 fixed2float(pcpath->outer_box.p.y),
999 fixed2float(pcpath->outer_box.q.x),
1000 fixed2float(pcpath->outer_box.q.y));
1001 dprintf2(" rule=%d list.refct=%ld\n",
1002 pcpath->rule, pcpath->rect_list->rc.ref_count);
1003 gx_clip_list_print(gx_cpath_list(pcpath));
1004 }
1005
1006 #endif /* DEBUG */
1007