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}