1
2/*
3 * Copyright 2011 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
10#include "GrTesselatedPathRenderer.h"
11
12#include "GrDrawState.h"
13#include "GrPathUtils.h"
14#include "GrPoint.h"
15#include "GrRenderTarget.h"
16#include "GrTDArray.h"
17
18#include "SkTemplates.h"
19
20#include <limits.h>
21#include <sk_glu.h>
22
23typedef GrTDArray<GrDrawState::Edge> GrEdgeArray;
24typedef GrTDArray<GrPoint> GrPointArray;
25typedef GrTDArray<uint16_t> GrIndexArray;
26typedef void (*TESSCB)();
27
28// limit the allowable vertex range to approximately half of the representable
29// IEEE exponent in order to avoid overflow when doing multiplies between
30// vertex components,
31const float kMaxVertexValue = 1e18f;
32
33static inline GrDrawState::Edge computeEdge(const GrPoint& p,
34                                             const GrPoint& q,
35                                             float sign) {
36    GrVec tangent = GrVec::Make(p.fY - q.fY, q.fX - p.fX);
37    float scale = sign / tangent.length();
38    float cross2 = p.fX * q.fY - q.fX * p.fY;
39    return GrDrawState::Edge(tangent.fX * scale,
40                              tangent.fY * scale,
41                              cross2 * scale);
42}
43
44static inline GrPoint sanitizePoint(const GrPoint& pt) {
45    GrPoint r;
46    r.fX = SkScalarPin(pt.fX, -kMaxVertexValue, kMaxVertexValue);
47    r.fY = SkScalarPin(pt.fY, -kMaxVertexValue, kMaxVertexValue);
48    return r;
49}
50
51class GrTess {
52public:
53    GrTess(int count, unsigned winding_rule) {
54        fTess = Sk_gluNewTess();
55        Sk_gluTessProperty(fTess, GLU_TESS_WINDING_RULE, winding_rule);
56        Sk_gluTessNormal(fTess, 0.0f, 0.0f, 1.0f);
57        Sk_gluTessCallback(fTess, GLU_TESS_BEGIN_DATA, (TESSCB) &beginCB);
58        Sk_gluTessCallback(fTess, GLU_TESS_VERTEX_DATA, (TESSCB) &vertexCB);
59        Sk_gluTessCallback(fTess, GLU_TESS_END_DATA, (TESSCB) &endCB);
60        Sk_gluTessCallback(fTess, GLU_TESS_EDGE_FLAG_DATA, (TESSCB) &edgeFlagCB);
61        Sk_gluTessCallback(fTess, GLU_TESS_COMBINE_DATA, (TESSCB) &combineCB);
62        fInVertices = new double[count * 3];
63    }
64    virtual ~GrTess() {
65        Sk_gluDeleteTess(fTess);
66        delete[] fInVertices;
67    }
68    void addVertex(const GrPoint& pt, int index) {
69        if (index > USHRT_MAX) return;
70        double* inVertex = &fInVertices[index * 3];
71        inVertex[0] = pt.fX;
72        inVertex[1] = pt.fY;
73        inVertex[2] = 0.0;
74        *fVertices.append() = pt;
75        Sk_gluTessVertex(fTess, inVertex, reinterpret_cast<void*>(index));
76    }
77    void addVertices(const GrPoint* points, const uint16_t* contours, int numContours) {
78        Sk_gluTessBeginPolygon(fTess, this);
79        size_t i = 0;
80        for (int j = 0; j < numContours; ++j) {
81            Sk_gluTessBeginContour(fTess);
82            size_t end = i + contours[j];
83            for (; i < end; ++i) {
84                addVertex(points[i], i);
85            }
86            Sk_gluTessEndContour(fTess);
87        }
88        Sk_gluTessEndPolygon(fTess);
89    }
90    GLUtesselator* tess() { return fTess; }
91    const GrPointArray& vertices() const { return fVertices; }
92protected:
93    virtual void begin(GLenum type) = 0;
94    virtual void vertex(int index) = 0;
95    virtual void edgeFlag(bool flag) = 0;
96    virtual void end() = 0;
97    virtual int combine(GLdouble coords[3], int vertexIndices[4],
98                         GLfloat weight[4]) = 0;
99    static void beginCB(GLenum type, void* data) {
100        static_cast<GrTess*>(data)->begin(type);
101    }
102    static void vertexCB(void* vertexData, void* data) {
103        static_cast<GrTess*>(data)->vertex(reinterpret_cast<long>(vertexData));
104    }
105    static void edgeFlagCB(GLboolean flag, void* data) {
106        static_cast<GrTess*>(data)->edgeFlag(flag != 0);
107    }
108    static void endCB(void* data) {
109        static_cast<GrTess*>(data)->end();
110    }
111    static void combineCB(GLdouble coords[3], void* vertexData[4],
112                          GLfloat weight[4], void **outData, void* data) {
113        int vertexIndex[4];
114        vertexIndex[0] = reinterpret_cast<long>(vertexData[0]);
115        vertexIndex[1] = reinterpret_cast<long>(vertexData[1]);
116        vertexIndex[2] = reinterpret_cast<long>(vertexData[2]);
117        vertexIndex[3] = reinterpret_cast<long>(vertexData[3]);
118        GrTess* tess = static_cast<GrTess*>(data);
119        int outIndex = tess->combine(coords, vertexIndex, weight);
120        *reinterpret_cast<long*>(outData) = outIndex;
121    }
122protected:
123    GLUtesselator* fTess;
124    GrPointArray fVertices;
125    double* fInVertices;
126};
127
128class GrPolygonTess : public GrTess {
129public:
130    GrPolygonTess(int count, unsigned winding_rule)
131      : GrTess(count, winding_rule) {
132    }
133    ~GrPolygonTess() {
134    }
135    const GrIndexArray& indices() const { return fIndices; }
136protected:
137    virtual void begin(GLenum type) {
138        GR_DEBUGASSERT(type == GL_TRIANGLES);
139    }
140    virtual void vertex(int index) {
141        *fIndices.append() = index;
142    }
143    virtual void edgeFlag(bool flag) {}
144    virtual void end() {}
145    virtual int combine(GLdouble coords[3], int vertexIndices[4],
146                         GLfloat weight[4]) {
147        int index = fVertices.count();
148        GrPoint p = GrPoint::Make(static_cast<float>(coords[0]),
149                                  static_cast<float>(coords[1]));
150        *fVertices.append() = p;
151        return index;
152    }
153protected:
154    GrIndexArray fIndices;
155};
156
157class GrEdgePolygonTess : public GrPolygonTess {
158public:
159    GrEdgePolygonTess(int count, unsigned winding_rule, const SkMatrix& matrix)
160      : GrPolygonTess(count, winding_rule),
161        fMatrix(matrix),
162        fEdgeFlag(false),
163        fEdgeVertex(-1),
164        fTriStartVertex(-1),
165        fEdges(NULL) {
166    }
167    ~GrEdgePolygonTess() {
168        delete[] fEdges;
169    }
170    const GrDrawState::Edge* edges() const { return fEdges; }
171private:
172    void addEdge(int index0, int index1) {
173        GrPoint p = fVertices[index0];
174        GrPoint q = fVertices[index1];
175        fMatrix.mapPoints(&p, 1);
176        fMatrix.mapPoints(&q, 1);
177        p = sanitizePoint(p);
178        q = sanitizePoint(q);
179        if (p == q) return;
180        GrDrawState::Edge edge = computeEdge(p, q, 1.0f);
181        fEdges[index0 * 2 + 1] = edge;
182        fEdges[index1 * 2] = edge;
183    }
184    virtual void begin(GLenum type) {
185        GR_DEBUGASSERT(type == GL_TRIANGLES);
186        int count = fVertices.count() * 2;
187        fEdges = new GrDrawState::Edge[count];
188        memset(fEdges, 0, count * sizeof(GrDrawState::Edge));
189    }
190    virtual void edgeFlag(bool flag) {
191        fEdgeFlag = flag;
192    }
193    virtual void vertex(int index) {
194        bool triStart = fIndices.count() % 3 == 0;
195        GrPolygonTess::vertex(index);
196        if (fEdgeVertex != -1) {
197            if (triStart) {
198                addEdge(fEdgeVertex, fTriStartVertex);
199            } else {
200                addEdge(fEdgeVertex, index);
201            }
202        }
203        if (triStart) {
204            fTriStartVertex = index;
205        }
206        if (fEdgeFlag) {
207            fEdgeVertex = index;
208        } else {
209            fEdgeVertex = -1;
210        }
211    }
212    virtual void end() {
213        if (fEdgeVertex != -1) {
214            addEdge(fEdgeVertex, fTriStartVertex);
215        }
216    }
217    GrMatrix fMatrix;
218    bool fEdgeFlag;
219    int fEdgeVertex, fTriStartVertex;
220    GrDrawState::Edge* fEdges;
221};
222
223class GrBoundaryTess : public GrTess {
224public:
225    GrBoundaryTess(int count, unsigned winding_rule)
226      : GrTess(count, winding_rule),
227        fContourStart(0) {
228        Sk_gluTessProperty(fTess, GLU_TESS_BOUNDARY_ONLY, 1);
229    }
230    ~GrBoundaryTess() {
231    }
232    GrPointArray& contourPoints() { return fContourPoints; }
233    const GrIndexArray& contours() const { return fContours; }
234private:
235    virtual void begin(GLenum type) {
236        fContourStart = fContourPoints.count();
237    }
238    virtual void vertex(int index) {
239        *fContourPoints.append() = fVertices.at(index);
240    }
241    virtual void edgeFlag(bool flag) {}
242    virtual void end() {
243        *fContours.append() = fContourPoints.count() - fContourStart;
244    }
245    virtual int combine(GLdouble coords[3], int vertexIndices[4],
246                        GLfloat weight[4]) {
247        int index = fVertices.count();
248        *fVertices.append() = GrPoint::Make(static_cast<float>(coords[0]),
249                                            static_cast<float>(coords[1]));
250        return index;
251    }
252    GrPointArray fContourPoints;
253    GrIndexArray fContours;
254    size_t fContourStart;
255};
256
257static bool nearlyEqual(float a, float b) {
258    return fabsf(a - b) < 0.0001f;
259}
260
261static bool nearlyEqual(const GrPoint& a, const GrPoint& b) {
262    return nearlyEqual(a.fX, b.fX) && nearlyEqual(a.fY, b.fY);
263}
264
265static bool parallel(const GrDrawState::Edge& a, const GrDrawState::Edge& b) {
266    return (nearlyEqual(a.fX, b.fX) && nearlyEqual(a.fY, b.fY)) ||
267           (nearlyEqual(a.fX, -b.fX) && nearlyEqual(a.fY, -b.fY));
268}
269
270static unsigned fill_type_to_glu_winding_rule(GrPathFill fill) {
271    switch (fill) {
272        case kWinding_PathFill:
273            return GLU_TESS_WINDING_NONZERO;
274        case kEvenOdd_PathFill:
275            return GLU_TESS_WINDING_ODD;
276        case kInverseWinding_PathFill:
277            return GLU_TESS_WINDING_POSITIVE;
278        case kInverseEvenOdd_PathFill:
279            return GLU_TESS_WINDING_ODD;
280        case kHairLine_PathFill:
281            return GLU_TESS_WINDING_NONZERO;  // FIXME:  handle this
282        default:
283            GrAssert(!"Unknown path fill!");
284            return 0;
285    }
286}
287
288GrTesselatedPathRenderer::GrTesselatedPathRenderer() {
289}
290
291static bool isCCW(const GrPoint* pts, int count) {
292    GrVec v1, v2;
293    do {
294        v1 = pts[1] - pts[0];
295        v2 = pts[2] - pts[1];
296        pts++;
297        count--;
298    } while (nearlyEqual(v1, v2) && count > 3);
299    return v1.cross(v2) < 0;
300}
301
302static bool validEdge(const GrDrawState::Edge& edge) {
303    return !(edge.fX == 0.0f && edge.fY == 0.0f && edge.fZ == 0.0f);
304}
305
306static size_t computeEdgesAndIntersect(const GrMatrix& matrix,
307                                       const GrMatrix& inverse,
308                                       GrPoint* vertices,
309                                       size_t numVertices,
310                                       GrEdgeArray* edges,
311                                       float sign) {
312    if (numVertices < 3) {
313        return 0;
314    }
315    matrix.mapPoints(vertices, numVertices);
316    if (sign == 0.0f) {
317        sign = isCCW(vertices, numVertices) ? -1.0f : 1.0f;
318    }
319    GrPoint p = sanitizePoint(vertices[numVertices - 1]);
320    for (size_t i = 0; i < numVertices; ++i) {
321        GrPoint q = sanitizePoint(vertices[i]);
322        if (p == q) {
323            continue;
324        }
325        GrDrawState::Edge edge = computeEdge(p, q, sign);
326        edge.fZ += 0.5f;    // Offset by half a pixel along the tangent.
327        *edges->append() = edge;
328        p = q;
329    }
330    int count = edges->count();
331    if (count == 0) {
332        return 0;
333    }
334    GrDrawState::Edge prev_edge = edges->at(0);
335    for (int i = 0; i < count; ++i) {
336        GrDrawState::Edge edge = edges->at(i < count - 1 ? i + 1 : 0);
337        if (parallel(edge, prev_edge)) {
338            // 3 points are collinear; offset by half the tangent instead
339            vertices[i].fX -= edge.fX * 0.5f;
340            vertices[i].fY -= edge.fY * 0.5f;
341        } else {
342            vertices[i] = prev_edge.intersect(edge);
343        }
344        inverse.mapPoints(&vertices[i], 1);
345        prev_edge = edge;
346    }
347    return edges->count();
348}
349
350bool GrTesselatedPathRenderer::onDrawPath(const SkPath& path,
351                                          GrPathFill fill,
352                                          const GrVec* translate,
353                                          GrDrawTarget* target,
354                                          GrDrawState::StageMask stageMask,
355                                          bool antiAlias) {
356
357    GrDrawTarget::AutoStateRestore asr(target);
358    GrDrawState* drawState = target->drawState();
359    // face culling doesn't make sense here
360    GrAssert(GrDrawState::kBoth_DrawFace == drawState->getDrawFace());
361
362    GrMatrix viewM = drawState->getViewMatrix();
363
364    GrScalar tol = GR_Scalar1;
365    tol = GrPathUtils::scaleToleranceToSrc(tol, viewM, path.getBounds());
366    GrScalar tolSqd = GrMul(tol, tol);
367
368    int subpathCnt;
369    int maxPts = GrPathUtils::worstCasePointCount(path, &subpathCnt, tol);
370
371    GrVertexLayout layout = 0;
372    for (int s = 0; s < GrDrawState::kNumStages; ++s) {
373        if ((1 << s) & stageMask) {
374            layout |= GrDrawTarget::StagePosAsTexCoordVertexLayoutBit(s);
375        }
376    }
377
378    bool inverted = GrIsFillInverted(fill);
379    if (inverted) {
380        maxPts += 4;
381        subpathCnt++;
382    }
383    if (maxPts > USHRT_MAX) {
384        return false;
385    }
386    SkAutoSTMalloc<8, GrPoint> baseMem(maxPts);
387    GrPoint* base = baseMem;
388    GrPoint* vert = base;
389    GrPoint* subpathBase = base;
390
391    SkAutoSTMalloc<8, uint16_t> subpathVertCount(subpathCnt);
392
393    GrPoint pts[4];
394    SkPath::Iter iter(path, false);
395
396    bool first = true;
397    int subpath = 0;
398
399    for (;;) {
400        switch (iter.next(pts)) {
401            case kMove_PathCmd:
402                if (!first) {
403                    subpathVertCount[subpath] = vert-subpathBase;
404                    subpathBase = vert;
405                    ++subpath;
406                }
407                *vert = pts[0];
408                vert++;
409                break;
410            case kLine_PathCmd:
411                *vert = pts[1];
412                vert++;
413                break;
414            case kQuadratic_PathCmd: {
415                GrPathUtils::generateQuadraticPoints(pts[0], pts[1], pts[2],
416                                                     tolSqd, &vert,
417                                                     GrPathUtils::quadraticPointCount(pts, tol));
418                break;
419            }
420            case kCubic_PathCmd: {
421                GrPathUtils::generateCubicPoints(pts[0], pts[1], pts[2], pts[3],
422                                                 tolSqd, &vert,
423                                                 GrPathUtils::cubicPointCount(pts, tol));
424                break;
425            }
426            case kClose_PathCmd:
427                break;
428            case kEnd_PathCmd:
429                subpathVertCount[subpath] = vert-subpathBase;
430                ++subpath; // this could be only in debug
431                goto FINISHED;
432        }
433        first = false;
434    }
435FINISHED:
436    if (NULL != translate && 0 != translate->fX && 0 != translate->fY) {
437        for (int i = 0; i < vert - base; i++) {
438            base[i].offset(translate->fX, translate->fY);
439        }
440    }
441
442    if (inverted) {
443        GrRect bounds;
444        GrAssert(NULL != drawState->getRenderTarget());
445        bounds.setLTRB(0, 0,
446                       GrIntToScalar(drawState->getRenderTarget()->width()),
447                       GrIntToScalar(drawState->getRenderTarget()->height()));
448        GrMatrix vmi;
449        if (drawState->getViewInverse(&vmi)) {
450            vmi.mapRect(&bounds);
451        }
452        *vert++ = GrPoint::Make(bounds.fLeft, bounds.fTop);
453        *vert++ = GrPoint::Make(bounds.fLeft, bounds.fBottom);
454        *vert++ = GrPoint::Make(bounds.fRight, bounds.fBottom);
455        *vert++ = GrPoint::Make(bounds.fRight, bounds.fTop);
456        subpathVertCount[subpath++] = 4;
457    }
458
459    GrAssert(subpath == subpathCnt);
460    GrAssert((vert - base) <= maxPts);
461
462    size_t count = vert - base;
463
464    if (count < 3) {
465        return true;
466    }
467
468    if (subpathCnt == 1 && !inverted && path.isConvex()) {
469        if (antiAlias) {
470            GrEdgeArray edges;
471            GrMatrix inverse, matrix = drawState->getViewMatrix();
472            drawState->getViewInverse(&inverse);
473
474            count = computeEdgesAndIntersect(matrix, inverse, base, count, &edges, 0.0f);
475            size_t maxEdges = target->getMaxEdges();
476            if (count == 0) {
477                return true;
478            }
479            if (count <= maxEdges) {
480                // All edges fit; upload all edges and draw all verts as a fan
481                target->setVertexSourceToArray(layout, base, count);
482                drawState->setEdgeAAData(&edges[0], count);
483                target->drawNonIndexed(kTriangleFan_PrimitiveType, 0, count);
484            } else {
485                // Upload "maxEdges" edges and verts at a time, and draw as
486                // separate fans
487                for (size_t i = 0; i < count - 2; i += maxEdges - 2) {
488                    edges[i] = edges[0];
489                    base[i] = base[0];
490                    int size = GR_CT_MIN(count - i, maxEdges);
491                    target->setVertexSourceToArray(layout, &base[i], size);
492                    drawState->setEdgeAAData(&edges[i], size);
493                    target->drawNonIndexed(kTriangleFan_PrimitiveType, 0, size);
494                }
495            }
496            drawState->setEdgeAAData(NULL, 0);
497        } else {
498            target->setVertexSourceToArray(layout, base, count);
499            target->drawNonIndexed(kTriangleFan_PrimitiveType, 0, count);
500        }
501        return true;
502    }
503
504    if (antiAlias) {
505        // Run the tesselator once to get the boundaries.
506        GrBoundaryTess btess(count, fill_type_to_glu_winding_rule(fill));
507        btess.addVertices(base, subpathVertCount, subpathCnt);
508
509        GrMatrix inverse, matrix = drawState->getViewMatrix();
510        if (!drawState->getViewInverse(&inverse)) {
511            return false;
512        }
513
514        if (btess.vertices().count() > USHRT_MAX) {
515            return false;
516        }
517
518        // Inflate the boundary, and run the tesselator again to generate
519        // interior polys.
520        const GrPointArray& contourPoints = btess.contourPoints();
521        const GrIndexArray& contours = btess.contours();
522        GrEdgePolygonTess ptess(contourPoints.count(), GLU_TESS_WINDING_NONZERO, matrix);
523
524        size_t i = 0;
525        Sk_gluTessBeginPolygon(ptess.tess(), &ptess);
526        for (int contour = 0; contour < contours.count(); ++contour) {
527            int count = contours[contour];
528            GrEdgeArray edges;
529            int newCount = computeEdgesAndIntersect(matrix, inverse, &btess.contourPoints()[i], count, &edges, 1.0f);
530            Sk_gluTessBeginContour(ptess.tess());
531            for (int j = 0; j < newCount; j++) {
532                ptess.addVertex(contourPoints[i + j], ptess.vertices().count());
533            }
534            i += count;
535            Sk_gluTessEndContour(ptess.tess());
536        }
537
538        Sk_gluTessEndPolygon(ptess.tess());
539
540        if (ptess.vertices().count() > USHRT_MAX) {
541            return false;
542        }
543
544        // Draw the resulting polys and upload their edge data.
545        drawState->enableState(GrDrawState::kEdgeAAConcave_StateBit);
546        const GrPointArray& vertices = ptess.vertices();
547        const GrIndexArray& indices = ptess.indices();
548        const GrDrawState::Edge* edges = ptess.edges();
549        GR_DEBUGASSERT(indices.count() % 3 == 0);
550        for (int i = 0; i < indices.count(); i += 3) {
551            GrPoint tri_verts[3];
552            int index0 = indices[i];
553            int index1 = indices[i + 1];
554            int index2 = indices[i + 2];
555            tri_verts[0] = vertices[index0];
556            tri_verts[1] = vertices[index1];
557            tri_verts[2] = vertices[index2];
558            GrDrawState::Edge tri_edges[6];
559            int t = 0;
560            const GrDrawState::Edge& edge0 = edges[index0 * 2];
561            const GrDrawState::Edge& edge1 = edges[index0 * 2 + 1];
562            const GrDrawState::Edge& edge2 = edges[index1 * 2];
563            const GrDrawState::Edge& edge3 = edges[index1 * 2 + 1];
564            const GrDrawState::Edge& edge4 = edges[index2 * 2];
565            const GrDrawState::Edge& edge5 = edges[index2 * 2 + 1];
566            if (validEdge(edge0) && validEdge(edge1)) {
567                tri_edges[t++] = edge0;
568                tri_edges[t++] = edge1;
569            }
570            if (validEdge(edge2) && validEdge(edge3)) {
571                tri_edges[t++] = edge2;
572                tri_edges[t++] = edge3;
573            }
574            if (validEdge(edge4) && validEdge(edge5)) {
575                tri_edges[t++] = edge4;
576                tri_edges[t++] = edge5;
577            }
578            drawState->setEdgeAAData(&tri_edges[0], t);
579            target->setVertexSourceToArray(layout, &tri_verts[0], 3);
580            target->drawNonIndexed(kTriangles_PrimitiveType, 0, 3);
581        }
582        drawState->setEdgeAAData(NULL, 0);
583        drawState->disableState(GrDrawState::kEdgeAAConcave_StateBit);
584        return true;
585    }
586
587    GrPolygonTess ptess(count, fill_type_to_glu_winding_rule(fill));
588    ptess.addVertices(base, subpathVertCount, subpathCnt);
589    const GrPointArray& vertices = ptess.vertices();
590    const GrIndexArray& indices = ptess.indices();
591    if (indices.count() > 0) {
592        target->setVertexSourceToArray(layout, vertices.begin(), vertices.count());
593        target->setIndexSourceToArray(indices.begin(), indices.count());
594        target->drawIndexed(kTriangles_PrimitiveType,
595                            0,
596                            0,
597                            vertices.count(),
598                            indices.count());
599    }
600    return true;
601}
602
603bool GrTesselatedPathRenderer::canDrawPath(const SkPath& path,
604                                           GrPathFill fill,
605                                           const GrDrawTarget* target,
606                                           bool antiAlias) const {
607    return kHairLine_PathFill != fill;
608}
609
610