| OLD | NEW |
| 1 /* | 1 /* |
| 2 * Copyright 2006 The Android Open Source Project | 2 * Copyright 2006 The Android Open Source Project |
| 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 "SkGeometry.h" | 8 #include "SkGeometry.h" |
| 9 #include "SkMatrix.h" | 9 #include "SkMatrix.h" |
| 10 #include "SkNx.h" | 10 #include "SkNx.h" |
| (...skipping 932 matching lines...) Expand 10 before | Expand all | Expand 10 after Loading... |
| 943 | 943 |
| 944 bool SkChopMonoCubicAtY(SkPoint src[4], SkScalar y, SkPoint dst[7]) { | 944 bool SkChopMonoCubicAtY(SkPoint src[4], SkScalar y, SkPoint dst[7]) { |
| 945 return cubic_dchop_at_intercept(src, y, dst, &SkDCubic::horizontalIntersect)
; | 945 return cubic_dchop_at_intercept(src, y, dst, &SkDCubic::horizontalIntersect)
; |
| 946 } | 946 } |
| 947 | 947 |
| 948 bool SkChopMonoCubicAtX(SkPoint src[4], SkScalar x, SkPoint dst[7]) { | 948 bool SkChopMonoCubicAtX(SkPoint src[4], SkScalar x, SkPoint dst[7]) { |
| 949 return cubic_dchop_at_intercept(src, x, dst, &SkDCubic::verticalIntersect); | 949 return cubic_dchop_at_intercept(src, x, dst, &SkDCubic::verticalIntersect); |
| 950 } | 950 } |
| 951 | 951 |
| 952 /////////////////////////////////////////////////////////////////////////////// | 952 /////////////////////////////////////////////////////////////////////////////// |
| 953 | |
| 954 #ifdef SK_SUPPORT_LEGACY_ARCTO | |
| 955 /* Find t value for quadratic [a, b, c] = d. | |
| 956 Return 0 if there is no solution within [0, 1) | |
| 957 */ | |
| 958 static SkScalar quad_solve(SkScalar a, SkScalar b, SkScalar c, SkScalar d) { | |
| 959 // At^2 + Bt + C = d | |
| 960 SkScalar A = a - 2 * b + c; | |
| 961 SkScalar B = 2 * (b - a); | |
| 962 SkScalar C = a - d; | |
| 963 | |
| 964 SkScalar roots[2]; | |
| 965 int count = SkFindUnitQuadRoots(A, B, C, roots); | |
| 966 | |
| 967 SkASSERT(count <= 1); | |
| 968 return count == 1 ? roots[0] : 0; | |
| 969 } | |
| 970 | |
| 971 /* given a quad-curve and a point (x,y), chop the quad at that point and place | |
| 972 the new off-curve point and endpoint into 'dest'. | |
| 973 Should only return false if the computed pos is the start of the curve | |
| 974 (i.e. root == 0) | |
| 975 */ | |
| 976 static bool truncate_last_curve(const SkPoint quad[3], SkScalar x, SkScalar y, | |
| 977 SkPoint* dest) { | |
| 978 const SkScalar* base; | |
| 979 SkScalar value; | |
| 980 | |
| 981 if (SkScalarAbs(x) < SkScalarAbs(y)) { | |
| 982 base = &quad[0].fX; | |
| 983 value = x; | |
| 984 } else { | |
| 985 base = &quad[0].fY; | |
| 986 value = y; | |
| 987 } | |
| 988 | |
| 989 // note: this returns 0 if it thinks value is out of range, meaning the | |
| 990 // root might return something outside of [0, 1) | |
| 991 SkScalar t = quad_solve(base[0], base[2], base[4], value); | |
| 992 | |
| 993 if (t > 0) { | |
| 994 SkPoint tmp[5]; | |
| 995 SkChopQuadAt(quad, tmp, t); | |
| 996 dest[0] = tmp[1]; | |
| 997 dest[1].set(x, y); | |
| 998 return true; | |
| 999 } else { | |
| 1000 /* t == 0 means either the value triggered a root outside of [0, 1) | |
| 1001 For our purposes, we can ignore the <= 0 roots, but we want to | |
| 1002 catch the >= 1 roots (which given our caller, will basically mean | |
| 1003 a root of 1, give-or-take numerical instability). If we are in the | |
| 1004 >= 1 case, return the existing offCurve point. | |
| 1005 | |
| 1006 The test below checks to see if we are close to the "end" of the | |
| 1007 curve (near base[4]). Rather than specifying a tolerance, I just | |
| 1008 check to see if value is on to the right/left of the middle point | |
| 1009 (depending on the direction/sign of the end points). | |
| 1010 */ | |
| 1011 if ((base[0] < base[4] && value > base[2]) || | |
| 1012 (base[0] > base[4] && value < base[2])) // should root have been 1 | |
| 1013 { | |
| 1014 dest[0] = quad[1]; | |
| 1015 dest[1].set(x, y); | |
| 1016 return true; | |
| 1017 } | |
| 1018 } | |
| 1019 return false; | |
| 1020 } | |
| 1021 | |
| 1022 static const SkPoint gQuadCirclePts[kSkBuildQuadArcStorage] = { | |
| 1023 // The mid point of the quadratic arc approximation is half way between the two | |
| 1024 // control points. The float epsilon adjustment moves the on curve point out by | |
| 1025 // two bits, distributing the convex test error between the round rect | |
| 1026 // approximation and the convex cross product sign equality test. | |
| 1027 #define SK_MID_RRECT_OFFSET \ | |
| 1028 (SK_Scalar1 + SK_ScalarTanPIOver8 + FLT_EPSILON * 4) / 2 | |
| 1029 { SK_Scalar1, 0 }, | |
| 1030 { SK_Scalar1, SK_ScalarTanPIOver8 }, | |
| 1031 { SK_MID_RRECT_OFFSET, SK_MID_RRECT_OFFSET }, | |
| 1032 { SK_ScalarTanPIOver8, SK_Scalar1 }, | |
| 1033 | |
| 1034 { 0, SK_Scalar1 }, | |
| 1035 { -SK_ScalarTanPIOver8, SK_Scalar1 }, | |
| 1036 { -SK_MID_RRECT_OFFSET, SK_MID_RRECT_OFFSET }, | |
| 1037 { -SK_Scalar1, SK_ScalarTanPIOver8 }, | |
| 1038 | |
| 1039 { -SK_Scalar1, 0 }, | |
| 1040 { -SK_Scalar1, -SK_ScalarTanPIOver8 }, | |
| 1041 { -SK_MID_RRECT_OFFSET, -SK_MID_RRECT_OFFSET }, | |
| 1042 { -SK_ScalarTanPIOver8, -SK_Scalar1 }, | |
| 1043 | |
| 1044 { 0, -SK_Scalar1 }, | |
| 1045 { SK_ScalarTanPIOver8, -SK_Scalar1 }, | |
| 1046 { SK_MID_RRECT_OFFSET, -SK_MID_RRECT_OFFSET }, | |
| 1047 { SK_Scalar1, -SK_ScalarTanPIOver8 }, | |
| 1048 | |
| 1049 { SK_Scalar1, 0 } | |
| 1050 #undef SK_MID_RRECT_OFFSET | |
| 1051 }; | |
| 1052 | |
| 1053 int SkBuildQuadArc(const SkVector& uStart, const SkVector& uStop, | |
| 1054 SkRotationDirection dir, const SkMatrix* userMatrix, | |
| 1055 SkPoint quadPoints[]) { | |
| 1056 // rotate by x,y so that uStart is (1.0) | |
| 1057 SkScalar x = SkPoint::DotProduct(uStart, uStop); | |
| 1058 SkScalar y = SkPoint::CrossProduct(uStart, uStop); | |
| 1059 | |
| 1060 SkScalar absX = SkScalarAbs(x); | |
| 1061 SkScalar absY = SkScalarAbs(y); | |
| 1062 | |
| 1063 int pointCount; | |
| 1064 | |
| 1065 // check for (effectively) coincident vectors | |
| 1066 // this can happen if our angle is nearly 0 or nearly 180 (y == 0) | |
| 1067 // ... we use the dot-prod to distinguish between 0 and 180 (x > 0) | |
| 1068 if (absY <= SK_ScalarNearlyZero && x > 0 && | |
| 1069 ((y >= 0 && kCW_SkRotationDirection == dir) || | |
| 1070 (y <= 0 && kCCW_SkRotationDirection == dir))) { | |
| 1071 | |
| 1072 // just return the start-point | |
| 1073 quadPoints[0].set(SK_Scalar1, 0); | |
| 1074 pointCount = 1; | |
| 1075 } else { | |
| 1076 if (dir == kCCW_SkRotationDirection) { | |
| 1077 y = -y; | |
| 1078 } | |
| 1079 // what octant (quadratic curve) is [xy] in? | |
| 1080 int oct = 0; | |
| 1081 bool sameSign = true; | |
| 1082 | |
| 1083 if (0 == y) { | |
| 1084 oct = 4; // 180 | |
| 1085 SkASSERT(SkScalarAbs(x + SK_Scalar1) <= SK_ScalarNearlyZero); | |
| 1086 } else if (0 == x) { | |
| 1087 SkASSERT(absY - SK_Scalar1 <= SK_ScalarNearlyZero); | |
| 1088 oct = y > 0 ? 2 : 6; // 90 : 270 | |
| 1089 } else { | |
| 1090 if (y < 0) { | |
| 1091 oct += 4; | |
| 1092 } | |
| 1093 if ((x < 0) != (y < 0)) { | |
| 1094 oct += 2; | |
| 1095 sameSign = false; | |
| 1096 } | |
| 1097 if ((absX < absY) == sameSign) { | |
| 1098 oct += 1; | |
| 1099 } | |
| 1100 } | |
| 1101 | |
| 1102 int wholeCount = oct << 1; | |
| 1103 memcpy(quadPoints, gQuadCirclePts, (wholeCount + 1) * sizeof(SkPoint)); | |
| 1104 | |
| 1105 const SkPoint* arc = &gQuadCirclePts[wholeCount]; | |
| 1106 if (truncate_last_curve(arc, x, y, &quadPoints[wholeCount + 1])) { | |
| 1107 wholeCount += 2; | |
| 1108 } | |
| 1109 pointCount = wholeCount + 1; | |
| 1110 } | |
| 1111 | |
| 1112 // now handle counter-clockwise and the initial unitStart rotation | |
| 1113 SkMatrix matrix; | |
| 1114 matrix.setSinCos(uStart.fY, uStart.fX); | |
| 1115 if (dir == kCCW_SkRotationDirection) { | |
| 1116 matrix.preScale(SK_Scalar1, -SK_Scalar1); | |
| 1117 } | |
| 1118 if (userMatrix) { | |
| 1119 matrix.postConcat(*userMatrix); | |
| 1120 } | |
| 1121 matrix.mapPoints(quadPoints, pointCount); | |
| 1122 return pointCount; | |
| 1123 } | |
| 1124 #endif | |
| 1125 | |
| 1126 /////////////////////////////////////////////////////////////////////////////// | |
| 1127 // | 953 // |
| 1128 // NURB representation for conics. Helpful explanations at: | 954 // NURB representation for conics. Helpful explanations at: |
| 1129 // | 955 // |
| 1130 // http://citeseerx.ist.psu.edu/viewdoc/ | 956 // http://citeseerx.ist.psu.edu/viewdoc/ |
| 1131 // download?doi=10.1.1.44.5740&rep=rep1&type=ps | 957 // download?doi=10.1.1.44.5740&rep=rep1&type=ps |
| 1132 // and | 958 // and |
| 1133 // http://www.cs.mtu.edu/~shene/COURSES/cs3621/NOTES/spline/NURBS/RB-conics.html | 959 // http://www.cs.mtu.edu/~shene/COURSES/cs3621/NOTES/spline/NURBS/RB-conics.html |
| 1134 // | 960 // |
| 1135 // F = (A (1 - t)^2 + C t^2 + 2 B (1 - t) t w) | 961 // F = (A (1 - t)^2 + C t^2 + 2 B (1 - t) t w) |
| 1136 // ------------------------------------------ | 962 // ------------------------------------------ |
| (...skipping 455 matching lines...) Expand 10 before | Expand all | Expand 10 after Loading... |
| 1592 matrix.preScale(SK_Scalar1, -SK_Scalar1); | 1418 matrix.preScale(SK_Scalar1, -SK_Scalar1); |
| 1593 } | 1419 } |
| 1594 if (userMatrix) { | 1420 if (userMatrix) { |
| 1595 matrix.postConcat(*userMatrix); | 1421 matrix.postConcat(*userMatrix); |
| 1596 } | 1422 } |
| 1597 for (int i = 0; i < conicCount; ++i) { | 1423 for (int i = 0; i < conicCount; ++i) { |
| 1598 matrix.mapPoints(dst[i].fPts, 3); | 1424 matrix.mapPoints(dst[i].fPts, 3); |
| 1599 } | 1425 } |
| 1600 return conicCount; | 1426 return conicCount; |
| 1601 } | 1427 } |
| OLD | NEW |