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