The Tor Browser / file comparison

comparison: gfx/skia/trunk/src/core/SkMatrix.cpp

gfx/skia/trunk/src/core/SkMatrix.cpp

branch
TOR_BUG_3246
changeset 6
8bccb770b82d
equal deleted inserted replaced
-1:000000000000 0:c3ebf74295fa
1 /*
2 * Copyright 2006 The Android Open Source Project
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 "SkMatrix.h"
9 #include "SkFloatBits.h"
10 #include "SkOnce.h"
11 #include "SkString.h"
12
13 // In a few places, we performed the following
14 // a * b + c * d + e
15 // as
16 // a * b + (c * d + e)
17 //
18 // sdot and scross are indended to capture these compound operations into a
19 // function, with an eye toward considering upscaling the intermediates to
20 // doubles for more precision (as we do in concat and invert).
21 //
22 // However, these few lines that performed the last add before the "dot", cause
23 // tiny image differences, so we guard that change until we see the impact on
24 // chrome's layouttests.
25 //
26 #define SK_LEGACY_MATRIX_MATH_ORDER
27
28 static inline float SkDoubleToFloat(double x) {
29 return static_cast<float>(x);
30 }
31
32 /* [scale-x skew-x trans-x] [X] [X']
33 [skew-y scale-y trans-y] * [Y] = [Y']
34 [persp-0 persp-1 persp-2] [1] [1 ]
35 */
36
37 void SkMatrix::reset() {
38 fMat[kMScaleX] = fMat[kMScaleY] = fMat[kMPersp2] = 1;
39 fMat[kMSkewX] = fMat[kMSkewY] =
40 fMat[kMTransX] = fMat[kMTransY] =
41 fMat[kMPersp0] = fMat[kMPersp1] = 0;
42
43 this->setTypeMask(kIdentity_Mask | kRectStaysRect_Mask);
44 }
45
46 // this guy aligns with the masks, so we can compute a mask from a varaible 0/1
47 enum {
48 kTranslate_Shift,
49 kScale_Shift,
50 kAffine_Shift,
51 kPerspective_Shift,
52 kRectStaysRect_Shift
53 };
54
55 static const int32_t kScalar1Int = 0x3f800000;
56
57 uint8_t SkMatrix::computePerspectiveTypeMask() const {
58 // Benchmarking suggests that replacing this set of SkScalarAs2sCompliment
59 // is a win, but replacing those below is not. We don't yet understand
60 // that result.
61 if (fMat[kMPersp0] != 0 || fMat[kMPersp1] != 0 || fMat[kMPersp2] != 1) {
62 // If this is a perspective transform, we return true for all other
63 // transform flags - this does not disable any optimizations, respects
64 // the rule that the type mask must be conservative, and speeds up
65 // type mask computation.
66 return SkToU8(kORableMasks);
67 }
68
69 return SkToU8(kOnlyPerspectiveValid_Mask | kUnknown_Mask);
70 }
71
72 uint8_t SkMatrix::computeTypeMask() const {
73 unsigned mask = 0;
74
75 if (fMat[kMPersp0] != 0 || fMat[kMPersp1] != 0 || fMat[kMPersp2] != 1) {
76 // Once it is determined that that this is a perspective transform,
77 // all other flags are moot as far as optimizations are concerned.
78 return SkToU8(kORableMasks);
79 }
80
81 if (fMat[kMTransX] != 0 || fMat[kMTransY] != 0) {
82 mask |= kTranslate_Mask;
83 }
84
85 int m00 = SkScalarAs2sCompliment(fMat[SkMatrix::kMScaleX]);
86 int m01 = SkScalarAs2sCompliment(fMat[SkMatrix::kMSkewX]);
87 int m10 = SkScalarAs2sCompliment(fMat[SkMatrix::kMSkewY]);
88 int m11 = SkScalarAs2sCompliment(fMat[SkMatrix::kMScaleY]);
89
90 if (m01 | m10) {
91 // The skew components may be scale-inducing, unless we are dealing
92 // with a pure rotation. Testing for a pure rotation is expensive,
93 // so we opt for being conservative by always setting the scale bit.
94 // along with affine.
95 // By doing this, we are also ensuring that matrices have the same
96 // type masks as their inverses.
97 mask |= kAffine_Mask | kScale_Mask;
98
99 // For rectStaysRect, in the affine case, we only need check that
100 // the primary diagonal is all zeros and that the secondary diagonal
101 // is all non-zero.
102
103 // map non-zero to 1
104 m01 = m01 != 0;
105 m10 = m10 != 0;
106
107 int dp0 = 0 == (m00 | m11) ; // true if both are 0
108 int ds1 = m01 & m10; // true if both are 1
109
110 mask |= (dp0 & ds1) << kRectStaysRect_Shift;
111 } else {
112 // Only test for scale explicitly if not affine, since affine sets the
113 // scale bit.
114 if ((m00 - kScalar1Int) | (m11 - kScalar1Int)) {
115 mask |= kScale_Mask;
116 }
117
118 // Not affine, therefore we already know secondary diagonal is
119 // all zeros, so we just need to check that primary diagonal is
120 // all non-zero.
121
122 // map non-zero to 1
123 m00 = m00 != 0;
124 m11 = m11 != 0;
125
126 // record if the (p)rimary diagonal is all non-zero
127 mask |= (m00 & m11) << kRectStaysRect_Shift;
128 }
129
130 return SkToU8(mask);
131 }
132
133 ///////////////////////////////////////////////////////////////////////////////
134
135 bool operator==(const SkMatrix& a, const SkMatrix& b) {
136 const SkScalar* SK_RESTRICT ma = a.fMat;
137 const SkScalar* SK_RESTRICT mb = b.fMat;
138
139 return ma[0] == mb[0] && ma[1] == mb[1] && ma[2] == mb[2] &&
140 ma[3] == mb[3] && ma[4] == mb[4] && ma[5] == mb[5] &&
141 ma[6] == mb[6] && ma[7] == mb[7] && ma[8] == mb[8];
142 }
143
144 ///////////////////////////////////////////////////////////////////////////////
145
146 // helper function to determine if upper-left 2x2 of matrix is degenerate
147 static inline bool is_degenerate_2x2(SkScalar scaleX, SkScalar skewX,
148 SkScalar skewY, SkScalar scaleY) {
149 SkScalar perp_dot = scaleX*scaleY - skewX*skewY;
150 return SkScalarNearlyZero(perp_dot, SK_ScalarNearlyZero*SK_ScalarNearlyZero);
151 }
152
153 ///////////////////////////////////////////////////////////////////////////////
154
155 bool SkMatrix::isSimilarity(SkScalar tol) const {
156 // if identity or translate matrix
157 TypeMask mask = this->getType();
158 if (mask <= kTranslate_Mask) {
159 return true;
160 }
161 if (mask & kPerspective_Mask) {
162 return false;
163 }
164
165 SkScalar mx = fMat[kMScaleX];
166 SkScalar my = fMat[kMScaleY];
167 // if no skew, can just compare scale factors
168 if (!(mask & kAffine_Mask)) {
169 return !SkScalarNearlyZero(mx) && SkScalarNearlyEqual(SkScalarAbs(mx), SkScalarAbs(my));
170 }
171 SkScalar sx = fMat[kMSkewX];
172 SkScalar sy = fMat[kMSkewY];
173
174 if (is_degenerate_2x2(mx, sx, sy, my)) {
175 return false;
176 }
177
178 // it has scales and skews, but it could also be rotation, check it out.
179 SkVector vec[2];
180 vec[0].set(mx, sx);
181 vec[1].set(sy, my);
182
183 return SkScalarNearlyZero(vec[0].dot(vec[1]), SkScalarSquare(tol)) &&
184 SkScalarNearlyEqual(vec[0].lengthSqd(), vec[1].lengthSqd(),
185 SkScalarSquare(tol));
186 }
187
188 bool SkMatrix::preservesRightAngles(SkScalar tol) const {
189 TypeMask mask = this->getType();
190
191 if (mask <= (SkMatrix::kTranslate_Mask | SkMatrix::kScale_Mask)) {
192 // identity, translate and/or scale
193 return true;
194 }
195 if (mask & kPerspective_Mask) {
196 return false;
197 }
198
199 SkASSERT(mask & kAffine_Mask);
200
201 SkScalar mx = fMat[kMScaleX];
202 SkScalar my = fMat[kMScaleY];
203 SkScalar sx = fMat[kMSkewX];
204 SkScalar sy = fMat[kMSkewY];
205
206 if (is_degenerate_2x2(mx, sx, sy, my)) {
207 return false;
208 }
209
210 // it has scales and skews, but it could also be rotation, check it out.
211 SkVector vec[2];
212 vec[0].set(mx, sx);
213 vec[1].set(sy, my);
214
215 return SkScalarNearlyZero(vec[0].dot(vec[1]), SkScalarSquare(tol)) &&
216 SkScalarNearlyEqual(vec[0].lengthSqd(), vec[1].lengthSqd(),
217 SkScalarSquare(tol));
218 }
219
220 ///////////////////////////////////////////////////////////////////////////////
221
222 static inline SkScalar sdot(SkScalar a, SkScalar b, SkScalar c, SkScalar d) {
223 return a * b + c * d;
224 }
225
226 static inline SkScalar sdot(SkScalar a, SkScalar b, SkScalar c, SkScalar d,
227 SkScalar e, SkScalar f) {
228 return a * b + c * d + e * f;
229 }
230
231 static inline SkScalar scross(SkScalar a, SkScalar b, SkScalar c, SkScalar d) {
232 return a * b - c * d;
233 }
234
235 void SkMatrix::setTranslate(SkScalar dx, SkScalar dy) {
236 if (dx || dy) {
237 fMat[kMTransX] = dx;
238 fMat[kMTransY] = dy;
239
240 fMat[kMScaleX] = fMat[kMScaleY] = fMat[kMPersp2] = 1;
241 fMat[kMSkewX] = fMat[kMSkewY] =
242 fMat[kMPersp0] = fMat[kMPersp1] = 0;
243
244 this->setTypeMask(kTranslate_Mask | kRectStaysRect_Mask);
245 } else {
246 this->reset();
247 }
248 }
249
250 bool SkMatrix::preTranslate(SkScalar dx, SkScalar dy) {
251 if (this->hasPerspective()) {
252 SkMatrix m;
253 m.setTranslate(dx, dy);
254 return this->preConcat(m);
255 }
256
257 if (dx || dy) {
258 fMat[kMTransX] += sdot(fMat[kMScaleX], dx, fMat[kMSkewX], dy);
259 fMat[kMTransY] += sdot(fMat[kMSkewY], dx, fMat[kMScaleY], dy);
260
261 this->setTypeMask(kUnknown_Mask | kOnlyPerspectiveValid_Mask);
262 }
263 return true;
264 }
265
266 bool SkMatrix::postTranslate(SkScalar dx, SkScalar dy) {
267 if (this->hasPerspective()) {
268 SkMatrix m;
269 m.setTranslate(dx, dy);
270 return this->postConcat(m);
271 }
272
273 if (dx || dy) {
274 fMat[kMTransX] += dx;
275 fMat[kMTransY] += dy;
276 this->setTypeMask(kUnknown_Mask | kOnlyPerspectiveValid_Mask);
277 }
278 return true;
279 }
280
281 ///////////////////////////////////////////////////////////////////////////////
282
283 void SkMatrix::setScale(SkScalar sx, SkScalar sy, SkScalar px, SkScalar py) {
284 if (1 == sx && 1 == sy) {
285 this->reset();
286 } else {
287 fMat[kMScaleX] = sx;
288 fMat[kMScaleY] = sy;
289 fMat[kMTransX] = px - sx * px;
290 fMat[kMTransY] = py - sy * py;
291 fMat[kMPersp2] = 1;
292
293 fMat[kMSkewX] = fMat[kMSkewY] =
294 fMat[kMPersp0] = fMat[kMPersp1] = 0;
295
296 this->setTypeMask(kScale_Mask | kTranslate_Mask | kRectStaysRect_Mask);
297 }
298 }
299
300 void SkMatrix::setScale(SkScalar sx, SkScalar sy) {
301 if (1 == sx && 1 == sy) {
302 this->reset();
303 } else {
304 fMat[kMScaleX] = sx;
305 fMat[kMScaleY] = sy;
306 fMat[kMPersp2] = 1;
307
308 fMat[kMTransX] = fMat[kMTransY] =
309 fMat[kMSkewX] = fMat[kMSkewY] =
310 fMat[kMPersp0] = fMat[kMPersp1] = 0;
311
312 this->setTypeMask(kScale_Mask | kRectStaysRect_Mask);
313 }
314 }
315
316 bool SkMatrix::setIDiv(int divx, int divy) {
317 if (!divx || !divy) {
318 return false;
319 }
320 this->setScale(SkScalarInvert(divx), SkScalarInvert(divy));
321 return true;
322 }
323
324 bool SkMatrix::preScale(SkScalar sx, SkScalar sy, SkScalar px, SkScalar py) {
325 SkMatrix m;
326 m.setScale(sx, sy, px, py);
327 return this->preConcat(m);
328 }
329
330 bool SkMatrix::preScale(SkScalar sx, SkScalar sy) {
331 if (1 == sx && 1 == sy) {
332 return true;
333 }
334
335 // the assumption is that these multiplies are very cheap, and that
336 // a full concat and/or just computing the matrix type is more expensive.
337 // Also, the fixed-point case checks for overflow, but the float doesn't,
338 // so we can get away with these blind multiplies.
339
340 fMat[kMScaleX] *= sx;
341 fMat[kMSkewY] *= sx;
342 fMat[kMPersp0] *= sx;
343
344 fMat[kMSkewX] *= sy;
345 fMat[kMScaleY] *= sy;
346 fMat[kMPersp1] *= sy;
347
348 this->orTypeMask(kScale_Mask);
349 return true;
350 }
351
352 bool SkMatrix::postScale(SkScalar sx, SkScalar sy, SkScalar px, SkScalar py) {
353 if (1 == sx && 1 == sy) {
354 return true;
355 }
356 SkMatrix m;
357 m.setScale(sx, sy, px, py);
358 return this->postConcat(m);
359 }
360
361 bool SkMatrix::postScale(SkScalar sx, SkScalar sy) {
362 if (1 == sx && 1 == sy) {
363 return true;
364 }
365 SkMatrix m;
366 m.setScale(sx, sy);
367 return this->postConcat(m);
368 }
369
370 // this guy perhaps can go away, if we have a fract/high-precision way to
371 // scale matrices
372 bool SkMatrix::postIDiv(int divx, int divy) {
373 if (divx == 0 || divy == 0) {
374 return false;
375 }
376
377 const float invX = 1.f / divx;
378 const float invY = 1.f / divy;
379
380 fMat[kMScaleX] *= invX;
381 fMat[kMSkewX] *= invX;
382 fMat[kMTransX] *= invX;
383
384 fMat[kMScaleY] *= invY;
385 fMat[kMSkewY] *= invY;
386 fMat[kMTransY] *= invY;
387
388 this->setTypeMask(kUnknown_Mask);
389 return true;
390 }
391
392 ////////////////////////////////////////////////////////////////////////////////////
393
394 void SkMatrix::setSinCos(SkScalar sinV, SkScalar cosV,
395 SkScalar px, SkScalar py) {
396 const SkScalar oneMinusCosV = 1 - cosV;
397
398 fMat[kMScaleX] = cosV;
399 fMat[kMSkewX] = -sinV;
400 fMat[kMTransX] = sdot(sinV, py, oneMinusCosV, px);
401
402 fMat[kMSkewY] = sinV;
403 fMat[kMScaleY] = cosV;
404 fMat[kMTransY] = sdot(-sinV, px, oneMinusCosV, py);
405
406 fMat[kMPersp0] = fMat[kMPersp1] = 0;
407 fMat[kMPersp2] = 1;
408
409 this->setTypeMask(kUnknown_Mask | kOnlyPerspectiveValid_Mask);
410 }
411
412 void SkMatrix::setSinCos(SkScalar sinV, SkScalar cosV) {
413 fMat[kMScaleX] = cosV;
414 fMat[kMSkewX] = -sinV;
415 fMat[kMTransX] = 0;
416
417 fMat[kMSkewY] = sinV;
418 fMat[kMScaleY] = cosV;
419 fMat[kMTransY] = 0;
420
421 fMat[kMPersp0] = fMat[kMPersp1] = 0;
422 fMat[kMPersp2] = 1;
423
424 this->setTypeMask(kUnknown_Mask | kOnlyPerspectiveValid_Mask);
425 }
426
427 void SkMatrix::setRotate(SkScalar degrees, SkScalar px, SkScalar py) {
428 SkScalar sinV, cosV;
429 sinV = SkScalarSinCos(SkDegreesToRadians(degrees), &cosV);
430 this->setSinCos(sinV, cosV, px, py);
431 }
432
433 void SkMatrix::setRotate(SkScalar degrees) {
434 SkScalar sinV, cosV;
435 sinV = SkScalarSinCos(SkDegreesToRadians(degrees), &cosV);
436 this->setSinCos(sinV, cosV);
437 }
438
439 bool SkMatrix::preRotate(SkScalar degrees, SkScalar px, SkScalar py) {
440 SkMatrix m;
441 m.setRotate(degrees, px, py);
442 return this->preConcat(m);
443 }
444
445 bool SkMatrix::preRotate(SkScalar degrees) {
446 SkMatrix m;
447 m.setRotate(degrees);
448 return this->preConcat(m);
449 }
450
451 bool SkMatrix::postRotate(SkScalar degrees, SkScalar px, SkScalar py) {
452 SkMatrix m;
453 m.setRotate(degrees, px, py);
454 return this->postConcat(m);
455 }
456
457 bool SkMatrix::postRotate(SkScalar degrees) {
458 SkMatrix m;
459 m.setRotate(degrees);
460 return this->postConcat(m);
461 }
462
463 ////////////////////////////////////////////////////////////////////////////////////
464
465 void SkMatrix::setSkew(SkScalar sx, SkScalar sy, SkScalar px, SkScalar py) {
466 fMat[kMScaleX] = 1;
467 fMat[kMSkewX] = sx;
468 fMat[kMTransX] = -sx * py;
469
470 fMat[kMSkewY] = sy;
471 fMat[kMScaleY] = 1;
472 fMat[kMTransY] = -sy * px;
473
474 fMat[kMPersp0] = fMat[kMPersp1] = 0;
475 fMat[kMPersp2] = 1;
476
477 this->setTypeMask(kUnknown_Mask | kOnlyPerspectiveValid_Mask);
478 }
479
480 void SkMatrix::setSkew(SkScalar sx, SkScalar sy) {
481 fMat[kMScaleX] = 1;
482 fMat[kMSkewX] = sx;
483 fMat[kMTransX] = 0;
484
485 fMat[kMSkewY] = sy;
486 fMat[kMScaleY] = 1;
487 fMat[kMTransY] = 0;
488
489 fMat[kMPersp0] = fMat[kMPersp1] = 0;
490 fMat[kMPersp2] = 1;
491
492 this->setTypeMask(kUnknown_Mask | kOnlyPerspectiveValid_Mask);
493 }
494
495 bool SkMatrix::preSkew(SkScalar sx, SkScalar sy, SkScalar px, SkScalar py) {
496 SkMatrix m;
497 m.setSkew(sx, sy, px, py);
498 return this->preConcat(m);
499 }
500
501 bool SkMatrix::preSkew(SkScalar sx, SkScalar sy) {
502 SkMatrix m;
503 m.setSkew(sx, sy);
504 return this->preConcat(m);
505 }
506
507 bool SkMatrix::postSkew(SkScalar sx, SkScalar sy, SkScalar px, SkScalar py) {
508 SkMatrix m;
509 m.setSkew(sx, sy, px, py);
510 return this->postConcat(m);
511 }
512
513 bool SkMatrix::postSkew(SkScalar sx, SkScalar sy) {
514 SkMatrix m;
515 m.setSkew(sx, sy);
516 return this->postConcat(m);
517 }
518
519 ///////////////////////////////////////////////////////////////////////////////
520
521 bool SkMatrix::setRectToRect(const SkRect& src, const SkRect& dst,
522 ScaleToFit align)
523 {
524 if (src.isEmpty()) {
525 this->reset();
526 return false;
527 }
528
529 if (dst.isEmpty()) {
530 sk_bzero(fMat, 8 * sizeof(SkScalar));
531 this->setTypeMask(kScale_Mask | kRectStaysRect_Mask);
532 } else {
533 SkScalar tx, sx = dst.width() / src.width();
534 SkScalar ty, sy = dst.height() / src.height();
535 bool xLarger = false;
536
537 if (align != kFill_ScaleToFit) {
538 if (sx > sy) {
539 xLarger = true;
540 sx = sy;
541 } else {
542 sy = sx;
543 }
544 }
545
546 tx = dst.fLeft - src.fLeft * sx;
547 ty = dst.fTop - src.fTop * sy;
548 if (align == kCenter_ScaleToFit || align == kEnd_ScaleToFit) {
549 SkScalar diff;
550
551 if (xLarger) {
552 diff = dst.width() - src.width() * sy;
553 } else {
554 diff = dst.height() - src.height() * sy;
555 }
556
557 if (align == kCenter_ScaleToFit) {
558 diff = SkScalarHalf(diff);
559 }
560
561 if (xLarger) {
562 tx += diff;
563 } else {
564 ty += diff;
565 }
566 }
567
568 fMat[kMScaleX] = sx;
569 fMat[kMScaleY] = sy;
570 fMat[kMTransX] = tx;
571 fMat[kMTransY] = ty;
572 fMat[kMSkewX] = fMat[kMSkewY] =
573 fMat[kMPersp0] = fMat[kMPersp1] = 0;
574
575 unsigned mask = kRectStaysRect_Mask;
576 if (sx != 1 || sy != 1) {
577 mask |= kScale_Mask;
578 }
579 if (tx || ty) {
580 mask |= kTranslate_Mask;
581 }
582 this->setTypeMask(mask);
583 }
584 // shared cleanup
585 fMat[kMPersp2] = 1;
586 return true;
587 }
588
589 ///////////////////////////////////////////////////////////////////////////////
590
591 static inline int fixmuladdmul(float a, float b, float c, float d,
592 float* result) {
593 *result = SkDoubleToFloat((double)a * b + (double)c * d);
594 return true;
595 }
596
597 static inline bool rowcol3(const float row[], const float col[],
598 float* result) {
599 *result = row[0] * col[0] + row[1] * col[3] + row[2] * col[6];
600 return true;
601 }
602
603 static inline int negifaddoverflows(float& result, float a, float b) {
604 result = a + b;
605 return 0;
606 }
607
608 static void normalize_perspective(SkScalar mat[9]) {
609 if (SkScalarAbs(mat[SkMatrix::kMPersp2]) > 1) {
610 for (int i = 0; i < 9; i++)
611 mat[i] = SkScalarHalf(mat[i]);
612 }
613 }
614
615 bool SkMatrix::setConcat(const SkMatrix& a, const SkMatrix& b) {
616 TypeMask aType = a.getPerspectiveTypeMaskOnly();
617 TypeMask bType = b.getPerspectiveTypeMaskOnly();
618
619 if (a.isTriviallyIdentity()) {
620 *this = b;
621 } else if (b.isTriviallyIdentity()) {
622 *this = a;
623 } else {
624 SkMatrix tmp;
625
626 if ((aType | bType) & kPerspective_Mask) {
627 if (!rowcol3(&a.fMat[0], &b.fMat[0], &tmp.fMat[kMScaleX])) {
628 return false;
629 }
630 if (!rowcol3(&a.fMat[0], &b.fMat[1], &tmp.fMat[kMSkewX])) {
631 return false;
632 }
633 if (!rowcol3(&a.fMat[0], &b.fMat[2], &tmp.fMat[kMTransX])) {
634 return false;
635 }
636
637 if (!rowcol3(&a.fMat[3], &b.fMat[0], &tmp.fMat[kMSkewY])) {
638 return false;
639 }
640 if (!rowcol3(&a.fMat[3], &b.fMat[1], &tmp.fMat[kMScaleY])) {
641 return false;
642 }
643 if (!rowcol3(&a.fMat[3], &b.fMat[2], &tmp.fMat[kMTransY])) {
644 return false;
645 }
646
647 if (!rowcol3(&a.fMat[6], &b.fMat[0], &tmp.fMat[kMPersp0])) {
648 return false;
649 }
650 if (!rowcol3(&a.fMat[6], &b.fMat[1], &tmp.fMat[kMPersp1])) {
651 return false;
652 }
653 if (!rowcol3(&a.fMat[6], &b.fMat[2], &tmp.fMat[kMPersp2])) {
654 return false;
655 }
656
657 normalize_perspective(tmp.fMat);
658 tmp.setTypeMask(kUnknown_Mask);
659 } else { // not perspective
660 if (!fixmuladdmul(a.fMat[kMScaleX], b.fMat[kMScaleX],
661 a.fMat[kMSkewX], b.fMat[kMSkewY], &tmp.fMat[kMScaleX])) {
662 return false;
663 }
664 if (!fixmuladdmul(a.fMat[kMScaleX], b.fMat[kMSkewX],
665 a.fMat[kMSkewX], b.fMat[kMScaleY], &tmp.fMat[kMSkewX])) {
666 return false;
667 }
668 if (!fixmuladdmul(a.fMat[kMScaleX], b.fMat[kMTransX],
669 a.fMat[kMSkewX], b.fMat[kMTransY], &tmp.fMat[kMTransX])) {
670 return false;
671 }
672 if (negifaddoverflows(tmp.fMat[kMTransX], tmp.fMat[kMTransX],
673 a.fMat[kMTransX]) < 0) {
674 return false;
675 }
676
677 if (!fixmuladdmul(a.fMat[kMSkewY], b.fMat[kMScaleX],
678 a.fMat[kMScaleY], b.fMat[kMSkewY], &tmp.fMat[kMSkewY])) {
679 return false;
680 }
681 if (!fixmuladdmul(a.fMat[kMSkewY], b.fMat[kMSkewX],
682 a.fMat[kMScaleY], b.fMat[kMScaleY], &tmp.fMat[kMScaleY])) {
683 return false;
684 }
685 if (!fixmuladdmul(a.fMat[kMSkewY], b.fMat[kMTransX],
686 a.fMat[kMScaleY], b.fMat[kMTransY], &tmp.fMat[kMTransY])) {
687 return false;
688 }
689 if (negifaddoverflows(tmp.fMat[kMTransY], tmp.fMat[kMTransY],
690 a.fMat[kMTransY]) < 0) {
691 return false;
692 }
693
694 tmp.fMat[kMPersp0] = tmp.fMat[kMPersp1] = 0;
695 tmp.fMat[kMPersp2] = 1;
696 //SkDebugf("Concat mat non-persp type: %d\n", tmp.getType());
697 //SkASSERT(!(tmp.getType() & kPerspective_Mask));
698 tmp.setTypeMask(kUnknown_Mask | kOnlyPerspectiveValid_Mask);
699 }
700 *this = tmp;
701 }
702 return true;
703 }
704
705 bool SkMatrix::preConcat(const SkMatrix& mat) {
706 // check for identity first, so we don't do a needless copy of ourselves
707 // to ourselves inside setConcat()
708 return mat.isIdentity() || this->setConcat(*this, mat);
709 }
710
711 bool SkMatrix::postConcat(const SkMatrix& mat) {
712 // check for identity first, so we don't do a needless copy of ourselves
713 // to ourselves inside setConcat()
714 return mat.isIdentity() || this->setConcat(mat, *this);
715 }
716
717 ///////////////////////////////////////////////////////////////////////////////
718
719 /* Matrix inversion is very expensive, but also the place where keeping
720 precision may be most important (here and matrix concat). Hence to avoid
721 bitmap blitting artifacts when walking the inverse, we use doubles for
722 the intermediate math, even though we know that is more expensive.
723 */
724
725 static inline SkScalar scross_dscale(SkScalar a, SkScalar b,
726 SkScalar c, SkScalar d, double scale) {
727 return SkDoubleToScalar(scross(a, b, c, d) * scale);
728 }
729
730 static inline double dcross(double a, double b, double c, double d) {
731 return a * b - c * d;
732 }
733
734 static inline SkScalar dcross_dscale(double a, double b,
735 double c, double d, double scale) {
736 return SkDoubleToScalar(dcross(a, b, c, d) * scale);
737 }
738
739 static double sk_inv_determinant(const float mat[9], int isPerspective) {
740 double det;
741
742 if (isPerspective) {
743 det = mat[SkMatrix::kMScaleX] *
744 dcross(mat[SkMatrix::kMScaleY], mat[SkMatrix::kMPersp2],
745 mat[SkMatrix::kMTransY], mat[SkMatrix::kMPersp1])
746 +
747 mat[SkMatrix::kMSkewX] *
748 dcross(mat[SkMatrix::kMTransY], mat[SkMatrix::kMPersp0],
749 mat[SkMatrix::kMSkewY], mat[SkMatrix::kMPersp2])
750 +
751 mat[SkMatrix::kMTransX] *
752 dcross(mat[SkMatrix::kMSkewY], mat[SkMatrix::kMPersp1],
753 mat[SkMatrix::kMScaleY], mat[SkMatrix::kMPersp0]);
754 } else {
755 det = dcross(mat[SkMatrix::kMScaleX], mat[SkMatrix::kMScaleY],
756 mat[SkMatrix::kMSkewX], mat[SkMatrix::kMSkewY]);
757 }
758
759 // Since the determinant is on the order of the cube of the matrix members,
760 // compare to the cube of the default nearly-zero constant (although an
761 // estimate of the condition number would be better if it wasn't so expensive).
762 if (SkScalarNearlyZero((float)det, SK_ScalarNearlyZero * SK_ScalarNearlyZero * SK_ScalarNearlyZero)) {
763 return 0;
764 }
765 return 1.0 / det;
766 }
767
768 void SkMatrix::SetAffineIdentity(SkScalar affine[6]) {
769 affine[kAScaleX] = 1;
770 affine[kASkewY] = 0;
771 affine[kASkewX] = 0;
772 affine[kAScaleY] = 1;
773 affine[kATransX] = 0;
774 affine[kATransY] = 0;
775 }
776
777 bool SkMatrix::asAffine(SkScalar affine[6]) const {
778 if (this->hasPerspective()) {
779 return false;
780 }
781 if (affine) {
782 affine[kAScaleX] = this->fMat[kMScaleX];
783 affine[kASkewY] = this->fMat[kMSkewY];
784 affine[kASkewX] = this->fMat[kMSkewX];
785 affine[kAScaleY] = this->fMat[kMScaleY];
786 affine[kATransX] = this->fMat[kMTransX];
787 affine[kATransY] = this->fMat[kMTransY];
788 }
789 return true;
790 }
791
792 bool SkMatrix::invertNonIdentity(SkMatrix* inv) const {
793 SkASSERT(!this->isIdentity());
794
795 TypeMask mask = this->getType();
796
797 if (0 == (mask & ~(kScale_Mask | kTranslate_Mask))) {
798 bool invertible = true;
799 if (inv) {
800 if (mask & kScale_Mask) {
801 SkScalar invX = fMat[kMScaleX];
802 SkScalar invY = fMat[kMScaleY];
803 if (0 == invX || 0 == invY) {
804 return false;
805 }
806 invX = SkScalarInvert(invX);
807 invY = SkScalarInvert(invY);
808
809 // Must be careful when writing to inv, since it may be the
810 // same memory as this.
811
812 inv->fMat[kMSkewX] = inv->fMat[kMSkewY] =
813 inv->fMat[kMPersp0] = inv->fMat[kMPersp1] = 0;
814
815 inv->fMat[kMScaleX] = invX;
816 inv->fMat[kMScaleY] = invY;
817 inv->fMat[kMPersp2] = 1;
818 inv->fMat[kMTransX] = -fMat[kMTransX] * invX;
819 inv->fMat[kMTransY] = -fMat[kMTransY] * invY;
820
821 inv->setTypeMask(mask | kRectStaysRect_Mask);
822 } else {
823 // translate only
824 inv->setTranslate(-fMat[kMTransX], -fMat[kMTransY]);
825 }
826 } else { // inv is NULL, just check if we're invertible
827 if (!fMat[kMScaleX] || !fMat[kMScaleY]) {
828 invertible = false;
829 }
830 }
831 return invertible;
832 }
833
834 int isPersp = mask & kPerspective_Mask;
835 double scale = sk_inv_determinant(fMat, isPersp);
836
837 if (scale == 0) { // underflow
838 return false;
839 }
840
841 if (inv) {
842 SkMatrix tmp;
843 if (inv == this) {
844 inv = &tmp;
845 }
846
847 if (isPersp) {
848 inv->fMat[kMScaleX] = scross_dscale(fMat[kMScaleY], fMat[kMPersp2], fMat[kMTransY], fMat[kMPersp1], scale);
849 inv->fMat[kMSkewX] = scross_dscale(fMat[kMTransX], fMat[kMPersp1], fMat[kMSkewX], fMat[kMPersp2], scale);
850 inv->fMat[kMTransX] = scross_dscale(fMat[kMSkewX], fMat[kMTransY], fMat[kMTransX], fMat[kMScaleY], scale);
851
852 inv->fMat[kMSkewY] = scross_dscale(fMat[kMTransY], fMat[kMPersp0], fMat[kMSkewY], fMat[kMPersp2], scale);
853 inv->fMat[kMScaleY] = scross_dscale(fMat[kMScaleX], fMat[kMPersp2], fMat[kMTransX], fMat[kMPersp0], scale);
854 inv->fMat[kMTransY] = scross_dscale(fMat[kMTransX], fMat[kMSkewY], fMat[kMScaleX], fMat[kMTransY], scale);
855
856 inv->fMat[kMPersp0] = scross_dscale(fMat[kMSkewY], fMat[kMPersp1], fMat[kMScaleY], fMat[kMPersp0], scale);
857 inv->fMat[kMPersp1] = scross_dscale(fMat[kMSkewX], fMat[kMPersp0], fMat[kMScaleX], fMat[kMPersp1], scale);
858 inv->fMat[kMPersp2] = scross_dscale(fMat[kMScaleX], fMat[kMScaleY], fMat[kMSkewX], fMat[kMSkewY], scale);
859 } else { // not perspective
860 inv->fMat[kMScaleX] = SkDoubleToScalar(fMat[kMScaleY] * scale);
861 inv->fMat[kMSkewX] = SkDoubleToScalar(-fMat[kMSkewX] * scale);
862 inv->fMat[kMTransX] = dcross_dscale(fMat[kMSkewX], fMat[kMTransY], fMat[kMScaleY], fMat[kMTransX], scale);
863
864 inv->fMat[kMSkewY] = SkDoubleToScalar(-fMat[kMSkewY] * scale);
865 inv->fMat[kMScaleY] = SkDoubleToScalar(fMat[kMScaleX] * scale);
866 inv->fMat[kMTransY] = dcross_dscale(fMat[kMSkewY], fMat[kMTransX], fMat[kMScaleX], fMat[kMTransY], scale);
867
868 inv->fMat[kMPersp0] = 0;
869 inv->fMat[kMPersp1] = 0;
870 inv->fMat[kMPersp2] = 1;
871 }
872
873 inv->setTypeMask(fTypeMask);
874
875 if (inv == &tmp) {
876 *(SkMatrix*)this = tmp;
877 }
878 }
879 return true;
880 }
881
882 ///////////////////////////////////////////////////////////////////////////////
883
884 void SkMatrix::Identity_pts(const SkMatrix& m, SkPoint dst[],
885 const SkPoint src[], int count) {
886 SkASSERT(m.getType() == 0);
887
888 if (dst != src && count > 0)
889 memcpy(dst, src, count * sizeof(SkPoint));
890 }
891
892 void SkMatrix::Trans_pts(const SkMatrix& m, SkPoint dst[],
893 const SkPoint src[], int count) {
894 SkASSERT(m.getType() == kTranslate_Mask);
895
896 if (count > 0) {
897 SkScalar tx = m.fMat[kMTransX];
898 SkScalar ty = m.fMat[kMTransY];
899 do {
900 dst->fY = src->fY + ty;
901 dst->fX = src->fX + tx;
902 src += 1;
903 dst += 1;
904 } while (--count);
905 }
906 }
907
908 void SkMatrix::Scale_pts(const SkMatrix& m, SkPoint dst[],
909 const SkPoint src[], int count) {
910 SkASSERT(m.getType() == kScale_Mask);
911
912 if (count > 0) {
913 SkScalar mx = m.fMat[kMScaleX];
914 SkScalar my = m.fMat[kMScaleY];
915 do {
916 dst->fY = src->fY * my;
917 dst->fX = src->fX * mx;
918 src += 1;
919 dst += 1;
920 } while (--count);
921 }
922 }
923
924 void SkMatrix::ScaleTrans_pts(const SkMatrix& m, SkPoint dst[],
925 const SkPoint src[], int count) {
926 SkASSERT(m.getType() == (kScale_Mask | kTranslate_Mask));
927
928 if (count > 0) {
929 SkScalar mx = m.fMat[kMScaleX];
930 SkScalar my = m.fMat[kMScaleY];
931 SkScalar tx = m.fMat[kMTransX];
932 SkScalar ty = m.fMat[kMTransY];
933 do {
934 dst->fY = src->fY * my + ty;
935 dst->fX = src->fX * mx + tx;
936 src += 1;
937 dst += 1;
938 } while (--count);
939 }
940 }
941
942 void SkMatrix::Rot_pts(const SkMatrix& m, SkPoint dst[],
943 const SkPoint src[], int count) {
944 SkASSERT((m.getType() & (kPerspective_Mask | kTranslate_Mask)) == 0);
945
946 if (count > 0) {
947 SkScalar mx = m.fMat[kMScaleX];
948 SkScalar my = m.fMat[kMScaleY];
949 SkScalar kx = m.fMat[kMSkewX];
950 SkScalar ky = m.fMat[kMSkewY];
951 do {
952 SkScalar sy = src->fY;
953 SkScalar sx = src->fX;
954 src += 1;
955 dst->fY = sdot(sx, ky, sy, my);
956 dst->fX = sdot(sx, mx, sy, kx);
957 dst += 1;
958 } while (--count);
959 }
960 }
961
962 void SkMatrix::RotTrans_pts(const SkMatrix& m, SkPoint dst[],
963 const SkPoint src[], int count) {
964 SkASSERT(!m.hasPerspective());
965
966 if (count > 0) {
967 SkScalar mx = m.fMat[kMScaleX];
968 SkScalar my = m.fMat[kMScaleY];
969 SkScalar kx = m.fMat[kMSkewX];
970 SkScalar ky = m.fMat[kMSkewY];
971 SkScalar tx = m.fMat[kMTransX];
972 SkScalar ty = m.fMat[kMTransY];
973 do {
974 SkScalar sy = src->fY;
975 SkScalar sx = src->fX;
976 src += 1;
977 #ifdef SK_LEGACY_MATRIX_MATH_ORDER
978 dst->fY = sx * ky + (sy * my + ty);
979 dst->fX = sx * mx + (sy * kx + tx);
980 #else
981 dst->fY = sdot(sx, ky, sy, my) + ty;
982 dst->fX = sdot(sx, mx, sy, kx) + tx;
983 #endif
984 dst += 1;
985 } while (--count);
986 }
987 }
988
989 void SkMatrix::Persp_pts(const SkMatrix& m, SkPoint dst[],
990 const SkPoint src[], int count) {
991 SkASSERT(m.hasPerspective());
992
993 if (count > 0) {
994 do {
995 SkScalar sy = src->fY;
996 SkScalar sx = src->fX;
997 src += 1;
998
999 SkScalar x = sdot(sx, m.fMat[kMScaleX], sy, m.fMat[kMSkewX]) + m.fMat[kMTransX];
1000 SkScalar y = sdot(sx, m.fMat[kMSkewY], sy, m.fMat[kMScaleY]) + m.fMat[kMTransY];
1001 #ifdef SK_LEGACY_MATRIX_MATH_ORDER
1002 SkScalar z = sx * m.fMat[kMPersp0] + (sy * m.fMat[kMPersp1] + m.fMat[kMPersp2]);
1003 #else
1004 SkScalar z = sdot(sx, m.fMat[kMPersp0], sy, m.fMat[kMPersp1]) + m.fMat[kMPersp2];
1005 #endif
1006 if (z) {
1007 z = SkScalarFastInvert(z);
1008 }
1009
1010 dst->fY = y * z;
1011 dst->fX = x * z;
1012 dst += 1;
1013 } while (--count);
1014 }
1015 }
1016
1017 const SkMatrix::MapPtsProc SkMatrix::gMapPtsProcs[] = {
1018 SkMatrix::Identity_pts, SkMatrix::Trans_pts,
1019 SkMatrix::Scale_pts, SkMatrix::ScaleTrans_pts,
1020 SkMatrix::Rot_pts, SkMatrix::RotTrans_pts,
1021 SkMatrix::Rot_pts, SkMatrix::RotTrans_pts,
1022 // repeat the persp proc 8 times
1023 SkMatrix::Persp_pts, SkMatrix::Persp_pts,
1024 SkMatrix::Persp_pts, SkMatrix::Persp_pts,
1025 SkMatrix::Persp_pts, SkMatrix::Persp_pts,
1026 SkMatrix::Persp_pts, SkMatrix::Persp_pts
1027 };
1028
1029 void SkMatrix::mapPoints(SkPoint dst[], const SkPoint src[], int count) const {
1030 SkASSERT((dst && src && count > 0) || 0 == count);
1031 // no partial overlap
1032 SkASSERT(src == dst || &dst[count] <= &src[0] || &src[count] <= &dst[0]);
1033
1034 this->getMapPtsProc()(*this, dst, src, count);
1035 }
1036
1037 ///////////////////////////////////////////////////////////////////////////////
1038
1039 void SkMatrix::mapHomogeneousPoints(SkScalar dst[], const SkScalar src[], int count) const {
1040 SkASSERT((dst && src && count > 0) || 0 == count);
1041 // no partial overlap
1042 SkASSERT(src == dst || SkAbs32((int32_t)(src - dst)) >= 3*count);
1043
1044 if (count > 0) {
1045 if (this->isIdentity()) {
1046 memcpy(dst, src, 3*count*sizeof(SkScalar));
1047 return;
1048 }
1049 do {
1050 SkScalar sx = src[0];
1051 SkScalar sy = src[1];
1052 SkScalar sw = src[2];
1053 src += 3;
1054
1055 SkScalar x = sdot(sx, fMat[kMScaleX], sy, fMat[kMSkewX], sw, fMat[kMTransX]);
1056 SkScalar y = sdot(sx, fMat[kMSkewY], sy, fMat[kMScaleY], sw, fMat[kMTransY]);
1057 SkScalar w = sdot(sx, fMat[kMPersp0], sy, fMat[kMPersp1], sw, fMat[kMPersp2]);
1058
1059 dst[0] = x;
1060 dst[1] = y;
1061 dst[2] = w;
1062 dst += 3;
1063 } while (--count);
1064 }
1065 }
1066
1067 ///////////////////////////////////////////////////////////////////////////////
1068
1069 void SkMatrix::mapVectors(SkPoint dst[], const SkPoint src[], int count) const {
1070 if (this->hasPerspective()) {
1071 SkPoint origin;
1072
1073 MapXYProc proc = this->getMapXYProc();
1074 proc(*this, 0, 0, &origin);
1075
1076 for (int i = count - 1; i >= 0; --i) {
1077 SkPoint tmp;
1078
1079 proc(*this, src[i].fX, src[i].fY, &tmp);
1080 dst[i].set(tmp.fX - origin.fX, tmp.fY - origin.fY);
1081 }
1082 } else {
1083 SkMatrix tmp = *this;
1084
1085 tmp.fMat[kMTransX] = tmp.fMat[kMTransY] = 0;
1086 tmp.clearTypeMask(kTranslate_Mask);
1087 tmp.mapPoints(dst, src, count);
1088 }
1089 }
1090
1091 bool SkMatrix::mapRect(SkRect* dst, const SkRect& src) const {
1092 SkASSERT(dst && &src);
1093
1094 if (this->rectStaysRect()) {
1095 this->mapPoints((SkPoint*)dst, (const SkPoint*)&src, 2);
1096 dst->sort();
1097 return true;
1098 } else {
1099 SkPoint quad[4];
1100
1101 src.toQuad(quad);
1102 this->mapPoints(quad, quad, 4);
1103 dst->set(quad, 4);
1104 return false;
1105 }
1106 }
1107
1108 SkScalar SkMatrix::mapRadius(SkScalar radius) const {
1109 SkVector vec[2];
1110
1111 vec[0].set(radius, 0);
1112 vec[1].set(0, radius);
1113 this->mapVectors(vec, 2);
1114
1115 SkScalar d0 = vec[0].length();
1116 SkScalar d1 = vec[1].length();
1117
1118 // return geometric mean
1119 return SkScalarSqrt(d0 * d1);
1120 }
1121
1122 ///////////////////////////////////////////////////////////////////////////////
1123
1124 void SkMatrix::Persp_xy(const SkMatrix& m, SkScalar sx, SkScalar sy,
1125 SkPoint* pt) {
1126 SkASSERT(m.hasPerspective());
1127
1128 SkScalar x = sdot(sx, m.fMat[kMScaleX], sy, m.fMat[kMSkewX]) + m.fMat[kMTransX];
1129 SkScalar y = sdot(sx, m.fMat[kMSkewY], sy, m.fMat[kMScaleY]) + m.fMat[kMTransY];
1130 SkScalar z = sdot(sx, m.fMat[kMPersp0], sy, m.fMat[kMPersp1]) + m.fMat[kMPersp2];
1131 if (z) {
1132 z = SkScalarFastInvert(z);
1133 }
1134 pt->fX = x * z;
1135 pt->fY = y * z;
1136 }
1137
1138 void SkMatrix::RotTrans_xy(const SkMatrix& m, SkScalar sx, SkScalar sy,
1139 SkPoint* pt) {
1140 SkASSERT((m.getType() & (kAffine_Mask | kPerspective_Mask)) == kAffine_Mask);
1141
1142 #ifdef SK_LEGACY_MATRIX_MATH_ORDER
1143 pt->fX = sx * m.fMat[kMScaleX] + (sy * m.fMat[kMSkewX] + m.fMat[kMTransX]);
1144 pt->fY = sx * m.fMat[kMSkewY] + (sy * m.fMat[kMScaleY] + m.fMat[kMTransY]);
1145 #else
1146 pt->fX = sdot(sx, m.fMat[kMScaleX], sy, m.fMat[kMSkewX]) + m.fMat[kMTransX];
1147 pt->fY = sdot(sx, m.fMat[kMSkewY], sy, m.fMat[kMScaleY]) + m.fMat[kMTransY];
1148 #endif
1149 }
1150
1151 void SkMatrix::Rot_xy(const SkMatrix& m, SkScalar sx, SkScalar sy,
1152 SkPoint* pt) {
1153 SkASSERT((m.getType() & (kAffine_Mask | kPerspective_Mask))== kAffine_Mask);
1154 SkASSERT(0 == m.fMat[kMTransX]);
1155 SkASSERT(0 == m.fMat[kMTransY]);
1156
1157 #ifdef SK_LEGACY_MATRIX_MATH_ORDER
1158 pt->fX = sx * m.fMat[kMScaleX] + (sy * m.fMat[kMSkewX] + m.fMat[kMTransX]);
1159 pt->fY = sx * m.fMat[kMSkewY] + (sy * m.fMat[kMScaleY] + m.fMat[kMTransY]);
1160 #else
1161 pt->fX = sdot(sx, m.fMat[kMScaleX], sy, m.fMat[kMSkewX]) + m.fMat[kMTransX];
1162 pt->fY = sdot(sx, m.fMat[kMSkewY], sy, m.fMat[kMScaleY]) + m.fMat[kMTransY];
1163 #endif
1164 }
1165
1166 void SkMatrix::ScaleTrans_xy(const SkMatrix& m, SkScalar sx, SkScalar sy,
1167 SkPoint* pt) {
1168 SkASSERT((m.getType() & (kScale_Mask | kAffine_Mask | kPerspective_Mask))
1169 == kScale_Mask);
1170
1171 pt->fX = sx * m.fMat[kMScaleX] + m.fMat[kMTransX];
1172 pt->fY = sy * m.fMat[kMScaleY] + m.fMat[kMTransY];
1173 }
1174
1175 void SkMatrix::Scale_xy(const SkMatrix& m, SkScalar sx, SkScalar sy,
1176 SkPoint* pt) {
1177 SkASSERT((m.getType() & (kScale_Mask | kAffine_Mask | kPerspective_Mask))
1178 == kScale_Mask);
1179 SkASSERT(0 == m.fMat[kMTransX]);
1180 SkASSERT(0 == m.fMat[kMTransY]);
1181
1182 pt->fX = sx * m.fMat[kMScaleX];
1183 pt->fY = sy * m.fMat[kMScaleY];
1184 }
1185
1186 void SkMatrix::Trans_xy(const SkMatrix& m, SkScalar sx, SkScalar sy,
1187 SkPoint* pt) {
1188 SkASSERT(m.getType() == kTranslate_Mask);
1189
1190 pt->fX = sx + m.fMat[kMTransX];
1191 pt->fY = sy + m.fMat[kMTransY];
1192 }
1193
1194 void SkMatrix::Identity_xy(const SkMatrix& m, SkScalar sx, SkScalar sy,
1195 SkPoint* pt) {
1196 SkASSERT(0 == m.getType());
1197
1198 pt->fX = sx;
1199 pt->fY = sy;
1200 }
1201
1202 const SkMatrix::MapXYProc SkMatrix::gMapXYProcs[] = {
1203 SkMatrix::Identity_xy, SkMatrix::Trans_xy,
1204 SkMatrix::Scale_xy, SkMatrix::ScaleTrans_xy,
1205 SkMatrix::Rot_xy, SkMatrix::RotTrans_xy,
1206 SkMatrix::Rot_xy, SkMatrix::RotTrans_xy,
1207 // repeat the persp proc 8 times
1208 SkMatrix::Persp_xy, SkMatrix::Persp_xy,
1209 SkMatrix::Persp_xy, SkMatrix::Persp_xy,
1210 SkMatrix::Persp_xy, SkMatrix::Persp_xy,
1211 SkMatrix::Persp_xy, SkMatrix::Persp_xy
1212 };
1213
1214 ///////////////////////////////////////////////////////////////////////////////
1215
1216 // if its nearly zero (just made up 26, perhaps it should be bigger or smaller)
1217 #define PerspNearlyZero(x) SkScalarNearlyZero(x, (1.0f / (1 << 26)))
1218
1219 bool SkMatrix::fixedStepInX(SkScalar y, SkFixed* stepX, SkFixed* stepY) const {
1220 if (PerspNearlyZero(fMat[kMPersp0])) {
1221 if (stepX || stepY) {
1222 if (PerspNearlyZero(fMat[kMPersp1]) &&
1223 PerspNearlyZero(fMat[kMPersp2] - 1)) {
1224 if (stepX) {
1225 *stepX = SkScalarToFixed(fMat[kMScaleX]);
1226 }
1227 if (stepY) {
1228 *stepY = SkScalarToFixed(fMat[kMSkewY]);
1229 }
1230 } else {
1231 SkScalar z = y * fMat[kMPersp1] + fMat[kMPersp2];
1232 if (stepX) {
1233 *stepX = SkScalarToFixed(fMat[kMScaleX] / z);
1234 }
1235 if (stepY) {
1236 *stepY = SkScalarToFixed(fMat[kMSkewY] / z);
1237 }
1238 }
1239 }
1240 return true;
1241 }
1242 return false;
1243 }
1244
1245 ///////////////////////////////////////////////////////////////////////////////
1246
1247 #include "SkPerspIter.h"
1248
1249 SkPerspIter::SkPerspIter(const SkMatrix& m, SkScalar x0, SkScalar y0, int count)
1250 : fMatrix(m), fSX(x0), fSY(y0), fCount(count) {
1251 SkPoint pt;
1252
1253 SkMatrix::Persp_xy(m, x0, y0, &pt);
1254 fX = SkScalarToFixed(pt.fX);
1255 fY = SkScalarToFixed(pt.fY);
1256 }
1257
1258 int SkPerspIter::next() {
1259 int n = fCount;
1260
1261 if (0 == n) {
1262 return 0;
1263 }
1264 SkPoint pt;
1265 SkFixed x = fX;
1266 SkFixed y = fY;
1267 SkFixed dx, dy;
1268
1269 if (n >= kCount) {
1270 n = kCount;
1271 fSX += SkIntToScalar(kCount);
1272 SkMatrix::Persp_xy(fMatrix, fSX, fSY, &pt);
1273 fX = SkScalarToFixed(pt.fX);
1274 fY = SkScalarToFixed(pt.fY);
1275 dx = (fX - x) >> kShift;
1276 dy = (fY - y) >> kShift;
1277 } else {
1278 fSX += SkIntToScalar(n);
1279 SkMatrix::Persp_xy(fMatrix, fSX, fSY, &pt);
1280 fX = SkScalarToFixed(pt.fX);
1281 fY = SkScalarToFixed(pt.fY);
1282 dx = (fX - x) / n;
1283 dy = (fY - y) / n;
1284 }
1285
1286 SkFixed* p = fStorage;
1287 for (int i = 0; i < n; i++) {
1288 *p++ = x; x += dx;
1289 *p++ = y; y += dy;
1290 }
1291
1292 fCount -= n;
1293 return n;
1294 }
1295
1296 ///////////////////////////////////////////////////////////////////////////////
1297
1298 static inline bool checkForZero(float x) {
1299 return x*x == 0;
1300 }
1301
1302 static inline bool poly_to_point(SkPoint* pt, const SkPoint poly[], int count) {
1303 float x = 1, y = 1;
1304 SkPoint pt1, pt2;
1305
1306 if (count > 1) {
1307 pt1.fX = poly[1].fX - poly[0].fX;
1308 pt1.fY = poly[1].fY - poly[0].fY;
1309 y = SkPoint::Length(pt1.fX, pt1.fY);
1310 if (checkForZero(y)) {
1311 return false;
1312 }
1313 switch (count) {
1314 case 2:
1315 break;
1316 case 3:
1317 pt2.fX = poly[0].fY - poly[2].fY;
1318 pt2.fY = poly[2].fX - poly[0].fX;
1319 goto CALC_X;
1320 default:
1321 pt2.fX = poly[0].fY - poly[3].fY;
1322 pt2.fY = poly[3].fX - poly[0].fX;
1323 CALC_X:
1324 x = sdot(pt1.fX, pt2.fX, pt1.fY, pt2.fY) / y;
1325 break;
1326 }
1327 }
1328 pt->set(x, y);
1329 return true;
1330 }
1331
1332 bool SkMatrix::Poly2Proc(const SkPoint srcPt[], SkMatrix* dst,
1333 const SkPoint& scale) {
1334 float invScale = 1 / scale.fY;
1335
1336 dst->fMat[kMScaleX] = (srcPt[1].fY - srcPt[0].fY) * invScale;
1337 dst->fMat[kMSkewY] = (srcPt[0].fX - srcPt[1].fX) * invScale;
1338 dst->fMat[kMPersp0] = 0;
1339 dst->fMat[kMSkewX] = (srcPt[1].fX - srcPt[0].fX) * invScale;
1340 dst->fMat[kMScaleY] = (srcPt[1].fY - srcPt[0].fY) * invScale;
1341 dst->fMat[kMPersp1] = 0;
1342 dst->fMat[kMTransX] = srcPt[0].fX;
1343 dst->fMat[kMTransY] = srcPt[0].fY;
1344 dst->fMat[kMPersp2] = 1;
1345 dst->setTypeMask(kUnknown_Mask);
1346 return true;
1347 }
1348
1349 bool SkMatrix::Poly3Proc(const SkPoint srcPt[], SkMatrix* dst,
1350 const SkPoint& scale) {
1351 float invScale = 1 / scale.fX;
1352 dst->fMat[kMScaleX] = (srcPt[2].fX - srcPt[0].fX) * invScale;
1353 dst->fMat[kMSkewY] = (srcPt[2].fY - srcPt[0].fY) * invScale;
1354 dst->fMat[kMPersp0] = 0;
1355
1356 invScale = 1 / scale.fY;
1357 dst->fMat[kMSkewX] = (srcPt[1].fX - srcPt[0].fX) * invScale;
1358 dst->fMat[kMScaleY] = (srcPt[1].fY - srcPt[0].fY) * invScale;
1359 dst->fMat[kMPersp1] = 0;
1360
1361 dst->fMat[kMTransX] = srcPt[0].fX;
1362 dst->fMat[kMTransY] = srcPt[0].fY;
1363 dst->fMat[kMPersp2] = 1;
1364 dst->setTypeMask(kUnknown_Mask);
1365 return true;
1366 }
1367
1368 bool SkMatrix::Poly4Proc(const SkPoint srcPt[], SkMatrix* dst,
1369 const SkPoint& scale) {
1370 float a1, a2;
1371 float x0, y0, x1, y1, x2, y2;
1372
1373 x0 = srcPt[2].fX - srcPt[0].fX;
1374 y0 = srcPt[2].fY - srcPt[0].fY;
1375 x1 = srcPt[2].fX - srcPt[1].fX;
1376 y1 = srcPt[2].fY - srcPt[1].fY;
1377 x2 = srcPt[2].fX - srcPt[3].fX;
1378 y2 = srcPt[2].fY - srcPt[3].fY;
1379
1380 /* check if abs(x2) > abs(y2) */
1381 if ( x2 > 0 ? y2 > 0 ? x2 > y2 : x2 > -y2 : y2 > 0 ? -x2 > y2 : x2 < y2) {
1382 float denom = SkScalarMulDiv(x1, y2, x2) - y1;
1383 if (checkForZero(denom)) {
1384 return false;
1385 }
1386 a1 = (SkScalarMulDiv(x0 - x1, y2, x2) - y0 + y1) / denom;
1387 } else {
1388 float denom = x1 - SkScalarMulDiv(y1, x2, y2);
1389 if (checkForZero(denom)) {
1390 return false;
1391 }
1392 a1 = (x0 - x1 - SkScalarMulDiv(y0 - y1, x2, y2)) / denom;
1393 }
1394
1395 /* check if abs(x1) > abs(y1) */
1396 if ( x1 > 0 ? y1 > 0 ? x1 > y1 : x1 > -y1 : y1 > 0 ? -x1 > y1 : x1 < y1) {
1397 float denom = y2 - SkScalarMulDiv(x2, y1, x1);
1398 if (checkForZero(denom)) {
1399 return false;
1400 }
1401 a2 = (y0 - y2 - SkScalarMulDiv(x0 - x2, y1, x1)) / denom;
1402 } else {
1403 float denom = SkScalarMulDiv(y2, x1, y1) - x2;
1404 if (checkForZero(denom)) {
1405 return false;
1406 }
1407 a2 = (SkScalarMulDiv(y0 - y2, x1, y1) - x0 + x2) / denom;
1408 }
1409
1410 float invScale = SkScalarInvert(scale.fX);
1411 dst->fMat[kMScaleX] = (a2 * srcPt[3].fX + srcPt[3].fX - srcPt[0].fX) * invScale;
1412 dst->fMat[kMSkewY] = (a2 * srcPt[3].fY + srcPt[3].fY - srcPt[0].fY) * invScale;
1413 dst->fMat[kMPersp0] = a2 * invScale;
1414
1415 invScale = SkScalarInvert(scale.fY);
1416 dst->fMat[kMSkewX] = (a1 * srcPt[1].fX + srcPt[1].fX - srcPt[0].fX) * invScale;
1417 dst->fMat[kMScaleY] = (a1 * srcPt[1].fY + srcPt[1].fY - srcPt[0].fY) * invScale;
1418 dst->fMat[kMPersp1] = a1 * invScale;
1419
1420 dst->fMat[kMTransX] = srcPt[0].fX;
1421 dst->fMat[kMTransY] = srcPt[0].fY;
1422 dst->fMat[kMPersp2] = 1;
1423 dst->setTypeMask(kUnknown_Mask);
1424 return true;
1425 }
1426
1427 typedef bool (*PolyMapProc)(const SkPoint[], SkMatrix*, const SkPoint&);
1428
1429 /* Taken from Rob Johnson's original sample code in QuickDraw GX
1430 */
1431 bool SkMatrix::setPolyToPoly(const SkPoint src[], const SkPoint dst[],
1432 int count) {
1433 if ((unsigned)count > 4) {
1434 SkDebugf("--- SkMatrix::setPolyToPoly count out of range %d\n", count);
1435 return false;
1436 }
1437
1438 if (0 == count) {
1439 this->reset();
1440 return true;
1441 }
1442 if (1 == count) {
1443 this->setTranslate(dst[0].fX - src[0].fX, dst[0].fY - src[0].fY);
1444 return true;
1445 }
1446
1447 SkPoint scale;
1448 if (!poly_to_point(&scale, src, count) ||
1449 SkScalarNearlyZero(scale.fX) ||
1450 SkScalarNearlyZero(scale.fY)) {
1451 return false;
1452 }
1453
1454 static const PolyMapProc gPolyMapProcs[] = {
1455 SkMatrix::Poly2Proc, SkMatrix::Poly3Proc, SkMatrix::Poly4Proc
1456 };
1457 PolyMapProc proc = gPolyMapProcs[count - 2];
1458
1459 SkMatrix tempMap, result;
1460 tempMap.setTypeMask(kUnknown_Mask);
1461
1462 if (!proc(src, &tempMap, scale)) {
1463 return false;
1464 }
1465 if (!tempMap.invert(&result)) {
1466 return false;
1467 }
1468 if (!proc(dst, &tempMap, scale)) {
1469 return false;
1470 }
1471 if (!result.setConcat(tempMap, result)) {
1472 return false;
1473 }
1474 *this = result;
1475 return true;
1476 }
1477
1478 ///////////////////////////////////////////////////////////////////////////////
1479
1480 enum MinOrMax {
1481 kMin_MinOrMax,
1482 kMax_MinOrMax
1483 };
1484
1485 template <MinOrMax MIN_OR_MAX> SkScalar get_stretch_factor(SkMatrix::TypeMask typeMask,
1486 const SkScalar m[9]) {
1487 if (typeMask & SkMatrix::kPerspective_Mask) {
1488 return -1;
1489 }
1490 if (SkMatrix::kIdentity_Mask == typeMask) {
1491 return 1;
1492 }
1493 if (!(typeMask & SkMatrix::kAffine_Mask)) {
1494 if (kMin_MinOrMax == MIN_OR_MAX) {
1495 return SkMinScalar(SkScalarAbs(m[SkMatrix::kMScaleX]),
1496 SkScalarAbs(m[SkMatrix::kMScaleY]));
1497 } else {
1498 return SkMaxScalar(SkScalarAbs(m[SkMatrix::kMScaleX]),
1499 SkScalarAbs(m[SkMatrix::kMScaleY]));
1500 }
1501 }
1502 // ignore the translation part of the matrix, just look at 2x2 portion.
1503 // compute singular values, take largest or smallest abs value.
1504 // [a b; b c] = A^T*A
1505 SkScalar a = sdot(m[SkMatrix::kMScaleX], m[SkMatrix::kMScaleX],
1506 m[SkMatrix::kMSkewY], m[SkMatrix::kMSkewY]);
1507 SkScalar b = sdot(m[SkMatrix::kMScaleX], m[SkMatrix::kMSkewX],
1508 m[SkMatrix::kMScaleY], m[SkMatrix::kMSkewY]);
1509 SkScalar c = sdot(m[SkMatrix::kMSkewX], m[SkMatrix::kMSkewX],
1510 m[SkMatrix::kMScaleY], m[SkMatrix::kMScaleY]);
1511 // eigenvalues of A^T*A are the squared singular values of A.
1512 // characteristic equation is det((A^T*A) - l*I) = 0
1513 // l^2 - (a + c)l + (ac-b^2)
1514 // solve using quadratic equation (divisor is non-zero since l^2 has 1 coeff
1515 // and roots are guaranteed to be pos and real).
1516 SkScalar chosenRoot;
1517 SkScalar bSqd = b * b;
1518 // if upper left 2x2 is orthogonal save some math
1519 if (bSqd <= SK_ScalarNearlyZero*SK_ScalarNearlyZero) {
1520 if (kMin_MinOrMax == MIN_OR_MAX) {
1521 chosenRoot = SkMinScalar(a, c);
1522 } else {
1523 chosenRoot = SkMaxScalar(a, c);
1524 }
1525 } else {
1526 SkScalar aminusc = a - c;
1527 SkScalar apluscdiv2 = SkScalarHalf(a + c);
1528 SkScalar x = SkScalarHalf(SkScalarSqrt(aminusc * aminusc + 4 * bSqd));
1529 if (kMin_MinOrMax == MIN_OR_MAX) {
1530 chosenRoot = apluscdiv2 - x;
1531 } else {
1532 chosenRoot = apluscdiv2 + x;
1533 }
1534 }
1535 SkASSERT(chosenRoot >= 0);
1536 return SkScalarSqrt(chosenRoot);
1537 }
1538
1539 SkScalar SkMatrix::getMinStretch() const {
1540 return get_stretch_factor<kMin_MinOrMax>(this->getType(), fMat);
1541 }
1542
1543 SkScalar SkMatrix::getMaxStretch() const {
1544 return get_stretch_factor<kMax_MinOrMax>(this->getType(), fMat);
1545 }
1546
1547 static void reset_identity_matrix(SkMatrix* identity) {
1548 identity->reset();
1549 }
1550
1551 const SkMatrix& SkMatrix::I() {
1552 // If you can use C++11 now, you might consider replacing this with a constexpr constructor.
1553 static SkMatrix gIdentity;
1554 SK_DECLARE_STATIC_ONCE(once);
1555 SkOnce(&once, reset_identity_matrix, &gIdentity);
1556 return gIdentity;
1557 }
1558
1559 const SkMatrix& SkMatrix::InvalidMatrix() {
1560 static SkMatrix gInvalid;
1561 static bool gOnce;
1562 if (!gOnce) {
1563 gInvalid.setAll(SK_ScalarMax, SK_ScalarMax, SK_ScalarMax,
1564 SK_ScalarMax, SK_ScalarMax, SK_ScalarMax,
1565 SK_ScalarMax, SK_ScalarMax, SK_ScalarMax);
1566 gInvalid.getType(); // force the type to be computed
1567 gOnce = true;
1568 }
1569 return gInvalid;
1570 }
1571
1572 ///////////////////////////////////////////////////////////////////////////////
1573
1574 size_t SkMatrix::writeToMemory(void* buffer) const {
1575 // TODO write less for simple matrices
1576 static const size_t sizeInMemory = 9 * sizeof(SkScalar);
1577 if (buffer) {
1578 memcpy(buffer, fMat, sizeInMemory);
1579 }
1580 return sizeInMemory;
1581 }
1582
1583 size_t SkMatrix::readFromMemory(const void* buffer, size_t length) {
1584 static const size_t sizeInMemory = 9 * sizeof(SkScalar);
1585 if (length < sizeInMemory) {
1586 return 0;
1587 }
1588 if (buffer) {
1589 memcpy(fMat, buffer, sizeInMemory);
1590 this->setTypeMask(kUnknown_Mask);
1591 }
1592 return sizeInMemory;
1593 }
1594
1595 #ifdef SK_DEVELOPER
1596 void SkMatrix::dump() const {
1597 SkString str;
1598 this->toString(&str);
1599 SkDebugf("%s\n", str.c_str());
1600 }
1601 #endif
1602
1603 #ifndef SK_IGNORE_TO_STRING
1604 void SkMatrix::toString(SkString* str) const {
1605 str->appendf("[%8.4f %8.4f %8.4f][%8.4f %8.4f %8.4f][%8.4f %8.4f %8.4f]",
1606 fMat[0], fMat[1], fMat[2], fMat[3], fMat[4], fMat[5],
1607 fMat[6], fMat[7], fMat[8]);
1608 }
1609 #endif
1610
1611 ///////////////////////////////////////////////////////////////////////////////
1612
1613 #include "SkMatrixUtils.h"
1614
1615 bool SkTreatAsSprite(const SkMatrix& mat, int width, int height,
1616 unsigned subpixelBits) {
1617 // quick reject on affine or perspective
1618 if (mat.getType() & ~(SkMatrix::kScale_Mask | SkMatrix::kTranslate_Mask)) {
1619 return false;
1620 }
1621
1622 // quick success check
1623 if (!subpixelBits && !(mat.getType() & ~SkMatrix::kTranslate_Mask)) {
1624 return true;
1625 }
1626
1627 // mapRect supports negative scales, so we eliminate those first
1628 if (mat.getScaleX() < 0 || mat.getScaleY() < 0) {
1629 return false;
1630 }
1631
1632 SkRect dst;
1633 SkIRect isrc = { 0, 0, width, height };
1634
1635 {
1636 SkRect src;
1637 src.set(isrc);
1638 mat.mapRect(&dst, src);
1639 }
1640
1641 // just apply the translate to isrc
1642 isrc.offset(SkScalarRoundToInt(mat.getTranslateX()),
1643 SkScalarRoundToInt(mat.getTranslateY()));
1644
1645 if (subpixelBits) {
1646 isrc.fLeft <<= subpixelBits;
1647 isrc.fTop <<= subpixelBits;
1648 isrc.fRight <<= subpixelBits;
1649 isrc.fBottom <<= subpixelBits;
1650
1651 const float scale = 1 << subpixelBits;
1652 dst.fLeft *= scale;
1653 dst.fTop *= scale;
1654 dst.fRight *= scale;
1655 dst.fBottom *= scale;
1656 }
1657
1658 SkIRect idst;
1659 dst.round(&idst);
1660 return isrc == idst;
1661 }
1662
1663 // A square matrix M can be decomposed (via polar decomposition) into two matrices --
1664 // an orthogonal matrix Q and a symmetric matrix S. In turn we can decompose S into U*W*U^T,
1665 // where U is another orthogonal matrix and W is a scale matrix. These can be recombined
1666 // to give M = (Q*U)*W*U^T, i.e., the product of two orthogonal matrices and a scale matrix.
1667 //
1668 // The one wrinkle is that traditionally Q may contain a reflection -- the
1669 // calculation has been rejiggered to put that reflection into W.
1670 bool SkDecomposeUpper2x2(const SkMatrix& matrix,
1671 SkPoint* rotation1,
1672 SkPoint* scale,
1673 SkPoint* rotation2) {
1674
1675 SkScalar A = matrix[SkMatrix::kMScaleX];
1676 SkScalar B = matrix[SkMatrix::kMSkewX];
1677 SkScalar C = matrix[SkMatrix::kMSkewY];
1678 SkScalar D = matrix[SkMatrix::kMScaleY];
1679
1680 if (is_degenerate_2x2(A, B, C, D)) {
1681 return false;
1682 }
1683
1684 double w1, w2;
1685 SkScalar cos1, sin1;
1686 SkScalar cos2, sin2;
1687
1688 // do polar decomposition (M = Q*S)
1689 SkScalar cosQ, sinQ;
1690 double Sa, Sb, Sd;
1691 // if M is already symmetric (i.e., M = I*S)
1692 if (SkScalarNearlyEqual(B, C)) {
1693 cosQ = 1;
1694 sinQ = 0;
1695
1696 Sa = A;
1697 Sb = B;
1698 Sd = D;
1699 } else {
1700 cosQ = A + D;
1701 sinQ = C - B;
1702 SkScalar reciplen = SkScalarInvert(SkScalarSqrt(cosQ*cosQ + sinQ*sinQ));
1703 cosQ *= reciplen;
1704 sinQ *= reciplen;
1705
1706 // S = Q^-1*M
1707 // we don't calc Sc since it's symmetric
1708 Sa = A*cosQ + C*sinQ;
1709 Sb = B*cosQ + D*sinQ;
1710 Sd = -B*sinQ + D*cosQ;
1711 }
1712
1713 // Now we need to compute eigenvalues of S (our scale factors)
1714 // and eigenvectors (bases for our rotation)
1715 // From this, should be able to reconstruct S as U*W*U^T
1716 if (SkScalarNearlyZero(SkDoubleToScalar(Sb))) {
1717 // already diagonalized
1718 cos1 = 1;
1719 sin1 = 0;
1720 w1 = Sa;
1721 w2 = Sd;
1722 cos2 = cosQ;
1723 sin2 = sinQ;
1724 } else {
1725 double diff = Sa - Sd;
1726 double discriminant = sqrt(diff*diff + 4.0*Sb*Sb);
1727 double trace = Sa + Sd;
1728 if (diff > 0) {
1729 w1 = 0.5*(trace + discriminant);
1730 w2 = 0.5*(trace - discriminant);
1731 } else {
1732 w1 = 0.5*(trace - discriminant);
1733 w2 = 0.5*(trace + discriminant);
1734 }
1735
1736 cos1 = SkDoubleToScalar(Sb); sin1 = SkDoubleToScalar(w1 - Sa);
1737 SkScalar reciplen = SkScalarInvert(SkScalarSqrt(cos1*cos1 + sin1*sin1));
1738 cos1 *= reciplen;
1739 sin1 *= reciplen;
1740
1741 // rotation 2 is composition of Q and U
1742 cos2 = cos1*cosQ - sin1*sinQ;
1743 sin2 = sin1*cosQ + cos1*sinQ;
1744
1745 // rotation 1 is U^T
1746 sin1 = -sin1;
1747 }
1748
1749 if (NULL != scale) {
1750 scale->fX = SkDoubleToScalar(w1);
1751 scale->fY = SkDoubleToScalar(w2);
1752 }
1753 if (NULL != rotation1) {
1754 rotation1->fX = cos1;
1755 rotation1->fY = sin1;
1756 }
1757 if (NULL != rotation2) {
1758 rotation2->fX = cos2;
1759 rotation2->fY = sin2;
1760 }
1761
1762 return true;
1763 }

Mercurial Repository: The Tor Browser

Europalab SCM Repository Server

mercurial