001: /*
002: *
003: * Copyright 1990-2007 Sun Microsystems, Inc. All Rights Reserved.
004: * DO NOT ALTER OR REMOVE COPYRIGHT NOTICES OR THIS FILE HEADER
005: *
006: * This program is free software; you can redistribute it and/or
007: * modify it under the terms of the GNU General Public License version
008: * 2 only, as published by the Free Software Foundation.
009: *
010: * This program is distributed in the hope that it will be useful, but
011: * WITHOUT ANY WARRANTY; without even the implied warranty of
012: * MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the GNU
013: * General Public License version 2 for more details (a copy is
014: * included at /legal/license.txt).
015: *
016: * You should have received a copy of the GNU General Public License
017: * version 2 along with this work; if not, write to the Free Software
018: * Foundation, Inc., 51 Franklin St, Fifth Floor, Boston, MA
019: * 02110-1301 USA
020: *
021: * Please contact Sun Microsystems, Inc., 4150 Network Circle, Santa
022: * Clara, CA 95054 or visit www.sun.com if you need additional
023: * information or have any questions.
024: */
025:
026: package com.sun.pisces;
027:
028: /**
029: * The <code>Flattener</code> class rewrites a general path, which
030: * may include curved segments, into one containing only linear
031: * segments suitable for sending to a <code>LineSink</code>.
032: *
033: * <p> Curved segments specified by <code>quadTo</code> and
034: * <code>curveTo</code> commands will be subdivided into two pieces.
035: * When the control points of a segment lie sufficiently close
036: * togther, such that <code>max(x_i) - min(x_i) < flatness</code> and
037: * <code>max(y_i) - min(y_i) < flatness</code> for a user-supplied
038: * <code>flatness</code> parameter, a <code>lineTo</code> command is
039: * emitted between the first and last points of the curve.
040: */
041: public class Flattener extends PathSink {
042:
043: // Always subdivide segments where the endpoints are
044: // separated by more than this amount
045: public static final long MAX_CHORD_LENGTH_SQ = 16L * 16L * 65536L * 65536L;
046: public static final long MIN_CHORD_LENGTH_SQ = 65536L * 65536L / (2L * 2L);
047:
048: public static final int LG_FLATNESS = 0; // half pixel, 2^(-1)
049: public static final int FLATNESS_SQ_SHIFT = 2 * (-LG_FLATNESS);
050:
051: LineSink output;
052: int flatness, flatnessSq;
053: int x0, y0;
054:
055: /**
056: * Empty constructor. <code>setOutput</code> and
057: * <code>setFlatness</code> must be called prior to calling any
058: * other methods.
059: */
060: public Flattener() {
061: }
062:
063: /**
064: * Constructs a <code>Flattener</code> that will rewrite any
065: * incoming <code>quadTo</code> and <code>curveTo</code> commands
066: * into a series of <code>lineTo</code> commands with maximum X
067: * and Y extents no larger than the supplied <code>flatness</code>
068: * value. The flat segments will be sent as commands to the given
069: * <code>LineSink</code>.
070: *
071: * @param output a <code>LineSink</code> to which commands
072: * should be sent.
073: * @param flatness the maximum extent of a subdivided output line
074: * segment, in S15.16 format.
075: */
076: public Flattener(LineSink output, int flatness) {
077: setOutput(output);
078: setFlatness(flatness);
079: }
080:
081: /**
082: * Sets the output <code>LineSink</code> of this
083: * <code>Flattener</code>.
084: *
085: * @param output an output <code>LineSink</code>.
086: */
087: public void setOutput(LineSink output) {
088: this .output = output;
089: }
090:
091: /**
092: * Sets the desired output flatness for this <code>Flattener</code>.
093: *
094: * @param flatness the maximum extent of a subdivided output line
095: * segment, in S15.16 format.
096: */
097: public void setFlatness(int flatness) {
098: this .flatness = flatness;
099: this .flatnessSq = (int) ((long) flatness * flatness >> 16);
100: }
101:
102: public void moveTo(int x0, int y0) {
103: output.moveTo(x0, y0);
104: this .x0 = x0;
105: this .y0 = y0;
106: }
107:
108: public void lineJoin() {
109: output.lineJoin();
110: }
111:
112: public void lineTo(int x1, int y1) {
113: output.lineJoin();
114: output.lineTo(x1, y1);
115: this .x0 = x1;
116: this .y0 = y1;
117: }
118:
119: public void quadTo(int x1, int y1, int x2, int y2) {
120: output.lineJoin();
121: quadToHelper(x1, y1, x2, y2);
122: }
123:
124: // See cubic (8 argument) version below for commentary
125: private boolean flatEnough(int x0, int y0, int x1, int y1, int x2,
126: int y2) {
127: long dx = (long) x2 - (long) x0;
128: long dy = (long) y2 - (long) y0;
129: long denom2 = dx * dx + dy * dy;
130: if (denom2 > MAX_CHORD_LENGTH_SQ) {
131: return false;
132: }
133:
134: // Stop dividing if all control points are close together
135: if (denom2 < MIN_CHORD_LENGTH_SQ) {
136: int minx = Math.min(Math.min(x0, x1), x2);
137: int miny = Math.min(Math.min(y0, y1), y2);
138: int maxx = Math.max(Math.max(x0, x1), x2);
139: int maxy = Math.max(Math.max(y0, y1), y2);
140:
141: long dx1 = (long) maxx - (long) minx;
142: long dy1 = (long) maxy - (long) miny;
143: long l2 = dx1 * dx1 + dy1 * dy1;
144: if (l2 < MIN_CHORD_LENGTH_SQ) {
145: return true;
146: }
147: }
148:
149: long num = -dy * x1 + dx * y1
150: + ((long) x0 * y2 - (long) x2 * y0);
151: num >>= 16;
152: long numsq = num * num;
153: long df2 = denom2 * flatnessSq >> 16;
154: return numsq < df2;
155: }
156:
157: private void quadToHelper(int x1, int y1, int x2, int y2) {
158: if (flatEnough(x0, y0, x1, y1, x2, y2)) {
159: output.lineTo(x1, y1);
160: output.lineTo(x2, y2);
161: } else {
162: long lx1 = (long) x1;
163: long ly1 = (long) y1;
164: long x01 = x0 + lx1; // >> 1
165: long y01 = y0 + ly1; // >> 1
166: long x12 = lx1 + x2; // >> 1
167: long y12 = ly1 + y2; // >> 1
168:
169: long x012 = x01 + x12; // >> 2
170: long y012 = y01 + y12; // >> 2
171:
172: quadToHelper((int) (x01 >> 1), (int) (y01 >> 1),
173: (int) (x012 >> 2), (int) (y012 >> 2));
174: quadToHelper((int) (x12 >> 1), (int) (y12 >> 1), x2, y2);
175: }
176:
177: this .x0 = x2;
178: this .y0 = y2;
179: }
180:
181: public void cubicTo(int x1, int y1, int x2, int y2, int x3, int y3) {
182: output.lineJoin();
183: cubicToHelper(x1, y1, x2, y2, x3, y3);
184: }
185:
186: // IMPL_NOTE - analyze position of radix points to avoid possibility
187: // of overflow
188: private boolean flatEnough(int x0, int y0, int x1, int y1, int x2,
189: int y2, int x3, int y3) {
190: long dx = (long) x3 - (long) x0; // S47.16
191: long dy = (long) y3 - (long) y0; // S47.16
192: long denom2 = dx * dx + dy * dy; // S31.32
193: // Always subdivide curves with a large chord length
194: if (denom2 > MAX_CHORD_LENGTH_SQ) {
195: return false;
196: }
197:
198: // Stop dividing if all control points are close together
199: if (denom2 < MIN_CHORD_LENGTH_SQ) {
200: int minx = Math.min(Math.min(Math.min(x0, x1), x2), x3);
201: int miny = Math.min(Math.min(Math.min(y0, y1), y2), y3);
202: int maxx = Math.max(Math.max(Math.max(x0, x1), x2), x3);
203: int maxy = Math.max(Math.max(Math.max(y0, y1), y2), y3);
204:
205: long dx1 = (long) maxx - (long) minx;
206: long dy1 = (long) maxy - (long) miny;
207: long l2 = dx1 * dx1 + dy1 * dy1;
208: if (l2 < MIN_CHORD_LENGTH_SQ) {
209: return true;
210: }
211: }
212:
213: // Want to know if num/denom < flatness, so compare
214: // numerator^2 against (denominator*flatness)^2 to avoid a square root
215: long df2 = denom2 * flatnessSq >> 16; // S31.32
216:
217: long cross = (long) x0 * y3 - (long) x3 * y0; // S31.32
218: long num1 = dx * y1 - dy * x1 + cross; // S31.32
219: num1 >>= 16; // S47.16
220: long num1sq = num1 * num1; // S31.32
221: if (num1sq > df2) {
222: return false;
223: }
224:
225: long num2 = dx * y2 - dy * x2 + cross; // S31.32
226: num2 >>= 16; // S47.16
227: long num2sq = num2 * num2; // S31.32
228:
229: return num2sq < df2;
230: }
231:
232: private void cubicToHelper(int x1, int y1, int x2, int y2, int x3,
233: int y3) {
234: if (flatEnough(x0, y0, x1, y1, x2, y2, x3, y3)) {
235: output.lineTo(x1, y1);
236: output.lineTo(x2, y2);
237: output.lineTo(x3, y3);
238: } else {
239: long lx1 = (long) x1;
240: long ly1 = (long) y1;
241: long lx2 = (long) x2;
242: long ly2 = (long) y2;
243:
244: long x01 = x0 + lx1; // >> 1
245: long y01 = y0 + ly1; // >> 1
246: long x12 = lx1 + lx2; // >> 1
247: long y12 = ly1 + ly2; // >> 1
248: long x23 = lx2 + x3; // >> 1
249: long y23 = ly2 + y3; // >> 1
250:
251: long x012 = x01 + x12; // >> 2
252: long y012 = y01 + y12; // >> 2
253: long x123 = x12 + x23; // >> 2
254: long y123 = y12 + y23; // >> 2
255: long x0123 = x012 + x123; // >> 3
256: long y0123 = y012 + y123; // >> 3
257:
258: cubicToHelper((int) (x01 >> 1), (int) (y01 >> 1),
259: (int) (x012 >> 2), (int) (y012 >> 2),
260: (int) (x0123 >> 3), (int) (y0123 >> 3));
261: cubicToHelper((int) (x123 >> 2), (int) (y123 >> 2),
262: (int) (x23 >> 1), (int) (y23 >> 1), x3, y3);
263: }
264:
265: this .x0 = x3;
266: this .y0 = y3;
267: }
268:
269: public void close() {
270: output.lineJoin();
271: output.close();
272: }
273:
274: public void end() {
275: output.end();
276: }
277: }
|