3 * Copyright 2012 Google Inc.
5 * Use of this source code is governed by a BSD-style license that can be
6 * found in the LICENSE file.
9 #include "GrAAConvexPathRenderer.h"
11 #include "GrContext.h"
12 #include "GrDrawState.h"
13 #include "GrDrawTargetCaps.h"
14 #include "GrProcessor.h"
15 #include "GrPathUtils.h"
16 #include "GrTBackendProcessorFactory.h"
18 #include "SkStrokeRec.h"
19 #include "SkTraceEvent.h"
21 #include "gl/builders/GrGLProgramBuilder.h"
22 #include "gl/GrGLProcessor.h"
23 #include "gl/GrGLSL.h"
24 #include "gl/GrGLGeometryProcessor.h"
26 #include "GrGeometryProcessor.h"
28 GrAAConvexPathRenderer::GrAAConvexPathRenderer() {
33 // These enum values are assumed in member functions below.
38 // line uses one pt, quad uses 2 pts
40 // normal to edge ending at each pt
42 // is the corner where the previous segment meets this segment
43 // sharp. If so, fMid is a normalized bisector facing outward.
47 GR_STATIC_ASSERT(0 == kLine && 1 == kQuad);
50 const SkPoint& endPt() const {
51 GR_STATIC_ASSERT(0 == kLine && 1 == kQuad);
54 const SkPoint& endNorm() const {
55 GR_STATIC_ASSERT(0 == kLine && 1 == kQuad);
60 typedef SkTArray<Segment, true> SegmentArray;
62 static void center_of_mass(const SegmentArray& segments, SkPoint* c) {
64 SkPoint center = {0, 0};
65 int count = segments.count();
68 // We translate the polygon so that the first point is at the origin.
69 // This avoids some precision issues with small area polygons far away
71 p0 = segments[0].endPt();
74 // the first and last iteration of the below loop would compute
75 // zeros since the starting / ending point is (0,0). So instead we start
76 // at i=1 and make the last iteration i=count-2.
77 pj = segments[1].endPt() - p0;
78 for (int i = 1; i < count - 1; ++i) {
80 const SkPoint pj = segments[i + 1].endPt() - p0;
82 SkScalar t = SkScalarMul(pi.fX, pj.fY) - SkScalarMul(pj.fX, pi.fY);
84 center.fX += (pi.fX + pj.fX) * t;
85 center.fY += (pi.fY + pj.fY) * t;
89 // If the poly has no area then we instead return the average of
91 if (SkScalarNearlyZero(area)) {
94 for (int i = 0; i < count; ++i) {
95 const SkPoint& pt = segments[i].endPt();
99 SkScalar denom = SK_Scalar1 / count;
104 area = SkScalarDiv(SK_Scalar1, area);
105 center.fX = SkScalarMul(center.fX, area);
106 center.fY = SkScalarMul(center.fY, area);
107 // undo the translate of p0 to the origin.
110 SkASSERT(!SkScalarIsNaN(c->fX) && !SkScalarIsNaN(c->fY));
113 static void compute_vectors(SegmentArray* segments,
115 SkPath::Direction dir,
118 center_of_mass(*segments, fanPt);
119 int count = segments->count();
121 // Make the normals point towards the outside
122 SkPoint::Side normSide;
123 if (dir == SkPath::kCCW_Direction) {
124 normSide = SkPoint::kRight_Side;
126 normSide = SkPoint::kLeft_Side;
131 // compute normals at all points
132 for (int a = 0; a < count; ++a) {
133 Segment& sega = (*segments)[a];
134 int b = (a + 1) % count;
135 Segment& segb = (*segments)[b];
137 const SkPoint* prevPt = &sega.endPt();
138 int n = segb.countPoints();
139 for (int p = 0; p < n; ++p) {
140 segb.fNorms[p] = segb.fPts[p] - *prevPt;
141 segb.fNorms[p].normalize();
142 segb.fNorms[p].setOrthog(segb.fNorms[p], normSide);
143 prevPt = &segb.fPts[p];
145 if (Segment::kLine == segb.fType) {
154 // compute mid-vectors where segments meet. TODO: Detect shallow corners
155 // and leave out the wedges and close gaps by stitching segments together.
156 for (int a = 0; a < count; ++a) {
157 const Segment& sega = (*segments)[a];
158 int b = (a + 1) % count;
159 Segment& segb = (*segments)[b];
160 segb.fMid = segb.fNorms[0] + sega.endNorm();
161 segb.fMid.normalize();
168 struct DegenerateTestData {
169 DegenerateTestData() { fStage = kInitial; }
170 bool isDegenerate() const { return kNonDegenerate != fStage; }
178 SkVector fLineNormal;
182 static const SkScalar kClose = (SK_Scalar1 / 16);
183 static const SkScalar kCloseSqd = SkScalarMul(kClose, kClose);
185 static void update_degenerate_test(DegenerateTestData* data, const SkPoint& pt) {
186 switch (data->fStage) {
187 case DegenerateTestData::kInitial:
188 data->fFirstPoint = pt;
189 data->fStage = DegenerateTestData::kPoint;
191 case DegenerateTestData::kPoint:
192 if (pt.distanceToSqd(data->fFirstPoint) > kCloseSqd) {
193 data->fLineNormal = pt - data->fFirstPoint;
194 data->fLineNormal.normalize();
195 data->fLineNormal.setOrthog(data->fLineNormal);
196 data->fLineC = -data->fLineNormal.dot(data->fFirstPoint);
197 data->fStage = DegenerateTestData::kLine;
200 case DegenerateTestData::kLine:
201 if (SkScalarAbs(data->fLineNormal.dot(pt) + data->fLineC) > kClose) {
202 data->fStage = DegenerateTestData::kNonDegenerate;
204 case DegenerateTestData::kNonDegenerate:
207 SkFAIL("Unexpected degenerate test stage.");
211 static inline bool get_direction(const SkPath& path, const SkMatrix& m, SkPath::Direction* dir) {
212 if (!path.cheapComputeDirection(dir)) {
215 // check whether m reverses the orientation
216 SkASSERT(!m.hasPerspective());
217 SkScalar det2x2 = SkScalarMul(m.get(SkMatrix::kMScaleX), m.get(SkMatrix::kMScaleY)) -
218 SkScalarMul(m.get(SkMatrix::kMSkewX), m.get(SkMatrix::kMSkewY));
220 *dir = SkPath::OppositeDirection(*dir);
225 static inline void add_line_to_segment(const SkPoint& pt,
226 SegmentArray* segments,
228 segments->push_back();
229 segments->back().fType = Segment::kLine;
230 segments->back().fPts[0] = pt;
231 devBounds->growToInclude(pt.fX, pt.fY);
235 static inline bool contains_inclusive(const SkRect& rect, const SkPoint& p) {
236 return p.fX >= rect.fLeft && p.fX <= rect.fRight && p.fY >= rect.fTop && p.fY <= rect.fBottom;
240 static inline void add_quad_segment(const SkPoint pts[3],
241 SegmentArray* segments,
243 if (pts[0].distanceToSqd(pts[1]) < kCloseSqd || pts[1].distanceToSqd(pts[2]) < kCloseSqd) {
244 if (pts[0] != pts[2]) {
245 add_line_to_segment(pts[2], segments, devBounds);
248 segments->push_back();
249 segments->back().fType = Segment::kQuad;
250 segments->back().fPts[0] = pts[1];
251 segments->back().fPts[1] = pts[2];
252 SkASSERT(contains_inclusive(*devBounds, pts[0]));
253 devBounds->growToInclude(pts + 1, 2);
257 static inline void add_cubic_segments(const SkPoint pts[4],
258 SkPath::Direction dir,
259 SegmentArray* segments,
261 SkSTArray<15, SkPoint, true> quads;
262 GrPathUtils::convertCubicToQuads(pts, SK_Scalar1, true, dir, &quads);
263 int count = quads.count();
264 for (int q = 0; q < count; q += 3) {
265 add_quad_segment(&quads[q], segments, devBounds);
269 static bool get_segments(const SkPath& path,
271 SegmentArray* segments,
276 SkPath::Iter iter(path, true);
277 // This renderer over-emphasizes very thin path regions. We use the distance
278 // to the path from the sample to compute coverage. Every pixel intersected
279 // by the path will be hit and the maximum distance is sqrt(2)/2. We don't
280 // notice that the sample may be close to a very thin area of the path and
281 // thus should be very light. This is particularly egregious for degenerate
282 // line paths. We detect paths that are very close to a line (zero area) and
284 DegenerateTestData degenerateData;
285 SkPath::Direction dir;
286 // get_direction can fail for some degenerate paths.
287 if (!get_direction(path, m, &dir)) {
293 SkPath::Verb verb = iter.next(pts);
295 case SkPath::kMove_Verb:
297 update_degenerate_test(°enerateData, pts[0]);
298 devBounds->set(pts->fX, pts->fY, pts->fX, pts->fY);
300 case SkPath::kLine_Verb: {
301 m.mapPoints(&pts[1], 1);
302 update_degenerate_test(°enerateData, pts[1]);
303 add_line_to_segment(pts[1], segments, devBounds);
306 case SkPath::kQuad_Verb:
308 update_degenerate_test(°enerateData, pts[1]);
309 update_degenerate_test(°enerateData, pts[2]);
310 add_quad_segment(pts, segments, devBounds);
312 case SkPath::kCubic_Verb: {
314 update_degenerate_test(°enerateData, pts[1]);
315 update_degenerate_test(°enerateData, pts[2]);
316 update_degenerate_test(°enerateData, pts[3]);
317 add_cubic_segments(pts, dir, segments, devBounds);
320 case SkPath::kDone_Verb:
321 if (degenerateData.isDegenerate()) {
324 compute_vectors(segments, fanPt, dir, vCount, iCount);
341 Draw() : fVertexCnt(0), fIndexCnt(0) {}
346 typedef SkTArray<Draw, true> DrawArray;
348 static void create_vertices(const SegmentArray& segments,
349 const SkPoint& fanPt,
353 Draw* draw = &draws->push_back();
354 // alias just to make vert/index assignments easier to read.
355 int* v = &draw->fVertexCnt;
356 int* i = &draw->fIndexCnt;
358 int count = segments.count();
359 for (int a = 0; a < count; ++a) {
360 const Segment& sega = segments[a];
361 int b = (a + 1) % count;
362 const Segment& segb = segments[b];
364 // Check whether adding the verts for this segment to the current draw would cause index
365 // values to overflow.
367 if (Segment::kLine == segb.fType) {
372 if (draw->fVertexCnt + vCount > (1 << 16)) {
375 draw = &draws->push_back();
376 v = &draw->fVertexCnt;
377 i = &draw->fIndexCnt;
380 // FIXME: These tris are inset in the 1 unit arc around the corner
381 verts[*v + 0].fPos = sega.endPt();
382 verts[*v + 1].fPos = verts[*v + 0].fPos + sega.endNorm();
383 verts[*v + 2].fPos = verts[*v + 0].fPos + segb.fMid;
384 verts[*v + 3].fPos = verts[*v + 0].fPos + segb.fNorms[0];
385 verts[*v + 0].fUV.set(0,0);
386 verts[*v + 1].fUV.set(0,-SK_Scalar1);
387 verts[*v + 2].fUV.set(0,-SK_Scalar1);
388 verts[*v + 3].fUV.set(0,-SK_Scalar1);
389 verts[*v + 0].fD0 = verts[*v + 0].fD1 = -SK_Scalar1;
390 verts[*v + 1].fD0 = verts[*v + 1].fD1 = -SK_Scalar1;
391 verts[*v + 2].fD0 = verts[*v + 2].fD1 = -SK_Scalar1;
392 verts[*v + 3].fD0 = verts[*v + 3].fD1 = -SK_Scalar1;
394 idxs[*i + 0] = *v + 0;
395 idxs[*i + 1] = *v + 2;
396 idxs[*i + 2] = *v + 1;
397 idxs[*i + 3] = *v + 0;
398 idxs[*i + 4] = *v + 3;
399 idxs[*i + 5] = *v + 2;
404 if (Segment::kLine == segb.fType) {
405 verts[*v + 0].fPos = fanPt;
406 verts[*v + 1].fPos = sega.endPt();
407 verts[*v + 2].fPos = segb.fPts[0];
409 verts[*v + 3].fPos = verts[*v + 1].fPos + segb.fNorms[0];
410 verts[*v + 4].fPos = verts[*v + 2].fPos + segb.fNorms[0];
412 // we draw the line edge as a degenerate quad (u is 0, v is the
413 // signed distance to the edge)
414 SkScalar dist = fanPt.distanceToLineBetween(verts[*v + 1].fPos,
416 verts[*v + 0].fUV.set(0, dist);
417 verts[*v + 1].fUV.set(0, 0);
418 verts[*v + 2].fUV.set(0, 0);
419 verts[*v + 3].fUV.set(0, -SK_Scalar1);
420 verts[*v + 4].fUV.set(0, -SK_Scalar1);
422 verts[*v + 0].fD0 = verts[*v + 0].fD1 = -SK_Scalar1;
423 verts[*v + 1].fD0 = verts[*v + 1].fD1 = -SK_Scalar1;
424 verts[*v + 2].fD0 = verts[*v + 2].fD1 = -SK_Scalar1;
425 verts[*v + 3].fD0 = verts[*v + 3].fD1 = -SK_Scalar1;
426 verts[*v + 4].fD0 = verts[*v + 4].fD1 = -SK_Scalar1;
428 idxs[*i + 0] = *v + 0;
429 idxs[*i + 1] = *v + 2;
430 idxs[*i + 2] = *v + 1;
432 idxs[*i + 3] = *v + 3;
433 idxs[*i + 4] = *v + 1;
434 idxs[*i + 5] = *v + 2;
436 idxs[*i + 6] = *v + 4;
437 idxs[*i + 7] = *v + 3;
438 idxs[*i + 8] = *v + 2;
443 SkPoint qpts[] = {sega.endPt(), segb.fPts[0], segb.fPts[1]};
445 SkVector midVec = segb.fNorms[0] + segb.fNorms[1];
448 verts[*v + 0].fPos = fanPt;
449 verts[*v + 1].fPos = qpts[0];
450 verts[*v + 2].fPos = qpts[2];
451 verts[*v + 3].fPos = qpts[0] + segb.fNorms[0];
452 verts[*v + 4].fPos = qpts[2] + segb.fNorms[1];
453 verts[*v + 5].fPos = qpts[1] + midVec;
455 SkScalar c = segb.fNorms[0].dot(qpts[0]);
456 verts[*v + 0].fD0 = -segb.fNorms[0].dot(fanPt) + c;
457 verts[*v + 1].fD0 = 0.f;
458 verts[*v + 2].fD0 = -segb.fNorms[0].dot(qpts[2]) + c;
459 verts[*v + 3].fD0 = -SK_ScalarMax/100;
460 verts[*v + 4].fD0 = -SK_ScalarMax/100;
461 verts[*v + 5].fD0 = -SK_ScalarMax/100;
463 c = segb.fNorms[1].dot(qpts[2]);
464 verts[*v + 0].fD1 = -segb.fNorms[1].dot(fanPt) + c;
465 verts[*v + 1].fD1 = -segb.fNorms[1].dot(qpts[0]) + c;
466 verts[*v + 2].fD1 = 0.f;
467 verts[*v + 3].fD1 = -SK_ScalarMax/100;
468 verts[*v + 4].fD1 = -SK_ScalarMax/100;
469 verts[*v + 5].fD1 = -SK_ScalarMax/100;
471 GrPathUtils::QuadUVMatrix toUV(qpts);
472 toUV.apply<6, sizeof(QuadVertex), sizeof(SkPoint)>(verts + *v);
474 idxs[*i + 0] = *v + 3;
475 idxs[*i + 1] = *v + 1;
476 idxs[*i + 2] = *v + 2;
477 idxs[*i + 3] = *v + 4;
478 idxs[*i + 4] = *v + 3;
479 idxs[*i + 5] = *v + 2;
481 idxs[*i + 6] = *v + 5;
482 idxs[*i + 7] = *v + 3;
483 idxs[*i + 8] = *v + 4;
485 idxs[*i + 9] = *v + 0;
486 idxs[*i + 10] = *v + 2;
487 idxs[*i + 11] = *v + 1;
495 ///////////////////////////////////////////////////////////////////////////////
498 * Quadratic specified by 0=u^2-v canonical coords. u and v are the first
499 * two components of the vertex attribute. Coverage is based on signed
500 * distance with negative being inside, positive outside. The edge is specified in
501 * window space (y-down). If either the third or fourth component of the interpolated
502 * vertex coord is > 0 then the pixel is considered outside the edge. This is used to
503 * attempt to trim to a portion of the infinite quad.
504 * Requires shader derivative instruction support.
507 class QuadEdgeEffect : public GrGeometryProcessor {
510 static GrGeometryProcessor* Create() {
511 GR_CREATE_STATIC_PROCESSOR(gQuadEdgeEffect, QuadEdgeEffect, ());
512 gQuadEdgeEffect->ref();
513 return gQuadEdgeEffect;
516 virtual ~QuadEdgeEffect() {}
518 static const char* Name() { return "QuadEdge"; }
520 const GrShaderVar& inQuadEdge() const { return fInQuadEdge; }
522 virtual const GrBackendGeometryProcessorFactory& getFactory() const SK_OVERRIDE {
523 return GrTBackendGeometryProcessorFactory<QuadEdgeEffect>::getInstance();
526 class GLProcessor : public GrGLGeometryProcessor {
528 GLProcessor(const GrBackendProcessorFactory& factory, const GrProcessor&)
529 : INHERITED (factory) {}
531 virtual void emitCode(const EmitArgs& args) SK_OVERRIDE {
532 GrGLVertToFrag v(kVec4f_GrSLType);
533 args.fPB->addVarying("QuadEdge", &v);
535 GrGLGPFragmentBuilder* fsBuilder = args.fPB->getFragmentShaderBuilder();
537 SkAssertResult(fsBuilder->enableFeature(
538 GrGLFragmentShaderBuilder::kStandardDerivatives_GLSLFeature));
539 fsBuilder->codeAppendf("float edgeAlpha;");
541 // keep the derivative instructions outside the conditional
542 fsBuilder->codeAppendf("vec2 duvdx = dFdx(%s.xy);", v.fsIn());
543 fsBuilder->codeAppendf("vec2 duvdy = dFdy(%s.xy);", v.fsIn());
544 fsBuilder->codeAppendf("if (%s.z > 0.0 && %s.w > 0.0) {", v.fsIn(), v.fsIn());
545 // today we know z and w are in device space. We could use derivatives
546 fsBuilder->codeAppendf("edgeAlpha = min(min(%s.z, %s.w) + 0.5, 1.0);", v.fsIn(),
548 fsBuilder->codeAppendf ("} else {");
549 fsBuilder->codeAppendf("vec2 gF = vec2(2.0*%s.x*duvdx.x - duvdx.y,"
550 " 2.0*%s.x*duvdy.x - duvdy.y);",
552 fsBuilder->codeAppendf("edgeAlpha = (%s.x*%s.x - %s.y);", v.fsIn(), v.fsIn(),
554 fsBuilder->codeAppendf("edgeAlpha = "
555 "clamp(0.5 - edgeAlpha / length(gF), 0.0, 1.0);}");
558 fsBuilder->codeAppendf("%s = %s;", args.fOutput,
559 (GrGLSLExpr4(args.fInput) * GrGLSLExpr1("edgeAlpha")).c_str());
561 const GrShaderVar& inQuadEdge = args.fGP.cast<QuadEdgeEffect>().inQuadEdge();
562 GrGLVertexBuilder* vsBuilder = args.fPB->getVertexShaderBuilder();
563 vsBuilder->codeAppendf("\t%s = %s;\n", v.vsOut(), inQuadEdge.c_str());
566 static inline void GenKey(const GrProcessor&, const GrGLCaps&, GrProcessorKeyBuilder*) {}
568 virtual void setData(const GrGLProgramDataManager&, const GrProcessor&) SK_OVERRIDE {}
571 typedef GrGLGeometryProcessor INHERITED;
576 : fInQuadEdge(this->addVertexAttrib(GrShaderVar("inQuadEdge",
578 GrShaderVar::kAttribute_TypeModifier))) {
581 virtual bool onIsEqual(const GrGeometryProcessor& other) const SK_OVERRIDE {
585 virtual void onComputeInvariantOutput(InvariantOutput* inout) const SK_OVERRIDE {
586 inout->mulByUnknownAlpha();
589 const GrShaderVar& fInQuadEdge;
591 GR_DECLARE_GEOMETRY_PROCESSOR_TEST;
593 typedef GrFragmentProcessor INHERITED;
596 GR_DEFINE_GEOMETRY_PROCESSOR_TEST(QuadEdgeEffect);
598 GrGeometryProcessor* QuadEdgeEffect::TestCreate(SkRandom* random,
600 const GrDrawTargetCaps& caps,
602 // Doesn't work without derivative instructions.
603 return caps.shaderDerivativeSupport() ? QuadEdgeEffect::Create() : NULL;
606 ///////////////////////////////////////////////////////////////////////////////
608 bool GrAAConvexPathRenderer::canDrawPath(const SkPath& path,
609 const SkStrokeRec& stroke,
610 const GrDrawTarget* target,
611 bool antiAlias) const {
612 return (target->caps()->shaderDerivativeSupport() && antiAlias &&
613 stroke.isFillStyle() && !path.isInverseFillType() && path.isConvex());
619 extern const GrVertexAttrib gPathAttribs[] = {
620 {kVec2f_GrVertexAttribType, 0, kPosition_GrVertexAttribBinding},
621 {kVec4f_GrVertexAttribType, sizeof(SkPoint), kGeometryProcessor_GrVertexAttribBinding}
626 bool GrAAConvexPathRenderer::onDrawPath(const SkPath& origPath,
628 GrDrawTarget* target,
631 const SkPath* path = &origPath;
632 if (path->isEmpty()) {
636 SkMatrix viewMatrix = target->getDrawState().getViewMatrix();
637 GrDrawTarget::AutoStateRestore asr;
638 if (!asr.setIdentity(target, GrDrawTarget::kPreserve_ASRInit)) {
641 GrDrawState* drawState = target->drawState();
643 // We use the fact that SkPath::transform path does subdivision based on
644 // perspective. Otherwise, we apply the view matrix when copying to the
645 // segment representation.
647 if (viewMatrix.hasPerspective()) {
648 origPath.transform(viewMatrix, &tmpPath);
650 viewMatrix = SkMatrix::I();
659 kPreallocSegmentCnt = 512 / sizeof(Segment),
660 kPreallocDrawCnt = 4,
662 SkSTArray<kPreallocSegmentCnt, Segment, true> segments;
665 // We can't simply use the path bounds because we may degenerate cubics to quads which produces
666 // new control points outside the original convex hull.
668 if (!get_segments(*path, viewMatrix, &segments, &fanPt, &vCount, &iCount, &devBounds)) {
672 // Our computed verts should all be within one pixel of the segment control points.
673 devBounds.outset(SK_Scalar1, SK_Scalar1);
675 drawState->setVertexAttribs<gPathAttribs>(SK_ARRAY_COUNT(gPathAttribs), sizeof(QuadVertex));
677 GrGeometryProcessor* quadProcessor = QuadEdgeEffect::Create();
678 drawState->setGeometryProcessor(quadProcessor)->unref();
680 GrDrawTarget::AutoReleaseGeometry arg(target, vCount, iCount);
681 if (!arg.succeeded()) {
684 verts = reinterpret_cast<QuadVertex*>(arg.vertices());
685 idxs = reinterpret_cast<uint16_t*>(arg.indices());
687 SkSTArray<kPreallocDrawCnt, Draw, true> draws;
688 create_vertices(segments, fanPt, &draws, verts, idxs);
692 SkRect tolDevBounds = devBounds;
693 tolDevBounds.outset(SK_Scalar1 / 10000, SK_Scalar1 / 10000);
695 actualBounds.set(verts[0].fPos, verts[1].fPos);
696 for (int i = 2; i < vCount; ++i) {
697 actualBounds.growToInclude(verts[i].fPos.fX, verts[i].fPos.fY);
699 SkASSERT(tolDevBounds.contains(actualBounds));
703 for (int i = 0; i < draws.count(); ++i) {
704 const Draw& draw = draws[i];
705 target->drawIndexed(kTriangles_GrPrimitiveType,
706 vOffset, // start vertex
711 vOffset += draw.fVertexCnt;