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 |