1 /*
2 * Copyright 2020 Google Inc.
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 "include/core/SkM44.h"
9 #include "include/core/SkMatrix.h"
10 #include "src/base/SkVx.h"
11
12 #include "src/core/SkMatrixInvert.h"
13 #include "src/core/SkMatrixPriv.h"
14 #include "src/core/SkPathPriv.h"
15
operator ==(const SkM44 & other) const16 bool SkM44::operator==(const SkM44& other) const {
17 if (this == &other) {
18 return true;
19 }
20
21 auto a0 = skvx::float4::Load(fMat + 0);
22 auto a1 = skvx::float4::Load(fMat + 4);
23 auto a2 = skvx::float4::Load(fMat + 8);
24 auto a3 = skvx::float4::Load(fMat + 12);
25
26 auto b0 = skvx::float4::Load(other.fMat + 0);
27 auto b1 = skvx::float4::Load(other.fMat + 4);
28 auto b2 = skvx::float4::Load(other.fMat + 8);
29 auto b3 = skvx::float4::Load(other.fMat + 12);
30
31 auto eq = (a0 == b0) & (a1 == b1) & (a2 == b2) & (a3 == b3);
32 return (eq[0] & eq[1] & eq[2] & eq[3]) == ~0;
33 }
34
transpose_arrays(SkScalar dst[],const SkScalar src[])35 static void transpose_arrays(SkScalar dst[], const SkScalar src[]) {
36 dst[0] = src[0]; dst[1] = src[4]; dst[2] = src[8]; dst[3] = src[12];
37 dst[4] = src[1]; dst[5] = src[5]; dst[6] = src[9]; dst[7] = src[13];
38 dst[8] = src[2]; dst[9] = src[6]; dst[10] = src[10]; dst[11] = src[14];
39 dst[12] = src[3]; dst[13] = src[7]; dst[14] = src[11]; dst[15] = src[15];
40 }
41
getRowMajor(SkScalar v[]) const42 void SkM44::getRowMajor(SkScalar v[]) const {
43 transpose_arrays(v, fMat);
44 }
45
setConcat(const SkM44 & a,const SkM44 & b)46 SkM44& SkM44::setConcat(const SkM44& a, const SkM44& b) {
47 auto c0 = skvx::float4::Load(a.fMat + 0);
48 auto c1 = skvx::float4::Load(a.fMat + 4);
49 auto c2 = skvx::float4::Load(a.fMat + 8);
50 auto c3 = skvx::float4::Load(a.fMat + 12);
51
52 auto compute = [&](skvx::float4 r) {
53 return c0*r[0] + (c1*r[1] + (c2*r[2] + c3*r[3]));
54 };
55
56 auto m0 = compute(skvx::float4::Load(b.fMat + 0));
57 auto m1 = compute(skvx::float4::Load(b.fMat + 4));
58 auto m2 = compute(skvx::float4::Load(b.fMat + 8));
59 auto m3 = compute(skvx::float4::Load(b.fMat + 12));
60
61 m0.store(fMat + 0);
62 m1.store(fMat + 4);
63 m2.store(fMat + 8);
64 m3.store(fMat + 12);
65 return *this;
66 }
67
preConcat(const SkMatrix & b)68 SkM44& SkM44::preConcat(const SkMatrix& b) {
69 auto c0 = skvx::float4::Load(fMat + 0);
70 auto c1 = skvx::float4::Load(fMat + 4);
71 auto c3 = skvx::float4::Load(fMat + 12);
72
73 auto compute = [&](float r0, float r1, float r3) {
74 return (c0*r0 + (c1*r1 + c3*r3));
75 };
76
77 auto m0 = compute(b[0], b[3], b[6]);
78 auto m1 = compute(b[1], b[4], b[7]);
79 auto m3 = compute(b[2], b[5], b[8]);
80
81 m0.store(fMat + 0);
82 m1.store(fMat + 4);
83 m3.store(fMat + 12);
84 return *this;
85 }
86
preTranslate(SkScalar x,SkScalar y,SkScalar z)87 SkM44& SkM44::preTranslate(SkScalar x, SkScalar y, SkScalar z) {
88 auto c0 = skvx::float4::Load(fMat + 0);
89 auto c1 = skvx::float4::Load(fMat + 4);
90 auto c2 = skvx::float4::Load(fMat + 8);
91 auto c3 = skvx::float4::Load(fMat + 12);
92
93 // only need to update the last column
94 (c0*x + (c1*y + (c2*z + c3))).store(fMat + 12);
95 return *this;
96 }
97
postTranslate(SkScalar x,SkScalar y,SkScalar z)98 SkM44& SkM44::postTranslate(SkScalar x, SkScalar y, SkScalar z) {
99 skvx::float4 t = { x, y, z, 0 };
100 (t * fMat[ 3] + skvx::float4::Load(fMat + 0)).store(fMat + 0);
101 (t * fMat[ 7] + skvx::float4::Load(fMat + 4)).store(fMat + 4);
102 (t * fMat[11] + skvx::float4::Load(fMat + 8)).store(fMat + 8);
103 (t * fMat[15] + skvx::float4::Load(fMat + 12)).store(fMat + 12);
104 return *this;
105 }
106
preScale(SkScalar x,SkScalar y)107 SkM44& SkM44::preScale(SkScalar x, SkScalar y) {
108 auto c0 = skvx::float4::Load(fMat + 0);
109 auto c1 = skvx::float4::Load(fMat + 4);
110
111 (c0 * x).store(fMat + 0);
112 (c1 * y).store(fMat + 4);
113 return *this;
114 }
115
preScale(SkScalar x,SkScalar y,SkScalar z)116 SkM44& SkM44::preScale(SkScalar x, SkScalar y, SkScalar z) {
117 auto c0 = skvx::float4::Load(fMat + 0);
118 auto c1 = skvx::float4::Load(fMat + 4);
119 auto c2 = skvx::float4::Load(fMat + 8);
120
121 (c0 * x).store(fMat + 0);
122 (c1 * y).store(fMat + 4);
123 (c2 * z).store(fMat + 8);
124 return *this;
125 }
126
map(float x,float y,float z,float w) const127 SkV4 SkM44::map(float x, float y, float z, float w) const {
128 auto c0 = skvx::float4::Load(fMat + 0);
129 auto c1 = skvx::float4::Load(fMat + 4);
130 auto c2 = skvx::float4::Load(fMat + 8);
131 auto c3 = skvx::float4::Load(fMat + 12);
132
133 SkV4 v;
134 (c0*x + (c1*y + (c2*z + c3*w))).store(&v.x);
135 return v;
136 }
137
map_rect_affine(const SkRect & src,const float mat[16])138 static SkRect map_rect_affine(const SkRect& src, const float mat[16]) {
139 // When multiplied against vectors of the form <x,y,x,y>, 'flip' allows a single min()
140 // to compute both the min and "negated" max between the xy coordinates. Once finished, another
141 // multiplication produces the original max.
142 const skvx::float4 flip{1.f, 1.f, -1.f, -1.f};
143
144 // Since z = 0 and it's assumed ther's no perspective, only load the upper 2x2 and (tx,ty) in c3
145 auto c0 = skvx::shuffle<0,1,0,1>(skvx::float2::Load(mat + 0)) * flip;
146 auto c1 = skvx::shuffle<0,1,0,1>(skvx::float2::Load(mat + 4)) * flip;
147 auto c3 = skvx::shuffle<0,1,0,1>(skvx::float2::Load(mat + 12));
148
149 // Compute the min and max of the four transformed corners pre-translation; then translate once
150 // at the end.
151 auto minMax = c3 + flip * min(min(c0 * src.fLeft + c1 * src.fTop,
152 c0 * src.fRight + c1 * src.fTop),
153 min(c0 * src.fLeft + c1 * src.fBottom,
154 c0 * src.fRight + c1 * src.fBottom));
155
156 // minMax holds (min x, min y, max x, max y) so can be copied into an SkRect expecting l,t,r,b
157 SkRect r;
158 minMax.store(&r);
159 return r;
160 }
161
map_rect_perspective(const SkRect & src,const float mat[16])162 static SkRect map_rect_perspective(const SkRect& src, const float mat[16]) {
163 // Like map_rect_affine, z = 0 so we can skip the 3rd column, but we do need to compute w's
164 // for each corner of the src rect.
165 auto c0 = skvx::float4::Load(mat + 0);
166 auto c1 = skvx::float4::Load(mat + 4);
167 auto c3 = skvx::float4::Load(mat + 12);
168
169 // Unlike map_rect_affine, we do not defer the 4th column since we may need to homogeneous
170 // coordinates to clip against the w=0 plane
171 auto tl = c0 * src.fLeft + c1 * src.fTop + c3;
172 auto tr = c0 * src.fRight + c1 * src.fTop + c3;
173 auto bl = c0 * src.fLeft + c1 * src.fBottom + c3;
174 auto br = c0 * src.fRight + c1 * src.fBottom + c3;
175
176 // After clipping to w>0 and projecting to 2d, 'project' employs the same negation trick to
177 // compute min and max at the same time.
178 const skvx::float4 flip{1.f, 1.f, -1.f, -1.f};
179 auto project = [&flip](const skvx::float4& p0, const skvx::float4& p1, const skvx::float4& p2) {
180 float w0 = p0[3];
181 if (w0 >= SkPathPriv::kW0PlaneDistance) {
182 // Unclipped, just divide by w
183 return flip * skvx::shuffle<0,1,0,1>(p0) / w0;
184 } else {
185 auto clip = [&](const skvx::float4& p) {
186 float w = p[3];
187 if (w >= SkPathPriv::kW0PlaneDistance) {
188 float t = (SkPathPriv::kW0PlaneDistance - w0) / (w - w0);
189 auto c = (t * skvx::shuffle<0,1>(p) + (1.f - t) * skvx::shuffle<0,1>(p0)) /
190 SkPathPriv::kW0PlaneDistance;
191
192 return flip * skvx::shuffle<0,1,0,1>(c);
193 } else {
194 return skvx::float4(SK_ScalarInfinity);
195 }
196 };
197 // Clip both edges leaving p0, and return the min/max of the two clipped points
198 // (since clip returns infinity when both p0 and 2nd vertex have w<0, it'll
199 // automatically be ignored).
200 return min(clip(p1), clip(p2));
201 }
202 };
203
204 // Project all 4 corners, and pass in their adjacent vertices for clipping if it has w < 0,
205 // then accumulate the min and max xy's.
206 auto minMax = flip * min(min(project(tl, tr, bl), project(tr, br, tl)),
207 min(project(br, bl, tr), project(bl, tl, br)));
208
209 SkRect r;
210 minMax.store(&r);
211 return r;
212 }
213
MapRect(const SkM44 & m,const SkRect & src)214 SkRect SkMatrixPriv::MapRect(const SkM44& m, const SkRect& src) {
215 const bool hasPerspective =
216 m.fMat[3] != 0 || m.fMat[7] != 0 || m.fMat[11] != 0 || m.fMat[15] != 1;
217 if (hasPerspective) {
218 return map_rect_perspective(src, m.fMat);
219 } else {
220 return map_rect_affine(src, m.fMat);
221 }
222 }
223
normalizePerspective()224 void SkM44::normalizePerspective() {
225 // If the bottom row of the matrix is [0, 0, 0, not_one], we will treat the matrix as if it
226 // is in perspective, even though it stills behaves like its affine. If we divide everything
227 // by the not_one value, then it will behave the same, but will be treated as affine,
228 // and therefore faster (e.g. clients can forward-difference calculations).
229 if (fMat[15] != 1 && fMat[15] != 0 && fMat[3] == 0 && fMat[7] == 0 && fMat[11] == 0) {
230 double inv = 1.0 / fMat[15];
231 (skvx::float4::Load(fMat + 0) * inv).store(fMat + 0);
232 (skvx::float4::Load(fMat + 4) * inv).store(fMat + 4);
233 (skvx::float4::Load(fMat + 8) * inv).store(fMat + 8);
234 (skvx::float4::Load(fMat + 12) * inv).store(fMat + 12);
235 fMat[15] = 1.0f;
236 }
237 }
238
239 ///////////////////////////////////////////////////////////////////////////////
240
241 /** We always perform the calculation in doubles, to avoid prematurely losing
242 precision along the way. This relies on the compiler automatically
243 promoting our SkScalar values to double (if needed).
244 */
invert(SkM44 * inverse) const245 bool SkM44::invert(SkM44* inverse) const {
246 SkScalar tmp[16];
247 if (SkInvert4x4Matrix(fMat, tmp) == 0.0f) {
248 return false;
249 }
250 memcpy(inverse->fMat, tmp, sizeof(tmp));
251 return true;
252 }
253
transpose() const254 SkM44 SkM44::transpose() const {
255 SkM44 trans(SkM44::kUninitialized_Constructor);
256 transpose_arrays(trans.fMat, fMat);
257 return trans;
258 }
259
setRotateUnitSinCos(SkV3 axis,SkScalar sinAngle,SkScalar cosAngle)260 SkM44& SkM44::setRotateUnitSinCos(SkV3 axis, SkScalar sinAngle, SkScalar cosAngle) {
261 // Taken from "Essential Mathematics for Games and Interactive Applications"
262 // James M. Van Verth and Lars M. Bishop -- third edition
263 SkScalar x = axis.x;
264 SkScalar y = axis.y;
265 SkScalar z = axis.z;
266 SkScalar c = cosAngle;
267 SkScalar s = sinAngle;
268 SkScalar t = 1 - c;
269
270 *this = { t*x*x + c, t*x*y - s*z, t*x*z + s*y, 0,
271 t*x*y + s*z, t*y*y + c, t*y*z - s*x, 0,
272 t*x*z - s*y, t*y*z + s*x, t*z*z + c, 0,
273 0, 0, 0, 1 };
274 return *this;
275 }
276
setRotate(SkV3 axis,SkScalar radians)277 SkM44& SkM44::setRotate(SkV3 axis, SkScalar radians) {
278 SkScalar len = axis.length();
279 if (len > 0 && SkScalarIsFinite(len)) {
280 this->setRotateUnit(axis * (SK_Scalar1 / len), radians);
281 } else {
282 this->setIdentity();
283 }
284 return *this;
285 }
286
287 ///////////////////////////////////////////////////////////////////////////////
288
dump() const289 void SkM44::dump() const {
290 SkDebugf("|%g %g %g %g|\n"
291 "|%g %g %g %g|\n"
292 "|%g %g %g %g|\n"
293 "|%g %g %g %g|\n",
294 fMat[0], fMat[4], fMat[8], fMat[12],
295 fMat[1], fMat[5], fMat[9], fMat[13],
296 fMat[2], fMat[6], fMat[10], fMat[14],
297 fMat[3], fMat[7], fMat[11], fMat[15]);
298 }
299
300 ///////////////////////////////////////////////////////////////////////////////
301
RectToRect(const SkRect & src,const SkRect & dst)302 SkM44 SkM44::RectToRect(const SkRect& src, const SkRect& dst) {
303 if (src.isEmpty()) {
304 return SkM44();
305 } else if (dst.isEmpty()) {
306 return SkM44::Scale(0.f, 0.f, 0.f);
307 }
308
309 float sx = dst.width() / src.width();
310 float sy = dst.height() / src.height();
311
312 float tx = dst.fLeft - sx * src.fLeft;
313 float ty = dst.fTop - sy * src.fTop;
314
315 return SkM44{sx, 0.f, 0.f, tx,
316 0.f, sy, 0.f, ty,
317 0.f, 0.f, 1.f, 0.f,
318 0.f, 0.f, 0.f, 1.f};
319 }
320
normalize(SkV3 v)321 static SkV3 normalize(SkV3 v) {
322 const auto vlen = v.length();
323
324 return SkScalarNearlyZero(vlen) ? v : v * (1.0f / vlen);
325 }
326
v4(SkV3 v,SkScalar w)327 static SkV4 v4(SkV3 v, SkScalar w) { return {v.x, v.y, v.z, w}; }
328
LookAt(const SkV3 & eye,const SkV3 & center,const SkV3 & up)329 SkM44 SkM44::LookAt(const SkV3& eye, const SkV3& center, const SkV3& up) {
330 SkV3 f = normalize(center - eye);
331 SkV3 u = normalize(up);
332 SkV3 s = normalize(f.cross(u));
333
334 SkM44 m(SkM44::kUninitialized_Constructor);
335 if (!SkM44::Cols(v4(s, 0), v4(s.cross(f), 0), v4(-f, 0), v4(eye, 1)).invert(&m)) {
336 m.setIdentity();
337 }
338 return m;
339 }
340
Perspective(float near,float far,float angle)341 SkM44 SkM44::Perspective(float near, float far, float angle) {
342 SkASSERT(far > near);
343
344 float denomInv = sk_ieee_float_divide(1, far - near);
345 float halfAngle = angle * 0.5f;
346 SkASSERT(halfAngle != 0);
347 float cot = sk_ieee_float_divide(1, sk_float_tan(halfAngle));
348
349 SkM44 m;
350 m.setRC(0, 0, cot);
351 m.setRC(1, 1, cot);
352 m.setRC(2, 2, (far + near) * denomInv);
353 m.setRC(2, 3, 2 * far * near * denomInv);
354 m.setRC(3, 2, -1);
355 return m;
356 }
357