MatrixUtils.java

/*
 * 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 android.util.Pair;
import com.google.common.collect.ImmutableList;
import java.util.Arrays;

/** 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 Pair<Integer, Integer> configureAndGetOutputSize(
      int inputWidth,
      int inputHeight,
      ImmutableList<GlMatrixTransformation> matrixTransformations) {
    checkArgument(inputWidth > 0, "inputWidth must be positive");
    checkArgument(inputHeight > 0, "inputHeight must be positive");

    Pair<Integer, Integer> outputSize = Pair.create(inputWidth, inputHeight);
    for (int i = 0; i < matrixTransformations.size(); i++) {
      outputSize = matrixTransformations.get(i).configure(outputSize.first, outputSize.second);
    }

    return outputSize;
  }

  /** Class only contains static methods. */
  private MatrixUtils() {}
}