| /* Copyright (C) 1989, 1990 Aladdin Enterprises. All rights reserved. | |
| Distributed by Free Software Foundation, Inc. | |
| This file is part of Ghostscript. | |
| Ghostscript is distributed in the hope that it will be useful, but | |
| WITHOUT ANY WARRANTY. No author or distributor accepts responsibility | |
| to anyone for the consequences of using it or for whether it serves any | |
| particular purpose or works at all, unless he says so in writing. Refer | |
| to the Ghostscript General Public License for full details. | |
| Everyone is granted permission to copy, modify and redistribute | |
| Ghostscript, but only under the conditions described in the Ghostscript | |
| General Public License. A copy of this license is supposed to have been | |
| given to you along with Ghostscript so you can know your rights and | |
| responsibilities. It should be in a file named COPYING. Among other | |
| things, the copyright notice and this notice must be preserved on all | |
| copies. */ | |
| /* gxpath2.c */ | |
| /* Path tracing procedures for GhostScript library */ | |
| #include "math_.h" | |
| #include "gx.h" | |
| #include "gserrors.h" | |
| #include "gxfixed.h" | |
| #include "gxarith.h" | |
| #include "gzpath.h" | |
| /* Forward declarations */ | |
| private int copy_path(P3(gx_path *, gx_path *, | |
| int (*)(P7(gx_path *, fixed, fixed, fixed, fixed, fixed, fixed)))); | |
| private int flatten_curve(P7(gx_path *, | |
| fixed, fixed, fixed, fixed, fixed, fixed)); | |
| /* Read the current point of a path. */ | |
| int | |
| gx_path_current_point(gx_path *ppath, gs_fixed_point *ppt) | |
| { if ( !ppath->position_valid ) | |
| 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 bounding box of a path. */ | |
| int | |
| gx_path_bbox(gx_path *ppath, gs_fixed_rect *pbox) | |
| { if ( ppath->first_subpath == 0 ) | |
| { /* The path is empty, use the current point if any. */ | |
| gx_path_current_point(ppath, &pbox->p); | |
| return gx_path_current_point(ppath, &pbox->q); | |
| } | |
| /* 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 | |
| { gs_fixed_rect box; | |
| register segment *pseg = ppath->box_last; | |
| if ( pseg == 0 ) /* box is uninitialized */ | |
| { pseg = (segment *)ppath->first_subpath; | |
| box.p.x = box.q.x = pseg->pt.x; | |
| box.p.y = box.q.y = pseg->pt.y; | |
| } | |
| else | |
| { box = ppath->bbox; | |
| pseg = pseg->next; | |
| } | |
| /* Macro for adjusting the bounding box when adding a point */ | |
| #define adjust_bbox(pt)\ | |
| if ( (pt).x < box.p.x ) box.p.x = (pt).x;\ | |
| else if ( (pt).x > box.q.x ) box.q.x = (pt).x;\ | |
| if ( (pt).y < box.p.y ) box.p.y = (pt).y;\ | |
| else if ( (pt).y > box.q.y ) box.q.y = (pt).y | |
| while ( pseg ) | |
| { switch ( pseg->type ) | |
| { | |
| case s_curve: | |
| #define pcurve ((curve_segment *)pseg) | |
| adjust_bbox(pcurve->p1); | |
| adjust_bbox(pcurve->p2); | |
| #undef pcurve | |
| /* falls through */ | |
| default: | |
| adjust_bbox(pseg->pt); | |
| } | |
| pseg = pseg->next; | |
| } | |
| #undef adjust_bbox | |
| ppath->bbox = box; | |
| ppath->box_last = ppath->current_subpath->last; | |
| *pbox = box; | |
| } | |
| return 0; | |
| } | |
| /* Test if a path has any curves. */ | |
| int | |
| gx_path_has_curves(gx_path *ppath) | |
| { return ppath->curve_count != 0; | |
| } | |
| /* Test if a path has any segments. */ | |
| int | |
| gx_path_is_void(gx_path *ppath) | |
| { return ppath->segment_count == 0; | |
| } | |
| /* Test if a path is a rectangle. */ | |
| /* If so, return its bounding box. */ | |
| int | |
| gx_path_is_rectangle(gx_path *ppath, gs_fixed_rect *pbox) | |
| { subpath *pseg0; | |
| if ( ppath->subpath_count == 1 && | |
| ppath->segment_count == 4 && ppath->curve_count == 0 && | |
| (pseg0 = ppath->first_subpath)->last->type == s_line_close ) | |
| { fixed x0 = pseg0->pt.x, y0 = pseg0->pt.y; | |
| segment *pseg1 = pseg0->next; | |
| segment *pseg2 = pseg1->next; | |
| fixed x2 = pseg2->pt.x, y2 = pseg2->pt.y; | |
| segment *pseg3 = pseg2->next; | |
| 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 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; | |
| return 1; | |
| } | |
| } | |
| return 0; | |
| } | |
| /* Return the quick-check rectangle for a clipping path. */ | |
| /* This only works for paths that have gone through set_clip_path. */ | |
| /* which is why the name is different. */ | |
| int | |
| gx_cpath_box_for_check(register gx_path *ppath, gs_fixed_rect *pbox) | |
| { *pbox = ppath->cbox; | |
| return 0; | |
| } | |
| /* Test if a clipping path includes a rectangle. */ | |
| /* The rectangle need not be oriented correctly, i.e. x0 > x1 is OK. */ | |
| /* This only works for paths that have gone through set_clip_path. */ | |
| /* which is why the name is different. */ | |
| int | |
| gx_cpath_includes_rectangle(register gx_path *ppath, | |
| fixed x0, fixed y0, fixed x1, fixed y1) | |
| { return | |
| (x0 <= x1 ? | |
| (ppath->cbox.p.x <= x0 && x1 <= ppath->cbox.q.x) : | |
| (ppath->cbox.p.x <= x1 && x0 <= ppath->cbox.q.x)) && | |
| (y0 <= y1 ? | |
| (ppath->cbox.p.y <= y0 && y1 <= ppath->cbox.q.y) : | |
| (ppath->cbox.p.y <= y1 && y0 <= ppath->cbox.q.y)); | |
| } | |
| /* Copy a path */ | |
| int | |
| gx_path_copy(gx_path *ppath_old, gx_path *ppath) | |
| { return copy_path(ppath_old, ppath, gx_path_add_curve); | |
| } | |
| /* Merge a path into its parent (the path in the previous graphics */ | |
| /* context). If ppto is not the parent of ppfrom, chaos may result! */ | |
| int | |
| gx_path_merge(gx_path *ppfrom, gx_path *ppto) | |
| { /* If no new segments, don't release the parent. */ | |
| subpath *psfrom = ppfrom->current_subpath; | |
| subpath *psto = ppto->current_subpath; | |
| if ( psto != 0 && psfrom->last != psto->last ) | |
| { gx_path_release(ppto); | |
| } | |
| *ppto = *ppfrom; | |
| ppfrom->shares_segments = 1; | |
| return 0; | |
| } | |
| /* Translate an already-constructed path (in device space). */ | |
| /* Don't bother to translate the cbox. */ | |
| int | |
| gx_path_translate(gx_path *ppath, fixed dx, fixed dy) | |
| { segment *pseg; | |
| #define translate_xy(pt)\ | |
| pt.x += dx, pt.y += dy | |
| translate_xy(ppath->bbox.p); | |
| translate_xy(ppath->bbox.q); | |
| translate_xy(ppath->position); | |
| pseg = (segment *)(ppath->first_subpath); | |
| while ( pseg ) | |
| { switch ( pseg->type ) | |
| { | |
| case s_curve: | |
| { curve_segment *pc = (curve_segment *)pseg; | |
| translate_xy(pc->p1); | |
| translate_xy(pc->p2); | |
| } | |
| default: | |
| translate_xy(pseg->pt); | |
| } | |
| pseg = pseg->next; | |
| } | |
| return 0; | |
| } | |
| /* Define magic quantities used for flatness checking. */ | |
| /* Approximate sqrt(1+t*t)*scaled_flat by (1+t*t*0.45)*scaled_flat. */ | |
| /* This is good to within about 10% in the range 0<=abs(t)<=1. */ | |
| #define sqrt_magic 0.45 | |
| #define sqrt1t2xf(t) ((fixed)(t * t * scaled_flat_sq) + scaled_flat) | |
| private fixed scaled_flat; | |
| private float scaled_flat_sq; | |
| /* Flatten a path */ | |
| int | |
| gx_path_flatten(gx_path *ppath_old, gx_path *ppath, floatp flatness) | |
| { /* See the flattening algorithm below for an explanation of */ | |
| /* the following computation. */ | |
| float ff = flatness * ((float)int2fixed(1)); | |
| scaled_flat = ff; | |
| scaled_flat_sq = ff * sqrt_magic; | |
| return copy_path(ppath_old, ppath, flatten_curve); | |
| } | |
| /* Copy a path, optionally flattening it. */ | |
| /* If the copy fails, free the new path. */ | |
| private int | |
| copy_path(gx_path *ppath_old, gx_path *ppath, | |
| int (*curve_proc)(P7(gx_path *, fixed, fixed, fixed, fixed, fixed, fixed))) | |
| { gx_path old; | |
| segment *pseg; | |
| int code; | |
| #ifdef DEBUG | |
| if ( gs_debug['p'] ) | |
| gx_dump_path(ppath_old, "before copy_path"); | |
| #endif | |
| old = *ppath_old; | |
| gx_path_init(ppath, &ppath_old->memory_procs); | |
| pseg = (segment *)(old.first_subpath); | |
| while ( pseg ) | |
| { switch ( pseg->type ) | |
| { | |
| case s_start: | |
| code = gx_path_add_point(ppath, pseg->pt.x, pseg->pt.y); | |
| break; | |
| case s_curve: | |
| { curve_segment *pc = (curve_segment *)pseg; | |
| code = (*curve_proc)(ppath, | |
| pc->p1.x, pc->p1.y, | |
| pc->p2.x, pc->p2.y, | |
| pc->pt.x, pc->pt.y); | |
| break; | |
| } | |
| case s_line: | |
| code = gx_path_add_line(ppath, pseg->pt.x, pseg->pt.y); | |
| break; | |
| case s_line_close: | |
| code = gx_path_close_subpath(ppath); | |
| break; | |
| } | |
| if ( code ) | |
| { gx_path_release(ppath); | |
| if ( ppath == ppath_old ) *ppath_old = old; | |
| return code; | |
| } | |
| pseg = pseg->next; | |
| } | |
| ppath->position = old.position; /* restore current point */ | |
| #ifdef DEBUG | |
| if ( gs_debug['p'] ) | |
| gx_dump_path(ppath, "after copy_path"); | |
| #endif | |
| return 0; | |
| } | |
| /* Internal routine to flatten a curve. */ | |
| /* This calls itself recursively, using binary subdivision, */ | |
| /* until the approximation is good enough to satisfy the */ | |
| /* flatness requirement. The starting point is ppath->position, */ | |
| /* which gets updated as line segments are added. */ | |
| #ifdef DEBUG | |
| private void | |
| print_curve_point(fixed x, fixed y) | |
| { printf("[u]\t*** x=%f, y=%f ***\n", fixed2float(x), fixed2float(y)); | |
| } | |
| #endif | |
| private int | |
| flatten_curve(gx_path *ppath, | |
| fixed x1, fixed y1, fixed x2, fixed y2, fixed x3, fixed y3) | |
| { fixed | |
| x0 = ppath->position.x, | |
| y0 = ppath->position.y; | |
| top: | |
| #ifdef DEBUG | |
| if ( gs_debug['u'] ) | |
| printf("[u]x0=%f y0=%f x1=%f y1=%f\n x2=%f y2=%f x3=%f y3=%f\n", | |
| fixed2float(x0), fixed2float(y0), fixed2float(x1), | |
| fixed2float(y1), fixed2float(x2), fixed2float(y2), | |
| fixed2float(x3), fixed2float(y3)); | |
| #endif | |
| { /* Compute the maximum distance of the curve from */ | |
| /* the line (x0,y0)->(x3,y3). We do this conservatively */ | |
| /* by observing that the curve is enclosed by the */ | |
| /* quadrilateral of its control points, so we simply */ | |
| /* compute the distances of (x1,y1) and (x2,y2) */ | |
| /* from the line. The distance of (xp,yp) from the line is */ | |
| /* abs(N)/sqrt(D), where N = dy*(xp-x0)-dx*(yp-y0) and */ | |
| /* D = dx*dx+dy*dy. However, since we are only */ | |
| /* interested in whether this is greater than the flatness */ | |
| /* F, we may as well avoid the square root by testing */ | |
| /* whether N*N > D*F*F, where we can precompute F*F. */ | |
| /* Indeed, we can go further by letting t=dy/dx, and */ | |
| /* testing N1*N1 > D1*F*F, where N1=t*(xp-x0)-(yp-y0) and */ | |
| /* D1 = 1+t*t. (If dx < dy, we swap x and y for this */ | |
| /* computation, which incidentally guarantees abs(t) <= 1.) */ | |
| /* We can even avoid doing any scaling in converting the */ | |
| /* coordinates and distances from fixed to floating: */ | |
| /* if s is the scale factor for fixed quantities, and we */ | |
| /* disregard it in converting the d, x, and y values to */ | |
| /* floating point, then we actually wind up comparing */ | |
| /* N1*N1*(s^4) > D1*(s^2)*F1, and everything will come out */ | |
| /* if we let F1 = F*F*s^2. This explains the computation */ | |
| /* of flat_factor above. */ | |
| fixed dx3 = x3 - x0, dy3 = y3 - y0; | |
| float t; | |
| fixed d, dist; | |
| if ( (dx3 < 0 ? -dx3 : dx3) >= (dy3 < 0 ? -dy3 : dy3) ) | |
| { if ( dx3 == 0 ) return 0; /* degenerate */ | |
| t = (float)dy3 / (float)dx3; | |
| d = sqrt1t2xf(t); | |
| if ( ((dist = (fixed)(t * (x1 - x0)) - y1 + y0) < 0 ? | |
| -dist : dist) <= d && | |
| ((dist = (fixed)(t * (x2 - x0)) - y2 + y0) < 0 ? | |
| -dist : dist) <= d | |
| ) | |
| { /* Curve is flat enough. Add a line and exit. */ | |
| #ifdef DEBUG | |
| if ( gs_debug['u'] ) | |
| print_curve_point(x3, y3); | |
| #endif | |
| return gx_path_add_line(ppath, x3, y3); | |
| } | |
| } | |
| else | |
| { t = (float)dx3 / (float)dy3; | |
| d = sqrt1t2xf(t); | |
| if ( ((dist = (fixed)(t * (y1 - y0)) - x1 + x0) < 0 ? | |
| -dist : dist) <= d && | |
| ((dist = (fixed)(t * (y2 - y0)) - x2 + x0) < 0 ? | |
| -dist : dist) <= d | |
| ) | |
| { /* Curve is flat enough. Add a line and exit. */ | |
| #ifdef DEBUG | |
| if ( gs_debug['u'] ) | |
| print_curve_point(x3, y3); | |
| #endif | |
| return gx_path_add_line(ppath, x3, y3); | |
| } | |
| } | |
| } | |
| /* Curve isn't flat enough. Break into two pieces and recur. */ | |
| /* Algorithm is from "The Beta2-split: A special case of the */ | |
| /* Beta-spline Curve and Surface Representation," B. A. Barsky */ | |
| /* and A. D. DeRose, IEEE, 1985, courtesy of Crispin Goswell. */ | |
| #define midpoint(a,b) arith_rshift((a) +(b), 1) | |
| { fixed x01 = midpoint(x0, x1), y01 = midpoint(y0, y1); | |
| fixed x12 = midpoint(x1, x2), y12 = midpoint(y1, y2); | |
| fixed x02 = midpoint(x01, x12), y02 = midpoint(y01, y12); | |
| int code; | |
| /* Update x/y1, x/y2, and x/y0 now for the second half. */ | |
| x2 = midpoint(x2, x3), y2 = midpoint(y2, y3); | |
| x1 = midpoint(x12, x2), y1 = midpoint(y12, y2); | |
| code = flatten_curve( | |
| ppath, | |
| x01, y01, x02, y02, | |
| (x0 = midpoint(x02, x1)), | |
| (y0 = midpoint(y02, y1))); | |
| if ( code < 0 ) return code; | |
| } | |
| goto top; | |
| } |