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