123456789101112131415161718192021222324252627282930313233343536373839404142434445464748495051525354555657585960616263646566676869707172737475767778798081828384858687888990919293949596979899100101102103104105106107108109110111112113114115116117118119120121122123124125126127128129130131132133134135136137138139140141142143144145146147148149150151152153154155156157158159160161162163164165166167168169170171172173174175176177178179180181182183184185186187188189190191192193194195196197198199200201202203204205206207208209210211212213214215216217218219220221222223224225226227228229230231232233234235236237238239240241242243244245246247248249250251252253254255256257258259260261262263264265266267268269270271272273274275276277278279280281282283284285286287288289290291292293294295296297298299300301302303304305306307308309310311312313314315316317318319320321322323324325326327328329330331332333334335336337338339340341342343344345346347348349350351352353354355356357358359360361362363364365366367368369370371372373374375376377378379380381382383384385386387388389390391392393394395396397398399400401402403404405406407408409410411412413414415416417418419420421422423424425426427428429430431432433434435436437438439440441442443444445446447448449450451452453454455456457458459460461462463464465466467468469470471472473474475476477478479480481482483484485486487488489490491492493494495496497498499500501502503504505506507508509510511512513514515516517518519 |
- /* Copyright (C) 1989, 1995, 1997, 1998, 1999 Aladdin Enterprises. All rights reserved.
-
- This file is part of AFPL Ghostscript.
-
- AFPL Ghostscript is distributed with NO WARRANTY OF ANY KIND. No author or
- distributor accepts any responsibility for the consequences of using it, or
- for whether it serves any particular purpose or works at all, unless he or
- she says so in writing. Refer to the Aladdin Free Public License (the
- "License") for full details.
-
- Every copy of AFPL Ghostscript must include a copy of the License, normally
- in a plain ASCII text file named PUBLIC. The License grants you the right
- to copy, modify and redistribute AFPL Ghostscript, but only under certain
- conditions described in the License. Among other things, the License
- requires that the copyright notice and this notice be preserved on all
- copies.
- */
- /*$Id: gxpath2.c,v 1.2 2000/09/19 19:00:39 lpd Exp $ */
- /* Path tracing procedures for Ghostscript library */
- #include "math_.h"
- #include "gx.h"
- #include "gserrors.h"
- #include "gspath.h" /* for gs_path_enum_alloc prototype */
- #include "gsstruct.h"
- #include "gxfixed.h"
- #include "gxarith.h"
- #include "gzpath.h"
- /* Define the enumeration structure. */
- public_st_path_enum();
- /* Read the current point of a path. */
- int
- gx_path_current_point(const gx_path * ppath, gs_fixed_point * ppt)
- {
- if (!path_position_valid(ppath))
- return_error(gs_error_nocurrentpoint);
- /* Copying the coordinates individually */
- /* is much faster on a PC, and almost as fast on other machines.... */
- ppt->x = ppath->position.x, ppt->y = ppath->position.y;
- return 0;
- }
- /* Read the start point of the current subpath. */
- int
- gx_path_subpath_start_point(const gx_path * ppath, gs_fixed_point * ppt)
- {
- const subpath *psub = ppath->current_subpath;
- if (!psub)
- return_error(gs_error_nocurrentpoint);
- *ppt = psub->pt;
- return 0;
- }
- /* Read the bounding box of a path. */
- /* Note that if the last element of the path is a moveto, */
- /* the bounding box does not include this point, */
- /* unless this is the only element of the path. */
- int
- gx_path_bbox(gx_path * ppath, gs_fixed_rect * pbox)
- {
- if (ppath->bbox_set) {
- /* The bounding box was set by setbbox. */
- *pbox = ppath->bbox;
- return 0;
- }
- if (ppath->first_subpath == 0) {
- /* The path is empty, use the current point if any. */
- int code = gx_path_current_point(ppath, &pbox->p);
- if (code < 0) {
- /*
- * Don't return garbage, in case the caller doesn't
- * check the return code.
- */
- pbox->p.x = pbox->p.y = 0;
- }
- pbox->q = pbox->p;
- return code;
- }
- /* The stored bounding box may not be up to date. */
- /* Correct it now if necessary. */
- if (ppath->box_last == ppath->current_subpath->last) {
- /* Box is up to date */
- *pbox = ppath->bbox;
- } else {
- fixed px, py, qx, qy;
- const segment *pseg = ppath->box_last;
- if (pseg == 0) { /* box is uninitialized */
- pseg = (const segment *)ppath->first_subpath;
- px = qx = pseg->pt.x;
- py = qy = pseg->pt.y;
- } else {
- px = ppath->bbox.p.x, py = ppath->bbox.p.y;
- qx = ppath->bbox.q.x, qy = ppath->bbox.q.y;
- }
- /* Macro for adjusting the bounding box when adding a point */
- #define ADJUST_BBOX(pt)\
- if ((pt).x < px) px = (pt).x;\
- else if ((pt).x > qx) qx = (pt).x;\
- if ((pt).y < py) py = (pt).y;\
- else if ((pt).y > qy) qy = (pt).y
- while ((pseg = pseg->next) != 0) {
- switch (pseg->type) {
- case s_curve:
- ADJUST_BBOX(((const curve_segment *)pseg)->p1);
- ADJUST_BBOX(((const curve_segment *)pseg)->p2);
- /* falls through */
- default:
- ADJUST_BBOX(pseg->pt);
- }
- }
- #undef ADJUST_BBOX
- #define STORE_BBOX(b)\
- (b).p.x = px, (b).p.y = py, (b).q.x = qx, (b).q.y = qy;
- STORE_BBOX(*pbox);
- STORE_BBOX(ppath->bbox);
- #undef STORE_BBOX
- ppath->box_last = ppath->current_subpath->last;
- }
- return 0;
- }
- /* Test if a path has any curves. */
- #undef gx_path_has_curves
- bool
- gx_path_has_curves(const gx_path * ppath)
- {
- return gx_path_has_curves_inline(ppath);
- }
- #define gx_path_has_curves(ppath)\
- gx_path_has_curves_inline(ppath)
- /* Test if a path has no segments. */
- #undef gx_path_is_void
- bool
- gx_path_is_void(const gx_path * ppath)
- {
- return gx_path_is_void_inline(ppath);
- }
- #define gx_path_is_void(ppath)\
- gx_path_is_void_inline(ppath)
- /* Test if a path has no elements at all. */
- bool
- gx_path_is_null(const gx_path * ppath)
- {
- return gx_path_is_null_inline(ppath);
- }
- /*
- * Test if a subpath is a rectangle; if so, return its bounding box
- * and the start of the next subpath.
- * Note that this must recognize:
- * ordinary closed rectangles (M, L, L, L, C);
- * open rectangles (M, L, L, L);
- * rectangles closed with lineto (Mo, L, L, L, Lo);
- * rectangles closed with *both* lineto and closepath (bad PostScript,
- * but unfortunately not rare) (Mo, L, L, L, Lo, C).
- */
- gx_path_rectangular_type
- gx_subpath_is_rectangular(const subpath * pseg0, gs_fixed_rect * pbox,
- const subpath ** ppnext)
- {
- const segment *pseg1, *pseg2, *pseg3, *pseg4;
- gx_path_rectangular_type type;
- if (pseg0->curve_count == 0 &&
- (pseg1 = pseg0->next) != 0 &&
- (pseg2 = pseg1->next) != 0 &&
- (pseg3 = pseg2->next) != 0
- ) {
- if ((pseg4 = pseg3->next) == 0 || pseg4->type == s_start)
- type = prt_open; /* M, L, L, L */
- else if (pseg4->type != s_line) /* must be s_line_close */
- type = prt_closed; /* M, L, L, L, C */
- else if (pseg4->pt.x != pseg0->pt.x ||
- pseg4->pt.y != pseg0->pt.y
- )
- return prt_none;
- else if (pseg4->next == 0 || pseg4->next->type == s_start)
- type = prt_fake_closed; /* Mo, L, L, L, Lo */
- else if (pseg4->next->type != s_line) /* must be s_line_close */
- type = prt_closed; /* Mo, L, L, L, Lo, C */
- else
- return prt_none;
- {
- fixed x0 = pseg0->pt.x, y0 = pseg0->pt.y;
- fixed x2 = pseg2->pt.x, y2 = pseg2->pt.y;
- if ((x0 == pseg1->pt.x && pseg1->pt.y == y2 &&
- x2 == pseg3->pt.x && pseg3->pt.y == y0) ||
- (x0 == pseg3->pt.x && pseg3->pt.y == y2 &&
- x2 == pseg1->pt.x && pseg1->pt.y == y0)
- ) { /* Path is a rectangle. Return the bounding box. */
- if (x0 < x2)
- pbox->p.x = x0, pbox->q.x = x2;
- else
- pbox->p.x = x2, pbox->q.x = x0;
- if (y0 < y2)
- pbox->p.y = y0, pbox->q.y = y2;
- else
- pbox->p.y = y2, pbox->q.y = y0;
- while (pseg4 != 0 && pseg4->type != s_start)
- pseg4 = pseg4->next;
- *ppnext = (const subpath *)pseg4;
- return type;
- }
- }
- }
- return prt_none;
- }
- /* Test if an entire path to be filled is a rectangle. */
- gx_path_rectangular_type
- gx_path_is_rectangular(const gx_path * ppath, gs_fixed_rect * pbox)
- {
- const subpath *pnext;
- return
- (gx_path_subpath_count(ppath) == 1 ?
- gx_subpath_is_rectangular(ppath->first_subpath, pbox, &pnext) :
- prt_none);
- }
- /* Translate an already-constructed path (in device space). */
- /* Don't bother to update the cbox. */
- int
- gx_path_translate(gx_path * ppath, fixed dx, fixed dy)
- {
- segment *pseg;
- #define update_xy(pt)\
- pt.x += dx, pt.y += dy
- if (ppath->box_last != 0) {
- update_xy(ppath->bbox.p);
- update_xy(ppath->bbox.q);
- }
- if (path_position_valid(ppath))
- update_xy(ppath->position);
- for (pseg = (segment *) (ppath->first_subpath); pseg != 0;
- pseg = pseg->next
- )
- switch (pseg->type) {
- case s_curve:
- #define pcseg ((curve_segment *)pseg)
- update_xy(pcseg->p1);
- update_xy(pcseg->p2);
- #undef pcseg
- default:
- update_xy(pseg->pt);
- }
- #undef update_xy
- return 0;
- }
- /* Scale an existing path by a power of 2 (positive or negative). */
- void
- gx_point_scale_exp2(gs_fixed_point * pt, int sx, int sy)
- {
- if (sx >= 0)
- pt->x <<= sx;
- else
- pt->x >>= -sx;
- if (sy >= 0)
- pt->y <<= sy;
- else
- pt->y >>= -sy;
- }
- void
- gx_rect_scale_exp2(gs_fixed_rect * pr, int sx, int sy)
- {
- gx_point_scale_exp2(&pr->p, sx, sy);
- gx_point_scale_exp2(&pr->q, sx, sy);
- }
- int
- gx_path_scale_exp2_shared(gx_path * ppath, int log2_scale_x, int log2_scale_y,
- bool segments_shared)
- {
- segment *pseg;
- gx_rect_scale_exp2(&ppath->bbox, log2_scale_x, log2_scale_y);
- #define SCALE_XY(pt) gx_point_scale_exp2(&pt, log2_scale_x, log2_scale_y)
- SCALE_XY(ppath->position);
- if (!segments_shared) {
- for (pseg = (segment *) (ppath->first_subpath); pseg != 0;
- pseg = pseg->next
- )
- switch (pseg->type) {
- case s_curve:
- SCALE_XY(((curve_segment *)pseg)->p1);
- SCALE_XY(((curve_segment *)pseg)->p2);
- default:
- SCALE_XY(pseg->pt);
- }
- }
- #undef SCALE_XY
- return 0;
- }
- /*
- * Reverse a path. We know ppath != ppath_old.
- * NOTE: in releases 5.01 and earlier, the implicit line added by closepath
- * became the first segment of the reversed path. Starting in release
- * 5.02, the code follows the Adobe implementation (and LanguageLevel 3
- * specification), in which this line becomes the *last* segment of the
- * reversed path. This can produce some quite unintuitive results.
- */
- int
- gx_path_copy_reversed(const gx_path * ppath_old, gx_path * ppath)
- {
- const subpath *psub = ppath_old->first_subpath;
- #ifdef DEBUG
- if (gs_debug_c('P'))
- gx_dump_path(ppath_old, "before reversepath");
- #endif
- nsp:
- if (psub) {
- const segment *prev = psub->last;
- const segment *pseg;
- segment_notes notes =
- (prev == (const segment *)psub ? sn_none :
- psub->next->notes);
- segment_notes prev_notes;
- int code;
- if (!psub->is_closed) {
- code = gx_path_add_point(ppath, prev->pt.x, prev->pt.y);
- if (code < 0)
- return code;
- }
- /*
- * The do ... while structure of this loop is artificial,
- * designed solely to keep compilers from complaining about
- * 'statement not reached' or 'end-of-loop code not reached'.
- * The normal exit from this loop is the goto statement in
- * the s_start arm of the switch.
- */
- do {
- pseg = prev;
- prev_notes = notes;
- prev = pseg->prev;
- notes = pseg->notes;
- prev_notes = (prev_notes & sn_not_first) |
- (notes & ~sn_not_first);
- switch (pseg->type) {
- case s_start:
- /* Finished subpath */
- if (psub->is_closed) {
- code =
- gx_path_close_subpath_notes(ppath, prev_notes);
- if (code < 0)
- return code;
- }
- psub = (const subpath *)psub->last->next;
- goto nsp;
- case s_curve:
- {
- const curve_segment *pc =
- (const curve_segment *)pseg;
- code = gx_path_add_curve_notes(ppath,
- pc->p2.x, pc->p2.y,
- pc->p1.x, pc->p1.y,
- prev->pt.x, prev->pt.y, prev_notes);
- break;
- }
- case s_line:
- code = gx_path_add_line_notes(ppath,
- prev->pt.x, prev->pt.y, prev_notes);
- break;
- case s_line_close:
- /* Skip the closing line. */
- code = gx_path_add_point(ppath, prev->pt.x,
- prev->pt.y);
- break;
- default: /* not possible */
- return_error(gs_error_Fatal);
- }
- } while (code >= 0);
- return code; /* only reached if code < 0 */
- }
- #undef sn_not_end
- /*
- * In the Adobe implementations, reversepath discards a trailing
- * moveto unless the path consists only of a moveto. We reproduce
- * this behavior here, even though we consider it a bug.
- */
- if (ppath_old->first_subpath == 0 &&
- path_last_is_moveto(ppath_old)
- ) {
- int code = gx_path_add_point(ppath, ppath_old->position.x,
- ppath_old->position.y);
- if (code < 0)
- return code;
- }
- #ifdef DEBUG
- if (gs_debug_c('P'))
- gx_dump_path(ppath, "after reversepath");
- #endif
- return 0;
- }
- /* ------ Path enumeration ------ */
- /* Allocate a path enumerator. */
- gs_path_enum *
- gs_path_enum_alloc(gs_memory_t * mem, client_name_t cname)
- {
- return gs_alloc_struct(mem, gs_path_enum, &st_path_enum, cname);
- }
- /* Start enumerating a path. */
- int
- gx_path_enum_init(gs_path_enum * penum, const gx_path * ppath)
- {
- penum->memory = 0; /* path not copied */
- penum->path = ppath;
- penum->copied_path = 0; /* not copied */
- penum->pseg = (const segment *)ppath->first_subpath;
- penum->moveto_done = false;
- penum->notes = sn_none;
- return 0;
- }
- /* Enumerate the next element of a path. */
- /* If the path is finished, return 0; */
- /* otherwise, return the element type. */
- int
- gx_path_enum_next(gs_path_enum * penum, gs_fixed_point ppts[3])
- {
- const segment *pseg = penum->pseg;
- if (pseg == 0) { /* We've enumerated all the segments, but there might be */
- /* a trailing moveto. */
- const gx_path *ppath = penum->path;
- if (path_last_is_moveto(ppath) && !penum->moveto_done) { /* Handle a trailing moveto */
- penum->moveto_done = true;
- penum->notes = sn_none;
- ppts[0] = ppath->position;
- return gs_pe_moveto;
- }
- return 0;
- }
- penum->pseg = pseg->next;
- penum->notes = pseg->notes;
- switch (pseg->type) {
- case s_start:
- ppts[0] = pseg->pt;
- return gs_pe_moveto;
- case s_line:
- ppts[0] = pseg->pt;
- return gs_pe_lineto;
- case s_line_close:
- ppts[0] = pseg->pt;
- return gs_pe_closepath;
- case s_curve:
- #define pcseg ((const curve_segment *)pseg)
- ppts[0] = pcseg->p1;
- ppts[1] = pcseg->p2;
- ppts[2] = pseg->pt;
- return gs_pe_curveto;
- #undef pcseg
- default:
- lprintf1("bad type %x in gx_path_enum_next!\n", pseg->type);
- return_error(gs_error_Fatal);
- }
- }
- /* Return the notes from the last-enumerated segment. */
- segment_notes
- gx_path_enum_notes(const gs_path_enum * penum)
- {
- return penum->notes;
- }
- /* Back up 1 element in the path being enumerated. */
- /* Return true if successful, false if we are at the beginning of the path. */
- /* This implementation allows backing up multiple times, */
- /* but no client currently relies on this. */
- bool
- gx_path_enum_backup(gs_path_enum * penum)
- {
- const segment *pseg = penum->pseg;
- if (pseg != 0) {
- if ((pseg = pseg->prev) == 0)
- return false;
- penum->pseg = pseg;
- return true;
- }
- /* We're at the end of the path. Check to see whether */
- /* we need to back up over a trailing moveto. */
- {
- const gx_path *ppath = penum->path;
- if (path_last_is_moveto(ppath) && penum->moveto_done) { /* Back up over the trailing moveto. */
- penum->moveto_done = false;
- return true;
- } {
- const subpath *psub = ppath->current_subpath;
- if (psub == 0) /* empty path */
- return false;
- /* Back up to the last segment of the last subpath. */
- penum->pseg = psub->last;
- return true;
- }
- }
- }
|