1 /* libs/graphics/sgl/SkStrokerPriv.cpp 2 ** 3 ** Copyright 2006, The Android Open Source Project 4 ** 5 ** Licensed under the Apache License, Version 2.0 (the "License"); 6 ** you may not use this file except in compliance with the License. 7 ** You may obtain a copy of the License at 8 ** 9 ** http://www.apache.org/licenses/LICENSE-2.0 10 ** 11 ** Unless required by applicable law or agreed to in writing, software 12 ** distributed under the License is distributed on an "AS IS" BASIS, 13 ** WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied. 14 ** See the License for the specific language governing permissions and 15 ** limitations under the License. 16 */ 17 18 #include "SkStrokerPriv.h" 19 #include "SkGeometry.h" 20 #include "SkPath.h" 21 22 static void ButtCapper(SkPath* path, const SkPoint& pivot, 23 const SkVector& normal, const SkPoint& stop, 24 SkPath*) 25 { 26 path->lineTo(stop.fX, stop.fY); 27 } 28 29 static void RoundCapper(SkPath* path, const SkPoint& pivot, 30 const SkVector& normal, const SkPoint& stop, 31 SkPath*) 32 { 33 SkScalar px = pivot.fX; 34 SkScalar py = pivot.fY; 35 SkScalar nx = normal.fX; 36 SkScalar ny = normal.fY; 37 SkScalar sx = SkScalarMul(nx, CUBIC_ARC_FACTOR); 38 SkScalar sy = SkScalarMul(ny, CUBIC_ARC_FACTOR); 39 40 path->cubicTo(px + nx + CWX(sx, sy), py + ny + CWY(sx, sy), 41 px + CWX(nx, ny) + sx, py + CWY(nx, ny) + sy, 42 px + CWX(nx, ny), py + CWY(nx, ny)); 43 path->cubicTo(px + CWX(nx, ny) - sx, py + CWY(nx, ny) - sy, 44 px - nx + CWX(sx, sy), py - ny + CWY(sx, sy), 45 stop.fX, stop.fY); 46 } 47 48 static void SquareCapper(SkPath* path, const SkPoint& pivot, 49 const SkVector& normal, const SkPoint& stop, 50 SkPath* otherPath) 51 { 52 SkVector parallel; 53 normal.rotateCW(¶llel); 54 55 if (otherPath) 56 { 57 path->setLastPt(pivot.fX + normal.fX + parallel.fX, pivot.fY + normal.fY + parallel.fY); 58 path->lineTo(pivot.fX - normal.fX + parallel.fX, pivot.fY - normal.fY + parallel.fY); 59 } 60 else 61 { 62 path->lineTo(pivot.fX + normal.fX + parallel.fX, pivot.fY + normal.fY + parallel.fY); 63 path->lineTo(pivot.fX - normal.fX + parallel.fX, pivot.fY - normal.fY + parallel.fY); 64 path->lineTo(stop.fX, stop.fY); 65 } 66 } 67 68 ///////////////////////////////////////////////////////////////////////////// 69 70 static bool is_clockwise(const SkVector& before, const SkVector& after) 71 { 72 return SkScalarMul(before.fX, after.fY) - SkScalarMul(before.fY, after.fX) > 0; 73 } 74 75 enum AngleType { 76 kNearly180_AngleType, 77 kSharp_AngleType, 78 kShallow_AngleType, 79 kNearlyLine_AngleType 80 }; 81 82 static AngleType Dot2AngleType(SkScalar dot) 83 { 84 // need more precise fixed normalization 85 // SkASSERT(SkScalarAbs(dot) <= SK_Scalar1 + SK_ScalarNearlyZero); 86 87 if (dot >= 0) // shallow or line 88 return SkScalarNearlyZero(SK_Scalar1 - dot) ? kNearlyLine_AngleType : kShallow_AngleType; 89 else // sharp or 180 90 return SkScalarNearlyZero(SK_Scalar1 + dot) ? kNearly180_AngleType : kSharp_AngleType; 91 } 92 93 static void HandleInnerJoin(SkPath* inner, const SkPoint& pivot, const SkVector& after) 94 { 95 #if 1 96 /* In the degenerate case that the stroke radius is larger than our segments 97 just connecting the two inner segments may "show through" as a funny 98 diagonal. To pseudo-fix this, we go through the pivot point. This adds 99 an extra point/edge, but I can't see a cheap way to know when this is 100 not needed :( 101 */ 102 inner->lineTo(pivot.fX, pivot.fY); 103 #endif 104 105 inner->lineTo(pivot.fX - after.fX, pivot.fY - after.fY); 106 } 107 108 static void BluntJoiner(SkPath* outer, SkPath* inner, const SkVector& beforeUnitNormal, 109 const SkPoint& pivot, const SkVector& afterUnitNormal, 110 SkScalar radius, SkScalar invMiterLimit, bool, bool) 111 { 112 SkVector after; 113 afterUnitNormal.scale(radius, &after); 114 115 if (!is_clockwise(beforeUnitNormal, afterUnitNormal)) 116 { 117 SkTSwap<SkPath*>(outer, inner); 118 after.negate(); 119 } 120 121 outer->lineTo(pivot.fX + after.fX, pivot.fY + after.fY); 122 HandleInnerJoin(inner, pivot, after); 123 } 124 125 static void RoundJoiner(SkPath* outer, SkPath* inner, const SkVector& beforeUnitNormal, 126 const SkPoint& pivot, const SkVector& afterUnitNormal, 127 SkScalar radius, SkScalar invMiterLimit, bool, bool) 128 { 129 SkScalar dotProd = SkPoint::DotProduct(beforeUnitNormal, afterUnitNormal); 130 AngleType angleType = Dot2AngleType(dotProd); 131 132 if (angleType == kNearlyLine_AngleType) 133 return; 134 135 SkVector before = beforeUnitNormal; 136 SkVector after = afterUnitNormal; 137 SkRotationDirection dir = kCW_SkRotationDirection; 138 139 if (!is_clockwise(before, after)) 140 { 141 SkTSwap<SkPath*>(outer, inner); 142 before.negate(); 143 after.negate(); 144 dir = kCCW_SkRotationDirection; 145 } 146 147 SkPoint pts[kSkBuildQuadArcStorage]; 148 SkMatrix matrix; 149 matrix.setScale(radius, radius); 150 matrix.postTranslate(pivot.fX, pivot.fY); 151 int count = SkBuildQuadArc(before, after, dir, &matrix, pts); 152 SkASSERT((count & 1) == 1); 153 154 if (count > 1) 155 { 156 for (int i = 1; i < count; i += 2) 157 outer->quadTo(pts[i].fX, pts[i].fY, pts[i+1].fX, pts[i+1].fY); 158 159 after.scale(radius); 160 HandleInnerJoin(inner, pivot, after); 161 } 162 } 163 164 #ifdef SK_SCALAR_IS_FLOAT 165 #define kOneOverSqrt2 (0.707106781f) 166 #else 167 #define kOneOverSqrt2 (46341) 168 #endif 169 170 static void MiterJoiner(SkPath* outer, SkPath* inner, const SkVector& beforeUnitNormal, 171 const SkPoint& pivot, const SkVector& afterUnitNormal, 172 SkScalar radius, SkScalar invMiterLimit, 173 bool prevIsLine, bool currIsLine) 174 { 175 // negate the dot since we're using normals instead of tangents 176 SkScalar dotProd = SkPoint::DotProduct(beforeUnitNormal, afterUnitNormal); 177 AngleType angleType = Dot2AngleType(dotProd); 178 SkVector before = beforeUnitNormal; 179 SkVector after = afterUnitNormal; 180 SkVector mid; 181 SkScalar sinHalfAngle; 182 bool ccw; 183 184 if (angleType == kNearlyLine_AngleType) 185 return; 186 if (angleType == kNearly180_AngleType) 187 { 188 currIsLine = false; 189 goto DO_BLUNT; 190 } 191 192 ccw = !is_clockwise(before, after); 193 if (ccw) 194 { 195 SkTSwap<SkPath*>(outer, inner); 196 before.negate(); 197 after.negate(); 198 } 199 200 /* Before we enter the world of square-roots and divides, 201 check if we're trying to join an upright right angle 202 (common case for stroking rectangles). If so, special case 203 that (for speed an accuracy). 204 Note: we only need to check one normal if dot==0 205 */ 206 if (0 == dotProd && invMiterLimit <= kOneOverSqrt2) 207 { 208 mid.set(SkScalarMul(before.fX + after.fX, radius), 209 SkScalarMul(before.fY + after.fY, radius)); 210 goto DO_MITER; 211 } 212 213 /* midLength = radius / sinHalfAngle 214 if (midLength > miterLimit * radius) abort 215 if (radius / sinHalf > miterLimit * radius) abort 216 if (1 / sinHalf > miterLimit) abort 217 if (1 / miterLimit > sinHalf) abort 218 My dotProd is opposite sign, since it is built from normals and not tangents 219 hence 1 + dot instead of 1 - dot in the formula 220 */ 221 sinHalfAngle = SkScalarSqrt(SkScalarHalf(SK_Scalar1 + dotProd)); 222 if (sinHalfAngle < invMiterLimit) 223 { 224 currIsLine = false; 225 goto DO_BLUNT; 226 } 227 228 // choose the most accurate way to form the initial mid-vector 229 if (angleType == kSharp_AngleType) 230 { 231 mid.set(after.fY - before.fY, before.fX - after.fX); 232 if (ccw) 233 mid.negate(); 234 } 235 else 236 mid.set(before.fX + after.fX, before.fY + after.fY); 237 238 mid.setLength(SkScalarDiv(radius, sinHalfAngle)); 239 DO_MITER: 240 if (prevIsLine) 241 outer->setLastPt(pivot.fX + mid.fX, pivot.fY + mid.fY); 242 else 243 outer->lineTo(pivot.fX + mid.fX, pivot.fY + mid.fY); 244 245 DO_BLUNT: 246 after.scale(radius); 247 if (!currIsLine) 248 outer->lineTo(pivot.fX + after.fX, pivot.fY + after.fY); 249 HandleInnerJoin(inner, pivot, after); 250 } 251 252 ///////////////////////////////////////////////////////////////////////////// 253 254 SkStrokerPriv::CapProc SkStrokerPriv::CapFactory(SkPaint::Cap cap) 255 { 256 static const SkStrokerPriv::CapProc gCappers[] = { 257 ButtCapper, RoundCapper, SquareCapper 258 }; 259 260 SkASSERT((unsigned)cap < SkPaint::kCapCount); 261 return gCappers[cap]; 262 } 263 264 SkStrokerPriv::JoinProc SkStrokerPriv::JoinFactory(SkPaint::Join join) 265 { 266 static const SkStrokerPriv::JoinProc gJoiners[] = { 267 MiterJoiner, RoundJoiner, BluntJoiner 268 }; 269 270 SkASSERT((unsigned)join < SkPaint::kJoinCount); 271 return gJoiners[join]; 272 } 273 274 275 276