OLD | NEW |
---|---|
1 /* | 1 /* |
2 * Copyright 2011 Google Inc. | 2 * Copyright 2011 Google Inc. |
3 * | 3 * |
4 * Use of this source code is governed by a BSD-style license that can be | 4 * Use of this source code is governed by a BSD-style license that can be |
5 * found in the LICENSE file. | 5 * found in the LICENSE file. |
6 */ | 6 */ |
7 | 7 |
8 #include "GrPathUtils.h" | 8 #include "GrPathUtils.h" |
9 | 9 |
10 #include "GrPoint.h" | 10 #include "GrPoint.h" |
(...skipping 458 matching lines...) Expand 10 before | Expand all | Expand 10 after Loading... | |
469 // base tolerance is 1 pixel. | 469 // base tolerance is 1 pixel. |
470 static const SkScalar kTolerance = SK_Scalar1; | 470 static const SkScalar kTolerance = SK_Scalar1; |
471 const SkScalar tolSqd = SkScalarSquare(SkScalarMul(tolScale, kTolerance)); | 471 const SkScalar tolSqd = SkScalarSquare(SkScalarMul(tolScale, kTolerance)); |
472 | 472 |
473 for (int i = 0; i < count; ++i) { | 473 for (int i = 0; i < count; ++i) { |
474 SkPoint* cubic = chopped + 3*i; | 474 SkPoint* cubic = chopped + 3*i; |
475 convert_noninflect_cubic_to_quads(cubic, tolSqd, constrainWithinTangents , dir, quads); | 475 convert_noninflect_cubic_to_quads(cubic, tolSqd, constrainWithinTangents , dir, quads); |
476 } | 476 } |
477 | 477 |
478 } | 478 } |
479 | |
480 //////////////////////////////////////////////////////////////////////////////// | |
481 | |
482 enum CubicType { | |
bsalomon
2013/08/16 17:47:00
style nit:
kSerpentine_CubicType,
kCusp_CubicType
| |
483 kSerpentine, | |
484 kCusp, | |
485 kLoop, | |
486 kQuadratic, | |
487 kCubicLine, | |
488 kCubicPoint | |
489 }; | |
490 | |
491 // discr(I) = d0^2 * (3*d1^2 - 4*d0*d2) | |
492 // Classification: | |
493 // discr(I) > 0 Serpentine | |
494 // discr(I) = 0 Cusp | |
495 // discr(I) < 0 Loop | |
496 // d0 = d1 = 0 Quadratic | |
497 // d0 = d1 = d2 = 0 Line | |
498 // p0 = p1 = p2 = p3 Point | |
499 static CubicType classify_cubic(const SkPoint p[4], const SkScalar d[3]) { | |
500 if (p[0] == p[1] && p[0] == p[2] && p[0] == p[3]) { | |
501 return kCubicPoint; | |
502 } | |
503 const SkScalar discr = d[0] * d[0] * (3.f * d[1] * d[1] - 4.f * d[0] * d[2]) ; | |
504 if (discr > 0.f) { | |
505 return kSerpentine; | |
506 } else if (discr < 0.f) { | |
507 return kLoop; | |
bsalomon
2013/08/16 17:47:00
indent
| |
508 } else { | |
509 if (0.f == d[0] && 0.f == d[1]) { | |
510 return (0.f == d[2] ? kCubicLine : kQuadratic); | |
511 } else { | |
512 return kCusp; | |
513 } | |
514 } | |
515 } | |
516 | |
517 // Assumes the third component of points is 1. | |
518 // Calcs p0 . (p1 x p2) | |
519 static SkScalar calc_dot_cross_cubic(const SkPoint& p0, const SkPoint& p1, const SkPoint& p2) { | |
520 const SkScalar xComp = p0.fX * (p1.fY - p2.fY); | |
521 const SkScalar yComp = p0.fY * (p2.fX - p1.fX); | |
522 const SkScalar wComp = p1.fX * p2.fY - p1.fY * p2.fX; | |
523 return (xComp + yComp + wComp); | |
524 } | |
525 | |
526 // Solves linear system to extract klm | |
527 // P.K = k (similarly for l, m) | |
528 // Where P is matrix of control points | |
529 // K is coefficients for the line K | |
530 // k is vector of values of K evaluated at the control points | |
531 // Solving for K, thus K = P^(-1) . k | |
532 static void calc_cubic_klm(const SkPoint p[4], const SkScalar controlK[4], | |
533 const SkScalar controlL[4], const SkScalar controlM[4 ], | |
534 SkScalar k[3], SkScalar l[3], SkScalar m[3]) { | |
535 SkMatrix matrix; | |
536 matrix.setAll(p[0].fX, p[0].fY, 1.f, | |
537 p[1].fX, p[1].fY, 1.f, | |
538 p[2].fX, p[2].fY, 1.f); | |
539 SkMatrix inverse; | |
540 if (matrix.invert(&inverse)) { | |
541 inverse.mapHomogeneousPoints(k, controlK, 1); | |
542 inverse.mapHomogeneousPoints(l, controlL, 1); | |
543 inverse.mapHomogeneousPoints(m, controlM, 1); | |
544 } | |
545 | |
546 } | |
547 | |
548 static void set_serp_klm(const SkScalar d[3], SkScalar k[4], SkScalar l[4], SkSc alar m[4]) { | |
549 SkScalar tempSqrt = SkScalarSqrt(9.f * d[1] * d[1] - 12.f * d[0] * d[2]); | |
550 SkScalar ls = 3.f * d[1] - tempSqrt; | |
551 SkScalar lt = 6.f * d[0]; | |
552 SkScalar ms = 3.f * d[1] + tempSqrt; | |
553 SkScalar mt = 6.f * d[0]; | |
554 | |
555 k[0] = ls * ms; | |
556 k[1] = (3.f * ls * ms - ls * mt - lt * ms) / 3.f; | |
557 k[2] = (lt * (mt - 2.f * ms) + ls * (3.f * ms - 2.f * mt)) / 3.f; | |
558 k[3] = (lt - ls) * (mt - ms); | |
559 | |
560 l[0] = ls * ls * ls; | |
561 const SkScalar lt_ls = lt - ls; | |
562 l[1] = ls * ls * lt_ls * -1.f; | |
563 l[2] = lt_ls * lt_ls * ls; | |
564 l[3] = -1.f * lt_ls * lt_ls * lt_ls; | |
565 | |
566 m[0] = ms * ms * ms; | |
567 const SkScalar mt_ms = mt - ms; | |
568 m[1] = ms * ms * mt_ms * -1.f; | |
569 m[2] = mt_ms * mt_ms * ms; | |
570 m[3] = -1.ff * mt_ms * mt_ms * mt_ms; | |
571 | |
572 // If d0 < 0 we need to flip the orientation of our curve | |
573 // This is done by negating the k and l values | |
574 // We want negative distance values to be on the inside | |
575 if ( d[0] > 0) { | |
576 for (int i = 0; i < 4; ++i) { | |
577 k[i] *= -1.f; | |
bsalomon
2013/08/16 17:47:00
I'd say k[i] = -k[i]
maybe not faster but seems l
| |
578 l[i] *= -1.f; | |
579 } | |
580 } | |
581 } | |
582 | |
583 static void set_loop_klm(const SkScalar d[3], SkScalar k[4], SkScalar l[4], SkSc alar m[4]) { | |
584 SkScalar tempSqrt = SkScalarSqrt(4.f * d[0] * d[2] - 3.f * d[1] * d[1]); | |
585 SkScalar ls = d[1] - tempSqrt; | |
586 SkScalar lt = 2.f * d[0]; | |
587 SkScalar ms = d[1] + tempSqrt; | |
588 SkScalar mt = 2.f * d[0]; | |
589 | |
590 k[0] = ls * ms; | |
591 k[1] = (3.f * ls*ms - ls * mt - lt * ms) / 3.f; | |
592 k[2] = (lt * (mt - 2.f * ms) + ls * (3.f * ms - 2.f * mt)) / 3.f; | |
593 k[3] = (lt - ls) * (mt - ms); | |
594 | |
595 l[0] = ls * ls * ms; | |
596 l[1] = (ls * (ls * (mt - 3.f * ms) + 2.f * lt * ms))/-3.f; | |
597 l[2] = ((lt - ls) * (ls * (2.f * mt - 3.f * ms) + lt * ms))/3.f; | |
598 l[3] = -1.f * (lt - ls) * (lt - ls) * (mt - ms); | |
599 | |
600 m[0] = ls * ms * ms; | |
601 m[1] = (ms * (ls * (2.f * mt - 3.f * ms) + lt * ms))/-3.f; | |
602 m[2] = ((mt - ms) * (ls * (mt - 3.f * ms) + 2.f * lt * ms))/3.f; | |
603 m[3] = -1.f * (lt - ls) * (mt - ms) * (mt - ms); | |
604 | |
605 | |
606 // If (d0 < 0 && sign(k1) > 0) || (d0 > 0 && sign(k1) < 0), | |
607 // we need to flip the orientation of our curve. | |
608 // This is done by negating the k and l values | |
609 if ( (d[0] < 0 && k[1] < 0) || (d[0] > 0 && k[1] > 0)) { | |
610 for (int i = 0; i < 4; ++i) { | |
611 k[i] *= -1.f; | |
bsalomon
2013/08/16 17:47:00
ditto
| |
612 l[i] *= -1.f; | |
613 } | |
614 } | |
615 } | |
616 | |
617 static void set_cusp_klm(const SkScalar d[3], SkScalar k[4], SkScalar l[4], SkSc alar m[4]) { | |
618 const SkScalar ls = d[2]; | |
619 const SkScalar lt = 3.f * d[1]; | |
620 | |
621 k[0] = ls; | |
622 k[1] = ls - lt / 3.f; | |
623 k[2] = ls - 2.f * lt / 3.f; | |
624 k[3] = ls - lt; | |
625 | |
626 l[0] = ls * ls * ls; | |
627 const SkScalar ls_lt = ls - lt; | |
628 l[1] = ls * ls * ls_lt; | |
629 l[2] = ls_lt * ls_lt * ls; | |
630 l[3] = ls_lt * ls_lt * ls_lt; | |
631 | |
632 m[0] = 1.f; | |
633 m[1] = 1.f; | |
634 m[2] = 1.f; | |
635 m[3] = 1.f; | |
636 } | |
637 | |
638 // For the case when a cubic is actually a quadratic | |
639 // M = | |
640 // 0 0 0 | |
641 // 1/3 0 1/3 | |
642 // 2/3 1/3 2/3 | |
643 // 1 1 1 | |
644 static void set_quadratic_klm(const SkScalar d[3], SkScalar k[4], SkScalar l[4], SkScalar m[4]) { | |
645 k[0] = 0.f; | |
646 k[1] = 1.f/3.f; | |
647 k[2] = 2.f/3.f; | |
648 k[3] = 1.f; | |
649 | |
650 l[0] = 0.f; | |
651 l[1] = 0.f; | |
652 l[2] = 1.f/3.f; | |
653 l[3] = 1.f; | |
654 | |
655 m[0] = 0.f; | |
656 m[1] = 1.f/3.f; | |
657 m[2] = 2.f/3.f; | |
658 m[3] = 1.f; | |
659 | |
660 // If d2 < 0 we need to flip the orientation of our curve | |
661 // This is done by negating the k and l values | |
662 if ( d[2] > 0) { | |
663 for (int i = 0; i < 4; ++i) { | |
664 k[i] *= -1.f; | |
bsalomon
2013/08/16 17:47:00
ditto
| |
665 l[i] *= -1.f; | |
666 } | |
667 } | |
668 } | |
669 | |
670 // Calc coefficients of I(s,t) where roots of I are inflection points of curve | |
671 // I(s,t) = t*(3*d0*s^2 - 3*d1*s*t + d2*t^2) | |
672 // d0 = a1 - 2*a2+3*a3 | |
673 // d1 = -a2 + 3*a3 | |
674 // d2 = 3*a3 | |
675 // a1 = p0 . (p3 x p2) | |
676 // a2 = p1 . (p0 x p3) | |
677 // a3 = p2 . (p1 x p0) | |
678 // Places the values of d1, d2, d3 in array d passed in | |
679 static void calc_cubic_inflection_func(const SkPoint p[4], SkScalar d[3]) { | |
680 SkScalar a1 = calc_dot_cross_cubic(p[0], p[3], p[2]); | |
681 SkScalar a2 = calc_dot_cross_cubic(p[1], p[0], p[3]); | |
682 SkScalar a3 = calc_dot_cross_cubic(p[2], p[1], p[0]); | |
683 | |
684 // need to scale a's or values in later calculations will grow to high | |
685 SkScalar max = SkScalarAbs(a1); | |
686 max = SkMaxScalar(max, SkScalarAbs(a2)); | |
687 max = SkMaxScalar(max, SkScalarAbs(a3)); | |
688 max = 1.f/max; | |
689 a1 = a1 * max; | |
690 a2 = a2 * max; | |
691 a3 = a3 * max; | |
692 | |
693 d[2] = 3.f * a3; | |
694 d[1] = d[2] - a2; | |
695 d[0] = d[1] - a2 + a1; | |
696 } | |
697 | |
698 int GrPathUtils::chopCubicAtLoopIntersection(const SkPoint src[4], SkPoint dst[1 0], SkScalar klm[9], | |
699 SkScalar klm_rev[3], const SkPoint devPts[4]) { | |
700 | |
701 // Variable to store the two parametric values at the loop double point | |
702 SkScalar smallS = 0.f; | |
703 SkScalar largeS = 0.f; | |
704 | |
705 SkScalar d[3]; | |
706 const SkPoint* cPts = devPts ? devPts : src; | |
707 calc_cubic_inflection_func(cPts, d); | |
708 | |
709 CubicType cType = classify_cubic(cPts, d); | |
710 | |
711 int chop_count = 0; | |
712 if (kLoop == cType) { | |
713 SkScalar tempSqrt = SkScalarSqrt(4.f * d[0] * d[2] - 3.f * d[1] * d[1]); | |
714 SkScalar ls = d[1] - tempSqrt; | |
715 SkScalar lt = 2.f * d[0]; | |
716 SkScalar ms = d[1] + tempSqrt; | |
717 SkScalar mt = 2.f * d[0]; | |
718 ls = ls / lt; | |
719 ms = ms / mt; | |
720 // need to have t values sorted since this is what is expected by SkChop CubicAt | |
721 if (ls <= ms) { | |
722 smallS = ls; | |
723 largeS = ms; | |
724 } else { | |
725 smallS = ms; | |
726 largeS = ls; | |
727 } | |
728 | |
729 SkScalar chop_ts[2]; | |
730 if (smallS > 0.f && smallS < 1.f) { | |
731 chop_ts[chop_count++] = smallS; | |
732 } | |
733 if (largeS > 0.f && largeS < 1.f) { | |
734 chop_ts[chop_count++] = largeS; | |
735 } | |
736 if(dst) { | |
737 SkChopCubicAt(src, dst, chop_ts, chop_count); | |
738 } | |
739 } else { | |
740 if (dst) { | |
741 memcpy(dst, src, sizeof(SkPoint) * 4); | |
742 } | |
743 } | |
744 | |
745 if (klm && klm_rev && devPts) { | |
746 // Set klm_rev to to match the sub_section of cubic that needs to have i ts orientation | |
747 // flipped. This will always be the section that is the "loop" | |
748 if (2 == chop_count) { | |
749 klm_rev[0] = 1.f; | |
750 klm_rev[1] = -1.f; | |
751 klm_rev[2] = 1.f; | |
752 } else if (2 == chop_count) { | |
753 if (smallS < 0.f) { | |
754 klm_rev[0] = -1.f; | |
755 klm_rev[1] = 1.f; | |
756 } else { | |
757 klm_rev[0] = 1.f; | |
758 klm_rev[1] = -1.f; | |
759 } | |
760 } else { | |
761 if (smallS < 0.f && largeS > 1.f) { | |
762 klm_rev[0] = -1.f; | |
763 } else { | |
764 klm_rev[0] = 1.f; | |
765 } | |
766 } | |
767 SkScalar controlK[4]; | |
768 SkScalar controlL[4]; | |
769 SkScalar controlM[4]; | |
770 | |
771 if (kSerpentine == cType || (kCusp == cType && 0.f != d[0])) { | |
772 set_serp_klm(d, controlK, controlL, controlM); | |
773 } else if (kLoop == cType) { | |
774 set_loop_klm(d, controlK, controlL, controlM); | |
775 } else if (kCusp == cType) { | |
776 GrAssert(0.f == d[0]); | |
777 set_cusp_klm(d, controlK, controlL, controlM); | |
778 } else if (kQuadratic == cType) { | |
779 set_quadratic_klm(d, controlK, controlL, controlM); | |
780 } | |
781 | |
782 calc_cubic_klm(devPts, controlK, controlL, controlM, klm, &klm[3], &klm[ 6]); | |
783 } | |
784 return chop_count + 1; | |
785 } | |
786 | |
787 void GrPathUtils::getCubicKLM(const SkPoint p[4], SkScalar klm[9]) { | |
788 SkScalar d[3]; | |
789 calc_cubic_inflection_func(p, d); | |
790 | |
791 CubicType cType = classify_cubic(p, d); | |
792 | |
793 SkScalar controlK[4]; | |
794 SkScalar controlL[4]; | |
795 SkScalar controlM[4]; | |
796 | |
797 if (kSerpentine == cType || (kCusp == cType && 0.f != d[0])) { | |
798 set_serp_klm(d, controlK, controlL, controlM); | |
799 } else if (kLoop == cType) { | |
800 set_loop_klm(d, controlK, controlL, controlM); | |
801 } else if (kCusp == cType) { | |
802 GrAssert(0.f == d[0]); | |
803 set_cusp_klm(d, controlK, controlL, controlM); | |
804 } else if (kQuadratic == cType) { | |
805 set_quadratic_klm(d, controlK, controlL, controlM); | |
806 } | |
807 | |
808 calc_cubic_klm(p, controlK, controlL, controlM, klm, &klm[3], &klm[6]); | |
809 } | |
810 | |
bsalomon
2013/08/16 17:47:00
style-nit: a few extra \ns here
| |
811 | |
812 | |
OLD | NEW |