001    /*
002    *
003    
004    Licensed under the Apache License, Version 2.0 (the "License");
005    you may not use this file except in compliance with the License.
006    You may obtain a copy of the License at
007    
008       http://www.apache.org/licenses/LICENSE-2.0
009    
010    Unless required by applicable law or agreed to in writing, software
011    distributed under the License is distributed on an "AS IS" BASIS,
012    WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied.
013    See the License for the specific language governing permissions and
014    limitations under the License.
015    */
016    
017    package railo.runtime.img.filter;
018    
019    /**
020     * A warp grid.
021     * From "A simplified approach to Image Processing" by Randy Crane
022     */
023    public class WarpGrid {
024    
025            public float[] xGrid = null;
026            public float[] yGrid = null;
027            public int rows, cols;
028    
029            public WarpGrid(int rows, int cols, int w, int h) {
030                    this.rows = rows;
031                    this.cols = cols;
032                    xGrid = new float[rows*cols];
033                    yGrid = new float[rows*cols];
034                    int index = 0;
035                    for (int row = 0; row < rows; row++) {
036                            for (int col = 0; col < cols; col++) {
037                                    xGrid[index] = (float)col*(w-1)/(cols-1);
038                                    yGrid[index] = (float)row*(h-1)/(rows-1);
039                                    index++;
040                            }
041                    }
042            }
043    
044            /**
045             * Add a new row to the grid. "before" must be in the range 1..rows-1. i.e. you can only add rows inside the grid.
046             */
047            public void addRow( int before ) {
048                    int size = (rows+1) * cols;
049                    float[] x = new float[size];
050                    float[] y = new float[size];
051    
052                    rows++;
053                    int i = 0;
054                    int j = 0;
055                    for (int row = 0; row < rows; row++) {
056                            for (int col = 0; col < cols; col++) {
057                                    int k = j+col;
058                                    int l = i+col;
059                                    if ( row == before ) {
060                                            x[k] = (xGrid[l]+xGrid[k])/2;
061                                            y[k] = (yGrid[l]+yGrid[k])/2;
062                                    } else {
063                                            x[k] = xGrid[l];
064                                            y[k] = yGrid[l];
065                                    }
066                            }
067                            if ( row != before-1 )
068                                    i += cols;
069                            j += cols;
070                    }
071                    xGrid = x;
072                    yGrid = y;
073            }
074    
075            /**
076             * Add a new column to the grid. "before" must be in the range 1..cols-1. i.e. you can only add columns inside the grid.
077             */
078            public void addCol( int before ) {
079                    int size = rows * (cols+1);
080                    float[] x = new float[size];
081                    float[] y = new float[size];
082    
083                    cols++;
084    int i = 0;
085    int j = 0;
086                    for (int row = 0; row < rows; row++) {
087    //                      int i = row*(cols-1);
088    //                      int j = row*cols;
089                            for (int col = 0; col < cols; col++) {
090                                    if ( col == before ) {
091                                            x[j] = (xGrid[i]+xGrid[i-1])/2;
092                                            y[j] = (yGrid[i]+yGrid[i-1])/2;
093                                    } else {
094                                            x[j] = xGrid[i];
095                                            y[j] = yGrid[i];
096                                            i++;
097                                    }
098                                    j++;
099                            }
100                    }
101                    xGrid = x;
102                    yGrid = y;
103            }
104    
105            /**
106             * Remove a row from the grid.
107             */
108            public void removeRow( int r ) {
109                    int size = (rows-1) * cols;
110                    float[] x = new float[size];
111                    float[] y = new float[size];
112    
113                    rows--;
114                    int i = 0;
115                    int j = 0;
116                    for (int row = 0; row < rows; row++) {
117                            for (int col = 0; col < cols; col++) {
118                                    int k = j+col;
119                                    int l = i+col;
120                                    x[k] = xGrid[l];
121                                    y[k] = yGrid[l];
122                            }
123                            if ( row == r-1 )
124                                    i += cols;
125                            i += cols;
126                            j += cols;
127                    }
128                    xGrid = x;
129                    yGrid = y;
130            }
131    
132            /**
133             * Remove a column from the grid.
134             */
135            public void removeCol( int r ) {
136                    int size = rows * (cols+1);
137                    float[] x = new float[size];
138                    float[] y = new float[size];
139    
140                    cols--;
141                    for (int row = 0; row < rows; row++) {
142                            int i = row*(cols+1);
143                            int j = row*cols;
144                            for (int col = 0; col < cols; col++) {
145                                    x[j] = xGrid[i];
146                                    y[j] = yGrid[i];
147                                    if ( col == r-1 )
148                                            i++;
149                                    i++;
150                                    j++;
151                            }
152                    }
153                    xGrid = x;
154                    yGrid = y;
155            }
156    
157            public void lerp(float t, WarpGrid destination, WarpGrid intermediate) {
158                    if (rows != destination.rows || cols != destination.cols)
159                            throw new IllegalArgumentException("source and destination are different sizes");
160                    if (rows != intermediate.rows || cols != intermediate.cols)
161                            throw new IllegalArgumentException("source and intermediate are different sizes");
162                    int index = 0;
163                    for (int row = 0; row < rows; row++) {
164                            for (int col = 0; col < cols; col++) {
165                                    intermediate.xGrid[index] = ImageMath.lerp(t, xGrid[index], destination.xGrid[index]);
166                                    intermediate.yGrid[index] = ImageMath.lerp(t, yGrid[index], destination.yGrid[index]);
167                                    index++;
168                            }
169                    }
170            }
171            
172            public void warp(int[] inPixels, int cols, int rows, WarpGrid sourceGrid, WarpGrid destGrid, int[] outPixels) {
173    try {
174                    int x, y;
175                    int u, v;
176                    int[] intermediate;
177                    WarpGrid splines;
178    
179                    if (sourceGrid.rows != destGrid.rows || sourceGrid.cols != destGrid.cols)
180                            throw new IllegalArgumentException("source and destination grids are different sizes");
181    
182                    int size = Math.max(cols, rows);
183                    float[] xrow = new float[size];
184                    float[] yrow = new float[size];
185                    float[] scale  = new float[size + 1];
186                    float[] interpolated = new float[size + 1];
187    
188                    int gridCols = sourceGrid.cols;
189                    int gridRows = sourceGrid.rows;
190    
191                    splines = new WarpGrid(rows, gridCols, 1, 1);
192    
193                    for (u = 0; u < gridCols;u++) {
194                            int i = u;
195    
196                            for (v = 0; v < gridRows;v++) {
197                                    xrow[v] = sourceGrid.xGrid[i];
198                                    yrow[v] = sourceGrid.yGrid[i];
199                                    i += gridCols;
200                            }
201    
202                            interpolateSpline(yrow, xrow, 0, gridRows, interpolated, 0, rows);
203    
204                            i = u;
205                            for (y = 0;y < rows;y++) {
206                                    splines.xGrid[i] = interpolated[y];
207                                    i += gridCols;
208                            }
209                    }
210    
211                    for (u = 0; u < gridCols;u++) {
212                            int i = u;
213    
214                            for (v = 0; v < gridRows;v++) {
215                                    xrow[v] = destGrid.xGrid[i];
216                                    yrow[v] = destGrid.yGrid[i];
217                                    i += gridCols;
218                            }
219    
220                            interpolateSpline(yrow, xrow, 0, gridRows, interpolated, 0, rows);
221    
222                            i = u;
223                            for (y = 0;y < rows; y++) {
224                                    splines.yGrid[i] = interpolated[y];
225                                    i += gridCols;
226                            }
227                    }
228    
229                    /* first pass: warp x using splines */
230                    intermediate = new int[rows*cols];
231    
232                    int offset = 0;
233                    for (y = 0; y < rows; y++) {
234                            /* fit spline to x-intercepts;resample over all cols */
235                            interpolateSpline(splines.xGrid, splines.yGrid, offset, gridCols, scale, 0, cols);
236                            scale[cols] = cols;
237                            ImageMath.resample(inPixels, intermediate, cols, y*cols, 1, scale);
238                            offset += gridCols;
239                    }
240                    /* create table of y-intercepts for intermediate mesh's hor splines */
241    
242                    splines = new WarpGrid(gridRows, cols, 1, 1);
243    
244                    offset = 0;
245                    int offset2 = 0;
246                    for (v = 0; v < gridRows; v++) {
247                            interpolateSpline(sourceGrid.xGrid, sourceGrid.yGrid, offset, gridCols, splines.xGrid, offset2, cols);
248                            offset += gridCols;
249                            offset2 += cols;
250                    }
251    
252                    offset = 0;
253                    offset2 = 0;
254                    for (v = 0; v < gridRows; v++) {
255                            interpolateSpline(destGrid.xGrid, destGrid.yGrid, offset, gridCols, splines.yGrid, offset2, cols);
256                            offset += gridCols;
257                            offset2 += cols;
258                    }
259    
260                    /* second pass: warp y */
261    
262                    for (x = 0; x < cols; x++) {
263                            int i = x;
264                            
265                            for (v = 0; v < gridRows; v++) {
266                                    xrow[v] = splines.xGrid[i];;
267                                    yrow[v] = splines.yGrid[i];;
268                                    i += cols;
269                            }
270    
271                            interpolateSpline(xrow, yrow, 0, gridRows, scale, 0, rows);
272                            scale[rows] = rows;
273                            ImageMath.resample(intermediate, outPixels, rows, x, cols, scale);
274                    }
275    }
276    catch (Exception e) {
277            
278    }
279            }
280    
281            private final static float m00 = -0.5f;
282            private final static float m01 =  1.5f;
283            private final static float m02 = -1.5f;
284            private final static float m03 =  0.5f;
285            private final static float m10 =  1.0f;
286            private final static float m11 = -2.5f;
287            private final static float m12 =  2.0f;
288            private final static float m13 = -0.5f;
289            private final static float m20 = -0.5f;
290            private final static float m22 =  0.5f;
291            private final static float m31 =  1.0f;
292    
293            protected void interpolateSpline(float[] xKnots, float[] yKnots, int offset, int length, float[] splineY, int splineOffset, int splineLength) {
294                    int index = offset;
295                    int end = offset+length-1;
296                    float x0, x1;
297                    float k0, k1, k2, k3;
298                    float c0, c1, c2, c3;
299    
300                    x0 = xKnots[index];
301                    k0 = k1 = k2 = yKnots[index];
302                    x1 = xKnots[index+1];
303                    k3 = yKnots[index+1];
304    
305                    for (int i = 0;i < splineLength;i++) {
306                            if (index <= end && i > xKnots[index]) {
307                                    k0 = k1;
308                                    k1 = k2;
309                                    k2 = k3;
310                                    x0 = xKnots[index];
311                                    index++;
312                                    if ( index <= end )
313                                            x1 = xKnots[index];
314                                    if ( index < end )
315                                            k3 = yKnots[index+1];
316                                    else
317                                            k3 = k2;
318                            }
319                            float t = (i - x0) / (x1 - x0);
320                            c3 = m00*k0 + m01*k1 + m02*k2 + m03*k3;
321                            c2 = m10*k0 + m11*k1 + m12*k2 + m13*k3;
322                            c1 = m20*k0 + m22*k2;
323                            c0 = m31*k1;
324                            
325                            splineY[splineOffset+i] = ((c3*t + c2)*t + c1)*t + c0;
326                    }
327            }
328    
329            protected void interpolateSpline2(float[] xKnots, float[] yKnots, int offset, float[] splineY, int splineOffset, int splineLength) {
330                    int index = offset;
331                    float leftX, rightX;
332                    float leftY, rightY;
333    
334                    leftX = xKnots[index];
335                    leftY = yKnots[index];
336                    rightX = xKnots[index+1];
337                    rightY = yKnots[index+1];
338    
339                    for (int i = 0;i < splineLength;i++) {
340                            if (i > xKnots[index]) {
341                                    leftX = xKnots[index];
342                                    leftY = yKnots[index];
343                                    index++;
344                                    rightX = xKnots[index];
345                                    rightY = yKnots[index];
346                            }
347                            float f = (i - leftX) / (rightX - leftX);
348                            splineY[splineOffset+i] = leftY + f * (rightY - leftY);
349                    }
350            }
351    }