epoger@google.com | ec3ed6a | 2011-07-28 14:26:00 +0000 | [diff] [blame] | 1 | /* |
| 2 | * Copyright 2006 The Android Open Source Project |
| 3 | * |
| 4 | * Use of this source code is governed by a BSD-style license that can be |
| 5 | * found in the LICENSE file. |
| 6 | */ |
| 7 | |
reed@android.com | 8a1c16f | 2008-12-17 15:59:43 +0000 | [diff] [blame] | 8 | #include "SkStrokerPriv.h" |
| 9 | #include "SkGeometry.h" |
| 10 | #include "SkPath.h" |
Cary Clark | df429f3 | 2017-11-08 11:44:31 -0500 | [diff] [blame] | 11 | #include "SkPointPriv.h" |
reed@android.com | 8a1c16f | 2008-12-17 15:59:43 +0000 | [diff] [blame] | 12 | |
Ben Wagner | f08d1d0 | 2018-06-18 15:11:00 -0400 | [diff] [blame] | 13 | #include <utility> |
| 14 | |
Mike Reed | a99b6ce | 2017-02-04 11:04:26 -0500 | [diff] [blame] | 15 | static void ButtCapper(SkPath* path, const SkPoint& pivot, const SkVector& normal, |
| 16 | const SkPoint& stop, SkPath*) { |
reed@android.com | 8a1c16f | 2008-12-17 15:59:43 +0000 | [diff] [blame] | 17 | path->lineTo(stop.fX, stop.fY); |
| 18 | } |
| 19 | |
Mike Reed | a99b6ce | 2017-02-04 11:04:26 -0500 | [diff] [blame] | 20 | static void RoundCapper(SkPath* path, const SkPoint& pivot, const SkVector& normal, |
| 21 | const SkPoint& stop, SkPath*) { |
reed | 88f0a99 | 2015-02-10 08:45:06 -0800 | [diff] [blame] | 22 | SkVector parallel; |
Cary Clark | df429f3 | 2017-11-08 11:44:31 -0500 | [diff] [blame] | 23 | SkPointPriv::RotateCW(normal, ¶llel); |
reed | 88f0a99 | 2015-02-10 08:45:06 -0800 | [diff] [blame] | 24 | |
| 25 | SkPoint projectedCenter = pivot + parallel; |
| 26 | |
| 27 | path->conicTo(projectedCenter + normal, projectedCenter, SK_ScalarRoot2Over2); |
| 28 | path->conicTo(projectedCenter - normal, stop, SK_ScalarRoot2Over2); |
reed@android.com | 8a1c16f | 2008-12-17 15:59:43 +0000 | [diff] [blame] | 29 | } |
| 30 | |
Mike Reed | a99b6ce | 2017-02-04 11:04:26 -0500 | [diff] [blame] | 31 | static void SquareCapper(SkPath* path, const SkPoint& pivot, const SkVector& normal, |
| 32 | const SkPoint& stop, SkPath* otherPath) { |
reed@android.com | 8a1c16f | 2008-12-17 15:59:43 +0000 | [diff] [blame] | 33 | SkVector parallel; |
Cary Clark | df429f3 | 2017-11-08 11:44:31 -0500 | [diff] [blame] | 34 | SkPointPriv::RotateCW(normal, ¶llel); |
reed@android.com | 8a1c16f | 2008-12-17 15:59:43 +0000 | [diff] [blame] | 35 | |
Mike Reed | a99b6ce | 2017-02-04 11:04:26 -0500 | [diff] [blame] | 36 | if (otherPath) { |
reed@android.com | 8a1c16f | 2008-12-17 15:59:43 +0000 | [diff] [blame] | 37 | path->setLastPt(pivot.fX + normal.fX + parallel.fX, pivot.fY + normal.fY + parallel.fY); |
| 38 | path->lineTo(pivot.fX - normal.fX + parallel.fX, pivot.fY - normal.fY + parallel.fY); |
Mike Reed | a99b6ce | 2017-02-04 11:04:26 -0500 | [diff] [blame] | 39 | } else { |
reed@android.com | 8a1c16f | 2008-12-17 15:59:43 +0000 | [diff] [blame] | 40 | path->lineTo(pivot.fX + normal.fX + parallel.fX, pivot.fY + normal.fY + parallel.fY); |
| 41 | path->lineTo(pivot.fX - normal.fX + parallel.fX, pivot.fY - normal.fY + parallel.fY); |
| 42 | path->lineTo(stop.fX, stop.fY); |
| 43 | } |
| 44 | } |
| 45 | |
| 46 | ///////////////////////////////////////////////////////////////////////////// |
| 47 | |
Mike Reed | a99b6ce | 2017-02-04 11:04:26 -0500 | [diff] [blame] | 48 | static bool is_clockwise(const SkVector& before, const SkVector& after) { |
| 49 | return before.fX * after.fY > before.fY * after.fX; |
reed@android.com | 8a1c16f | 2008-12-17 15:59:43 +0000 | [diff] [blame] | 50 | } |
| 51 | |
| 52 | enum AngleType { |
| 53 | kNearly180_AngleType, |
| 54 | kSharp_AngleType, |
| 55 | kShallow_AngleType, |
| 56 | kNearlyLine_AngleType |
| 57 | }; |
| 58 | |
Mike Reed | a99b6ce | 2017-02-04 11:04:26 -0500 | [diff] [blame] | 59 | static AngleType Dot2AngleType(SkScalar dot) { |
reed@android.com | 8a1c16f | 2008-12-17 15:59:43 +0000 | [diff] [blame] | 60 | // need more precise fixed normalization |
| 61 | // SkASSERT(SkScalarAbs(dot) <= SK_Scalar1 + SK_ScalarNearlyZero); |
| 62 | |
Mike Reed | a99b6ce | 2017-02-04 11:04:26 -0500 | [diff] [blame] | 63 | if (dot >= 0) { // shallow or line |
reed@android.com | 8a1c16f | 2008-12-17 15:59:43 +0000 | [diff] [blame] | 64 | return SkScalarNearlyZero(SK_Scalar1 - dot) ? kNearlyLine_AngleType : kShallow_AngleType; |
Mike Reed | a99b6ce | 2017-02-04 11:04:26 -0500 | [diff] [blame] | 65 | } else { // sharp or 180 |
reed@android.com | 8a1c16f | 2008-12-17 15:59:43 +0000 | [diff] [blame] | 66 | return SkScalarNearlyZero(SK_Scalar1 + dot) ? kNearly180_AngleType : kSharp_AngleType; |
Mike Reed | a99b6ce | 2017-02-04 11:04:26 -0500 | [diff] [blame] | 67 | } |
reed@android.com | 8a1c16f | 2008-12-17 15:59:43 +0000 | [diff] [blame] | 68 | } |
| 69 | |
Mike Reed | a99b6ce | 2017-02-04 11:04:26 -0500 | [diff] [blame] | 70 | static void HandleInnerJoin(SkPath* inner, const SkPoint& pivot, const SkVector& after) { |
reed@android.com | 8a1c16f | 2008-12-17 15:59:43 +0000 | [diff] [blame] | 71 | #if 1 |
| 72 | /* In the degenerate case that the stroke radius is larger than our segments |
| 73 | just connecting the two inner segments may "show through" as a funny |
| 74 | diagonal. To pseudo-fix this, we go through the pivot point. This adds |
| 75 | an extra point/edge, but I can't see a cheap way to know when this is |
| 76 | not needed :( |
| 77 | */ |
| 78 | inner->lineTo(pivot.fX, pivot.fY); |
| 79 | #endif |
| 80 | |
| 81 | inner->lineTo(pivot.fX - after.fX, pivot.fY - after.fY); |
| 82 | } |
| 83 | |
| 84 | static void BluntJoiner(SkPath* outer, SkPath* inner, const SkVector& beforeUnitNormal, |
| 85 | const SkPoint& pivot, const SkVector& afterUnitNormal, |
Mike Reed | a99b6ce | 2017-02-04 11:04:26 -0500 | [diff] [blame] | 86 | SkScalar radius, SkScalar invMiterLimit, bool, bool) { |
reed@android.com | 8a1c16f | 2008-12-17 15:59:43 +0000 | [diff] [blame] | 87 | SkVector after; |
| 88 | afterUnitNormal.scale(radius, &after); |
| 89 | |
Mike Reed | a99b6ce | 2017-02-04 11:04:26 -0500 | [diff] [blame] | 90 | if (!is_clockwise(beforeUnitNormal, afterUnitNormal)) { |
Ben Wagner | f08d1d0 | 2018-06-18 15:11:00 -0400 | [diff] [blame] | 91 | using std::swap; |
| 92 | swap(outer, inner); |
reed@android.com | 8a1c16f | 2008-12-17 15:59:43 +0000 | [diff] [blame] | 93 | after.negate(); |
| 94 | } |
| 95 | |
| 96 | outer->lineTo(pivot.fX + after.fX, pivot.fY + after.fY); |
| 97 | HandleInnerJoin(inner, pivot, after); |
| 98 | } |
| 99 | |
| 100 | static void RoundJoiner(SkPath* outer, SkPath* inner, const SkVector& beforeUnitNormal, |
| 101 | const SkPoint& pivot, const SkVector& afterUnitNormal, |
Mike Reed | a99b6ce | 2017-02-04 11:04:26 -0500 | [diff] [blame] | 102 | SkScalar radius, SkScalar invMiterLimit, bool, bool) { |
reed@android.com | 8a1c16f | 2008-12-17 15:59:43 +0000 | [diff] [blame] | 103 | SkScalar dotProd = SkPoint::DotProduct(beforeUnitNormal, afterUnitNormal); |
| 104 | AngleType angleType = Dot2AngleType(dotProd); |
| 105 | |
| 106 | if (angleType == kNearlyLine_AngleType) |
| 107 | return; |
| 108 | |
| 109 | SkVector before = beforeUnitNormal; |
| 110 | SkVector after = afterUnitNormal; |
| 111 | SkRotationDirection dir = kCW_SkRotationDirection; |
| 112 | |
Mike Reed | a99b6ce | 2017-02-04 11:04:26 -0500 | [diff] [blame] | 113 | if (!is_clockwise(before, after)) { |
Ben Wagner | f08d1d0 | 2018-06-18 15:11:00 -0400 | [diff] [blame] | 114 | using std::swap; |
| 115 | swap(outer, inner); |
reed@android.com | 8a1c16f | 2008-12-17 15:59:43 +0000 | [diff] [blame] | 116 | before.negate(); |
| 117 | after.negate(); |
| 118 | dir = kCCW_SkRotationDirection; |
| 119 | } |
| 120 | |
reed@android.com | 8a1c16f | 2008-12-17 15:59:43 +0000 | [diff] [blame] | 121 | SkMatrix matrix; |
| 122 | matrix.setScale(radius, radius); |
| 123 | matrix.postTranslate(pivot.fX, pivot.fY); |
reed | 88f0a99 | 2015-02-10 08:45:06 -0800 | [diff] [blame] | 124 | SkConic conics[SkConic::kMaxConicsForArc]; |
| 125 | int count = SkConic::BuildUnitArc(before, after, dir, &matrix, conics); |
| 126 | if (count > 0) { |
| 127 | for (int i = 0; i < count; ++i) { |
| 128 | outer->conicTo(conics[i].fPts[1], conics[i].fPts[2], conics[i].fW); |
| 129 | } |
| 130 | after.scale(radius); |
| 131 | HandleInnerJoin(inner, pivot, after); |
| 132 | } |
reed@android.com | 8a1c16f | 2008-12-17 15:59:43 +0000 | [diff] [blame] | 133 | } |
| 134 | |
reed@google.com | 8f4d230 | 2013-12-17 16:44:46 +0000 | [diff] [blame] | 135 | #define kOneOverSqrt2 (0.707106781f) |
reed@android.com | 8a1c16f | 2008-12-17 15:59:43 +0000 | [diff] [blame] | 136 | |
| 137 | static void MiterJoiner(SkPath* outer, SkPath* inner, const SkVector& beforeUnitNormal, |
| 138 | const SkPoint& pivot, const SkVector& afterUnitNormal, |
| 139 | SkScalar radius, SkScalar invMiterLimit, |
Mike Reed | a99b6ce | 2017-02-04 11:04:26 -0500 | [diff] [blame] | 140 | bool prevIsLine, bool currIsLine) { |
reed@android.com | 8a1c16f | 2008-12-17 15:59:43 +0000 | [diff] [blame] | 141 | // negate the dot since we're using normals instead of tangents |
| 142 | SkScalar dotProd = SkPoint::DotProduct(beforeUnitNormal, afterUnitNormal); |
| 143 | AngleType angleType = Dot2AngleType(dotProd); |
| 144 | SkVector before = beforeUnitNormal; |
| 145 | SkVector after = afterUnitNormal; |
| 146 | SkVector mid; |
| 147 | SkScalar sinHalfAngle; |
| 148 | bool ccw; |
| 149 | |
Mike Reed | a99b6ce | 2017-02-04 11:04:26 -0500 | [diff] [blame] | 150 | if (angleType == kNearlyLine_AngleType) { |
reed@android.com | 8a1c16f | 2008-12-17 15:59:43 +0000 | [diff] [blame] | 151 | return; |
Mike Reed | a99b6ce | 2017-02-04 11:04:26 -0500 | [diff] [blame] | 152 | } |
| 153 | if (angleType == kNearly180_AngleType) { |
reed@android.com | 8a1c16f | 2008-12-17 15:59:43 +0000 | [diff] [blame] | 154 | currIsLine = false; |
| 155 | goto DO_BLUNT; |
| 156 | } |
rmistry@google.com | fbfcd56 | 2012-08-23 18:09:54 +0000 | [diff] [blame] | 157 | |
reed@android.com | 8a1c16f | 2008-12-17 15:59:43 +0000 | [diff] [blame] | 158 | ccw = !is_clockwise(before, after); |
Mike Reed | a99b6ce | 2017-02-04 11:04:26 -0500 | [diff] [blame] | 159 | if (ccw) { |
Ben Wagner | f08d1d0 | 2018-06-18 15:11:00 -0400 | [diff] [blame] | 160 | using std::swap; |
| 161 | swap(outer, inner); |
reed@android.com | 8a1c16f | 2008-12-17 15:59:43 +0000 | [diff] [blame] | 162 | before.negate(); |
| 163 | after.negate(); |
| 164 | } |
rmistry@google.com | fbfcd56 | 2012-08-23 18:09:54 +0000 | [diff] [blame] | 165 | |
reed@android.com | 8a1c16f | 2008-12-17 15:59:43 +0000 | [diff] [blame] | 166 | /* Before we enter the world of square-roots and divides, |
| 167 | check if we're trying to join an upright right angle |
| 168 | (common case for stroking rectangles). If so, special case |
| 169 | that (for speed an accuracy). |
| 170 | Note: we only need to check one normal if dot==0 |
| 171 | */ |
Mike Reed | a99b6ce | 2017-02-04 11:04:26 -0500 | [diff] [blame] | 172 | if (0 == dotProd && invMiterLimit <= kOneOverSqrt2) { |
| 173 | mid = (before + after) * radius; |
reed@android.com | 8a1c16f | 2008-12-17 15:59:43 +0000 | [diff] [blame] | 174 | goto DO_MITER; |
| 175 | } |
| 176 | |
| 177 | /* midLength = radius / sinHalfAngle |
| 178 | if (midLength > miterLimit * radius) abort |
| 179 | if (radius / sinHalf > miterLimit * radius) abort |
| 180 | if (1 / sinHalf > miterLimit) abort |
| 181 | if (1 / miterLimit > sinHalf) abort |
| 182 | My dotProd is opposite sign, since it is built from normals and not tangents |
| 183 | hence 1 + dot instead of 1 - dot in the formula |
| 184 | */ |
| 185 | sinHalfAngle = SkScalarSqrt(SkScalarHalf(SK_Scalar1 + dotProd)); |
Mike Reed | a99b6ce | 2017-02-04 11:04:26 -0500 | [diff] [blame] | 186 | if (sinHalfAngle < invMiterLimit) { |
reed@android.com | 8a1c16f | 2008-12-17 15:59:43 +0000 | [diff] [blame] | 187 | currIsLine = false; |
| 188 | goto DO_BLUNT; |
| 189 | } |
| 190 | |
| 191 | // choose the most accurate way to form the initial mid-vector |
Mike Reed | a99b6ce | 2017-02-04 11:04:26 -0500 | [diff] [blame] | 192 | if (angleType == kSharp_AngleType) { |
reed@android.com | 8a1c16f | 2008-12-17 15:59:43 +0000 | [diff] [blame] | 193 | mid.set(after.fY - before.fY, before.fX - after.fX); |
Mike Reed | a99b6ce | 2017-02-04 11:04:26 -0500 | [diff] [blame] | 194 | if (ccw) { |
reed@android.com | 8a1c16f | 2008-12-17 15:59:43 +0000 | [diff] [blame] | 195 | mid.negate(); |
Mike Reed | a99b6ce | 2017-02-04 11:04:26 -0500 | [diff] [blame] | 196 | } |
| 197 | } else { |
reed@android.com | 8a1c16f | 2008-12-17 15:59:43 +0000 | [diff] [blame] | 198 | mid.set(before.fX + after.fX, before.fY + after.fY); |
Mike Reed | a99b6ce | 2017-02-04 11:04:26 -0500 | [diff] [blame] | 199 | } |
reed@android.com | 8a1c16f | 2008-12-17 15:59:43 +0000 | [diff] [blame] | 200 | |
reed | 80ea19c | 2015-05-12 10:37:34 -0700 | [diff] [blame] | 201 | mid.setLength(radius / sinHalfAngle); |
reed@android.com | 8a1c16f | 2008-12-17 15:59:43 +0000 | [diff] [blame] | 202 | DO_MITER: |
Mike Reed | a99b6ce | 2017-02-04 11:04:26 -0500 | [diff] [blame] | 203 | if (prevIsLine) { |
reed@android.com | 8a1c16f | 2008-12-17 15:59:43 +0000 | [diff] [blame] | 204 | outer->setLastPt(pivot.fX + mid.fX, pivot.fY + mid.fY); |
Mike Reed | a99b6ce | 2017-02-04 11:04:26 -0500 | [diff] [blame] | 205 | } else { |
reed@android.com | 8a1c16f | 2008-12-17 15:59:43 +0000 | [diff] [blame] | 206 | outer->lineTo(pivot.fX + mid.fX, pivot.fY + mid.fY); |
Mike Reed | a99b6ce | 2017-02-04 11:04:26 -0500 | [diff] [blame] | 207 | } |
reed@android.com | 8a1c16f | 2008-12-17 15:59:43 +0000 | [diff] [blame] | 208 | |
| 209 | DO_BLUNT: |
| 210 | after.scale(radius); |
Mike Reed | a99b6ce | 2017-02-04 11:04:26 -0500 | [diff] [blame] | 211 | if (!currIsLine) { |
reed@android.com | 8a1c16f | 2008-12-17 15:59:43 +0000 | [diff] [blame] | 212 | outer->lineTo(pivot.fX + after.fX, pivot.fY + after.fY); |
Mike Reed | a99b6ce | 2017-02-04 11:04:26 -0500 | [diff] [blame] | 213 | } |
reed@android.com | 8a1c16f | 2008-12-17 15:59:43 +0000 | [diff] [blame] | 214 | HandleInnerJoin(inner, pivot, after); |
| 215 | } |
| 216 | |
| 217 | ///////////////////////////////////////////////////////////////////////////// |
| 218 | |
Mike Reed | a99b6ce | 2017-02-04 11:04:26 -0500 | [diff] [blame] | 219 | SkStrokerPriv::CapProc SkStrokerPriv::CapFactory(SkPaint::Cap cap) { |
| 220 | const SkStrokerPriv::CapProc gCappers[] = { |
reed@android.com | 8a1c16f | 2008-12-17 15:59:43 +0000 | [diff] [blame] | 221 | ButtCapper, RoundCapper, SquareCapper |
| 222 | }; |
| 223 | |
| 224 | SkASSERT((unsigned)cap < SkPaint::kCapCount); |
| 225 | return gCappers[cap]; |
| 226 | } |
| 227 | |
Mike Reed | a99b6ce | 2017-02-04 11:04:26 -0500 | [diff] [blame] | 228 | SkStrokerPriv::JoinProc SkStrokerPriv::JoinFactory(SkPaint::Join join) { |
| 229 | const SkStrokerPriv::JoinProc gJoiners[] = { |
reed@android.com | 8a1c16f | 2008-12-17 15:59:43 +0000 | [diff] [blame] | 230 | MiterJoiner, RoundJoiner, BluntJoiner |
| 231 | }; |
| 232 | |
| 233 | SkASSERT((unsigned)join < SkPaint::kJoinCount); |
| 234 | return gJoiners[join]; |
| 235 | } |