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