src/gpu/GrTesselatedPathRenderer.cpp

/*
 * Copyright 2011 Google Inc.
 *
 * Use of this source code is governed by a BSD-style license that can be
 * found in the LICENSE file.
 */


#include "GrTesselatedPathRenderer.h"

#include "GrDrawState.h"
#include "GrPathUtils.h"
#include "GrPoint.h"
#include "GrRenderTarget.h"
#include "GrTDArray.h"

#include "SkTemplates.h"

#include <limits.h>
#include <sk_glu.h>

typedef GrTDArray<GrDrawState::Edge> GrEdgeArray;
typedef GrTDArray<GrPoint> GrPointArray;
typedef GrTDArray<uint16_t> GrIndexArray;
typedef void (*TESSCB)();

// limit the allowable vertex range to approximately half of the representable
// IEEE exponent in order to avoid overflow when doing multiplies between
// vertex components,
const float kMaxVertexValue = 1e18f;

static inline GrDrawState::Edge computeEdge(const GrPoint& p,
                                             const GrPoint& q,
                                             float sign) {
    GrVec tangent = GrVec::Make(p.fY - q.fY, q.fX - p.fX);
    float scale = sign / tangent.length();
    float cross2 = p.fX * q.fY - q.fX * p.fY;
    return GrDrawState::Edge(tangent.fX * scale,
                              tangent.fY * scale,
                              cross2 * scale);
}

static inline GrPoint sanitizePoint(const GrPoint& pt) {
    GrPoint r;
    r.fX = SkScalarPin(pt.fX, 
                       SkFloatToScalar(-kMaxVertexValue), 
                       SkFloatToScalar(kMaxVertexValue));
    r.fY = SkScalarPin(pt.fY, 
                       SkFloatToScalar(-kMaxVertexValue), 
                       SkFloatToScalar(kMaxVertexValue));
    return r;
}

class GrTess {
public:
    GrTess(int count, unsigned winding_rule) {
        fTess = Sk_gluNewTess();
        Sk_gluTessProperty(fTess, GLU_TESS_WINDING_RULE, winding_rule);
        Sk_gluTessNormal(fTess, 0.0f, 0.0f, 1.0f);
        Sk_gluTessCallback(fTess, GLU_TESS_BEGIN_DATA, (TESSCB) &beginCB);
        Sk_gluTessCallback(fTess, GLU_TESS_VERTEX_DATA, (TESSCB) &vertexCB);
        Sk_gluTessCallback(fTess, GLU_TESS_END_DATA, (TESSCB) &endCB);
        Sk_gluTessCallback(fTess, GLU_TESS_EDGE_FLAG_DATA, (TESSCB) &edgeFlagCB);
        Sk_gluTessCallback(fTess, GLU_TESS_COMBINE_DATA, (TESSCB) &combineCB);
        fInVertices = new double[count * 3];
    }
    virtual ~GrTess() {
        Sk_gluDeleteTess(fTess);
        delete[] fInVertices;
    }
    void addVertex(const GrPoint& pt, int index) {
        if (index > USHRT_MAX) return;
        double* inVertex = &fInVertices[index * 3];
        inVertex[0] = pt.fX;
        inVertex[1] = pt.fY;
        inVertex[2] = 0.0;
        *fVertices.append() = pt;
        Sk_gluTessVertex(fTess, inVertex, reinterpret_cast<void*>(index));
    }
    void addVertices(const GrPoint* points, const uint16_t* contours, int numContours) {
        Sk_gluTessBeginPolygon(fTess, this);
        size_t i = 0;
        for (int j = 0; j < numContours; ++j) {
            Sk_gluTessBeginContour(fTess);
            size_t end = i + contours[j];
            for (; i < end; ++i) {
                addVertex(points[i], i);
            }
            Sk_gluTessEndContour(fTess);
        }
        Sk_gluTessEndPolygon(fTess);
    }
    GLUtesselator* tess() { return fTess; }
    const GrPointArray& vertices() const { return fVertices; }
protected:
    virtual void begin(GLenum type) = 0;
    virtual void vertex(int index) = 0;
    virtual void edgeFlag(bool flag) = 0;
    virtual void end() = 0;
    virtual int combine(GLdouble coords[3], int vertexIndices[4], 
                         GLfloat weight[4]) = 0;
    static void beginCB(GLenum type, void* data) {
        static_cast<GrTess*>(data)->begin(type);
    }
    static void vertexCB(void* vertexData, void* data) {
        static_cast<GrTess*>(data)->vertex(reinterpret_cast<long>(vertexData));
    }
    static void edgeFlagCB(GLboolean flag, void* data) {
        static_cast<GrTess*>(data)->edgeFlag(flag != 0);
    }
    static void endCB(void* data) {
        static_cast<GrTess*>(data)->end();
    }
    static void combineCB(GLdouble coords[3], void* vertexData[4],
                          GLfloat weight[4], void **outData, void* data) {
        int vertexIndex[4];
        vertexIndex[0] = reinterpret_cast<long>(vertexData[0]);
        vertexIndex[1] = reinterpret_cast<long>(vertexData[1]);
        vertexIndex[2] = reinterpret_cast<long>(vertexData[2]);
        vertexIndex[3] = reinterpret_cast<long>(vertexData[3]);
        GrTess* tess = static_cast<GrTess*>(data);
        int outIndex = tess->combine(coords, vertexIndex, weight);
        *reinterpret_cast<long*>(outData) = outIndex;
    }
protected:
    GLUtesselator* fTess;
    GrPointArray fVertices;
    double* fInVertices;
};

