Java > Open Source Codes > org > openlaszlo > iv > flash > util > GeomHelper


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

A to Z: JavaDoc & Examples

---

Daily Java News & Articles

---

Open Source Projects

---

Open Source Codes

---

Free Computer Books

---

Remove Frame

---

Popular Tags