import com.anotherbigidea.flash.movie.Shape; import java.awt.geom.CubicCurve2D; import java.awt.geom.QuadCurve2D; import java.awt.geom.Point2D; /** *************************************************************************** Cubic Bezier approximation Approximates a cubic curve by converting the cubic curve into multiple quadratic curve segments. If the points on a (sub-divided) cubic curve are co-linear, a line segment is drawn instead. The code was ported from the SWF Ming library code, version 0.2a, "shape_cubic.c" (http://www.opaque.net/ming/) Double precision. @author Shazron Abdullah (shazron 'at' stormgate.com), Feb 2002 (Java port) Original code Copyright (C) 2001 Opaque Industries - http://www.opaque.net/ This library is free software; you can redistribute it and/or modify it under the terms of the GNU Lesser General Public License as published by the Free Software Foundation; either version 2.1 of the License, or (at your option) any later version. This library is distributed in the hope that it will be useful, but WITHOUT ANY WARRANTY; without even the implied warranty of MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the GNU Lesser General Public License for more details. You should have received a copy of the GNU Lesser General Public License along with this library; if not, write to the Free Software Foundation, Inc., 59 Temple Place, Suite 330, Boston, MA 02111-1307 USA or view it at: http://www.gnu.org/licenses/lgpl.txt *****************************************************************************/ public class Cubic2Quadratic { private static final double DOUBLE_EQUALITY_TOLERANCE = 1e-3; private static final double CUBIC_MIDPT_TOLERANCE = 1e-1; /** ************************************************************************** * * Gets the point that is the midpoint of a cubic curve. * * @param q a java.awt.geom.CubicCurve2D defining the cubic curve * @return the midpt of the cubic curve * ****************************************************************************/ public static Point2D.Double halfpointCubic(CubicCurve2D c) { return new Point2D.Double( (c.getX1() + 3*c.getCtrlX1() + 3*c.getCtrlX2() + c.getX2()) / 8, (c.getY1() + 3*c.getCtrlY1() + 3*c.getCtrlY2() + c.getY2()) / 8 ); } /** ************************************************************************** * * Gets the point that is the midpoint of a quadratic curve. * * @param q a java.awt.geom.QuadCurve2D defining the quadratic curve * @return the midpt of the quadratic curve * ****************************************************************************/ public static Point2D.Double halfpointQuadratic(QuadCurve2D q) { return new Point2D.Double( (q.getX1() + 2*q.getCtrlX() + q.getX2()) / 4, (q.getY1() + 2*q.getCtrlY() + q.getY2()) / 4 ); } /** ************************************************************************** * * Returns the distance error amount between two points. * ****************************************************************************/ public static double errorPoints(Point2D.Double a, Point2D.Double b) { return errorPoints(a.x, a.y, b.x, b.y); } /** ************************************************************************** * * Returns the distance error amount between two points. * * @param ax the X coordinate of the first point * @param ay the Y coordinate of the first point * @param bx the X coordinate of the second point * @param by the Y coordinate of the second point * ****************************************************************************/ public static double errorPoints(double ax, double ay, double bx, double by) { return Math.abs(ax-bx) + Math.abs(ay-by); } /** ************************************************************************** * * Subdivides a cubic curve, getting the left segment ending at a parametric * value. * * @param cnew (in/out) the CubicCurve2D that will hold the left subdivided segment * @param old (in) the CubicCurve2D that will be subdivided * @param t (in) the parametric value to get the left subdivided curve from * ****************************************************************************/ public static void subdivideCubicLeft(CubicCurve2D.Double cnew, CubicCurve2D.Double old, double t) { //SWF_assert(t>0.0 && t<1.0); if(!cubicEquals(cnew,old)) { cnew.setCurve(old.getP1(), old.getCtrlP1(), old.getCtrlP2(), old.getP2()); } Point2D.Double a = new Point2D.Double(cnew.getX1(), cnew.getY1()); Point2D.Double b = new Point2D.Double(cnew.getCtrlX1(), cnew.getCtrlY1()); Point2D.Double c = new Point2D.Double(cnew.getCtrlX2(), cnew.getCtrlY2()); Point2D.Double d = new Point2D.Double(cnew.getX2(), cnew.getY2()); d.x = t*c.x + (1.0-t)*d.x; d.y = t*c.y + (1.0-t)*d.y; c.x = t*b.x + (1.0-t)*c.x; c.y = t*b.y + (1.0-t)*c.y; b.x = t*a.x + (1.0-t)*b.x; b.y = t*a.y + (1.0-t)*b.y; d.x = t*c.x + (1.0-t)*d.x; d.y = t*c.y + (1.0-t)*d.y; c.x = t*b.x + (1.0-t)*c.x; c.y = t*b.y + (1.0-t)*c.y; d.x = t*c.x + (1.0-t)*d.x; d.y = t*c.y + (1.0-t)*d.y; cnew.setCurve(a,b,c,d); } /** ************************************************************************** * * Subdivides a cubic curve, getting the right segment starting at a parametric * value. * * @param cnew (in/out) the CubicCurve2D that will hold the right subdivided segment * @param old (in) the CubicCurve2D that will be subdivided * @param t (in) the parametric value to get the right subdivided curve from * ****************************************************************************/ public static void subdivideCubicRight(CubicCurve2D.Double cnew, CubicCurve2D.Double old, double t) { //SWF_assert(t>0.0 && t<1.0); if(!cubicEquals(cnew,old)) { cnew.setCurve(old.getP1(), old.getCtrlP1(), old.getCtrlP2(), old.getP2()); } Point2D.Double a = new Point2D.Double(cnew.getX1(), cnew.getY1()); Point2D.Double b = new Point2D.Double(cnew.getCtrlX1(), cnew.getCtrlY1()); Point2D.Double c = new Point2D.Double(cnew.getCtrlX2(), cnew.getCtrlY2()); Point2D.Double d = new Point2D.Double(cnew.getX2(), cnew.getY2()); a.x = t*a.x + (1.0-t)*b.x; a.y = t*a.y + (1.0-t)*b.y; b.x = t*b.x + (1.0-t)*c.x; b.y = t*b.y + (1.0-t)*c.y; c.x = t*c.x + (1.0-t)*d.x; c.y = t*c.y + (1.0-t)*d.y; a.x = t*a.x + (1.0-t)*b.x; a.y = t*a.y + (1.0-t)*b.y; b.x = t*b.x + (1.0-t)*c.x; b.y = t*b.y + (1.0-t)*c.y; a.x = t*a.x + (1.0-t)*b.x; a.y = t*a.y + (1.0-t)*b.y; cnew.setCurve(a,b,c,d); } /** ************************************************************************** * * Subdivides a cubic curve equally (at t=0.5) into two cubic curves, renders * the subdivided curves into the Shape provided. * * @return the number of quadratic curves used to render the cubic (includes * the count of any line segments used, also) * ****************************************************************************/ public static int subdivideCubic(Shape shape, CubicCurve2D.Double c) { CubicCurve2D.Double cnew = new CubicCurve2D.Double(); int nCurves; subdivideCubicLeft(cnew, c, 0.5); nCurves = approxCubic(shape, cnew); subdivideCubicRight(cnew, c, 0.5); nCurves += approxCubic(shape, cnew); return nCurves; } /** ************************************************************************** * * Returns true if the two CubicCurve2D objects' values are "equal" (falls within * the default tolerance), false if not. * ****************************************************************************/ public static boolean cubicEquals( CubicCurve2D a, CubicCurve2D b) { return ( dEquals(a.getP1(),b.getP1()) && dEquals(a.getCtrlP1(),b.getCtrlP1()) && dEquals(a.getCtrlP2(),b.getCtrlP2()) && dEquals(a.getP2(),b.getP2()) ); } /** ************************************************************************** * * Approximates a cubic bezier curve with quadratic bezier curve segments (and * line segments, if the points in a cubic curve are co-linear). Renders the * quadratic curves and line segments into the Shape provided. * * @param shape a com.anotherbigidea.flash.movie.Shape to render the cubic curve into * @param cc a java.awt.geom.CubicCurve2D object, that defines the Cubic Bezier curve to draw * * @return the number of quadratic curves used to render the cubic (includes * the count of any line segments used, also) * ****************************************************************************/ public static int approxCubic(Shape shape, CubicCurve2D.Double c) { QuadCurve2D.Double q = new QuadCurve2D.Double(); double cx, cy, qx, qy; if( dEquals(c.getCtrlP1(), c.getP1()) ) { q.setCurve(c.getP1(), c.getCtrlP2(), c.getP2()); } else if( dEquals(c.getP2(),c.getCtrlP2()) ) { q.setCurve(c.getP1(), c.getCtrlP1(), c.getP2()); } else if((c.getX1()-c.getCtrlX1())*(c.getCtrlX2()-c.getCtrlX1())+(c.getY1()-c.getCtrlY1())*(c.getCtrlY2()-c.getCtrlY1()) >= 0 || (c.getCtrlX1()-c.getCtrlX2())*(c.getX2()-c.getCtrlX2())+(c.getCtrlY1()-c.getCtrlY2())*(c.getY2()-c.getCtrlY2()) >= 0) { /* make sure that angles B and C are obtuse, so that outside edges meet on the right side */ return subdivideCubic(shape, c); } else { double bcrossa = c.getCtrlX1()*c.getY1() - c.getX1()*c.getCtrlY1(); double ccrossd = c.getCtrlX2()*c.getY2() - c.getX2()*c.getCtrlY2(); double denom = (c.getY1()-c.getCtrlY1())*(c.getX2()-c.getCtrlX2()) - (c.getX1()-c.getCtrlX1())*(c.getY2()-c.getCtrlY2()); if (denom == 0) { /* XXX - they're collinear?? */ shape.line(c.getX2(), c.getY2()); return 1; } Point2D.Double cp = new Point2D.Double( ((c.getX2()-c.getCtrlX2())*bcrossa + (c.getCtrlX1()-c.getX1())*ccrossd) / denom, ((c.getY2()-c.getCtrlY2())*bcrossa + (c.getCtrlY1()-c.getY1())*ccrossd) / denom ); q.setCurve(c.getP1(), cp, c.getP2()); } Point2D.Double hpc = halfpointCubic(c); Point2D.Double hpq = halfpointQuadratic(q); if(errorPoints(hpc, hpq) > CUBIC_MIDPT_TOLERANCE) // midpt distance tolerance amount { return subdivideCubic(shape, c); } else { /* draw quadratic w/ control point at intersection of outside edges */ shape.curve(q.getX2(), q.getY2(), q.getCtrlX(), q.getCtrlY()); return 1; } } /** ************************************************************************** * * Renders the cubic bezier curve defined by the CubicCurve object - into * the Shape object provided. * * @param shape a com.anotherbigidea.flash.movie.Shape to render the cubic curve into * @param cc a java.awt.geom.CubicCurve2D object, that defines the Cubic Bezier curve to draw * * @return the number of quadratic curves used to render the cubic (includes * the count of any line segments used, also) * ****************************************************************************/ public static int renderCubicBezier(Shape shp, CubicCurve2D cc) { return renderCubicBezier(shp, cc.getX1(), cc.getY1(), cc.getCtrlX1(), cc.getCtrlY1(), cc.getCtrlX2(), cc.getCtrlY2(), cc.getX2(), cc.getY2()); } /** ************************************************************************** * * Renders the cubic bezier curve defined by the points a, b, c, d - into * the Shape object provided. * * @param shape a com.anotherbigidea.flash.movie.Shape to render the cubic curve into * @param ax the X coordinate of the start point * @param ay the Y coordinate of the start point * @param bx the X coordinate of the first control point * @param by the Y coordinate of the first control point * @param cx the X coordinate of the second control point * @param cy the Y coordinate of the second control point * @param dx the X coordinate of the end point * @param dy the Y coordinate of the end point * * @return the number of quadratic curves used to render the cubic (includes * the count of any line segments used, also) * ****************************************************************************/ public static int renderCubicBezier(Shape shape, double ax, double ay, double bx, double by, double cx, double cy, double dx, double dy) { /* compute coefficients */ double a1x = -ax + 3*bx - 3*cx + dx; double a1y = -ay + 3*by - 3*cy + dy; double a2x = ax - 2*bx + cx; double a2y = ay - 2*by + cy; double a3x = -ax + bx; double a3y = -ay + by; double a = 6*(a2x*a1y-a2y*a1x); double b = 6*(a3x*a1y-a3y*a1x); double c = 2*(a3x*a2y-a3y*a2x); /* First, chop at inflection points, where a*t^2 + b*t + c = 0 */ double d = b*b - 4*a*c; double t1 = 0.0, t2 = 1.0; int nCurves = 0; CubicCurve2D.Double pts = new CubicCurve2D.Double(ax,ay,bx,by,cx,cy,dx,dy); CubicCurve2D.Double cnew = new CubicCurve2D.Double(); if (d>0) { /* two roots */ t1 = (-b-Math.sqrt(d))/(2*a); t2 = (-b+Math.sqrt(d))/(2*a); if(a<0) { double tmp = t2; t2 = t1; t1 = tmp; } } else if(d==0) { /* singular root */ t1 = -b/(2*a); } /* use subdivision method to build t=0..t1, t=t1..t2, t=t2..1 curves */ if(t1 > 0.0 && t1 < 1.0) { subdivideCubicLeft(cnew, pts, t1); nCurves += approxCubic(shape, cnew); subdivideCubicRight(pts, pts, t1); t2 = (t2-t1)/(1-t1); } if(t2 > 0.0 && t2 < 1.0) { subdivideCubicLeft(cnew, pts, t2); nCurves += approxCubic(shape, cnew); subdivideCubicRight(pts, pts, t2); } nCurves += approxCubic(shape, pts); return nCurves; } /*/////////////////////////////////////////////////////////////////////////////// Miscellaneous helper functions. *//////////////////////////////////////////////////////////////////////////////// /** ************************************************************************** * * Returns true if the two Point2D objects' values are "equal" (falls within * the default tolerance) * ****************************************************************************/ public static boolean dEquals( Point2D a, Point2D b ) { return dEquals(a, b, DOUBLE_EQUALITY_TOLERANCE); } /** ************************************************************************** * * Returns true if the difference between the values of the two Point2D objects * are within the tolerance value, false if not. * ****************************************************************************/ public static boolean dEquals( Point2D a, Point2D b, double tolerance ) { return ( Math.abs(a.getX() - b.getX()) <= tolerance && Math.abs(a.getY() - b.getY()) <= tolerance); } }