Added classes SkPatch and SkPatchMesh which help encapsulate and generalize this new primitive. The functionality and responsability of each class is better explained in the comments of the files.

Each patch defines a method genMesh that produces the geometry to draw. To do this they receive a SkPatchMesh object which they need to initialize in order to set up how the data is going to be formatted. Later they call function like setColor or pointAt to set the values at a specific index, the SkMeshPatch object handles the indices based on the format and makes it transparent to the client.

Added a slide to sample app to show how to set up this classes and how they interact.

BUG=skia:
R=jvanverth@google.com, egdaniel@google.com, bsalomon@google.com

Author: dandov@google.com

Review URL: https://codereview.chromium.org/405163003

5 files changed, 465 insertions, 0 deletions

diff --git a/gm/patch.cpp b/gm/patch.cpp
new file mode 100644
index 0000000000..eb99944c0b
--- /dev/null
+++ b/gm/patch.cpp
@@ -0,0 +1,114 @@
+
+/*
+ * Copyright 2014 Google Inc.
+ *
+ * Use of this source code is governed by a BSD-style license that can be
+ * found in the LICENSE file.
+ */
+
+// This test only works with the GPU backend.
+
+#include "gm.h"
+
+#if SK_SUPPORT_GPU
+
+#include "GrContext.h"
+#include "GrTest.h"
+
+#include "SkPatch.h"
+
+namespace skiagm {
+/**
+ * This GM draws a SkPatch.
+ */
+class SkPatchGM : public GM {
+public:
+    SkPatchGM() {
+        this->setBGColor(0xFFFFFFFF);
+    }
+
+protected:
+    virtual SkString onShortName() SK_OVERRIDE {
+        return SkString("patch_primitive");
+    }
+
+    virtual SkISize onISize() SK_OVERRIDE {
+        return SkISize::Make(800, 800);
+    }
+
+    virtual uint32_t onGetFlags() const SK_OVERRIDE {
+        return kGPUOnly_Flag;
+    }
+
+
+    virtual void onDraw(SkCanvas* canvas) SK_OVERRIDE {
+
+        SkPaint paint;
+        SkColor colors[4] = {
+            SK_ColorRED, SK_ColorGREEN, SK_ColorBLUE, SK_ColorCYAN
+        };
+        SkPoint points[] = {
+            {100,100},{130,50},{500,70}, {650,60},
+            {350,125},{490,555},{600,700},
+            {515,595},{140,550},{110,590},
+            {125,400},{70,150}
+            
+        };
+
+        SkPatch coons(points, colors);
+        
+        SkPatch::VertexData data;
+        coons.getVertexData(&data, 10);
+
+        canvas->drawVertices(SkCanvas::kTriangles_VertexMode,data.fVertexCount,
+            data.fPoints, data.fTexCoords, data.fColors, NULL, data.fIndices,
+            data.fIndexCount, paint);
+
+        //draw control points
+        SkPoint bottom[4];
+        coons.getBottomPoints(bottom);
+        SkPoint top[4];
+        coons.getTopPoints(top);
+        SkPoint left[4];
+        coons.getLeftPoints(left);
+        SkPoint right[4];
+        coons.getRightPoints(right);
+
+        SkPoint corners[4] = { bottom[0], bottom[3], top[0], top[3] };
+        canvas->drawPoints(SkCanvas::kLines_PointMode, 4, bottom, paint);
+        canvas->drawPoints(SkCanvas::kLines_PointMode, 2, bottom+1, paint);
+        canvas->drawPoints(SkCanvas::kLines_PointMode, 4, top, paint);
+        canvas->drawPoints(SkCanvas::kLines_PointMode, 4, left, paint);
+        canvas->drawPoints(SkCanvas::kLines_PointMode, 4, right, paint);
+
+        canvas->drawPoints(SkCanvas::kLines_PointMode, 2, top+1, paint);
+        canvas->drawPoints(SkCanvas::kLines_PointMode, 2, left+1, paint);
+        canvas->drawPoints(SkCanvas::kLines_PointMode, 2, right+1, paint);
+
+        paint.setStrokeWidth(10);
+
+        paint.setColor(SK_ColorRED);
+        canvas->drawPoints(SkCanvas::kPoints_PointMode, 4, corners, paint);
+
+        paint.setColor(SK_ColorBLUE);
+        canvas->drawPoints(SkCanvas::kPoints_PointMode, 2, bottom+1, paint);
+
+        paint.setColor(SK_ColorCYAN);
+        canvas->drawPoints(SkCanvas::kPoints_PointMode, 2, top+1, paint);
+
+        paint.setColor(SK_ColorYELLOW);
+        canvas->drawPoints(SkCanvas::kPoints_PointMode, 2, left+1, paint);
+
+        paint.setColor(SK_ColorGREEN);
+        canvas->drawPoints(SkCanvas::kPoints_PointMode, 2, right+1, paint);
+    }
+
+private:
+    typedef GM INHERITED;
+};
+
+DEF_GM( return SkNEW(SkPatchGM); )
+
+}
+
+#endif
diff --git a/gyp/core.gypi b/gyp/core.gypi
index f7853f91d5..da43a05ff1 100644
--- a/gyp/core.gypi
+++ b/gyp/core.gypi
@@ -122,6 +122,7 @@
         '<(skia_src_path)/core/SkPaintOptionsAndroid.cpp',
         '<(skia_src_path)/core/SkPaintPriv.cpp',
         '<(skia_src_path)/core/SkPaintPriv.h',