class GrPolygonTess : public GrTess {
public:
    GrPolygonTess(int count, unsigned winding_rule)
      : GrTess(count, winding_rule) {
    }
    ~GrPolygonTess() {
    }
    const GrIndexArray& indices() const { return fIndices; }
protected:
    virtual void begin(GLenum type) {
        GR_DEBUGASSERT(type == GL_TRIANGLES);
    }
    virtual void vertex(int index) {
        *fIndices.append() = index;
    }
    virtual void edgeFlag(bool flag) {}
    virtual void end() {}
    virtual int combine(GLdouble coords[3], int vertexIndices[4],
                         GLfloat weight[4]) {
        int index = fVertices.count();
        GrPoint p = GrPoint::Make(static_cast<float>(coords[0]),
                                  static_cast<float>(coords[1]));
        *fVertices.append() = p;
        return index;
    }
protected:
    GrIndexArray fIndices;
};

class GrEdgePolygonTess : public GrPolygonTess {
public:
    GrEdgePolygonTess(int count, unsigned winding_rule, const SkMatrix& matrix)
      : GrPolygonTess(count, winding_rule),
        fMatrix(matrix),
        fEdgeFlag(false),
        fEdgeVertex(-1),
        fTriStartVertex(-1),
        fEdges(NULL) {
    }
    ~GrEdgePolygonTess() {
        delete[] fEdges;
    }
    const GrDrawState::Edge* edges() const { return fEdges; }
private:
    void addEdge(int index0, int index1) {
        GrPoint p = fVertices[index0];
        GrPoint q = fVertices[index1];
        fMatrix.mapPoints(&p, 1);
        fMatrix.mapPoints(&q, 1);
        p = sanitizePoint(p);
        q = sanitizePoint(q);
        if (p == q) return;
        GrDrawState::Edge edge = computeEdge(p, q, 1.0f);
        fEdges[index0 * 2 + 1] = edge;
        fEdges[index1 * 2] = edge;
    }
    virtual void begin(GLenum type) {
        GR_DEBUGASSERT(type == GL_TRIANGLES);
        int count = fVertices.count() * 2;
        fEdges = new GrDrawState::Edge[count];
        memset(fEdges, 0, count * sizeof(GrDrawState::Edge));
    }
    virtual void edgeFlag(bool flag) {
        fEdgeFlag = flag;
    }
    virtual void vertex(int index) {
        bool triStart = fIndices.count() % 3 == 0;
        GrPolygonTess::vertex(index);
        if (fEdgeVertex != -1) {
            if (triStart) {
                addEdge(fEdgeVertex, fTriStartVertex);
            } else {
                addEdge(fEdgeVertex, index);
            }
        }
        if (triStart) {
            fTriStartVertex = index;
        }
        if (fEdgeFlag) {
            fEdgeVertex = index;
        } else {
            fEdgeVertex = -1;
        }
    }
    virtual void end() {
        if (fEdgeVertex != -1) {
            addEdge(fEdgeVertex, fTriStartVertex);
        }
    }
    GrMatrix fMatrix;
    bool fEdgeFlag;
    int fEdgeVertex, fTriStartVertex;
    GrDrawState::Edge* fEdges;
};

