GrStrokePathRenderer.cpp revision af3a3b9fb1f3be46082013a2d1977d12faf1f61c 
1/*
2 * Copyright 2012 Google Inc.
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 "GrStrokePathRenderer.h"
9
10#include "GrDrawTarget.h"
11#include "SkPath.h"
12#include "SkStrokeRec.h"
13
14namespace {
15
16bool is_clockwise(const SkVector& before, const SkVector& after) {
17    return before.cross(after) > 0;
18}
19
20enum IntersectionType {
21    kNone_IntersectionType,
22    kIn_IntersectionType,
23    kOut_IntersectionType
24};
25
26IntersectionType intersection(const SkPoint& p1, const SkPoint& p2,
27                              const SkPoint& p3, const SkPoint& p4,
28                                    SkPoint& res) {
29    // Store the values for fast access and easy
30    // equations-to-code conversion
31    SkScalar x1 = p1.x(), x2 = p2.x(), x3 = p3.x(), x4 = p4.x();
32    SkScalar y1 = p1.y(), y2 = p2.y(), y3 = p3.y(), y4 = p4.y();
33
34    SkScalar d = SkScalarMul(x1 - x2, y3 - y4) - SkScalarMul(y1 - y2, x3 - x4);
35    // If d is zero, there is no intersection
36    if (SkScalarNearlyZero(d)) {
37        return kNone_IntersectionType;
38    }
39
40    // Get the x and y
41    SkScalar pre  = SkScalarMul(x1, y2) - SkScalarMul(y1, x2),
42             post = SkScalarMul(x3, y4) - SkScalarMul(y3, x4);
43    // Compute the point of intersection
44    res.set(SkScalarDiv(SkScalarMul(pre, x3 - x4) - SkScalarMul(x1 - x2, post), d),
45            SkScalarDiv(SkScalarMul(pre, y3 - y4) - SkScalarMul(y1 - y2, post), d));
46
47    // Check if the x and y coordinates are within both lines
48    return (res.x() < GrMin(x1, x2) || res.x() > GrMax(x1, x2) ||
49            res.x() < GrMin(x3, x4) || res.x() > GrMax(x3, x4) ||
50            res.y() < GrMin(y1, y2) || res.y() > GrMax(y1, y2) ||
51            res.y() < GrMin(y3, y4) || res.y() > GrMax(y3, y4)) ?
52            kOut_IntersectionType : kIn_IntersectionType;
53}
54
55} // namespace
56
57GrStrokePathRenderer::GrStrokePathRenderer() {
58}
59
60bool GrStrokePathRenderer::canDrawPath(const SkPath& path,
61                                       const SkStrokeRec& stroke,
62                                       const GrDrawTarget* target,
63                                       bool antiAlias) const {
64    // FIXME : put the proper condition once GrDrawTarget::isOpaque is implemented
65    const bool isOpaque = true; // target->isOpaque();
66
67    // FIXME : remove this requirement once we have AA circles and implement the
68    //         circle joins/caps appropriately in the ::onDrawPath() function.
69    const bool requiresAACircle = (stroke.getCap()  == SkPaint::kRound_Cap) ||
70                                  (stroke.getJoin() == SkPaint::kRound_Join);
71
72    // Indices being stored in uint16, we don't want to overflow the indices capacity
73    static const int maxVBSize = 1 << 16;
74    const int maxNbVerts = (path.countPoints() + 1) * 5;
75
76    // Check that the path contains no curved lines, only straight lines
77    static const uint32_t unsupportedMask = SkPath::kQuad_SegmentMask | SkPath::kCubic_SegmentMask;
78
79    // Must not be filled nor hairline nor semi-transparent
80    // Note : May require a check to path.isConvex() if AA is supported
81    return ((stroke.getStyle() == SkStrokeRec::kStroke_Style) && (maxNbVerts < maxVBSize) &&
82            !path.isInverseFillType() && isOpaque && !requiresAACircle && !antiAlias &&
83            ((path.getSegmentMasks() & unsupportedMask) == 0));
84}
85
86bool GrStrokePathRenderer::onDrawPath(const SkPath& origPath,
87                                      const SkStrokeRec& stroke,
88                                      GrDrawTarget* target,
89                                      bool antiAlias) {
90    if (origPath.isEmpty()) {
91        return true;
92    }
93
94    SkScalar width = stroke.getWidth();
95    if (width <= 0) {
96        return false;
97    }
98
99    // Get the join type
100    SkPaint::Join join = stroke.getJoin();
101    SkScalar miterLimit = stroke.getMiter();
102    SkScalar sqMiterLimit = SkScalarMul(miterLimit, miterLimit);
103    if ((join == SkPaint::kMiter_Join) && (miterLimit <= SK_Scalar1)) {
104        // If the miter limit is small, treat it as a bevel join
105        join = SkPaint::kBevel_Join;
106    }
107    const bool isMiter       = (join == SkPaint::kMiter_Join);
108    const bool isBevel       = (join == SkPaint::kBevel_Join);
109    SkScalar invMiterLimit   = isMiter ? SK_Scalar1 / miterLimit : 0;
110    SkScalar invMiterLimitSq = SkScalarMul(invMiterLimit, invMiterLimit);
111
112    // Allocate vertices
113    const int nbQuads     = origPath.countPoints() + 1; // Could be "-1" if path is not closed
114    GrVertexLayout layout = 0; // Just 3D points
115    const int extraVerts  = isMiter || isBevel ? 1 : 0;
116    const int maxVertexCount = nbQuads * (4 + extraVerts);
117    const int maxIndexCount  = nbQuads * (6 + extraVerts * 3); // Each extra vert adds a triangle
118    GrDrawTarget::AutoReleaseGeometry arg(target, layout, maxVertexCount, maxIndexCount);
119    if (!arg.succeeded()) {
120        return false;
121    }
122    SkPoint* verts = reinterpret_cast<SkPoint*>(arg.vertices());
123    uint16_t* idxs = reinterpret_cast<uint16_t*>(arg.indices());
124    int vCount = 0, iCount = 0;
125
126    // Transform the path into a list of triangles
127    SkPath::Iter iter(origPath, false);
128    SkPoint pts[4];
129    const SkScalar radius = SkScalarMul(width, 0.5);
130    SkPoint *firstPt = verts, *lastPt = NULL;
131    SkVector firstDir, dir;
132    firstDir.set(0, 0);
133    dir.set(0, 0);
134    bool isOpen = true;
135    for(SkPath::Verb v = iter.next(pts); v != SkPath::kDone_Verb; v = iter.next(pts)) {
136        switch(v) {
137            case SkPath::kMove_Verb:
138                // This will already be handled as pts[0] of the 1st line
139                break;
140            case SkPath::kClose_Verb:
141                isOpen = (lastPt == NULL);
142                break;
143            case SkPath::kLine_Verb:
144            {
145                SkVector v0 = dir;
146                dir = pts[1] - pts[0];
147                if (dir.setLength(radius)) {
148                    SkVector dirT;
149                    dirT.set(dir.fY, -dir.fX); // Get perpendicular direction
150                    SkPoint l1a = pts[0]+dirT, l1b = pts[1]+dirT,
151                            l2a = pts[0]-dirT, l2b = pts[1]-dirT;
152                    SkPoint miterPt[2];
153                    bool useMiterPoint = false;
154                    int idx0(-1), idx1(-1);
155                    if (NULL == lastPt) {
156                        firstDir = dir;
157                    } else {
158                        SkVector v1 = dir;
159                        if (v0.normalize() && v1.normalize()) {
160                            SkScalar dotProd = v0.dot(v1);
161                            // No need for bevel or miter join if the angle
162                            // is either 0 or 180 degrees
163                            if (!SkScalarNearlyZero(dotProd + SK_Scalar1) &&
164                                !SkScalarNearlyZero(dotProd - SK_Scalar1)) {
165                                bool ccw = !is_clockwise(v0, v1);
166                                int offset = ccw ? 1 : 0;
167                                idx0 = vCount-2+offset;
168                                idx1 = vCount+offset;
169                                const SkPoint* pt0 = &(lastPt[offset]);
170                                const SkPoint* pt1 = ccw ? &l2a : &l1a;
171                                switch(join) {
172                                    case SkPaint::kMiter_Join:
173                                    {
174                                        // *Note : Logic is from MiterJoiner
175
176                                        // FIXME : Special case if we have a right angle ?
177                                        // if (SkScalarNearlyZero(dotProd)) {...}
178
179                                        SkScalar sinHalfAngleSq =
180                                                SkScalarHalf(SK_Scalar1 + dotProd);
181                                        if (sinHalfAngleSq >= invMiterLimitSq) {
182                                            // Find the miter point (or points if it is further
183                                            // than the miter limit)
184                                            const SkPoint pt2 = *pt0+v0, pt3 = *pt1+v1;
185                                            if (intersection(*pt0, pt2, *pt1, pt3, miterPt[0]) !=
186                                                kNone_IntersectionType) {
187                                                SkPoint miterPt0 = miterPt[0] - *pt0;
188                                                SkPoint miterPt1 = miterPt[0] - *pt1;
189                                                SkScalar sqDist0 = miterPt0.dot(miterPt0);
190                                                SkScalar sqDist1 = miterPt1.dot(miterPt1);
191                                                const SkScalar rSq =
192                                                        SkScalarDiv(SkScalarMul(radius, radius),
193                                                                    sinHalfAngleSq);
194                                                const SkScalar sqRLimit =
195                                                        SkScalarMul(sqMiterLimit, rSq);
196                                                if (sqDist0 > sqRLimit || sqDist1 > sqRLimit) {
197                                                    if (sqDist1 > sqRLimit) {
198                                                        v1.setLength(SkScalarSqrt(sqRLimit));
199                                                        miterPt[1] = *pt1+v1;
200                                                    } else {
201                                                        miterPt[1] = miterPt[0];
202                                                    }
203                                                    if (sqDist0 > sqRLimit) {
204                                                        v0.setLength(SkScalarSqrt(sqRLimit));
205                                                        miterPt[0] = *pt0+v0;
206                                                    }
207                                                } else {
208                                                    miterPt[1] = miterPt[0];
209                                                }
210                                                useMiterPoint = true;
211                                            }
212                                        }
213                                        if (useMiterPoint && (miterPt[1] == miterPt[0])) {
214                                            break;
215                                        }
216                                    }
217                                    default:
218                                    case SkPaint::kBevel_Join:
219                                    {
220                                        // Note : This currently causes some overdraw where both
221                                        //        lines initially intersect. We'd need to add
222                                        //        another line intersection check here if the
223                                        //        overdraw becomes an issue instead of using the
224                                        //        current point directly.
225
226                                        // Add center point
227                                        *verts++ = pts[0]; // Use current point directly
228                                        // This idx is passed the current point so increment it
229                                        ++idx1;
230                                        // Add center triangle
231                                        *idxs++ = idx0;
232                                        *idxs++ = vCount;
233                                        *idxs++ = idx1;
234                                        vCount++;
235                                        iCount += 3;
236                                    }
237                                    break;
238                                }
239                            }
240                        }
241                    }
242                    *verts++ = l1a;
243                    *verts++ = l2a;
244                    lastPt   = verts;
245                    *verts++ = l1b;
246                    *verts++ = l2b;
247
248                    if (useMiterPoint && (idx0 >= 0) && (idx1 >= 0)) {
249                        firstPt[idx0] = miterPt[0];
250                        firstPt[idx1] = miterPt[1];
251                    }
252
253                    // 1st triangle
254                    *idxs++  = vCount+0;
255                    *idxs++  = vCount+2;
256                    *idxs++  = vCount+1;
257                    // 2nd triangle
258                    *idxs++  = vCount+1;
259                    *idxs++  = vCount+2;
260                    *idxs++  = vCount+3;
261
262                    vCount += 4;
263                    iCount += 6;
264                }
265            }
266                break;
267            case SkPath::kQuad_Verb:
268            case SkPath::kCubic_Verb:
269                GrAssert(!"Curves not supported!");
270            default:
271                // Unhandled cases
272                GrAssert(false);
273        }
274    }
275
276    if (isOpen) {
277        // Add caps
278        switch (stroke.getCap()) {
279            case SkPaint::kSquare_Cap:
280                firstPt[0] -= firstDir;
281                firstPt[1] -= firstDir;
282                lastPt [0] += dir;
283                lastPt [1] += dir;
284                break;
285            case SkPaint::kRound_Cap:
286                GrAssert(!"Round caps not supported!");
287            default: // No cap
288                break;
289        }
290    }
291
292    GrAssert(vCount <= maxVertexCount);
293    GrAssert(iCount <= maxIndexCount);
294
295    if (vCount > 0) {
296        target->drawIndexed(kTriangles_GrPrimitiveType,
297                            0,        // start vertex
298                            0,        // start index
299                            vCount,
300                            iCount);
301    }
302
303    return true;
304}
305