+        '<(skia_src_path)/core/SkPatch.cpp',
         '<(skia_src_path)/core/SkPath.cpp',
         '<(skia_src_path)/core/SkPathEffect.cpp',
         '<(skia_src_path)/core/SkPathHeap.cpp',
@@ -278,6 +279,7 @@
         '<(skia_include_path)/core/SkOSFile.h',
         '<(skia_include_path)/core/SkPackBits.h',
         '<(skia_include_path)/core/SkPaint.h',
+        '<(skia_include_path)/core/SkPatch.h',
         '<(skia_include_path)/core/SkPath.h',
         '<(skia_include_path)/core/SkPathEffect.h',
         '<(skia_include_path)/core/SkPathMeasure.h',
diff --git a/gyp/gmslides.gypi b/gyp/gmslides.gypi
index 1ee27fda8c..b9563511a4 100644
--- a/gyp/gmslides.gypi
+++ b/gyp/gmslides.gypi
@@ -122,6 +122,7 @@
     '../gm/offsetimagefilter.cpp',
     '../gm/optimizations.cpp',
     '../gm/ovals.cpp',
+    '../gm/patch.cpp',
     '../gm/patheffects.cpp',
     '../gm/pathfill.cpp',
     '../gm/pathinterior.cpp',
diff --git a/include/core/SkPatch.h b/include/core/SkPatch.h
new file mode 100644
index 0000000000..2354423aba
--- /dev/null
+++ b/include/core/SkPatch.h
@@ -0,0 +1,124 @@
+/*
+ * Copyright 2014 Google Inc.
+ *
+ * Use of this source code is governed by a BSD-style license that can be
+ * found in the LICENSE file.
+ */
+
+#ifndef SkPatch_DEFINED
+#define SkPatch_DEFINED
+
+#include "SkColor.h"
+#include "SkPreConfig.h"
+#include "SkPoint.h"
+
+/**
+ * Class that represents a coons patch.
+ */
+class SK_API SkPatch {
+
+public:
+    /**
+     * Structure that holds the vertex data related to the tessellation of a SkPatch. It is passed 
+     * as a parameter to the function getVertexData which sets the points, colors and texture 
+     * coordinates of the vertices and the indices for them to be drawn as triangles.
+     */
+    struct VertexData {
+        int fVertexCount, fIndexCount;
+        SkPoint* fPoints;
+        SkPoint* fTexCoords;
+        uint32_t* fColors;
+        uint16_t* fIndices;
+        
+        VertexData()
+        : fVertexCount(0)
+        , fIndexCount(0)
+        , fPoints(NULL)
+        , fTexCoords(NULL)
+        , fColors(NULL)
+        , fIndices(NULL) { }
+        
+        ~VertexData() {
+            SkDELETE_ARRAY(fPoints);
+            SkDELETE_ARRAY(fTexCoords);
+            SkDELETE_ARRAY(fColors);
+            SkDELETE_ARRAY(fIndices);
+        }
+    };
+    
+    enum CubicCtrlPts {
+        kTopP0_CubicCtrlPts = 0,
+        kTopP1_CubicCtrlPts = 1,
+        kTopP2_CubicCtrlPts = 2,
+        kTopP3_CubicCtrlPts = 3,
+        
+        kRightP0_CubicCtrlPts = 3,
+        kRightP1_CubicCtrlPts = 4,
+        kRightP2_CubicCtrlPts = 5,
+        kRightP3_CubicCtrlPts = 6,
+        
+        kBottomP0_CubicCtrlPts = 9,
+        kBottomP1_CubicCtrlPts = 8,
+        kBottomP2_CubicCtrlPts = 7,
+        kBottomP3_CubicCtrlPts = 6,
+        
+        kLeftP0_CubicCtrlPts = 0,
+        kLeftP1_CubicCtrlPts = 11,
+        kLeftP2_CubicCtrlPts = 10,
+        kLeftP3_CubicCtrlPts = 9,
+    };
+    
+    /**
+     * Points are in the following order:
+     *              (top curve)
+     *                0 1 2 3
+     * (left curve)  11     4   (right curve)
+     *               10     5
+     *                9 8 7 6
+     *              (bottom curve)
+     * Used pointer to an array to guarantee that this method receives an array of 4 SkColors
+     */
+    SkPatch(SkPoint points[12], SkColor colors[4]);
+
+    /**
+     * Function that evaluates the coons patch interpolation.
+     * data refers to the pointer of the PatchData struct in which the tessellation data is set.
+     * divisions defines the number of steps in which the SkPatch is going to be subdivided per
+     * axis.
+     */
+    bool getVertexData(SkPatch::VertexData* data, int divisions);
+
+    void getTopPoints(SkPoint points[4]) {
+        points[0] = fCtrlPoints[kTopP0_CubicCtrlPts];
+        points[1] = fCtrlPoints[kTopP1_CubicCtrlPts];
+        points[2] = fCtrlPoints[kTopP2_CubicCtrlPts];
+        points[3] = fCtrlPoints[kTopP3_CubicCtrlPts];
+    }
+    
+    void getBottomPoints(SkPoint points[4]) {
+        points[0] = fCtrlPoints[kBottomP0_CubicCtrlPts];
+        points[1] = fCtrlPoints[kBottomP1_CubicCtrlPts];
+        points[2] = fCtrlPoints[kBottomP2_CubicCtrlPts];
+        points[3] = fCtrlPoints[kBottomP3_CubicCtrlPts];
+    }
+
+    void getLeftPoints(SkPoint points[4]) {
+        points[0] = fCtrlPoints[kLeftP0_CubicCtrlPts];
+        points[1] = fCtrlPoints[kLeftP1_CubicCtrlPts];
+        points[2] = fCtrlPoints[kLeftP2_CubicCtrlPts];
+        points[3] = fCtrlPoints[kLeftP3_CubicCtrlPts];
+    }
+
+    void getRightPoints(SkPoint points[4]) {
+        points[0] = fCtrlPoints[kRightP0_CubicCtrlPts];
+        points[1] = fCtrlPoints[kRightP1_CubicCtrlPts];
+        points[2] = fCtrlPoints[kRightP2_CubicCtrlPts];
+        points[3] = fCtrlPoints[kRightP3_CubicCtrlPts];
+    }
+    
+private:
+    SkPoint fCtrlPoints[12];
+    SkPMColor fCornerColors[4];
+};
+
+#endif
diff --git a/src/core/SkPatch.cpp b/src/core/SkPatch.cpp
new file mode 100644
index 0000000000..acd6cb9b57
--- /dev/null
+++ b/src/core/SkPatch.cpp
@@ -0,0 +1,224 @@
+/*
+ * Copyright 2014 Google Inc.
+ *
+ * Use of this source code is governed by a BSD-style license that can be
+ * found in the LICENSE file.
+ */
+
+#include "SkPatch.h"
+
+#include "SkGeometry.h"
+#include "SkColorPriv.h"
+
+////////////////////////////////////////////////////////////////////////////////
+
+/**
+ * Evaluator to sample the values of a cubic bezier using forward differences.
+ * Forward differences is a method for evaluating a nth degree polynomial at a uniform step by only
+ * adding precalculated values.
+ * For a linear example we have the function f(t) = m*t+b, then the value of that function at t+h
+ * would be f(t+h) = m*(t+h)+b. If we want to know the uniform step that we must add to the first
+ * evaluation f(t) then we need to substract f(t+h) - f(t) = m*t + m*h + b - m*t + b = mh. After
+ * obtaining this value (mh) we could just add this constant step to our first sampled point
+ * to compute the next one.
+ *
+ * For the cubic case the first difference gives as a result a quadratic polynomial to which we can
+ * apply again forward differences and get linear function to which we can apply again forward
+ * differences to get a constant difference. This is why we keep an array of size 4, the 0th
+ * position keeps the sampled value while the next ones keep the quadratic, linear and constant
+ * difference values.
+ */
+
+class FwDCubicEvaluator {
+    
+public:
+    FwDCubicEvaluator() { }
+    
+    /**
+     * Receives the 4 control points of the cubic bezier.
+     */
+    FwDCubicEvaluator(SkPoint a, SkPoint b, SkPoint c, SkPoint d) {
+        fPoints[0] = a;
+        fPoints[1] = b;
+        fPoints[2] = c;
+        fPoints[3] = d;
+        
+        SkScalar cx[4], cy[4];
+        SkGetCubicCoeff(fPoints, cx, cy);
+        fCoefs[0].set(cx[0], cy[0]);
+        fCoefs[1].set(cx[1], cy[1]);
+        fCoefs[2].set(cx[2], cy[2]);
+        fCoefs[3].set(cx[3], cy[3]);
+        
+        this->restart(1);
+    }
+    
+    /**
+     * Restarts the forward differences evaluator to the first value of t = 0.
+     */
+    void restart(int divisions) {
+        fDivisions = divisions;
+        SkScalar h  = 1.f / fDivisions;
+        fCurrent    = 0;
+        fMax        = fDivisions + 1;
+        fFwDiff[0]  = fCoefs[3];
+        SkScalar h2 = h * h;
+        SkScalar h3 = h2 * h;
+        
+        fFwDiff[3].set(6.f * fCoefs[0].x() * h3, 6.f * fCoefs[0].y() * h3); //6ah^3
+        fFwDiff[2].set(fFwDiff[3].x() + 2.f * fCoefs[1].x() * h2, //6ah^3 + 2bh^2
+                       fFwDiff[3].y() + 2.f * fCoefs[1].y() * h2);
+        fFwDiff[1].set(fCoefs[0].x() * h3 + fCoefs[1].x() * h2 + fCoefs[2].x() * h,//ah^3 + bh^2 +ch
+                       fCoefs[0].y() * h3 + fCoefs[1].y() * h2 + fCoefs[2].y() * h);
+    }
+    
+    /**
+     * Check if the evaluator is still within the range of 0<=t<=1
+     */
+    bool done() const {
+        return fCurrent > fMax;
+    }
+    
+    /**
+     * Call next to obtain the SkPoint sampled and move to the next one.
+     */
+    SkPoint next() {
+        SkPoint point = fFwDiff[0];
+        fFwDiff[0]    += fFwDiff[1];
+        fFwDiff[1]    += fFwDiff[2];
+        fFwDiff[2]    += fFwDiff[3];
+        fCurrent++;
+        return point;
+    }
+    
+    const SkPoint* getCtrlPoints() const {
+        return fPoints;
+    }
+    
+private:
+    int fMax, fCurrent, fDivisions;
+    SkPoint fFwDiff[4], fCoefs[4], fPoints[4];
+};
+
+////////////////////////////////////////////////////////////////////////////////
+
+SkPatch::SkPatch(SkPoint points[12], SkColor colors[4]) {
+        
+    for (int i = 0; i<12; i++) {
+        fCtrlPoints[i] = points[i];
+    }
+    
+    fCornerColors[0] = SkPreMultiplyColor(colors[0]);
+    fCornerColors[1] = SkPreMultiplyColor(colors[1]);
+    fCornerColors[2] = SkPreMultiplyColor(colors[2]);
+    fCornerColors[3] = SkPreMultiplyColor(colors[3]);
+}
+
+uint8_t bilinear(SkScalar tx, SkScalar ty, SkScalar c00, SkScalar c10, SkScalar c01, SkScalar c11) {
+    SkScalar a = c00 * (1.f - tx) + c10 * tx;
+    SkScalar b = c01 * (1.f - tx) + c11 * tx;
+    return uint8_t(a * (1.f - ty) + b * ty);
+}
+
+bool SkPatch::getVertexData(SkPatch::VertexData* data, int divisions) {
+    
+    if (divisions < 1) {
+        return false;
+    }
+    
+    int divX = divisions, divY = divisions;
+    
+    data->fVertexCount = (divX + 1) * (divY + 1);
+    data->fIndexCount = divX * divY * 6;
+
+    data->fPoints = SkNEW_ARRAY(SkPoint, data->fVertexCount);
+    data->fColors = SkNEW_ARRAY(uint32_t, data->fVertexCount);
+    data->fTexCoords = SkNEW_ARRAY(SkPoint, data->fVertexCount);
+    data->fIndices = SkNEW_ARRAY(uint16_t, data->fIndexCount);
+    
+    FwDCubicEvaluator fBottom(fCtrlPoints[kBottomP0_CubicCtrlPts],
+                              fCtrlPoints[kBottomP1_CubicCtrlPts],
+                              fCtrlPoints[kBottomP2_CubicCtrlPts],
+                              fCtrlPoints[kBottomP3_CubicCtrlPts]),
+                        fTop(fCtrlPoints[kTopP0_CubicCtrlPts],
+                             fCtrlPoints[kTopP1_CubicCtrlPts],
+                             fCtrlPoints[kTopP2_CubicCtrlPts],
+                             fCtrlPoints[kTopP2_CubicCtrlPts]),
+                        fLeft(fCtrlPoints[kLeftP0_CubicCtrlPts],
+                              fCtrlPoints[kLeftP1_CubicCtrlPts],
+                              fCtrlPoints[kLeftP2_CubicCtrlPts],
+                              fCtrlPoints[kLeftP3_CubicCtrlPts]),
+                        fRight(fCtrlPoints[kRightP0_CubicCtrlPts],
+                               fCtrlPoints[kRightP1_CubicCtrlPts],
+                               fCtrlPoints[kRightP2_CubicCtrlPts],
+                               fCtrlPoints[kRightP3_CubicCtrlPts]);
+
+    fBottom.restart(divX);
+    fTop.restart(divX);
+
+    SkScalar u = 0.0f;
+    int stride = divY + 1;
+    for (int x = 0; x <= divX; x++) {
+        SkPoint bottom = fBottom.next(), top = fTop.next();
+        fLeft.restart(divY);
+        fRight.restart(divY);
+        SkScalar v = 0.f;
+        for (int y = 0; y <= divY; y++) {
+            int dataIndex = x * (divX + 1) + y;
+
+            SkPoint left = fLeft.next(), right = fRight.next();
+
+            SkPoint s0 = SkPoint::Make((1.0f - v) * top.x() + v * bottom.x(),
+                                       (1.0f - v) * top.y() + v * bottom.y());
+            SkPoint s1 = SkPoint::Make((1.0f - u) * left.x() + u * right.x(),
+                                       (1.0f - u) * left.y() + u * right.y());
+            SkPoint s2 = SkPoint::Make(
+                                       (1.0f - v) * ((1.0f - u) * fTop.getCtrlPoints()[0].x()
+                                        + u * fTop.getCtrlPoints()[3].x())
+                                        + v * ((1.0f - u) * fBottom.getCtrlPoints()[0].x()
+                                        + u * fBottom.getCtrlPoints()[3].x()),
+                                       (1.0f - v) * ((1.0f - u) * fTop.getCtrlPoints()[0].y()
+                                        + u * fTop.getCtrlPoints()[3].y())
+                                        + v * ((1.0f - u) * fBottom.getCtrlPoints()[0].y()
+                                        + u * fBottom.getCtrlPoints()[3].y()));
+            data->fPoints[dataIndex] = s0 + s1 - s2;
+
+            uint8_t a = bilinear(u, v, 
+                            SkScalar(SkColorGetA(fCornerColors[0])), 
+                            SkScalar(SkColorGetA(fCornerColors[1])), 
+                            SkScalar(SkColorGetA(fCornerColors[2])), 
+                            SkScalar(SkColorGetA(fCornerColors[3])));
+            uint8_t r = bilinear(u, v, 
+                            SkScalar(SkColorGetR(fCornerColors[0])), 
+                            SkScalar(SkColorGetR(fCornerColors[1])), 
+                            SkScalar(SkColorGetR(fCornerColors[2])), 
+                            SkScalar(SkColorGetR(fCornerColors[3])));
+            uint8_t g = bilinear(u, v, 
+                            SkScalar(SkColorGetG(fCornerColors[0])), 
+                            SkScalar(SkColorGetG(fCornerColors[1])), 
+                            SkScalar(SkColorGetG(fCornerColors[2])), 
+                            SkScalar(SkColorGetG(fCornerColors[3])));
+            uint8_t b = bilinear(u, v, 
+                            SkScalar(SkColorGetB(fCornerColors[0])), 
+                            SkScalar(SkColorGetB(fCornerColors[1])), 
+                            SkScalar(SkColorGetB(fCornerColors[2])), 
+                            SkScalar(SkColorGetB(fCornerColors[3])));
+            data->fColors[dataIndex] = SkPackARGB32(a,r,g,b);
+            
+            data->fTexCoords[dataIndex] = SkPoint::Make(u, v);
+
+            if(x < divX && y < divY) {
+                int i = 6 * (x * divY + y);
+                data->fIndices[i] = x * stride + y;
+                data->fIndices[i + 1] = x * stride + 1 + y;
+                data->fIndices[i + 2] = (x + 1) * stride + 1 + y;
+                data->fIndices[i + 3] = data->fIndices[i];
+                data->fIndices[i + 4] = data->fIndices[i + 2];
+                data->fIndices[i + 5] = (x + 1) * stride + y;
+            }
+            v += 1.f / divY;
+        }
+        u += 1.f / divX;
+    }
+    return true;
+}