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
GrAAConvexPathRenderer()18 GrAAConvexPathRenderer::GrAAConvexPathRenderer() {
19 }
20
21 namespace {
22
23 struct 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
countPoints__anon3d16c6210111::Segment36 int countPoints() {
37 return (kLine == fType) ? 1 : 2;
38 }
endPt__anon3d16c6210111::Segment39 const SkPoint& endPt() const {
40 return (kLine == fType) ? fPts[0] : fPts[1];
41 };
endNorm__anon3d16c6210111::Segment42 const SkPoint& endNorm() const {
43 return (kLine == fType) ? fNorms[0] : fNorms[1];
44 };
45 };
46
47 typedef SkTArray<Segment, true> SegmentArray;
48
center_of_mass(const SegmentArray & segments,SkPoint * c)49 void 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
compute_vectors(SegmentArray * segments,SkPoint * fanPt,SkPath::Direction dir,int * vCount,int * iCount)101 void 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
156 struct DegenerateTestData {
DegenerateTestData__anon3d16c6210111::DegenerateTestData157 DegenerateTestData() { fStage = kInitial; }
isDegenerate__anon3d16c6210111::DegenerateTestData158 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
update_degenerate_test(DegenerateTestData * data,const GrPoint & pt)170 void 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
get_segments(const GrPath & path,SegmentArray * segments,SkPoint * fanPt,int * vCount,int * iCount)199 bool 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(°enerateData, pts[0]);
220 break;
221 case kLine_PathCmd: {
222 update_degenerate_test(°enerateData, 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(°enerateData, pts[1]);
230 update_degenerate_test(°enerateData, 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(°enerateData, pts[1]);
238 update_degenerate_test(°enerateData, pts[2]);
239 update_degenerate_test(°enerateData, 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
268 struct QuadVertex {
269 GrPoint fPos;
270 GrPoint fUV;
271 GrScalar fD0;
272 GrScalar fD1;
273 };
274
create_vertices(const SegmentArray & segments,const SkPoint & fanPt,QuadVertex * verts,uint16_t * idxs)275 void 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
canDrawPath(const SkPath & path,GrPathFill fill,const GrDrawTarget * target,bool antiAlias) const409 bool 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
onDrawPath(const SkPath & origPath,GrPathFill fill,const GrVec * translate,GrDrawTarget * target,GrDrawState::StageMask stageMask,bool antiAlias)422 bool 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