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