001: /*
002: * $Id: GeomHelper.java,v 1.4 2002/04/05 05:49:14 skavish Exp $
003: *
004: * ===========================================================================
005: *
006: * The JGenerator Software License, Version 1.0
007: *
008: * Copyright (c) 2000 Dmitry Skavish (skavish@usa.net). All rights reserved.
009: *
010: * Redistribution and use in source and binary forms, with or without
011: * modification, are permitted provided that the following conditions are met:
012: *
013: * 1. Redistributions of source code must retain the above copyright
014: * notice, this list of conditions and the following disclaimer.
015: *
016: * 2. Redistributions in binary form must reproduce the above copyright
017: * notice, this list of conditions and the following disclaimer in
018: * the documentation and/or other materials provided with the
019: * distribution.
020: *
021: * 3. The end-user documentation included with the redistribution, if
022: * any, must include the following acknowlegement:
023: * "This product includes software developed by Dmitry Skavish
024: * (skavish@usa.net, http://www.flashgap.com/)."
025: * Alternately, this acknowlegement may appear in the software itself,
026: * if and wherever such third-party acknowlegements normally appear.
027: *
028: * 4. The name "The JGenerator" must not be used to endorse or promote
029: * products derived from this software without prior written permission.
030: * For written permission, please contact skavish@usa.net.
031: *
032: * 5. Products derived from this software may not be called "The JGenerator"
033: * nor may "The JGenerator" appear in their names without prior written
034: * permission of Dmitry Skavish.
035: *
036: * THIS SOFTWARE IS PROVIDED ``AS IS'' AND ANY EXPRESSED OR IMPLIED
037: * WARRANTIES, INCLUDING, BUT NOT LIMITED TO, THE IMPLIED WARRANTIES
038: * OF MERCHANTABILITY AND FITNESS FOR A PARTICULAR PURPOSE ARE
039: * DISCLAIMED. IN NO EVENT SHALL DMITRY SKAVISH OR THE OTHER
040: * CONTRIBUTORS BE LIABLE FOR ANY DIRECT, INDIRECT, INCIDENTAL,
041: * SPECIAL, EXEMPLARY, OR CONSEQUENTIAL DAMAGES (INCLUDING, BUT NOT
042: * LIMITED TO, PROCUREMENT OF SUBSTITUTE GOODS OR SERVICES; LOSS OF
043: * USE, DATA, OR PROFITS; OR BUSINESS INTERRUPTION) HOWEVER CAUSED AND
044: * ON ANY THEORY OF LIABILITY, WHETHER IN CONTRACT, STRICT LIABILITY,
045: * OR TORT (INCLUDING NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY OUT
046: * OF THE USE OF THIS SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF
047: * SUCH DAMAGE.
048: *
049: */
050:
051: package org.openlaszlo.iv.flash.util;
052:
053: import org.openlaszlo.iv.flash.api.*;
054:
055: import org.openlaszlo.iv.flash.cache.*;
056: import org.openlaszlo.iv.flash.url.*;
057:
058: import java.awt.geom.Rectangle2D;
059: import java.awt.geom.Point2D;
060: import java.awt.geom.AffineTransform;
061: import java.io.*;
062: import java.util.*;
063:
064: /**
065: * Geometric helper: AffineTransform, Rectangle and related stuff.
066: *
067: * @author Dmitry Skavish
068: */
069: public class GeomHelper {
070:
071: /**
072: * Creates new rectangle
073: *
074: * @return empty rectangle (everything zero)
075: */
076: public static Rectangle2D newRectangle() {
077: return new Rectangle2D.Double();
078: }
079:
080: /**
081: * Creates new rectangle
082: *
083: * @param x x coordinate
084: * @param y y coordinate
085: * @param w width of the rectangle
086: * @param h height of the rectangle
087: * @return new rectangle
088: */
089: public static Rectangle2D newRectangle(int x, int y, int w, int h) {
090: return new Rectangle2D.Double(x, y, w, h);
091: }
092:
093: /**
094: * Creates new rectangle
095: *
096: * @param x x coordinate
097: * @param y y coordinate
098: * @param w width of the rectangle
099: * @param h height of the rectangle
100: * @return new rectangle
101: */
102: public static Rectangle2D newRectangle(double x, double y,
103: double w, double h) {
104: return new Rectangle2D.Double((int) x, (int) y, (int) w,
105: (int) h);
106: }
107:
108: /**
109: * Transforms specified rectangle and return its bounds
110: *
111: * @param m matrix which is used to transform the rectangle
112: * @param src rectangle which is transformed
113: * @param dst destination rectangle which is used to hold the bounds
114: * @return destination rectangle
115: */
116: public static Rectangle2D calcBounds(AffineTransform m,
117: Rectangle2D src, Rectangle2D dst) {
118: double x0 = src.getMinX();
119: double y0 = src.getMinY();
120: double x1 = src.getMaxX();
121: double y1 = src.getMaxY();
122: double[] a = new double[] { x0, y0, // left, top
123: x1, y1, // right, bottom
124: x0, y1, // left, bottom
125: x1, y0 // right, top
126: };
127: m.transform(a, 0, a, 0, 4);
128: x0 = Math.min(Math.min(a[0], a[2]), Math.min(a[4], a[6]));
129: x1 = Math.max(Math.max(a[0], a[2]), Math.max(a[4], a[6]));
130: y0 = Math.min(Math.min(a[1], a[3]), Math.min(a[5], a[7]));
131: y1 = Math.max(Math.max(a[1], a[3]), Math.max(a[5], a[7]));
132: dst.setFrame(x0, y0, x1 - x0, y1 - y0);
133: return dst;
134: }
135:
136: /**
137: * Transforms specified rectangle and return its bounds
138: *
139: * @param m matrix which is used to transform the rectangle
140: * @param src rectangle which is transformed
141: * @return new rectangle which is used to hold the bounds
142: */
143: public static Rectangle2D calcBounds(AffineTransform m,
144: Rectangle2D src) {
145: return calcBounds(m, src, newRectangle());
146: }
147:
148: /**
149: * Adds one specified rectangle to another
150: *
151: * @param dst destination rectangle (can be null)
152: * @param src rectangle which is going to be added to destination one (can be null)
153: * @return destination rectangle
154: */
155: public static Rectangle2D add(Rectangle2D dst, Rectangle2D src) {
156: if (src == null)
157: return dst;
158: if (dst == null) {
159: dst = (Rectangle2D) src.clone();
160: } else {
161: dst.add(src);
162: }
163: return dst;
164: }
165:
166: /**
167: * Returns size of specified rectangle as if it were written to swf file
168: *
169: * @param r specified rectangle
170: * @return size of rectangle in bytes
171: */
172: public static int getSize(Rectangle2D r) {
173: int xmin = (int) r.getMinX();
174: int xmax = (int) r.getMaxX();
175: int ymin = (int) r.getMinY();
176: int ymax = (int) r.getMaxY();
177:
178: int nBits = Util.getMinBitsS(Util
179: .getMax(xmin, xmax, ymin, ymax));
180: int s = 5 + nBits * 4;
181: return (s + 7) / 8;
182: }
183:
184: /**
185: * Concatenate two matrix without modifying them
186: *
187: * @param m1 left matrix
188: * @param m2 right matrix
189: * @return result of concatenation of two matrix (new matrix)
190: */
191: public static AffineTransform concatenate(AffineTransform m1,
192: AffineTransform m2) {
193: AffineTransform res = (AffineTransform) m1.clone();
194: res.concatenate(m2);
195: return res;
196: }
197:
198: private static final double c1 = 10000.0;
199:
200: /**
201: * Discard 'scale' of the matrix
202: * <p>
203: * retrieve scale of the matrix and create new one which is descale
204: * of the first and then multiply them in right order
205: *
206: * @param m matrix to discard scale from, this matrix is modified
207: * @return same matrix but scale is 1
208: */
209: public static AffineTransform deScaleMatrix(AffineTransform m) {
210:
211: double scalex = 1.0;
212: double scaley = 1.0;
213:
214: double[] r = new double[] { 0, c1, 0, 0, c1, 0 };
215:
216: m.transform(r, 0, r, 0, 3);
217:
218: boolean mult = false;
219: double sz = getDist(r, 0);
220: if (Math.abs(sz - c1) > 1e-2) {
221: scaley = c1 / sz;
222: mult = true;
223: }
224: sz = getDist(r, 2);
225: if (Math.abs(sz - c1) > 1e-2) {
226: scalex = c1 / sz;
227: mult = true;
228: }
229:
230: if (mult) {
231: m.scale(scalex, scaley);
232: }
233: return m;
234: }
235:
236: /**
237: * Get values inverse to 'scale' of the matrix
238: * <p>
239: * retrieve inverse scale of the matrix
240: *
241: * @param m matrix to get inverse scale from
242: * @return array of x and y descale
243: */
244: public static double[] getMatrixScale(AffineTransform m) {
245:
246: double scalex = 1.0;
247: double scaley = 1.0;
248:
249: double[] r = new double[] { 0, c1, 0, 0, c1, 0 };
250:
251: m.transform(r, 0, r, 0, 3);
252:
253: double sz = getDist(r, 0);
254: if (Math.abs(sz - c1) > 1e-2) {
255: scaley = c1 / sz;
256: }
257: sz = getDist(r, 2);
258: if (Math.abs(sz - c1) > 1e-2) {
259: scalex = c1 / sz;
260: }
261: return new double[] { scalex, scaley };
262: }
263:
264: /**
265: * Discard 'rotate' of the matrix
266: * <p>
267: * retrieve scale and transform of the matrix and create new one from them
268: *
269: * @param m matrix to discard rotate from, this matrix is modified
270: * @return same matrix but without rotate
271: */
272: public static AffineTransform deRotateMatrix(AffineTransform m) {
273: if (m.getShearX() == 0.0 && m.getShearY() == 0.0)
274: return m;
275:
276: double scalex = 1.0;
277: double scaley = 1.0;
278:
279: double[] r = new double[] { 0, c1, 0, 0, c1, 0 };
280:
281: m.transform(r, 0, r, 0, 3);
282:
283: double sz = getDist(r, 0);
284: if (Math.abs(sz - c1) > 1e-2) {
285: scaley = sz / c1;
286: }
287: sz = getDist(r, 2);
288: if (Math.abs(sz - c1) > 1e-2) {
289: scalex = sz / c1;
290: }
291:
292: m.setTransform(scalex, 0, 0, scaley, m.getTranslateX(), m
293: .getTranslateY());
294: return m;
295: }
296:
297: /**
298: * Return distance between two points defined by the Rect
299: *
300: * @param r rectangle which defines two points
301: * @return distance
302: */
303: public static double getDist(Rectangle2D r) {
304: double dx = r.getWidth();
305: double dy = r.getHeight();
306: return Math.sqrt(dx * dx + dy * dy);
307: }
308:
309: /**
310: * Return distance between two points defined by array
311: *
312: * @param r 4 elements array which hold the points (x0,y0), (x1,y1)
313: * @return distance between two points
314: */
315: public static double getDist(double[] r) {
316: return getDist(r, 0);
317: }
318:
319: /**
320: * Return distance between two points defined by array
321: *
322: * @param r array which hold the points (x0,y0), (x1,y1)
323: * @param offset offset in the array
324: * @return distance between two points
325: */
326: public static double getDist(double[] r, int offset) {
327: double dx = r[offset + 2] - r[offset + 0];
328: double dy = r[offset + 3] - r[offset + 1];
329: return Math.sqrt(dx * dx + dy * dy);
330: }
331:
332: /**
333: * Transforms specified rect using specified matrix and
334: * returns rectangle which has width and height as of transformed one.
335: *
336: * @param m specified matrix
337: * @param r specified rectangle
338: * @return rectangle which has width and height as of transformed one.
339: */
340: public static Rectangle2D getTransformedSize(AffineTransform m,
341: Rectangle2D r) {
342: double[] a = new double[] { 0, r.getHeight(), 0, 0,
343: r.getWidth(), 0 };
344:
345: m.transform(a, 0, a, 0, 3);
346:
347: return newRectangle(0, 0, getDist(a, 2), getDist(a, 0));
348: }
349:
350: /**
351: * Quadratic Bezier interpolation
352: * <p>
353: * B(t) = P0*(1-t)^2 + P1*2*t*(1-t) + P2*t^2
354: *
355: * @param p0 first control point (anchor)
356: * @param p1 second control point (control)
357: * @param p2 third control point (anchor)
358: * @param t parameter from 0 to 1
359: * @return point on the curve corresponding given parameter
360: */
361: public static Point2D quadraticBezier(Point2D p0, Point2D p1,
362: Point2D p2, double t) {
363: double tt = t * t; // t^2
364: double t1 = 1 - t; // 1-t
365: double tt1 = t1 * t1; // (1-t)^2
366: double tt4 = 2 * t * t1; // 2*t*(1-t)
367:
368: double x = p0.getX() * tt1 + p1.getX() * tt4 + p2.getX() * tt;
369: double y = p0.getY() * tt1 + p1.getY() * tt4 + p2.getY() * tt;
370:
371: return new Point2D.Double(x, y);
372: }
373:
374: /**
375: * Cubic Bezier interpolation
376: * <p>
377: * B(t) = P0*(1-t)^3 + P1*3*t*(1-t)^2 + P2*3*t^2*(1-t) + P3*t^3
378: *
379: * @param p0 first control point
380: * @param p1 second control point
381: * @param p2 third control point
382: * @param p3 fourth control point
383: * @param t parameter from 0 to 1
384: * @return point on the curve corresponding given parameter
385: */
386: public static Point2D cubicBezier(Point2D p0, Point2D p1,
387: Point2D p2, Point2D p3, double t) {
388: double tt = t * t; // t^2
389: double ttt = tt * t; // t^3
390: double t1 = 1 - t; // 1-t
391: double tt1 = t1 * t1; // (1-t)^2
392: double tt2 = tt1 * t1; // (1-t)^3
393: double tt3 = 3 * t * tt1; // 3*t*(1-t)^2
394: double tt4 = 3 * tt * t1; // 3*t^2*(1-t)
395:
396: double x = p0.getX() * tt2 + p1.getX() * tt3 + p2.getX() * tt4
397: + p3.getX() * ttt;
398: double y = p0.getY() * tt2 + p1.getY() * tt3 + p2.getY() * tt4
399: + p3.getY() * ttt;
400:
401: return new Point2D.Double(x, y);
402: }
403:
404: /**
405: * Converts qubic bezier to quadratic one with some approximation
406: * <P>
407: * Used the following algorithm by Jens Alfke:<BR>
408: * James Smith writes:
409: * <P>
410: * <LI>
411: * <I> Can anyone show me a way to convert a Bezier cubic curve to a quadratic spline?
412: * Is this a trivial conversion?
413: * Can this conversion (if possible) be done to produce an identical curve from the Bezier to the spline?
414: * </I></LI>
415: * <P>
416: * The answer is it's not trivial, and it will necessarily be an approximation
417: * (since you're going from 3rd order to 2nd order). The usual technique is recursive subdivision:
418: * <P>
419: * <OL>
420: * <LI>Create a quadric that tries to approximate your cubic.
421: * <LI>Apply some metric to see how close an approximation it is.
422: * <LI>If it's not close enough, break the cubic in half at the midpoint and recurse on each half.
423: * </OL>
424: * <P>
425: * Call the Bezier curve ABCD, where A and D are the endpoints and B and C the control points.
426: * For step (1) I found the intersection of AB and CD (call it E) and used AED as the quadric.
427: * This is about your only option because the curve at A has to be parallel to AE, and at D has
428: * to be parallel to ED. In step (2), I used as my metric the distance from the midpoint of the
429: * quadric to the midpoint of the Bezier. The midpoint of the quadric is, if I remember correctly,
430: * halfway between the midpoint of AE and the midpoint of ED. The midpoint of the Bezier involves
431: * computing a few more midpoints; it's a standard construction that you should be able to find in a text.
432: * <P>
433: * This worked well enough but tended to produce more quadrics than was optimal. (In general there
434: * were 2-3 times as many quadrics as Beziers. But the quadrics are faster to render, so it balances out.)
435: * I know some people at Apple with more mathematical savvy than I have had worked on this a bit and
436: * had interesting techniques where they didn't always break the Bezier in the middle, and were sometimes
437: * able to merge pieces of adjacent Beziers into the same quadrics. This produced much more efficient
438: * results. To my knowlege their results haven't been published anywhere; but they probably ought to be
439: * now that the ship of QuickDraw GX is imminent. (If you have GX, you might look at the "cubic library",
440: * which apparently does some or all of this stuff. It does describe cubics in quadric form, but I'm not
441: * sure it does all the optimizations I've described in this paragraph...)
442: *
443: * @param p0 1-st control point of cubic bezier
444: * @param p1 2-st control point of cubic bezier
445: * @param p2 3-st control point of cubic bezier
446: * @param p3 4-st control point of cubic bezier
447: * @return array of qudratic bezier. each curve consists of three control points (Point2D)
448: */
449: public static Point2D[] CubicToQudratricBezier(Point2D p0,
450: Point2D p1, Point2D p2, Point2D p3) {
451: IVVector quadPoints = new IVVector();
452:
453: // make first quadric approximation
454: Point2D q0 = p0;
455: Point2D q1 = getIntersectionPoint(p0, p1, p2, p3);
456: Point2D q2 = p3;
457:
458: // check and break if needed
459: breakCubic(p0, p1, p2, p3, q0, q1, q2, 0.0, 1.0, quadPoints);
460:
461: Point2D[] res = new Point2D[quadPoints.size()];
462: quadPoints.copyInto(res);
463: return res;
464: }
465:
466: private static void breakCubic(Point2D c0, Point2D c1, Point2D c2,
467: Point2D c3, Point2D q0, Point2D q1, Point2D q2, double t0,
468: double t1, IVVector result) {
469: // compute mid point on cubic curve on specified interval
470: double mp = t0 + (t1 - t0) * 0.5;
471: Point2D cubic_mid_point = cubicBezier(c0, c1, c2, c3, mp);
472:
473: // compute mid point on quatric curve on interval 0..1
474: Point2D quad_mid_point = quadraticBezier(q0, q1, q2, 0.5);
475:
476: // compute distance between mid points
477: double dist = quad_mid_point.distance(cubic_mid_point);
478:
479: // if distance less than one twixel, then we are done
480: if (dist < 20) {
481: result.addElement(q0);
482: result.addElement(q1);
483: result.addElement(q2);
484: return;
485: }
486:
487: // compute tangent of cubic curve at mid point
488: Point2D dl = derivativeOfCubicBezier(c0, c1, c2, c3, mp);
489:
490: // transfer tangent vector to cibic mid point, so they they together represent true tangent
491: dl.setLocation(dl.getX() + cubic_mid_point.getX(), dl.getY()
492: + cubic_mid_point.getY());
493:
494: // left subdivision
495: Point2D qq1 = getIntersectionPoint(q0, q1, cubic_mid_point, dl);
496: breakCubic(c0, c1, c2, c3, q0, qq1, cubic_mid_point, t0, mp,
497: result);
498:
499: // right subdivision
500: qq1 = getIntersectionPoint(q2, q1, cubic_mid_point, dl);
501: breakCubic(c0, c1, c2, c3, cubic_mid_point, qq1, q2, mp, t1,
502: result);
503: }
504:
505: /**
506: * Computes derivative of cubic bezier at specified point
507: *
508: * @param p0 cubic curve parameter
509: * @param p1 cubic curve parameter
510: * @param p2 cubic curve parameter
511: * @param p3 cubic curve parameter
512: * @param t specified point on the curve
513: * @return derivative of specified curve at specified point
514: */
515: private static Point2D derivativeOfCubicBezier(Point2D p0,
516: Point2D p1, Point2D p2, Point2D p3, double t) {
517: double ax = 3 * p1.getX() - 3 * p2.getX() - p0.getX()
518: + p3.getX();
519: double bx = 3 * (p0.getX() - 2 * p1.getX() + p2.getX());
520: double cx = 3 * (p1.getX() - p0.getX());
521:
522: double ay = 3 * p1.getY() - 3 * p2.getY() - p0.getY()
523: + p3.getY();
524: double by = 3 * (p0.getY() - 2 * p1.getY() + p2.getY());
525: double cy = 3 * (p1.getY() - p0.getY());
526:
527: double x = 3 * ax * t * t + 2 * bx * t + cx;
528: double y = 3 * ay * t * t + 2 * by * t + cy;
529:
530: return new Point2D.Double(x, y);
531: }
532:
533: /**
534: * Computes intersection of two lines
535: * <P>
536: * Each line is specified by two points
537: *
538: * @param a0 first point of line A
539: * @param a1 second point of line A
540: * @param b0 first point of line B
541: * @param b1 second point of line B
542: * @return intersection point
543: */
544: public static Point2D getIntersectionPoint(Point2D a0, Point2D a1,
545: Point2D b0, Point2D b1) {
546: double dAx = a1.getX() - a0.getX();
547: double dAy = a1.getY() - a0.getY();
548: double dBx = b1.getX() - b0.getX();
549: double dBy = b1.getY() - b0.getY();
550: double Fa = dAx * a0.getY() - dAy * a0.getX();
551: double Fb = dBx * b0.getY() - dBy * b0.getX();
552: double ddd = dBy * dAx - dBx * dAy;
553:
554: double x = (Fa * dBx - Fb * dAx) / ddd;
555: double y = (Fa * dBy - Fb * dAy) / ddd;
556:
557: return new Point2D.Double(x, y);
558: }
559: }
|