home *** CD-ROM | disk | FTP | other *** search
/ PC World Komputer 1996 February / PCWK0296.iso / sharewar / dos / program / gs300sr1 / gs300sr1.exe / GXPATH.C < prev    next >
C/C++ Source or Header  |  1994-07-27  |  14KB  |  457 lines
  1. /* Copyright (C) 1989, 1992, 1993 Aladdin Enterprises.  All rights reserved.
  2.   
  3.   This file is part of Aladdin Ghostscript.
  4.   
  5.   Aladdin Ghostscript is distributed with NO WARRANTY OF ANY KIND.  No author
  6.   or distributor accepts any responsibility for the consequences of using it,
  7.   or for whether it serves any particular purpose or works at all, unless he
  8.   or she says so in writing.  Refer to the Aladdin Ghostscript Free Public
  9.   License (the "License") for full details.
  10.   
  11.   Every copy of Aladdin Ghostscript must include a copy of the License,
  12.   normally in a plain ASCII text file named PUBLIC.  The License grants you
  13.   the right to copy, modify and redistribute Aladdin Ghostscript, but only
  14.   under certain conditions described in the License.  Among other things, the
  15.   License requires that the copyright notice and this notice be preserved on
  16.   all copies.
  17. */
  18.  
  19. /* gxpath.c */
  20. /* Internal path construction routines for Ghostscript library */
  21. #include "gx.h"
  22. #include "gserrors.h"
  23. #include "gsstruct.h"
  24. #include "gxfixed.h"
  25. #include "gzpath.h"
  26.  
  27. /* These routines all assume that all points are */
  28. /* already in device coordinates, and in fixed representation. */
  29. /* As usual, they return either 0 or a (negative) error code. */
  30.  
  31. /* Forward references */
  32. private subpath *path_alloc_copy(P1(gx_path *));
  33. private int gx_path_new_subpath(P1(gx_path *));
  34. #ifdef DEBUG
  35. void gx_print_segment(P1(const segment *));
  36. #endif
  37.  
  38. /* Macro for checking a point against a preset bounding box. */
  39. #define check_in_bbox(ppath, px, py)\
  40.   if ( px < ppath->bbox.p.x || px > ppath->bbox.q.x ||\
  41.        py < ppath->bbox.p.y || py > ppath->bbox.q.y\
  42.      )\
  43.     return_error(gs_error_rangecheck)
  44.  
  45. /* Structure descriptors for paths and path segment types. */
  46. public_st_path();
  47. private_st_line();
  48. private_st_line_close();
  49. private_st_curve();
  50. private_st_subpath();
  51.  
  52. /* ------ Initialize/free paths ------ */
  53.  
  54. /* Initialize a path */
  55. void
  56. gx_path_init(gx_path *ppath, gs_memory_t *mem)
  57. {    ppath->memory = mem;
  58.     gx_path_reset(ppath);
  59. }
  60. void
  61. gx_path_reset(register gx_path *ppath)
  62. {    ppath->box_last = 0;
  63.     ppath->position_valid = 0;
  64.     ppath->first_subpath = ppath->current_subpath = 0;
  65.     ppath->subpath_count = 0;
  66.     ppath->curve_count = 0;
  67.     ppath->subpath_open = 0;
  68.     ppath->shares_segments = 0;
  69.     ppath->bbox_set = 0;
  70. }
  71.  
  72. /* Release the contents of a path.  We do this in reverse order */
  73. /* so as to maximize LIFO allocator behavior. */
  74. void
  75. gx_path_release(gx_path *ppath)
  76. {    segment *pseg;
  77.     if ( ppath->first_subpath == 0 ) return;    /* empty path */
  78.     if ( ppath->shares_segments ) return;    /* segments are shared */
  79.     pseg = (segment *)ppath->current_subpath->last;
  80.     while ( pseg )
  81.     {    segment *prev = pseg->prev;
  82. #ifdef DEBUG
  83. if ( gs_debug_c('p') )
  84.         dprintf("[p]release"), gx_print_segment(pseg);
  85. #endif
  86.         gs_free_object(ppath->memory, pseg, "gx_path_release");
  87.         pseg = prev;
  88.     }
  89.     ppath->first_subpath = 0;    /* prevent re-release */
  90. }
  91.  
  92. /* Mark a path as shared */
  93. void
  94. gx_path_share(gx_path *ppath)
  95. {    if ( ppath->first_subpath ) ppath->shares_segments = 1;
  96. }
  97.  
  98. /* ------ Incremental path building ------ */
  99.  
  100. /* Macro for opening the current subpath. */
  101. /* ppath points to the path; psub has been set to ppath->current_subpath. */
  102. #define path_open()\
  103.     if ( ppath->subpath_open <= 0 )\
  104.        {    int code;\
  105.         if ( !ppath->position_valid )\
  106.           return_error(gs_error_nocurrentpoint);\
  107.         code = gx_path_new_subpath(ppath);\
  108.         if ( code < 0 ) return code;\
  109.         psub = ppath->current_subpath;\
  110.        }
  111.  
  112. /* Macros for allocating path segments. */
  113. /* Note that they assume that ppath points to the path, */
  114. /* and that psub points to the current subpath. */
  115. /* We have to split the macro into two because of limitations */
  116. /* on the size of a single statement (sigh). */
  117. #define p_alloc(pseg,size)\
  118.   if_debug2('A', "[p]0x%lx<%lu>\n", (ulong)(pseg), (ulong)(size))
  119. #define path_unshare(ppath)\
  120.   if(ppath->shares_segments)\
  121.     if(!(psub = path_alloc_copy(ppath)))return_error(gs_error_VMerror)
  122. #define path_alloc_segment(pseg,ctype,pstype,stype,cname)\
  123.   path_unshare(ppath);\
  124.   if( !(pseg = gs_alloc_struct(ppath->memory, ctype, pstype, cname)) )\
  125.     return_error(gs_error_VMerror);\
  126.   p_alloc((char *)pseg, sizeof(ctype));\
  127.   pseg->type = stype, pseg->next = 0
  128. #define path_alloc_link(pseg)\
  129.   { segment *prev = psub->last;\
  130.     prev->next = (segment *)pseg;\
  131.     pseg->prev = prev;\
  132.     psub->last = (segment *)pseg;\
  133.   }
  134.  
  135. /* Open a new subpath */
  136. private int
  137. gx_path_new_subpath(gx_path *ppath)
  138. {    subpath *psub = ppath->current_subpath;
  139.     register subpath *spp;
  140.     path_alloc_segment(spp, subpath, &st_subpath, s_start,
  141.                "gx_path_new_subpath");
  142.     spp->last = (segment *)spp;
  143.     spp->curve_count = 0;
  144.     spp->is_closed = 0;
  145.     spp->pt = ppath->position;
  146.     ppath->subpath_open = 1;
  147.     if ( !psub )            /* first subpath */
  148.        {    ppath->first_subpath = spp;
  149.         spp->prev = 0;
  150.        }
  151.     else
  152.        {    segment *prev = psub->last;
  153.         prev->next = (segment *)spp;
  154.         spp->prev = prev;
  155.        }
  156.     ppath->current_subpath = spp;
  157.     ppath->subpath_count++;
  158. #ifdef DEBUG
  159. if ( gs_debug_c('p') )
  160.     dprintf("[p]"), gx_print_segment((const segment *)spp);
  161. #endif
  162.     return 0;
  163. }
  164.  
  165. /* Add a point to the current path (moveto). */
  166. int
  167. gx_path_add_point(register gx_path *ppath, fixed x, fixed y)
  168. {    if ( ppath->bbox_set )
  169.         check_in_bbox(ppath, x, y);
  170.     ppath->subpath_open = -1;
  171.     ppath->position_valid = 1;
  172.     ppath->position.x = x;
  173.     ppath->position.y = y;
  174.     return 0;
  175. }
  176.  
  177. /* Add a relative point to the current path (rmoveto). */
  178. int
  179. gx_path_add_relative_point(register gx_path *ppath, fixed dx, fixed dy)
  180. {    if ( !ppath->position_valid )
  181.       return_error(gs_error_nocurrentpoint);
  182.     if ( ppath->bbox_set )
  183.       check_in_bbox(ppath, ppath->position.x + dx, ppath->position.y + dy);
  184.     ppath->subpath_open = -1;
  185.     ppath->position.x += dx;
  186.     ppath->position.y += dy;
  187.     return 0;
  188. }
  189.  
  190. /* Set the segment point and the current point in the path. */
  191. /* Assumes ppath points to the path. */
  192. #define path_set_point(pseg, fx, fy)\
  193.     (pseg)->pt.x = ppath->position.x = (fx),\
  194.     (pseg)->pt.y = ppath->position.y = (fy)
  195.  
  196. /* Add a line to the current path (lineto). */
  197. int
  198. gx_path_add_line(gx_path *ppath, fixed x, fixed y)
  199. {    subpath *psub = ppath->current_subpath;
  200.     register line_segment *lp;
  201.     if ( ppath->bbox_set )
  202.         check_in_bbox(ppath, x, y);
  203.     path_open();
  204.     path_alloc_segment(lp, line_segment, &st_line, s_line,
  205.                "gx_path_add_line");
  206.     path_alloc_link(lp);
  207.     path_set_point(lp, x, y);
  208. #ifdef DEBUG
  209. if ( gs_debug_c('p') )
  210.     dprintf("[p]"), gx_print_segment((segment *)lp);
  211. #endif
  212.     return 0;
  213. }
  214.  
  215. /* Add a rectangle to the current path. */
  216. /* This is a special case of adding a parallelogram. */
  217. int
  218. gx_path_add_rectangle(gx_path *ppath, fixed x0, fixed y0, fixed x1, fixed y1)
  219. {    return gx_path_add_pgram(ppath, x0, y0, x0, y1, x1, y1);
  220. }
  221.  
  222. /* Add a parallelogram to the current path. */
  223. /* This is equivalent to an add_point, three add_lines, */
  224. /* and a close_subpath. */
  225. int
  226. gx_path_add_pgram(gx_path *ppath,
  227.   fixed x0, fixed y0, fixed x1, fixed y1, fixed x2, fixed y2)
  228. {    int code;
  229.      if (    (code = gx_path_add_point(ppath, x0, y0)) < 0 ||
  230.         (code = gx_path_add_line(ppath, x1, y1)) < 0 ||
  231.         (code = gx_path_add_line(ppath, x2, y2)) < 0 ||
  232.         (code = gx_path_add_line(ppath, x0 + x2 - x1, y0 + y2 - y1)) < 0 ||
  233.         (code = gx_path_close_subpath(ppath)) < 0
  234.        ) return code;
  235.     return 0;
  236. }
  237.  
  238. /* Add a curve to the current path (curveto). */
  239. int
  240. gx_path_add_curve(gx_path *ppath,
  241.   fixed x1, fixed y1, fixed x2, fixed y2, fixed x3, fixed y3)
  242. {    subpath *psub = ppath->current_subpath;
  243.     register curve_segment *lp;
  244.     if ( ppath->bbox_set )
  245.     {    check_in_bbox(ppath, x1, y1);
  246.         check_in_bbox(ppath, x2, y2);
  247.         check_in_bbox(ppath, x3, y3);
  248.     }
  249.     path_open();
  250.     path_alloc_segment(lp, curve_segment, &st_curve, s_curve,
  251.                "gx_path_add_curve");
  252.     path_alloc_link(lp);
  253.     lp->p1.x = x1;
  254.     lp->p1.y = y1;
  255.     lp->p2.x = x2;
  256.     lp->p2.y = y2;
  257.     path_set_point(lp, x3, y3);
  258.     psub->curve_count++;
  259.     ppath->curve_count++;
  260. #ifdef DEBUG
  261. if ( gs_debug_c('p') )
  262.     dprintf("[p]"), gx_print_segment((segment *)lp);
  263. #endif
  264.     return 0;
  265. }
  266.  
  267. /*
  268.  * Add an approximation of an arc to the current path.
  269.  * Parameters are the initial and final points of the arc,
  270.  * and the point at which the extended tangents meet.
  271.  * We assume that the arc is less than a semicircle.
  272.  * The arc may go either clockwise or counterclockwise.
  273.  * The approximation is a very simple one: a single curve
  274.  * whose other two control points are a fraction F of the way
  275.  * to the intersection of the tangents, where
  276.  *    F = (4/3)(1 / (1 + sqrt(1+(d/r)^2)))
  277.  * where r is the radius and d is the distance from either tangent
  278.  * point to the intersection of the tangents.  This produces
  279.  * a curve whose center point, as well as its ends, lies on
  280.  * the desired arc.
  281.  *
  282.  * Because F has to be computed in user space, we let the client
  283.  * compute it and pass it in as an argument.
  284.  */
  285. int
  286. gx_path_add_arc(gx_path *ppath,
  287.   fixed x0, fixed y0, fixed x3, fixed y3, fixed xt, fixed yt, floatp fraction)
  288. {    return gx_path_add_curve(ppath,
  289.             x0 + (fixed)((xt - x0) * fraction),
  290.             y0 + (fixed)((yt - y0) * fraction),
  291.             x3 + (fixed)((xt - x3) * fraction),
  292.             y3 + (fixed)((yt - y3) * fraction),
  293.             x3, y3);
  294. }
  295.  
  296. /* Append a path to another path, and reset the first path. */
  297. /* Currently this is only used to append a path to its parent */
  298. /* (the path in the previous graphics context). */
  299. int
  300. gx_path_add_path(gx_path *ppath, gx_path *ppfrom)
  301. {    subpath *psub;
  302.     path_unshare(ppfrom);
  303.     path_unshare(ppath);
  304.     if ( ppfrom->first_subpath )    /* i.e. ppfrom not empty */
  305.        {    if ( ppath->first_subpath )    /* i.e. ppath not empty */
  306.            {    subpath *psub = ppath->current_subpath;
  307.             segment *pseg = psub->last;
  308.             subpath *pfsub = ppfrom->first_subpath;
  309.             pseg->next = (segment *)pfsub;
  310.             pfsub->prev = pseg;
  311.            }
  312.         else
  313.             ppath->first_subpath = ppfrom->first_subpath;
  314.         ppath->current_subpath = ppfrom->current_subpath;
  315.         ppath->subpath_count += ppfrom->subpath_count;
  316.         ppath->curve_count += ppfrom->curve_count;
  317.        }
  318.     /* Transfer the remaining state. */
  319.     ppath->position = ppfrom->position;
  320.     ppath->position_valid = ppfrom->position_valid;
  321.     ppath->subpath_open = ppfrom->subpath_open;
  322.     gx_path_reset(ppfrom);        /* reset the source path */
  323.     return 0;
  324. }
  325.  
  326. /* Close the current subpath. */
  327. int
  328. gx_path_close_subpath(gx_path *ppath)
  329. {    subpath *psub = ppath->current_subpath;
  330.     register line_close_segment *lp;
  331.     int code;
  332.     switch ( ppath->subpath_open )
  333.     {
  334.     case 0:
  335.         return 0;
  336.     case -1:
  337.         code = gx_path_new_subpath(ppath);
  338.         if ( code < 0 )
  339.             return 0;
  340.         psub = ppath->current_subpath;
  341.     /*case 1:*/
  342.     }
  343.     path_alloc_segment(lp, line_close_segment, &st_line_close, s_line_close,
  344.                "gx_path_close_subpath");
  345.     path_alloc_link(lp);
  346.     path_set_point(lp, psub->pt.x, psub->pt.y);
  347.     lp->sub = psub;
  348.     psub->is_closed = 1;
  349.     ppath->subpath_open = 0;
  350. #ifdef DEBUG
  351. if ( gs_debug_c('p') )
  352.     if ( lp != 0 )
  353.       dprintf("[p]"), gx_print_segment((segment *)lp);
  354. #endif
  355.     return 0;
  356. }
  357.  
  358. /* ------ Internal routines ------ */
  359.  
  360. /* Copy the current path, because it was shared. */
  361. /* Return a pointer to the current subpath, or 0. */
  362. private subpath *
  363. path_alloc_copy(gx_path *ppath)
  364. {    gx_path path_new;
  365.     int code;
  366.     code = gx_path_copy(ppath, &path_new, 1);
  367.     if ( code < 0 ) return 0;
  368.     *ppath = path_new;
  369.     ppath->shares_segments = 0;
  370.     return ppath->current_subpath;
  371. }
  372.  
  373. /* ------ Debugging printout ------ */
  374.  
  375. #ifdef DEBUG
  376.  
  377. /* Print out a path with a label */
  378. void
  379. gx_dump_path(const gx_path *ppath, const char *tag)
  380. {    dprintf2("[p]Path 0x%lx %s:\n", (ulong)ppath, tag);
  381.     gx_path_print(ppath);
  382. }
  383.  
  384. /* Print a path */
  385. void
  386. gx_path_print(const gx_path *ppath)
  387. {    const segment *pseg = (const segment *)ppath->first_subpath;
  388.     dprintf4("   subpaths=%d, curves=%d, point=(%f,%f)\n",
  389.          ppath->subpath_count, ppath->curve_count,
  390.          fixed2float(ppath->position.x),
  391.          fixed2float(ppath->position.y));
  392.     dprintf5("   box=(%f,%f),(%f,%f) last=0x%lx\n",
  393.          fixed2float(ppath->bbox.p.x), fixed2float(ppath->bbox.p.y),
  394.          fixed2float(ppath->bbox.q.x), fixed2float(ppath->bbox.q.y),
  395.          (ulong)ppath->box_last);
  396.     while ( pseg )
  397.        {    gx_print_segment(pseg);
  398.         pseg = pseg->next;
  399.        }
  400. }
  401. void
  402. gx_print_segment(const segment *pseg)
  403. {    char out[80];
  404.     sprintf(out, "   0x%lx<0x%lx,0x%lx>: %%s (%6g,%6g) ",
  405.         (ulong)pseg, (ulong)pseg->prev, (ulong)pseg->next,
  406.         fixed2float(pseg->pt.x), fixed2float(pseg->pt.y));
  407.     switch ( pseg->type )
  408.        {
  409.     case s_start:
  410. #define psub ((const subpath *)pseg)
  411.         dprintf1(out, "start");
  412.         dprintf2("#curves=%d last=0x%lx",
  413.              psub->curve_count, (ulong)psub->last);
  414. #undef psub
  415.         break;
  416.     case s_curve:
  417.         dprintf1(out, "curve");
  418. #define pcur ((const curve_segment *)pseg)
  419.         dprintf4("\n\tp1=(%f,%f) p2=(%f,%f)",
  420.              fixed2float(pcur->p1.x), fixed2float(pcur->p1.y),
  421.              fixed2float(pcur->p2.x), fixed2float(pcur->p2.y));
  422. #undef pcur
  423.         break;
  424.     case s_line:
  425.         dprintf1(out, "line");
  426.         break;
  427.     case s_line_close:
  428. #define plc ((const line_close_segment *)pseg)
  429.         dprintf1(out, "close");
  430.         dprintf1(" 0x%lx", (ulong)(plc->sub));
  431. #undef plc
  432.         break;
  433.     default:
  434.        {    char t[20];
  435.         sprintf(t, "type 0x%x", pseg->type);
  436.         dprintf1(out, t);
  437.        }
  438.        }
  439.     dputc('\n');
  440. }
  441.  
  442. /* Print a clipping path */
  443. void
  444. gx_cpath_print(const gx_clip_path *pcpath)
  445. {    if ( pcpath->segments_valid )
  446.         gx_path_print(&pcpath->path);
  447.     else
  448.         dputs("   (segments not valid)\n");
  449.     dprintf5("   cbox=(%f,%f),(%f,%f) count=%d\n",
  450.          fixed2float(pcpath->cbox.p.x), fixed2float(pcpath->cbox.p.y),
  451.          fixed2float(pcpath->cbox.q.x), fixed2float(pcpath->cbox.q.y),
  452.          pcpath->list.count);
  453.     /****** SHOULD PRINT CLIP LIST ******/
  454. }
  455.  
  456. #endif                    /* DEBUG */
  457.