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