GrAAConvexTessellator.h 9.9 KB

123456789101112131415161718192021222324252627282930313233343536373839404142434445464748495051525354555657585960616263646566676869707172737475767778798081828384858687888990919293949596979899100101102103104105106107108109110111112113114115116117118119120121122123124125126127128129130131132133134135136137138139140141142143144145146147148149150151152153154155156157158159160161162163164165166167168169170171172173174175176177178179180181182183184185186187188189190191192193194195196197198199200201202203204205206207208209210211212213214215216217218219220221222223224225226227228229230231232233234235236237238239240241242243244245246247248249250251252253254255256257258259260261262263264265266267268269270271272273274275276277278279280281282283284285286287288289290291292
  1. /*
  2. * Copyright 2015 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 GrAAConvexTessellator_DEFINED
  8. #define GrAAConvexTessellator_DEFINED
  9. #include "include/core/SkColor.h"
  10. #include "include/core/SkPaint.h"
  11. #include "include/core/SkScalar.h"
  12. #include "include/core/SkStrokeRec.h"
  13. #include "include/private/SkTDArray.h"
  14. #include "src/core/SkPointPriv.h"
  15. class SkCanvas;
  16. class SkMatrix;
  17. class SkPath;
  18. //#define GR_AA_CONVEX_TESSELLATOR_VIZ 1
  19. // device space distance which we inset / outset points in order to create the soft antialiased edge
  20. static const SkScalar kAntialiasingRadius = 0.5f;
  21. class GrAAConvexTessellator;
  22. // The AAConvexTessellator holds the global pool of points and the triangulation
  23. // that connects them. It also drives the tessellation process.
  24. // The outward facing normals of the original polygon are stored (in 'fNorms') to service
  25. // computeDepthFromEdge requests.
  26. class GrAAConvexTessellator {
  27. public:
  28. GrAAConvexTessellator(SkStrokeRec::Style style = SkStrokeRec::kFill_Style,
  29. SkScalar strokeWidth = -1.0f,
  30. SkPaint::Join join = SkPaint::Join::kBevel_Join,
  31. SkScalar miterLimit = 0.0f)
  32. : fSide(SkPointPriv::kOn_Side)
  33. , fStrokeWidth(strokeWidth)
  34. , fStyle(style)
  35. , fJoin(join)
  36. , fMiterLimit(miterLimit) {
  37. }
  38. SkPointPriv::Side side() const { return fSide; }
  39. bool tessellate(const SkMatrix& m, const SkPath& path);
  40. // The next five should only be called after tessellate to extract the result
  41. int numPts() const { return fPts.count(); }
  42. int numIndices() const { return fIndices.count(); }
  43. const SkPoint& lastPoint() const { return fPts.top(); }
  44. const SkPoint& point(int index) const { return fPts[index]; }
  45. int index(int index) const { return fIndices[index]; }
  46. SkScalar coverage(int index) const { return fCoverages[index]; }
  47. #if GR_AA_CONVEX_TESSELLATOR_VIZ
  48. void draw(SkCanvas* canvas) const;
  49. #endif
  50. // The tessellator can be reused for multiple paths by rewinding in between
  51. void rewind();
  52. private:
  53. // CandidateVerts holds the vertices for the next ring while they are
  54. // being generated. Its main function is to de-dup the points.
  55. class CandidateVerts {
  56. public:
  57. void setReserve(int numPts) { fPts.setReserve(numPts); }
  58. void rewind() { fPts.rewind(); }
  59. int numPts() const { return fPts.count(); }
  60. const SkPoint& lastPoint() const { return fPts.top().fPt; }
  61. const SkPoint& firstPoint() const { return fPts[0].fPt; }
  62. const SkPoint& point(int index) const { return fPts[index].fPt; }
  63. int originatingIdx(int index) const { return fPts[index].fOriginatingIdx; }
  64. int origEdge(int index) const { return fPts[index].fOrigEdgeId; }
  65. bool needsToBeNew(int index) const { return fPts[index].fNeedsToBeNew; }
  66. int addNewPt(const SkPoint& newPt, int originatingIdx, int origEdge, bool needsToBeNew) {
  67. struct PointData* pt = fPts.push();
  68. pt->fPt = newPt;
  69. pt->fOrigEdgeId = origEdge;
  70. pt->fOriginatingIdx = originatingIdx;
  71. pt->fNeedsToBeNew = needsToBeNew;
  72. return fPts.count() - 1;
  73. }
  74. int fuseWithPrior(int origEdgeId) {
  75. fPts.top().fOrigEdgeId = origEdgeId;
  76. fPts.top().fOriginatingIdx = -1;
  77. fPts.top().fNeedsToBeNew = true;
  78. return fPts.count() - 1;
  79. }
  80. int fuseWithNext() {
  81. fPts[0].fOriginatingIdx = -1;
  82. fPts[0].fNeedsToBeNew = true;
  83. return 0;
  84. }
  85. int fuseWithBoth() {
  86. if (fPts.count() > 1) {
  87. fPts.pop();
  88. }
  89. fPts[0].fOriginatingIdx = -1;
  90. fPts[0].fNeedsToBeNew = true;
  91. return 0;
  92. }
  93. private:
  94. struct PointData {
  95. SkPoint fPt;
  96. int fOriginatingIdx;
  97. int fOrigEdgeId;
  98. bool fNeedsToBeNew;
  99. };
  100. SkTDArray<struct PointData> fPts;
  101. };
  102. // The Ring holds a set of indices into the global pool that together define
  103. // a single polygon inset.
  104. class Ring {
  105. public:
  106. void setReserve(int numPts) { fPts.setReserve(numPts); }
  107. void rewind() { fPts.rewind(); }
  108. int numPts() const { return fPts.count(); }
  109. void addIdx(int index, int origEdgeId) {
  110. struct PointData* pt = fPts.push();
  111. pt->fIndex = index;
  112. pt->fOrigEdgeId = origEdgeId;
  113. }
  114. // Upgrade this ring so that it can behave like an originating ring
  115. void makeOriginalRing() {
  116. for (int i = 0; i < fPts.count(); ++i) {
  117. fPts[i].fOrigEdgeId = fPts[i].fIndex;
  118. }
  119. }
  120. // init should be called after all the indices have been added (via addIdx)
  121. void init(const GrAAConvexTessellator& tess);
  122. void init(const SkTDArray<SkVector>& norms, const SkTDArray<SkVector>& bisectors);
  123. const SkPoint& norm(int index) const { return fPts[index].fNorm; }
  124. const SkPoint& bisector(int index) const { return fPts[index].fBisector; }
  125. int index(int index) const { return fPts[index].fIndex; }
  126. int origEdgeID(int index) const { return fPts[index].fOrigEdgeId; }
  127. void setOrigEdgeId(int index, int id) { fPts[index].fOrigEdgeId = id; }
  128. #if GR_AA_CONVEX_TESSELLATOR_VIZ
  129. void draw(SkCanvas* canvas, const GrAAConvexTessellator& tess) const;
  130. #endif
  131. private:
  132. void computeNormals(const GrAAConvexTessellator& result);
  133. void computeBisectors(const GrAAConvexTessellator& tess);
  134. SkDEBUGCODE(bool isConvex(const GrAAConvexTessellator& tess) const;)
  135. struct PointData {
  136. SkPoint fNorm;
  137. SkPoint fBisector;
  138. int fIndex;
  139. int fOrigEdgeId;
  140. };
  141. SkTDArray<PointData> fPts;
  142. };
  143. // Represents whether a given point is within a curve. A point is inside a curve only if it is
  144. // an interior point within a quad, cubic, or conic, or if it is the endpoint of a quad, cubic,
  145. // or conic with another curve meeting it at (more or less) the same angle.
  146. enum CurveState {
  147. // point is a sharp vertex
  148. kSharp_CurveState,
  149. // endpoint of a curve with the other side's curvature not yet determined
  150. kIndeterminate_CurveState,
  151. // point is in the interior of a curve
  152. kCurve_CurveState
  153. };
  154. bool movable(int index) const { return fMovable[index]; }
  155. // Movable points are those that can be slid along their bisector.
  156. // Basically, a point is immovable if it is part of the original
  157. // polygon or it results from the fusing of two bisectors.
  158. int addPt(const SkPoint& pt, SkScalar depth, SkScalar coverage, bool movable, CurveState curve);
  159. void popLastPt();
  160. void popFirstPtShuffle();
  161. void updatePt(int index, const SkPoint& pt, SkScalar depth, SkScalar coverage);
  162. void addTri(int i0, int i1, int i2);
  163. void reservePts(int count) {
  164. fPts.setReserve(count);
  165. fCoverages.setReserve(count);
  166. fMovable.setReserve(count);
  167. }
  168. SkScalar computeDepthFromEdge(int edgeIdx, const SkPoint& p) const;
  169. bool computePtAlongBisector(int startIdx, const SkPoint& bisector,
  170. int edgeIdx, SkScalar desiredDepth,
  171. SkPoint* result) const;
  172. void lineTo(const SkPoint& p, CurveState curve);
  173. void lineTo(const SkMatrix& m, SkPoint p, CurveState curve);
  174. void quadTo(const SkPoint pts[3]);
  175. void quadTo(const SkMatrix& m, SkPoint pts[3]);
  176. void cubicTo(const SkMatrix& m, SkPoint pts[4]);
  177. void conicTo(const SkMatrix& m, SkPoint pts[3], SkScalar w);
  178. void terminate(const Ring& lastRing);
  179. // return false on failure/degenerate path
  180. bool extractFromPath(const SkMatrix& m, const SkPath& path);
  181. void computeBisectors();
  182. void computeNormals();
  183. void fanRing(const Ring& ring);
  184. Ring* getNextRing(Ring* lastRing);
  185. void createOuterRing(const Ring& previousRing, SkScalar outset, SkScalar coverage,
  186. Ring* nextRing);
  187. bool createInsetRings(Ring& previousRing, SkScalar initialDepth, SkScalar initialCoverage,
  188. SkScalar targetDepth, SkScalar targetCoverage, Ring** finalRing);
  189. bool createInsetRing(const Ring& lastRing, Ring* nextRing,
  190. SkScalar initialDepth, SkScalar initialCoverage, SkScalar targetDepth,
  191. SkScalar targetCoverage, bool forceNew);
  192. void validate() const;
  193. // fPts, fCoverages, fMovable & fCurveState should always have the same # of elements
  194. SkTDArray<SkPoint> fPts;
  195. SkTDArray<SkScalar> fCoverages;
  196. // movable points are those that can be slid further along their bisector
  197. SkTDArray<bool> fMovable;
  198. // Tracks whether a given point is interior to a curve. Such points are
  199. // assumed to have shallow curvature.
  200. SkTDArray<CurveState> fCurveState;
  201. // The outward facing normals for the original polygon
  202. SkTDArray<SkVector> fNorms;
  203. // The inward facing bisector at each point in the original polygon. Only
  204. // needed for exterior ring creation and then handed off to the initial ring.
  205. SkTDArray<SkVector> fBisectors;
  206. SkPointPriv::Side fSide; // winding of the original polygon
  207. // The triangulation of the points
  208. SkTDArray<int> fIndices;
  209. Ring fInitialRing;
  210. #if GR_AA_CONVEX_TESSELLATOR_VIZ
  211. // When visualizing save all the rings
  212. SkTDArray<Ring*> fRings;
  213. #else
  214. Ring fRings[2];
  215. #endif
  216. CandidateVerts fCandidateVerts;
  217. // the stroke width is only used for stroke or stroke-and-fill styles
  218. SkScalar fStrokeWidth;
  219. SkStrokeRec::Style fStyle;
  220. SkPaint::Join fJoin;
  221. SkScalar fMiterLimit;
  222. SkTDArray<SkPoint> fPointBuffer;
  223. };
  224. #endif