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#ifdef SK_SCALAR_IS_FLOAT
157    #define kOneOverSqrt2   (0.707106781f)
158#else
159    #define kOneOverSqrt2   (46341)
160#endif
161
162static void MiterJoiner(SkPath* outer, SkPath* inner, const SkVector& beforeUnitNormal,
163                        const SkPoint& pivot, const SkVector& afterUnitNormal,
164                        SkScalar radius, SkScalar invMiterLimit,
165                        bool prevIsLine, bool currIsLine)
166{
167    // negate the dot since we're using normals instead of tangents
168    SkScalar    dotProd = SkPoint::DotProduct(beforeUnitNormal, afterUnitNormal);
169    AngleType   angleType = Dot2AngleType(dotProd);
170    SkVector    before = beforeUnitNormal;
171    SkVector    after = afterUnitNormal;
172    SkVector    mid;
173    SkScalar    sinHalfAngle;
174    bool        ccw;
175
176    if (angleType == kNearlyLine_AngleType)
177        return;
178    if (angleType == kNearly180_AngleType)
179    {
180        currIsLine = false;
181        goto DO_BLUNT;
182    }
183
184    ccw = !is_clockwise(before, after);
185    if (ccw)
186    {
187        SkTSwap<SkPath*>(outer, inner);
188        before.negate();
189        after.negate();
190    }
191
192    /*  Before we enter the world of square-roots and divides,
193        check if we're trying to join an upright right angle
194        (common case for stroking rectangles). If so, special case
195        that (for speed an accuracy).
196        Note: we only need to check one normal if dot==0
197    */
198    if (0 == dotProd && invMiterLimit <= kOneOverSqrt2)
199    {
200        mid.set(SkScalarMul(before.fX + after.fX, radius),
201                SkScalarMul(before.fY + after.fY, radius));
202        goto DO_MITER;
203    }
204
205    /*  midLength = radius / sinHalfAngle
206        if (midLength > miterLimit * radius) abort
207        if (radius / sinHalf > miterLimit * radius) abort
208        if (1 / sinHalf > miterLimit) abort
209        if (1 / miterLimit > sinHalf) abort
210        My dotProd is opposite sign, since it is built from normals and not tangents
211        hence 1 + dot instead of 1 - dot in the formula
212    */
213    sinHalfAngle = SkScalarSqrt(SkScalarHalf(SK_Scalar1 + dotProd));
214    if (sinHalfAngle < invMiterLimit)
215    {
216        currIsLine = false;
217        goto DO_BLUNT;
218    }
219
220    // choose the most accurate way to form the initial mid-vector
221    if (angleType == kSharp_AngleType)
222    {
223        mid.set(after.fY - before.fY, before.fX - after.fX);
224        if (ccw)
225            mid.negate();
226    }
227    else
228        mid.set(before.fX + after.fX, before.fY + after.fY);
229
230    mid.setLength(SkScalarDiv(radius, sinHalfAngle));
231DO_MITER:
232    if (prevIsLine)
233        outer->setLastPt(pivot.fX + mid.fX, pivot.fY + mid.fY);
234    else
235        outer->lineTo(pivot.fX + mid.fX, pivot.fY + mid.fY);
236
237DO_BLUNT:
238    after.scale(radius);
239    if (!currIsLine)
240        outer->lineTo(pivot.fX + after.fX, pivot.fY + after.fY);
241    HandleInnerJoin(inner, pivot, after);
242}
243
244/////////////////////////////////////////////////////////////////////////////
245
246SkStrokerPriv::CapProc SkStrokerPriv::CapFactory(SkPaint::Cap cap)
247{
248    static const SkStrokerPriv::CapProc gCappers[] = {
249        ButtCapper, RoundCapper, SquareCapper
250    };
251
252    SkASSERT((unsigned)cap < SkPaint::kCapCount);
253    return gCappers[cap];
254}
255
256SkStrokerPriv::JoinProc SkStrokerPriv::JoinFactory(SkPaint::Join join)
257{
258    static const SkStrokerPriv::JoinProc gJoiners[] = {
259        MiterJoiner, RoundJoiner, BluntJoiner
260    };
261
262    SkASSERT((unsigned)join < SkPaint::kJoinCount);
263    return gJoiners[join];
264}
265