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(°enerateData, pts[0]);
245 break;
246 case kLine_PathCmd: {
247 m.mapPoints(pts + 1, 1);
248 update_degenerate_test(°enerateData, 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(°enerateData, pts[1]);
257 update_degenerate_test(°enerateData, 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(°enerateData, pts[1]);
266 update_degenerate_test(°enerateData, pts[2]);
267 update_degenerate_test(°enerateData, 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