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