1 /*
2 * Copyright 2021 Google LLC
3 *
4 * Use of this source code is governed by a BSD-style license that can be
5 * found in the LICENSE file.
6 */
7 #include "src/gpu/graphite/geom/Transform_graphite.h"
8
9 #include "include/core/SkM44.h"
10 #include "include/core/SkScalar.h"
11 #include "include/private/base/SkAssert.h"
12 #include "include/private/base/SkFloatingPoint.h"
13 #include "src/base/SkVx.h"
14 #include "src/core/SkMatrixInvert.h"
15 #include "src/core/SkMatrixPriv.h"
16 #include "src/gpu/graphite/geom/Rect.h"
17
18 #include <algorithm>
19 #include <cmath>
20 #include <tuple>
21 #include <utility>
22
23 namespace skgpu::graphite {
24
25 namespace {
26
scale_translate_rect(skvx::float4 rectVals,float sx,float sy,float tx,float ty)27 skvx::float4 scale_translate_rect(skvx::float4 rectVals, float sx, float sy, float tx, float ty) {
28 // The (-tx,-ty) terms preserve the calculated values in (l,t,-r,-b) form so that the return
29 // value can be passed directly into FromVals() to avoid extra negation operations in ltrb().
30 return rectVals * skvx::float4{sx,sy,sx,sy} + skvx::float4{tx,ty,-tx,-ty};
31 }
32
map_rect(Transform::Type type,const SkM44 & m,const Rect & r)33 Rect map_rect(Transform::Type type, const SkM44& m, const Rect& r) {
34 switch (type) {
35 case Transform::Type::kIdentity:
36 return r;
37 case Transform::Type::kSimpleRectStaysRect:
38 // Since scale factors are positive, the returned rectangle is already sorted
39 return Rect::FromVals(
40 scale_translate_rect(r.vals(), m.rc(0,0), m.rc(1,1), m.rc(0,3), m.rc(1,3)));
41 case Transform::Type::kRectStaysRect: {
42 // Which is not the case for general rect-stays-rect transforms
43 skvx::float4 xformed = r.vals();
44 if (m.rc(0,0) == 0.f) {
45 // Anti-diagonal matrix (90/270 rotation), so scale L+R by m10 and T+B by m01 and
46 // then swizzle so that the transformed values swap X and Y components and then sort
47 xformed = skvx::shuffle<1,0,3,2>(
48 scale_translate_rect(xformed, m.rc(1,0), m.rc(0,1), m.rc(1,3), m.rc(0,3)));
49 } else {
50 // Mirror or 180 rotation, so X and/or Y edges may be flipped so just sort after.
51 xformed = scale_translate_rect(xformed, m.rc(0,0), m.rc(1,1), m.rc(0,3), m.rc(1,3));
52 }
53 return Rect::FromVals(xformed).sort();
54 }
55 case Transform::Type::kAffine:
56 [[fallthrough]];
57 case Transform::Type::kPerspective:
58 return SkMatrixPriv::MapRect(m, r.asSkRect());
59 case Transform::Type::kInvalid:
60 return Rect::InfiniteInverted();
61 }
62 SkUNREACHABLE;
63 }
64
map_points(const SkM44 & m,const SkV4 * in,SkV4 * out,int count)65 void map_points(const SkM44& m, const SkV4* in, SkV4* out, int count) {
66 // TODO: These maybe should go into SkM44, since bulk point mapping seems generally useful
67 auto c0 = skvx::float4::Load(SkMatrixPriv::M44ColMajor(m) + 0);
68 auto c1 = skvx::float4::Load(SkMatrixPriv::M44ColMajor(m) + 4);
69 auto c2 = skvx::float4::Load(SkMatrixPriv::M44ColMajor(m) + 8);
70 auto c3 = skvx::float4::Load(SkMatrixPriv::M44ColMajor(m) + 12);
71
72 for (int i = 0; i < count; ++i) {
73 auto p = (c0 * in[i].x) + (c1 * in[i].y) + (c2 * in[i].z) + (c3 * in[i].w);
74 p.store(out + i);
75 }
76 }
77
78 // Returns singular value decomposition of the 2x2 matrix [m00 m01] as {min, max}
79 // [m10 m11]
compute_svd(float m00,float m01,float m10,float m11)80 std::pair<float, float> compute_svd(float m00, float m01, float m10, float m11) {
81 // no-persp, these are the singular values of [m00,m01][m10,m11], which is just the upper 2x2
82 // and equivalent to SkMatrix::getMinmaxScales().
83 float s1 = m00*m00 + m01*m01 + m10*m10 + m11*m11;
84
85 float e = m00*m00 + m01*m01 - m10*m10 - m11*m11;
86 float f = m00*m10 + m01*m11;
87 float s2 = SkScalarSqrt(e*e + 4*f*f);
88
89 // s2 >= 0, so (s1 - s2) <= (s1 + s2) so this always returns {min, max}.
90 return {SkScalarSqrt(0.5f * (s1 - s2)),
91 SkScalarSqrt(0.5f * (s1 + s2))};
92 }
93
sort_scale(float sx,float sy)94 std::pair<float, float> sort_scale(float sx, float sy) {
95 float min = std::abs(sx);
96 float max = std::abs(sy);
97 if (min > max) {
98 return {max, min};
99 } else {
100 return {min, max};
101 }
102 }
103
104 } // anonymous namespace
105
Transform(const SkM44 & m)106 Transform::Transform(const SkM44& m) : fM(m) {
107 static constexpr SkV4 kNoPerspective = {0.f, 0.f, 0.f, 1.f};
108 static constexpr SkV4 kNoZ = {0.f, 0.f, 1.f, 0.f};
109 if (m.row(3) != kNoPerspective) {
110 // Perspective matrices will have per-location scale factors calculated, so cached scale
111 // factors will not be used.
112 if (m.invert(&fInvM)) {
113 fType = Type::kPerspective;
114 } else {
115 fType = Type::kInvalid;
116 }
117 return;
118 } else if (m.col(2) != kNoZ || m.row(2) != kNoZ) {
119 // Orthographic matrices are lumped into the kAffine type although we use SkM44::invert()
120 // instead of taking short cuts.
121 if (m.invert(&fInvM)) {
122 fType = Type::kAffine;
123 // These scale factors are valid for the case where Z=0, which is the case for all
124 // local geometry that's drawn.
125 std::tie(fMinScaleFactor, fMaxScaleFactor) = compute_svd(m.rc(0,0), m.rc(0,1),
126 m.rc(1,0), m.rc(1,1));
127 } else {
128 fType = Type::kInvalid;
129 }
130 return;
131 }
132
133 // [sx kx 0 tx]
134 // At this point, we know that m is of the form [ky sy 0 ty]
135 // [0 0 1 0 ]
136 // [0 0 0 1 ]
137 // Other than kIdentity, none of the types depend on (tx, ty). The remaining types are
138 // identified by considering the upper 2x2 (tx and ty are still used to compute the inverse).
139 const float sx = m.rc(0, 0);
140 const float sy = m.rc(1, 1);
141 const float kx = m.rc(0, 1);
142 const float ky = m.rc(1, 0);
143 const float tx = m.rc(0, 3);
144 const float ty = m.rc(1, 3);
145 if (kx == 0.f && ky == 0.f) {
146 // 2x2 is a diagonal matrix
147 if (sx == 0.f || sy == 0.f) {
148 // Not invertible
149 fType = Type::kInvalid;
150 } else if (sx == 1.f && sy == 1.f && tx == 0.f && ty == 0.f) {
151 fType = Type::kIdentity;
152 fInvM.setIdentity();
153 } else {
154 const float ix = 1.f / sx;
155 const float iy = 1.f / sy;
156 fType = sx > 0.f && sy > 0.f ? Type::kSimpleRectStaysRect
157 : Type::kRectStaysRect;
158 fInvM = SkM44(ix, 0.f, 0.f, -ix*tx,
159 0.f, iy, 0.f, -iy*ty,
160 0.f, 0.f, 1.f, 0.f,
161 0.f, 0.f, 0.f, 1.f);
162 std::tie(fMinScaleFactor, fMaxScaleFactor) = sort_scale(sx, sy);
163 }
164 } else if (sx == 0.f && sy == 0.f) {
165 // 2x2 is an anti-diagonal matrix and represents a 90 or 270 degree rotation plus optional
166 // scale and translate.
167 if (kx == 0.f || ky == 0.f) {
168 // Not invertible
169 fType = Type::kInvalid;
170 } else {
171 const float ix = 1.f / kx;
172 const float iy = 1.f / ky;
173 fType = Type::kRectStaysRect;
174 fInvM = SkM44(0.f, iy, 0.f, -iy*ty,
175 ix, 0.f, 0.f, -ix*tx,
176 0.f, 0.f, 1.f, 0.f,
177 0.f, 0.f, 0.f, 1.f);
178 std::tie(fMinScaleFactor, fMaxScaleFactor) = sort_scale(kx, ky);
179 }
180 } else {
181 // Invert just the upper 2x2 and derive inverse translation from that
182 float upper[4] = {sx, ky, kx, sy}; // col-major
183 float invUpper[4];
184 if (SkInvert2x2Matrix(upper, invUpper) == 0.f) {
185 // 2x2 was not invertible, so the original matrix won't be invertible either
186 fType = Type::kInvalid;
187 } else {
188 fType = Type::kAffine;
189 fInvM = SkM44(invUpper[0], invUpper[2], 0.f, -invUpper[0]*tx - invUpper[2]*ty,
190 invUpper[1], invUpper[3], 0.f, -invUpper[1]*tx - invUpper[3]*ty,
191 0.f, 0.f, 1.f, 0.f,
192 0.f, 0.f, 0.f, 1.f);
193 std::tie(fMinScaleFactor, fMaxScaleFactor) = compute_svd(sx, kx, ky, sy);
194 }
195 }
196 }
197
scaleFactors(const SkV2 & p) const198 std::pair<float, float> Transform::scaleFactors(const SkV2& p) const {
199 SkASSERT(this->valid());
200 if (fType < Type::kPerspective) {
201 return {fMinScaleFactor, fMaxScaleFactor};
202 }
203
204 // [m00 m01 * m03] [f(u,v)]
205 // Assuming M = [m10 m11 * m13], define the projected p'(u,v) = [g(u,v)] where
206 // [ * * * * ]
207 // [m30 m31 * m33]
208 // [x] [u]
209 // f(u,v) = x(u,v) / w(u,v), g(u,v) = y(u,v) / w(u,v) and [y] = M*[v]
210 // [*] = [0]
211 // [w] [1]
212 //
213 // x(u,v) = m00*u + m01*v + m03
214 // y(u,v) = m10*u + m11*v + m13
215 // w(u,v) = m30*u + m31*v + m33
216 //
217 // dx/du = m00, dx/dv = m01,
218 // dy/du = m10, dy/dv = m11
219 // dw/du = m30, dw/dv = m31
220 //
221 // df/du = (dx/du*w - x*dw/du)/w^2 = (m00*w - m30*x)/w^2 = (m00 - m30*f)/w
222 // df/dv = (dx/dv*w - x*dw/dv)/w^2 = (m01*w - m31*x)/w^2 = (m01 - m31*f)/w
223 // dg/du = (dy/du*w - y*dw/du)/w^2 = (m10*w - m30*y)/w^2 = (m10 - m30*g)/w
224 // dg/dv = (dy/dv*w - y*dw/du)/w^2 = (m11*w - m31*y)/w^2 = (m11 - m31*g)/w
225 //
226 // Singular values of [df/du df/dv] define perspective correct minimum and maximum scale factors
227 // [dg/du dg/dv]
228 // for M evaluated at (u,v)
229 SkV4 devP = fM.map(p.x, p.y, 0.f, 1.f);
230
231 const float dxdu = fM.rc(0,0);
232 const float dxdv = fM.rc(0,1);
233 const float dydu = fM.rc(1,0);
234 const float dydv = fM.rc(1,1);
235 const float dwdu = fM.rc(3,0);
236 const float dwdv = fM.rc(3,1);
237
238 float invW2 = sk_ieee_float_divide(1.f, (devP.w * devP.w));
239 // non-persp has invW2 = 1, devP.w = 1, dwdu = 0, dwdv = 0
240 float dfdu = (devP.w*dxdu - devP.x*dwdu) * invW2; // non-persp -> dxdu -> m00
241 float dfdv = (devP.w*dxdv - devP.x*dwdv) * invW2; // non-persp -> dxdv -> m01
242 float dgdu = (devP.w*dydu - devP.y*dwdu) * invW2; // non-persp -> dydu -> m10
243 float dgdv = (devP.w*dydv - devP.y*dwdv) * invW2; // non-persp -> dydv -> m11
244
245 // no-persp, these are the singular values of [m00,m01][m10,m11], which was already calculated
246 // in get_matrix_info.
247 return compute_svd(dfdu, dfdv, dgdu, dgdv);
248 }
249
localAARadius(const Rect & bounds) const250 float Transform::localAARadius(const Rect& bounds) const {
251 SkASSERT(this->valid());
252
253 float min;
254 if (fType < Type::kPerspective) {
255 // The scale factor is constant
256 min = fMinScaleFactor;
257 } else {
258 // Calculate the minimum scale factor over the 4 corners of the bounding box
259 float tl = std::get<0>(this->scaleFactors(SkV2{bounds.left(), bounds.top()}));
260 float tr = std::get<0>(this->scaleFactors(SkV2{bounds.right(), bounds.top()}));
261 float br = std::get<0>(this->scaleFactors(SkV2{bounds.right(), bounds.bot()}));
262 float bl = std::get<0>(this->scaleFactors(SkV2{bounds.left(), bounds.bot()}));
263 min = std::min(std::min(tl, tr), std::min(br, bl));
264 }
265
266 // Moving 1 from 'p' before transforming will move at least 'min' and at most 'max' from
267 // the transformed point. Thus moving between [1/max, 1/min] pre-transformation means post
268 // transformation moves between [1,max/min] so using 1/min as the local AA radius ensures that
269 // the post-transformed point is at least 1px away from the original.
270 float aaRadius = sk_ieee_float_divide(1.f, min);
271 if (SkIsFinite(aaRadius)) {
272 return aaRadius;
273 } else {
274 return SK_FloatInfinity;
275 }
276 }
277
mapRect(const Rect & rect) const278 Rect Transform::mapRect(const Rect& rect) const {
279 SkASSERT(this->valid());
280 return map_rect(fType, fM, rect);
281 }
inverseMapRect(const Rect & rect) const282 Rect Transform::inverseMapRect(const Rect& rect) const {
283 SkASSERT(this->valid());
284 return map_rect(fType, fInvM, rect);
285 }
286
mapPoints(const Rect & localRect,SkV4 deviceOut[4]) const287 void Transform::mapPoints(const Rect& localRect, SkV4 deviceOut[4]) const {
288 SkASSERT(this->valid());
289 SkV2 localCorners[4] = {{localRect.left(), localRect.top()},
290 {localRect.right(), localRect.top()},
291 {localRect.right(), localRect.bot()},
292 {localRect.left(), localRect.bot()}};
293 this->mapPoints(localCorners, deviceOut, 4);
294 }
295
mapPoints(const SkV2 * localIn,SkV4 * deviceOut,int count) const296 void Transform::mapPoints(const SkV2* localIn, SkV4* deviceOut, int count) const {
297 SkASSERT(this->valid());
298 // TODO: These maybe should go into SkM44, since bulk point mapping seems generally useful
299 auto c0 = skvx::float4::Load(SkMatrixPriv::M44ColMajor(fM) + 0);
300 auto c1 = skvx::float4::Load(SkMatrixPriv::M44ColMajor(fM) + 4);
301 // skip c2 since localIn's z is assumed to be 0
302 auto c3 = skvx::float4::Load(SkMatrixPriv::M44ColMajor(fM) + 12);
303
304 for (int i = 0; i < count; ++i) {
305 auto p = c0 * localIn[i].x + c1 * localIn[i].y /* + c2*0.f */ + c3 /* *1.f */;
306 p.store(deviceOut + i);
307 }
308 }
309
mapPoints(const SkV4 * localIn,SkV4 * deviceOut,int count) const310 void Transform::mapPoints(const SkV4* localIn, SkV4* deviceOut, int count) const {
311 SkASSERT(this->valid());
312 return map_points(fM, localIn, deviceOut, count);
313 }
314
inverseMapPoints(const SkV4 * deviceIn,SkV4 * localOut,int count) const315 void Transform::inverseMapPoints(const SkV4* deviceIn, SkV4* localOut, int count) const {
316 SkASSERT(this->valid());
317 return map_points(fInvM, deviceIn, localOut, count);
318 }
319
320 } // namespace skgpu::graphite
321