GrPathUtils.h 9.4 KB

123456789101112131415161718192021222324252627282930313233343536373839404142434445464748495051525354555657585960616263646566676869707172737475767778798081828384858687888990919293949596979899100101102103104105106107108109110111112113114115116117118119120121122123124125126127128129130131132133134135136137138139140141142143144145146147148149150151152153154155156157158159160161162163164165166167168169170171172173174175176177178179180181182183184185186187188189190191192193194195196197198199200201202203204205206207208209210211212213214215216217
  1. /*
  2. * Copyright 2011 Google Inc.
  3. *
  4. * Use of this source code is governed by a BSD-style license that can be
  5. * found in the LICENSE file.
  6. */
  7. #ifndef GrPathUtils_DEFINED
  8. #define GrPathUtils_DEFINED
  9. #include "include/core/SkRect.h"
  10. #include "include/private/SkTArray.h"
  11. #include "src/core/SkGeometry.h"
  12. #include "src/core/SkPathPriv.h"
  13. class SkMatrix;
  14. /**
  15. * Utilities for evaluating paths.
  16. */
  17. namespace GrPathUtils {
  18. // Very small tolerances will be increased to a minimum threshold value, to avoid division
  19. // problems in subsequent math.
  20. SkScalar scaleToleranceToSrc(SkScalar devTol,
  21. const SkMatrix& viewM,
  22. const SkRect& pathBounds);
  23. int worstCasePointCount(const SkPath&,
  24. int* subpaths,
  25. SkScalar tol);
  26. uint32_t quadraticPointCount(const SkPoint points[], SkScalar tol);
  27. uint32_t generateQuadraticPoints(const SkPoint& p0,
  28. const SkPoint& p1,
  29. const SkPoint& p2,
  30. SkScalar tolSqd,
  31. SkPoint** points,
  32. uint32_t pointsLeft);
  33. uint32_t cubicPointCount(const SkPoint points[], SkScalar tol);
  34. uint32_t generateCubicPoints(const SkPoint& p0,
  35. const SkPoint& p1,
  36. const SkPoint& p2,
  37. const SkPoint& p3,
  38. SkScalar tolSqd,
  39. SkPoint** points,
  40. uint32_t pointsLeft);
  41. // A 2x3 matrix that goes from the 2d space coordinates to UV space where
  42. // u^2-v = 0 specifies the quad. The matrix is determined by the control
  43. // points of the quadratic.
  44. class QuadUVMatrix {
  45. public:
  46. QuadUVMatrix() {}
  47. // Initialize the matrix from the control pts
  48. QuadUVMatrix(const SkPoint controlPts[3]) { this->set(controlPts); }
  49. void set(const SkPoint controlPts[3]);
  50. /**
  51. * Applies the matrix to vertex positions to compute UV coords.
  52. *
  53. * vertices is a pointer to the first vertex.
  54. * vertexCount is the number of vertices.
  55. * stride is the size of each vertex.
  56. * uvOffset is the offset of the UV values within each vertex.
  57. */
  58. void apply(void* vertices, int vertexCount, size_t stride, size_t uvOffset) const {
  59. intptr_t xyPtr = reinterpret_cast<intptr_t>(vertices);
  60. intptr_t uvPtr = reinterpret_cast<intptr_t>(vertices) + uvOffset;
  61. float sx = fM[0];
  62. float kx = fM[1];
  63. float tx = fM[2];
  64. float ky = fM[3];
  65. float sy = fM[4];
  66. float ty = fM[5];
  67. for (int i = 0; i < vertexCount; ++i) {
  68. const SkPoint* xy = reinterpret_cast<const SkPoint*>(xyPtr);
  69. SkPoint* uv = reinterpret_cast<SkPoint*>(uvPtr);
  70. uv->fX = sx * xy->fX + kx * xy->fY + tx;
  71. uv->fY = ky * xy->fX + sy * xy->fY + ty;
  72. xyPtr += stride;
  73. uvPtr += stride;
  74. }
  75. }
  76. private:
  77. float fM[6];
  78. };
  79. // Input is 3 control points and a weight for a bezier conic. Calculates the
  80. // three linear functionals (K,L,M) that represent the implicit equation of the
  81. // conic, k^2 - lm.
  82. //
  83. // Output: klm holds the linear functionals K,L,M as row vectors:
  84. //
  85. // | ..K.. | | x | | k |
  86. // | ..L.. | * | y | == | l |
  87. // | ..M.. | | 1 | | m |
  88. //
  89. void getConicKLM(const SkPoint p[3], const SkScalar weight, SkMatrix* klm);
  90. // Converts a cubic into a sequence of quads. If working in device space
  91. // use tolScale = 1, otherwise set based on stretchiness of the matrix. The
  92. // result is sets of 3 points in quads. This will preserve the starting and
  93. // ending tangent vectors (modulo FP precision).
  94. void convertCubicToQuads(const SkPoint p[4],
  95. SkScalar tolScale,
  96. SkTArray<SkPoint, true>* quads);
  97. // When we approximate a cubic {a,b,c,d} with a quadratic we may have to
  98. // ensure that the new control point lies between the lines ab and cd. The
  99. // convex path renderer requires this. It starts with a path where all the
  100. // control points taken together form a convex polygon. It relies on this
  101. // property and the quadratic approximation of cubics step cannot alter it.
  102. // This variation enforces this constraint. The cubic must be simple and dir
  103. // must specify the orientation of the contour containing the cubic.
  104. void convertCubicToQuadsConstrainToTangents(const SkPoint p[4],
  105. SkScalar tolScale,
  106. SkPathPriv::FirstDirection dir,
  107. SkTArray<SkPoint, true>* quads);
  108. enum class ExcludedTerm {
  109. kNonInvertible,
  110. kQuadraticTerm,
  111. kLinearTerm
  112. };
  113. // Computes the inverse-transpose of the cubic's power basis matrix, after removing a specific
  114. // row of coefficients.
  115. //
  116. // E.g. if the cubic is defined in power basis form as follows:
  117. //
  118. // | x3 y3 0 |
  119. // C(t,s) = [t^3 t^2*s t*s^2 s^3] * | x2 y2 0 |
  120. // | x1 y1 0 |
  121. // | x0 y0 1 |
  122. //
  123. // And the excluded term is "kQuadraticTerm", then the resulting inverse-transpose will be:
  124. //
  125. // | x3 y3 0 | -1 T
  126. // | x1 y1 0 |
  127. // | x0 y0 1 |
  128. //
  129. // (The term to exclude is chosen based on maximizing the resulting matrix determinant.)
  130. //
  131. // This can be used to find the KLM linear functionals:
  132. //
  133. // | ..K.. | | ..kcoeffs.. |
  134. // | ..L.. | = | ..lcoeffs.. | * inverse_transpose_power_basis_matrix
  135. // | ..M.. | | ..mcoeffs.. |
  136. //
  137. // NOTE: the same term that was excluded here must also be removed from the corresponding column
  138. // of the klmcoeffs matrix.
  139. //
  140. // Returns which row of coefficients was removed, or kNonInvertible if the cubic was degenerate.
  141. ExcludedTerm calcCubicInverseTransposePowerBasisMatrix(const SkPoint p[4], SkMatrix* out);
  142. // Computes the KLM linear functionals for the cubic implicit form. The "right" side of the
  143. // curve (when facing in the direction of increasing parameter values) will be the area that
  144. // satisfies:
  145. //
  146. // k^3 < l*m
  147. //
  148. // Output:
  149. //
  150. // klm: Holds the linear functionals K,L,M as row vectors:
  151. //
  152. // | ..K.. | | x | | k |
  153. // | ..L.. | * | y | == | l |
  154. // | ..M.. | | 1 | | m |
  155. //
  156. // NOTE: the KLM lines are calculated in the same space as the input control points. If you
  157. // transform the points the lines will also need to be transformed. This can be done by mapping
  158. // the lines with the inverse-transpose of the matrix used to map the points.
  159. //
  160. // t[],s[]: These are set to the two homogeneous parameter values at which points the lines L&M
  161. // intersect with K (See SkClassifyCubic).
  162. //
  163. // Returns the cubic's classification.
  164. SkCubicType getCubicKLM(const SkPoint src[4], SkMatrix* klm, double t[2], double s[2]);
  165. // Chops the cubic bezier passed in by src, at the double point (intersection point)
  166. // if the curve is a cubic loop. If it is a loop, there will be two parametric values for
  167. // the double point: t1 and t2. We chop the cubic at these values if they are between 0 and 1.
  168. // Return value:
  169. // Value of 3: t1 and t2 are both between (0,1), and dst will contain the three cubics,
  170. // dst[0..3], dst[3..6], and dst[6..9] if dst is not nullptr
  171. // Value of 2: Only one of t1 and t2 are between (0,1), and dst will contain the two cubics,
  172. // dst[0..3] and dst[3..6] if dst is not nullptr
  173. // Value of 1: Neither t1 nor t2 are between (0,1), and dst will contain the one original cubic,
  174. // src[0..3]
  175. //
  176. // Output:
  177. //
  178. // klm: Holds the linear functionals K,L,M as row vectors. (See getCubicKLM().)
  179. //
  180. // loopIndex: This value will tell the caller which of the chopped sections (if any) are the
  181. // actual loop. A value of -1 means there is no loop section. The caller can then use
  182. // this value to decide how/if they want to flip the orientation of this section.
  183. // The flip should be done by negating the k and l values as follows:
  184. //
  185. // KLM.postScale(-1, -1)
  186. int chopCubicAtLoopIntersection(const SkPoint src[4], SkPoint dst[10], SkMatrix* klm,
  187. int* loopIndex);
  188. // When tessellating curved paths into linear segments, this defines the maximum distance
  189. // in screen space which a segment may deviate from the mathmatically correct value.
  190. // Above this value, the segment will be subdivided.
  191. // This value was chosen to approximate the supersampling accuracy of the raster path (16
  192. // samples, or one quarter pixel).
  193. static const SkScalar kDefaultTolerance = SkDoubleToScalar(0.25);
  194. // We guarantee that no quad or cubic will ever produce more than this many points
  195. static const int kMaxPointsPerCurve = 1 << 10;
  196. };
  197. #endif