OLD | NEW |
---|---|
1 | 1 |
2 /* | 2 /* |
3 * Copyright 2006 The Android Open Source Project | 3 * Copyright 2006 The Android Open Source Project |
4 * | 4 * |
5 * Use of this source code is governed by a BSD-style license that can be | 5 * Use of this source code is governed by a BSD-style license that can be |
6 * found in the LICENSE file. | 6 * found in the LICENSE file. |
7 */ | 7 */ |
8 | 8 |
9 | 9 |
10 #include "SkGeometry.h" | 10 #include "SkGeometry.h" |
(...skipping 781 matching lines...) Expand 10 before | Expand all | Expand 10 after Loading... | |
792 for (int i = count - 1; i > 0; --i) | 792 for (int i = count - 1; i > 0; --i) |
793 for (int j = i; j > 0; --j) | 793 for (int j = i; j > 0; --j) |
794 if (array[j] < array[j-1]) | 794 if (array[j] < array[j-1]) |
795 { | 795 { |
796 T tmp(array[j]); | 796 T tmp(array[j]); |
797 array[j] = array[j-1]; | 797 array[j] = array[j-1]; |
798 array[j-1] = tmp; | 798 array[j-1] = tmp; |
799 } | 799 } |
800 } | 800 } |
801 | 801 |
802 #include "SkFP.h" | |
803 | |
804 // newton refinement | 802 // newton refinement |
805 #if 0 | 803 #if 0 |
806 static SkScalar refine_cubic_root(const SkFP coeff[4], SkScalar root) | 804 static SkScalar refine_cubic_root(const SkFP coeff[4], SkScalar root) |
807 { | 805 { |
808 // x1 = x0 - f(t) / f'(t) | 806 // x1 = x0 - f(t) / f'(t) |
809 | 807 |
810 SkFP T = SkScalarToFloat(root); | 808 SkFP T = SkScalarToFloat(root); |
811 SkFP N, D; | 809 SkFP N, D; |
812 | 810 |
813 // f' = 3*coeff[0]*T^2 + 2*coeff[1]*T + coeff[2] | 811 // f' = 3*coeff[0]*T^2 + 2*coeff[1]*T + coeff[2] |
(...skipping 76 matching lines...) Expand 10 before | Expand all | Expand 10 after Loading... | |
890 SkASSERT(dst[j-1] < dst[j]); | 888 SkASSERT(dst[j-1] < dst[j]); |
891 } | 889 } |
892 } | 890 } |
893 } | 891 } |
894 #endif | 892 #endif |
895 | 893 |
896 #if defined _WIN32 && _MSC_VER >= 1300 && defined SK_SCALAR_IS_FIXED // disable warning : unreachable code if building fixed point for windows desktop | 894 #if defined _WIN32 && _MSC_VER >= 1300 && defined SK_SCALAR_IS_FIXED // disable warning : unreachable code if building fixed point for windows desktop |
897 #pragma warning ( disable : 4702 ) | 895 #pragma warning ( disable : 4702 ) |
898 #endif | 896 #endif |
899 | 897 |
898 static SkScalar SkScalarCubeRoot(SkScalar x) { | |
899 return sk_float_pow(x, 0.3333333f); | |
900 } | |
caryclark
2013/12/16 13:39:31
Here's what I came up with for float in my experim
| |
901 | |
900 /* Solve coeff(t) == 0, returning the number of roots that | 902 /* Solve coeff(t) == 0, returning the number of roots that |
901 lie withing 0 < t < 1. | 903 lie withing 0 < t < 1. |
902 coeff[0]t^3 + coeff[1]t^2 + coeff[2]t + coeff[3] | 904 coeff[0]t^3 + coeff[1]t^2 + coeff[2]t + coeff[3] |
903 | 905 |
904 Eliminates repeated roots (so that all tValues are distinct, and are always | 906 Eliminates repeated roots (so that all tValues are distinct, and are always |
905 in increasing order. | 907 in increasing order. |
906 */ | 908 */ |
907 static int solve_cubic_polynomial(const SkFP coeff[4], SkScalar tValues[3]) | 909 static int solve_cubic_polynomial(const SkScalar coeff[4], SkScalar tValues[3]) |
908 { | 910 { |
909 #ifndef SK_SCALAR_IS_FLOAT | |
910 return 0; // this is not yet implemented for software float | |
911 #endif | |
912 | |
913 if (SkScalarNearlyZero(coeff[0])) // we're just a quadratic | 911 if (SkScalarNearlyZero(coeff[0])) // we're just a quadratic |
914 { | 912 { |
915 return SkFindUnitQuadRoots(coeff[1], coeff[2], coeff[3], tValues); | 913 return SkFindUnitQuadRoots(coeff[1], coeff[2], coeff[3], tValues); |
916 } | 914 } |
917 | 915 |
918 SkFP a, b, c, Q, R; | 916 SkScalar a, b, c, Q, R; |
919 | 917 |
920 { | 918 { |
921 SkASSERT(coeff[0] != 0); | 919 SkASSERT(coeff[0] != 0); |
922 | 920 |
923 SkFP inva = SkFPInvert(coeff[0]); | 921 SkScalar inva = SkScalarInvert(coeff[0]); |
924 a = SkFPMul(coeff[1], inva); | 922 a = coeff[1] * inva; |
925 b = SkFPMul(coeff[2], inva); | 923 b = coeff[2] * inva; |
926 c = SkFPMul(coeff[3], inva); | 924 c = coeff[3] * inva; |
927 } | 925 } |
928 Q = SkFPDivInt(SkFPSub(SkFPMul(a,a), SkFPMulInt(b, 3)), 9); | 926 Q = (a*a - b*3) / 9; |
929 // R = (2*a*a*a - 9*a*b + 27*c) / 54; | 927 R = (2*a*a*a - 9*a*b + 27*c) / 54; |
930 R = SkFPMulInt(SkFPMul(SkFPMul(a, a), a), 2); | |
931 R = SkFPSub(R, SkFPMulInt(SkFPMul(a, b), 9)); | |
932 R = SkFPAdd(R, SkFPMulInt(c, 27)); | |
933 R = SkFPDivInt(R, 54); | |
934 | 928 |
935 SkFP Q3 = SkFPMul(SkFPMul(Q, Q), Q); | 929 SkScalar Q3 = Q * Q * Q; |
936 SkFP R2MinusQ3 = SkFPSub(SkFPMul(R,R), Q3); | 930 SkScalar R2MinusQ3 = R * R - Q3; |
937 SkFP adiv3 = SkFPDivInt(a, 3); | 931 SkScalar adiv3 = a / 3; |
938 | 932 |
939 SkScalar* roots = tValues; | 933 SkScalar* roots = tValues; |
940 SkScalar r; | 934 SkScalar r; |
941 | 935 |
942 if (SkFPLT(R2MinusQ3, 0)) // we have 3 real roots | 936 if (R2MinusQ3 < 0) // we have 3 real roots |
943 { | 937 { |
944 #ifdef SK_SCALAR_IS_FLOAT | |
945 float theta = sk_float_acos(R / sk_float_sqrt(Q3)); | 938 float theta = sk_float_acos(R / sk_float_sqrt(Q3)); |
946 float neg2RootQ = -2 * sk_float_sqrt(Q); | 939 float neg2RootQ = -2 * sk_float_sqrt(Q); |
947 | 940 |
948 r = neg2RootQ * sk_float_cos(theta/3) - adiv3; | 941 r = neg2RootQ * sk_float_cos(theta/3) - adiv3; |
949 if (is_unit_interval(r)) | 942 if (is_unit_interval(r)) |
950 *roots++ = r; | 943 *roots++ = r; |
951 | 944 |
952 r = neg2RootQ * sk_float_cos((theta + 2*SK_ScalarPI)/3) - adiv3; | 945 r = neg2RootQ * sk_float_cos((theta + 2*SK_ScalarPI)/3) - adiv3; |
953 if (is_unit_interval(r)) | 946 if (is_unit_interval(r)) |
954 *roots++ = r; | 947 *roots++ = r; |
955 | 948 |
956 r = neg2RootQ * sk_float_cos((theta - 2*SK_ScalarPI)/3) - adiv3; | 949 r = neg2RootQ * sk_float_cos((theta - 2*SK_ScalarPI)/3) - adiv3; |
957 if (is_unit_interval(r)) | 950 if (is_unit_interval(r)) |
958 *roots++ = r; | 951 *roots++ = r; |
959 | 952 |
960 SkDEBUGCODE(test_collaps_duplicates();) | 953 SkDEBUGCODE(test_collaps_duplicates();) |
961 | 954 |
962 // now sort the roots | 955 // now sort the roots |
963 int count = (int)(roots - tValues); | 956 int count = (int)(roots - tValues); |
964 SkASSERT((unsigned)count <= 3); | 957 SkASSERT((unsigned)count <= 3); |
965 bubble_sort(tValues, count); | 958 bubble_sort(tValues, count); |
966 count = collaps_duplicates(tValues, count); | 959 count = collaps_duplicates(tValues, count); |
967 roots = tValues + count; // so we compute the proper count below | 960 roots = tValues + count; // so we compute the proper count below |
968 #endif | |
969 } | 961 } |
970 else // we have 1 real root | 962 else // we have 1 real root |
971 { | 963 { |
972 SkFP A = SkFPAdd(SkFPAbs(R), SkFPSqrt(R2MinusQ3)); | 964 SkScalar A = SkScalarAbs(R) + SkScalarSqrt(R2MinusQ3); |
973 A = SkFPCubeRoot(A); | 965 A = SkScalarCubeRoot(A); |
974 if (SkFPGT(R, 0)) | 966 if (R > 0) |
975 A = SkFPNeg(A); | 967 A = -A; |
976 | 968 |
977 if (A != 0) | 969 if (A != 0) |
978 A = SkFPAdd(A, SkFPDiv(Q, A)); | 970 A += Q / A; |
979 r = SkFPToScalar(SkFPSub(A, adiv3)); | 971 r = A - adiv3; |
980 if (is_unit_interval(r)) | 972 if (is_unit_interval(r)) |
981 *roots++ = r; | 973 *roots++ = r; |
982 } | 974 } |
983 | 975 |
984 return (int)(roots - tValues); | 976 return (int)(roots - tValues); |
985 } | 977 } |
986 | 978 |
987 /* Looking for F' dot F'' == 0 | 979 /* Looking for F' dot F'' == 0 |
988 | 980 |
989 A = b - a | 981 A = b - a |
990 B = c - 2b + a | 982 B = c - 2b + a |
991 C = d - 3c + 3b - a | 983 C = d - 3c + 3b - a |
992 | 984 |
993 F' = 3Ct^2 + 6Bt + 3A | 985 F' = 3Ct^2 + 6Bt + 3A |
994 F'' = 6Ct + 6B | 986 F'' = 6Ct + 6B |
995 | 987 |
996 F' dot F'' -> CCt^3 + 3BCt^2 + (2BB + CA)t + AB | 988 F' dot F'' -> CCt^3 + 3BCt^2 + (2BB + CA)t + AB |
997 */ | 989 */ |
998 static void formulate_F1DotF2(const SkScalar src[], SkFP coeff[4]) | 990 static void formulate_F1DotF2(const SkScalar src[], SkScalar coeff[4]) |
999 { | 991 { |
1000 SkScalar a = src[2] - src[0]; | 992 SkScalar a = src[2] - src[0]; |
1001 SkScalar b = src[4] - 2 * src[2] + src[0]; | 993 SkScalar b = src[4] - 2 * src[2] + src[0]; |
1002 SkScalar c = src[6] + 3 * (src[2] - src[4]) - src[0]; | 994 SkScalar c = src[6] + 3 * (src[2] - src[4]) - src[0]; |
1003 | 995 |
1004 SkFP A = SkScalarToFP(a); | 996 coeff[0] = c * c; |
1005 SkFP B = SkScalarToFP(b); | 997 coeff[1] = 3 * b * c; |
1006 SkFP C = SkScalarToFP(c); | 998 coeff[2] = 2 * b * b + c * a; |
1007 | 999 coeff[3] = a * b; |
1008 coeff[0] = SkFPMul(C, C); | |
1009 coeff[1] = SkFPMulInt(SkFPMul(B, C), 3); | |
1010 coeff[2] = SkFPMulInt(SkFPMul(B, B), 2); | |
1011 coeff[2] = SkFPAdd(coeff[2], SkFPMul(C, A)); | |
1012 coeff[3] = SkFPMul(A, B); | |
1013 } | 1000 } |
1014 | 1001 |
1015 // EXPERIMENTAL: can set this to zero to accept all t-values 0 < t < 1 | 1002 // EXPERIMENTAL: can set this to zero to accept all t-values 0 < t < 1 |
1016 //#define kMinTValueForChopping (SK_Scalar1 / 256) | 1003 //#define kMinTValueForChopping (SK_Scalar1 / 256) |
1017 #define kMinTValueForChopping 0 | 1004 #define kMinTValueForChopping 0 |
1018 | 1005 |
1019 /* Looking for F' dot F'' == 0 | 1006 /* Looking for F' dot F'' == 0 |
1020 | 1007 |
1021 A = b - a | 1008 A = b - a |
1022 B = c - 2b + a | 1009 B = c - 2b + a |
1023 C = d - 3c + 3b - a | 1010 C = d - 3c + 3b - a |
1024 | 1011 |
1025 F' = 3Ct^2 + 6Bt + 3A | 1012 F' = 3Ct^2 + 6Bt + 3A |
1026 F'' = 6Ct + 6B | 1013 F'' = 6Ct + 6B |
1027 | 1014 |
1028 F' dot F'' -> CCt^3 + 3BCt^2 + (2BB + CA)t + AB | 1015 F' dot F'' -> CCt^3 + 3BCt^2 + (2BB + CA)t + AB |
1029 */ | 1016 */ |
1030 int SkFindCubicMaxCurvature(const SkPoint src[4], SkScalar tValues[3]) | 1017 int SkFindCubicMaxCurvature(const SkPoint src[4], SkScalar tValues[3]) |
1031 { | 1018 { |
1032 SkFP coeffX[4], coeffY[4]; | 1019 SkScalar coeffX[4], coeffY[4]; |
1033 int i; | 1020 int i; |
1034 | 1021 |
1035 formulate_F1DotF2(&src[0].fX, coeffX); | 1022 formulate_F1DotF2(&src[0].fX, coeffX); |
1036 formulate_F1DotF2(&src[0].fY, coeffY); | 1023 formulate_F1DotF2(&src[0].fY, coeffY); |
1037 | 1024 |
1038 for (i = 0; i < 4; i++) | 1025 for (i = 0; i < 4; i++) |
1039 coeffX[i] = SkFPAdd(coeffX[i],coeffY[i]); | 1026 coeffX[i] += coeffY[i]; |
1040 | 1027 |
1041 SkScalar t[3]; | 1028 SkScalar t[3]; |
1042 int count = solve_cubic_polynomial(coeffX, t); | 1029 int count = solve_cubic_polynomial(coeffX, t); |
1043 int maxCount = 0; | 1030 int maxCount = 0; |
1044 | 1031 |
1045 // now remove extrema where the curvature is zero (mins) | 1032 // now remove extrema where the curvature is zero (mins) |
1046 // !!!! need a test for this !!!! | 1033 // !!!! need a test for this !!!! |
1047 for (i = 0; i < count; i++) | 1034 for (i = 0; i < count; i++) |
1048 { | 1035 { |
1049 // if (not_min_curvature()) | 1036 // if (not_min_curvature()) |
(...skipping 591 matching lines...) Expand 10 before | Expand all | Expand 10 after Loading... | |
1641 } | 1628 } |
1642 if (this->findYExtrema(&t)) { | 1629 if (this->findYExtrema(&t)) { |
1643 this->evalAt(t, &pts[count++]); | 1630 this->evalAt(t, &pts[count++]); |
1644 } | 1631 } |
1645 bounds->set(pts, count); | 1632 bounds->set(pts, count); |
1646 } | 1633 } |
1647 | 1634 |
1648 void SkConic::computeFastBounds(SkRect* bounds) const { | 1635 void SkConic::computeFastBounds(SkRect* bounds) const { |
1649 bounds->set(fPts, 3); | 1636 bounds->set(fPts, 3); |
1650 } | 1637 } |
OLD | NEW |