// Copyright 2014 The Flutter Authors. All rights reserved.
// Use of this source code is governed by a BSD-style license that can be
// found in the LICENSE file.
import 'dart:typed_data';
import 'package:flutter/foundation.dart';
import 'package:vector_math/vector_math_64.dart';
import 'basic_types.dart';
/// Utility functions for working with matrices.
class MatrixUtils {
// This class is not meant to be instatiated or extended; this constructor
// prevents instantiation and extension.
// ignore: unused_element
MatrixUtils._();
/// Returns the given [transform] matrix as an [Offset], if the matrix is
/// nothing but a 2D translation.
///
/// Otherwise, returns null.
static Offset getAsTranslation(Matrix4 transform) {
assert(transform != null);
final Float64List values = transform.storage;
// Values are stored in column-major order.
if (values[0] == 1.0 && // col 1
values[1] == 0.0 &&
values[2] == 0.0 &&
values[3] == 0.0 &&
values[4] == 0.0 && // col 2
values[5] == 1.0 &&
values[6] == 0.0 &&
values[7] == 0.0 &&
values[8] == 0.0 && // col 3
values[9] == 0.0 &&
values[10] == 1.0 &&
values[11] == 0.0 &&
values[14] == 0.0 && // bottom of col 4 (values 12 and 13 are the x and y offsets)
values[15] == 1.0) {
return Offset(values[12], values[13]);
}
return null;
}
/// Returns the given [transform] matrix as a [double] describing a uniform
/// scale, if the matrix is nothing but a symmetric 2D scale transform.
///
/// Otherwise, returns null.
static double getAsScale(Matrix4 transform) {
assert(transform != null);
final Float64List values = transform.storage;
// Values are stored in column-major order.
if (values[1] == 0.0 && // col 1 (value 0 is the scale)
values[2] == 0.0 &&
values[3] == 0.0 &&
values[4] == 0.0 && // col 2 (value 5 is the scale)
values[6] == 0.0 &&
values[7] == 0.0 &&
values[8] == 0.0 && // col 3
values[9] == 0.0 &&
values[10] == 1.0 &&
values[11] == 0.0 &&
values[12] == 0.0 && // col 4
values[13] == 0.0 &&
values[14] == 0.0 &&
values[15] == 1.0 &&
values[0] == values[5]) { // uniform scale
return values[0];
}
return null;
}
/// Returns true if the given matrices are exactly equal, and false
/// otherwise. Null values are assumed to be the identity matrix.
static bool matrixEquals(Matrix4 a, Matrix4 b) {
if (identical(a, b))
return true;
assert(a != null || b != null);
if (a == null)
return isIdentity(b);
if (b == null)
return isIdentity(a);
assert(a != null && b != null);
return a.storage[0] == b.storage[0]
&& a.storage[1] == b.storage[1]
&& a.storage[2] == b.storage[2]
&& a.storage[3] == b.storage[3]
&& a.storage[4] == b.storage[4]
&& a.storage[5] == b.storage[5]
&& a.storage[6] == b.storage[6]
&& a.storage[7] == b.storage[7]
&& a.storage[8] == b.storage[8]
&& a.storage[9] == b.storage[9]
&& a.storage[10] == b.storage[10]
&& a.storage[11] == b.storage[11]
&& a.storage[12] == b.storage[12]
&& a.storage[13] == b.storage[13]
&& a.storage[14] == b.storage[14]
&& a.storage[15] == b.storage[15];
}
/// Whether the given matrix is the identity matrix.
static bool isIdentity(Matrix4 a) {
assert(a != null);
return a.storage[0] == 1.0 // col 1
&& a.storage[1] == 0.0
&& a.storage[2] == 0.0
&& a.storage[3] == 0.0
&& a.storage[4] == 0.0 // col 2
&& a.storage[5] == 1.0
&& a.storage[6] == 0.0
&& a.storage[7] == 0.0
&& a.storage[8] == 0.0 // col 3
&& a.storage[9] == 0.0
&& a.storage[10] == 1.0
&& a.storage[11] == 0.0
&& a.storage[12] == 0.0 // col 4
&& a.storage[13] == 0.0
&& a.storage[14] == 0.0
&& a.storage[15] == 1.0;
}
/// Applies the given matrix as a perspective transform to the given point.
///
/// This function assumes the given point has a z-coordinate of 0.0. The
/// z-coordinate of the result is ignored.
static Offset transformPoint(Matrix4 transform, Offset point) {
final Float64List storage = transform.storage;
final double x = point.dx;
final double y = point.dy;
// Directly simulate the transform of the vector (x, y, 0, 1),
// dropping the resulting Z coordinate, and normalizing only
// if needed.
final double rx = storage[0] * x + storage[4] * y + storage[12];
final double ry = storage[1] * x + storage[5] * y + storage[13];
final double rw = storage[3] * x + storage[7] * y + storage[15];
if (rw == 1.0) {
return Offset(rx, ry);
} else {
return Offset(rx / rw, ry / rw);
}
}
/// Returns a rect that bounds the result of applying the given matrix as a
/// perspective transform to the given rect.
///
/// This version of the operation is slower than the regular transformRect
/// method, but it avoids creating infinite values from large finite values
/// if it can.
static Rect _safeTransformRect(Matrix4 transform, Rect rect) {
final Float64List storage = transform.storage;
final bool isAffine = storage[3] == 0.0 &&
storage[7] == 0.0 &&
storage[15] == 1.0;
_minMax ??= Float64List(4);
_accumulate(storage, rect.left, rect.top, true, isAffine);
_accumulate(storage, rect.right, rect.top, false, isAffine);
_accumulate(storage, rect.left, rect.bottom, false, isAffine);
_accumulate(storage, rect.right, rect.bottom, false, isAffine);
return Rect.fromLTRB(_minMax[0], _minMax[1], _minMax[2], _minMax[3]);
}
static Float64List _minMax;
static void _accumulate(Float64List m, double x, double y, bool first, bool isAffine) {
final double w = isAffine ? 1.0 : 1.0 / (m[3] * x + m[7] * y + m[15]);
final double tx = (m[0] * x + m[4] * y + m[12]) * w;
final double ty = (m[1] * x + m[5] * y + m[13]) * w;
if (first) {
_minMax[0] = _minMax[2] = tx;
_minMax[1] = _minMax[3] = ty;
} else {
if (tx < _minMax[0]) {
_minMax[0] = tx;
}
if (ty < _minMax[1]) {
_minMax[1] = ty;
}
if (tx > _minMax[2]) {
_minMax[2] = tx;
}
if (ty > _minMax[3]) {
_minMax[3] = ty;
}
}
}
/// Returns a rect that bounds the result of applying the given matrix as a
/// perspective transform to the given rect.
///
/// This function assumes the given rect is in the plane with z equals 0.0.
/// The transformed rect is then projected back into the plane with z equals
/// 0.0 before computing its bounding rect.
static Rect transformRect(Matrix4 transform, Rect rect) {
final Float64List storage = transform.storage;
final double x = rect.left;
final double y = rect.top;
final double w = rect.right - x;
final double h = rect.bottom - y;
// We want to avoid turning a finite rect into an infinite one if we can.
if (!w.isFinite || !h.isFinite) {
return _safeTransformRect(transform, rect);
}
// Transforming the 4 corners of a rectangle the straightforward way
// incurs the cost of transforming 4 points using vector math which
// involves 48 multiplications and 48 adds and then normalizing
// the points using 4 inversions of the homogeneous weight factor
// and then 12 multiplies. Once we have transformed all of the points
// we then need to turn them into a bounding box using 4 min/max
// operations each on 4 values yielding 12 total comparisons.
//
// On top of all of those operations, using the vector_math package to
// do the work for us involves allocating several objects in order to
// communicate the values back and forth - 4 allocating getters to extract
// the [Offset] objects for the corners of the [Rect], 4 conversions to
// a [Vector3] to use [Matrix4.perspectiveTransform()], and then 4 new
// [Offset] objects allocated to hold those results, yielding 8 [Offset]
// and 4 [Vector3] object allocations per rectangle transformed.
//
// But the math we really need to get our answer is actually much less
// than that.
//
// First, consider that a full point transform using the vector math
// package involves expanding it out into a vector3 with a Z coordinate
// of 0.0 and then performing 3 multiplies and 3 adds per coordinate:
// ```
// xt = x*m00 + y*m10 + z*m20 + m30;
// yt = x*m01 + y*m11 + z*m21 + m31;
// zt = x*m02 + y*m12 + z*m22 + m32;
// wt = x*m03 + y*m13 + z*m23 + m33;
// ```
// Immediately we see that we can get rid of the 3rd column of multiplies
// since we know that Z=0.0. We can also get rid of the 3rd row because
// we ignore the resulting Z coordinate. Finally we can get rid of the
// last row if we don't have a perspective transform since we can verify
// that the results are 1.0 for all points. This gets us down to 16
// multiplies and 16 adds in the non-perspective case and 24 of each for
// the perspective case. (Plus the 12 comparisons to turn them back into
// a bounding box.)
//
// But we can do even better than that.
//
// Under optimal conditions of no perspective transformation,
// which is actually a very common condition, we can transform
// a rectangle in as little as 3 operations:
//
// (rx,ry) = transform of upper left corner of rectangle
// (wx,wy) = delta transform of the (w, 0) width relative vector
// (hx,hy) = delta transform of the (0, h) height relative vector
//
// A delta transform is a transform of all elements of the matrix except
// for the translation components. The translation components are added
// in at the end of each transform computation so they represent a
// constant offset for each point transformed. A delta transform of
// a horizontal or vertical vector involves a single multiplication due
// to the fact that it only has one non-zero coordinate and no addition
// of the translation component.
//
// In the absence of a perspective transform, the transformed
// rectangle will be mapped into a parallelogram with corners at:
// corner1 = (rx, ry)
// corner2 = corner1 + dTransformed width vector = (rx+wx, ry+wy)
// corner3 = corner1 + dTransformed height vector = (rx+hx, ry+hy)
// corner4 = corner1 + both dTransformed vectors = (rx+wx+hx, ry+wy+hy)
// In all, this method of transforming the rectangle requires only
// 8 multiplies and 12 additions (which we can reduce to 8 additions if
// we only need a bounding box, see below).
//
// In the presence of a perspective transform, the above conditions
// continue to hold with respect to the non-normalized coordinates so
// we can still save a lot of multiplications by computing the 4
// non-normalized coordinates using relative additions before we normalize
// them and they lose their "pseudo-parallelogram" relationships. We still
// have to do the normalization divisions and min/max all 4 points to
// get the resulting transformed bounding box, but we save a lot of
// calculations over blindly transforming all 4 coordinates independently.
// In all, we need 12 multiplies and 22 additions to construct the
// non-normalized vectors and then 8 divisions (or 4 inversions and 8
// multiplies) for normalization (plus the standard set of 12 comparisons
// for the min/max bounds operations).
//
// Back to the non-perspective case, the optimization that lets us get
// away with fewer additions if we only need a bounding box comes from
// analyzing the impact of the relative vectors on expanding the
// bounding box of the parallelogram. First, the bounding box always
// contains the transformed upper-left corner of the rectangle. Next,
// each relative vector either pushes on the left or right side of the
// bounding box and also either the top or bottom side, depending on
// whether it is positive or negative. Finally, you can consider the
// impact of each vector on the bounding box independently. If, say,
// wx and hx have the same sign, then the limiting point in the bounding
// box will be the one that involves adding both of them to the origin
// point. If they have opposite signs, then one will push one wall one
// way and the other will push the opposite wall the other way and when
// you combine both of them, the resulting "opposite corner" will
// actually be between the limits they established by pushing the walls
// away from each other, as below:
// ```
// +---------(originx,originy)--------------+
// | -----^---- |
// | ----- ---- |
// | ----- ---- |
// (+hx,+hy)< ---- |
// | ---- ---- |
// | ---- >(+wx,+wy)
// | ---- ----- |
// | ---- ----- |
// | ---- ----- |
// | v |
// +---------------(+wx+hx,+wy+hy)----------+
// ```
// In this diagram, consider that:
// ```
// wx would be a positive number
// hx would be a negative number
// wy and hy would both be positive numbers
// ```
// As a result, wx pushes out the right wall, hx pushes out the left wall,
// and both wy and hy push down the bottom wall of the bounding box. The
// wx,hx pair (of opposite signs) worked on opposite walls and the final
// opposite corner had an X coordinate between the limits they established.
// The wy,hy pair (of the same sign) both worked together to push the
// bottom wall down by their sum.
//
// This relationship allows us to simply start with the point computed by
// transforming the upper left corner of the rectangle, and then
// conditionally adding wx, wy, hx, and hy to either the left or top
// or right or bottom of the bounding box independently depending on sign.
// In that case we only need 4 comparisons and 4 additions total to
// compute the bounding box, combined with the 8 multiplications and
// 4 additions to compute the transformed point and relative vectors
// for a total of 8 multiplies, 8 adds, and 4 comparisons.
//
// An astute observer will note that we do need to do 2 subtractions at
// the top of the method to compute the width and height. Add those to
// all of the relative solutions listed above. The test for perspective
// also adds 3 compares to the affine case and up to 3 compares to the
// perspective case (depending on which test fails, the rest are omitted).
//
// The final tally:
// basic method = 60 mul + 48 add + 12 compare
// optimized perspective = 12 mul + 22 add + 15 compare + 2 sub
// optimized affine = 8 mul + 8 add + 7 compare + 2 sub
//
// Since compares are essentially subtractions and subtractions are
// the same cost as adds, we end up with:
// basic method = 60 mul + 60 add/sub/compare
// optimized perspective = 12 mul + 39 add/sub/compare
// optimized affine = 8 mul + 17 add/sub/compare
final double wx = storage[0] * w;
final double hx = storage[4] * h;
final double rx = storage[0] * x + storage[4] * y + storage[12];
final double wy = storage[1] * w;
final double hy = storage[5] * h;
final double ry = storage[1] * x + storage[5] * y + storage[13];
if (storage[3] == 0.0 && storage[7] == 0.0 && storage[15] == 1.0) {
double left = rx;
double right = rx;
if (wx < 0) {
left += wx;
} else {
right += wx;
}
if (hx < 0) {
left += hx;
} else {
right += hx;
}
double top = ry;
double bottom = ry;
if (wy < 0) {
top += wy;
} else {
bottom += wy;
}
if (hy < 0) {
top += hy;
} else {
bottom += hy;
}
return Rect.fromLTRB(left, top, right, bottom);
} else {
final double ww = storage[3] * w;
final double hw = storage[7] * h;
final double rw = storage[3] * x + storage[7] * y + storage[15];
final double ulx = rx / rw;
final double uly = ry / rw;
final double urx = (rx + wx) / (rw + ww);
final double ury = (ry + wy) / (rw + ww);
final double llx = (rx + hx) / (rw + hw);
final double lly = (ry + hy) / (rw + hw);
final double lrx = (rx + wx + hx) / (rw + ww + hw);
final double lry = (ry + wy + hy) / (rw + ww + hw);
return Rect.fromLTRB(
_min4(ulx, urx, llx, lrx),
_min4(uly, ury, lly, lry),
_max4(ulx, urx, llx, lrx),
_max4(uly, ury, lly, lry),
);
}
}
static double _min4(double a, double b, double c, double d) {
final double e = (a < b) ? a : b;
final double f = (c < d) ? c : d;
return (e < f) ? e : f;
}
static double _max4(double a, double b, double c, double d) {
final double e = (a > b) ? a : b;
final double f = (c > d) ? c : d;
return (e > f) ? e : f;
}
/// Returns a rect that bounds the result of applying the inverse of the given
/// matrix as a perspective transform to the given rect.
///
/// This function assumes the given rect is in the plane with z equals 0.0.
/// The transformed rect is then projected back into the plane with z equals
/// 0.0 before computing its bounding rect.
static Rect inverseTransformRect(Matrix4 transform, Rect rect) {
assert(rect != null);
// As exposed by `unrelated_type_equality_checks`, this assert was a no-op.
// Fixing it introduces a bunch of runtime failures; for more context see:
// https://github.com/flutter/flutter/pull/31568
// assert(transform.determinant != 0.0);
if (isIdentity(transform))
return rect;
transform = Matrix4.copy(transform)..invert();
return transformRect(transform, rect);
}
/// Create a transformation matrix which mimics the effects of tangentially
/// wrapping the plane on which this transform is applied around a cylinder
/// and then looking at the cylinder from a point outside the cylinder.
///
/// The `radius` simulates the radius of the cylinder the plane is being
/// wrapped onto. If the transformation is applied to a 0-dimensional dot
/// instead of a plane, the dot would simply translate by +/- `radius` pixels
/// along the `orientation` [Axis] when rotating from 0 to +/- 90 degrees.
///
/// A positive radius means the object is closest at 0 `angle` and a negative
/// radius means the object is closest at π `angle` or 180 degrees.
///
/// The `angle` argument is the difference in angle in radians between the
/// object and the viewing point. A positive `angle` on a positive `radius`
/// moves the object up when `orientation` is vertical and right when
/// horizontal.
///
/// The transformation is always done such that a 0 `angle` keeps the
/// transformed object at exactly the same size as before regardless of
/// `radius` and `perspective` when `radius` is positive.
///
/// The `perspective` argument is a number between 0 and 1 where 0 means
/// looking at the object from infinitely far with an infinitely narrow field
/// of view and 1 means looking at the object from infinitely close with an
/// infinitely wide field of view. Defaults to a sane but arbitrary 0.001.
///
/// The `orientation` is the direction of the rotation axis.
///
/// Because the viewing position is a point, it's never possible to see the
/// outer side of the cylinder at or past +/- π / 2 or 90 degrees and it's
/// almost always possible to end up seeing the inner side of the cylinder
/// or the back side of the transformed plane before π / 2 when perspective > 0.
static Matrix4 createCylindricalProjectionTransform({
@required double radius,
@required double angle,
double perspective = 0.001,
Axis orientation = Axis.vertical,
}) {
assert(radius != null);
assert(angle != null);
assert(perspective >= 0 && perspective <= 1.0);
assert(orientation != null);
// Pre-multiplied matrix of a projection matrix and a view matrix.
//
// Projection matrix is a simplified perspective matrix
// http://web.iitd.ac.in/~hegde/cad/lecture/L9_persproj.pdf
// in the form of
// [[1.0, 0.0, 0.0, 0.0],
// [0.0, 1.0, 0.0, 0.0],
// [0.0, 0.0, 1.0, 0.0],
// [0.0, 0.0, -perspective, 1.0]]
//
// View matrix is a simplified camera view matrix.
// Basically re-scales to keep object at original size at angle = 0 at
// any radius in the form of
// [[1.0, 0.0, 0.0, 0.0],
// [0.0, 1.0, 0.0, 0.0],
// [0.0, 0.0, 1.0, -radius],
// [0.0, 0.0, 0.0, 1.0]]
Matrix4 result = Matrix4.identity()
..setEntry(3, 2, -perspective)
..setEntry(2, 3, -radius)
..setEntry(3, 3, perspective * radius + 1.0);
// Model matrix by first translating the object from the origin of the world
// by radius in the z axis and then rotating against the world.
result = result * ((
orientation == Axis.horizontal
? Matrix4.rotationY(angle)
: Matrix4.rotationX(angle)
) * Matrix4.translationValues(0.0, 0.0, radius)) as Matrix4;
// Essentially perspective * view * model.
return result;
}
/// Returns a matrix that transforms every point to [offset].
static Matrix4 forceToPoint(Offset offset) {
return Matrix4.identity()
..setRow(0, Vector4(0, 0, 0, offset.dx))
..setRow(1, Vector4(0, 0, 0, offset.dy));
}
}
/// Returns a list of strings representing the given transform in a format
/// useful for [TransformProperty].
///
/// If the argument is null, returns a list with the single string "null".
List<String> debugDescribeTransform(Matrix4 transform) {
if (transform == null)
return const <String>['null'];
return <String>[
'[0] ${debugFormatDouble(transform.entry(0, 0))},${debugFormatDouble(transform.entry(0, 1))},${debugFormatDouble(transform.entry(0, 2))},${debugFormatDouble(transform.entry(0, 3))}',
'[1] ${debugFormatDouble(transform.entry(1, 0))},${debugFormatDouble(transform.entry(1, 1))},${debugFormatDouble(transform.entry(1, 2))},${debugFormatDouble(transform.entry(1, 3))}',
'[2] ${debugFormatDouble(transform.entry(2, 0))},${debugFormatDouble(transform.entry(2, 1))},${debugFormatDouble(transform.entry(2, 2))},${debugFormatDouble(transform.entry(2, 3))}',
'[3] ${debugFormatDouble(transform.entry(3, 0))},${debugFormatDouble(transform.entry(3, 1))},${debugFormatDouble(transform.entry(3, 2))},${debugFormatDouble(transform.entry(3, 3))}',
];
}
/// Property which handles [Matrix4] that represent transforms.
class TransformProperty extends DiagnosticsProperty<Matrix4> {
/// Create a diagnostics property for [Matrix4] objects.
///
/// The [showName] and [level] arguments must not be null.
TransformProperty(
String name,
Matrix4 value, {
bool showName = true,
Object defaultValue = kNoDefaultValue,
DiagnosticLevel level = DiagnosticLevel.info,
}) : assert(showName != null),
assert(level != null),
super(
name,
value,
showName: showName,
defaultValue: defaultValue,
level: level,
);
@override
String valueToString({ TextTreeConfiguration parentConfiguration }) {
if (parentConfiguration != null && !parentConfiguration.lineBreakProperties) {
// Format the value on a single line to be compatible with the parent's
// style.
final List<String> values = <String>[
'${debugFormatDouble(value.entry(0, 0))},${debugFormatDouble(value.entry(0, 1))},${debugFormatDouble(value.entry(0, 2))},${debugFormatDouble(value.entry(0, 3))}',
'${debugFormatDouble(value.entry(1, 0))},${debugFormatDouble(value.entry(1, 1))},${debugFormatDouble(value.entry(1, 2))},${debugFormatDouble(value.entry(1, 3))}',
'${debugFormatDouble(value.entry(2, 0))},${debugFormatDouble(value.entry(2, 1))},${debugFormatDouble(value.entry(2, 2))},${debugFormatDouble(value.entry(2, 3))}',
'${debugFormatDouble(value.entry(3, 0))},${debugFormatDouble(value.entry(3, 1))},${debugFormatDouble(value.entry(3, 2))},${debugFormatDouble(value.entry(3, 3))}',
];
return '[${values.join('; ')}]';
}
return debugDescribeTransform(value).join('\n');
}
}