ethannicholas | e9709e8 | 2016-01-07 13:34:16 -0800 | [diff] [blame] | 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 | |
Chris Dalton | 17dc418 | 2020-03-25 16:18:16 -0600 | [diff] [blame] | 8 | #ifndef GrTriangulator_DEFINED |
| 9 | #define GrTriangulator_DEFINED |
ethannicholas | e9709e8 | 2016-01-07 13:34:16 -0800 | [diff] [blame] | 10 | |
Chris Dalton | 57ea1fc | 2021-01-05 13:37:44 -0700 | [diff] [blame] | 11 | #include "include/core/SkPath.h" |
Mike Klein | c0bd9f9 | 2019-04-23 12:05:21 -0500 | [diff] [blame] | 12 | #include "include/core/SkPoint.h" |
Mike Klein | c0bd9f9 | 2019-04-23 12:05:21 -0500 | [diff] [blame] | 13 | #include "include/private/SkColorData.h" |
Chris Dalton | 57ea1fc | 2021-01-05 13:37:44 -0700 | [diff] [blame] | 14 | #include "src/core/SkArenaAlloc.h" |
Greg Daniel | f91aeb2 | 2019-06-18 09:58:02 -0400 | [diff] [blame] | 15 | #include "src/gpu/GrColor.h" |
senorblanco | 6599eff | 2016-03-10 08:38:45 -0800 | [diff] [blame] | 16 | |
Chris Dalton | d081dce | 2020-01-23 12:09:04 -0700 | [diff] [blame] | 17 | class GrEagerVertexAllocator; |
senorblanco | 6599eff | 2016-03-10 08:38:45 -0800 | [diff] [blame] | 18 | struct SkRect; |
ethannicholas | e9709e8 | 2016-01-07 13:34:16 -0800 | [diff] [blame] | 19 | |
Chris Dalton | 5045de3 | 2021-01-07 19:09:01 -0700 | [diff] [blame^] | 20 | #define TRIANGULATOR_LOGGING 0 |
Chris Dalton | 57ea1fc | 2021-01-05 13:37:44 -0700 | [diff] [blame] | 21 | #define TRIANGULATOR_WIREFRAME 0 |
| 22 | |
ethannicholas | e9709e8 | 2016-01-07 13:34:16 -0800 | [diff] [blame] | 23 | /** |
| 24 | * Provides utility functions for converting paths to a collection of triangles. |
| 25 | */ |
Chris Dalton | 57ea1fc | 2021-01-05 13:37:44 -0700 | [diff] [blame] | 26 | class GrTriangulator { |
| 27 | public: |
Chris Dalton | 854ee85 | 2021-01-05 15:12:59 -0700 | [diff] [blame] | 28 | static int PathToTriangles(const SkPath& path, SkScalar tolerance, const SkRect& clipBounds, |
| 29 | GrEagerVertexAllocator* vertexAllocator, bool* isLinear) { |
| 30 | GrTriangulator triangulator(path); |
| 31 | int count = triangulator.pathToTriangles(tolerance, clipBounds, vertexAllocator, |
| 32 | path.getFillType()); |
| 33 | *isLinear = triangulator.fIsLinear; |
| 34 | return count; |
Chris Dalton | 57ea1fc | 2021-01-05 13:37:44 -0700 | [diff] [blame] | 35 | } |
ethannicholas | e9709e8 | 2016-01-07 13:34:16 -0800 | [diff] [blame] | 36 | |
Chris Dalton | 854ee85 | 2021-01-05 15:12:59 -0700 | [diff] [blame] | 37 | static int PathToAATriangles(const SkPath& path, SkScalar tolerance, const SkRect& clipBounds, |
| 38 | GrEagerVertexAllocator* vertexAllocator, bool* isLinear) { |
| 39 | GrTriangulator triangulator(path); |
| 40 | triangulator.fRoundVerticesToQuarterPixel = true; |
| 41 | triangulator.fEmitCoverage = true; |
| 42 | int count = triangulator.pathToTriangles(tolerance, clipBounds, vertexAllocator, |
| 43 | SkPathFillType::kWinding); |
| 44 | *isLinear = triangulator.fIsLinear; |
| 45 | return count; |
| 46 | } |
| 47 | |
| 48 | static int TriangulateSimpleInnerPolygons(const SkPath& path, |
| 49 | GrEagerVertexAllocator* vertexAllocator, |
| 50 | bool *isLinear) { |
| 51 | GrTriangulator triangulator(path); |
| 52 | triangulator.fCullCollinearVertices = false; |
| 53 | triangulator.fSimpleInnerPolygons = true; |
| 54 | int count = triangulator.pathToTriangles(0, SkRect::MakeEmpty(), vertexAllocator, |
| 55 | path.getFillType()); |
| 56 | *isLinear = triangulator.fIsLinear; |
| 57 | return count; |
| 58 | } |
ethannicholas | e9709e8 | 2016-01-07 13:34:16 -0800 | [diff] [blame] | 59 | |
Chris Dalton | 57ea1fc | 2021-01-05 13:37:44 -0700 | [diff] [blame] | 60 | struct WindingVertex { |
| 61 | SkPoint fPos; |
| 62 | int fWinding; |
| 63 | }; |
Chris Dalton | 6ccc032 | 2020-01-29 11:38:16 -0700 | [diff] [blame] | 64 | |
Chris Dalton | 57ea1fc | 2021-01-05 13:37:44 -0700 | [diff] [blame] | 65 | // *DEPRECATED*: Once CCPR is removed this method will go away. |
Chris Dalton | 6ccc032 | 2020-01-29 11:38:16 -0700 | [diff] [blame] | 66 | // |
Chris Dalton | 57ea1fc | 2021-01-05 13:37:44 -0700 | [diff] [blame] | 67 | // Triangulates a path to an array of vertices. Each triangle is represented as a set of three |
| 68 | // WindingVertex entries, each of which contains the position and winding count (which is the |
| 69 | // same for all three vertices of a triangle). The 'verts' out parameter is set to point to the |
| 70 | // resultant vertex array. CALLER IS RESPONSIBLE for deleting this buffer to avoid a memory |
| 71 | // leak! |
| 72 | static int PathToVertices(const SkPath& path, SkScalar tolerance, const SkRect& clipBounds, |
| 73 | WindingVertex** verts); |
| 74 | |
Chris Dalton | 17ce8c5 | 2021-01-07 18:08:46 -0700 | [diff] [blame] | 75 | // Enums used by GrTriangulator internals. |
| 76 | typedef enum { kLeft_Side, kRight_Side } Side; |
| 77 | enum class EdgeType { kInner, kOuter, kConnector }; |
| 78 | |
Chris Dalton | 57ea1fc | 2021-01-05 13:37:44 -0700 | [diff] [blame] | 79 | // Structs used by GrTriangulator internals. |
| 80 | struct Vertex; |
| 81 | struct VertexList; |
Chris Dalton | 17ce8c5 | 2021-01-07 18:08:46 -0700 | [diff] [blame] | 82 | struct Line; |
Chris Dalton | 57ea1fc | 2021-01-05 13:37:44 -0700 | [diff] [blame] | 83 | struct Edge; |
| 84 | struct EdgeList; |
Chris Dalton | 17ce8c5 | 2021-01-07 18:08:46 -0700 | [diff] [blame] | 85 | struct MonotonePoly; |
Chris Dalton | 57ea1fc | 2021-01-05 13:37:44 -0700 | [diff] [blame] | 86 | struct Poly; |
| 87 | struct Comparator; |
| 88 | |
| 89 | private: |
Chris Dalton | 854ee85 | 2021-01-05 15:12:59 -0700 | [diff] [blame] | 90 | GrTriangulator(const SkPath& path) : fPath(path) {} |
Chris Dalton | 57ea1fc | 2021-01-05 13:37:44 -0700 | [diff] [blame] | 91 | |
| 92 | // There are six stages to the basic algorithm: |
| 93 | // |
| 94 | // 1) Linearize the path contours into piecewise linear segments: |
| 95 | void pathToContours(float tolerance, const SkRect& clipBounds, VertexList* contours); |
| 96 | |
| 97 | // 2) Build a mesh of edges connecting the vertices: |
Chris Dalton | 811dc6a | 2021-01-07 16:40:32 -0700 | [diff] [blame] | 98 | void contoursToMesh(VertexList* contours, int contourCnt, VertexList* mesh, const Comparator&); |
Chris Dalton | 57ea1fc | 2021-01-05 13:37:44 -0700 | [diff] [blame] | 99 | |
| 100 | // 3) Sort the vertices in Y (and secondarily in X) (merge_sort()). |
| 101 | static void SortMesh(VertexList* vertices, const Comparator&); |
| 102 | |
| 103 | // 4) Simplify the mesh by inserting new vertices at intersecting edges: |
| 104 | enum class SimplifyResult { |
| 105 | kAlreadySimple, |
| 106 | kFoundSelfIntersection, |
| 107 | kAbort |
| 108 | }; |
| 109 | |
Chris Dalton | 811dc6a | 2021-01-07 16:40:32 -0700 | [diff] [blame] | 110 | SimplifyResult simplify(VertexList* mesh, const Comparator&); |
Chris Dalton | 57ea1fc | 2021-01-05 13:37:44 -0700 | [diff] [blame] | 111 | |
| 112 | // 5) Tessellate the simplified mesh into monotone polygons: |
| 113 | Poly* tessellate(const VertexList& vertices); |
| 114 | |
| 115 | // 6) Triangulate the monotone polygons directly into a vertex buffer: |
| 116 | void* polysToTriangles(Poly* polys, void* data, SkPathFillType overrideFillType); |
| 117 | |
| 118 | // For screenspace antialiasing, the algorithm is modified as follows: |
| 119 | // |
| 120 | // Run steps 1-5 above to produce polygons. |
| 121 | // 5b) Apply fill rules to extract boundary contours from the polygons (extract_boundaries()). |
| 122 | // 5c) Simplify boundaries to remove "pointy" vertices that cause inversions |
| 123 | // (simplify_boundary()). |
| 124 | // 5d) Displace edges by half a pixel inward and outward along their normals. Intersect to find |
| 125 | // new vertices, and set zero alpha on the exterior and one alpha on the interior. Build a |
| 126 | // new antialiased mesh from those vertices (stroke_boundary()). |
| 127 | // Run steps 3-6 above on the new mesh, and produce antialiased triangles. |
| 128 | // |
| 129 | // The vertex sorting in step (3) is a merge sort, since it plays well with the linked list |
| 130 | // of vertices (and the necessity of inserting new vertices on intersection). |
| 131 | // |
| 132 | // Stages (4) and (5) use an active edge list -- a list of all edges for which the |
| 133 | // sweep line has crossed the top vertex, but not the bottom vertex. It's sorted |
| 134 | // left-to-right based on the point where both edges are active (when both top vertices |
| 135 | // have been seen, so the "lower" top vertex of the two). If the top vertices are equal |
| 136 | // (shared), it's sorted based on the last point where both edges are active, so the |
| 137 | // "upper" bottom vertex. |
| 138 | // |
| 139 | // The most complex step is the simplification (4). It's based on the Bentley-Ottman |
| 140 | // line-sweep algorithm, but due to floating point inaccuracy, the intersection points are |
| 141 | // not exact and may violate the mesh topology or active edge list ordering. We |
| 142 | // accommodate this by adjusting the topology of the mesh and AEL to match the intersection |
| 143 | // points. This occurs in two ways: |
| 144 | // |
| 145 | // A) Intersections may cause a shortened edge to no longer be ordered with respect to its |
| 146 | // neighbouring edges at the top or bottom vertex. This is handled by merging the |
| 147 | // edges (merge_collinear_edges()). |
| 148 | // B) Intersections may cause an edge to violate the left-to-right ordering of the |
| 149 | // active edge list. This is handled by detecting potential violations and rewinding |
| 150 | // the active edge list to the vertex before they occur (rewind() during merging, |
| 151 | // rewind_if_necessary() during splitting). |
| 152 | // |
| 153 | // The tessellation steps (5) and (6) are based on "Triangulating Simple Polygons and |
| 154 | // Equivalent Problems" (Fournier and Montuno); also a line-sweep algorithm. Note that it |
| 155 | // currently uses a linked list for the active edge list, rather than a 2-3 tree as the |
| 156 | // paper describes. The 2-3 tree gives O(lg N) lookups, but insertion and removal also |
| 157 | // become O(lg N). In all the test cases, it was found that the cost of frequent O(lg N) |
| 158 | // insertions and removals was greater than the cost of infrequent O(N) lookups with the |
| 159 | // linked list implementation. With the latter, all removals are O(1), and most insertions |
| 160 | // are O(1), since we know the adjacent edge in the active edge list based on the topology. |
| 161 | // Only type 2 vertices (see paper) require the O(N) lookups, and these are much less |
| 162 | // frequent. There may be other data structures worth investigating, however. |
| 163 | // |
| 164 | // Note that the orientation of the line sweep algorithms is determined by the aspect ratio of |
| 165 | // the path bounds. When the path is taller than it is wide, we sort vertices based on |
| 166 | // increasing Y coordinate, and secondarily by increasing X coordinate. When the path is wider |
| 167 | // than it is tall, we sort by increasing X coordinate, but secondarily by *decreasing* Y |
| 168 | // coordinate. This is so that the "left" and "right" orientation in the code remains correct |
| 169 | // (edges to the left are increasing in Y; edges to the right are decreasing in Y). That is, the |
| 170 | // setting rotates 90 degrees counterclockwise, rather that transposing. |
| 171 | |
| 172 | // Additional helpers and driver functions. |
| 173 | void appendPointToContour(const SkPoint& p, VertexList* contour); |
| 174 | void appendQuadraticToContour(const SkPoint[3], SkScalar toleranceSqd, VertexList* contour); |
| 175 | void generateCubicPoints(const SkPoint&, const SkPoint&, const SkPoint&, const SkPoint&, |
| 176 | SkScalar tolSqd, VertexList* contour, int pointsLeft); |
Chris Dalton | 811dc6a | 2021-01-07 16:40:32 -0700 | [diff] [blame] | 177 | bool splitEdge(Edge* edge, Vertex* v, EdgeList* activeEdges, Vertex** current, |
| 178 | const Comparator&); |
Chris Dalton | 57ea1fc | 2021-01-05 13:37:44 -0700 | [diff] [blame] | 179 | bool intersectEdgePair(Edge* left, Edge* right, EdgeList* activeEdges, Vertex** current, |
Chris Dalton | 811dc6a | 2021-01-07 16:40:32 -0700 | [diff] [blame] | 180 | const Comparator&); |
Chris Dalton | 57ea1fc | 2021-01-05 13:37:44 -0700 | [diff] [blame] | 181 | bool checkForIntersection(Edge* left, Edge* right, EdgeList* activeEdges, Vertex** current, |
Chris Dalton | 811dc6a | 2021-01-07 16:40:32 -0700 | [diff] [blame] | 182 | VertexList* mesh, const Comparator&); |
Chris Dalton | 57ea1fc | 2021-01-05 13:37:44 -0700 | [diff] [blame] | 183 | void sanitizeContours(VertexList* contours, int contourCnt); |
Chris Dalton | 811dc6a | 2021-01-07 16:40:32 -0700 | [diff] [blame] | 184 | bool mergeCoincidentVertices(VertexList* mesh, const Comparator&); |
| 185 | void buildEdges(VertexList* contours, int contourCnt, VertexList* mesh, const Comparator&); |
Chris Dalton | 57ea1fc | 2021-01-05 13:37:44 -0700 | [diff] [blame] | 186 | Poly* contoursToPolys(VertexList* contours, int contourCnt, VertexList* outerMesh); |
| 187 | Poly* pathToPolys(float tolerance, const SkRect& clipBounds, int contourCnt, |
| 188 | VertexList* outerMesh); |
| 189 | int pathToTriangles(float tolerance, const SkRect& clipBounds, GrEagerVertexAllocator*, |
| 190 | SkPathFillType overrideFillType); |
| 191 | |
| 192 | constexpr static int kArenaChunkSize = 16 * 1024; |
| 193 | SkArenaAlloc fAlloc{kArenaChunkSize}; |
| 194 | const SkPath fPath; |
Chris Dalton | 57ea1fc | 2021-01-05 13:37:44 -0700 | [diff] [blame] | 195 | bool fIsLinear = false; |
Chris Dalton | 854ee85 | 2021-01-05 15:12:59 -0700 | [diff] [blame] | 196 | |
| 197 | // Flags. |
| 198 | bool fRoundVerticesToQuarterPixel = false; |
| 199 | bool fEmitCoverage = false; |
| 200 | bool fCullCollinearVertices = true; |
| 201 | bool fSimpleInnerPolygons = false; |
Chris Dalton | dcc8c54 | 2020-01-28 17:55:56 -0700 | [diff] [blame] | 202 | }; |
| 203 | |
Chris Dalton | 5045de3 | 2021-01-07 19:09:01 -0700 | [diff] [blame^] | 204 | /** |
| 205 | * Vertices are used in three ways: first, the path contours are converted into a |
| 206 | * circularly-linked list of Vertices for each contour. After edge construction, the same Vertices |
| 207 | * are re-ordered by the merge sort according to the sweep_lt comparator (usually, increasing |
| 208 | * in Y) using the same fPrev/fNext pointers that were used for the contours, to avoid |
| 209 | * reallocation. Finally, MonotonePolys are built containing a circularly-linked list of |
| 210 | * Vertices. (Currently, those Vertices are newly-allocated for the MonotonePolys, since |
| 211 | * an individual Vertex from the path mesh may belong to multiple |
| 212 | * MonotonePolys, so the original Vertices cannot be re-used. |
| 213 | */ |
| 214 | |
| 215 | struct GrTriangulator::Vertex { |
| 216 | Vertex(const SkPoint& point, uint8_t alpha) |
| 217 | : fPoint(point), fPrev(nullptr), fNext(nullptr) |
| 218 | , fFirstEdgeAbove(nullptr), fLastEdgeAbove(nullptr) |
| 219 | , fFirstEdgeBelow(nullptr), fLastEdgeBelow(nullptr) |
| 220 | , fLeftEnclosingEdge(nullptr), fRightEnclosingEdge(nullptr) |
| 221 | , fPartner(nullptr) |
| 222 | , fAlpha(alpha) |
| 223 | , fSynthetic(false) |
| 224 | #if TRIANGULATOR_LOGGING |
| 225 | , fID (-1.0f) |
| 226 | #endif |
| 227 | {} |
| 228 | SkPoint fPoint; // Vertex position |
| 229 | Vertex* fPrev; // Linked list of contours, then Y-sorted vertices. |
| 230 | Vertex* fNext; // " |
| 231 | Edge* fFirstEdgeAbove; // Linked list of edges above this vertex. |
| 232 | Edge* fLastEdgeAbove; // " |
| 233 | Edge* fFirstEdgeBelow; // Linked list of edges below this vertex. |
| 234 | Edge* fLastEdgeBelow; // " |
| 235 | Edge* fLeftEnclosingEdge; // Nearest edge in the AEL left of this vertex. |
| 236 | Edge* fRightEnclosingEdge; // Nearest edge in the AEL right of this vertex. |
| 237 | Vertex* fPartner; // Corresponding inner or outer vertex (for AA). |
| 238 | uint8_t fAlpha; |
| 239 | bool fSynthetic; // Is this a synthetic vertex? |
| 240 | #if TRIANGULATOR_LOGGING |
| 241 | float fID; // Identifier used for logging. |
| 242 | #endif |
| 243 | }; |
| 244 | |
| 245 | struct GrTriangulator::VertexList { |
| 246 | VertexList() : fHead(nullptr), fTail(nullptr) {} |
| 247 | VertexList(Vertex* head, Vertex* tail) : fHead(head), fTail(tail) {} |
| 248 | Vertex* fHead; |
| 249 | Vertex* fTail; |
| 250 | void insert(Vertex* v, Vertex* prev, Vertex* next); |
| 251 | void append(Vertex* v) { insert(v, fTail, nullptr); } |
| 252 | void append(const VertexList& list) { |
| 253 | if (!list.fHead) { |
| 254 | return; |
| 255 | } |
| 256 | if (fTail) { |
| 257 | fTail->fNext = list.fHead; |
| 258 | list.fHead->fPrev = fTail; |
| 259 | } else { |
| 260 | fHead = list.fHead; |
| 261 | } |
| 262 | fTail = list.fTail; |
| 263 | } |
| 264 | void prepend(Vertex* v) { insert(v, nullptr, fHead); } |
| 265 | void remove(Vertex* v); |
| 266 | void close() { |
| 267 | if (fHead && fTail) { |
| 268 | fTail->fNext = fHead; |
| 269 | fHead->fPrev = fTail; |
| 270 | } |
| 271 | } |
| 272 | }; |
| 273 | |
| 274 | // A line equation in implicit form. fA * x + fB * y + fC = 0, for all points (x, y) on the line. |
| 275 | struct GrTriangulator::Line { |
| 276 | Line(double a, double b, double c) : fA(a), fB(b), fC(c) {} |
| 277 | Line(Vertex* p, Vertex* q) : Line(p->fPoint, q->fPoint) {} |
| 278 | Line(const SkPoint& p, const SkPoint& q) |
| 279 | : fA(static_cast<double>(q.fY) - p.fY) // a = dY |
| 280 | , fB(static_cast<double>(p.fX) - q.fX) // b = -dX |
| 281 | , fC(static_cast<double>(p.fY) * q.fX - // c = cross(q, p) |
| 282 | static_cast<double>(p.fX) * q.fY) {} |
| 283 | double dist(const SkPoint& p) const { return fA * p.fX + fB * p.fY + fC; } |
| 284 | Line operator*(double v) const { return Line(fA * v, fB * v, fC * v); } |
| 285 | double magSq() const { return fA * fA + fB * fB; } |
| 286 | void normalize() { |
| 287 | double len = sqrt(this->magSq()); |
| 288 | if (len == 0.0) { |
| 289 | return; |
| 290 | } |
| 291 | double scale = 1.0f / len; |
| 292 | fA *= scale; |
| 293 | fB *= scale; |
| 294 | fC *= scale; |
| 295 | } |
| 296 | bool nearParallel(const Line& o) const { |
| 297 | return fabs(o.fA - fA) < 0.00001 && fabs(o.fB - fB) < 0.00001; |
| 298 | } |
| 299 | |
| 300 | // Compute the intersection of two (infinite) Lines. |
| 301 | bool intersect(const Line& other, SkPoint* point) const; |
| 302 | double fA, fB, fC; |
| 303 | }; |
| 304 | |
| 305 | /** |
| 306 | * An Edge joins a top Vertex to a bottom Vertex. Edge ordering for the list of "edges above" and |
| 307 | * "edge below" a vertex as well as for the active edge list is handled by isLeftOf()/isRightOf(). |
| 308 | * Note that an Edge will give occasionally dist() != 0 for its own endpoints (because floating |
| 309 | * point). For speed, that case is only tested by the callers that require it (e.g., |
| 310 | * rewind_if_necessary()). Edges also handle checking for intersection with other edges. |
| 311 | * Currently, this converts the edges to the parametric form, in order to avoid doing a division |
| 312 | * until an intersection has been confirmed. This is slightly slower in the "found" case, but |
| 313 | * a lot faster in the "not found" case. |
| 314 | * |
| 315 | * The coefficients of the line equation stored in double precision to avoid catastrophic |
| 316 | * cancellation in the isLeftOf() and isRightOf() checks. Using doubles ensures that the result is |
| 317 | * correct in float, since it's a polynomial of degree 2. The intersect() function, being |
| 318 | * degree 5, is still subject to catastrophic cancellation. We deal with that by assuming its |
| 319 | * output may be incorrect, and adjusting the mesh topology to match (see comment at the top of |
| 320 | * this file). |
| 321 | */ |
| 322 | |
| 323 | struct GrTriangulator::Edge { |
| 324 | Edge(Vertex* top, Vertex* bottom, int winding, EdgeType type) |
| 325 | : fWinding(winding) |
| 326 | , fTop(top) |
| 327 | , fBottom(bottom) |
| 328 | , fType(type) |
| 329 | , fLeft(nullptr) |
| 330 | , fRight(nullptr) |
| 331 | , fPrevEdgeAbove(nullptr) |
| 332 | , fNextEdgeAbove(nullptr) |
| 333 | , fPrevEdgeBelow(nullptr) |
| 334 | , fNextEdgeBelow(nullptr) |
| 335 | , fLeftPoly(nullptr) |
| 336 | , fRightPoly(nullptr) |
| 337 | , fLeftPolyPrev(nullptr) |
| 338 | , fLeftPolyNext(nullptr) |
| 339 | , fRightPolyPrev(nullptr) |
| 340 | , fRightPolyNext(nullptr) |
| 341 | , fUsedInLeftPoly(false) |
| 342 | , fUsedInRightPoly(false) |
| 343 | , fLine(top, bottom) { |
| 344 | } |
| 345 | int fWinding; // 1 == edge goes downward; -1 = edge goes upward. |
| 346 | Vertex* fTop; // The top vertex in vertex-sort-order (sweep_lt). |
| 347 | Vertex* fBottom; // The bottom vertex in vertex-sort-order. |
| 348 | EdgeType fType; |
| 349 | Edge* fLeft; // The linked list of edges in the active edge list. |
| 350 | Edge* fRight; // " |
| 351 | Edge* fPrevEdgeAbove; // The linked list of edges in the bottom Vertex's "edges above". |
| 352 | Edge* fNextEdgeAbove; // " |
| 353 | Edge* fPrevEdgeBelow; // The linked list of edges in the top Vertex's "edges below". |
| 354 | Edge* fNextEdgeBelow; // " |
| 355 | Poly* fLeftPoly; // The Poly to the left of this edge, if any. |
| 356 | Poly* fRightPoly; // The Poly to the right of this edge, if any. |
| 357 | Edge* fLeftPolyPrev; |
| 358 | Edge* fLeftPolyNext; |
| 359 | Edge* fRightPolyPrev; |
| 360 | Edge* fRightPolyNext; |
| 361 | bool fUsedInLeftPoly; |
| 362 | bool fUsedInRightPoly; |
| 363 | Line fLine; |
| 364 | double dist(const SkPoint& p) const { return fLine.dist(p); } |
| 365 | bool isRightOf(Vertex* v) const { return fLine.dist(v->fPoint) < 0.0; } |
| 366 | bool isLeftOf(Vertex* v) const { return fLine.dist(v->fPoint) > 0.0; } |
| 367 | void recompute() { fLine = Line(fTop, fBottom); } |
| 368 | bool intersect(const Edge& other, SkPoint* p, uint8_t* alpha = nullptr) const; |
| 369 | }; |
| 370 | |
| 371 | struct GrTriangulator::EdgeList { |
| 372 | EdgeList() : fHead(nullptr), fTail(nullptr) {} |
| 373 | Edge* fHead; |
| 374 | Edge* fTail; |
| 375 | void insert(Edge* edge, Edge* prev, Edge* next); |
| 376 | void append(Edge* e) { insert(e, fTail, nullptr); } |
| 377 | void remove(Edge* edge); |
| 378 | void removeAll() { |
| 379 | while (fHead) { |
| 380 | this->remove(fHead); |
| 381 | } |
| 382 | } |
| 383 | void close() { |
| 384 | if (fHead && fTail) { |
| 385 | fTail->fRight = fHead; |
| 386 | fHead->fLeft = fTail; |
| 387 | } |
| 388 | } |
| 389 | bool contains(Edge* edge) const { return edge->fLeft || edge->fRight || fHead == edge; } |
| 390 | }; |
| 391 | |
| 392 | struct GrTriangulator::MonotonePoly { |
| 393 | MonotonePoly(Edge* edge, Side side, int winding) |
| 394 | : fSide(side) |
| 395 | , fFirstEdge(nullptr) |
| 396 | , fLastEdge(nullptr) |
| 397 | , fPrev(nullptr) |
| 398 | , fNext(nullptr) |
| 399 | , fWinding(winding) { |
| 400 | this->addEdge(edge); |
| 401 | } |
| 402 | Side fSide; |
| 403 | Edge* fFirstEdge; |
| 404 | Edge* fLastEdge; |
| 405 | MonotonePoly* fPrev; |
| 406 | MonotonePoly* fNext; |
| 407 | int fWinding; |
| 408 | void addEdge(Edge*); |
| 409 | void* emit(bool emitCoverage, void* data); |
| 410 | void* emitTriangle(Vertex* prev, Vertex* curr, Vertex* next, bool emitCoverage, |
| 411 | void* data) const; |
| 412 | }; |
| 413 | |
| 414 | struct GrTriangulator::Poly { |
| 415 | Poly(Vertex* v, int winding) |
| 416 | : fFirstVertex(v) |
| 417 | , fWinding(winding) |
| 418 | , fHead(nullptr) |
| 419 | , fTail(nullptr) |
| 420 | , fNext(nullptr) |
| 421 | , fPartner(nullptr) |
| 422 | , fCount(0) |
| 423 | { |
| 424 | #if TRIANGULATOR_LOGGING |
| 425 | static int gID = 0; |
| 426 | fID = gID++; |
| 427 | TESS_LOG("*** created Poly %d\n", fID); |
| 428 | #endif |
| 429 | } |
| 430 | Poly* addEdge(Edge* e, Side side, SkArenaAlloc& alloc); |
| 431 | void* emit(bool emitCoverage, void *data); |
| 432 | Vertex* lastVertex() const { return fTail ? fTail->fLastEdge->fBottom : fFirstVertex; } |
| 433 | Vertex* fFirstVertex; |
| 434 | int fWinding; |
| 435 | MonotonePoly* fHead; |
| 436 | MonotonePoly* fTail; |
| 437 | Poly* fNext; |
| 438 | Poly* fPartner; |
| 439 | int fCount; |
| 440 | #if TRIANGULATOR_LOGGING |
| 441 | int fID; |
| 442 | #endif |
| 443 | }; |
| 444 | |
| 445 | struct GrTriangulator::Comparator { |
| 446 | enum class Direction { kVertical, kHorizontal }; |
| 447 | Comparator(Direction direction) : fDirection(direction) {} |
| 448 | bool sweep_lt(const SkPoint& a, const SkPoint& b) const; |
| 449 | Direction fDirection; |
| 450 | }; |
| 451 | |
ethannicholas | e9709e8 | 2016-01-07 13:34:16 -0800 | [diff] [blame] | 452 | #endif |