001: /*
002: * $RCSfile: WarpGrid.java,v $
003: *
004: * Copyright (c) 2005 Sun Microsystems, Inc. All rights reserved.
005: *
006: * Use is subject to license terms.
007: *
008: * $Revision: 1.1 $
009: * $Date: 2005/02/11 04:57:24 $
010: * $State: Exp $
011: */
012: package javax.media.jai;
013:
014: import java.awt.Rectangle;
015: import java.awt.geom.Point2D;
016:
017: /**
018: * A regular grid-based description of an image warp.
019: *
020: * <p> The mapping from destination pixels to source positions is
021: * described by bilinear interpolation within a rectilinear grid of
022: * points with known mappings.
023: *
024: * <p> Given a destination pixel coordinate (x, y) that lies within
025: * a cell having corners at (x0, y0), (x1, y0), (x0, y1) and (x1, y1),
026: * with source coordinates defined at each respective corner equal
027: * to (sx0, sy0), (sx1, sy1), (sx2, sy2) and (sx3, sy3), the
028: * source position (sx, sy) that maps onto (x, y) is given by the formulas:
029: *
030: * <pre>
031: * xfrac = (x - x0)/(x1 - x0)
032: * yfrac = (y - y0)/(y1 - y0)
033: *
034: * s = sx0 + (sx1 - sx0)*xfrac
035: * t = sy0 + (sy1 - sy0)*xfrac
036: *
037: * u = sx2 + (sx3 - sx2)*xfrac
038: * v = sy2 + (sy3 - sy2)*xfrac
039: *
040: * sx = s + (u - s)*yfrac
041: * sy = t + (v - t)*yfrac
042: * </pre>
043: *
044: * <p> In other words, the source x and y values are interpolated
045: * horizontally along the top and bottom edges of the grid cell,
046: * and the results are interpolated vertically:
047: *
048: * <pre>
049: * (x0, y0) -> (x1, y0) ->
050: * (sx0, sy0) (sx1, sy1)
051: * +------------+---------+
052: * | |\ |
053: * | | (s, t) |
054: * | | |
055: * | | |
056: * | | |
057: * | | |
058: * | (x, y) -> | |
059: * | (sx, sy)--+ |
060: * | | |
061: * | | |
062: * | | (u, v) |
063: * | |/ |
064: * +------------+---------+
065: * (x0, y1) -> (x1, y1) ->
066: * (sx2, sy2) (sx3, sy3)
067: * </pre>
068: *
069: * <p> Points outside the bounds of the cells defining the grid warp will
070: * be mapped to the source image using the identity transformation.
071: *
072: * <p> WarpGrid is marked final so that it may be more easily inlined.
073: *
074: */
075: public final class WarpGrid extends Warp {
076:
077: private int xStart;
078: private int yStart;
079:
080: private int xEnd;
081: private int yEnd;
082:
083: private int xStep;
084: private int yStep;
085:
086: private int xNumCells;
087: private int yNumCells;
088:
089: private float[] xWarpPos;
090: private float[] yWarpPos;
091:
092: /**
093: * @param xStart
094: * @param xStep
095: * @param xNumCells
096: * @param yStart
097: * @param yStep
098: * @param yNumCells
099: * @param warpPositions
100: */
101: private void initialize(int xStart, int xStep, int xNumCells,
102: int yStart, int yStep, int yNumCells, float[] warpPositions) {
103: this .xStart = xStart;
104: this .yStart = yStart;
105:
106: this .xEnd = xStart + xStep * xNumCells;
107: this .yEnd = yStart + yStep * yNumCells;
108:
109: this .xStep = xStep;
110: this .yStep = yStep;
111:
112: this .xNumCells = xNumCells;
113: this .yNumCells = yNumCells;
114:
115: int xNumGrids = xNumCells + 1;
116: int yNumGrids = yNumCells + 1;
117:
118: int numNodes = yNumGrids * xNumGrids;
119:
120: xWarpPos = new float[numNodes];
121: yWarpPos = new float[numNodes];
122:
123: int index = 0;
124: for (int idx = 0; idx < numNodes; idx++) {
125: xWarpPos[idx] = warpPositions[index++];
126: yWarpPos[idx] = warpPositions[index++];
127: }
128: }
129:
130: /**
131: * Constructs a WarpGrid with a given grid-based transform mapping
132: * destination pixels into source space. Note that this is
133: * a backward mapping as opposed to the forward mapping used in
134: * AffineOpImage.
135: *
136: * <p> The grid is defined by a set of equal-sized cells.
137: * The grid starts at (xStart, yStart). Each cell has width
138: * equal to xStep and height equal to yStep, and there are
139: * xNumCells cells horizontally and yNumCells cells vertically.
140: *
141: * <p> The local mapping within each cell is defined by
142: * the values in the table parameter. This parameter must
143: * contain 2*(xNumCells + 1)*(yNumCells + 1) values, which
144: * alternately contain the source X and Y coordinates to which
145: * each destination grid intersection point maps.
146: * The cells are enumerated in row-major order, that is,
147: * all the grid points along a row are enumerated first, then
148: * the grid points for the next row are enumerated, and so on.
149: *
150: * <p> As an example, suppose xNumCells is equal to 2 and
151: * yNumCells is equal 1. Then the order of the data in table
152: * would be:
153: *
154: * <pre>
155: * x00, y00, x10, y10, x20, y20, x01, y01, x11, y11, x21, y21
156: * </pre>
157: *
158: * for a total of 2*(2 + 1)*(1 + 1) = 12 elements.
159: *
160: * @param xStart the minimum X coordinate of the grid.
161: * @param xStep the horizontal spacing between grid cells.
162: * @param xNumCells the number of grid cell columns.
163: * @param yStart the minimum Y coordinate of the grid.
164: * @param yStep the vertical spacing between grid cells.
165: * @param yNumCells the number of grid cell rows.
166: * @param warpPositions a float array of length 2*(xNumCells + 1)*
167: * (yNumCells + 1) containing the warp positions at the
168: * grid points, in row-major order.
169: * @throws IllegalArgumentException if the length of warpPositions is incorrect
170: */
171: public WarpGrid(int xStart, int xStep, int xNumCells, int yStart,
172: int yStep, int yNumCells, float[] warpPositions) {
173: if (warpPositions.length != 2 * (xNumCells + 1)
174: * (yNumCells + 1)) {
175: throw new IllegalArgumentException(JaiI18N
176: .getString("WarpGrid0"));
177: }
178:
179: initialize(xStart, xStep, xNumCells, yStart, yStep, yNumCells,
180: warpPositions);
181: }
182:
183: /**
184: * Constructs a WarpGrid object by sampling the displacements
185: * given by another Warp object of any kind.
186: *
187: * <p> The grid is defined by a set of equal-sized cells.
188: * The grid starts at (xStart, yStart). Each cell has width
189: * equal to xStep and height equal to yStep, and there are
190: * xNumCells cells horizontally and yNumCells cells vertically.
191: *
192: * @param master the Warp object used to initialize the grid
193: * displacements.
194: * @param xStart the minimum X coordinate of the grid.
195: * @param xStep the horizontal spacing between grid cells.
196: * @param xNumCells the number of grid cell columns.
197: * @param yStart the minimum Y coordinate of the grid.
198: * @param yStep the vertical spacing between grid cells.
199: * @param yNumCells the number of grid cell rows.
200: */
201: public WarpGrid(Warp master, int xStart, int xStep, int xNumCells,
202: int yStart, int yStep, int yNumCells) {
203: int size = 2 * (xNumCells + 1) * (yNumCells + 1);
204:
205: float[] warpPositions = new float[size];
206: warpPositions = master.warpSparseRect(xStart, yStart, xNumCells
207: * xStep + 1, // width
208: yNumCells * yStep + 1, // height
209: xStep, yStep, warpPositions);
210:
211: initialize(xStart, xStep, xNumCells, yStart, yStep, yNumCells,
212: warpPositions);
213: }
214:
215: /** Returns the minimum X coordinate of the grid. */
216: public int getXStart() {
217: return xStart;
218: }
219:
220: /** Returns the minimum Y coordinate of the grid. */
221: public int getYStart() {
222: return yStart;
223: }
224:
225: /** Returns the horizontal spacing between grid cells. */
226: public int getXStep() {
227: return xStep;
228: }
229:
230: /** Returns the vertical spacing between grid cells. */
231: public int getYStep() {
232: return yStep;
233: }
234:
235: /** Returns the number of grid cell columns. */
236: public int getXNumCells() {
237: return xNumCells;
238: }
239:
240: /** Returns the number of grid cell rows. */
241: public int getYNumCells() {
242: return yNumCells;
243: }
244:
245: /** Returns the horizontal warp positions at the grid points. */
246: public float[] getXWarpPos() {
247: return xWarpPos;
248: }
249:
250: /** Returns the vertical warp positions at the grid points. */
251: public float[] getYWarpPos() {
252: return yWarpPos;
253: }
254:
255: /**
256: * Copies source to destination, no warpping.
257: *
258: * @param x1
259: * @param x2
260: * @param y1
261: * @param y2
262: * @param periodX
263: * @param periodY
264: * @param offset
265: * @param stride
266: * @param destRect
267: * @return An array of <code>float</code>s.
268: * @throws IllegalArgumentException if destRect is null
269: * @throws ArrayBoundsException if destRect is too small
270: */
271: private float[] noWarpSparseRect(int x1, int x2, int y1, int y2,
272: int periodX, int periodY, int offset, int stride,
273: float[] destRect) {
274:
275: if (destRect == null) {
276: throw new IllegalArgumentException(JaiI18N
277: .getString("Generic0"));
278: }
279:
280: for (int j = y1; j <= y2; j += periodY) {
281: int index = offset;
282: offset += stride;
283:
284: for (int i = x1; i <= x2; i += periodX) {
285: destRect[index++] = i;
286: destRect[index++] = j;
287: }
288: }
289:
290: return destRect;
291: }
292:
293: /**
294: * Computes the source subpixel positions for a given rectangular
295: * destination region, subsampled with an integral period.
296: *
297: * <p> Points outside the bounds of the cells defining the grid warp will
298: * be mapped to the source image using the identity transformation.
299:
300: * @param x The minimum X coordinate of the destination region.
301: * @param y The minimum Y coordinate of the destination region.
302: * @param width The width of the destination region.
303: * @param height The height of the destination region.
304: * @param periodX The horizontal sampling period.
305: * @param periodY The vertical sampling period.
306: * @param destRect An int array containing at least
307: * 2*((width+periodX-1)/periodX)*((height+periodY-1)/periodY)
308: * elements, or <code>null</code>. If <code>null</code>, a
309: * new array will be constructed.
310: *
311: * @return a reference to the destRect parameter if it is
312: * non-<code>null</code>, or a new int array of length
313: * 2*width*height otherwise.
314: * @throws ArrayBoundsException if destRect is too small
315: */
316: public float[] warpSparseRect(int x, int y, int width, int height,
317: int periodX, int periodY, float[] destRect) {
318: // Number of points (x, y) per scanline
319: int stride = 2 * ((width + periodX - 1) / periodX);
320:
321: if (destRect == null) {
322: destRect = new float[stride
323: * ((height + periodY - 1) / periodY)];
324: }
325:
326: int x1 = x; // first x point
327: int x2 = x + width - 1; // last x point
328: int y1 = y; // first y point
329: int y2 = y + height - 1; // last y point
330:
331: if (y1 >= yEnd || y2 < yStart || x1 >= xEnd || x2 < xStart) {
332: // destRect is completely outside of warp grid
333: return noWarpSparseRect(x1, x2, y1, y2, periodX, periodY,
334: 0, stride, destRect);
335: }
336:
337: if (y1 < yStart) { // the rectangle above the warp grid area
338: int periods = (yStart - y1 + periodY - 1) / periodY;
339: noWarpSparseRect(x1, x2, y1, yStart - 1, periodX, periodY,
340: 0, stride, destRect);
341: y1 += periods * periodY;
342: }
343:
344: if (y2 >= yEnd) { // the rectangle below the warp grid area
345: int periods = (yEnd - y + periodY - 1) / periodY;
346: noWarpSparseRect(x1, x2, y + periods * periodY, y2,
347: periodX, periodY, periods * stride, stride,
348: destRect);
349: // One period up should be inside warp grid
350: y2 = y + (periods - 1) * periodY;
351: }
352:
353: if (x1 < xStart) { // the rectangle left of the warp grid area
354: int periods = (xStart - x1 + periodX - 1) / periodX;
355: noWarpSparseRect(x1, xStart - 1, y1, y2, periodX, periodY,
356: (y1 - y) / periodY * stride, stride, destRect);
357: x1 += periods * periodX;
358: }
359:
360: if (x2 >= xEnd) { // the rectangle right of the warp grid area
361: int periods = (xEnd - x + periodX - 1) / periodX;
362: noWarpSparseRect(x + periods * periodX, x2, y1, y2,
363: periodX, periodY, (y1 - y) / periodY * stride
364: + periods * 2, stride, destRect);
365: // One period left should be inside warp grid
366: x2 = x + (periods - 1) * periodX;
367: }
368:
369: //
370: // Now the rectangle is within warp grid, that is
371: // xStart <= x1 <= x2 < xEnd and yStart <= y1 <= y2 < yEnd.
372: //
373: // address = s0(1-x)(1-y) + s1x(1-y) + s2(1-x)y + s3xy
374: //
375:
376: // A table stores the number of points inside each cell
377: int[] cellPoints = new int[xNumCells];
378: for (int i = x1; i <= x2; i += periodX) {
379: cellPoints[(i - xStart) / xStep]++;
380: }
381:
382: int offset = (y1 - y) / periodY * stride + (x1 - x) / periodX
383: * 2;
384:
385: // Store the number of horizontal grid nodes.
386: int xNumGrids = xNumCells + 1;
387:
388: // Fractional step in X.
389: float deltaX = (float) periodX / (float) xStep;
390:
391: // The rectangle within the warp grid
392: for (int j = y1; j <= y2; j += periodY) {
393: int index = offset;
394: offset += stride;
395:
396: int yCell = (j - yStart) / yStep;
397: int yGrid = yStart + yCell * yStep;
398: float yFrac = (float) (j + 0.5F - yGrid) / (float) yStep;
399:
400: // Cache some values to avoid two multiplications per x loop.
401: float deltaTop = (1.0F - yFrac) * deltaX;
402: float deltaBottom = yFrac * deltaX;
403:
404: int i = x1;
405: while (i <= x2) {
406: // Entering a new cell, set up
407: int xCell = (i - xStart) / xStep;
408: int xGrid = xStart + xCell * xStep;
409: float xFrac = (float) (i + 0.5F - xGrid)
410: / (float) xStep;
411:
412: int nodeOffset = yCell * xNumGrids + xCell;
413: float wx0 = xWarpPos[nodeOffset];
414: float wy0 = yWarpPos[nodeOffset];
415: float wx1 = xWarpPos[++nodeOffset];
416: float wy1 = yWarpPos[nodeOffset];
417: nodeOffset += xNumCells; // NB: xNumCells == xNumGrids - 1
418: float wx2 = xWarpPos[nodeOffset];
419: float wy2 = yWarpPos[nodeOffset];
420: float wx3 = xWarpPos[++nodeOffset];
421: float wy3 = yWarpPos[nodeOffset];
422:
423: float s = wx0 + (wx1 - wx0) * xFrac;
424: float t = wy0 + (wy1 - wy0) * xFrac;
425: float u = wx2 + (wx3 - wx2) * xFrac;
426: float v = wy2 + (wy3 - wy2) * xFrac;
427:
428: float wx = s + (u - s) * yFrac;
429: float wy = t + (v - t) * yFrac;
430:
431: // Delta in x and y.
432: float dx = (wx1 - wx0) * deltaTop + (wx3 - wx2)
433: * deltaBottom;
434: float dy = (wy1 - wy0) * deltaTop + (wy3 - wy2)
435: * deltaBottom;
436:
437: // The points inside the current cell
438: int nPoints = cellPoints[xCell];
439: for (int k = 0; k < nPoints; k++) {
440: destRect[index++] = wx - 0.5F;
441: destRect[index++] = wy - 0.5F;
442:
443: wx += dx;
444: wy += dy;
445: i += periodX;
446: }
447: }
448: }
449:
450: return destRect;
451: }
452:
453: /**
454: * Computes the source point corresponding to the supplied point.
455: *
456: * <p>This method returns the value of <code>pt</code> in the following
457: * code snippet:
458: *
459: * <pre>
460: * float[] sxy = warpSparseRect((int)destPt.getX(), (int)destPt.getY(),
461: * 2, 2, 1, 1, null);
462: *
463: * double wtRight = destPt.getX() - (int)destPt.getX();
464: * double wtLeft = 1.0 - wtRight;
465: * double wtBottom = destPt.getY() - (int)destPt.getY();
466: * double wtTop = 1.0 - wtBottom;
467: *
468: * Point2D pt = (Point2D)destPt.clone();
469: * pt.setLocation((sxy[0]*wtLeft + sxy[2]*wtRight)*wtTop +
470: * (sxy[4]*wtLeft + sxy[6]*wtRight)*wtBottom,
471: * (sxy[1]*wtLeft + sxy[3]*wtRight)*wtTop +
472: * (sxy[5]*wtLeft + sxy[7]*wtRight)*wtBottom);
473: * </pre>
474: * </p>
475: *
476: * @param destPt the position in destination image coordinates
477: * to map to source image coordinates.
478: *
479: * @return a <code>Point2D</code> of the same class as
480: * <code>destPt</code>.
481: *
482: * @throws IllegalArgumentException if <code>destPt</code> is
483: * <code>null</code>.
484: *
485: * @since JAI 1.1.2
486: */
487: public Point2D mapDestPoint(Point2D destPt) {
488: if (destPt == null) {
489: throw new IllegalArgumentException(JaiI18N
490: .getString("Generic0"));
491: }
492:
493: float[] sxy = warpSparseRect((int) destPt.getX(), (int) destPt
494: .getY(), 2, 2, 1, 1, null);
495:
496: double wtRight = destPt.getX() - (int) destPt.getX();
497: double wtLeft = 1.0 - wtRight;
498: double wtBottom = destPt.getY() - (int) destPt.getY();
499: double wtTop = 1.0 - wtBottom;
500:
501: Point2D pt = (Point2D) destPt.clone();
502: pt.setLocation((sxy[0] * wtLeft + sxy[2] * wtRight) * wtTop
503: + (sxy[4] * wtLeft + sxy[6] * wtRight) * wtBottom,
504: (sxy[1] * wtLeft + sxy[3] * wtRight) * wtTop
505: + (sxy[5] * wtLeft + sxy[7] * wtRight)
506: * wtBottom);
507:
508: return pt;
509: }
510: }
|