/*
* 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;
}