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