1ec3ed6a5ebf6f2c406d7bcf94b6bc34fcaeb976eepoger@google.com/* 2ec3ed6a5ebf6f2c406d7bcf94b6bc34fcaeb976eepoger@google.com * Copyright 2011 Google Inc. 3ec3ed6a5ebf6f2c406d7bcf94b6bc34fcaeb976eepoger@google.com * 4ec3ed6a5ebf6f2c406d7bcf94b6bc34fcaeb976eepoger@google.com * Use of this source code is governed by a BSD-style license that can be 5ec3ed6a5ebf6f2c406d7bcf94b6bc34fcaeb976eepoger@google.com * found in the LICENSE file. 69d18b7873ce9b44f130a41e0cbd0a3df76ab9adfsenorblanco@chromium.org */ 79d18b7873ce9b44f130a41e0cbd0a3df76ab9adfsenorblanco@chromium.org 89d18b7873ce9b44f130a41e0cbd0a3df76ab9adfsenorblanco@chromium.org#ifndef GrPathUtils_DEFINED 99d18b7873ce9b44f130a41e0cbd0a3df76ab9adfsenorblanco@chromium.org#define GrPathUtils_DEFINED 109d18b7873ce9b44f130a41e0cbd0a3df76ab9adfsenorblanco@chromium.org 11fd03d4a829efe2d77a712fd991927c55f59a2ffecommit-bot@chromium.org#include "SkRect.h" 128d033a1b125886c62906d975b5cc28a382064526bsalomon@google.com#include "SkPath.h" 1369cc6ad20ed03f35f9d3c8119a2c32187669a22bbsalomon@google.com#include "SkTArray.h" 149d18b7873ce9b44f130a41e0cbd0a3df76ab9adfsenorblanco@chromium.org 15b9086a026844e4cfd08b219e49ce3f12294cba98bsalomon@google.comclass SkMatrix; 16b9086a026844e4cfd08b219e49ce3f12294cba98bsalomon@google.com 179d18b7873ce9b44f130a41e0cbd0a3df76ab9adfsenorblanco@chromium.org/** 189d18b7873ce9b44f130a41e0cbd0a3df76ab9adfsenorblanco@chromium.org * Utilities for evaluating paths. 199d18b7873ce9b44f130a41e0cbd0a3df76ab9adfsenorblanco@chromium.org */ 20181e9bd9484ece4132e0cc5cfcff602134e5489dbsalomon@google.comnamespace GrPathUtils { 2181712883419f76e25d2ffec38a9438284a45a48dbsalomon@google.com SkScalar scaleToleranceToSrc(SkScalar devTol, 22b9086a026844e4cfd08b219e49ce3f12294cba98bsalomon@google.com const SkMatrix& viewM, 23fd03d4a829efe2d77a712fd991927c55f59a2ffecommit-bot@chromium.org const SkRect& pathBounds); 24181e9bd9484ece4132e0cc5cfcff602134e5489dbsalomon@google.com 25c10a88825d119054a9f4e7b7af7a3f887e30ab6btomhudson@google.com /// Since we divide by tol if we're computing exact worst-case bounds, 26c10a88825d119054a9f4e7b7af7a3f887e30ab6btomhudson@google.com /// very small tolerances will be increased to gMinCurveTol. 278d033a1b125886c62906d975b5cc28a382064526bsalomon@google.com int worstCasePointCount(const SkPath&, 28181e9bd9484ece4132e0cc5cfcff602134e5489dbsalomon@google.com int* subpaths, 2981712883419f76e25d2ffec38a9438284a45a48dbsalomon@google.com SkScalar tol); 301971317bb43580330a9e7e9a1c09c5025fe84aacbsalomon@google.com 31c10a88825d119054a9f4e7b7af7a3f887e30ab6btomhudson@google.com /// Since we divide by tol if we're computing exact worst-case bounds, 32c10a88825d119054a9f4e7b7af7a3f887e30ab6btomhudson@google.com /// very small tolerances will be increased to gMinCurveTol. 33972f9cd7a063d0544f8c919fd12b9a3adbd12b24commit-bot@chromium.org uint32_t quadraticPointCount(const SkPoint points[], SkScalar tol); 341971317bb43580330a9e7e9a1c09c5025fe84aacbsalomon@google.com 35972f9cd7a063d0544f8c919fd12b9a3adbd12b24commit-bot@chromium.org uint32_t generateQuadraticPoints(const SkPoint& p0, 36972f9cd7a063d0544f8c919fd12b9a3adbd12b24commit-bot@chromium.org const SkPoint& p1, 37972f9cd7a063d0544f8c919fd12b9a3adbd12b24commit-bot@chromium.org const SkPoint& p2, 3881712883419f76e25d2ffec38a9438284a45a48dbsalomon@google.com SkScalar tolSqd, 39972f9cd7a063d0544f8c919fd12b9a3adbd12b24commit-bot@chromium.org SkPoint** points, 40181e9bd9484ece4132e0cc5cfcff602134e5489dbsalomon@google.com uint32_t pointsLeft); 411971317bb43580330a9e7e9a1c09c5025fe84aacbsalomon@google.com 42c10a88825d119054a9f4e7b7af7a3f887e30ab6btomhudson@google.com /// Since we divide by tol if we're computing exact worst-case bounds, 43c10a88825d119054a9f4e7b7af7a3f887e30ab6btomhudson@google.com /// very small tolerances will be increased to gMinCurveTol. 44972f9cd7a063d0544f8c919fd12b9a3adbd12b24commit-bot@chromium.org uint32_t cubicPointCount(const SkPoint points[], SkScalar tol); 451971317bb43580330a9e7e9a1c09c5025fe84aacbsalomon@google.com 46972f9cd7a063d0544f8c919fd12b9a3adbd12b24commit-bot@chromium.org uint32_t generateCubicPoints(const SkPoint& p0, 47972f9cd7a063d0544f8c919fd12b9a3adbd12b24commit-bot@chromium.org const SkPoint& p1, 48972f9cd7a063d0544f8c919fd12b9a3adbd12b24commit-bot@chromium.org const SkPoint& p2, 49972f9cd7a063d0544f8c919fd12b9a3adbd12b24commit-bot@chromium.org const SkPoint& p3, 5081712883419f76e25d2ffec38a9438284a45a48dbsalomon@google.com SkScalar tolSqd, 51972f9cd7a063d0544f8c919fd12b9a3adbd12b24commit-bot@chromium.org SkPoint** points, 52181e9bd9484ece4132e0cc5cfcff602134e5489dbsalomon@google.com uint32_t pointsLeft); 531971317bb43580330a9e7e9a1c09c5025fe84aacbsalomon@google.com 541971317bb43580330a9e7e9a1c09c5025fe84aacbsalomon@google.com // A 2x3 matrix that goes from the 2d space coordinates to UV space where 551971317bb43580330a9e7e9a1c09c5025fe84aacbsalomon@google.com // u^2-v = 0 specifies the quad. The matrix is determined by the control 561971317bb43580330a9e7e9a1c09c5025fe84aacbsalomon@google.com // points of the quadratic. 571971317bb43580330a9e7e9a1c09c5025fe84aacbsalomon@google.com class QuadUVMatrix { 581971317bb43580330a9e7e9a1c09c5025fe84aacbsalomon@google.com public: 591971317bb43580330a9e7e9a1c09c5025fe84aacbsalomon@google.com QuadUVMatrix() {}; 601971317bb43580330a9e7e9a1c09c5025fe84aacbsalomon@google.com // Initialize the matrix from the control pts 61972f9cd7a063d0544f8c919fd12b9a3adbd12b24commit-bot@chromium.org QuadUVMatrix(const SkPoint controlPts[3]) { this->set(controlPts); } 62972f9cd7a063d0544f8c919fd12b9a3adbd12b24commit-bot@chromium.org void set(const SkPoint controlPts[3]); 631971317bb43580330a9e7e9a1c09c5025fe84aacbsalomon@google.com 641971317bb43580330a9e7e9a1c09c5025fe84aacbsalomon@google.com /** 651971317bb43580330a9e7e9a1c09c5025fe84aacbsalomon@google.com * Applies the matrix to vertex positions to compute UV coords. This 661971317bb43580330a9e7e9a1c09c5025fe84aacbsalomon@google.com * has been templated so that the compiler can easliy unroll the loop 671971317bb43580330a9e7e9a1c09c5025fe84aacbsalomon@google.com * and reorder to avoid stalling for loads. The assumption is that a 681971317bb43580330a9e7e9a1c09c5025fe84aacbsalomon@google.com * path renderer will have a small fixed number of vertices that it 691971317bb43580330a9e7e9a1c09c5025fe84aacbsalomon@google.com * uploads for each quad. 701971317bb43580330a9e7e9a1c09c5025fe84aacbsalomon@google.com * 711971317bb43580330a9e7e9a1c09c5025fe84aacbsalomon@google.com * N is the number of vertices. 721971317bb43580330a9e7e9a1c09c5025fe84aacbsalomon@google.com * STRIDE is the size of each vertex. 731971317bb43580330a9e7e9a1c09c5025fe84aacbsalomon@google.com * UV_OFFSET is the offset of the UV values within each vertex. 741971317bb43580330a9e7e9a1c09c5025fe84aacbsalomon@google.com * vertices is a pointer to the first vertex. 751971317bb43580330a9e7e9a1c09c5025fe84aacbsalomon@google.com */ 761971317bb43580330a9e7e9a1c09c5025fe84aacbsalomon@google.com template <int N, size_t STRIDE, size_t UV_OFFSET> 771971317bb43580330a9e7e9a1c09c5025fe84aacbsalomon@google.com void apply(const void* vertices) { 781971317bb43580330a9e7e9a1c09c5025fe84aacbsalomon@google.com intptr_t xyPtr = reinterpret_cast<intptr_t>(vertices); 791971317bb43580330a9e7e9a1c09c5025fe84aacbsalomon@google.com intptr_t uvPtr = reinterpret_cast<intptr_t>(vertices) + UV_OFFSET; 801971317bb43580330a9e7e9a1c09c5025fe84aacbsalomon@google.com float sx = fM[0]; 811971317bb43580330a9e7e9a1c09c5025fe84aacbsalomon@google.com float kx = fM[1]; 821971317bb43580330a9e7e9a1c09c5025fe84aacbsalomon@google.com float tx = fM[2]; 831971317bb43580330a9e7e9a1c09c5025fe84aacbsalomon@google.com float ky = fM[3]; 841971317bb43580330a9e7e9a1c09c5025fe84aacbsalomon@google.com float sy = fM[4]; 851971317bb43580330a9e7e9a1c09c5025fe84aacbsalomon@google.com float ty = fM[5]; 861971317bb43580330a9e7e9a1c09c5025fe84aacbsalomon@google.com for (int i = 0; i < N; ++i) { 87972f9cd7a063d0544f8c919fd12b9a3adbd12b24commit-bot@chromium.org const SkPoint* xy = reinterpret_cast<const SkPoint*>(xyPtr); 88972f9cd7a063d0544f8c919fd12b9a3adbd12b24commit-bot@chromium.org SkPoint* uv = reinterpret_cast<SkPoint*>(uvPtr); 891971317bb43580330a9e7e9a1c09c5025fe84aacbsalomon@google.com uv->fX = sx * xy->fX + kx * xy->fY + tx; 901971317bb43580330a9e7e9a1c09c5025fe84aacbsalomon@google.com uv->fY = ky * xy->fX + sy * xy->fY + ty; 911971317bb43580330a9e7e9a1c09c5025fe84aacbsalomon@google.com xyPtr += STRIDE; 921971317bb43580330a9e7e9a1c09c5025fe84aacbsalomon@google.com uvPtr += STRIDE; 931971317bb43580330a9e7e9a1c09c5025fe84aacbsalomon@google.com } 941971317bb43580330a9e7e9a1c09c5025fe84aacbsalomon@google.com } 951971317bb43580330a9e7e9a1c09c5025fe84aacbsalomon@google.com private: 961971317bb43580330a9e7e9a1c09c5025fe84aacbsalomon@google.com float fM[6]; 971971317bb43580330a9e7e9a1c09c5025fe84aacbsalomon@google.com }; 981971317bb43580330a9e7e9a1c09c5025fe84aacbsalomon@google.com 99139484095f014ab08265c32337fddeeec6c0877dcommit-bot@chromium.org // Input is 3 control points and a weight for a bezier conic. Calculates the 100139484095f014ab08265c32337fddeeec6c0877dcommit-bot@chromium.org // three linear functionals (K,L,M) that represent the implicit equation of the 101139484095f014ab08265c32337fddeeec6c0877dcommit-bot@chromium.org // conic, K^2 - LM. 102139484095f014ab08265c32337fddeeec6c0877dcommit-bot@chromium.org // 103139484095f014ab08265c32337fddeeec6c0877dcommit-bot@chromium.org // Output: 104139484095f014ab08265c32337fddeeec6c0877dcommit-bot@chromium.org // K = (klm[0], klm[1], klm[2]) 105139484095f014ab08265c32337fddeeec6c0877dcommit-bot@chromium.org // L = (klm[3], klm[4], klm[5]) 106139484095f014ab08265c32337fddeeec6c0877dcommit-bot@chromium.org // M = (klm[6], klm[7], klm[8]) 107139484095f014ab08265c32337fddeeec6c0877dcommit-bot@chromium.org void getConicKLM(const SkPoint p[3], const SkScalar weight, SkScalar klm[9]); 108a51ab8416db9772a2eae3122f4f69801642daeb5bsalomon@google.com 10969cc6ad20ed03f35f9d3c8119a2c32187669a22bbsalomon@google.com // Converts a cubic into a sequence of quads. If working in device space 11069cc6ad20ed03f35f9d3c8119a2c32187669a22bbsalomon@google.com // use tolScale = 1, otherwise set based on stretchiness of the matrix. The 11169cc6ad20ed03f35f9d3c8119a2c32187669a22bbsalomon@google.com // result is sets of 3 points in quads (TODO: share endpoints in returned 11269cc6ad20ed03f35f9d3c8119a2c32187669a22bbsalomon@google.com // array) 113a51ab8416db9772a2eae3122f4f69801642daeb5bsalomon@google.com // When we approximate a cubic {a,b,c,d} with a quadratic we may have to 114a51ab8416db9772a2eae3122f4f69801642daeb5bsalomon@google.com // ensure that the new control point lies between the lines ab and cd. The 115a51ab8416db9772a2eae3122f4f69801642daeb5bsalomon@google.com // convex path renderer requires this. It starts with a path where all the 116a51ab8416db9772a2eae3122f4f69801642daeb5bsalomon@google.com // control points taken together form a convex polygon. It relies on this 117a51ab8416db9772a2eae3122f4f69801642daeb5bsalomon@google.com // property and the quadratic approximation of cubics step cannot alter it. 118a51ab8416db9772a2eae3122f4f69801642daeb5bsalomon@google.com // Setting constrainWithinTangents to true enforces this property. When this 119a51ab8416db9772a2eae3122f4f69801642daeb5bsalomon@google.com // is true the cubic must be simple and dir must specify the orientation of 120a51ab8416db9772a2eae3122f4f69801642daeb5bsalomon@google.com // the cubic. Otherwise, dir is ignored. 121972f9cd7a063d0544f8c919fd12b9a3adbd12b24commit-bot@chromium.org void convertCubicToQuads(const SkPoint p[4], 12269cc6ad20ed03f35f9d3c8119a2c32187669a22bbsalomon@google.com SkScalar tolScale, 123a51ab8416db9772a2eae3122f4f69801642daeb5bsalomon@google.com bool constrainWithinTangents, 124a51ab8416db9772a2eae3122f4f69801642daeb5bsalomon@google.com SkPath::Direction dir, 12569cc6ad20ed03f35f9d3c8119a2c32187669a22bbsalomon@google.com SkTArray<SkPoint, true>* quads); 126858638d8a5bef8f9940ccec2346a9bcc5f804979commit-bot@chromium.org 127858638d8a5bef8f9940ccec2346a9bcc5f804979commit-bot@chromium.org // Chops the cubic bezier passed in by src, at the double point (intersection point) 128858638d8a5bef8f9940ccec2346a9bcc5f804979commit-bot@chromium.org // if the curve is a cubic loop. If it is a loop, there will be two parametric values for 129858638d8a5bef8f9940ccec2346a9bcc5f804979commit-bot@chromium.org // the double point: ls and ms. We chop the cubic at these values if they are between 0 and 1. 130858638d8a5bef8f9940ccec2346a9bcc5f804979commit-bot@chromium.org // Return value: 131858638d8a5bef8f9940ccec2346a9bcc5f804979commit-bot@chromium.org // Value of 3: ls and ms are both between (0,1), and dst will contain the three cubics, 132858638d8a5bef8f9940ccec2346a9bcc5f804979commit-bot@chromium.org // dst[0..3], dst[3..6], and dst[6..9] if dst is not NULL 133858638d8a5bef8f9940ccec2346a9bcc5f804979commit-bot@chromium.org // Value of 2: Only one of ls and ms are between (0,1), and dst will contain the two cubics, 134858638d8a5bef8f9940ccec2346a9bcc5f804979commit-bot@chromium.org // dst[0..3] and dst[3..6] if dst is not NULL 135858638d8a5bef8f9940ccec2346a9bcc5f804979commit-bot@chromium.org // Value of 1: Neither ls or ms are between (0,1), and dst will contain the one original cubic, 136858638d8a5bef8f9940ccec2346a9bcc5f804979commit-bot@chromium.org // dst[0..3] if dst is not NULL 137858638d8a5bef8f9940ccec2346a9bcc5f804979commit-bot@chromium.org // 138858638d8a5bef8f9940ccec2346a9bcc5f804979commit-bot@chromium.org // Optional KLM Calculation: 139858638d8a5bef8f9940ccec2346a9bcc5f804979commit-bot@chromium.org // The function can also return the KLM linear functionals for the chopped cubic implicit form 140858638d8a5bef8f9940ccec2346a9bcc5f804979commit-bot@chromium.org // of K^3 - LM. 141858638d8a5bef8f9940ccec2346a9bcc5f804979commit-bot@chromium.org // It will calculate a single set of KLM values that can be shared by all sub cubics, except 142858638d8a5bef8f9940ccec2346a9bcc5f804979commit-bot@chromium.org // for the subsection that is "the loop" the K and L values need to be negated. 143858638d8a5bef8f9940ccec2346a9bcc5f804979commit-bot@chromium.org // Output: 144858638d8a5bef8f9940ccec2346a9bcc5f804979commit-bot@chromium.org // klm: Holds the values for the linear functionals as: 145858638d8a5bef8f9940ccec2346a9bcc5f804979commit-bot@chromium.org // K = (klm[0], klm[1], klm[2]) 146858638d8a5bef8f9940ccec2346a9bcc5f804979commit-bot@chromium.org // L = (klm[3], klm[4], klm[5]) 147858638d8a5bef8f9940ccec2346a9bcc5f804979commit-bot@chromium.org // M = (klm[6], klm[7], klm[8]) 148858638d8a5bef8f9940ccec2346a9bcc5f804979commit-bot@chromium.org // klm_rev: These values are flags for the corresponding sub cubic saying whether or not 149858638d8a5bef8f9940ccec2346a9bcc5f804979commit-bot@chromium.org // the K and L values need to be flipped. A value of -1.f means flip K and L and 150858638d8a5bef8f9940ccec2346a9bcc5f804979commit-bot@chromium.org // a value of 1.f means do nothing. 151858638d8a5bef8f9940ccec2346a9bcc5f804979commit-bot@chromium.org // *****DO NOT FLIP M, JUST K AND L***** 152858638d8a5bef8f9940ccec2346a9bcc5f804979commit-bot@chromium.org // 153858638d8a5bef8f9940ccec2346a9bcc5f804979commit-bot@chromium.org // Notice that the klm lines are calculated in the same space as the input control points. 154858638d8a5bef8f9940ccec2346a9bcc5f804979commit-bot@chromium.org // If you transform the points the lines will also need to be transformed. This can be done 155858638d8a5bef8f9940ccec2346a9bcc5f804979commit-bot@chromium.org // by mapping the lines with the inverse-transpose of the matrix used to map the points. 156858638d8a5bef8f9940ccec2346a9bcc5f804979commit-bot@chromium.org int chopCubicAtLoopIntersection(const SkPoint src[4], SkPoint dst[10] = NULL, 157858638d8a5bef8f9940ccec2346a9bcc5f804979commit-bot@chromium.org SkScalar klm[9] = NULL, SkScalar klm_rev[3] = NULL); 158858638d8a5bef8f9940ccec2346a9bcc5f804979commit-bot@chromium.org 159858638d8a5bef8f9940ccec2346a9bcc5f804979commit-bot@chromium.org // Input is p which holds the 4 control points of a non-rational cubic Bezier curve. 160858638d8a5bef8f9940ccec2346a9bcc5f804979commit-bot@chromium.org // Output is the coefficients of the three linear functionals K, L, & M which 161858638d8a5bef8f9940ccec2346a9bcc5f804979commit-bot@chromium.org // represent the implicit form of the cubic as f(x,y,w) = K^3 - LM. The w term 162858638d8a5bef8f9940ccec2346a9bcc5f804979commit-bot@chromium.org // will always be 1. The output is stored in the array klm, where the values are: 163858638d8a5bef8f9940ccec2346a9bcc5f804979commit-bot@chromium.org // K = (klm[0], klm[1], klm[2]) 164858638d8a5bef8f9940ccec2346a9bcc5f804979commit-bot@chromium.org // L = (klm[3], klm[4], klm[5]) 165858638d8a5bef8f9940ccec2346a9bcc5f804979commit-bot@chromium.org // M = (klm[6], klm[7], klm[8]) 166858638d8a5bef8f9940ccec2346a9bcc5f804979commit-bot@chromium.org // 167858638d8a5bef8f9940ccec2346a9bcc5f804979commit-bot@chromium.org // Notice that the klm lines are calculated in the same space as the input control points. 168858638d8a5bef8f9940ccec2346a9bcc5f804979commit-bot@chromium.org // If you transform the points the lines will also need to be transformed. This can be done 169858638d8a5bef8f9940ccec2346a9bcc5f804979commit-bot@chromium.org // by mapping the lines with the inverse-transpose of the matrix used to map the points. 170858638d8a5bef8f9940ccec2346a9bcc5f804979commit-bot@chromium.org void getCubicKLM(const SkPoint p[4], SkScalar klm[9]); 1719d18b7873ce9b44f130a41e0cbd0a3df76ab9adfsenorblanco@chromium.org}; 1729d18b7873ce9b44f130a41e0cbd0a3df76ab9adfsenorblanco@chromium.org#endif 173