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
12static void ButtCapper(SkPath* path, const SkPoint& pivot, const SkVector& normal,
13                       const SkPoint& stop, SkPath*) {
14    path->lineTo(stop.fX, stop.fY);
15}
16
17static void RoundCapper(SkPath* path, const SkPoint& pivot, const SkVector& normal,
18                        const SkPoint& stop, SkPath*) {
19    SkVector parallel;
20    normal.rotateCW(&parallel);
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
28static void SquareCapper(SkPath* path, const SkPoint& pivot, const SkVector& normal,
29                         const SkPoint& stop, SkPath* otherPath) {
30    SkVector parallel;
31    normal.rotateCW(&parallel);
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
45static bool is_clockwise(const SkVector& before, const SkVector& after) {
46    return before.fX * after.fY > before.fY * after.fX;
47}
48
49enum AngleType {
50    kNearly180_AngleType,
51    kSharp_AngleType,
52    kShallow_AngleType,
53    kNearlyLine_AngleType
54};
55
56static 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
67static 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
81static 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
96static 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
132static 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);
196DO_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
203DO_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
213SkStrokerPriv::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
222SkStrokerPriv::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