#ifndef lint static char sccsid[] = "@(#)bezier.c 9.1 87/11/05 Copyright 1985 Sun Micro"; #endif /* * Copyright (c) 1985 by Sun Microsystems, Inc. */ /*- Routines for dealing with beziers bezier.c, Sat Apr 5 13:40:49 1986 James Gosling, Sun Microsystems */ #ifdef REF #include #include #endif #include "cscript.h" static frbezier(gc, offx, offy, x0, y0, x1, y1, x2, y2, x3, y3) register struct graphics_context *gc; fract offx, offy, x0, y0, x1, y1, x2, y2, x3, y3; { { register fract cx, cy; /* find center point */ cx = (x0 >> 2) + (x1 >> 2) + (x2 >> 2) + (x3 >> 2); cy = (y0 >> 2) + (y1 >> 2) + (y2 >> 2) + (y3 >> 2); /* * translate to being around the center (for range reduction) */ x0 -= cx; y0 -= cy; x1 -= cx; y1 -= cy; x2 -= cx; y2 -= cy; x3 -= cx; y3 -= cy; offx += cx; offy += cy; /* Find the "radius" of the set of points */ cx = x0; cy = x0; if (x0 < cx) cx = x0; if (x1 < cx) cx = x1; if (x2 < cx) cx = x2; if (x3 < cx) cx = x3; if (x0 > cy) cy = x0; if (x1 > cy) cy = x1; if (x2 > cy) cy = x2; if (x3 > cy) cy = x3; if (y0 < cx) cx = y0; if (y1 < cx) cx = y1; if (y2 < cx) cx = y2; if (y3 < cx) cx = y3; if (y0 > cy) cy = y0; if (y1 > cy) cy = y1; if (y2 > cy) cy = y2; if (y3 > cy) cy = y3; if (cx < 0) cx = -cx; if (cy < 0) cy = -cy; if (cy > cx) cx = cy; /* Finally! The maximum absolute delta */ if (cx < fracti(2)) /* Small curve, use straight line */ goto degenerate; if (cx >= fracti(170)) /* Big enough to cause overflow */ goto subdivide_curve; cx = x1 - x2; cy = x0 - x3; if ((cx ^ cy) < 0) /* Sign flip: twist */ goto subdivide_curve; if (abs(cx) >= abs(cy)) /* Bellows outward */ goto subdivide_curve; if (cy) { cx = frdiv(cx, cy); if (cx < fractf(.2) || cx > fractf(.45)) goto subdivide_curve; /* Not close enough to a parabola */ } else if (cx != 0) goto subdivide_curve; cx = y1 - y2; cy = y0 - y3; if ((cx ^ cy) < 0) /* Sign flip: twist */ goto subdivide_curve; if (abs(cx) >= abs(cy)) /* Bellows outward */ goto subdivide_curve; if (cy) { cx = frdiv(cx, cy); if (cx < fractf(.2) || cx > fractf(.45)) goto subdivide_curve; /* Not close enough to a parabola */ } else if (cx != 0) goto subdivide_curve; /* Thanks to microsoft!nathanm for finding a bug with inflection points, and suggesting * the following fix. His explanation follows. Take it away, Nathan... * * [microsoft!nathanm] * At an inflection point, the first and second derivatives of R * will be parallel vectors, and thus their cross product will be zero. * To see if a given bezier contains such a point, evaluate the cross * product at t = 0 and t = 1. If it changes sign, then subdivide the * bezier. At some point, the inflection point will be contained in a * very small segment of the bezier, and the code will approximate that * segment with a straight line. */ cx = frmul(x1 - x0, y0 + y2 - (y1 << 1)) - /* c' x c'' |t=0 */ frmul(y1 - y0, x0 + x2 - (x1 << 1)); cy = frmul(x3 - x2, y1 + y3 - (y2 << 1)) - /* c' x c'' |t=1 */ frmul(y3 - y2, x1 + x3 - (x2 << 1)); if ((cx ^ cy) < 0) goto subdivide_curve; /* segment contains an inflection point */ } { register fract dxa = x0 - x1, dya = y0 - y1, oa = frmul(x0, y1) - frmul(y0, x1), dxb = x2 - x3, dyb = y2 - y3, ob = frmul(x2, y3) - frmul(y2, x3), den = frmul(dya, dxb) - frmul(dyb, dxa); if (abs(den) > fracti(3)) { shape_point.x = frmul(frdiv(ob,den),dxa) - frmul(frdiv(oa,den),dxb); shape_point.y = abs(dxa) > abs(dxb) ? frdiv(oa + frmul(shape_point.x, dya), dxa) : frdiv(ob + frmul(shape_point.x, dyb), dxb); } else { shape_point.x = (x1 + x2) >> 1; shape_point.y = (y1 + y2) >> 1; } shape_point.x += offx; shape_point.y += offy; sh_frlineby(gc, fracti(1)); degenerate: shape_point.x = x3 + offx; shape_point.y = y3 + offy; sh_frlineby(gc, 0); } return; subdivide_curve: { register fract nx, ny; /* * sum of shifts rather than shift of sums to cope with possible * overflow */ nx = (x0 >> 3) + 3 * (x1 >> 3) + 3 * (x2 >> 3) + (x3 >> 3); ny = (y0 >> 3) + 3 * (y1 >> 3) + 3 * (y2 >> 3) + (y3 >> 3); frbezier(gc, offx, offy, x0, y0, (x0 >> 1) + (x1 >> 1), (y0 >> 1) + (y1 >> 1), (x0 >> 2) + (x1 >> 1) + (x2 >> 2), (y0 >> 2) + (y1 >> 1) + (y2 >> 2), nx, ny); frbezier(gc, offx, offy, nx, ny, (x3 >> 2) + (x2 >> 1) + (x1 >> 2), (y3 >> 2) + (y2 >> 1) + (y1 >> 2), (x3 >> 1) + (x2 >> 1), (y3 >> 1) + (y2 >> 1), x3, y3); } } cs_flcurveto(gc, x1, y1, x2, y2, x3, y3) register struct graphics_context *gc; double x1, y1, x2, y2, x3, y3; { struct fpoint p0, p1, p2; p0 = gc->currentpoint; sh_fltransform(&gc->transform, x1, y1); p1 = shape_point; sh_fltransform(&gc->transform, x2, y2); p2 = shape_point; sh_fltransform(&gc->transform, x3, y3); frbezier(gc, 0, 0, p0.x, p0.y, p1.x, p1.y, p2.x, p2.y, shape_point.x, shape_point.y); } cs_frcurveto(gc, x1, y1, x2, y2, x3, y3) /* This is the wimp's version */ register struct graphics_context *gc; fract x1, y1, x2, y2, x3, y3; { struct fpoint p0, p1, p2; p0 = gc->currentpoint; sh_frtransform(&gc->transform, x1, y1); p1 = shape_point; sh_frtransform(&gc->transform, x2, y2); p2 = shape_point; sh_frtransform(&gc->transform, x3, y3); frbezier(gc, 0, 0, p0.x, p0.y, p1.x, p1.y, p2.x, p2.y, shape_point.x, shape_point.y); } cs_flrcurveto(gc, x1, y1, x2, y2, x3, y3) register struct graphics_context *gc; double x1, y1, x2, y2, x3, y3; { struct fpoint p0, p1, p2; p0 = gc->currentpoint; sh_fldtransform(&gc->transform, x1, y1); p1 = shape_point; sh_fldtransform(&gc->transform, x2, y2); p2 = shape_point; sh_fldtransform(&gc->transform, x3, y3); frbezier(gc, p0.x, p0.y, 0, 0, p1.x, p1.y, p2.x, p2.y, shape_point.x, shape_point.y); } cs_frrcurveto(gc, x1, y1, x2, y2, x3, y3) /* This is the wimp's version */ register struct graphics_context *gc; fract x1, y1, x2, y2, x3, y3; { struct fpoint p0, p1, p2; p0 = gc->currentpoint; sh_frdtransform(&gc->transform, x1, y1); p1 = shape_point; sh_frdtransform(&gc->transform, x2, y2); p2 = shape_point; sh_frdtransform(&gc->transform, x3, y3); frbezier(gc, p0.x, p0.y, 0, 0, p1.x, p1.y, p2.x, p2.y, shape_point.x, shape_point.y); }