1 /* 2 * Copyright (C) 2012 The Android Open Source Project 3 * 4 * Licensed under the Apache License, Version 2.0 (the "License"); 5 * you may not use this file except in compliance with the License. 6 * You may obtain a copy of the License at 7 * 8 * http://www.apache.org/licenses/LICENSE-2.0 9 * 10 * Unless required by applicable law or agreed to in writing, software 11 * distributed under the License is distributed on an "AS IS" BASIS, 12 * WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied. 13 * See the License for the specific language governing permissions and 14 * limitations under the License. 15 */ 16 17 package com.android.gallery3d.filtershow.imageshow; 18 19 import android.graphics.Canvas; 20 import android.graphics.Color; 21 import android.graphics.Paint; 22 import android.graphics.Path; 23 import android.graphics.drawable.Drawable; 24 import android.util.Log; 25 26 import java.util.Collections; 27 import java.util.Vector; 28 29 public class Spline { 30 private final Vector<ControlPoint> mPoints; 31 private static Drawable mCurveHandle; 32 private static int mCurveHandleSize; 33 private static int mCurveWidth; 34 35 public static final int RGB = 0; 36 public static final int RED = 1; 37 public static final int GREEN = 2; 38 public static final int BLUE = 3; 39 private static final String LOGTAG = "Spline"; 40 41 private final Paint gPaint = new Paint(); 42 private ControlPoint mCurrentControlPoint = null; 43 44 public Spline() { 45 mPoints = new Vector<ControlPoint>(); 46 } 47 48 public Spline(Spline spline) { 49 mPoints = new Vector<ControlPoint>(); 50 for (int i = 0; i < spline.mPoints.size(); i++) { 51 ControlPoint p = spline.mPoints.elementAt(i); 52 ControlPoint newPoint = new ControlPoint(p); 53 mPoints.add(newPoint); 54 if (spline.mCurrentControlPoint == p) { 55 mCurrentControlPoint = newPoint; 56 } 57 } 58 Collections.sort(mPoints); 59 } 60 61 public static void setCurveHandle(Drawable drawable, int size) { 62 mCurveHandle = drawable; 63 mCurveHandleSize = size; 64 } 65 66 public static void setCurveWidth(int width) { 67 mCurveWidth = width; 68 } 69 70 public static int curveHandleSize() { 71 return mCurveHandleSize; 72 } 73 74 public static int colorForCurve(int curveIndex) { 75 switch (curveIndex) { 76 case Spline.RED: 77 return Color.RED; 78 case GREEN: 79 return Color.GREEN; 80 case BLUE: 81 return Color.BLUE; 82 } 83 return Color.WHITE; 84 } 85 86 public boolean sameValues(Spline other) { 87 if (this == other) { 88 return true; 89 } 90 if (other == null) { 91 return false; 92 } 93 94 if (getNbPoints() != other.getNbPoints()) { 95 return false; 96 } 97 98 for (int i = 0; i < getNbPoints(); i++) { 99 ControlPoint p = mPoints.elementAt(i); 100 ControlPoint otherPoint = other.mPoints.elementAt(i); 101 if (!p.sameValues(otherPoint)) { 102 return false; 103 } 104 } 105 return true; 106 } 107 108 private void didMovePoint(ControlPoint point) { 109 mCurrentControlPoint = point; 110 } 111 112 public void movePoint(int pick, float x, float y) { 113 if (pick < 0 || pick > mPoints.size() - 1) { 114 return; 115 } 116 ControlPoint point = mPoints.elementAt(pick); 117 point.x = x; 118 point.y = y; 119 didMovePoint(point); 120 } 121 122 public boolean isOriginal() { 123 if (this.getNbPoints() != 2) { 124 return false; 125 } 126 if (mPoints.elementAt(0).x != 0 || mPoints.elementAt(0).y != 1) { 127 return false; 128 } 129 if (mPoints.elementAt(1).x != 1 || mPoints.elementAt(1).y != 0) { 130 return false; 131 } 132 return true; 133 } 134 135 public void reset() { 136 mPoints.clear(); 137 addPoint(0.0f, 1.0f); 138 addPoint(1.0f, 0.0f); 139 } 140 141 private void drawHandles(Canvas canvas, Drawable indicator, float centerX, float centerY) { 142 int left = (int) centerX - mCurveHandleSize / 2; 143 int top = (int) centerY - mCurveHandleSize / 2; 144 indicator.setBounds(left, top, left + mCurveHandleSize, top + mCurveHandleSize); 145 indicator.draw(canvas); 146 } 147 148 public float[] getAppliedCurve() { 149 float[] curve = new float[256]; 150 ControlPoint[] points = new ControlPoint[mPoints.size()]; 151 for (int i = 0; i < mPoints.size(); i++) { 152 ControlPoint p = mPoints.get(i); 153 points[i] = new ControlPoint(p.x, p.y); 154 } 155 double[] derivatives = solveSystem(points); 156 int start = 0; 157 int end = 256; 158 if (points[0].x != 0) { 159 start = (int) (points[0].x * 256); 160 } 161 if (points[points.length - 1].x != 1) { 162 end = (int) (points[points.length - 1].x * 256); 163 } 164 for (int i = 0; i < start; i++) { 165 curve[i] = 1.0f - points[0].y; 166 } 167 for (int i = end; i < 256; i++) { 168 curve[i] = 1.0f - points[points.length - 1].y; 169 } 170 for (int i = start; i < end; i++) { 171 ControlPoint cur = null; 172 ControlPoint next = null; 173 double x = i / 256.0; 174 int pivot = 0; 175 for (int j = 0; j < points.length - 1; j++) { 176 if (x >= points[j].x && x <= points[j + 1].x) { 177 pivot = j; 178 } 179 } 180 cur = points[pivot]; 181 next = points[pivot + 1]; 182 if (x <= next.x) { 183 double x1 = cur.x; 184 double x2 = next.x; 185 double y1 = cur.y; 186 double y2 = next.y; 187 188 // Use the second derivatives to apply the cubic spline 189 // equation: 190 double delta = (x2 - x1); 191 double delta2 = delta * delta; 192 double b = (x - x1) / delta; 193 double a = 1 - b; 194 double ta = a * y1; 195 double tb = b * y2; 196 double tc = (a * a * a - a) * derivatives[pivot]; 197 double td = (b * b * b - b) * derivatives[pivot + 1]; 198 double y = ta + tb + (delta2 / 6) * (tc + td); 199 if (y > 1.0f) { 200 y = 1.0f; 201 } 202 if (y < 0) { 203 y = 0; 204 } 205 curve[i] = (float) (1.0f - y); 206 } else { 207 curve[i] = 1.0f - next.y; 208 } 209 } 210 return curve; 211 } 212 213 private void drawGrid(Canvas canvas, float w, float h) { 214 // Grid 215 gPaint.setARGB(128, 150, 150, 150); 216 gPaint.setStrokeWidth(1); 217 218 float stepH = h / 9; 219 float stepW = w / 9; 220 221 // central diagonal 222 gPaint.setARGB(255, 100, 100, 100); 223 gPaint.setStrokeWidth(2); 224 canvas.drawLine(0, h, w, 0, gPaint); 225 226 gPaint.setARGB(128, 200, 200, 200); 227 gPaint.setStrokeWidth(4); 228 stepH = h / 3; 229 stepW = w / 3; 230 for (int j = 1; j < 3; j++) { 231 canvas.drawLine(0, j * stepH, w, j * stepH, gPaint); 232 canvas.drawLine(j * stepW, 0, j * stepW, h, gPaint); 233 } 234 canvas.drawLine(0, 0, 0, h, gPaint); 235 canvas.drawLine(w, 0, w, h, gPaint); 236 canvas.drawLine(0, 0, w, 0, gPaint); 237 canvas.drawLine(0, h, w, h, gPaint); 238 } 239 240 public void draw(Canvas canvas, int color, int canvasWidth, int canvasHeight, 241 boolean showHandles, boolean moving) { 242 float w = canvasWidth - mCurveHandleSize; 243 float h = canvasHeight - mCurveHandleSize; 244 float dx = mCurveHandleSize / 2; 245 float dy = mCurveHandleSize / 2; 246 247 // The cubic spline equation is (from numerical recipes in C): 248 // y = a(y_i) + b(y_i+1) + c(y"_i) + d(y"_i+1) 249 // 250 // with c(y"_i) and d(y"_i+1): 251 // c(y"_i) = 1/6 (a^3 - a) delta^2 (y"_i) 252 // d(y"_i_+1) = 1/6 (b^3 - b) delta^2 (y"_i+1) 253 // 254 // and delta: 255 // delta = x_i+1 - x_i 256 // 257 // To find the second derivatives y", we can rearrange the equation as: 258 // A(y"_i-1) + B(y"_i) + C(y"_i+1) = D 259 // 260 // With the coefficients A, B, C, D: 261 // A = 1/6 (x_i - x_i-1) 262 // B = 1/3 (x_i+1 - x_i-1) 263 // C = 1/6 (x_i+1 - x_i) 264 // D = (y_i+1 - y_i)/(x_i+1 - x_i) - (y_i - y_i-1)/(x_i - x_i-1) 265 // 266 // We can now easily solve the equation to find the second derivatives: 267 ControlPoint[] points = new ControlPoint[mPoints.size()]; 268 for (int i = 0; i < mPoints.size(); i++) { 269 ControlPoint p = mPoints.get(i); 270 points[i] = new ControlPoint(p.x * w, p.y * h); 271 } 272 double[] derivatives = solveSystem(points); 273 274 Path path = new Path(); 275 path.moveTo(0, points[0].y); 276 for (int i = 0; i < points.length - 1; i++) { 277 double x1 = points[i].x; 278 double x2 = points[i + 1].x; 279 double y1 = points[i].y; 280 double y2 = points[i + 1].y; 281 282 for (double x = x1; x < x2; x += 20) { 283 // Use the second derivatives to apply the cubic spline 284 // equation: 285 double delta = (x2 - x1); 286 double delta2 = delta * delta; 287 double b = (x - x1) / delta; 288 double a = 1 - b; 289 double ta = a * y1; 290 double tb = b * y2; 291 double tc = (a * a * a - a) * derivatives[i]; 292 double td = (b * b * b - b) * derivatives[i + 1]; 293 double y = ta + tb + (delta2 / 6) * (tc + td); 294 if (y > h) { 295 y = h; 296 } 297 if (y < 0) { 298 y = 0; 299 } 300 path.lineTo((float) x, (float) y); 301 } 302 } 303 canvas.save(); 304 canvas.translate(dx, dy); 305 drawGrid(canvas, w, h); 306 ControlPoint lastPoint = points[points.length - 1]; 307 path.lineTo(lastPoint.x, lastPoint.y); 308 path.lineTo(w, lastPoint.y); 309 Paint paint = new Paint(); 310 paint.setAntiAlias(true); 311 paint.setFilterBitmap(true); 312 paint.setDither(true); 313 paint.setStyle(Paint.Style.STROKE); 314 int curveWidth = mCurveWidth; 315 if (showHandles) { 316 curveWidth *= 1.5; 317 } 318 paint.setStrokeWidth(curveWidth + 2); 319 paint.setColor(Color.BLACK); 320 canvas.drawPath(path, paint); 321 322 if (moving && mCurrentControlPoint != null) { 323 float px = mCurrentControlPoint.x * w; 324 float py = mCurrentControlPoint.y * h; 325 paint.setStrokeWidth(3); 326 paint.setColor(Color.BLACK); 327 canvas.drawLine(px, py, px, h, paint); 328 canvas.drawLine(0, py, px, py, paint); 329 paint.setStrokeWidth(1); 330 paint.setColor(color); 331 canvas.drawLine(px, py, px, h, paint); 332 canvas.drawLine(0, py, px, py, paint); 333 } 334 335 paint.setStrokeWidth(curveWidth); 336 paint.setColor(color); 337 canvas.drawPath(path, paint); 338 if (showHandles) { 339 for (int i = 0; i < points.length; i++) { 340 float x = points[i].x; 341 float y = points[i].y; 342 drawHandles(canvas, mCurveHandle, x, y); 343 } 344 } 345 canvas.restore(); 346 } 347 348 double[] solveSystem(ControlPoint[] points) { 349 int n = points.length; 350 double[][] system = new double[n][3]; 351 double[] result = new double[n]; // d 352 double[] solution = new double[n]; // returned coefficients 353 system[0][1] = 1; 354 system[n - 1][1] = 1; 355 double d6 = 1.0 / 6.0; 356 double d3 = 1.0 / 3.0; 357 358 // let's create a tridiagonal matrix representing the 359 // system, and apply the TDMA algorithm to solve it 360 // (see http://en.wikipedia.org/wiki/Tridiagonal_matrix_algorithm) 361 for (int i = 1; i < n - 1; i++) { 362 double deltaPrevX = points[i].x - points[i - 1].x; 363 double deltaX = points[i + 1].x - points[i - 1].x; 364 double deltaNextX = points[i + 1].x - points[i].x; 365 double deltaNextY = points[i + 1].y - points[i].y; 366 double deltaPrevY = points[i].y - points[i - 1].y; 367 system[i][0] = d6 * deltaPrevX; // a_i 368 system[i][1] = d3 * deltaX; // b_i 369 system[i][2] = d6 * deltaNextX; // c_i 370 result[i] = (deltaNextY / deltaNextX) - (deltaPrevY / deltaPrevX); // d_i 371 } 372 373 // Forward sweep 374 for (int i = 1; i < n; i++) { 375 // m = a_i/b_i-1 376 double m = system[i][0] / system[i - 1][1]; 377 // b_i = b_i - m(c_i-1) 378 system[i][1] = system[i][1] - m * system[i - 1][2]; 379 // d_i = d_i - m(d_i-1) 380 result[i] = result[i] - m * result[i - 1]; 381 } 382 383 // Back substitution 384 solution[n - 1] = result[n - 1] / system[n - 1][1]; 385 for (int i = n - 2; i >= 0; --i) { 386 solution[i] = (result[i] - system[i][2] * solution[i + 1]) / system[i][1]; 387 } 388 return solution; 389 } 390 391 public int addPoint(float x, float y) { 392 return addPoint(new ControlPoint(x, y)); 393 } 394 395 public int addPoint(ControlPoint v) { 396 mPoints.add(v); 397 Collections.sort(mPoints); 398 return mPoints.indexOf(v); 399 } 400 401 public void deletePoint(int n) { 402 mPoints.remove(n); 403 if (mPoints.size() < 2) { 404 reset(); 405 } 406 Collections.sort(mPoints); 407 } 408 409 public int getNbPoints() { 410 return mPoints.size(); 411 } 412 413 public ControlPoint getPoint(int n) { 414 return mPoints.elementAt(n); 415 } 416 417 public boolean isPointContained(float x, int n) { 418 for (int i = 0; i < n; i++) { 419 ControlPoint point = mPoints.elementAt(i); 420 if (point.x > x) { 421 return false; 422 } 423 } 424 for (int i = n + 1; i < mPoints.size(); i++) { 425 ControlPoint point = mPoints.elementAt(i); 426 if (point.x < x) { 427 return false; 428 } 429 } 430 return true; 431 } 432 433 public Spline copy() { 434 Spline spline = new Spline(); 435 for (int i = 0; i < mPoints.size(); i++) { 436 ControlPoint point = mPoints.elementAt(i); 437 spline.addPoint(point.copy()); 438 } 439 return spline; 440 } 441 442 public void show() { 443 Log.v(LOGTAG, "show curve " + this); 444 for (int i = 0; i < mPoints.size(); i++) { 445 ControlPoint point = mPoints.elementAt(i); 446 Log.v(LOGTAG, "point " + i + " is (" + point.x + ", " + point.y + ")"); 447 } 448 } 449 450 } 451
