| /* |
| * Copyright (C) 2018 The Android Open Source Project |
| * |
| * Licensed under the Apache License, Version 2.0 (the "License"); |
| * you may not use this file except in compliance with the License. |
| * You may obtain a copy of the License at |
| * |
| * http://www.apache.org/licenses/LICENSE-2.0 |
| * |
| * Unless required by applicable law or agreed to in writing, software |
| * distributed under the License is distributed on an "AS IS" BASIS, |
| * WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied. |
| * See the License for the specific language governing permissions and |
| * limitations under the License. |
| */ |
| |
| package android.view.math; |
| |
| public class Math3DHelper { |
| |
| private static final float EPSILON = 0.0000001f; |
| |
| private Math3DHelper() { } |
| |
| /** |
| * Calculates [p1x+t*(p2x-p1x)=dx*t2+px,p1y+t*(p2y-p1y)=dy*t2+py],[t,t2]; |
| * |
| * @param d - dimension in which the poly is represented (supports 2 or 3D) |
| * @return float[]{t2, t, p1} or float[]{Float.NaN} |
| */ |
| public static float[] rayIntersectPoly(float[] poly, int polyLength, float px, float py, |
| float dx, float dy, int d) { |
| int p1 = polyLength - 1; |
| for (int p2 = 0; p2 < polyLength; p2++) { |
| float p1x = poly[p1 * d + 0]; |
| float p1y = poly[p1 * d + 1]; |
| float p2x = poly[p2 * d + 0]; |
| float p2y = poly[p2 * d + 1]; |
| float div = (dx * (p1y - p2y) + dy * (p2x - p1x)); |
| if (div != 0) { |
| float t = (dx * (p1y - py) + dy * (px - p1x)) / div; |
| if (t >= 0 && t <= 1) { |
| float t2 = (p1x * (py - p2y) |
| + p2x * (p1y - py) |
| + px * (p2y - p1y)) |
| / div; |
| if (t2 > 0) { |
| return new float[]{t2, t, p1}; |
| } |
| } |
| } |
| p1 = p2; |
| } |
| return new float[]{Float.NaN}; |
| } |
| |
| public static void centroid2d(float[] poly, int len, float[] ret) { |
| float sumx = 0; |
| float sumy = 0; |
| int p1 = len - 1; |
| float area = 0; |
| for (int p2 = 0; p2 < len; p2++) { |
| float x1 = poly[p1 * 2 + 0]; |
| float y1 = poly[p1 * 2 + 1]; |
| float x2 = poly[p2 * 2 + 0]; |
| float y2 = poly[p2 * 2 + 1]; |
| float a = (x1 * y2 - x2 * y1); |
| sumx += (x1 + x2) * a; |
| sumy += (y1 + y2) * a; |
| area += a; |
| p1 = p2; |
| } |
| float centroidx = sumx / (3 * area); |
| float centroidy = sumy / (3 * area); |
| ret[0] = centroidx; |
| ret[1] = centroidy; |
| } |
| |
| public static void centroid3d(float[] poly, int len, float[] ret) { |
| int n = len - 1; |
| double area = 0; |
| double cx = 0; |
| double cy = 0; |
| double cz = 0; |
| for (int i = 1; i < n; i++) { |
| int k = i + 1; |
| float a0 = poly[i * 3 + 0] - poly[0 * 3 + 0]; |
| float a1 = poly[i * 3 + 1] - poly[0 * 3 + 1]; |
| float a2 = poly[i * 3 + 2] - poly[0 * 3 + 2]; |
| float b0 = poly[k * 3 + 0] - poly[0 * 3 + 0]; |
| float b1 = poly[k * 3 + 1] - poly[0 * 3 + 1]; |
| float b2 = poly[k * 3 + 2] - poly[0 * 3 + 2]; |
| float c0 = a1 * b2 - b1 * a2; |
| float c1 = a2 * b0 - b2 * a0; |
| float c2 = a0 * b1 - b0 * a1; |
| double areaOfTriangle = Math.sqrt(c0 * c0 + c1 * c1 + c2 * c2); |
| area += areaOfTriangle; |
| cx += areaOfTriangle * (poly[i * 3 + 0] + poly[k * 3 + 0] + poly[0 * 3 + 0]); |
| cy += areaOfTriangle * (poly[i * 3 + 1] + poly[k * 3 + 1] + poly[0 * 3 + 1]); |
| cz += areaOfTriangle * (poly[i * 3 + 2] + poly[k * 3 + 2] + poly[0 * 3 + 2]); |
| } |
| ret[0] = (float) (cx / (3 * area)); |
| ret[1] = (float) (cy / (3 * area)); |
| ret[2] = (float) (cz / (3 * area)); |
| } |
| |
| public final static int min(int x1, int x2, int x3) { |
| return (x1 > x2) ? ((x2 > x3) ? x3 : x2) : ((x1 > x3) ? x3 : x1); |
| } |
| |
| public final static int max(int x1, int x2, int x3) { |
| return (x1 < x2) ? ((x2 < x3) ? x3 : x2) : ((x1 < x3) ? x3 : x1); |
| } |
| |
| private static void xsort(float[] points, int pointsLength) { |
| quicksortX(points, 0, pointsLength - 1); |
| } |
| |
| public static int hull(float[] points, int pointsLength, float[] retPoly) { |
| xsort(points, pointsLength); |
| int n = pointsLength; |
| float[] lUpper = new float[n * 2]; |
| lUpper[0] = points[0]; |
| lUpper[1] = points[1]; |
| lUpper[2] = points[2]; |
| lUpper[3] = points[3]; |
| |
| int lUpperSize = 2; |
| |
| for (int i = 2; i < n; i++) { |
| lUpper[lUpperSize * 2 + 0] = points[i * 2 + 0]; |
| lUpper[lUpperSize * 2 + 1] = points[i * 2 + 1]; |
| lUpperSize++; |
| |
| while (lUpperSize > 2 && !rightTurn( |
| lUpper[(lUpperSize - 3) * 2], lUpper[(lUpperSize - 3) * 2 + 1], |
| lUpper[(lUpperSize - 2) * 2], lUpper[(lUpperSize - 2) * 2 + 1], |
| lUpper[(lUpperSize - 1) * 2], lUpper[(lUpperSize - 1) * 2 + 1])) { |
| // Remove the middle point of the three last |
| lUpper[(lUpperSize - 2) * 2 + 0] = lUpper[(lUpperSize - 1) * 2 + 0]; |
| lUpper[(lUpperSize - 2) * 2 + 1] = lUpper[(lUpperSize - 1) * 2 + 1]; |
| lUpperSize--; |
| } |
| } |
| |
| float[] lLower = new float[n * 2]; |
| lLower[0] = points[(n - 1) * 2 + 0]; |
| lLower[1] = points[(n - 1) * 2 + 1]; |
| lLower[2] = points[(n - 2) * 2 + 0]; |
| lLower[3] = points[(n - 2) * 2 + 1]; |
| |
| int lLowerSize = 2; |
| |
| for (int i = n - 3; i >= 0; i--) { |
| lLower[lLowerSize * 2 + 0] = points[i * 2 + 0]; |
| lLower[lLowerSize * 2 + 1] = points[i * 2 + 1]; |
| lLowerSize++; |
| |
| while (lLowerSize > 2 && !rightTurn( |
| lLower[(lLowerSize - 3) * 2], lLower[(lLowerSize - 3) * 2 + 1], |
| lLower[(lLowerSize - 2) * 2], lLower[(lLowerSize - 2) * 2 + 1], |
| lLower[(lLowerSize - 1) * 2], lLower[(lLowerSize - 1) * 2 + 1])) { |
| // Remove the middle point of the three last |
| lLower[(lLowerSize - 2) * 2 + 0] = lLower[(lLowerSize - 1) * 2 + 0]; |
| lLower[(lLowerSize - 2) * 2 + 1] = lLower[(lLowerSize - 1) * 2 + 1]; |
| lLowerSize--; |
| } |
| } |
| int count = 0; |
| |
| for (int i = 0; i < lUpperSize; i++) { |
| retPoly[count * 2 + 0] = lUpper[i * 2 + 0]; |
| retPoly[count * 2 + 1] = lUpper[i * 2 + 1]; |
| count++; |
| } |
| |
| for (int i = 1; i < lLowerSize - 1; i++) { |
| retPoly[count * 2 + 0] = lLower[i * 2 + 0]; |
| retPoly[count * 2 + 1] = lLower[i * 2 + 1]; |
| count++; |
| } |
| |
| return count; |
| } |
| |
| private static boolean rightTurn(float ax, float ay, float bx, float by, float cx, float cy) { |
| return (bx - ax) * (cy - ay) - (by - ay) * (cx - ax) > 0.00001; |
| } |
| |
| /** |
| * Calculates the intersection of poly1 with poly2 and puts in poly2 |
| * @return number of point in poly2 |
| */ |
| public static int intersection( |
| float[] poly1, int poly1length, float[] poly2, int poly2length) { |
| makeClockwise(poly1, poly1length); |
| makeClockwise(poly2, poly2length); |
| float[] poly = new float[(poly1length * poly2length + 2) * 2]; |
| int count = 0; |
| int pcount = 0; |
| for (int i = 0; i < poly1length; i++) { |
| if (pointInsidePolygon(poly1[i * 2], poly1[i * 2 + 1], poly2, poly2length)) { |
| poly[count * 2] = poly1[i * 2]; |
| poly[count * 2 + 1] = poly1[i * 2 + 1]; |
| count++; |
| pcount++; |
| } |
| } |
| int fromP1 = pcount; |
| for (int i = 0; i < poly2length; i++) { |
| if (pointInsidePolygon(poly2[i * 2], poly2[i * 2 + 1], poly1, poly1length)) { |
| poly[count * 2] = poly2[i * 2]; |
| poly[count * 2 + 1] = poly2[i * 2 + 1]; |
| count++; |
| } |
| } |
| int fromP2 = count - fromP1; |
| if (fromP1 == poly1length) { // use p1 |
| for (int i = 0; i < poly1length; i++) { |
| poly2[i * 2] = poly1[i * 2]; |
| poly2[i * 2 + 1] = poly1[i * 2 + 1]; |
| } |
| return poly1length; |
| } |
| if (fromP2 == poly2length) { // use p2 |
| return poly2length; |
| } |
| float[] intersection = new float[2]; |
| for (int i = 0; i < poly2length; i++) { |
| for (int j = 0; j < poly1length; j++) { |
| int i1_by_2 = i * 2; |
| int i2_by_2 = ((i + 1) % poly2length) * 2; |
| int j1_by_2 = j * 2; |
| int j2_by_2 = ((j + 1) % poly1length) * 2; |
| boolean found = lineIntersection( |
| poly2[i1_by_2], poly2[i1_by_2 + 1], |
| poly2[i2_by_2], poly2[i2_by_2 + 1], |
| poly1[j1_by_2], poly1[j1_by_2 + 1], |
| poly1[j2_by_2], poly1[j2_by_2 + 1], intersection); |
| if (found) { |
| poly[count * 2] = intersection[0]; |
| poly[count * 2 + 1] = intersection[1]; |
| count++; |
| } else { |
| float dx = poly2[i * 2] - poly1[j * 2]; |
| float dy = poly2[i * 2 + 1] - poly1[j * 2 + 1]; |
| |
| if (dx * dx + dy * dy < 0.01) { |
| poly[count * 2] = poly2[i * 2]; |
| poly[count * 2 + 1] = poly2[i * 2 + 1]; |
| count++; |
| } |
| } |
| } |
| } |
| if (count == 0) { |
| return 0; |
| } |
| float avgx = 0; |
| float avgy = 0; |
| for (int i = 0; i < count; i++) { |
| avgx += poly[i * 2]; |
| avgy += poly[i * 2 + 1]; |
| } |
| avgx /= count; |
| avgy /= count; |
| |
| float[] ctr = new float[] { avgx, avgy }; |
| sort(poly, count, ctr); |
| int size = count; |
| |
| poly2[0] = poly[0]; |
| poly2[1] = poly[1]; |
| |
| count = 1; |
| for (int i = 1; i < size; i++) { |
| float dx = poly[i * 2] - poly[(i - 1) * 2]; |
| float dy = poly[i * 2 + 1] - poly[(i - 1) * 2 + 1]; |
| if (dx * dx + dy * dy >= 0.01) { |
| poly2[count * 2] = poly[i * 2]; |
| poly2[count * 2 + 1] = poly[i * 2 + 1]; |
| count++; |
| } |
| } |
| return count; |
| } |
| |
| public static void sort(float[] poly, int polyLength, float[] ctr) { |
| quicksortCirc(poly, 0, polyLength - 1, ctr); |
| } |
| |
| public static float angle(float x1, float y1, float[] ctr) { |
| return -(float) Math.atan2(x1 - ctr[0], y1 - ctr[1]); |
| } |
| |
| private static void swap(float[] points, int i, int j) { |
| float x = points[i * 2]; |
| float y = points[i * 2 + 1]; |
| points[i * 2] = points[j * 2]; |
| points[i * 2 + 1] = points[j * 2 + 1]; |
| points[j * 2] = x; |
| points[j * 2 + 1] = y; |
| } |
| |
| private static void quicksortCirc(float[] points, int low, int high, float[] ctr) { |
| int i = low, j = high; |
| int p = low + (high - low) / 2; |
| float pivot = angle(points[p * 2], points[p * 2 + 1], ctr); |
| while (i <= j) { |
| while (angle(points[i * 2], points[i * 2 + 1], ctr) < pivot) { |
| i++; |
| } |
| while (angle(points[j * 2], points[j * 2 + 1], ctr) > pivot) { |
| j--; |
| } |
| |
| if (i <= j) { |
| swap(points, i, j); |
| i++; |
| j--; |
| } |
| } |
| if (low < j) { |
| quicksortCirc(points, low, j, ctr); |
| } |
| if (i < high) { |
| quicksortCirc(points, i, high, ctr); |
| } |
| } |
| |
| private static void quicksortX(float[] points, int low, int high) { |
| int i = low, j = high; |
| int p = low + (high - low) / 2; |
| float pivot = points[p * 2]; |
| while (i <= j) { |
| while (points[i * 2] < pivot) { |
| i++; |
| } |
| while (points[j * 2] > pivot) { |
| j--; |
| } |
| |
| if (i <= j) { |
| swap(points, i, j); |
| i++; |
| j--; |
| } |
| } |
| if (low < j) { |
| quicksortX(points, low, j); |
| } |
| if (i < high) { |
| quicksortX(points, i, high); |
| } |
| } |
| |
| private static boolean pointInsidePolygon(float x, float y, float[] poly, int len) { |
| boolean c = false; |
| float testx = x; |
| float testy = y; |
| for (int i = 0, j = len - 1; i < len; j = i++) { |
| if (((poly[i * 2 + 1] > testy) != (poly[j * 2 + 1] > testy)) && |
| (testx < (poly[j * 2] - poly[i * 2]) * (testy - poly[i * 2 + 1]) |
| / (poly[j * 2 + 1] - poly[i * 2 + 1]) + poly[i * 2])) { |
| c = !c; |
| } |
| } |
| return c; |
| } |
| |
| private static void makeClockwise(float[] polygon, int len) { |
| if (polygon == null || len == 0) { |
| return; |
| } |
| if (!isClockwise(polygon, len)) { |
| reverse(polygon, len); |
| } |
| } |
| |
| private static boolean isClockwise(float[] polygon, int len) { |
| float sum = 0; |
| float p1x = polygon[(len - 1) * 2]; |
| float p1y = polygon[(len - 1) * 2 + 1]; |
| for (int i = 0; i < len; i++) { |
| |
| float p2x = polygon[i * 2]; |
| float p2y = polygon[i * 2 + 1]; |
| sum += p1x * p2y - p2x * p1y; |
| p1x = p2x; |
| p1y = p2y; |
| } |
| return sum < 0; |
| } |
| |
| private static void reverse(float[] polygon, int len) { |
| int n = len / 2; |
| for (int i = 0; i < n; i++) { |
| float tmp0 = polygon[i * 2]; |
| float tmp1 = polygon[i * 2 + 1]; |
| int k = len - 1 - i; |
| polygon[i * 2] = polygon[k * 2]; |
| polygon[i * 2 + 1] = polygon[k * 2 + 1]; |
| polygon[k * 2] = tmp0; |
| polygon[k * 2 + 1] = tmp1; |
| } |
| } |
| |
| /** |
| * Intersects two lines in parametric form. |
| */ |
| private static final boolean lineIntersection( |
| float x1, float y1, |
| float x2, float y2, |
| float x3, float y3, |
| float x4, float y4, |
| float[] ret) { |
| |
| float d = (x1 - x2) * (y3 - y4) - (y1 - y2) * (x3 - x4); |
| if (d == 0.000f) { |
| return false; |
| } |
| |
| float dx = (x1 * y2 - y1 * x2); |
| float dy = (x3 * y4 - y3 * x4); |
| float x = (dx * (x3 - x4) - (x1 - x2) * dy) / d; |
| float y = (dx * (y3 - y4) - (y1 - y2) * dy) / d; |
| |
| if (((x - x1) * (x - x2) > EPSILON) |
| || ((x - x3) * (x - x4) > EPSILON) |
| || ((y - y1) * (y - y2) > EPSILON) |
| || ((y - y3) * (y - y4) > EPSILON)) { |
| |
| return false; |
| } |
| ret[0] = x; |
| ret[1] = y; |
| return true; |
| } |
| |
| /** |
| * Imagine a donut shaped image and trying to create triangles from its centroid (like |
| * cutting a pie). This function performs such action (and also edge-case triangle strips |
| * generation) then returns the resulting triangle strips. |
| * |
| * @param retstrips - the resulting triangle strips |
| */ |
| public static void donutPie2(float[] penumbra, int penumbraLength, |
| float[] umbra, int umbraLength, int rays, int layers, float strength, |
| float[] retstrips) { |
| int rings = layers + 1; |
| |
| double step = Math.PI * 2 / rays; |
| float[] retxy = new float[2]; |
| centroid2d(umbra, umbraLength, retxy); |
| float cx = retxy[0]; |
| float cy = retxy[1]; |
| |
| float[] t1 = new float[rays]; |
| float[] t2 = new float[rays]; |
| |
| for (int i = 0; i < rays; i++) { |
| float dx = (float) Math.sin(Math.PI / 4 + step * i); |
| float dy = (float) Math.cos(Math.PI / 4 + step * i); |
| t2[i] = rayIntersectPoly(umbra, umbraLength, cx, cy, dx, dy, 2)[0]; |
| t1[i] = rayIntersectPoly(penumbra, penumbraLength, cx, cy, dx, dy, 2)[0]; |
| } |
| |
| int p = 0; |
| // Calc the vertex |
| for (int r = 0; r < layers; r++) { |
| int startp = p; |
| for (int i = 0; i < rays; i++) { |
| float dx = (float) Math.sin(Math.PI / 4 + step * i); |
| float dy = (float) Math.cos(Math.PI / 4 + step * i); |
| |
| for (int j = r; j < (r + 2); j++) { |
| float jf = j / (float) (rings - 1); |
| float t = t1[i] + jf * (t2[i] - t1[i]); |
| float op = (jf + 1 - 1 / (1 + (t - t1[i]) * (t - t1[i]))) / 2; |
| |
| retstrips[p * 3] = dx * t + cx; |
| retstrips[p * 3 + 1] = dy * t + cy; |
| retstrips[p * 3 + 2] = jf * op * strength; |
| |
| p++; |
| } |
| } |
| retstrips[p * 3] = retstrips[startp * 3]; |
| retstrips[p * 3 + 1] = retstrips[startp * 3 + 1]; |
| retstrips[p * 3 + 2] = retstrips[startp * 3 + 2]; |
| p++; |
| startp++; |
| retstrips[p * 3] = retstrips[startp * 3]; |
| retstrips[p * 3 + 1] = retstrips[startp * 3 + 1]; |
| retstrips[p * 3 + 2] = retstrips[startp * 3 + 2]; |
| p++; |
| } |
| int oldp = p - 1; |
| retstrips[p * 3] = retstrips[oldp * 3]; |
| retstrips[p * 3 + 1] = retstrips[oldp * 3 + 1]; |
| retstrips[p * 3 + 2] = retstrips[oldp * 3 + 2]; |
| p+=2; |
| |
| oldp = p; |
| for (int k = 0; k < rays; k++) { |
| int i = k / 2; |
| if ((k & 1) == 1) { // traverse the inside in a zig zag pattern |
| // for strips |
| i = rays - i - 1; |
| } |
| float dx = (float) Math.sin(Math.PI / 4 + step * i); |
| float dy = (float) Math.cos(Math.PI / 4 + step * i); |
| |
| float jf = 1; |
| |
| float t = t1[i] + jf * (t2[i] - t1[i]); |
| float op = (jf + 1 - 1 / (1 + (t - t1[i]) * (t - t1[i]))) / 2; |
| |
| retstrips[p * 3] = dx * t + cx; |
| retstrips[p * 3 + 1] = dy * t + cy; |
| retstrips[p * 3 + 2] = jf * op * strength; |
| p++; |
| } |
| p = oldp - 1; |
| retstrips[p * 3] = retstrips[oldp * 3]; |
| retstrips[p * 3 + 1] = retstrips[oldp * 3 + 1]; |
| retstrips[p * 3 + 2] = retstrips[oldp * 3 + 2]; |
| } |
| |
| /** |
| * @return Rect bound of flattened (ignoring z). LTRB |
| * @param dimension - 2D or 3D |
| */ |
| public static float[] flatBound(float[] poly, int dimension) { |
| int polySize = poly.length/dimension; |
| float left = poly[0]; |
| float right = poly[0]; |
| float top = poly[1]; |
| float bottom = poly[1]; |
| |
| for (int i = 0; i < polySize; i++) { |
| float x = poly[i * dimension + 0]; |
| float y = poly[i * dimension + 1]; |
| |
| if (left > x) { |
| left = x; |
| } else if (right < x) { |
| right = x; |
| } |
| |
| if (top > y) { |
| top = y; |
| } else if (bottom < y) { |
| bottom = y; |
| } |
| } |
| return new float[]{left, top, right, bottom}; |
| } |
| |
| /** |
| * Translate the polygon to x and y |
| * @param dimension in what dimension is polygon represented (supports 2 or 3D). |
| */ |
| public static void translate(float[] poly, float translateX, float translateY, int dimension) { |
| int polySize = poly.length/dimension; |
| |
| for (int i = 0; i < polySize; i++) { |
| poly[i * dimension + 0] += translateX; |
| poly[i * dimension + 1] += translateY; |
| } |
| } |
| |
| } |
| |