⟦a5f888edb⟧

TextFile

/* Copyright (C) 1989 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 "gx.h"
#include "gserrors.h"
#include "gxfixed.h"
#include "gzpath.h"

/* Forward declarations */
private 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 in the order */
/* xmin, ymin, xmax, ymax. */
int
gx_path_bbox(gx_path *ppath, gs_fixed_rect *pbox)
{	if ( ppath->first_subpath == 0 )
	  return_error(gs_error_nocurrentpoint);
	/* 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.xmin = box.xmax = pseg->pt.x;
			box.ymin = box.ymax = pseg->pt.y;
		   }
		else
		   {	box = ppath->bbox;
			pseg = pseg->next;
		   }
/* Macro for adjusting the bounding box when adding a point */
#define adjust_bbox(x, y)\
  if ( (x) < box.xmin ) box.xmin = (x);\
  else if ( (x) > box.xmax ) box.xmax = (x);\
  if ( (y) < box.ymin ) box.ymin = (y);\
  else if ( (y) > box.ymax ) box.ymax = (y)
		while ( pseg )
		   {	switch ( pseg->type )
			   {
			case s_curve:
#define pcurve ((curve_segment *)pseg)
				adjust_bbox(pcurve->p1.x, pcurve->p1.y);
				adjust_bbox(pcurve->p2.x, pcurve->p2.y);
#undef pcurve
			default:
				adjust_bbox(pseg->pt.x, pseg->pt.y);
			   }
			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 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->xmin = x0, pbox->xmax = x2;
			else
				pbox->xmin = x2, pbox->xmax = x0;
			if ( y0 < y2 )
				pbox->ymin = y0, pbox->ymax = y2;
			else
				pbox->ymin = y2, pbox->ymax = 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.xmin <= x0 && x1 <= ppath->cbox.xmax) :
			(ppath->cbox.xmin <= x1 && x0 <= ppath->cbox.xmax)) &&
		(y0 <= y1 ?
			(ppath->cbox.ymin <= y0 && y1 <= ppath->cbox.ymax) :
			(ppath->cbox.ymin <= y1 && y0 <= ppath->cbox.ymax));
}

/* Copy a path */
int
gx_path_copy(gx_path *ppath_old, gx_path *ppath)
{	return copy_path(ppath_old, ppath, gx_path_add_curve);
}

/* Define magic quantities used for flatness checking. */
private fixed flat_factor_1;
private float flat_factor_2;

/* 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));
	flat_factor_1 = ff;
	flat_factor_2 = ff * ff;
	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, y0;
top:	x0 = ppath->position.x;
	y0 = ppath->position.y;
#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=0, we just test abs(xp-x0) > F.) */
		/* 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. */
		if ( x3 == x0 )		/* i.e. dx == 0 */
		   {	fixed diff;
			if (	((diff = x1 - x0) >= 0 ? diff : -diff) <= flat_factor_1 &&
				((diff = x2 - x0) >= 0 ? diff : -diff) <= flat_factor_1
			   )
			   {	/* 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
		   {	float t = (float)(y3 - y0) / (float)(x3 - x0);
			float d = (1 + t * t) * flat_factor_2;
			float dist = t * (x1 - x0) - (float)(y1 - y0);
			if (	dist * dist <= d &&
				((dist = t * (x2 - x0) - (float)(y2 - y0)),
				 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. */
	   {	fixed x01 = (x0 + x1) >> 1, y01 = (y0 + y1) >> 1;
		fixed x12 = (x1 + x2) >> 1, y12 = (y1 + y2) >> 1;
		fixed x23 = (x2 + x3) >> 1, y23 = (y2 + y3) >> 1;
		int code = flatten_curve(
			ppath,
			x01, y01,
			(x01 + x12) >> 1, (y01 + y12) >> 1,
			x12 + ((x0 - x1 - x2 + x3) >> 3),
			y12 + ((y0 - y1 - y2 + y3) >> 3));
		if ( code < 0 ) return code;
		/* ppath->position has been updated, so.... */
		x1 = (x12 + x23) >> 1, y1 = (y12 + y23) >> 1;
		x2 = x23, y2 = y23;
	   }
	goto top;
}

/* ------ Curve utilities ------ */

/* Evaluate a curve at a point */
int
gx_curve_eval(gs_fixed_point *p0, gs_point pabc[3],
  floatp t, gs_fixed_point *pp)
{	pp->x = float2fixed(((pabc[0].x * t + pabc[1].x) * t + pabc[2].x) * t) + p0->x;
	pp->y = float2fixed(((pabc[0].y * t + pabc[1].y) * t + pabc[2].y) * t) + p0->y;
	return 0;
}
DataMuseum.dk

DKUUG/EUUG Conference tapes

⟦a5f888edb⟧ TextFile

Derivation

TextFile
