1
2/*
3 * Copyright 2012 Google Inc.
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#include "GrAAConvexPathRenderer.h"
10
11#include "GrContext.h"
12#include "GrDrawState.h"
13#include "GrPathUtils.h"
14#include "SkString.h"
15#include "SkTrace.h"
16
17
18GrAAConvexPathRenderer::GrAAConvexPathRenderer() {
19}
20
21namespace {
22
23struct Segment {
24    enum {
25        kLine,
26        kQuad
27    } fType;
28    // line uses one pt, quad uses 2 pts
29    GrPoint fPts[2];
30    // normal to edge ending at each pt
31    GrVec fNorms[2];
32    // is the corner where the previous segment meets this segment
33    // sharp. If so, fMid is a normalized bisector facing outward.
34    GrVec fMid;
35
36    int countPoints() {
37        return (kLine == fType) ? 1 : 2;
38    }
39    const SkPoint& endPt() const {
40        return (kLine == fType) ? fPts[0] : fPts[1];
41    };
42    const SkPoint& endNorm() const {
43        return (kLine == fType) ? fNorms[0] : fNorms[1];
44    };
45};
46
47typedef SkTArray<Segment, true> SegmentArray;
48
49void center_of_mass(const SegmentArray& segments, SkPoint* c) {
50    GrScalar area = 0;
51    SkPoint center;
52    center.set(0, 0);
53    int count = segments.count();
54    SkPoint p0;
55    if (count > 2) {
56        // We translate the polygon so that the first point is at the origin.
57        // This avoids some precision issues with small area polygons far away
58        // from the origin.
59        p0 = segments[0].endPt();
60        SkPoint pi;
61        SkPoint pj;
62        // the first and last interation of the below loop would compute
63        // zeros since the starting / ending point is (0,0). So instead we start
64        // at i=1 and make the last iteration i=count-2.
65        pj = segments[1].endPt() - p0;
66        for (int i = 1; i < count - 1; ++i) {
67            pi = pj;
68            const SkPoint pj = segments[i + 1].endPt() - p0;
69
70            GrScalar t = GrMul(pi.fX, pj.fY) - GrMul(pj.fX, pi.fY);
71            area += t;
72            center.fX += (pi.fX + pj.fX) * t;
73            center.fY += (pi.fY + pj.fY) * t;
74
75        }
76    }
77    // If the poly has no area then we instead return the average of
78    // its points.
79    if (SkScalarNearlyZero(area)) {
80        SkPoint avg;
81        avg.set(0, 0);
82        for (int i = 0; i < count; ++i) {
83            const SkPoint& pt = segments[i].endPt();
84            avg.fX += pt.fX;
85            avg.fY += pt.fY;
86        }
87        SkScalar denom = SK_Scalar1 / count;
88        avg.scale(denom);
89        *c = avg;
90    } else {
91        area *= 3;
92        area = GrScalarDiv(GR_Scalar1, area);
93        center.fX = GrScalarMul(center.fX, area);
94        center.fY = GrScalarMul(center.fY, area);
95        // undo the translate of p0 to the origin.
96        *c = center + p0;
97    }
98    GrAssert(!SkScalarIsNaN(c->fX) && !SkScalarIsNaN(c->fY));
99}
100
101void compute_vectors(SegmentArray* segments,
102                     SkPoint* fanPt,
103                     SkPath::Direction dir,
104                     int* vCount,
105                     int* iCount) {
106    center_of_mass(*segments, fanPt);
107    int count = segments->count();
108
109    // Make the normals point towards the outside
110    GrPoint::Side normSide;
111    if (dir == SkPath::kCCW_Direction) {
112        normSide = GrPoint::kRight_Side;
113    } else {
114        normSide = GrPoint::kLeft_Side;
115    }
116
117    *vCount = 0;
118    *iCount = 0;
119    // compute normals at all points
120    for (int a = 0; a < count; ++a) {
121        const Segment& sega = (*segments)[a];
122        int b = (a + 1) % count;
123        Segment& segb = (*segments)[b];
124
125        const GrPoint* prevPt = &sega.endPt();
126        int n = segb.countPoints();
127        for (int p = 0; p < n; ++p) {
128            segb.fNorms[p] = segb.fPts[p] - *prevPt;
129            segb.fNorms[p].normalize();
130            segb.fNorms[p].setOrthog(segb.fNorms[p], normSide);
131            prevPt = &segb.fPts[p];
132        }
133        if (Segment::kLine == segb.fType) {
134            *vCount += 5;
135            *iCount += 9;
136        } else {
137            *vCount += 6;
138            *iCount += 12;
139        }
140    }
141
142    // compute mid-vectors where segments meet. TODO: Detect shallow corners
143    // and leave out the wedges and close gaps by stitching segments together.
144    for (int a = 0; a < count; ++a) {
145        const Segment& sega = (*segments)[a];
146        int b = (a + 1) % count;
147        Segment& segb = (*segments)[b];
148        segb.fMid = segb.fNorms[0] + sega.endNorm();
149        segb.fMid.normalize();
150        // corner wedges
151        *vCount += 4;
152        *iCount += 6;
153    }
154}
155
156struct DegenerateTestData {
157    DegenerateTestData() { fStage = kInitial; }
158    bool isDegenerate() const { return kNonDegenerate != fStage; }
159    enum {
160        kInitial,
161        kPoint,
162        kLine,
163        kNonDegenerate
164    }           fStage;
165    GrPoint     fFirstPoint;
166    GrVec       fLineNormal;
167    GrScalar    fLineC;
168};
169
170void update_degenerate_test(DegenerateTestData* data, const GrPoint& pt) {
171    static const SkScalar TOL = (SK_Scalar1 / 16);
172    static const SkScalar TOL_SQD = SkScalarMul(TOL, TOL);
173
174    switch (data->fStage) {
175        case DegenerateTestData::kInitial:
176            data->fFirstPoint = pt;
177            data->fStage = DegenerateTestData::kPoint;
178            break;
179        case DegenerateTestData::kPoint:
180            if (pt.distanceToSqd(data->fFirstPoint) > TOL_SQD) {
181                data->fLineNormal = pt - data->fFirstPoint;
182                data->fLineNormal.normalize();
183                data->fLineNormal.setOrthog(data->fLineNormal);
184                data->fLineC = -data->fLineNormal.dot(data->fFirstPoint);
185                data->fStage = DegenerateTestData::kLine;
186            }
187            break;
188        case DegenerateTestData::kLine:
189            if (SkScalarAbs(data->fLineNormal.dot(pt) + data->fLineC) > TOL) {
190                data->fStage = DegenerateTestData::kNonDegenerate;
191            }
192        case DegenerateTestData::kNonDegenerate:
193            break;
194        default:
195            GrCrash("Unexpected degenerate test stage.");
196    }
197}
198
199bool get_segments(const GrPath& path,
200                 SegmentArray* segments,
201                 SkPoint* fanPt,
202                 int* vCount,
203                 int* iCount) {
204    SkPath::Iter iter(path, true);
205    // This renderer overemphasises very thin path regions. We use the distance
206    // to the path from the sample to compute coverage. Every pixel intersected
207    // by the path will be hit and the maximum distance is sqrt(2)/2. We don't
208    // notice that the sample may be close to a very thin area of the path and
209    // thus should be very light. This is particularly egregious for degenerate
210    // line paths. We detect paths that are very close to a line (zero area) and
211    // draw nothing.
212    DegenerateTestData degenerateData;
213
214    for (;;) {
215        GrPoint pts[4];
216        GrPathCmd cmd = (GrPathCmd)iter.next(pts);
217        switch (cmd) {
218            case kMove_PathCmd:
219                update_degenerate_test(&degenerateData, pts[0]);
220                break;
221            case kLine_PathCmd: {
222                update_degenerate_test(&degenerateData, pts[1]);
223                segments->push_back();
224                segments->back().fType = Segment::kLine;
225                segments->back().fPts[0] = pts[1];
226                break;
227            }
228            case kQuadratic_PathCmd:
229                update_degenerate_test(&degenerateData, pts[1]);
230                update_degenerate_test(&degenerateData, pts[2]);
231                segments->push_back();
232                segments->back().fType = Segment::kQuad;
233                segments->back().fPts[0] = pts[1];
234                segments->back().fPts[1] = pts[2];
235                break;
236            case kCubic_PathCmd: {
237                update_degenerate_test(&degenerateData, pts[1]);
238                update_degenerate_test(&degenerateData, pts[2]);
239                update_degenerate_test(&degenerateData, pts[3]);
240                SkSTArray<15, SkPoint, true> quads;
241                GrPathUtils::convertCubicToQuads(pts, SK_Scalar1, &quads);
242                int count = quads.count();
243                for (int q = 0; q < count; q += 3) {
244                    segments->push_back();
245                    segments->back().fType = Segment::kQuad;
246                    segments->back().fPts[0] = quads[q + 1];
247                    segments->back().fPts[1] = quads[q + 2];
248                }
249                break;
250            };
251            case kEnd_PathCmd:
252                if (degenerateData.isDegenerate()) {
253                    return false;
254                } else {
255                    SkPath::Direction dir;
256                    GR_DEBUGCODE(bool succeeded = )
257                    path.cheapComputeDirection(&dir);
258                    GrAssert(succeeded);
259                    compute_vectors(segments, fanPt, dir, vCount, iCount);
260                    return true;
261                }
262            default:
263                break;
264        }
265    }
266}
267
268struct QuadVertex {
269    GrPoint  fPos;
270    GrPoint  fUV;
271    GrScalar fD0;
272    GrScalar fD1;
273};
274
275void create_vertices(const SegmentArray&  segments,
276                     const SkPoint& fanPt,
277                     QuadVertex*    verts,
278                     uint16_t*      idxs) {
279    int v = 0;
280    int i = 0;
281
282    int count = segments.count();
283    for (int a = 0; a < count; ++a) {
284        const Segment& sega = segments[a];
285        int b = (a + 1) % count;
286        const Segment& segb = segments[b];
287
288        // FIXME: These tris are inset in the 1 unit arc around the corner
289        verts[v + 0].fPos = sega.endPt();
290        verts[v + 1].fPos = verts[v + 0].fPos + sega.endNorm();
291        verts[v + 2].fPos = verts[v + 0].fPos + segb.fMid;
292        verts[v + 3].fPos = verts[v + 0].fPos + segb.fNorms[0];
293        verts[v + 0].fUV.set(0,0);
294        verts[v + 1].fUV.set(0,-SK_Scalar1);
295        verts[v + 2].fUV.set(0,-SK_Scalar1);
296        verts[v + 3].fUV.set(0,-SK_Scalar1);
297        verts[v + 0].fD0 = verts[v + 0].fD1 = -SK_Scalar1;
298        verts[v + 1].fD0 = verts[v + 1].fD1 = -SK_Scalar1;
299        verts[v + 2].fD0 = verts[v + 2].fD1 = -SK_Scalar1;
300        verts[v + 3].fD0 = verts[v + 3].fD1 = -SK_Scalar1;
301
302        idxs[i + 0] = v + 0;
303        idxs[i + 1] = v + 2;
304        idxs[i + 2] = v + 1;
305        idxs[i + 3] = v + 0;
306        idxs[i + 4] = v + 3;
307        idxs[i + 5] = v + 2;
308
309        v += 4;
310        i += 6;
311
312        if (Segment::kLine == segb.fType) {
313            verts[v + 0].fPos = fanPt;
314            verts[v + 1].fPos = sega.endPt();
315            verts[v + 2].fPos = segb.fPts[0];
316
317            verts[v + 3].fPos = verts[v + 1].fPos + segb.fNorms[0];
318            verts[v + 4].fPos = verts[v + 2].fPos + segb.fNorms[0];
319
320            // we draw the line edge as a degenerate quad (u is 0, v is the
321            // signed distance to the edge)
322            GrScalar dist = fanPt.distanceToLineBetween(verts[v + 1].fPos,
323                                                        verts[v + 2].fPos);
324            verts[v + 0].fUV.set(0, dist);
325            verts[v + 1].fUV.set(0, 0);
326            verts[v + 2].fUV.set(0, 0);
327            verts[v + 3].fUV.set(0, -SK_Scalar1);
328            verts[v + 4].fUV.set(0, -SK_Scalar1);
329
330            verts[v + 0].fD0 = verts[v + 0].fD1 = -SK_Scalar1;
331            verts[v + 1].fD0 = verts[v + 1].fD1 = -SK_Scalar1;
332            verts[v + 2].fD0 = verts[v + 2].fD1 = -SK_Scalar1;
333            verts[v + 3].fD0 = verts[v + 3].fD1 = -SK_Scalar1;
334            verts[v + 4].fD0 = verts[v + 4].fD1 = -SK_Scalar1;
335
336            idxs[i + 0] = v + 0;
337            idxs[i + 1] = v + 2;
338            idxs[i + 2] = v + 1;
339
340            idxs[i + 3] = v + 3;
341            idxs[i + 4] = v + 1;
342            idxs[i + 5] = v + 2;
343
344            idxs[i + 6] = v + 4;
345            idxs[i + 7] = v + 3;
346            idxs[i + 8] = v + 2;
347
348            v += 5;
349            i += 9;
350        } else {
351            GrPoint qpts[] = {sega.endPt(), segb.fPts[0], segb.fPts[1]};
352
353            GrVec midVec = segb.fNorms[0] + segb.fNorms[1];
354            midVec.normalize();
355
356            verts[v + 0].fPos = fanPt;
357            verts[v + 1].fPos = qpts[0];
358            verts[v + 2].fPos = qpts[2];
359            verts[v + 3].fPos = qpts[0] + segb.fNorms[0];
360            verts[v + 4].fPos = qpts[2] + segb.fNorms[1];
361            verts[v + 5].fPos = qpts[1] + midVec;
362
363            GrScalar c = segb.fNorms[0].dot(qpts[0]);
364            verts[v + 0].fD0 =  -segb.fNorms[0].dot(fanPt) + c;
365            verts[v + 1].fD0 =  0.f;
366            verts[v + 2].fD0 =  -segb.fNorms[0].dot(qpts[2]) + c;
367            verts[v + 3].fD0 = -GR_ScalarMax/100;
368            verts[v + 4].fD0 = -GR_ScalarMax/100;
369            verts[v + 5].fD0 = -GR_ScalarMax/100;
370
371            c = segb.fNorms[1].dot(qpts[2]);
372            verts[v + 0].fD1 =  -segb.fNorms[1].dot(fanPt) + c;
373            verts[v + 1].fD1 =  -segb.fNorms[1].dot(qpts[0]) + c;
374            verts[v + 2].fD1 =  0.f;
375            verts[v + 3].fD1 = -GR_ScalarMax/100;
376            verts[v + 4].fD1 = -GR_ScalarMax/100;
377            verts[v + 5].fD1 = -GR_ScalarMax/100;
378
379            GrMatrix toUV;
380            GrPathUtils::quadDesignSpaceToUVCoordsMatrix(qpts, &toUV);
381            toUV.mapPointsWithStride(&verts[v].fUV,
382                                     &verts[v].fPos,
383                                     sizeof(QuadVertex),
384                                     6);
385
386            idxs[i + 0] = v + 3;
387            idxs[i + 1] = v + 1;
388            idxs[i + 2] = v + 2;
389            idxs[i + 3] = v + 4;
390            idxs[i + 4] = v + 3;
391            idxs[i + 5] = v + 2;
392
393            idxs[i + 6] = v + 5;
394            idxs[i + 7] = v + 3;
395            idxs[i + 8] = v + 4;
396
397            idxs[i +  9] = v + 0;
398            idxs[i + 10] = v + 2;
399            idxs[i + 11] = v + 1;
400
401            v += 6;
402            i += 12;
403        }
404    }
405}
406
407}
408
409bool GrAAConvexPathRenderer::canDrawPath(const SkPath& path,
410                                         GrPathFill fill,
411                                         const GrDrawTarget* target,
412                                         bool antiAlias) const {
413    if (!target->getCaps().fShaderDerivativeSupport || !antiAlias ||
414        kHairLine_PathFill == fill || GrIsFillInverted(fill) ||
415        !path.isConvex()) {
416        return false;
417    }  else {
418        return true;
419    }
420}
421
422bool GrAAConvexPathRenderer::onDrawPath(const SkPath& origPath,
423                                        GrPathFill fill,
424                                        const GrVec* translate,
425                                        GrDrawTarget* target,
426                                        GrDrawState::StageMask stageMask,
427                                        bool antiAlias) {
428
429
430    if (origPath.isEmpty()) {
431        return true;
432    }
433    GrDrawState* drawState = target->drawState();
434
435    GrDrawTarget::AutoStateRestore asr;
436    GrMatrix vm = drawState->getViewMatrix();
437    if (NULL != translate) {
438        vm.postTranslate(translate->fX, translate->fY);
439    }
440    asr.set(target);
441    GrMatrix ivm;
442    if (vm.invert(&ivm)) {
443        drawState->preConcatSamplerMatrices(stageMask, ivm);
444    }
445    drawState->setViewMatrix(GrMatrix::I());
446
447    SkPath path;
448    origPath.transform(vm, &path);
449
450    GrVertexLayout layout = 0;
451    for (int s = 0; s < GrDrawState::kNumStages; ++s) {
452        if ((1 << s) & stageMask) {
453            layout |= GrDrawTarget::StagePosAsTexCoordVertexLayoutBit(s);
454        }
455    }
456    layout |= GrDrawTarget::kEdge_VertexLayoutBit;
457
458    QuadVertex *verts;
459    uint16_t* idxs;
460
461    int vCount;
462    int iCount;
463    SegmentArray segments;
464    SkPoint fanPt;
465    if (!get_segments(path, &segments, &fanPt, &vCount, &iCount)) {
466        return false;
467    }
468
469    if (!target->reserveVertexSpace(layout,
470                                    vCount,
471                                    reinterpret_cast<void**>(&verts))) {
472        return false;
473    }
474    if (!target->reserveIndexSpace(iCount, reinterpret_cast<void**>(&idxs))) {
475        target->resetVertexSource();
476        return false;
477    }
478
479    create_vertices(segments, fanPt, verts, idxs);
480
481    drawState->setVertexEdgeType(GrDrawState::kQuad_EdgeType);
482    target->drawIndexed(kTriangles_PrimitiveType,
483                        0,        // start vertex
484                        0,        // start index
485                        vCount,
486                        iCount);
487    return true;
488}
489
490