Chromium Code Reviews
chromiumcodereview-hr@appspot.gserviceaccount.com (chromiumcodereview-hr) | Please choose your nickname with Settings | Help | Chromium Project | Gerrit Changes | Sign out
(625)

Side by Side Diff: src/gpu/GrPathUtils.cpp

Issue 22900007: Add direct bezier cubic support for GPU shaders (Closed) Base URL: https://skia.googlecode.com/svn/trunk
Patch Set: Created 7 years, 4 months ago
Use n/p to move between diff chunks; N/P to move between comments. Draft comments are only viewable by you.
Jump to:
View unified diff | Download patch | Annotate | Revision Log
« no previous file with comments | « src/gpu/GrPathUtils.h ('k') | no next file » | no next file with comments »
Toggle Intra-line Diffs ('i') | Expand Comments ('e') | Collapse Comments ('c') | Show Comments Hide Comments ('s')
OLDNEW
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
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 {
483 kSerpentine_CubicType,
484 kCusp_CubicType,
485 kLoop_CubicType,
486 kQuadratic_CubicType,
487 kLine_CubicType,
488 kPoint_CubicType
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 kPoint_CubicType;
502 }
503 const SkScalar discr = d[0] * d[0] * (3.f * d[1] * d[1] - 4.f * d[0] * d[2]) ;
504 if (discr > SK_ScalarNearlyZero) {
505 return kSerpentine_CubicType;
506 } else if (discr < -SK_ScalarNearlyZero) {
507 return kLoop_CubicType;
508 } else {
509 if (0.f == d[0] && 0.f == d[1]) {
510 return (0.f == d[2] ? kLine_CubicType : kQuadratic_CubicType);
511 } else {
512 return kCusp_CubicType;
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.f * 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] = -k[i];
578 l[i] = -l[i];
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] = -k[i];
612 l[i] = -l[i];
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] = -k[i];
665 l[i] = -l[i];
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]) {
700 // Variable to store the two parametric values at the loop double point
701 SkScalar smallS = 0.f;
702 SkScalar largeS = 0.f;
703
704 SkScalar d[3];
705 calc_cubic_inflection_func(src, d);
706
707 CubicType cType = classify_cubic(src, d);
708
709 int chop_count = 0;
710 if (kLoop_CubicType == cType) {
711 SkScalar tempSqrt = SkScalarSqrt(4.f * d[0] * d[2] - 3.f * d[1] * d[1]);
712 SkScalar ls = d[1] - tempSqrt;
713 SkScalar lt = 2.f * d[0];
714 SkScalar ms = d[1] + tempSqrt;
715 SkScalar mt = 2.f * d[0];
716 ls = ls / lt;
717 ms = ms / mt;
718 // need to have t values sorted since this is what is expected by SkChop CubicAt
719 if (ls <= ms) {
720 smallS = ls;
721 largeS = ms;
722 } else {
723 smallS = ms;
724 largeS = ls;
725 }
726
727 SkScalar chop_ts[2];
728 if (smallS > 0.f && smallS < 1.f) {
729 chop_ts[chop_count++] = smallS;
730 }
731 if (largeS > 0.f && largeS < 1.f) {
732 chop_ts[chop_count++] = largeS;
733 }
734 if(dst) {
735 SkChopCubicAt(src, dst, chop_ts, chop_count);
736 }
737 } else {
738 if (dst) {
739 memcpy(dst, src, sizeof(SkPoint) * 4);
740 }
741 }
742
743 if (klm && klm_rev) {
744 // Set klm_rev to to match the sub_section of cubic that needs to have i ts orientation
745 // flipped. This will always be the section that is the "loop"
746 if (2 == chop_count) {
747 klm_rev[0] = 1.f;
748 klm_rev[1] = -1.f;
749 klm_rev[2] = 1.f;
750 } else if (1 == chop_count) {
751 if (smallS < 0.f) {
752 klm_rev[0] = -1.f;
753 klm_rev[1] = 1.f;
754 } else {
755 klm_rev[0] = 1.f;
756 klm_rev[1] = -1.f;
757 }
758 } else {
759 if (smallS < 0.f && largeS > 1.f) {
760 klm_rev[0] = -1.f;
761 } else {
762 klm_rev[0] = 1.f;
763 }
764 }
765 SkScalar controlK[4];
766 SkScalar controlL[4];
767 SkScalar controlM[4];
768
769 if (kSerpentine_CubicType == cType || (kCusp_CubicType == cType && 0.f ! = d[0])) {
770 set_serp_klm(d, controlK, controlL, controlM);
771 } else if (kLoop_CubicType == cType) {
772 set_loop_klm(d, controlK, controlL, controlM);
773 } else if (kCusp_CubicType == cType) {
774 SkASSERT(0.f == d[0]);
775 set_cusp_klm(d, controlK, controlL, controlM);
776 } else if (kQuadratic_CubicType == cType) {
777 set_quadratic_klm(d, controlK, controlL, controlM);
778 }
779
780 calc_cubic_klm(src, controlK, controlL, controlM, klm, &klm[3], &klm[6]) ;
781 }
782 return chop_count + 1;
783 }
784
785 void GrPathUtils::getCubicKLM(const SkPoint p[4], SkScalar klm[9]) {
786 SkScalar d[3];
787 calc_cubic_inflection_func(p, d);
788
789 CubicType cType = classify_cubic(p, d);
790
791 SkScalar controlK[4];
792 SkScalar controlL[4];
793 SkScalar controlM[4];
794
795 if (kSerpentine_CubicType == cType || (kCusp_CubicType == cType && 0.f != d[ 0])) {
796 set_serp_klm(d, controlK, controlL, controlM);
797 } else if (kLoop_CubicType == cType) {
798 set_loop_klm(d, controlK, controlL, controlM);
799 } else if (kCusp_CubicType == cType) {
800 SkASSERT(0.f == d[0]);
801 set_cusp_klm(d, controlK, controlL, controlM);
802 } else if (kQuadratic_CubicType == cType) {
803 set_quadratic_klm(d, controlK, controlL, controlM);
804 }
805
806 calc_cubic_klm(p, controlK, controlL, controlM, klm, &klm[3], &klm[6]);
807 }
OLDNEW
« no previous file with comments | « src/gpu/GrPathUtils.h ('k') | no next file » | no next file with comments »

Powered by Google App Engine
This is Rietveld 408576698