Skip to content

Commit 9946f7c

Browse files
flarflar
authored
Optimize the transformRect and transformPoint methods in matrix_utils. (flutter#36396)
Primarily these methods no longer allocate any objects other than their return values. Additionally, the math in the methods is reduced compared to the general case math based on known input conditions.
1 parent d708d9d commit 9946f7c

File tree

2 files changed

+306
-16
lines changed

2 files changed

+306
-16
lines changed

‎packages/flutter/lib/src/painting/matrix_utils.dart‎

Lines changed: 232 additions & 16 deletions
Original file line numberDiff line numberDiff line change
@@ -2,7 +2,6 @@
22
// Use of this source code is governed by a BSD-style license that can be
33
// found in the LICENSE file.
44

5-
import 'dart:math' as math;
65
import 'dart:typed_data';
76

87
import 'package:flutter/foundation.dart';
@@ -124,9 +123,22 @@ class MatrixUtils {
124123
/// This function assumes the given point has a z-coordinate of 0.0. The
125124
/// z-coordinate of the result is ignored.
126125
static Offset transformPoint(Matrix4 transform, Offset point) {
127-
final Vector3 position3 = Vector3(point.dx, point.dy, 0.0);
128-
final Vector3 transformed3 = transform.perspectiveTransform(position3);
129-
return Offset(transformed3.x, transformed3.y);
126+
final Float64List storage = transform.storage;
127+
final double x = point.dx;
128+
final double y = point.dy;
129+
130+
// Directly simulate the transform of the vector (x, y, 0, 1),
131+
// dropping the resulting Z coordinate, and normalizing only
132+
// if needed.
133+
134+
final double rx = storage[0] * x + storage[4] * y + storage[12];
135+
final double ry = storage[1] * x + storage[5] * y + storage[13];
136+
final double rw = storage[3] * x + storage[7] * y + storage[15];
137+
if (rw == 1.0) {
138+
return Offset(rx, ry);
139+
} else {
140+
return Offset(rx / rw, ry / rw);
141+
}
130142
}
131143

132144
/// Returns a rect that bounds the result of applying the given matrix as a
@@ -136,23 +148,227 @@ class MatrixUtils {
136148
/// The transformed rect is then projected back into the plane with z equals
137149
/// 0.0 before computing its bounding rect.
138150
static Rect transformRect(Matrix4 transform, Rect rect) {
139-
final Offset point1 = transformPoint(transform, rect.topLeft);
140-
final Offset point2 = transformPoint(transform, rect.topRight);
141-
final Offset point3 = transformPoint(transform, rect.bottomLeft);
142-
final Offset point4 = transformPoint(transform, rect.bottomRight);
143-
return Rect.fromLTRB(
144-
_min4(point1.dx, point2.dx, point3.dx, point4.dx),
145-
_min4(point1.dy, point2.dy, point3.dy, point4.dy),
146-
_max4(point1.dx, point2.dx, point3.dx, point4.dx),
147-
_max4(point1.dy, point2.dy, point3.dy, point4.dy),
148-
);
151+
final Float64List storage = transform.storage;
152+
final double x = rect.left;
153+
final double y = rect.top;
154+
final double w = rect.right - x;
155+
final double h = rect.bottom - y;
156+
157+
// Transforming the 4 corners of a rectangle the straightforward way
158+
// incurs the cost of transforming 4 points using vector math which
159+
// involves 48 multiplications and 48 adds and then normalizing
160+
// the points using 4 inversions of the homogeneous weight factor
161+
// and then 12 multiplies. Once we have transformed all of the points
162+
// we then need to turn them into a bounding box using 4 min/max
163+
// operations each on 4 values yielding 12 total comparisons.
164+
//
165+
// On top of all of those operations, using the vector_math package to
166+
// do the work for us involves allocating several objects in order to
167+
// communicate the values back and forth - 4 allocating getters to extract
168+
// the [Offset] objects for the corners of the [Rect], 4 conversions to
169+
// a [Vector3] to use [Matrix4.perspectiveTransform()], and then 4 new
170+
// [Offset] objects allocated to hold those results, yielding 8 [Offset]
171+
// and 4 [Vector3] object allocations per rectangle transformed.
172+
//
173+
// But the math we really need to get our answer is actually much less
174+
// than that.
175+
//
176+
// First, consider that a full point transform using the vector math
177+
// package involves expanding it out into a vector3 with a Z coordinate
178+
// of 0.0 and then performing 3 multiplies and 3 adds per coordinate:
179+
// ```
180+
// xt = x*m00 + y*m10 + z*m20 + m30;
181+
// yt = x*m01 + y*m11 + z*m21 + m31;
182+
// zt = x*m02 + y*m12 + z*m22 + m32;
183+
// wt = x*m03 + y*m13 + z*m23 + m33;
184+
// ```
185+
// Immediately we see that we can get rid of the 3rd column of multiplies
186+
// since we know that Z=0.0. We can also get rid of the 3rd row because
187+
// we ignore the resulting Z coordinate. Finally we can get rid of the
188+
// last row if we don't have a perspective transform since we can verify
189+
// that the results are 1.0 for all points. This gets us down to 16
190+
// multiplies and 16 adds in the non-perspective case and 24 of each for
191+
// the perspective case. (Plus the 12 comparisons to turn them back into
192+
// a bounding box.)
193+
//
194+
// But we can do even better than that.
195+
//
196+
// Under optimal conditions of no perspective transformation,
197+
// which is actually a very common condition, we can transform
198+
// a rectangle in as little as 3 operations:
199+
//
200+
// (rx,ry) = transform of upper left corner of rectangle
201+
// (wx,wy) = delta transform of the (w, 0) width relative vector
202+
// (hx,hy) = delta transform of the (0, h) height relative vector
203+
//
204+
// A delta transform is a transform of all elements of the matrix except
205+
// for the translation components. The translation components are added
206+
// in at the end of each transform computation so they represent a
207+
// constant offset for each point transformed. A delta transform of
208+
// a horizontal or vertical vector involves a single multiplication due
209+
// to the fact that it only has one non-zero coordinate and no addition
210+
// of the translation component.
211+
//
212+
// In the absence of a perspective transform, the transformed
213+
// rectangle will be mapped into a parallelogram with corners at:
214+
// corner1 = (rx, ry)
215+
// corner2 = corner1 + dTransformed width vector = (rx+wx, ry+wy)
216+
// corner3 = corner1 + dTransformed height vector = (rx+hx, ry+hy)
217+
// corner4 = corner1 + both dTransformed vectors = (rx+wx+hx, ry+wy+hy)
218+
// In all, this method of transforming the rectangle requires only
219+
// 8 multiplies and 12 additions (which we can reduce to 8 additions if
220+
// we only need a bounding box, see below).
221+
//
222+
// In the presence of a perspective transform, the above conditions
223+
// continue to hold with respect to the non-normalized coordinates so
224+
// we can still save a lot of multiplications by computing the 4
225+
// non-normalized coordinates using relative additions before we normalize
226+
// them and they lose their "pseudo-parallelogram" relationships. We still
227+
// have to do the normalization divisions and min/max all 4 points to
228+
// get the resulting transformed bounding box, but we save a lot of
229+
// calculations over blindly transforming all 4 coordinates independently.
230+
// In all, we need 12 multiplies and 22 additions to construct the
231+
// non-normalized vectors and then 8 divisions (or 4 inversions and 8
232+
// multiplies) for normalization (plus the standard set of 12 comparisons
233+
// for the min/max bounds operations).
234+
//
235+
// Back to the non-perspective case, the optimization that lets us get
236+
// away with fewer additions if we only need a bounding box comes from
237+
// analyzing the impact of the relative vectors on expanding the
238+
// bounding box of the parallelogram. First, the bounding box always
239+
// contains the transformed upper-left corner of the rectangle. Next,
240+
// each relative vector either pushes on the left or right side of the
241+
// bounding box and also either the top or bottom side, depending on
242+
// whether it is positive or negative. Finally, you can consider the
243+
// impact of each vector on the bounding box independently. If, say,
244+
// wx and hx have the same sign, then the limiting point in the bounding
245+
// box will be the one that involves adding both of them to the origin
246+
// point. If they have opposite signs, then one will push one wall one
247+
// way and the other will push the opposite wall the other way and when
248+
// you combine both of them, the resulting "opposite corner" will
249+
// actually be between the limits they established by pushing the walls
250+
// away from each other, as below:
251+
// ```
252+
// +---------(originx,originy)--------------+
253+
// | -----^---- |
254+
// | ----- ---- |
255+
// | ----- ---- |
256+
// (+hx,+hy)< ---- |
257+
// | ---- ---- |
258+
// | ---- >(+wx,+wy)
259+
// | ---- ----- |
260+
// | ---- ----- |
261+
// | ---- ----- |
262+
// | v |
263+
// +---------------(+wx+hx,+wy+hy)----------+
264+
// ```
265+
// In this diagram, consider that:
266+
// ```
267+
// wx would be a positive number
268+
// hx would be a negative number
269+
// wy and hy would both be positive numbers
270+
// ```
271+
// As a result, wx pushes out the right wall, hx pushes out the left wall,
272+
// and both wy and hy push down the bottom wall of the bounding box. The
273+
// wx,hx pair (of opposite signs) worked on opposite walls and the final
274+
// opposite corner had an X coordinate between the limits they established.
275+
// The wy,hy pair (of the same sign) both worked together to push the
276+
// bottom wall down by their sum.
277+
//
278+
// This relationship allows us to simply start with the point computed by
279+
// transforming the upper left corner of the rectangle, and then
280+
// conditionally adding wx, wy, hx, and hy to either the left or top
281+
// or right or bottom of the bounding box independently depending on sign.
282+
// In that case we only need 4 comparisons and 4 additions total to
283+
// compute the bounding box, combined with the 8 multiplications and
284+
// 4 additions to compute the transformed point and relative vectors
285+
// for a total of 8 multiplies, 8 adds, and 4 comparisons.
286+
//
287+
// An astute observer will note that we do need to do 2 subtractions at
288+
// the top of the method to compute the width and height. Add those to
289+
// all of the relative solutions listed above. The test for perspective
290+
// also adds 3 compares to the affine case and up to 3 compares to the
291+
// perspective case (depending on which test fails, the rest are omitted).
292+
//
293+
// The final tally:
294+
// basic method = 60 mul + 48 add + 12 compare
295+
// optimized perspective = 12 mul + 22 add + 15 compare + 2 sub
296+
// optimized affine = 8 mul + 8 add + 7 compare + 2 sub
297+
//
298+
// Since compares are essentially subtractions and subtractions are
299+
// the same cost as adds, we end up with:
300+
// basic method = 60 mul + 60 add/sub/compare
301+
// optimized perspective = 12 mul + 39 add/sub/compare
302+
// optimized affine = 8 mul + 17 add/sub/compare
303+
304+
final double wx = storage[0] * w;
305+
final double hx = storage[4] * h;
306+
final double rx = storage[0] * x + storage[4] * y + storage[12];
307+
308+
final double wy = storage[1] * w;
309+
final double hy = storage[5] * h;
310+
final double ry = storage[1] * x + storage[5] * y + storage[13];
311+
312+
if (storage[3] == 0.0 && storage[7] == 0.0 && storage[15] == 1.0) {
313+
double left = rx;
314+
double right = rx;
315+
if (wx < 0) {
316+
left += wx;
317+
} else {
318+
right += wx;
319+
}
320+
if (hx < 0) {
321+
left += hx;
322+
} else {
323+
right += hx;
324+
}
325+
326+
double top = ry;
327+
double bottom = ry;
328+
if (wy < 0) {
329+
top += wy;
330+
} else {
331+
bottom += wy;
332+
}
333+
if (hy < 0) {
334+
top += hy;
335+
} else {
336+
bottom += hy;
337+
}
338+
339+
return Rect.fromLTRB(left, top, right, bottom);
340+
} else {
341+
final double ww = storage[3] * w;
342+
final double hw = storage[7] * h;
343+
final double rw = storage[3] * x + storage[7] * y + storage[15];
344+
345+
final double ulx = rx / rw;
346+
final double uly = ry / rw;
347+
final double urx = (rx + wx) / (rw + ww);
348+
final double ury = (ry + wy) / (rw + ww);
349+
final double llx = (rx + hx) / (rw + hw);
350+
final double lly = (ry + hy) / (rw + hw);
351+
final double lrx = (rx + wx + hx) / (rw + ww + hw);
352+
final double lry = (ry + wy + hy) / (rw + ww + hw);
353+
354+
return Rect.fromLTRB(
355+
_min4(ulx, urx, llx, lrx),
356+
_min4(uly, ury, lly, lry),
357+
_max4(ulx, urx, llx, lrx),
358+
_max4(uly, ury, lly, lry),
359+
);
360+
}
149361
}
150362

151363
static double _min4(double a, double b, double c, double d) {
152-
return math.min(a, math.min(b, math.min(c, d)));
364+
final double e = (a < b) ? a : b;
365+
final double f = (c < d) ? c : d;
366+
return (e < f) ? e : f;
153367
}
154368
static double _max4(double a, double b, double c, double d) {
155-
return math.max(a, math.max(b, math.max(c, d)));
369+
final double e = (a > b) ? a : b;
370+
final double f = (c > d) ? c : d;
371+
return (e > f) ? e : f;
156372
}
157373

158374
/// Returns a rect that bounds the result of applying the inverse of the given

‎packages/flutter/test/painting/matrix_utils_test.dart‎

Lines changed: 74 additions & 0 deletions
Original file line numberDiff line numberDiff line change
@@ -121,4 +121,78 @@ void main() {
121121
forcedOffset,
122122
);
123123
});
124+
125+
test('transformRect with no perspective (w = 1)', () {
126+
const Rect rectangle20x20 = Rect.fromLTRB(10, 20, 30, 40);
127+
128+
// Identity
129+
expect(
130+
MatrixUtils.transformRect(Matrix4.identity(), rectangle20x20),
131+
rectangle20x20,
132+
);
133+
134+
// 2D Scaling
135+
expect(
136+
MatrixUtils.transformRect(Matrix4.diagonal3Values(2, 2, 2), rectangle20x20),
137+
const Rect.fromLTRB(20, 40, 60, 80),
138+
);
139+
140+
// Rotation
141+
expect(
142+
MatrixUtils.transformRect(Matrix4.rotationZ(pi / 2.0), rectangle20x20),
143+
within<Rect>(distance: 0.00001, from: const Rect.fromLTRB(-40.0, 10.0, -20.0, 30.0)),
144+
);
145+
});
146+
147+
test('transformRect with perspective (w != 1)', () {
148+
final Matrix4 transform = MatrixUtils.createCylindricalProjectionTransform(
149+
radius: 10.0,
150+
angle: pi / 8.0,
151+
perspective: 0.3,
152+
);
153+
154+
for (int i = 1; i < 10000; i++) {
155+
final Rect rect = Rect.fromLTRB(11.0 * i, 12.0 * i, 15.0 * i, 18.0 * i);
156+
final Rect golden = _vectorWiseTransformRect(transform, rect);
157+
expect(
158+
MatrixUtils.transformRect(transform, rect),
159+
within<Rect>(distance: 0.00001, from: golden),
160+
);
161+
}
162+
});
163+
}
164+
165+
// Produces the same computation as `MatrixUtils.transformPoint` but it uses
166+
// the built-in perspective transform methods in the Matrix4 class as a
167+
// golden implementation of the optimized `MatrixUtils.transformPoint`
168+
// to make sure optimizations do not contain bugs.
169+
Offset _transformPoint(Matrix4 transform, Offset point) {
170+
final Vector3 position3 = Vector3(point.dx, point.dy, 0.0);
171+
final Vector3 transformed3 = transform.perspectiveTransform(position3);
172+
return Offset(transformed3.x, transformed3.y);
173+
}
174+
175+
// Produces the same computation as `MatrixUtils.transformRect` but it does this
176+
// one point at a time. This function is used as the golden implementation of the
177+
// optimized `MatrixUtils.transformRect` to make sure optimizations do not contain
178+
// bugs.
179+
Rect _vectorWiseTransformRect(Matrix4 transform, Rect rect) {
180+
final Offset point1 = _transformPoint(transform, rect.topLeft);
181+
final Offset point2 = _transformPoint(transform, rect.topRight);
182+
final Offset point3 = _transformPoint(transform, rect.bottomLeft);
183+
final Offset point4 = _transformPoint(transform, rect.bottomRight);
184+
return Rect.fromLTRB(
185+
_min4(point1.dx, point2.dx, point3.dx, point4.dx),
186+
_min4(point1.dy, point2.dy, point3.dy, point4.dy),
187+
_max4(point1.dx, point2.dx, point3.dx, point4.dx),
188+
_max4(point1.dy, point2.dy, point3.dy, point4.dy),
189+
);
190+
}
191+
192+
double _min4(double a, double b, double c, double d) {
193+
return min(a, min(b, min(c, d)));
194+
}
195+
196+
double _max4(double a, double b, double c, double d) {
197+
return max(a, max(b, max(c, d)));
124198
}

0 commit comments

Comments
 (0)