Spline.java revision 599393ecad6803161d5e901ef625e34cfe088009
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 17package com.android.gallery3d.filtershow.ui; 18 19import android.graphics.Canvas; 20import android.graphics.Color; 21import android.graphics.Paint; 22import android.graphics.Path; 23import android.graphics.drawable.Drawable; 24import android.util.Log; 25 26import java.util.Collections; 27import java.util.Vector; 28 29public 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 private void didMovePoint(ControlPoint point) { 87 mCurrentControlPoint = point; 88 } 89 90 public void movePoint(int pick, float x, float y) { 91 if (pick < 0 || pick > mPoints.size() - 1) { 92 return; 93 } 94 ControlPoint point = mPoints.elementAt(pick); 95 point.x = x; 96 point.y = y; 97 didMovePoint(point); 98 } 99 100 public boolean isOriginal() { 101 if (this.getNbPoints() > 2) { 102 return false; 103 } 104 if (mPoints.elementAt(0).x != 0 || mPoints.elementAt(0).y != 1) { 105 return false; 106 } 107 if (mPoints.elementAt(1).x != 1 || mPoints.elementAt(1).y != 0) { 108 return false; 109 } 110 return true; 111 } 112 113 private void drawHandles(Canvas canvas, Drawable indicator, float centerX, float centerY) { 114 int left = (int) centerX - mCurveHandleSize / 2; 115 int top = (int) centerY - mCurveHandleSize / 2; 116 indicator.setBounds(left, top, left + mCurveHandleSize, top + mCurveHandleSize); 117 indicator.draw(canvas); 118 } 119 120 public float[] getAppliedCurve() { 121 float[] curve = new float[256]; 122 ControlPoint[] points = new ControlPoint[mPoints.size()]; 123 for (int i = 0; i < mPoints.size(); i++) { 124 ControlPoint p = mPoints.get(i); 125 points[i] = new ControlPoint(p.x, p.y); 126 } 127 double[] derivatives = solveSystem(points); 128 int start = 0; 129 int end = 256; 130 if (points[0].x != 0) { 131 start = (int) (points[0].x * 256); 132 } 133 if (points[points.length - 1].x != 1) { 134 end = (int) (points[points.length - 1].x * 256); 135 } 136 for (int i = 0; i < start; i++) { 137 curve[i] = 1.0f - points[0].y; 138 } 139 for (int i = end; i < 256; i++) { 140 curve[i] = 1.0f - points[points.length - 1].y; 141 } 142 for (int i = start; i < end; i++) { 143 ControlPoint cur = null; 144 ControlPoint next = null; 145 double x = i / 256.0; 146 int pivot = 0; 147 for (int j = 0; j < points.length - 1; j++) { 148 if (x >= points[j].x && x <= points[j + 1].x) { 149 pivot = j; 150 } 151 } 152 cur = points[pivot]; 153 next = points[pivot + 1]; 154 if (x <= next.x) { 155 double x1 = cur.x; 156 double x2 = next.x; 157 double y1 = cur.y; 158 double y2 = next.y; 159 160 // Use the second derivatives to apply the cubic spline 161 // equation: 162 double delta = (x2 - x1); 163 double delta2 = delta * delta; 164 double b = (x - x1) / delta; 165 double a = 1 - b; 166 double ta = a * y1; 167 double tb = b * y2; 168 double tc = (a * a * a - a) * derivatives[pivot]; 169 double td = (b * b * b - b) * derivatives[pivot + 1]; 170 double y = ta + tb + (delta2 / 6) * (tc + td); 171 if (y > 1.0f) { 172 y = 1.0f; 173 } 174 if (y < 0) { 175 y = 0; 176 } 177 curve[i] = (float) (1.0f - y); 178 } else { 179 curve[i] = 1.0f - next.y; 180 } 181 } 182 return curve; 183 } 184 185 private void drawGrid(Canvas canvas, float w, float h) { 186 // Grid 187 gPaint.setARGB(128, 150, 150, 150); 188 gPaint.setStrokeWidth(1); 189 190 float stepH = h / 9; 191 float stepW = w / 9; 192 193 // central diagonal 194 gPaint.setARGB(255, 100, 100, 100); 195 gPaint.setStrokeWidth(2); 196 canvas.drawLine(0, h, w, 0, gPaint); 197 198 gPaint.setARGB(128, 200, 200, 200); 199 gPaint.setStrokeWidth(4); 200 stepH = h / 3; 201 stepW = w / 3; 202 for (int j = 1; j < 3; j++) { 203 canvas.drawLine(0, j * stepH, w, j * stepH, gPaint); 204 canvas.drawLine(j * stepW, 0, j * stepW, h, gPaint); 205 } 206 canvas.drawLine(0, 0, 0, h, gPaint); 207 canvas.drawLine(w, 0, w, h, gPaint); 208 canvas.drawLine(0, 0, w, 0, gPaint); 209 canvas.drawLine(0, h, w, h, gPaint); 210 } 211 212 public void draw(Canvas canvas, int color, int canvasWidth, int canvasHeight, 213 boolean showHandles, boolean moving) { 214 float w = canvasWidth - mCurveHandleSize; 215 float h = canvasHeight - mCurveHandleSize; 216 float dx = mCurveHandleSize / 2; 217 float dy = mCurveHandleSize / 2; 218 219 // The cubic spline equation is (from numerical recipes in C): 220 // y = a(y_i) + b(y_i+1) + c(y"_i) + d(y"_i+1) 221 // 222 // with c(y"_i) and d(y"_i+1): 223 // c(y"_i) = 1/6 (a^3 - a) delta^2 (y"_i) 224 // d(y"_i_+1) = 1/6 (b^3 - b) delta^2 (y"_i+1) 225 // 226 // and delta: 227 // delta = x_i+1 - x_i 228 // 229 // To find the second derivatives y", we can rearrange the equation as: 230 // A(y"_i-1) + B(y"_i) + C(y"_i+1) = D 231 // 232 // With the coefficients A, B, C, D: 233 // A = 1/6 (x_i - x_i-1) 234 // B = 1/3 (x_i+1 - x_i-1) 235 // C = 1/6 (x_i+1 - x_i) 236 // D = (y_i+1 - y_i)/(x_i+1 - x_i) - (y_i - y_i-1)/(x_i - x_i-1) 237 // 238 // We can now easily solve the equation to find the second derivatives: 239 ControlPoint[] points = new ControlPoint[mPoints.size()]; 240 for (int i = 0; i < mPoints.size(); i++) { 241 ControlPoint p = mPoints.get(i); 242 points[i] = new ControlPoint(p.x * w, p.y * h); 243 } 244 double[] derivatives = solveSystem(points); 245 246 Path path = new Path(); 247 path.moveTo(0, points[0].y); 248 for (int i = 0; i < points.length - 1; i++) { 249 double x1 = points[i].x; 250 double x2 = points[i + 1].x; 251 double y1 = points[i].y; 252 double y2 = points[i + 1].y; 253 254 for (double x = x1; x < x2; x += 20) { 255 // Use the second derivatives to apply the cubic spline 256 // equation: 257 double delta = (x2 - x1); 258 double delta2 = delta * delta; 259 double b = (x - x1) / delta; 260 double a = 1 - b; 261 double ta = a * y1; 262 double tb = b * y2; 263 double tc = (a * a * a - a) * derivatives[i]; 264 double td = (b * b * b - b) * derivatives[i + 1]; 265 double y = ta + tb + (delta2 / 6) * (tc + td); 266 if (y > h) { 267 y = h; 268 } 269 if (y < 0) { 270 y = 0; 271 } 272 path.lineTo((float) x, (float) y); 273 } 274 } 275 canvas.save(); 276 canvas.translate(dx, dy); 277 drawGrid(canvas, w, h); 278 ControlPoint lastPoint = points[points.length - 1]; 279 path.lineTo(lastPoint.x, lastPoint.y); 280 path.lineTo(w, lastPoint.y); 281 Paint paint = new Paint(); 282 paint.setAntiAlias(true); 283 paint.setFilterBitmap(true); 284 paint.setDither(true); 285 paint.setStyle(Paint.Style.STROKE); 286 int curveWidth = mCurveWidth; 287 if (showHandles) { 288 curveWidth *= 1.5; 289 } 290 paint.setStrokeWidth(curveWidth + 2); 291 paint.setColor(Color.BLACK); 292 canvas.drawPath(path, paint); 293 294 if (moving && mCurrentControlPoint != null) { 295 float px = mCurrentControlPoint.x * w; 296 float py = mCurrentControlPoint.y * h; 297 paint.setStrokeWidth(3); 298 paint.setColor(Color.BLACK); 299 canvas.drawLine(px, py, px, h, paint); 300 canvas.drawLine(0, py, px, py, paint); 301 paint.setStrokeWidth(1); 302 paint.setColor(color); 303 canvas.drawLine(px, py, px, h, paint); 304 canvas.drawLine(0, py, px, py, paint); 305 } 306 307 paint.setStrokeWidth(curveWidth); 308 paint.setColor(color); 309 canvas.drawPath(path, paint); 310 if (showHandles) { 311 for (int i = 0; i < points.length; i++) { 312 float x = points[i].x; 313 float y = points[i].y; 314 drawHandles(canvas, mCurveHandle, x, y); 315 } 316 } 317 canvas.restore(); 318 } 319 320 double[] solveSystem(ControlPoint[] points) { 321 int n = points.length; 322 double[][] system = new double[n][3]; 323 double[] result = new double[n]; // d 324 double[] solution = new double[n]; // returned coefficients 325 system[0][1] = 1; 326 system[n - 1][1] = 1; 327 double d6 = 1.0 / 6.0; 328 double d3 = 1.0 / 3.0; 329 330 // let's create a tridiagonal matrix representing the 331 // system, and apply the TDMA algorithm to solve it 332 // (see http://en.wikipedia.org/wiki/Tridiagonal_matrix_algorithm) 333 for (int i = 1; i < n - 1; i++) { 334 double deltaPrevX = points[i].x - points[i - 1].x; 335 double deltaX = points[i + 1].x - points[i - 1].x; 336 double deltaNextX = points[i + 1].x - points[i].x; 337 double deltaNextY = points[i + 1].y - points[i].y; 338 double deltaPrevY = points[i].y - points[i - 1].y; 339 system[i][0] = d6 * deltaPrevX; // a_i 340 system[i][1] = d3 * deltaX; // b_i 341 system[i][2] = d6 * deltaNextX; // c_i 342 result[i] = (deltaNextY / deltaNextX) - (deltaPrevY / deltaPrevX); // d_i 343 } 344 345 // Forward sweep 346 for (int i = 1; i < n; i++) { 347 // m = a_i/b_i-1 348 double m = system[i][0] / system[i - 1][1]; 349 // b_i = b_i - m(c_i-1) 350 system[i][1] = system[i][1] - m * system[i - 1][2]; 351 // d_i = d_i - m(d_i-1) 352 result[i] = result[i] - m * result[i - 1]; 353 } 354 355 // Back substitution 356 solution[n - 1] = result[n - 1] / system[n - 1][1]; 357 for (int i = n - 2; i >= 0; --i) { 358 solution[i] = (result[i] - system[i][2] * solution[i + 1]) / system[i][1]; 359 } 360 return solution; 361 } 362 363 public int addPoint(float x, float y) { 364 return addPoint(new ControlPoint(x, y)); 365 } 366 367 public int addPoint(ControlPoint v) { 368 mPoints.add(v); 369 Collections.sort(mPoints); 370 return mPoints.indexOf(v); 371 } 372 373 public void deletePoint(int n) { 374 mPoints.remove(n); 375 Collections.sort(mPoints); 376 } 377 378 public int getNbPoints() { 379 return mPoints.size(); 380 } 381 382 public ControlPoint getPoint(int n) { 383 return mPoints.elementAt(n); 384 } 385 386 public boolean isPointContained(float x, int n) { 387 for (int i = 0; i < n; i++) { 388 ControlPoint point = mPoints.elementAt(i); 389 if (point.x > x) { 390 return false; 391 } 392 } 393 for (int i = n + 1; i < mPoints.size(); i++) { 394 ControlPoint point = mPoints.elementAt(i); 395 if (point.x < x) { 396 return false; 397 } 398 } 399 return true; 400 } 401 402 public Spline copy() { 403 Spline spline = new Spline(); 404 for (int i = 0; i < mPoints.size(); i++) { 405 ControlPoint point = mPoints.elementAt(i); 406 spline.addPoint(point.copy()); 407 } 408 return spline; 409 } 410 411 public void show() { 412 Log.v(LOGTAG, "show curve " + this); 413 for (int i = 0; i < mPoints.size(); i++) { 414 ControlPoint point = mPoints.elementAt(i); 415 Log.v(LOGTAG, "point " + i + " is (" + point.x + ", " + point.y + ")"); 416 } 417 } 418 419} 420