class GrBoundaryTess : public GrTess {
public:
    GrBoundaryTess(int count, unsigned winding_rule)
      : GrTess(count, winding_rule),
        fContourStart(0) {
        Sk_gluTessProperty(fTess, GLU_TESS_BOUNDARY_ONLY, 1);
    }
    ~GrBoundaryTess() {
    }
    GrPointArray& contourPoints() { return fContourPoints; }
    const GrIndexArray& contours() const { return fContours; }
private:
    virtual void begin(GLenum type) {
        fContourStart = fContourPoints.count();
    }
    virtual void vertex(int index) {
        *fContourPoints.append() = fVertices.at(index);
    }
    virtual void edgeFlag(bool flag) {}
    virtual void end() {
        *fContours.append() = fContourPoints.count() - fContourStart;
    }
    virtual int combine(GLdouble coords[3], int vertexIndices[4],
                        GLfloat weight[4]) {
        int index = fVertices.count();
        *fVertices.append() = GrPoint::Make(static_cast<float>(coords[0]),
                                            static_cast<float>(coords[1]));
        return index;
    }
    GrPointArray fContourPoints;
    GrIndexArray fContours;
    size_t fContourStart;
};

static bool nearlyEqual(float a, float b) {
    return fabsf(a - b) < 0.0001f;
}

static bool nearlyEqual(const GrPoint& a, const GrPoint& b) {
    return nearlyEqual(a.fX, b.fX) && nearlyEqual(a.fY, b.fY);
}

static bool parallel(const GrDrawState::Edge& a, const GrDrawState::Edge& b) {
    return (nearlyEqual(a.fX, b.fX) && nearlyEqual(a.fY, b.fY)) ||
           (nearlyEqual(a.fX, -b.fX) && nearlyEqual(a.fY, -b.fY));
}

static unsigned fill_type_to_glu_winding_rule(GrPathFill fill) {
    switch (fill) {
        case kWinding_PathFill:
            return GLU_TESS_WINDING_NONZERO;
        case kEvenOdd_PathFill:
            return GLU_TESS_WINDING_ODD;
        case kInverseWinding_PathFill:
            return GLU_TESS_WINDING_POSITIVE;
        case kInverseEvenOdd_PathFill:
            return GLU_TESS_WINDING_ODD;
        case kHairLine_PathFill:
            return GLU_TESS_WINDING_NONZERO;  // FIXME:  handle this
        default:
            GrAssert(!"Unknown path fill!");
            return 0;
    }
}

GrTesselatedPathRenderer::GrTesselatedPathRenderer() {
}

static bool isCCW(const GrPoint* pts, int count) {
    GrVec v1, v2;
    do {
        v1 = pts[1] - pts[0];
        v2 = pts[2] - pts[1];
        pts++;
        count--;
    } while (nearlyEqual(v1, v2) && count > 3);
    return v1.cross(v2) < 0;
}

static bool validEdge(const GrDrawState::Edge& edge) {
    return !(edge.fX == 0.0f && edge.fY == 0.0f && edge.fZ == 0.0f);
}

