area.java

linux下建立JAVA虚拟机的源码KAFFE

      for (int i = 0; i < allpaths.size(); i++)
        {
	  Segment v = (Segment) allpaths.elementAt(i);
	  Segment start = v;

	  IteratorSegment is = new IteratorSegment();
	  is.type = SEG_MOVETO;
	  is.coords[0] = start.P1.getX();
	  is.coords[1] = start.P1.getY();
	  segments.add(is);

	  do
	    {
	      is = new IteratorSegment();
	      is.type = v.pathIteratorFormat(is.coords);
	      segments.add(is);
	      v = v.next;
	    }
	  while (v != start);

	  is = new IteratorSegment();
	  is.type = SEG_CLOSE;
	  segments.add(is);
        }
    }

    public int currentSegment(double[] coords)
    {
      IteratorSegment s = (IteratorSegment) segments.elementAt(index);
      if (at != null)
	at.transform(s.coords, 0, coords, 0, 3);
      else
	for (int i = 0; i < 6; i++)
	  coords[i] = s.coords[i];
      return (s.type);
    }

    public int currentSegment(float[] coords)
    {
      IteratorSegment s = (IteratorSegment) segments.elementAt(index);
      double[] d = new double[6];
      if (at != null)
        {
	  at.transform(s.coords, 0, d, 0, 3);
	  for (int i = 0; i < 6; i++)
	    coords[i] = (float) d[i];
        }
      else
	for (int i = 0; i < 6; i++)
	  coords[i] = (float) s.coords[i];
      return (s.type);
    }

    // Note that the winding rule should not matter here,
    // EVEN_ODD is chosen because it renders faster.
    public int getWindingRule()
    {
      return (PathIterator.WIND_EVEN_ODD);
    }

    public boolean isDone()
    {
      return (index >= segments.size());
    }

    public void next()
    {
      index++;
    }
  }

  /**
   * Performs the fundamental task of the Weiler-Atherton algorithm,
   * traverse a list of segments, for each segment:
   * Follow it, removing segments from the list and switching paths
   * at each node. Do so until the starting segment is reached.
   *
   * Returns a Vector of the resulting paths.
   */
  private Vector weilerAtherton(Vector segments)
  {
    Vector paths = new Vector();
    while (segments.size() > 0)
      {
	// Iterate over the path
	Segment start = (Segment) segments.elementAt(0);
	Segment s = start;
	do
	  {
	    segments.remove(s);
	    if (s.node != null)
	      { // switch over
		s.next = s.node;
		s.node = null;
	      }
	    s = s.next; // continue
	  }
	while (s != start);

	paths.add(start);
      }
    return paths;
  }

  /**
   * A small wrapper class to store intersection points
   */
  private class Intersection
  {
    Point2D p; // the 2D point of intersection
    double ta; // the parametric value on a
    double tb; // the parametric value on b
    Segment seg; // segment placeholder for node setting

    public Intersection(Point2D p, double ta, double tb)
    {
      this.p = p;
      this.ta = ta;
      this.tb = tb;
    }
  }

  /**
   * Returns the recursion depth necessary to approximate the
   * curve by line segments within the error RS_EPSILON.
   *
   * This is done with Wang's formula:
   * L0 = max{0<=i<=N-2}(|xi - 2xi+1 + xi+2|,|yi - 2yi+1 + yi+2|)
   * r0 = log4(sqrt(2)*N*(N-1)*L0/8e)
   * Where e is the maximum distance error (RS_EPSILON)
   */
  private int getRecursionDepth(CubicSegment curve)
  {
    double x0 = curve.P1.getX();
    double y0 = curve.P1.getY();

    double x1 = curve.cp1.getX();
    double y1 = curve.cp1.getY();

    double x2 = curve.cp2.getX();
    double y2 = curve.cp2.getY();

    double x3 = curve.P2.getX();
    double y3 = curve.P2.getY();

    double L0 = Math.max(Math.max(Math.abs(x0 - 2 * x1 + x2),
                                  Math.abs(x1 - 2 * x2 + x3)),
                         Math.max(Math.abs(y0 - 2 * y1 + y2),
                                  Math.abs(y1 - 2 * y2 + y3)));

    double f = Math.sqrt(2) * 6.0 * L0 / (8.0 * RS_EPSILON);

    int r0 = (int) Math.ceil(Math.log(f) / Math.log(4.0));
    return (r0);
  }

  /**
   * Performs recursive subdivision:
   * @param c1 - curve 1
   * @param c2 - curve 2
   * @param depth1 - recursion depth of curve 1
   * @param depth2 - recursion depth of curve 2
   * @param t1 - global parametric value of the first curve's starting point
   * @param t2 - global parametric value of the second curve's starting point
   * @param w1 - global parametric length of curve 1
   * @param w2 - global parametric length of curve 2
   *
   * The final four parameters are for keeping track of the parametric
   * value of the curve. For a full curve t = 0, w = 1, w is halved with
   * each subdivision.
   */
  private void recursiveSubdivide(CubicCurve2D c1, CubicCurve2D c2,
                                  int depth1, int depth2, double t1,
                                  double t2, double w1, double w2)
  {
    boolean flat1 = depth1 <= 0;
    boolean flat2 = depth2 <= 0;

    if (flat1 && flat2)
      {
	double xlk = c1.getP2().getX() - c1.getP1().getX();
	double ylk = c1.getP2().getY() - c1.getP1().getY();

	double xnm = c2.getP2().getX() - c2.getP1().getX();
	double ynm = c2.getP2().getY() - c2.getP1().getY();

	double xmk = c2.getP1().getX() - c1.getP1().getX();
	double ymk = c2.getP1().getY() - c1.getP1().getY();
	double det = xnm * ylk - ynm * xlk;

	if (det + 1.0 == 1.0)
	  return;

	double detinv = 1.0 / det;
	double s = (xnm * ymk - ynm * xmk) * detinv;
	double t = (xlk * ymk - ylk * xmk) * detinv;
	if ((s < 0.0) || (s > 1.0) || (t < 0.0) || (t > 1.0))
	  return;

	double[] temp = new double[2];
	temp[0] = t1 + s * w1;
	temp[1] = t2 + t * w1;
	cc_intersections.add(temp);
	return;
      }

    CubicCurve2D.Double c11 = new CubicCurve2D.Double();
    CubicCurve2D.Double c12 = new CubicCurve2D.Double();
    CubicCurve2D.Double c21 = new CubicCurve2D.Double();
    CubicCurve2D.Double c22 = new CubicCurve2D.Double();

    if (! flat1 && ! flat2)
      {
	depth1--;
	depth2--;
	w1 = w1 * 0.5;
	w2 = w2 * 0.5;
	c1.subdivide(c11, c12);
	c2.subdivide(c21, c22);
	if (c11.getBounds2D().intersects(c21.getBounds2D()))
	  recursiveSubdivide(c11, c21, depth1, depth2, t1, t2, w1, w2);
	if (c11.getBounds2D().intersects(c22.getBounds2D()))
	  recursiveSubdivide(c11, c22, depth1, depth2, t1, t2 + w2, w1, w2);
	if (c12.getBounds2D().intersects(c21.getBounds2D()))
	  recursiveSubdivide(c12, c21, depth1, depth2, t1 + w1, t2, w1, w2);
	if (c12.getBounds2D().intersects(c22.getBounds2D()))
	  recursiveSubdivide(c12, c22, depth1, depth2, t1 + w1, t2 + w2, w1, w2);
	return;
      }

    if (! flat1)
      {
	depth1--;
	c1.subdivide(c11, c12);
	w1 = w1 * 0.5;
	if (c11.getBounds2D().intersects(c2.getBounds2D()))
	  recursiveSubdivide(c11, c2, depth1, depth2, t1, t2, w1, w2);
	if (c12.getBounds2D().intersects(c2.getBounds2D()))
	  recursiveSubdivide(c12, c2, depth1, depth2, t1 + w1, t2, w1, w2);
	return;
      }

    depth2--;
    c2.subdivide(c21, c22);
    w2 = w2 * 0.5;
    if (c1.getBounds2D().intersects(c21.getBounds2D()))
      recursiveSubdivide(c1, c21, depth1, depth2, t1, t2, w1, w2);
    if (c1.getBounds2D().intersects(c22.getBounds2D()))
      recursiveSubdivide(c1, c22, depth1, depth2, t1, t2 + w2, w1, w2);
  }

  /**
   * Returns a set of interesections between two Cubic segments
   * Or null if no intersections were found.
   *
   * The method used to find the intersection is recursive midpoint
   * subdivision. Outline description:
   *
   * 1) Check if the bounding boxes of the curves intersect,
   * 2) If so, divide the curves in the middle and test the bounding
   * boxes again,
   * 3) Repeat until a maximum recursion depth has been reached, where
   * the intersecting curves can be approximated by line segments.
   *
   * This is a reasonably accurate method, although the recursion depth
   * is typically around 20, the bounding-box tests allow for significant
   * pruning of the subdivision tree.
   * 
   * This is package-private to avoid an accessor method.
   */
  Intersection[] cubicCubicIntersect(CubicSegment curve1, CubicSegment curve2)
  {
    Rectangle2D r1 = curve1.getBounds();
    Rectangle2D r2 = curve2.getBounds();

    if (! r1.intersects(r2))
      return null;

    cc_intersections = new Vector();
    recursiveSubdivide(curve1.getCubicCurve2D(), curve2.getCubicCurve2D(),
                       getRecursionDepth(curve1), getRecursionDepth(curve2),
                       0.0, 0.0, 1.0, 1.0);

    if (cc_intersections.size() == 0)
      return null;

    Intersection[] results = new Intersection[cc_intersections.size()];
    for (int i = 0; i < cc_intersections.size(); i++)
      {
	double[] temp = (double[]) cc_intersections.elementAt(i);
	results[i] = new Intersection(curve1.evaluatePoint(temp[0]), temp[0],
	                              temp[1]);
      }
    cc_intersections = null;
    return (results);
  }

  /**
   * Returns the intersections between a line and a quadratic bezier
   * Or null if no intersections are found1
   * This is done through combining the line's equation with the
   * parametric form of the Bezier and solving the resulting quadratic.
   * This is package-private to avoid an accessor method.
   */
  Intersection[] lineQuadIntersect(LineSegment l, QuadSegment c)
  {
    double[] y = new double[3];
    double[] x = new double[3];
    double[] r = new double[3];
    int nRoots;
    double x0 = c.P1.getX();
    double y0 = c.P1.getY();
    double x1 = c.cp.getX();
    double y1 = c.cp.getY();
    double x2 = c.P2.getX();
    double y2 = c.P2.getY();

    double lx0 = l.P1.getX();
    double ly0 = l.P1.getY();
    double lx1 = l.P2.getX();
    double ly1 = l.P2.getY();
    double dx = lx1 - lx0;
    double dy = ly1 - ly0;

    // form r(t) = y(t) - x(t) for the bezier
    y[0] = y0;
    y[1] = 2 * (y1 - y0);
    y[2] = (y2 - 2 * y1 + y0);

    x[0] = x0;
    x[1] = 2 * (x1 - x0);
    x[2] = (x2 - 2 * x1 + x0);

    // a point, not a line
    if (dy == 0 && dx == 0)
      return null;

    // line on y axis
    if (dx == 0 || (dy / dx) > 1.0)
      {
	double k = dx / dy;
	x[0] -= lx0;
	y[0] -= ly0;
	y[0] *= k;
	y[1] *= k;
	y[2] *= k;
      }
    else
      {
	double k = dy / dx;
	x[0] -= lx0;
	y[0] -= ly0;
	x[0] *= k;
	x[1] *= k;
	x[2] *= k;
      }

    for (int i = 0; i < 3; i++)
      r[i] = y[i] - x[i];

    if ((nRoots = QuadCurve2D.solveQuadratic(r)) > 0)
      {
	Intersection[] temp = new Intersection[nRoots];
	int intersections = 0;
	for (int i = 0; i < nRoots; i++)
	  {
	    double t = r[i];
	    if (t >= 0.0 && t <= 1.0)
	      {
		Point2D p = c.evaluatePoint(t);

		// if the line is on an axis, snap the point to that axis.
		if (dx == 0)
		  p.setLocation(lx0, p.getY());
		if (dy == 0)
		  p.setLocation(p.getX(), ly0);

		if (p.getX() <= Math.max(lx0, lx1)
		    && p.getX() >= Math.min(lx0, lx1)
		    && p.getY() <= Math.max(ly0, ly1)
		    && p.getY() >= Math.min(ly0, ly1))
		  {
		    double lineparameter = p.distance(l.P1) / l.P2.distance(l.P1);
		    temp[i] = new Intersection(p, lineparameter, t);
		    intersections++;
		  }
	      }
	    else
	      temp[i] = null;
	  }
	if (intersections == 0)
	  return null;

	Intersection[] rValues = new Intersection[intersections];

	for (int i = 0; i < nRoots; i++)
	  if (temp[i] != null)
	    rValues[--intersections] = temp[i];
	return (rValues);
      }
    return null;
  }

  /**
   * Returns the intersections between a line and a cubic segment
   * This is done through combining the line's equation with the
   * parametric form of the Bezier and solving the resulting quadratic.
   * This is package-private to avoid an accessor method. 
   */
  Intersection[] lineCubicIntersect(LineSegment l, CubicSegment c)
  {
    double[] y = new double[4];
    double[] x = new double[4];
    double[] r = new double[4];
    int nRoots;
    double x0 = c.P1.getX();
    double y0 = c.P1.getY();
    double x1 = c.cp1.getX();
    double y1 = c.cp1.getY();
    double x2 = c.cp2.getX();
    double y2 = c.cp2.getY();
    double x3 = c.P2.getX();
    double y3 = c.P2.getY();

    double lx0 = l.P1.getX();
    double ly0 = l.P1.getY();
    double lx1 = l.P2.getX();
    double ly1 = l.P2.getY();
    double dx = lx1 - lx0;
    double dy = ly1 - ly0;

    // form r(t) = y(t) - x(t) for the bezier
    y[0] = y0;
    y[1] = 3 * (y1 - y0);
    y[2] = 3 * (y2 + y0 - 2 * y1);
    y[3] = y3 - 3 * y2 + 3 * y1 - y0;

    x[0] = x0;
    x[1] = 3 * (x1 - x0);
    x[2] = 3 * (x2 + x0 - 2 * x1);
    x[3] = x3 - 3 * x2 + 3 * x1 - x0;

    // a point, not a line
    if (dy == 0 && dx == 0)
      return null;

    // line on y axis
    if (dx == 0 || (dy / dx) > 1.0)
      {
	double k = dx / dy;
	x[0] -= lx0;
	y[0] -= ly0;
	y[0] *= k;
	y[1] *= k;
	y[2] *= k;
	y[3] *= k;
      }
    else
      {
	double k = dy / dx;
	x[0] -= lx0;
	y[0] -= ly0;
	x[0] *= k;
	x[1] *= k;
	x[2] *= k;
	x[3] *= k;
      }
    for (int i = 0; i < 4; i++)
      r[i] = y[i] - x[i];

    if ((nRoots = CubicCurve2D.solveCubic(r)) > 0)
      {
	Intersection[] temp = new Intersection[nRoots];
	int intersections = 0;
	for (int i = 0; i < nRoots; i++)
	  {
	    double t = r[i];
	    if (t >= 0.0 && t <= 1.0)
	      {
		// if the line is on an axis, snap the point to that axis.
		Point2D p = c.evaluatePoint(t);
		if (dx == 0)
		  p.setLocation(lx0, p.getY());
		if (dy == 0)
		  p.setLocation(p.getX(), ly0);

		if (p.getX() <= Math.max(lx0, lx1)
		    && p.getX() >= Math.min(lx0, lx1)
		    && p.getY() <= Math.max(ly0, ly1)
		    && p.getY() >= Math.min(ly0, ly1))
		  {
		    double lineparameter = p.distance(l.P1) / l.P2.distance(l.P1);
		    temp[i] = new Intersection(p, lineparameter, t);
		    intersections++;
		  }
	      }
	    else
	      temp[i] = null;
	  }

	if (intersections == 0)
	  return null;

	Intersection[] rValues = new Intersection[intersections];
	for (int i = 0; i < nRoots; i++)
	  if (temp[i] != null)
	    rValues[--intersections] = temp[i];
	return (rValues);
      }
    return null;
  }

  /**
   * Returns the intersection between two lines, or null if there is no
   * intersection.
   * This is package-private to avoid an accessor method.
   */
  Intersection linesIntersect(LineSegment a, LineSegment b)
  {
    Point2D P1 = a.P1;
    Point2D P2 = a.P2;
    Point2D P3 = b.P1;
    Point2D P4 = b.P2;

    if (! Line2D.linesIntersect(P1.getX(), P1.getY(), P2.getX(), P2.getY(),
                                P3.getX(), P3.getY(), P4.getX(), P4.getY()))