• Home
  • Line#
  • Scopes#
  • Navigate#
  • Raw
  • Download
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 "SkStrokeRec.h"
16 #include "SkTrace.h"
17 
GrAAConvexPathRenderer()18 GrAAConvexPathRenderer::GrAAConvexPathRenderer() {
19 }
20 
21 namespace {
22 
23 struct 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 
countPoints__anon591b70830111::Segment38     int countPoints() {
39         GR_STATIC_ASSERT(0 == kLine && 1 == kQuad);
40         return fType + 1;
41     }
endPt__anon591b70830111::Segment42     const SkPoint& endPt() const {
43         GR_STATIC_ASSERT(0 == kLine && 1 == kQuad);
44         return fPts[fType];
45     };
endNorm__anon591b70830111::Segment46     const SkPoint& endNorm() const {
47         GR_STATIC_ASSERT(0 == kLine && 1 == kQuad);
48         return fNorms[fType];
49     };
50 };
51 
52 typedef SkTArray<Segment, true> SegmentArray;
53 
center_of_mass(const SegmentArray & segments,SkPoint * c)54 void center_of_mass(const SegmentArray& segments, SkPoint* c) {
55     SkScalar 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             SkScalar t = SkScalarMul(pi.fX, pj.fY) - SkScalarMul(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 = SkScalarDiv(SK_Scalar1, area);
97         center.fX = SkScalarMul(center.fX, area);
98         center.fY = SkScalarMul(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 
compute_vectors(SegmentArray * segments,SkPoint * fanPt,SkPath::Direction dir,int * vCount,int * iCount)105 void 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 
160 struct DegenerateTestData {
DegenerateTestData__anon591b70830111::DegenerateTestData161     DegenerateTestData() { fStage = kInitial; }
isDegenerate__anon591b70830111::DegenerateTestData162     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     SkScalar    fLineC;
172 };
173 
update_degenerate_test(DegenerateTestData * data,const GrPoint & pt)174 void 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 
get_direction(const SkPath & path,const SkMatrix & m,SkPath::Direction * dir)203 inline bool get_direction(const SkPath& path, const SkMatrix& 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     SkScalar det2x2 = SkScalarMul(m.get(SkMatrix::kMScaleX), m.get(SkMatrix::kMScaleY)) -
210                       SkScalarMul(m.get(SkMatrix::kMSkewX), m.get(SkMatrix::kMSkewY));
211     if (det2x2 < 0) {
212         *dir = SkPath::OppositeDirection(*dir);
213     }
214     return true;
215 }
216 
get_segments(const SkPath & path,const SkMatrix & m,SegmentArray * segments,SkPoint * fanPt,int * vCount,int * iCount)217 bool get_segments(const SkPath& path,
218                   const SkMatrix& m,
219                   SegmentArray* segments,
220                   SkPoint* fanPt,
221                   int* vCount,
222                   int* iCount) {
223     SkPath::Iter iter(path, true);
224     // This renderer over-emphasizes very thin path regions. We use the distance
225     // to the path from the sample to compute coverage. Every pixel intersected
226     // by the path will be hit and the maximum distance is sqrt(2)/2. We don't
227     // notice that the sample may be close to a very thin area of the path and
228     // thus should be very light. This is particularly egregious for degenerate
229     // line paths. We detect paths that are very close to a line (zero area) and
230     // draw nothing.
231     DegenerateTestData degenerateData;
232     SkPath::Direction dir;
233     // get_direction can fail for some degenerate paths.
234     if (!get_direction(path, m, &dir)) {
235         return false;
236     }
237 
238     for (;;) {
239         GrPoint pts[4];
240         GrPathCmd cmd = (GrPathCmd)iter.next(pts);
241         switch (cmd) {
242             case kMove_PathCmd:
243                 m.mapPoints(pts, 1);
244                 update_degenerate_test(&degenerateData, pts[0]);
245                 break;
246             case kLine_PathCmd: {
247                 m.mapPoints(pts + 1, 1);
248                 update_degenerate_test(&degenerateData, pts[1]);
249                 segments->push_back();
250                 segments->back().fType = Segment::kLine;
251                 segments->back().fPts[0] = pts[1];
252                 break;
253             }
254             case kQuadratic_PathCmd:
255                 m.mapPoints(pts + 1, 2);
256                 update_degenerate_test(&degenerateData, pts[1]);
257                 update_degenerate_test(&degenerateData, pts[2]);
258                 segments->push_back();
259                 segments->back().fType = Segment::kQuad;
260                 segments->back().fPts[0] = pts[1];
261                 segments->back().fPts[1] = pts[2];
262                 break;
263             case kCubic_PathCmd: {
264                 m.mapPoints(pts, 4);
265                 update_degenerate_test(&degenerateData, pts[1]);
266                 update_degenerate_test(&degenerateData, pts[2]);
267                 update_degenerate_test(&degenerateData, pts[3]);
268                 // unlike quads and lines, the pts[0] will also be read (in
269                 // convertCubicToQuads).
270                 SkSTArray<15, SkPoint, true> quads;
271                 GrPathUtils::convertCubicToQuads(pts, SK_Scalar1, true, dir, &quads);
272                 int count = quads.count();
273                 for (int q = 0; q < count; q += 3) {
274                     segments->push_back();
275                     segments->back().fType = Segment::kQuad;
276                     segments->back().fPts[0] = quads[q + 1];
277                     segments->back().fPts[1] = quads[q + 2];
278                 }
279                 break;
280             };
281             case kEnd_PathCmd:
282                 if (degenerateData.isDegenerate()) {
283                     return false;
284                 } else {
285                     compute_vectors(segments, fanPt, dir, vCount, iCount);
286                     return true;
287                 }
288             default:
289                 break;
290         }
291     }
292 }
293 
294 struct QuadVertex {
295     GrPoint  fPos;
296     GrPoint  fUV;
297     SkScalar fD0;
298     SkScalar fD1;
299 };
300 
create_vertices(const SegmentArray & segments,const SkPoint & fanPt,QuadVertex * verts,uint16_t * idxs)301 void create_vertices(const SegmentArray&  segments,
302                      const SkPoint& fanPt,
303                      QuadVertex*    verts,
304                      uint16_t*      idxs) {
305     int v = 0;
306     int i = 0;
307 
308     int count = segments.count();
309     for (int a = 0; a < count; ++a) {
310         const Segment& sega = segments[a];
311         int b = (a + 1) % count;
312         const Segment& segb = segments[b];
313 
314         // FIXME: These tris are inset in the 1 unit arc around the corner
315         verts[v + 0].fPos = sega.endPt();
316         verts[v + 1].fPos = verts[v + 0].fPos + sega.endNorm();
317         verts[v + 2].fPos = verts[v + 0].fPos + segb.fMid;
318         verts[v + 3].fPos = verts[v + 0].fPos + segb.fNorms[0];
319         verts[v + 0].fUV.set(0,0);
320         verts[v + 1].fUV.set(0,-SK_Scalar1);
321         verts[v + 2].fUV.set(0,-SK_Scalar1);
322         verts[v + 3].fUV.set(0,-SK_Scalar1);
323         verts[v + 0].fD0 = verts[v + 0].fD1 = -SK_Scalar1;
324         verts[v + 1].fD0 = verts[v + 1].fD1 = -SK_Scalar1;
325         verts[v + 2].fD0 = verts[v + 2].fD1 = -SK_Scalar1;
326         verts[v + 3].fD0 = verts[v + 3].fD1 = -SK_Scalar1;
327 
328         idxs[i + 0] = v + 0;
329         idxs[i + 1] = v + 2;
330         idxs[i + 2] = v + 1;
331         idxs[i + 3] = v + 0;
332         idxs[i + 4] = v + 3;
333         idxs[i + 5] = v + 2;
334 
335         v += 4;
336         i += 6;
337 
338         if (Segment::kLine == segb.fType) {
339             verts[v + 0].fPos = fanPt;
340             verts[v + 1].fPos = sega.endPt();
341             verts[v + 2].fPos = segb.fPts[0];
342 
343             verts[v + 3].fPos = verts[v + 1].fPos + segb.fNorms[0];
344             verts[v + 4].fPos = verts[v + 2].fPos + segb.fNorms[0];
345 
346             // we draw the line edge as a degenerate quad (u is 0, v is the
347             // signed distance to the edge)
348             SkScalar dist = fanPt.distanceToLineBetween(verts[v + 1].fPos,
349                                                         verts[v + 2].fPos);
350             verts[v + 0].fUV.set(0, dist);
351             verts[v + 1].fUV.set(0, 0);
352             verts[v + 2].fUV.set(0, 0);
353             verts[v + 3].fUV.set(0, -SK_Scalar1);
354             verts[v + 4].fUV.set(0, -SK_Scalar1);
355 
356             verts[v + 0].fD0 = verts[v + 0].fD1 = -SK_Scalar1;
357             verts[v + 1].fD0 = verts[v + 1].fD1 = -SK_Scalar1;
358             verts[v + 2].fD0 = verts[v + 2].fD1 = -SK_Scalar1;
359             verts[v + 3].fD0 = verts[v + 3].fD1 = -SK_Scalar1;
360             verts[v + 4].fD0 = verts[v + 4].fD1 = -SK_Scalar1;
361 
362             idxs[i + 0] = v + 0;
363             idxs[i + 1] = v + 2;
364             idxs[i + 2] = v + 1;
365 
366             idxs[i + 3] = v + 3;
367             idxs[i + 4] = v + 1;
368             idxs[i + 5] = v + 2;
369 
370             idxs[i + 6] = v + 4;
371             idxs[i + 7] = v + 3;
372             idxs[i + 8] = v + 2;
373 
374             v += 5;
375             i += 9;
376         } else {
377             GrPoint qpts[] = {sega.endPt(), segb.fPts[0], segb.fPts[1]};
378 
379             GrVec midVec = segb.fNorms[0] + segb.fNorms[1];
380             midVec.normalize();
381 
382             verts[v + 0].fPos = fanPt;
383             verts[v + 1].fPos = qpts[0];
384             verts[v + 2].fPos = qpts[2];
385             verts[v + 3].fPos = qpts[0] + segb.fNorms[0];
386             verts[v + 4].fPos = qpts[2] + segb.fNorms[1];
387             verts[v + 5].fPos = qpts[1] + midVec;
388 
389             SkScalar c = segb.fNorms[0].dot(qpts[0]);
390             verts[v + 0].fD0 =  -segb.fNorms[0].dot(fanPt) + c;
391             verts[v + 1].fD0 =  0.f;
392             verts[v + 2].fD0 =  -segb.fNorms[0].dot(qpts[2]) + c;
393             verts[v + 3].fD0 = -SK_ScalarMax/100;
394             verts[v + 4].fD0 = -SK_ScalarMax/100;
395             verts[v + 5].fD0 = -SK_ScalarMax/100;
396 
397             c = segb.fNorms[1].dot(qpts[2]);
398             verts[v + 0].fD1 =  -segb.fNorms[1].dot(fanPt) + c;
399             verts[v + 1].fD1 =  -segb.fNorms[1].dot(qpts[0]) + c;
400             verts[v + 2].fD1 =  0.f;
401             verts[v + 3].fD1 = -SK_ScalarMax/100;
402             verts[v + 4].fD1 = -SK_ScalarMax/100;
403             verts[v + 5].fD1 = -SK_ScalarMax/100;
404 
405             GrPathUtils::QuadUVMatrix toUV(qpts);
406             toUV.apply<6, sizeof(QuadVertex), sizeof(GrPoint)>(verts + v);
407 
408             idxs[i + 0] = v + 3;
409             idxs[i + 1] = v + 1;
410             idxs[i + 2] = v + 2;
411             idxs[i + 3] = v + 4;
412             idxs[i + 4] = v + 3;
413             idxs[i + 5] = v + 2;
414 
415             idxs[i + 6] = v + 5;
416             idxs[i + 7] = v + 3;
417             idxs[i + 8] = v + 4;
418 
419             idxs[i +  9] = v + 0;
420             idxs[i + 10] = v + 2;
421             idxs[i + 11] = v + 1;
422 
423             v += 6;
424             i += 12;
425         }
426     }
427 }
428 
429 }
430 
canDrawPath(const SkPath & path,const SkStrokeRec & stroke,const GrDrawTarget * target,bool antiAlias) const431 bool GrAAConvexPathRenderer::canDrawPath(const SkPath& path,
432                                          const SkStrokeRec& stroke,
433                                          const GrDrawTarget* target,
434                                          bool antiAlias) const {
435     return (target->getCaps().shaderDerivativeSupport() && antiAlias &&
436             stroke.isFillStyle() && !path.isInverseFillType() && path.isConvex());
437 }
438 
onDrawPath(const SkPath & origPath,const SkStrokeRec &,GrDrawTarget * target,bool antiAlias)439 bool GrAAConvexPathRenderer::onDrawPath(const SkPath& origPath,
440                                         const SkStrokeRec&,
441                                         GrDrawTarget* target,
442                                         bool antiAlias) {
443 
444     const SkPath* path = &origPath;
445     if (path->isEmpty()) {
446         return true;
447     }
448     GrDrawState* drawState = target->drawState();
449 
450     GrDrawState::AutoDeviceCoordDraw adcd(drawState);
451     if (!adcd.succeeded()) {
452         return false;
453     }
454     const SkMatrix* vm = &adcd.getOriginalMatrix();
455 
456     GrVertexLayout layout = 0;
457     layout |= GrDrawState::kEdge_VertexLayoutBit;
458 
459     // We use the fact that SkPath::transform path does subdivision based on
460     // perspective. Otherwise, we apply the view matrix when copying to the
461     // segment representation.
462     SkPath tmpPath;
463     if (vm->hasPerspective()) {
464         origPath.transform(*vm, &tmpPath);
465         path = &tmpPath;
466         vm = &SkMatrix::I();
467     }
468 
469     QuadVertex *verts;
470     uint16_t* idxs;
471 
472     int vCount;
473     int iCount;
474     enum {
475         kPreallocSegmentCnt = 512 / sizeof(Segment),
476     };
477     SkSTArray<kPreallocSegmentCnt, Segment, true> segments;
478     SkPoint fanPt;
479 
480     if (!get_segments(*path, *vm, &segments, &fanPt, &vCount, &iCount)) {
481         return false;
482     }
483 
484     GrDrawTarget::AutoReleaseGeometry arg(target, layout, vCount, iCount);
485     if (!arg.succeeded()) {
486         return false;
487     }
488     verts = reinterpret_cast<QuadVertex*>(arg.vertices());
489     idxs = reinterpret_cast<uint16_t*>(arg.indices());
490 
491     create_vertices(segments, fanPt, verts, idxs);
492 
493     GrDrawState::VertexEdgeType oldEdgeType = drawState->getVertexEdgeType();
494     drawState->setVertexEdgeType(GrDrawState::kQuad_EdgeType);
495     target->drawIndexed(kTriangles_GrPrimitiveType,
496                         0,        // start vertex
497                         0,        // start index
498                         vCount,
499                         iCount);
500     drawState->setVertexEdgeType(oldEdgeType);
501 
502     return true;
503 }
504