static size_t computeEdgesAndIntersect(const GrMatrix& matrix,
                                       const GrMatrix& inverse,
                                       GrPoint* vertices,
                                       size_t numVertices,
                                       GrEdgeArray* edges,
                                       float sign) {
    if (numVertices < 3) {
        return 0;
    }
    matrix.mapPoints(vertices, numVertices);
    if (sign == 0.0f) {
        sign = isCCW(vertices, numVertices) ? -1.0f : 1.0f;
    }
    GrPoint p = sanitizePoint(vertices[numVertices - 1]);
    for (size_t i = 0; i < numVertices; ++i) {
        GrPoint q = sanitizePoint(vertices[i]);
        if (p == q) {
            continue;
        }
        GrDrawState::Edge edge = computeEdge(p, q, sign);
        edge.fZ += 0.5f;    // Offset by half a pixel along the tangent.
        *edges->append() = edge;
        p = q;
    }
    int count = edges->count();
    if (count == 0) {
        return 0;
    }
    GrDrawState::Edge prev_edge = edges->at(0);
    for (int i = 0; i < count; ++i) {
        GrDrawState::Edge edge = edges->at(i < count - 1 ? i + 1 : 0);
        if (parallel(edge, prev_edge)) {
            // 3 points are collinear; offset by half the tangent instead
            vertices[i].fX -= edge.fX * 0.5f;
            vertices[i].fY -= edge.fY * 0.5f;
        } else {
            vertices[i] = prev_edge.intersect(edge);
        }
        inverse.mapPoints(&vertices[i], 1);
        prev_edge = edge;
    }
    return edges->count();
}

