1 /* 2 * Copyright (C) 2018 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 android.view.math; 18 19 public class Math3DHelper { 20 21 private static final float EPSILON = 0.0000001f; 22 Math3DHelper()23 private Math3DHelper() { } 24 25 /** 26 * Calculates [p1x+t*(p2x-p1x)=dx*t2+px,p1y+t*(p2y-p1y)=dy*t2+py],[t,t2]; 27 * 28 * @param d - dimension in which the poly is represented (supports 2 or 3D) 29 * @return float[]{t2, t, p1} or float[]{Float.NaN} 30 */ rayIntersectPoly(float[] poly, int polyLength, float px, float py, float dx, float dy, int d)31 public static float[] rayIntersectPoly(float[] poly, int polyLength, float px, float py, 32 float dx, float dy, int d) { 33 int p1 = polyLength - 1; 34 for (int p2 = 0; p2 < polyLength; p2++) { 35 float p1x = poly[p1 * d + 0]; 36 float p1y = poly[p1 * d + 1]; 37 float p2x = poly[p2 * d + 0]; 38 float p2y = poly[p2 * d + 1]; 39 float div = (dx * (p1y - p2y) + dy * (p2x - p1x)); 40 if (div != 0) { 41 float t = (dx * (p1y - py) + dy * (px - p1x)) / div; 42 if (t >= 0 && t <= 1) { 43 float t2 = (p1x * (py - p2y) 44 + p2x * (p1y - py) 45 + px * (p2y - p1y)) 46 / div; 47 if (t2 > 0) { 48 return new float[]{t2, t, p1}; 49 } 50 } 51 } 52 p1 = p2; 53 } 54 return new float[]{Float.NaN}; 55 } 56 centroid2d(float[] poly, int len, float[] ret)57 public static void centroid2d(float[] poly, int len, float[] ret) { 58 float sumx = 0; 59 float sumy = 0; 60 int p1 = len - 1; 61 float area = 0; 62 for (int p2 = 0; p2 < len; p2++) { 63 float x1 = poly[p1 * 2 + 0]; 64 float y1 = poly[p1 * 2 + 1]; 65 float x2 = poly[p2 * 2 + 0]; 66 float y2 = poly[p2 * 2 + 1]; 67 float a = (x1 * y2 - x2 * y1); 68 sumx += (x1 + x2) * a; 69 sumy += (y1 + y2) * a; 70 area += a; 71 p1 = p2; 72 } 73 float centroidx = sumx / (3 * area); 74 float centroidy = sumy / (3 * area); 75 ret[0] = centroidx; 76 ret[1] = centroidy; 77 } 78 centroid3d(float[] poly, int len, float[] ret)79 public static void centroid3d(float[] poly, int len, float[] ret) { 80 int n = len - 1; 81 double area = 0; 82 double cx = 0; 83 double cy = 0; 84 double cz = 0; 85 for (int i = 1; i < n; i++) { 86 int k = i + 1; 87 float a0 = poly[i * 3 + 0] - poly[0 * 3 + 0]; 88 float a1 = poly[i * 3 + 1] - poly[0 * 3 + 1]; 89 float a2 = poly[i * 3 + 2] - poly[0 * 3 + 2]; 90 float b0 = poly[k * 3 + 0] - poly[0 * 3 + 0]; 91 float b1 = poly[k * 3 + 1] - poly[0 * 3 + 1]; 92 float b2 = poly[k * 3 + 2] - poly[0 * 3 + 2]; 93 float c0 = a1 * b2 - b1 * a2; 94 float c1 = a2 * b0 - b2 * a0; 95 float c2 = a0 * b1 - b0 * a1; 96 double areaOfTriangle = Math.sqrt(c0 * c0 + c1 * c1 + c2 * c2); 97 area += areaOfTriangle; 98 cx += areaOfTriangle * (poly[i * 3 + 0] + poly[k * 3 + 0] + poly[0 * 3 + 0]); 99 cy += areaOfTriangle * (poly[i * 3 + 1] + poly[k * 3 + 1] + poly[0 * 3 + 1]); 100 cz += areaOfTriangle * (poly[i * 3 + 2] + poly[k * 3 + 2] + poly[0 * 3 + 2]); 101 } 102 ret[0] = (float) (cx / (3 * area)); 103 ret[1] = (float) (cy / (3 * area)); 104 ret[2] = (float) (cz / (3 * area)); 105 } 106 min(int x1, int x2, int x3)107 public final static int min(int x1, int x2, int x3) { 108 return (x1 > x2) ? ((x2 > x3) ? x3 : x2) : ((x1 > x3) ? x3 : x1); 109 } 110 max(int x1, int x2, int x3)111 public final static int max(int x1, int x2, int x3) { 112 return (x1 < x2) ? ((x2 < x3) ? x3 : x2) : ((x1 < x3) ? x3 : x1); 113 } 114 xsort(float[] points, int pointsLength)115 private static void xsort(float[] points, int pointsLength) { 116 quicksortX(points, 0, pointsLength - 1); 117 } 118 hull(float[] points, int pointsLength, float[] retPoly)119 public static int hull(float[] points, int pointsLength, float[] retPoly) { 120 xsort(points, pointsLength); 121 int n = pointsLength; 122 float[] lUpper = new float[n * 2]; 123 lUpper[0] = points[0]; 124 lUpper[1] = points[1]; 125 lUpper[2] = points[2]; 126 lUpper[3] = points[3]; 127 128 int lUpperSize = 2; 129 130 for (int i = 2; i < n; i++) { 131 lUpper[lUpperSize * 2 + 0] = points[i * 2 + 0]; 132 lUpper[lUpperSize * 2 + 1] = points[i * 2 + 1]; 133 lUpperSize++; 134 135 while (lUpperSize > 2 && !rightTurn( 136 lUpper[(lUpperSize - 3) * 2], lUpper[(lUpperSize - 3) * 2 + 1], 137 lUpper[(lUpperSize - 2) * 2], lUpper[(lUpperSize - 2) * 2 + 1], 138 lUpper[(lUpperSize - 1) * 2], lUpper[(lUpperSize - 1) * 2 + 1])) { 139 // Remove the middle point of the three last 140 lUpper[(lUpperSize - 2) * 2 + 0] = lUpper[(lUpperSize - 1) * 2 + 0]; 141 lUpper[(lUpperSize - 2) * 2 + 1] = lUpper[(lUpperSize - 1) * 2 + 1]; 142 lUpperSize--; 143 } 144 } 145 146 float[] lLower = new float[n * 2]; 147 lLower[0] = points[(n - 1) * 2 + 0]; 148 lLower[1] = points[(n - 1) * 2 + 1]; 149 lLower[2] = points[(n - 2) * 2 + 0]; 150 lLower[3] = points[(n - 2) * 2 + 1]; 151 152 int lLowerSize = 2; 153 154 for (int i = n - 3; i >= 0; i--) { 155 lLower[lLowerSize * 2 + 0] = points[i * 2 + 0]; 156 lLower[lLowerSize * 2 + 1] = points[i * 2 + 1]; 157 lLowerSize++; 158 159 while (lLowerSize > 2 && !rightTurn( 160 lLower[(lLowerSize - 3) * 2], lLower[(lLowerSize - 3) * 2 + 1], 161 lLower[(lLowerSize - 2) * 2], lLower[(lLowerSize - 2) * 2 + 1], 162 lLower[(lLowerSize - 1) * 2], lLower[(lLowerSize - 1) * 2 + 1])) { 163 // Remove the middle point of the three last 164 lLower[(lLowerSize - 2) * 2 + 0] = lLower[(lLowerSize - 1) * 2 + 0]; 165 lLower[(lLowerSize - 2) * 2 + 1] = lLower[(lLowerSize - 1) * 2 + 1]; 166 lLowerSize--; 167 } 168 } 169 int count = 0; 170 171 for (int i = 0; i < lUpperSize; i++) { 172 retPoly[count * 2 + 0] = lUpper[i * 2 + 0]; 173 retPoly[count * 2 + 1] = lUpper[i * 2 + 1]; 174 count++; 175 } 176 177 for (int i = 1; i < lLowerSize - 1; i++) { 178 retPoly[count * 2 + 0] = lLower[i * 2 + 0]; 179 retPoly[count * 2 + 1] = lLower[i * 2 + 1]; 180 count++; 181 } 182 183 return count; 184 } 185 rightTurn(float ax, float ay, float bx, float by, float cx, float cy)186 private static boolean rightTurn(float ax, float ay, float bx, float by, float cx, float cy) { 187 return (bx - ax) * (cy - ay) - (by - ay) * (cx - ax) > 0.00001; 188 } 189 190 /** 191 * Calculates the intersection of poly1 with poly2 and puts in poly2 192 * @return number of point in poly2 193 */ intersection( float[] poly1, int poly1length, float[] poly2, int poly2length)194 public static int intersection( 195 float[] poly1, int poly1length, float[] poly2, int poly2length) { 196 makeClockwise(poly1, poly1length); 197 makeClockwise(poly2, poly2length); 198 float[] poly = new float[(poly1length * poly2length + 2) * 2]; 199 int count = 0; 200 int pcount = 0; 201 for (int i = 0; i < poly1length; i++) { 202 if (pointInsidePolygon(poly1[i * 2], poly1[i * 2 + 1], poly2, poly2length)) { 203 poly[count * 2] = poly1[i * 2]; 204 poly[count * 2 + 1] = poly1[i * 2 + 1]; 205 count++; 206 pcount++; 207 } 208 } 209 int fromP1 = pcount; 210 for (int i = 0; i < poly2length; i++) { 211 if (pointInsidePolygon(poly2[i * 2], poly2[i * 2 + 1], poly1, poly1length)) { 212 poly[count * 2] = poly2[i * 2]; 213 poly[count * 2 + 1] = poly2[i * 2 + 1]; 214 count++; 215 } 216 } 217 int fromP2 = count - fromP1; 218 if (fromP1 == poly1length) { // use p1 219 for (int i = 0; i < poly1length; i++) { 220 poly2[i * 2] = poly1[i * 2]; 221 poly2[i * 2 + 1] = poly1[i * 2 + 1]; 222 } 223 return poly1length; 224 } 225 if (fromP2 == poly2length) { // use p2 226 return poly2length; 227 } 228 float[] intersection = new float[2]; 229 for (int i = 0; i < poly2length; i++) { 230 for (int j = 0; j < poly1length; j++) { 231 int i1_by_2 = i * 2; 232 int i2_by_2 = ((i + 1) % poly2length) * 2; 233 int j1_by_2 = j * 2; 234 int j2_by_2 = ((j + 1) % poly1length) * 2; 235 boolean found = lineIntersection( 236 poly2[i1_by_2], poly2[i1_by_2 + 1], 237 poly2[i2_by_2], poly2[i2_by_2 + 1], 238 poly1[j1_by_2], poly1[j1_by_2 + 1], 239 poly1[j2_by_2], poly1[j2_by_2 + 1], intersection); 240 if (found) { 241 poly[count * 2] = intersection[0]; 242 poly[count * 2 + 1] = intersection[1]; 243 count++; 244 } else { 245 float dx = poly2[i * 2] - poly1[j * 2]; 246 float dy = poly2[i * 2 + 1] - poly1[j * 2 + 1]; 247 248 if (dx * dx + dy * dy < 0.01) { 249 poly[count * 2] = poly2[i * 2]; 250 poly[count * 2 + 1] = poly2[i * 2 + 1]; 251 count++; 252 } 253 } 254 } 255 } 256 if (count == 0) { 257 return 0; 258 } 259 float avgx = 0; 260 float avgy = 0; 261 for (int i = 0; i < count; i++) { 262 avgx += poly[i * 2]; 263 avgy += poly[i * 2 + 1]; 264 } 265 avgx /= count; 266 avgy /= count; 267 268 float[] ctr = new float[] { avgx, avgy }; 269 sort(poly, count, ctr); 270 int size = count; 271 272 poly2[0] = poly[0]; 273 poly2[1] = poly[1]; 274 275 count = 1; 276 for (int i = 1; i < size; i++) { 277 float dx = poly[i * 2] - poly[(i - 1) * 2]; 278 float dy = poly[i * 2 + 1] - poly[(i - 1) * 2 + 1]; 279 if (dx * dx + dy * dy >= 0.01) { 280 poly2[count * 2] = poly[i * 2]; 281 poly2[count * 2 + 1] = poly[i * 2 + 1]; 282 count++; 283 } 284 } 285 return count; 286 } 287 sort(float[] poly, int polyLength, float[] ctr)288 public static void sort(float[] poly, int polyLength, float[] ctr) { 289 quicksortCirc(poly, 0, polyLength - 1, ctr); 290 } 291 angle(float x1, float y1, float[] ctr)292 public static float angle(float x1, float y1, float[] ctr) { 293 return -(float) Math.atan2(x1 - ctr[0], y1 - ctr[1]); 294 } 295 swap(float[] points, int i, int j)296 private static void swap(float[] points, int i, int j) { 297 float x = points[i * 2]; 298 float y = points[i * 2 + 1]; 299 points[i * 2] = points[j * 2]; 300 points[i * 2 + 1] = points[j * 2 + 1]; 301 points[j * 2] = x; 302 points[j * 2 + 1] = y; 303 } 304 quicksortCirc(float[] points, int low, int high, float[] ctr)305 private static void quicksortCirc(float[] points, int low, int high, float[] ctr) { 306 int i = low, j = high; 307 int p = low + (high - low) / 2; 308 float pivot = angle(points[p * 2], points[p * 2 + 1], ctr); 309 while (i <= j) { 310 while (angle(points[i * 2], points[i * 2 + 1], ctr) < pivot) { 311 i++; 312 } 313 while (angle(points[j * 2], points[j * 2 + 1], ctr) > pivot) { 314 j--; 315 } 316 317 if (i <= j) { 318 swap(points, i, j); 319 i++; 320 j--; 321 } 322 } 323 if (low < j) { 324 quicksortCirc(points, low, j, ctr); 325 } 326 if (i < high) { 327 quicksortCirc(points, i, high, ctr); 328 } 329 } 330 quicksortX(float[] points, int low, int high)331 private static void quicksortX(float[] points, int low, int high) { 332 int i = low, j = high; 333 int p = low + (high - low) / 2; 334 float pivot = points[p * 2]; 335 while (i <= j) { 336 while (points[i * 2] < pivot) { 337 i++; 338 } 339 while (points[j * 2] > pivot) { 340 j--; 341 } 342 343 if (i <= j) { 344 swap(points, i, j); 345 i++; 346 j--; 347 } 348 } 349 if (low < j) { 350 quicksortX(points, low, j); 351 } 352 if (i < high) { 353 quicksortX(points, i, high); 354 } 355 } 356 pointInsidePolygon(float x, float y, float[] poly, int len)357 private static boolean pointInsidePolygon(float x, float y, float[] poly, int len) { 358 boolean c = false; 359 float testx = x; 360 float testy = y; 361 for (int i = 0, j = len - 1; i < len; j = i++) { 362 if (((poly[i * 2 + 1] > testy) != (poly[j * 2 + 1] > testy)) && 363 (testx < (poly[j * 2] - poly[i * 2]) * (testy - poly[i * 2 + 1]) 364 / (poly[j * 2 + 1] - poly[i * 2 + 1]) + poly[i * 2])) { 365 c = !c; 366 } 367 } 368 return c; 369 } 370 makeClockwise(float[] polygon, int len)371 private static void makeClockwise(float[] polygon, int len) { 372 if (polygon == null || len == 0) { 373 return; 374 } 375 if (!isClockwise(polygon, len)) { 376 reverse(polygon, len); 377 } 378 } 379 isClockwise(float[] polygon, int len)380 private static boolean isClockwise(float[] polygon, int len) { 381 float sum = 0; 382 float p1x = polygon[(len - 1) * 2]; 383 float p1y = polygon[(len - 1) * 2 + 1]; 384 for (int i = 0; i < len; i++) { 385 386 float p2x = polygon[i * 2]; 387 float p2y = polygon[i * 2 + 1]; 388 sum += p1x * p2y - p2x * p1y; 389 p1x = p2x; 390 p1y = p2y; 391 } 392 return sum < 0; 393 } 394 reverse(float[] polygon, int len)395 private static void reverse(float[] polygon, int len) { 396 int n = len / 2; 397 for (int i = 0; i < n; i++) { 398 float tmp0 = polygon[i * 2]; 399 float tmp1 = polygon[i * 2 + 1]; 400 int k = len - 1 - i; 401 polygon[i * 2] = polygon[k * 2]; 402 polygon[i * 2 + 1] = polygon[k * 2 + 1]; 403 polygon[k * 2] = tmp0; 404 polygon[k * 2 + 1] = tmp1; 405 } 406 } 407 408 /** 409 * Intersects two lines in parametric form. 410 */ lineIntersection( float x1, float y1, float x2, float y2, float x3, float y3, float x4, float y4, float[] ret)411 private static final boolean lineIntersection( 412 float x1, float y1, 413 float x2, float y2, 414 float x3, float y3, 415 float x4, float y4, 416 float[] ret) { 417 418 float d = (x1 - x2) * (y3 - y4) - (y1 - y2) * (x3 - x4); 419 if (d == 0.000f) { 420 return false; 421 } 422 423 float dx = (x1 * y2 - y1 * x2); 424 float dy = (x3 * y4 - y3 * x4); 425 float x = (dx * (x3 - x4) - (x1 - x2) * dy) / d; 426 float y = (dx * (y3 - y4) - (y1 - y2) * dy) / d; 427 428 if (((x - x1) * (x - x2) > EPSILON) 429 || ((x - x3) * (x - x4) > EPSILON) 430 || ((y - y1) * (y - y2) > EPSILON) 431 || ((y - y3) * (y - y4) > EPSILON)) { 432 433 return false; 434 } 435 ret[0] = x; 436 ret[1] = y; 437 return true; 438 } 439 440 /** 441 * Imagine a donut shaped image and trying to create triangles from its centroid (like 442 * cutting a pie). This function performs such action (and also edge-case triangle strips 443 * generation) then returns the resulting triangle strips. 444 * 445 * @param retstrips - the resulting triangle strips 446 */ donutPie2(float[] penumbra, int penumbraLength, float[] umbra, int umbraLength, int rays, int layers, float strength, float[] retstrips)447 public static void donutPie2(float[] penumbra, int penumbraLength, 448 float[] umbra, int umbraLength, int rays, int layers, float strength, 449 float[] retstrips) { 450 int rings = layers + 1; 451 452 double step = Math.PI * 2 / rays; 453 float[] retxy = new float[2]; 454 centroid2d(umbra, umbraLength, retxy); 455 float cx = retxy[0]; 456 float cy = retxy[1]; 457 458 float[] t1 = new float[rays]; 459 float[] t2 = new float[rays]; 460 461 for (int i = 0; i < rays; i++) { 462 float dx = (float) Math.sin(Math.PI / 4 + step * i); 463 float dy = (float) Math.cos(Math.PI / 4 + step * i); 464 t2[i] = rayIntersectPoly(umbra, umbraLength, cx, cy, dx, dy, 2)[0]; 465 t1[i] = rayIntersectPoly(penumbra, penumbraLength, cx, cy, dx, dy, 2)[0]; 466 } 467 468 int p = 0; 469 // Calc the vertex 470 for (int r = 0; r < layers; r++) { 471 int startp = p; 472 for (int i = 0; i < rays; i++) { 473 float dx = (float) Math.sin(Math.PI / 4 + step * i); 474 float dy = (float) Math.cos(Math.PI / 4 + step * i); 475 476 for (int j = r; j < (r + 2); j++) { 477 float jf = j / (float) (rings - 1); 478 float t = t1[i] + jf * (t2[i] - t1[i]); 479 float op = (jf + 1 - 1 / (1 + (t - t1[i]) * (t - t1[i]))) / 2; 480 481 retstrips[p * 3] = dx * t + cx; 482 retstrips[p * 3 + 1] = dy * t + cy; 483 retstrips[p * 3 + 2] = jf * op * strength; 484 485 p++; 486 } 487 } 488 retstrips[p * 3] = retstrips[startp * 3]; 489 retstrips[p * 3 + 1] = retstrips[startp * 3 + 1]; 490 retstrips[p * 3 + 2] = retstrips[startp * 3 + 2]; 491 p++; 492 startp++; 493 retstrips[p * 3] = retstrips[startp * 3]; 494 retstrips[p * 3 + 1] = retstrips[startp * 3 + 1]; 495 retstrips[p * 3 + 2] = retstrips[startp * 3 + 2]; 496 p++; 497 } 498 int oldp = p - 1; 499 retstrips[p * 3] = retstrips[oldp * 3]; 500 retstrips[p * 3 + 1] = retstrips[oldp * 3 + 1]; 501 retstrips[p * 3 + 2] = retstrips[oldp * 3 + 2]; 502 p+=2; 503 504 oldp = p; 505 for (int k = 0; k < rays; k++) { 506 int i = k / 2; 507 if ((k & 1) == 1) { // traverse the inside in a zig zag pattern 508 // for strips 509 i = rays - i - 1; 510 } 511 float dx = (float) Math.sin(Math.PI / 4 + step * i); 512 float dy = (float) Math.cos(Math.PI / 4 + step * i); 513 514 float jf = 1; 515 516 float t = t1[i] + jf * (t2[i] - t1[i]); 517 float op = (jf + 1 - 1 / (1 + (t - t1[i]) * (t - t1[i]))) / 2; 518 519 retstrips[p * 3] = dx * t + cx; 520 retstrips[p * 3 + 1] = dy * t + cy; 521 retstrips[p * 3 + 2] = jf * op * strength; 522 p++; 523 } 524 p = oldp - 1; 525 retstrips[p * 3] = retstrips[oldp * 3]; 526 retstrips[p * 3 + 1] = retstrips[oldp * 3 + 1]; 527 retstrips[p * 3 + 2] = retstrips[oldp * 3 + 2]; 528 } 529 530 /** 531 * @return Rect bound of flattened (ignoring z). LTRB 532 * @param dimension - 2D or 3D 533 */ flatBound(float[] poly, int dimension)534 public static float[] flatBound(float[] poly, int dimension) { 535 int polySize = poly.length/dimension; 536 float left = poly[0]; 537 float right = poly[0]; 538 float top = poly[1]; 539 float bottom = poly[1]; 540 541 for (int i = 0; i < polySize; i++) { 542 float x = poly[i * dimension + 0]; 543 float y = poly[i * dimension + 1]; 544 545 if (left > x) { 546 left = x; 547 } else if (right < x) { 548 right = x; 549 } 550 551 if (top > y) { 552 top = y; 553 } else if (bottom < y) { 554 bottom = y; 555 } 556 } 557 return new float[]{left, top, right, bottom}; 558 } 559 560 /** 561 * Translate the polygon to x and y 562 * @param dimension in what dimension is polygon represented (supports 2 or 3D). 563 */ translate(float[] poly, float translateX, float translateY, int dimension)564 public static void translate(float[] poly, float translateX, float translateY, int dimension) { 565 int polySize = poly.length/dimension; 566 567 for (int i = 0; i < polySize; i++) { 568 poly[i * dimension + 0] += translateX; 569 poly[i * dimension + 1] += translateY; 570 } 571 } 572 573 } 574 575