/*
* Copyright 2022 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 androidx.media3.effect;
import static androidx.media3.common.util.Assertions.checkArgument;
import android.opengl.Matrix;
import androidx.media3.common.util.Size;
import com.google.common.collect.ImmutableList;
import java.util.Arrays;
import java.util.List;
/** Utility functions for working with matrices, vertices, and polygons. */
/* package */ final class MatrixUtils {
/**
* Contains the normal vectors of the clipping planes in homogeneous coordinates which
* conveniently also double as origin vectors and parameters of the normal form of the planes ax +
* by + cz = d.
*/
private static final float[][] NDC_CUBE =
new float[][] {
new float[] {1, 0, 0, 1},
new float[] {-1, 0, 0, 1},
new float[] {0, 1, 0, 1},
new float[] {0, -1, 0, 1},
new float[] {0, 0, 1, 1},
new float[] {0, 0, -1, 1}
};
/**
* Returns a 4x4, column-major {@link Matrix} float array, from an input {@link
* android.graphics.Matrix}.
*
* <p>This is useful for converting to the 4x4 column-major format commonly used in OpenGL.
*/
public static float[] getGlMatrixArray(android.graphics.Matrix matrix) {
float[] matrix3x3Array = new float[9];
matrix.getValues(matrix3x3Array);
float[] matrix4x4Array = getMatrix4x4Array(matrix3x3Array);
// Transpose from row-major to column-major representations.
float[] transposedMatrix4x4Array = new float[16];
Matrix.transposeM(
transposedMatrix4x4Array, /* mTransOffset= */ 0, matrix4x4Array, /* mOffset= */ 0);
return transposedMatrix4x4Array;
}
/**
* Returns a 4x4 matrix array containing the 3x3 matrix array's contents.
*
* <p>The 3x3 matrix array is expected to be in 2 dimensions, and the 4x4 matrix array is expected
* to be in 3 dimensions. The output will have the third row/column's values be an identity
* matrix's values, so that vertex transformations using this matrix will not affect the z axis.
* <br>
* Input format: [a, b, c, d, e, f, g, h, i] <br>
* Output format: [a, b, 0, c, d, e, 0, f, 0, 0, 1, 0, g, h, 0, i]
*/
private static float[] getMatrix4x4Array(float[] matrix3x3Array) {
float[] matrix4x4Array = new float[16];
matrix4x4Array[10] = 1;
for (int inputRow = 0; inputRow < 3; inputRow++) {
for (int inputColumn = 0; inputColumn < 3; inputColumn++) {
int outputRow = (inputRow == 2) ? 3 : inputRow;
int outputColumn = (inputColumn == 2) ? 3 : inputColumn;
matrix4x4Array[outputRow * 4 + outputColumn] = matrix3x3Array[inputRow * 3 + inputColumn];
}
}
return matrix4x4Array;
}
/**
* Clips a convex polygon to normalized device coordinates (-1 to 1 on x, y, and z axes).
*
* <p>The input and output vertices are given in homogeneous coordinates (x,y,z,1) where the last
* element must always be 1. To convert a general vector in homogeneous coordinates (xw,yw,zw,w)
* to this form, simply divide all elements by w.
*
* @param polygonVertices The vertices in counter-clockwise order as 4 element vectors of
* homogeneous coordinates.
* @return The vertices of the clipped polygon, in counter-clockwise order, or an empty list if
* the polygon doesn't intersect with the NDC range.
*/
public static ImmutableList<float[]> clipConvexPolygonToNdcRange(
ImmutableList<float[]> polygonVertices) {
checkArgument(polygonVertices.size() >= 3, "A polygon must have at least 3 vertices.");
// This is a 3D generalization of the Sutherland-Hodgman algorithm
// https://en.wikipedia.org/wiki/Sutherland%E2%80%93Hodgman_algorithm
// using a convex clipping volume (the NDC cube) instead of a convex clipping polygon to clip a
// given subject polygon.
// For this algorithm, the subject polygon doesn't necessarily need to be convex. But since we
// require that it is convex, we can assume that the clipped result is a single connected
// convex polygon.
ImmutableList.Builder<float[]> outputVertices =
new ImmutableList.Builder<float[]>().addAll(polygonVertices);
for (float[] clippingPlane : NDC_CUBE) {
ImmutableList<float[]> inputVertices = outputVertices.build();
outputVertices = new ImmutableList.Builder<>();
for (int i = 0; i < inputVertices.size(); i++) {
float[] currentVertex = inputVertices.get(i);
float[] previousVertex =
inputVertices.get((inputVertices.size() + i - 1) % inputVertices.size());
if (isInsideClippingHalfSpace(currentVertex, clippingPlane)) {
if (!isInsideClippingHalfSpace(previousVertex, clippingPlane)) {
float[] intersectionPoint =
computeIntersectionPoint(
clippingPlane, clippingPlane, previousVertex, currentVertex);
if (!Arrays.equals(currentVertex, intersectionPoint)) {
outputVertices.add(intersectionPoint);
}
}
outputVertices.add(currentVertex);
} else if (isInsideClippingHalfSpace(previousVertex, clippingPlane)) {
float[] intersection =
computeIntersectionPoint(clippingPlane, clippingPlane, previousVertex, currentVertex);
if (!Arrays.equals(previousVertex, intersection)) {
outputVertices.add(intersection);
}
}
}
}
return outputVertices.build();
}
/**
* Returns whether the given point is inside the half-space bounded by the clipping plane and
* facing away from its normal vector.
*
* <p>The clipping plane has the form ax + by + cz = d.
*
* @param point A point in homogeneous coordinates (x,y,z,1).
* @param clippingPlane The parameters (a,b,c,d) of the plane's normal form.
* @return Whether the point is on the inside of the plane.
*/
private static boolean isInsideClippingHalfSpace(float[] point, float[] clippingPlane) {
checkArgument(clippingPlane.length == 4, "Expecting 4 plane parameters");
return clippingPlane[0] * point[0] + clippingPlane[1] * point[1] + clippingPlane[2] * point[2]
<= clippingPlane[3];
}
/**
* Returns the intersection point of the given line and plane.
*
* <p>This method may only be called if such an intersection exists.
*
* <p>The plane has the form ax + by + cz = d.
*
* <p>The points are given in homogeneous coordinates (x,y,z,1).
*
* @param planePoint A point on the plane.
* @param planeParameters The parameters of the plane's normal form.
* @param linePoint1 A point on the line.
* @param linePoint2 Another point on the line.
* @return The point of intersection.
*/
private static float[] computeIntersectionPoint(
float[] planePoint, float[] planeParameters, float[] linePoint1, float[] linePoint2) {
checkArgument(planeParameters.length == 4, "Expecting 4 plane parameters");
// See https://en.wikipedia.org/wiki/Line%E2%80%93plane_intersection#Algebraic_form for the
// derivation of this solution formula.
float lineEquationParameter =
((planePoint[0] - linePoint1[0]) * planeParameters[0]
+ (planePoint[1] - linePoint1[1]) * planeParameters[1]
+ (planePoint[2] - linePoint1[2]) * planeParameters[2])
/ ((linePoint2[0] - linePoint1[0]) * planeParameters[0]
+ (linePoint2[1] - linePoint1[1]) * planeParameters[1]
+ (linePoint2[2] - linePoint1[2]) * planeParameters[2]);
float x = linePoint1[0] + (linePoint2[0] - linePoint1[0]) * lineEquationParameter;
float y = linePoint1[1] + (linePoint2[1] - linePoint1[1]) * lineEquationParameter;
float z = linePoint1[2] + (linePoint2[2] - linePoint1[2]) * lineEquationParameter;
return new float[] {x, y, z, 1};
}
/**
* Applies a transformation matrix to each point.
*
* @param transformationMatrix The 4x4 transformation matrix.
* @param points The points as 4 element vectors of homogeneous coordinates (x,y,z,1).
* @return The transformed points as 4 element vectors of homogeneous coordinates (x,y,z,1).
*/
public static ImmutableList<float[]> transformPoints(
float[] transformationMatrix, ImmutableList<float[]> points) {
ImmutableList.Builder<float[]> transformedPoints = new ImmutableList.Builder<>();
for (int i = 0; i < points.size(); i++) {
float[] transformedPoint = new float[4];
Matrix.multiplyMV(
transformedPoint,
/* resultVecOffset= */ 0,
transformationMatrix,
/* lhsMatOffset= */ 0,
points.get(i),
/* rhsVecOffset= */ 0);
// Multiplication result is in homogeneous coordinates (xw,yw,zw,w) with any w. Divide by w
// to get (x,y,z,1).
transformedPoint[0] /= transformedPoint[3];
transformedPoint[1] /= transformedPoint[3];
transformedPoint[2] /= transformedPoint[3];
transformedPoint[3] = 1;
transformedPoints.add(transformedPoint);
}
return transformedPoints.build();
}
/**
* Returns the output frame size after applying the given list of {@link GlMatrixTransformation
* GlMatrixTransformations} to an input frame with the given size.
*/
public static Size configureAndGetOutputSize(
int inputWidth, int inputHeight, List<GlMatrixTransformation> matrixTransformations) {
checkArgument(inputWidth > 0, "inputWidth must be positive");
checkArgument(inputHeight > 0, "inputHeight must be positive");
Size outputSize = new Size(inputWidth, inputHeight);
for (int i = 0; i < matrixTransformations.size(); i++) {
outputSize =
matrixTransformations.get(i).configure(outputSize.getWidth(), outputSize.getHeight());
}
return outputSize;
}
/** Class only contains static methods. */
private MatrixUtils() {}
}