bool GrTesselatedPathRenderer::onDrawPath(const SkPath& path,
                                          GrPathFill fill,
                                          const GrVec* translate,
                                          GrDrawTarget* target,
                                          GrDrawState::StageMask stageMask,
                                          bool antiAlias) {

    GrDrawTarget::AutoStateRestore asr(target, GrDrawTarget::kPreserve_ASRInit);
    GrDrawState* drawState = target->drawState();
    // face culling doesn't make sense here
    GrAssert(GrDrawState::kBoth_DrawFace == drawState->getDrawFace());

    GrMatrix viewM = drawState->getViewMatrix();

    GrScalar tol = GR_Scalar1;
    tol = GrPathUtils::scaleToleranceToSrc(tol, viewM, path.getBounds());
    GrScalar tolSqd = GrMul(tol, tol);

    int subpathCnt;
    int maxPts = GrPathUtils::worstCasePointCount(path, &subpathCnt, tol);

    GrVertexLayout layout = 0;
    for (int s = 0; s < GrDrawState::kNumStages; ++s) {
        if ((1 << s) & stageMask) {
            layout |= GrDrawTarget::StagePosAsTexCoordVertexLayoutBit(s);
        }
    }

    bool inverted = GrIsFillInverted(fill);
    if (inverted) {
        maxPts += 4;
        subpathCnt++;
    }
    if (maxPts > USHRT_MAX) {
        return false;
    }
    SkAutoSTMalloc<8, GrPoint> baseMem(maxPts);
    GrPoint* base = baseMem;
    GrPoint* vert = base;
    GrPoint* subpathBase = base;

    SkAutoSTMalloc<8, uint16_t> subpathVertCount(subpathCnt);

    GrPoint pts[4];
    SkPath::Iter iter(path, false);

    bool first = true;
    int subpath = 0;

    for (;;) {
        switch (iter.next(pts)) {
            case kMove_PathCmd:
                if (!first) {
                    subpathVertCount[subpath] = vert-subpathBase;
                    subpathBase = vert;
                    ++subpath;
                }
                *vert = pts[0];
                vert++;
                break;
            case kLine_PathCmd:
                *vert = pts[1];
                vert++;
                break;
            case kQuadratic_PathCmd: {
                GrPathUtils::generateQuadraticPoints(pts[0], pts[1], pts[2],
                                                     tolSqd, &vert,
                                                     GrPathUtils::quadraticPointCount(pts, tol));
                break;
            }
            case kCubic_PathCmd: {
                GrPathUtils::generateCubicPoints(pts[0], pts[1], pts[2], pts[3],
                                                 tolSqd, &vert,
                                                 GrPathUtils::cubicPointCount(pts, tol));
                break;
            }
            case kClose_PathCmd:
                break;
            case kEnd_PathCmd:
                subpathVertCount[subpath] = vert-subpathBase;
                ++subpath; // this could be only in debug
                goto FINISHED;
        }
        first = false;
    }
FINISHED:
    if (NULL != translate && 0 != translate->fX && 0 != translate->fY) {
        for (int i = 0; i < vert - base; i++) {
            base[i].offset(translate->fX, translate->fY);
        }
    }

    if (inverted) {
        GrRect bounds;
        GrAssert(NULL != drawState->getRenderTarget());
        bounds.setLTRB(0, 0,
                       GrIntToScalar(drawState->getRenderTarget()->width()),
                       GrIntToScalar(drawState->getRenderTarget()->height()));
        GrMatrix vmi;
        if (drawState->getViewInverse(&vmi)) {
            vmi.mapRect(&bounds);
        }
        *vert++ = GrPoint::Make(bounds.fLeft, bounds.fTop);
        *vert++ = GrPoint::Make(bounds.fLeft, bounds.fBottom);
        *vert++ = GrPoint::Make(bounds.fRight, bounds.fBottom);
        *vert++ = GrPoint::Make(bounds.fRight, bounds.fTop);
        subpathVertCount[subpath++] = 4;
    }

    GrAssert(subpath == subpathCnt);
    GrAssert((vert - base) <= maxPts);

    size_t count = vert - base;

    if (count < 3) {
        return true;
    }

    if (subpathCnt == 1 && !inverted && path.isConvex()) {
        if (antiAlias) {
            GrEdgeArray edges;
            GrMatrix inverse, matrix = drawState->getViewMatrix();
            drawState->getViewInverse(&inverse);

            count = computeEdgesAndIntersect(matrix, inverse, base, count, &edges, 0.0f);
            size_t maxEdges = target->getMaxEdges();
            if (count == 0) {
                return true;
            }
            if (count <= maxEdges) {
                // All edges fit; upload all edges and draw all verts as a fan
                target->setVertexSourceToArray(layout, base, count);
                drawState->setEdgeAAData(&edges[0], count);
                target->drawNonIndexed(kTriangleFan_PrimitiveType, 0, count);
            } else {
                // Upload "maxEdges" edges and verts at a time, and draw as
                // separate fans
                for (size_t i = 0; i < count - 2; i += maxEdges - 2) {
                    edges[i] = edges[0];
                    base[i] = base[0];
                    int size = GR_CT_MIN(count - i, maxEdges);
                    target->setVertexSourceToArray(layout, &base[i], size);
                    drawState->setEdgeAAData(&edges[i], size);
                    target->drawNonIndexed(kTriangleFan_PrimitiveType, 0, size);
                }
            }
            drawState->setEdgeAAData(NULL, 0);
        } else {
            target->setVertexSourceToArray(layout, base, count);
            target->drawNonIndexed(kTriangleFan_PrimitiveType, 0, count);
        }
        return true;
    }

    if (antiAlias) {
        // Run the tesselator once to get the boundaries.
        GrBoundaryTess btess(count, fill_type_to_glu_winding_rule(fill));
        btess.addVertices(base, subpathVertCount, subpathCnt);

        GrMatrix inverse, matrix = drawState->getViewMatrix();
        if (!drawState->getViewInverse(&inverse)) {
            return false;
        }

        if (btess.vertices().count() > USHRT_MAX) {
            return false;
        }

        // Inflate the boundary, and run the tesselator again to generate
        // interior polys.
        const GrPointArray& contourPoints = btess.contourPoints();
        const GrIndexArray& contours = btess.contours();
        GrEdgePolygonTess ptess(contourPoints.count(), GLU_TESS_WINDING_NONZERO, matrix);

        size_t i = 0;
        Sk_gluTessBeginPolygon(ptess.tess(), &ptess);
        for (int contour = 0; contour < contours.count(); ++contour) {
            int count = contours[contour];
            GrEdgeArray edges;
            int newCount = computeEdgesAndIntersect(matrix, inverse, &btess.contourPoints()[i], count, &edges, 1.0f);
            Sk_gluTessBeginContour(ptess.tess());
            for (int j = 0; j < newCount; j++) {
                ptess.addVertex(contourPoints[i + j], ptess.vertices().count());
            }
            i += count;
            Sk_gluTessEndContour(ptess.tess());
        }

        Sk_gluTessEndPolygon(ptess.tess());

        if (ptess.vertices().count() > USHRT_MAX) {
            return false;
        }

        // Draw the resulting polys and upload their edge data.
        drawState->enableState(GrDrawState::kEdgeAAConcave_StateBit);
        const GrPointArray& vertices = ptess.vertices();
        const GrIndexArray& indices = ptess.indices();
        const GrDrawState::Edge* edges = ptess.edges();
        GR_DEBUGASSERT(indices.count() % 3 == 0);
        for (int i = 0; i < indices.count(); i += 3) {
            GrPoint tri_verts[3];
            int index0 = indices[i];
            int index1 = indices[i + 1];
            int index2 = indices[i + 2];
            tri_verts[0] = vertices[index0];
            tri_verts[1] = vertices[index1];
            tri_verts[2] = vertices[index2];
            GrDrawState::Edge tri_edges[6];
            int t = 0;
            const GrDrawState::Edge& edge0 = edges[index0 * 2];
            const GrDrawState::Edge& edge1 = edges[index0 * 2 + 1];
            const GrDrawState::Edge& edge2 = edges[index1 * 2];
            const GrDrawState::Edge& edge3 = edges[index1 * 2 + 1];
            const GrDrawState::Edge& edge4 = edges[index2 * 2];
            const GrDrawState::Edge& edge5 = edges[index2 * 2 + 1];
            if (validEdge(edge0) && validEdge(edge1)) {
                tri_edges[t++] = edge0;
                tri_edges[t++] = edge1;
            }
            if (validEdge(edge2) && validEdge(edge3)) {
                tri_edges[t++] = edge2;
                tri_edges[t++] = edge3;
            }
            if (validEdge(edge4) && validEdge(edge5)) {
                tri_edges[t++] = edge4;
                tri_edges[t++] = edge5;
            }
            drawState->setEdgeAAData(&tri_edges[0], t);
            target->setVertexSourceToArray(layout, &tri_verts[0], 3);
            target->drawNonIndexed(kTriangles_PrimitiveType, 0, 3);
        }
        drawState->setEdgeAAData(NULL, 0);
        drawState->disableState(GrDrawState::kEdgeAAConcave_StateBit);
        return true;
    }

    GrPolygonTess ptess(count, fill_type_to_glu_winding_rule(fill));
    ptess.addVertices(base, subpathVertCount, subpathCnt);
    const GrPointArray& vertices = ptess.vertices();
    const GrIndexArray& indices = ptess.indices();
    if (indices.count() > 0) {
        target->setVertexSourceToArray(layout, vertices.begin(), vertices.count());
        target->setIndexSourceToArray(indices.begin(), indices.count());
        target->drawIndexed(kTriangles_PrimitiveType,
                            0,
                            0,
                            vertices.count(),
                            indices.count());
    }
    return true;
}

bool GrTesselatedPathRenderer::canDrawPath(const SkPath& path,
                                           GrPathFill fill,
                                           const GrDrawTarget* target,
                                           bool antiAlias) const {
    return kHairLine_PathFill != fill;
}