| |
| /* |
| * Copyright 2012 Google Inc. |
| * |
| * Use of this source code is governed by a BSD-style license that can be |
| * found in the LICENSE file. |
| */ |
| |
| #include "GrAAConvexPathRenderer.h" |
| |
| #include "GrContext.h" |
| #include "GrDrawState.h" |
| #include "GrPathUtils.h" |
| #include "SkString.h" |
| #include "SkStrokeRec.h" |
| #include "SkTrace.h" |
| |
| GrAAConvexPathRenderer::GrAAConvexPathRenderer() { |
| } |
| |
| namespace { |
| |
| struct Segment { |
| enum { |
| // These enum values are assumed in member functions below. |
| kLine = 0, |
| kQuad = 1, |
| } fType; |
| |
| // line uses one pt, quad uses 2 pts |
| GrPoint fPts[2]; |
| // normal to edge ending at each pt |
| GrVec fNorms[2]; |
| // is the corner where the previous segment meets this segment |
| // sharp. If so, fMid is a normalized bisector facing outward. |
| GrVec fMid; |
| |
| int countPoints() { |
| GR_STATIC_ASSERT(0 == kLine && 1 == kQuad); |
| return fType + 1; |
| } |
| const SkPoint& endPt() const { |
| GR_STATIC_ASSERT(0 == kLine && 1 == kQuad); |
| return fPts[fType]; |
| }; |
| const SkPoint& endNorm() const { |
| GR_STATIC_ASSERT(0 == kLine && 1 == kQuad); |
| return fNorms[fType]; |
| }; |
| }; |
| |
| typedef SkTArray<Segment, true> SegmentArray; |
| |
| void center_of_mass(const SegmentArray& segments, SkPoint* c) { |
| SkScalar area = 0; |
| SkPoint center = {0, 0}; |
| int count = segments.count(); |
| SkPoint p0 = {0, 0}; |
| if (count > 2) { |
| // We translate the polygon so that the first point is at the origin. |
| // This avoids some precision issues with small area polygons far away |
| // from the origin. |
| p0 = segments[0].endPt(); |
| SkPoint pi; |
| SkPoint pj; |
| // the first and last iteration of the below loop would compute |
| // zeros since the starting / ending point is (0,0). So instead we start |
| // at i=1 and make the last iteration i=count-2. |
| pj = segments[1].endPt() - p0; |
| for (int i = 1; i < count - 1; ++i) { |
| pi = pj; |
| const SkPoint pj = segments[i + 1].endPt() - p0; |
| |
| SkScalar t = SkScalarMul(pi.fX, pj.fY) - SkScalarMul(pj.fX, pi.fY); |
| area += t; |
| center.fX += (pi.fX + pj.fX) * t; |
| center.fY += (pi.fY + pj.fY) * t; |
| |
| } |
| } |
| // If the poly has no area then we instead return the average of |
| // its points. |
| if (SkScalarNearlyZero(area)) { |
| SkPoint avg; |
| avg.set(0, 0); |
| for (int i = 0; i < count; ++i) { |
| const SkPoint& pt = segments[i].endPt(); |
| avg.fX += pt.fX; |
| avg.fY += pt.fY; |
| } |
| SkScalar denom = SK_Scalar1 / count; |
| avg.scale(denom); |
| *c = avg; |
| } else { |
| area *= 3; |
| area = SkScalarDiv(SK_Scalar1, area); |
| center.fX = SkScalarMul(center.fX, area); |
| center.fY = SkScalarMul(center.fY, area); |
| // undo the translate of p0 to the origin. |
| *c = center + p0; |
| } |
| GrAssert(!SkScalarIsNaN(c->fX) && !SkScalarIsNaN(c->fY)); |
| } |
| |
| void compute_vectors(SegmentArray* segments, |
| SkPoint* fanPt, |
| SkPath::Direction dir, |
| int* vCount, |
| int* iCount) { |
| center_of_mass(*segments, fanPt); |
| int count = segments->count(); |
| |
| // Make the normals point towards the outside |
| GrPoint::Side normSide; |
| if (dir == SkPath::kCCW_Direction) { |
| normSide = GrPoint::kRight_Side; |
| } else { |
| normSide = GrPoint::kLeft_Side; |
| } |
| |
| *vCount = 0; |
| *iCount = 0; |
| // compute normals at all points |
| for (int a = 0; a < count; ++a) { |
| const Segment& sega = (*segments)[a]; |
| int b = (a + 1) % count; |
| Segment& segb = (*segments)[b]; |
| |
| const GrPoint* prevPt = &sega.endPt(); |
| int n = segb.countPoints(); |
| for (int p = 0; p < n; ++p) { |
| segb.fNorms[p] = segb.fPts[p] - *prevPt; |
| segb.fNorms[p].normalize(); |
| segb.fNorms[p].setOrthog(segb.fNorms[p], normSide); |
| prevPt = &segb.fPts[p]; |
| } |
| if (Segment::kLine == segb.fType) { |
| *vCount += 5; |
| *iCount += 9; |
| } else { |
| *vCount += 6; |
| *iCount += 12; |
| } |
| } |
| |
| // compute mid-vectors where segments meet. TODO: Detect shallow corners |
| // and leave out the wedges and close gaps by stitching segments together. |
| for (int a = 0; a < count; ++a) { |
| const Segment& sega = (*segments)[a]; |
| int b = (a + 1) % count; |
| Segment& segb = (*segments)[b]; |
| segb.fMid = segb.fNorms[0] + sega.endNorm(); |
| segb.fMid.normalize(); |
| // corner wedges |
| *vCount += 4; |
| *iCount += 6; |
| } |
| } |
| |
| struct DegenerateTestData { |
| DegenerateTestData() { fStage = kInitial; } |
| bool isDegenerate() const { return kNonDegenerate != fStage; } |
| enum { |
| kInitial, |
| kPoint, |
| kLine, |
| kNonDegenerate |
| } fStage; |
| GrPoint fFirstPoint; |
| GrVec fLineNormal; |
| SkScalar fLineC; |
| }; |
| |
| void update_degenerate_test(DegenerateTestData* data, const GrPoint& pt) { |
| static const SkScalar TOL = (SK_Scalar1 / 16); |
| static const SkScalar TOL_SQD = SkScalarMul(TOL, TOL); |
| |
| switch (data->fStage) { |
| case DegenerateTestData::kInitial: |
| data->fFirstPoint = pt; |
| data->fStage = DegenerateTestData::kPoint; |
| break; |
| case DegenerateTestData::kPoint: |
| if (pt.distanceToSqd(data->fFirstPoint) > TOL_SQD) { |
| data->fLineNormal = pt - data->fFirstPoint; |
| data->fLineNormal.normalize(); |
| data->fLineNormal.setOrthog(data->fLineNormal); |
| data->fLineC = -data->fLineNormal.dot(data->fFirstPoint); |
| data->fStage = DegenerateTestData::kLine; |
| } |
| break; |
| case DegenerateTestData::kLine: |
| if (SkScalarAbs(data->fLineNormal.dot(pt) + data->fLineC) > TOL) { |
| data->fStage = DegenerateTestData::kNonDegenerate; |
| } |
| case DegenerateTestData::kNonDegenerate: |
| break; |
| default: |
| GrCrash("Unexpected degenerate test stage."); |
| } |
| } |
| |
| inline bool get_direction(const SkPath& path, const SkMatrix& m, SkPath::Direction* dir) { |
| if (!path.cheapComputeDirection(dir)) { |
| return false; |
| } |
| // check whether m reverses the orientation |
| GrAssert(!m.hasPerspective()); |
| SkScalar det2x2 = SkScalarMul(m.get(SkMatrix::kMScaleX), m.get(SkMatrix::kMScaleY)) - |
| SkScalarMul(m.get(SkMatrix::kMSkewX), m.get(SkMatrix::kMSkewY)); |
| if (det2x2 < 0) { |
| *dir = SkPath::OppositeDirection(*dir); |
| } |
| return true; |
| } |
| |
| bool get_segments(const SkPath& path, |
| const SkMatrix& m, |
| SegmentArray* segments, |
| SkPoint* fanPt, |
| int* vCount, |
| int* iCount) { |
| SkPath::Iter iter(path, true); |
| // This renderer over-emphasizes very thin path regions. We use the distance |
| // to the path from the sample to compute coverage. Every pixel intersected |
| // by the path will be hit and the maximum distance is sqrt(2)/2. We don't |
| // notice that the sample may be close to a very thin area of the path and |
| // thus should be very light. This is particularly egregious for degenerate |
| // line paths. We detect paths that are very close to a line (zero area) and |
| // draw nothing. |
| DegenerateTestData degenerateData; |
| SkPath::Direction dir; |
| // get_direction can fail for some degenerate paths. |
| if (!get_direction(path, m, &dir)) { |
| return false; |
| } |
| |
| for (;;) { |
| GrPoint pts[4]; |
| GrPathCmd cmd = (GrPathCmd)iter.next(pts); |
| switch (cmd) { |
| case kMove_PathCmd: |
| m.mapPoints(pts, 1); |
| update_degenerate_test(°enerateData, pts[0]); |
| break; |
| case kLine_PathCmd: { |
| m.mapPoints(pts + 1, 1); |
| update_degenerate_test(°enerateData, pts[1]); |
| segments->push_back(); |
| segments->back().fType = Segment::kLine; |
| segments->back().fPts[0] = pts[1]; |
| break; |
| } |
| case kQuadratic_PathCmd: |
| m.mapPoints(pts + 1, 2); |
| update_degenerate_test(°enerateData, pts[1]); |
| update_degenerate_test(°enerateData, pts[2]); |
| segments->push_back(); |
| segments->back().fType = Segment::kQuad; |
| segments->back().fPts[0] = pts[1]; |
| segments->back().fPts[1] = pts[2]; |
| break; |
| case kCubic_PathCmd: { |
| m.mapPoints(pts, 4); |
| update_degenerate_test(°enerateData, pts[1]); |
| update_degenerate_test(°enerateData, pts[2]); |
| update_degenerate_test(°enerateData, pts[3]); |
| // unlike quads and lines, the pts[0] will also be read (in |
| // convertCubicToQuads). |
| SkSTArray<15, SkPoint, true> quads; |
| GrPathUtils::convertCubicToQuads(pts, SK_Scalar1, true, dir, &quads); |
| int count = quads.count(); |
| for (int q = 0; q < count; q += 3) { |
| segments->push_back(); |
| segments->back().fType = Segment::kQuad; |
| segments->back().fPts[0] = quads[q + 1]; |
| segments->back().fPts[1] = quads[q + 2]; |
| } |
| break; |
| }; |
| case kEnd_PathCmd: |
| if (degenerateData.isDegenerate()) { |
| return false; |
| } else { |
| compute_vectors(segments, fanPt, dir, vCount, iCount); |
| return true; |
| } |
| default: |
| break; |
| } |
| } |
| } |
| |
| struct QuadVertex { |
| GrPoint fPos; |
| GrPoint fUV; |
| SkScalar fD0; |
| SkScalar fD1; |
| }; |
| |
| void create_vertices(const SegmentArray& segments, |
| const SkPoint& fanPt, |
| QuadVertex* verts, |
| uint16_t* idxs) { |
| int v = 0; |
| int i = 0; |
| |
| int count = segments.count(); |
| for (int a = 0; a < count; ++a) { |
| const Segment& sega = segments[a]; |
| int b = (a + 1) % count; |
| const Segment& segb = segments[b]; |
| |
| // FIXME: These tris are inset in the 1 unit arc around the corner |
| verts[v + 0].fPos = sega.endPt(); |
| verts[v + 1].fPos = verts[v + 0].fPos + sega.endNorm(); |
| verts[v + 2].fPos = verts[v + 0].fPos + segb.fMid; |
| verts[v + 3].fPos = verts[v + 0].fPos + segb.fNorms[0]; |
| verts[v + 0].fUV.set(0,0); |
| verts[v + 1].fUV.set(0,-SK_Scalar1); |
| verts[v + 2].fUV.set(0,-SK_Scalar1); |
| verts[v + 3].fUV.set(0,-SK_Scalar1); |
| verts[v + 0].fD0 = verts[v + 0].fD1 = -SK_Scalar1; |
| verts[v + 1].fD0 = verts[v + 1].fD1 = -SK_Scalar1; |
| verts[v + 2].fD0 = verts[v + 2].fD1 = -SK_Scalar1; |
| verts[v + 3].fD0 = verts[v + 3].fD1 = -SK_Scalar1; |
| |
| idxs[i + 0] = v + 0; |
| idxs[i + 1] = v + 2; |
| idxs[i + 2] = v + 1; |
| idxs[i + 3] = v + 0; |
| idxs[i + 4] = v + 3; |
| idxs[i + 5] = v + 2; |
| |
| v += 4; |
| i += 6; |
| |
| if (Segment::kLine == segb.fType) { |
| verts[v + 0].fPos = fanPt; |
| verts[v + 1].fPos = sega.endPt(); |
| verts[v + 2].fPos = segb.fPts[0]; |
| |
| verts[v + 3].fPos = verts[v + 1].fPos + segb.fNorms[0]; |
| verts[v + 4].fPos = verts[v + 2].fPos + segb.fNorms[0]; |
| |
| // we draw the line edge as a degenerate quad (u is 0, v is the |
| // signed distance to the edge) |
| SkScalar dist = fanPt.distanceToLineBetween(verts[v + 1].fPos, |
| verts[v + 2].fPos); |
| verts[v + 0].fUV.set(0, dist); |
| verts[v + 1].fUV.set(0, 0); |
| verts[v + 2].fUV.set(0, 0); |
| verts[v + 3].fUV.set(0, -SK_Scalar1); |
| verts[v + 4].fUV.set(0, -SK_Scalar1); |
| |
| verts[v + 0].fD0 = verts[v + 0].fD1 = -SK_Scalar1; |
| verts[v + 1].fD0 = verts[v + 1].fD1 = -SK_Scalar1; |
| verts[v + 2].fD0 = verts[v + 2].fD1 = -SK_Scalar1; |
| verts[v + 3].fD0 = verts[v + 3].fD1 = -SK_Scalar1; |
| verts[v + 4].fD0 = verts[v + 4].fD1 = -SK_Scalar1; |
| |
| idxs[i + 0] = v + 0; |
| idxs[i + 1] = v + 2; |
| idxs[i + 2] = v + 1; |
| |
| idxs[i + 3] = v + 3; |
| idxs[i + 4] = v + 1; |
| idxs[i + 5] = v + 2; |
| |
| idxs[i + 6] = v + 4; |
| idxs[i + 7] = v + 3; |
| idxs[i + 8] = v + 2; |
| |
| v += 5; |
| i += 9; |
| } else { |
| GrPoint qpts[] = {sega.endPt(), segb.fPts[0], segb.fPts[1]}; |
| |
| GrVec midVec = segb.fNorms[0] + segb.fNorms[1]; |
| midVec.normalize(); |
| |
| verts[v + 0].fPos = fanPt; |
| verts[v + 1].fPos = qpts[0]; |
| verts[v + 2].fPos = qpts[2]; |
| verts[v + 3].fPos = qpts[0] + segb.fNorms[0]; |
| verts[v + 4].fPos = qpts[2] + segb.fNorms[1]; |
| verts[v + 5].fPos = qpts[1] + midVec; |
| |
| SkScalar c = segb.fNorms[0].dot(qpts[0]); |
| verts[v + 0].fD0 = -segb.fNorms[0].dot(fanPt) + c; |
| verts[v + 1].fD0 = 0.f; |
| verts[v + 2].fD0 = -segb.fNorms[0].dot(qpts[2]) + c; |
| verts[v + 3].fD0 = -SK_ScalarMax/100; |
| verts[v + 4].fD0 = -SK_ScalarMax/100; |
| verts[v + 5].fD0 = -SK_ScalarMax/100; |
| |
| c = segb.fNorms[1].dot(qpts[2]); |
| verts[v + 0].fD1 = -segb.fNorms[1].dot(fanPt) + c; |
| verts[v + 1].fD1 = -segb.fNorms[1].dot(qpts[0]) + c; |
| verts[v + 2].fD1 = 0.f; |
| verts[v + 3].fD1 = -SK_ScalarMax/100; |
| verts[v + 4].fD1 = -SK_ScalarMax/100; |
| verts[v + 5].fD1 = -SK_ScalarMax/100; |
| |
| GrPathUtils::QuadUVMatrix toUV(qpts); |
| toUV.apply<6, sizeof(QuadVertex), sizeof(GrPoint)>(verts + v); |
| |
| idxs[i + 0] = v + 3; |
| idxs[i + 1] = v + 1; |
| idxs[i + 2] = v + 2; |
| idxs[i + 3] = v + 4; |
| idxs[i + 4] = v + 3; |
| idxs[i + 5] = v + 2; |
| |
| idxs[i + 6] = v + 5; |
| idxs[i + 7] = v + 3; |
| idxs[i + 8] = v + 4; |
| |
| idxs[i + 9] = v + 0; |
| idxs[i + 10] = v + 2; |
| idxs[i + 11] = v + 1; |
| |
| v += 6; |
| i += 12; |
| } |
| } |
| } |
| |
| } |
| |
| bool GrAAConvexPathRenderer::canDrawPath(const SkPath& path, |
| const SkStrokeRec& stroke, |
| const GrDrawTarget* target, |
| bool antiAlias) const { |
| return (target->getCaps().shaderDerivativeSupport() && antiAlias && |
| stroke.isFillStyle() && !path.isInverseFillType() && path.isConvex()); |
| } |
| |
| bool GrAAConvexPathRenderer::onDrawPath(const SkPath& origPath, |
| const SkStrokeRec&, |
| GrDrawTarget* target, |
| bool antiAlias) { |
| |
| const SkPath* path = &origPath; |
| if (path->isEmpty()) { |
| return true; |
| } |
| GrDrawState* drawState = target->drawState(); |
| |
| GrDrawState::AutoDeviceCoordDraw adcd(drawState); |
| if (!adcd.succeeded()) { |
| return false; |
| } |
| const SkMatrix* vm = &adcd.getOriginalMatrix(); |
| |
| GrVertexLayout layout = 0; |
| layout |= GrDrawState::kEdge_VertexLayoutBit; |
| |
| // We use the fact that SkPath::transform path does subdivision based on |
| // perspective. Otherwise, we apply the view matrix when copying to the |
| // segment representation. |
| SkPath tmpPath; |
| if (vm->hasPerspective()) { |
| origPath.transform(*vm, &tmpPath); |
| path = &tmpPath; |
| vm = &SkMatrix::I(); |
| } |
| |
| QuadVertex *verts; |
| uint16_t* idxs; |
| |
| int vCount; |
| int iCount; |
| enum { |
| kPreallocSegmentCnt = 512 / sizeof(Segment), |
| }; |
| SkSTArray<kPreallocSegmentCnt, Segment, true> segments; |
| SkPoint fanPt; |
| |
| if (!get_segments(*path, *vm, &segments, &fanPt, &vCount, &iCount)) { |
| return false; |
| } |
| |
| GrDrawTarget::AutoReleaseGeometry arg(target, layout, vCount, iCount); |
| if (!arg.succeeded()) { |
| return false; |
| } |
| verts = reinterpret_cast<QuadVertex*>(arg.vertices()); |
| idxs = reinterpret_cast<uint16_t*>(arg.indices()); |
| |
| create_vertices(segments, fanPt, verts, idxs); |
| |
| GrDrawState::VertexEdgeType oldEdgeType = drawState->getVertexEdgeType(); |
| drawState->setVertexEdgeType(GrDrawState::kQuad_EdgeType); |
| target->drawIndexed(kTriangles_GrPrimitiveType, |
| 0, // start vertex |
| 0, // start index |
| vCount, |
| iCount); |
| drawState->setVertexEdgeType(oldEdgeType); |
| |
| return true; |
| } |
