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