Chromium Code Reviews| OLD | NEW |
|---|---|
| 1 /* | 1 /* |
| 2 * Copyright 2015 Google Inc. | 2 * Copyright 2015 Google Inc. |
| 3 * | 3 * |
| 4 * Use of this source code is governed by a BSD-style license that can be | 4 * Use of this source code is governed by a BSD-style license that can be |
| 5 * found in the LICENSE file. | 5 * found in the LICENSE file. |
| 6 */ | 6 */ |
| 7 | 7 |
| 8 #include "GrTessellatingPathRenderer.h" | 8 #include "GrTessellator.h" |
| 9 | 9 |
| 10 #include "GrBatchFlushState.h" | 10 #include "GrBatchFlushState.h" |
| 11 #include "GrBatchTest.h" | 11 #include "GrBatchTest.h" |
| 12 #include "GrDefaultGeoProcFactory.h" | 12 #include "GrDefaultGeoProcFactory.h" |
| 13 #include "GrPathUtils.h" | 13 #include "GrPathUtils.h" |
| 14 #include "GrVertices.h" | 14 #include "GrVertices.h" |
| 15 #include "GrResourceCache.h" | 15 #include "GrResourceCache.h" |
| 16 #include "GrResourceProvider.h" | 16 #include "GrResourceProvider.h" |
| 17 #include "SkChunkAlloc.h" | |
| 18 #include "SkGeometry.h" | 17 #include "SkGeometry.h" |
| 19 | 18 |
| 20 #include "batches/GrVertexBatch.h" | 19 #include "batches/GrVertexBatch.h" |
| 21 | 20 |
| 22 #include <stdio.h> | 21 #include <stdio.h> |
| 23 | 22 |
| 24 /* | 23 /* |
| 25 * This path renderer tessellates the path into triangles, uploads the triangles to a | |
| 26 * vertex buffer, and renders them with a single draw call. It does not currentl y do | |
| 27 * antialiasing, so it must be used in conjunction with multisampling. | |
| 28 * | |
| 29 * There are six stages to the algorithm: | 24 * There are six stages to the algorithm: |
| 30 * | 25 * |
| 31 * 1) Linearize the path contours into piecewise linear segments (path_to_contou rs()). | 26 * 1) Linearize the path contours into piecewise linear segments (path_to_contou rs()). |
| 32 * 2) Build a mesh of edges connecting the vertices (build_edges()). | 27 * 2) Build a mesh of edges connecting the vertices (build_edges()). |
| 33 * 3) Sort the vertices in Y (and secondarily in X) (merge_sort()). | 28 * 3) Sort the vertices in Y (and secondarily in X) (merge_sort()). |
| 34 * 4) Simplify the mesh by inserting new vertices at intersecting edges (simplif y()). | 29 * 4) Simplify the mesh by inserting new vertices at intersecting edges (simplif y()). |
| 35 * 5) Tessellate the simplified mesh into monotone polygons (tessellate()). | 30 * 5) Tessellate the simplified mesh into monotone polygons (tessellate()). |
| 36 * 6) Triangulate the monotone polygons directly into a vertex buffer (polys_to_ triangles()). | 31 * 6) Triangulate the monotone polygons directly into a vertex buffer (polys_to_ triangles()). |
| 37 * | 32 * |
| 38 * The vertex sorting in step (3) is a merge sort, since it plays well with the linked list | 33 * The vertex sorting in step (3) is a merge sort, since it plays well with the linked list |
| (...skipping 34 matching lines...) Expand 10 before | Expand all | Expand 10 after Loading... | |
| 73 * frequent. There may be other data structures worth investigating, however. | 68 * frequent. There may be other data structures worth investigating, however. |
| 74 * | 69 * |
| 75 * Note that the orientation of the line sweep algorithms is determined by the a spect ratio of the | 70 * Note that the orientation of the line sweep algorithms is determined by the a spect ratio of the |
| 76 * path bounds. When the path is taller than it is wide, we sort vertices based on increasing Y | 71 * path bounds. When the path is taller than it is wide, we sort vertices based on increasing Y |
| 77 * coordinate, and secondarily by increasing X coordinate. When the path is wide r than it is tall, | 72 * coordinate, and secondarily by increasing X coordinate. When the path is wide r than it is tall, |
| 78 * we sort by increasing X coordinate, but secondarily by *decreasing* Y coordin ate. This is so | 73 * we sort by increasing X coordinate, but secondarily by *decreasing* Y coordin ate. This is so |
| 79 * that the "left" and "right" orientation in the code remains correct (edges to the left are | 74 * that the "left" and "right" orientation in the code remains correct (edges to the left are |
| 80 * increasing in Y; edges to the right are decreasing in Y). That is, the settin g rotates 90 | 75 * increasing in Y; edges to the right are decreasing in Y). That is, the settin g rotates 90 |
| 81 * degrees counterclockwise, rather that transposing. | 76 * degrees counterclockwise, rather that transposing. |
| 82 */ | 77 */ |
| 83 #define LOGGING_ENABLED 0 | |
|
Stephen White
2016/01/04 22:51:19
If we do manage to keep Vertex and friends in the
| |
| 84 #define WIREFRAME 0 | |
| 85 | 78 |
| 86 #if LOGGING_ENABLED | 79 #if TESSELLATOR_LOGGING_ENABLED |
| 87 #define LOG printf | 80 #define LOG printf |
| 88 #else | 81 #else |
| 89 #define LOG(...) | 82 #define LOG(...) |
| 90 #endif | 83 #endif |
| 91 | 84 |
| 92 #define ALLOC_NEW(Type, args, alloc) new (alloc.allocThrow(sizeof(Type))) Type a rgs | 85 #define ALLOC_NEW(Type, args, alloc) new (alloc.allocThrow(sizeof(Type))) Type a rgs |
| 93 | 86 |
| 94 namespace { | 87 double Edge::dist(const SkPoint& p) const { |
| 88 return fDY * p.fX - fDX * p.fY + fC; | |
| 89 } | |
| 95 | 90 |
| 96 struct Vertex; | 91 bool Edge::isRightOf(TessellatorVertex* v) const { |
| 97 struct Edge; | 92 return dist(v->fPoint) < 0.0; |
| 93 } | |
| 94 | |
| 95 bool Edge::isLeftOf(TessellatorVertex* v) const { | |
| 96 return dist(v->fPoint) > 0.0; | |
| 97 } | |
| 98 | |
| 99 void Edge::recompute() { | |
| 100 fDX = static_cast<double>(fBottom->fPoint.fX) - fTop->fPoint.fX; | |
| 101 fDY = static_cast<double>(fBottom->fPoint.fY) - fTop->fPoint.fY; | |
| 102 fC = static_cast<double>(fTop->fPoint.fY) * fBottom->fPoint.fX - | |
| 103 static_cast<double>(fTop->fPoint.fX) * fBottom->fPoint.fY; | |
| 104 } | |
| 105 | |
| 106 bool Edge::intersect(const Edge& other, SkPoint* p) { | |
| 107 #if TESSELLATOR_LOGGING_ENABLED | |
| 108 LOG("intersecting %g -> %g with %g -> %g\n", | |
| 109 fTop->fID, fBottom->fID, | |
| 110 other.fTop->fID, other.fBottom->fID); | |
| 111 #endif | |
| 112 if (fTop == other.fTop || fBottom == other.fBottom) { | |
| 113 return false; | |
| 114 } | |
| 115 double denom = fDX * other.fDY - fDY * other.fDX; | |
| 116 if (denom == 0.0) { | |
| 117 return false; | |
| 118 } | |
| 119 double dx = static_cast<double>(fTop->fPoint.fX) - other.fTop->fPoint.fX; | |
| 120 double dy = static_cast<double>(fTop->fPoint.fY) - other.fTop->fPoint.fY; | |
| 121 double sNumer = dy * other.fDX - dx * other.fDY; | |
| 122 double tNumer = dy * fDX - dx * fDY; | |
| 123 // If (sNumer / denom) or (tNumer / denom) is not in [0..1], exit early. | |
| 124 // This saves us doing the divide below unless absolutely necessary. | |
| 125 if (denom > 0.0 ? (sNumer < 0.0 || sNumer > denom || tNumer < 0.0 || tNumer > denom) | |
| 126 : (sNumer > 0.0 || sNumer < denom || tNumer > 0.0 || tNumer < denom)) { | |
| 127 return false; | |
| 128 } | |
| 129 double s = sNumer / denom; | |
| 130 SkASSERT(s >= 0.0 && s <= 1.0); | |
| 131 p->fX = SkDoubleToScalar(fTop->fPoint.fX + s * fDX); | |
| 132 p->fY = SkDoubleToScalar(fTop->fPoint.fY + s * fDY); | |
| 133 return true; | |
| 134 } | |
| 135 | |
| 136 bool Edge::isActive(EdgeList* activeEdges) const { | |
| 137 return activeEdges && (fLeft || fRight || activeEdges->fHead == this); | |
| 138 } | |
| 139 | |
| 98 struct Poly; | 140 struct Poly; |
| 99 | 141 |
| 100 template <class T, T* T::*Prev, T* T::*Next> | 142 template <class T, T* T::*Prev, T* T::*Next> |
| 101 void insert(T* t, T* prev, T* next, T** head, T** tail) { | 143 void insert(T* t, T* prev, T* next, T** head, T** tail) { |
| 102 t->*Prev = prev; | 144 t->*Prev = prev; |
| 103 t->*Next = next; | 145 t->*Next = next; |
| 104 if (prev) { | 146 if (prev) { |
| 105 prev->*Next = t; | 147 prev->*Next = t; |
| 106 } else if (head) { | 148 } else if (head) { |
| 107 *head = t; | 149 *head = t; |
| (...skipping 13 matching lines...) Expand all Loading... | |
| 121 *head = t->*Next; | 163 *head = t->*Next; |
| 122 } | 164 } |
| 123 if (t->*Next) { | 165 if (t->*Next) { |
| 124 t->*Next->*Prev = t->*Prev; | 166 t->*Next->*Prev = t->*Prev; |
| 125 } else if (tail) { | 167 } else if (tail) { |
| 126 *tail = t->*Prev; | 168 *tail = t->*Prev; |
| 127 } | 169 } |
| 128 t->*Prev = t->*Next = nullptr; | 170 t->*Prev = t->*Next = nullptr; |
| 129 } | 171 } |
| 130 | 172 |
| 131 /** | |
| 132 * Vertices are used in three ways: first, the path contours are converted into a | |
| 133 * circularly-linked list of Vertices for each contour. After edge construction, the same Vertices | |
| 134 * are re-ordered by the merge sort according to the sweep_lt comparator (usuall y, increasing | |
| 135 * in Y) using the same fPrev/fNext pointers that were used for the contours, to avoid | |
| 136 * reallocation. Finally, MonotonePolys are built containing a circularly-linked list of | |
| 137 * Vertices. (Currently, those Vertices are newly-allocated for the MonotonePoly s, since | |
| 138 * an individual Vertex from the path mesh may belong to multiple | |
| 139 * MonotonePolys, so the original Vertices cannot be re-used. | |
| 140 */ | |
| 141 | |
| 142 struct Vertex { | |
| 143 Vertex(const SkPoint& point) | |
| 144 : fPoint(point), fPrev(nullptr), fNext(nullptr) | |
| 145 , fFirstEdgeAbove(nullptr), fLastEdgeAbove(nullptr) | |
| 146 , fFirstEdgeBelow(nullptr), fLastEdgeBelow(nullptr) | |
| 147 , fProcessed(false) | |
| 148 #if LOGGING_ENABLED | |
| 149 , fID (-1.0f) | |
| 150 #endif | |
| 151 {} | |
| 152 SkPoint fPoint; // Vertex position | |
| 153 Vertex* fPrev; // Linked list of contours, then Y-sorted vertices . | |
| 154 Vertex* fNext; // " | |
| 155 Edge* fFirstEdgeAbove; // Linked list of edges above this vertex. | |
| 156 Edge* fLastEdgeAbove; // " | |
| 157 Edge* fFirstEdgeBelow; // Linked list of edges below this vertex. | |
| 158 Edge* fLastEdgeBelow; // " | |
| 159 bool fProcessed; // Has this vertex been seen in simplify()? | |
| 160 #if LOGGING_ENABLED | |
| 161 float fID; // Identifier used for logging. | |
| 162 #endif | |
| 163 }; | |
| 164 | |
| 165 /******************************************************************************* ********/ | 173 /******************************************************************************* ********/ |
| 166 | 174 |
| 167 typedef bool (*CompareFunc)(const SkPoint& a, const SkPoint& b); | 175 typedef bool (*CompareFunc)(const SkPoint& a, const SkPoint& b); |
| 168 | 176 |
| 169 struct Comparator { | 177 struct Comparator { |
| 170 CompareFunc sweep_lt; | 178 CompareFunc sweep_lt; |
| 171 CompareFunc sweep_gt; | 179 CompareFunc sweep_gt; |
| 172 }; | 180 }; |
| 173 | 181 |
| 174 bool sweep_lt_horiz(const SkPoint& a, const SkPoint& b) { | 182 bool sweep_lt_horiz(const SkPoint& a, const SkPoint& b) { |
| 175 return a.fX == b.fX ? a.fY > b.fY : a.fX < b.fX; | 183 return a.fX == b.fX ? a.fY > b.fY : a.fX < b.fX; |
| 176 } | 184 } |
| 177 | 185 |
| 178 bool sweep_lt_vert(const SkPoint& a, const SkPoint& b) { | 186 bool sweep_lt_vert(const SkPoint& a, const SkPoint& b) { |
| 179 return a.fY == b.fY ? a.fX < b.fX : a.fY < b.fY; | 187 return a.fY == b.fY ? a.fX < b.fX : a.fY < b.fY; |
| 180 } | 188 } |
| 181 | 189 |
| 182 bool sweep_gt_horiz(const SkPoint& a, const SkPoint& b) { | 190 bool sweep_gt_horiz(const SkPoint& a, const SkPoint& b) { |
| 183 return a.fX == b.fX ? a.fY < b.fY : a.fX > b.fX; | 191 return a.fX == b.fX ? a.fY < b.fY : a.fX > b.fX; |
| 184 } | 192 } |
| 185 | 193 |
| 186 bool sweep_gt_vert(const SkPoint& a, const SkPoint& b) { | 194 bool sweep_gt_vert(const SkPoint& a, const SkPoint& b) { |
| 187 return a.fY == b.fY ? a.fX > b.fX : a.fY > b.fY; | 195 return a.fY == b.fY ? a.fX > b.fX : a.fY > b.fY; |
| 188 } | 196 } |
| 189 | 197 |
| 190 inline SkPoint* emit_vertex(Vertex* v, SkPoint* data) { | 198 inline SkPoint* emit_vertex(TessellatorVertex* v, SkPoint* data) { |
| 191 *data++ = v->fPoint; | 199 *data++ = v->fPoint; |
| 192 return data; | 200 return data; |
| 193 } | 201 } |
| 194 | 202 |
| 195 SkPoint* emit_triangle(Vertex* v0, Vertex* v1, Vertex* v2, SkPoint* data) { | 203 SkPoint* emit_triangle(TessellatorVertex* v0, TessellatorVertex* v1, Tessellator Vertex* v2, |
| 196 #if WIREFRAME | 204 SkPoint* data) { |
| 205 #if TESSELLATOR_WIREFRAME | |
| 197 data = emit_vertex(v0, data); | 206 data = emit_vertex(v0, data); |
| 198 data = emit_vertex(v1, data); | 207 data = emit_vertex(v1, data); |
| 199 data = emit_vertex(v1, data); | 208 data = emit_vertex(v1, data); |
| 200 data = emit_vertex(v2, data); | 209 data = emit_vertex(v2, data); |
| 201 data = emit_vertex(v2, data); | 210 data = emit_vertex(v2, data); |
| 202 data = emit_vertex(v0, data); | 211 data = emit_vertex(v0, data); |
| 203 #else | 212 #else |
| 204 data = emit_vertex(v0, data); | 213 data = emit_vertex(v0, data); |
| 205 data = emit_vertex(v1, data); | 214 data = emit_vertex(v1, data); |
| 206 data = emit_vertex(v2, data); | 215 data = emit_vertex(v2, data); |
| 207 #endif | 216 #endif |
| 208 return data; | 217 return data; |
| 209 } | 218 } |
| 210 | 219 |
| 211 struct EdgeList { | |
| 212 EdgeList() : fHead(nullptr), fTail(nullptr) {} | |
| 213 Edge* fHead; | |
| 214 Edge* fTail; | |
| 215 }; | |
| 216 | |
| 217 /** | 220 /** |
| 218 * An Edge joins a top Vertex to a bottom Vertex. Edge ordering for the list of "edges above" and | 221 * An Edge joins a top Vertex to a bottom Vertex. Edge ordering for the list of "edges above" and |
| 219 * "edge below" a vertex as well as for the active edge list is handled by isLef tOf()/isRightOf(). | 222 * "edge below" a vertex as well as for the active edge list is handled by isLef tOf()/isRightOf(). |
| 220 * Note that an Edge will give occasionally dist() != 0 for its own endpoints (b ecause floating | 223 * Note that an Edge will give occasionally dist() != 0 for its own endpoints (b ecause floating |
| 221 * point). For speed, that case is only tested by the callers which require it ( e.g., | 224 * point). For speed, that case is only tested by the callers which require it ( e.g., |
| 222 * cleanup_active_edges()). Edges also handle checking for intersection with oth er edges. | 225 * cleanup_active_edges()). Edges also handle checking for intersection with oth er edges. |
| 223 * Currently, this converts the edges to the parametric form, in order to avoid doing a division | 226 * Currently, this converts the edges to the parametric form, in order to avoid doing a division |
| 224 * until an intersection has been confirmed. This is slightly slower in the "fou nd" case, but | 227 * until an intersection has been confirmed. This is slightly slower in the "fou nd" case, but |
| 225 * a lot faster in the "not found" case. | 228 * a lot faster in the "not found" case. |
| 226 * | 229 * |
| 227 * The coefficients of the line equation stored in double precision to avoid cat astrphic | 230 * The coefficients of the line equation stored in double precision to avoid cat astrphic |
| 228 * cancellation in the isLeftOf() and isRightOf() checks. Using doubles ensures that the result is | 231 * cancellation in the isLeftOf() and isRightOf() checks. Using doubles ensures that the result is |
| 229 * correct in float, since it's a polynomial of degree 2. The intersect() functi on, being | 232 * correct in float, since it's a polynomial of degree 2. The intersect() functi on, being |
| 230 * degree 5, is still subject to catastrophic cancellation. We deal with that by assuming its | 233 * degree 5, is still subject to catastrophic cancellation. We deal with that by assuming its |
| 231 * output may be incorrect, and adjusting the mesh topology to match (see commen t at the top of | 234 * output may be incorrect, and adjusting the mesh topology to match (see commen t at the top of |
| 232 * this file). | 235 * this file). |
| 233 */ | 236 */ |
| 234 | 237 |
| 235 struct Edge { | |
| 236 Edge(Vertex* top, Vertex* bottom, int winding) | |
| 237 : fWinding(winding) | |
| 238 , fTop(top) | |
| 239 , fBottom(bottom) | |
| 240 , fLeft(nullptr) | |
| 241 , fRight(nullptr) | |
| 242 , fPrevEdgeAbove(nullptr) | |
| 243 , fNextEdgeAbove(nullptr) | |
| 244 , fPrevEdgeBelow(nullptr) | |
| 245 , fNextEdgeBelow(nullptr) | |
| 246 , fLeftPoly(nullptr) | |
| 247 , fRightPoly(nullptr) { | |
| 248 recompute(); | |
| 249 } | |
| 250 int fWinding; // 1 == edge goes downward; -1 = edge goes upwar d. | |
| 251 Vertex* fTop; // The top vertex in vertex-sort-order (sweep_lt ). | |
| 252 Vertex* fBottom; // The bottom vertex in vertex-sort-order. | |
| 253 Edge* fLeft; // The linked list of edges in the active edge l ist. | |
| 254 Edge* fRight; // " | |
| 255 Edge* fPrevEdgeAbove; // The linked list of edges in the bottom Vertex 's "edges above". | |
| 256 Edge* fNextEdgeAbove; // " | |
| 257 Edge* fPrevEdgeBelow; // The linked list of edges in the top Vertex's "edges below". | |
| 258 Edge* fNextEdgeBelow; // " | |
| 259 Poly* fLeftPoly; // The Poly to the left of this edge, if any. | |
| 260 Poly* fRightPoly; // The Poly to the right of this edge, if any. | |
| 261 double fDX; // The line equation for this edge, in implicit form. | |
| 262 double fDY; // fDY * x + fDX * y + fC = 0, for point (x, y) on the line. | |
| 263 double fC; | |
| 264 double dist(const SkPoint& p) const { | |
| 265 return fDY * p.fX - fDX * p.fY + fC; | |
| 266 } | |
| 267 bool isRightOf(Vertex* v) const { | |
| 268 return dist(v->fPoint) < 0.0; | |
| 269 } | |
| 270 bool isLeftOf(Vertex* v) const { | |
| 271 return dist(v->fPoint) > 0.0; | |
| 272 } | |
| 273 void recompute() { | |
| 274 fDX = static_cast<double>(fBottom->fPoint.fX) - fTop->fPoint.fX; | |
| 275 fDY = static_cast<double>(fBottom->fPoint.fY) - fTop->fPoint.fY; | |
| 276 fC = static_cast<double>(fTop->fPoint.fY) * fBottom->fPoint.fX - | |
| 277 static_cast<double>(fTop->fPoint.fX) * fBottom->fPoint.fY; | |
| 278 } | |
| 279 bool intersect(const Edge& other, SkPoint* p) { | |
| 280 LOG("intersecting %g -> %g with %g -> %g\n", | |
| 281 fTop->fID, fBottom->fID, | |
| 282 other.fTop->fID, other.fBottom->fID); | |
| 283 if (fTop == other.fTop || fBottom == other.fBottom) { | |
| 284 return false; | |
| 285 } | |
| 286 double denom = fDX * other.fDY - fDY * other.fDX; | |
| 287 if (denom == 0.0) { | |
| 288 return false; | |
| 289 } | |
| 290 double dx = static_cast<double>(fTop->fPoint.fX) - other.fTop->fPoint.fX ; | |
| 291 double dy = static_cast<double>(fTop->fPoint.fY) - other.fTop->fPoint.fY ; | |
| 292 double sNumer = dy * other.fDX - dx * other.fDY; | |
| 293 double tNumer = dy * fDX - dx * fDY; | |
| 294 // If (sNumer / denom) or (tNumer / denom) is not in [0..1], exit early. | |
| 295 // This saves us doing the divide below unless absolutely necessary. | |
| 296 if (denom > 0.0 ? (sNumer < 0.0 || sNumer > denom || tNumer < 0.0 || tNu mer > denom) | |
| 297 : (sNumer > 0.0 || sNumer < denom || tNumer > 0.0 || tNu mer < denom)) { | |
| 298 return false; | |
| 299 } | |
| 300 double s = sNumer / denom; | |
| 301 SkASSERT(s >= 0.0 && s <= 1.0); | |
| 302 p->fX = SkDoubleToScalar(fTop->fPoint.fX + s * fDX); | |
| 303 p->fY = SkDoubleToScalar(fTop->fPoint.fY + s * fDY); | |
| 304 return true; | |
| 305 } | |
| 306 bool isActive(EdgeList* activeEdges) const { | |
| 307 return activeEdges && (fLeft || fRight || activeEdges->fHead == this); | |
| 308 } | |
| 309 }; | |
| 310 | |
| 311 /******************************************************************************* ********/ | 238 /******************************************************************************* ********/ |
| 312 | 239 |
| 313 struct Poly { | 240 struct Poly { |
| 314 Poly(int winding) | 241 Poly(int winding) |
| 315 : fWinding(winding) | 242 : fWinding(winding) |
| 316 , fHead(nullptr) | 243 , fHead(nullptr) |
| 317 , fTail(nullptr) | 244 , fTail(nullptr) |
| 318 , fActive(nullptr) | 245 , fActive(nullptr) |
| 319 , fNext(nullptr) | 246 , fNext(nullptr) |
| 320 , fPartner(nullptr) | 247 , fPartner(nullptr) |
| 321 , fCount(0) | 248 , fCount(0) |
| 322 { | 249 { |
| 323 #if LOGGING_ENABLED | 250 #if TESSELLATOR_LOGGING_ENABLED |
| 324 static int gID = 0; | 251 static int gID = 0; |
| 325 fID = gID++; | 252 fID = gID++; |
| 326 LOG("*** created Poly %d\n", fID); | 253 LOG("*** created Poly %d\n", fID); |
| 327 #endif | 254 #endif |
| 328 } | 255 } |
| 329 typedef enum { kNeither_Side, kLeft_Side, kRight_Side } Side; | 256 typedef enum { kNeither_Side, kLeft_Side, kRight_Side } Side; |
| 330 struct MonotonePoly { | 257 struct MonotonePoly { |
| 331 MonotonePoly() | 258 MonotonePoly() |
| 332 : fSide(kNeither_Side) | 259 : fSide(kNeither_Side) |
| 333 , fHead(nullptr) | 260 , fHead(nullptr) |
| 334 , fTail(nullptr) | 261 , fTail(nullptr) |
| 335 , fPrev(nullptr) | 262 , fPrev(nullptr) |
| 336 , fNext(nullptr) {} | 263 , fNext(nullptr) {} |
| 337 Side fSide; | 264 Side fSide; |
| 338 Vertex* fHead; | 265 TessellatorVertex* fHead; |
| 339 Vertex* fTail; | 266 TessellatorVertex* fTail; |
| 340 MonotonePoly* fPrev; | 267 MonotonePoly* fPrev; |
| 341 MonotonePoly* fNext; | 268 MonotonePoly* fNext; |
| 342 bool addVertex(Vertex* v, Side side, SkChunkAlloc& alloc) { | 269 bool addVertex(TessellatorVertex* v, Side side, SkChunkAlloc& alloc) { |
| 343 Vertex* newV = ALLOC_NEW(Vertex, (v->fPoint), alloc); | 270 TessellatorVertex* newV = ALLOC_NEW(TessellatorVertex, (v->fPoint), alloc); |
| 344 bool done = false; | 271 bool done = false; |
| 345 if (fSide == kNeither_Side) { | 272 if (fSide == kNeither_Side) { |
| 346 fSide = side; | 273 fSide = side; |
| 347 } else { | 274 } else { |
| 348 done = side != fSide; | 275 done = side != fSide; |
| 349 } | 276 } |
| 350 if (fHead == nullptr) { | 277 if (fHead == nullptr) { |
| 351 fHead = fTail = newV; | 278 fHead = fTail = newV; |
| 352 } else if (fSide == kRight_Side) { | 279 } else if (fSide == kRight_Side) { |
| 353 newV->fPrev = fTail; | 280 newV->fPrev = fTail; |
| 354 fTail->fNext = newV; | 281 fTail->fNext = newV; |
| 355 fTail = newV; | 282 fTail = newV; |
| 356 } else { | 283 } else { |
| 357 newV->fNext = fHead; | 284 newV->fNext = fHead; |
| 358 fHead->fPrev = newV; | 285 fHead->fPrev = newV; |
| 359 fHead = newV; | 286 fHead = newV; |
| 360 } | 287 } |
| 361 return done; | 288 return done; |
| 362 } | 289 } |
| 363 | 290 |
| 364 SkPoint* emit(SkPoint* data) { | 291 SkPoint* emit(int winding, SkPoint* data) { |
| 365 Vertex* first = fHead; | 292 TessellatorVertex* first = fHead; |
| 366 Vertex* v = first->fNext; | 293 TessellatorVertex* v = first->fNext; |
| 367 while (v != fTail) { | 294 while (v != fTail) { |
| 368 SkASSERT(v && v->fPrev && v->fNext); | 295 SkASSERT(v && v->fPrev && v->fNext); |
| 369 Vertex* prev = v->fPrev; | 296 TessellatorVertex* prev = v->fPrev; |
| 370 Vertex* curr = v; | 297 TessellatorVertex* curr = v; |
| 371 Vertex* next = v->fNext; | 298 TessellatorVertex* next = v->fNext; |
| 372 double ax = static_cast<double>(curr->fPoint.fX) - prev->fPoint. fX; | 299 double ax = static_cast<double>(curr->fPoint.fX) - prev->fPoint. fX; |
| 373 double ay = static_cast<double>(curr->fPoint.fY) - prev->fPoint. fY; | 300 double ay = static_cast<double>(curr->fPoint.fY) - prev->fPoint. fY; |
| 374 double bx = static_cast<double>(next->fPoint.fX) - curr->fPoint. fX; | 301 double bx = static_cast<double>(next->fPoint.fX) - curr->fPoint. fX; |
| 375 double by = static_cast<double>(next->fPoint.fY) - curr->fPoint. fY; | 302 double by = static_cast<double>(next->fPoint.fY) - curr->fPoint. fY; |
| 376 if (ax * by - ay * bx >= 0.0) { | 303 if (ax * by - ay * bx >= 0.0) { |
| 377 data = emit_triangle(prev, curr, next, data); | 304 data = emit_triangle(prev, curr, next, data); |
| 378 v->fPrev->fNext = v->fNext; | 305 v->fPrev->fNext = v->fNext; |
| 379 v->fNext->fPrev = v->fPrev; | 306 v->fNext->fPrev = v->fPrev; |
| 380 if (v->fPrev == first) { | 307 if (v->fPrev == first) { |
| 381 v = v->fNext; | 308 v = v->fNext; |
| 382 } else { | 309 } else { |
| 383 v = v->fPrev; | 310 v = v->fPrev; |
| 384 } | 311 } |
| 385 } else { | 312 } else { |
| 386 v = v->fNext; | 313 v = v->fNext; |
| 387 } | 314 } |
| 388 } | 315 } |
| 389 return data; | 316 return data; |
| 390 } | 317 } |
| 391 }; | 318 }; |
| 392 Poly* addVertex(Vertex* v, Side side, SkChunkAlloc& alloc) { | 319 Poly* addVertex(TessellatorVertex* v, Side side, SkChunkAlloc& alloc) { |
| 393 LOG("addVertex() to %d at %g (%g, %g), %s side\n", fID, v->fID, v->fPoin t.fX, v->fPoint.fY, | 320 LOG("addVertex() to %d at %g (%g, %g), %s side\n", fID, v->fID, v->fPoin t.fX, v->fPoint.fY, |
| 394 side == kLeft_Side ? "left" : side == kRight_Side ? "right" : "ne ither"); | 321 side == kLeft_Side ? "left" : side == kRight_Side ? "right" : "ne ither"); |
| 395 Poly* partner = fPartner; | 322 Poly* partner = fPartner; |
| 396 Poly* poly = this; | 323 Poly* poly = this; |
| 397 if (partner) { | 324 if (partner) { |
| 398 fPartner = partner->fPartner = nullptr; | 325 fPartner = partner->fPartner = nullptr; |
| 399 } | 326 } |
| 400 if (!fActive) { | 327 if (!fActive) { |
| 401 fActive = ALLOC_NEW(MonotonePoly, (), alloc); | 328 fActive = ALLOC_NEW(MonotonePoly, (), alloc); |
| 402 } | 329 } |
| 403 if (fActive->addVertex(v, side, alloc)) { | 330 if (fActive->addVertex(v, side, alloc)) { |
| 404 if (fTail) { | 331 if (fTail) { |
| 405 fActive->fPrev = fTail; | 332 fActive->fPrev = fTail; |
| 406 fTail->fNext = fActive; | 333 fTail->fNext = fActive; |
| 407 fTail = fActive; | 334 fTail = fActive; |
| 408 } else { | 335 } else { |
| 409 fHead = fTail = fActive; | 336 fHead = fTail = fActive; |
| 410 } | 337 } |
| 411 if (partner) { | 338 if (partner) { |
| 412 partner->addVertex(v, side, alloc); | 339 partner->addVertex(v, side, alloc); |
| 413 poly = partner; | 340 poly = partner; |
| 414 } else { | 341 } else { |
| 415 Vertex* prev = fActive->fSide == Poly::kLeft_Side ? | 342 TessellatorVertex* prev = fActive->fSide == Poly::kLeft_Side ? |
| 416 fActive->fHead->fNext : fActive->fTail->fPrev; | 343 fActive->fHead->fNext : fActive->fTail->fPrev; |
| 417 fActive = ALLOC_NEW(MonotonePoly, , alloc); | 344 fActive = ALLOC_NEW(MonotonePoly, , alloc); |
| 418 fActive->addVertex(prev, Poly::kNeither_Side, alloc); | 345 fActive->addVertex(prev, Poly::kNeither_Side, alloc); |
| 419 fActive->addVertex(v, side, alloc); | 346 fActive->addVertex(v, side, alloc); |
| 420 } | 347 } |
| 421 } | 348 } |
| 422 fCount++; | 349 fCount++; |
| 423 return poly; | 350 return poly; |
| 424 } | 351 } |
| 425 void end(Vertex* v, SkChunkAlloc& alloc) { | 352 void end(TessellatorVertex* v, SkChunkAlloc& alloc) { |
| 426 LOG("end() %d at %g, %g\n", fID, v->fPoint.fX, v->fPoint.fY); | 353 LOG("end() %d at %g, %g\n", fID, v->fPoint.fX, v->fPoint.fY); |
| 427 if (fPartner) { | 354 if (fPartner) { |
| 428 fPartner = fPartner->fPartner = nullptr; | 355 fPartner = fPartner->fPartner = nullptr; |
| 429 } | 356 } |
| 430 addVertex(v, fActive->fSide == kLeft_Side ? kRight_Side : kLeft_Side, al loc); | 357 addVertex(v, fActive->fSide == kLeft_Side ? kRight_Side : kLeft_Side, al loc); |
| 431 } | 358 } |
| 432 SkPoint* emit(SkPoint *data) { | 359 SkPoint* emit(SkPoint *data) { |
| 433 if (fCount < 3) { | 360 if (fCount < 3) { |
| 434 return data; | 361 return data; |
| 435 } | 362 } |
| 436 LOG("emit() %d, size %d\n", fID, fCount); | 363 LOG("emit() %d, size %d\n", fID, fCount); |
| 437 for (MonotonePoly* m = fHead; m != nullptr; m = m->fNext) { | 364 for (MonotonePoly* m = fHead; m != nullptr; m = m->fNext) { |
| 438 data = m->emit(data); | 365 data = m->emit(fWinding, data); |
| 439 } | 366 } |
| 440 return data; | 367 return data; |
| 441 } | 368 } |
| 442 int fWinding; | 369 int fWinding; |
| 443 MonotonePoly* fHead; | 370 MonotonePoly* fHead; |
| 444 MonotonePoly* fTail; | 371 MonotonePoly* fTail; |
| 445 MonotonePoly* fActive; | 372 MonotonePoly* fActive; |
| 446 Poly* fNext; | 373 Poly* fNext; |
| 447 Poly* fPartner; | 374 Poly* fPartner; |
| 448 int fCount; | 375 int fCount; |
| 449 #if LOGGING_ENABLED | 376 #if TESSELLATOR_LOGGING_ENABLED |
| 450 int fID; | 377 int fID; |
| 451 #endif | 378 #endif |
| 452 }; | 379 }; |
| 453 | 380 |
| 454 /******************************************************************************* ********/ | 381 /******************************************************************************* ********/ |
| 455 | 382 |
| 456 bool coincident(const SkPoint& a, const SkPoint& b) { | 383 bool coincident(const SkPoint& a, const SkPoint& b) { |
| 457 return a == b; | 384 return a == b; |
| 458 } | 385 } |
| 459 | 386 |
| 460 Poly* new_poly(Poly** head, Vertex* v, int winding, SkChunkAlloc& alloc) { | 387 Poly* new_poly(Poly** head, TessellatorVertex* v, int winding, SkChunkAlloc& all oc) { |
| 461 Poly* poly = ALLOC_NEW(Poly, (winding), alloc); | 388 Poly* poly = ALLOC_NEW(Poly, (winding), alloc); |
| 462 poly->addVertex(v, Poly::kNeither_Side, alloc); | 389 poly->addVertex(v, Poly::kNeither_Side, alloc); |
| 463 poly->fNext = *head; | 390 poly->fNext = *head; |
| 464 *head = poly; | 391 *head = poly; |
| 465 return poly; | 392 return poly; |
| 466 } | 393 } |
| 467 | 394 |
| 468 Vertex* append_point_to_contour(const SkPoint& p, Vertex* prev, Vertex** head, | 395 TessellatorVertex* append_point_to_contour(const SkPoint& p, TessellatorVertex* prev, |
| 469 SkChunkAlloc& alloc) { | 396 TessellatorVertex** head, SkChunkAllo c& alloc) { |
| 470 Vertex* v = ALLOC_NEW(Vertex, (p), alloc); | 397 TessellatorVertex* v = ALLOC_NEW(TessellatorVertex, (p), alloc); |
| 471 #if LOGGING_ENABLED | 398 #if TESSELLATOR_LOGGING_ENABLED |
| 472 static float gID = 0.0f; | 399 static float gID = 0.0f; |
| 473 v->fID = gID++; | 400 v->fID = gID++; |
| 474 #endif | 401 #endif |
| 475 if (prev) { | 402 if (prev) { |
| 476 prev->fNext = v; | 403 prev->fNext = v; |
| 477 v->fPrev = prev; | 404 v->fPrev = prev; |
| 478 } else { | 405 } else { |
| 479 *head = v; | 406 *head = v; |
| 480 } | 407 } |
| 481 return v; | 408 return v; |
| 482 } | 409 } |
| 483 | 410 |
| 484 Vertex* generate_quadratic_points(const SkPoint& p0, | 411 TessellatorVertex* generate_quadratic_points(const SkPoint& p0, |
| 485 const SkPoint& p1, | 412 const SkPoint& p1, |
| 486 const SkPoint& p2, | 413 const SkPoint& p2, |
| 487 SkScalar tolSqd, | 414 SkScalar tolSqd, |
| 488 Vertex* prev, | 415 TessellatorVertex* prev, |
| 489 Vertex** head, | 416 TessellatorVertex** head, |
| 490 int pointsLeft, | 417 int pointsLeft, |
| 491 SkChunkAlloc& alloc) { | 418 SkChunkAlloc& alloc) { |
| 492 SkScalar d = p1.distanceToLineSegmentBetweenSqd(p0, p2); | 419 SkScalar d = p1.distanceToLineSegmentBetweenSqd(p0, p2); |
| 493 if (pointsLeft < 2 || d < tolSqd || !SkScalarIsFinite(d)) { | 420 if (pointsLeft < 2 || d < tolSqd || !SkScalarIsFinite(d)) { |
| 494 return append_point_to_contour(p2, prev, head, alloc); | 421 return append_point_to_contour(p2, prev, head, alloc); |
| 495 } | 422 } |
| 496 | 423 |
| 497 const SkPoint q[] = { | 424 const SkPoint q[] = { |
| 498 { SkScalarAve(p0.fX, p1.fX), SkScalarAve(p0.fY, p1.fY) }, | 425 { SkScalarAve(p0.fX, p1.fX), SkScalarAve(p0.fY, p1.fY) }, |
| 499 { SkScalarAve(p1.fX, p2.fX), SkScalarAve(p1.fY, p2.fY) }, | 426 { SkScalarAve(p1.fX, p2.fX), SkScalarAve(p1.fY, p2.fY) }, |
| 500 }; | 427 }; |
| 501 const SkPoint r = { SkScalarAve(q[0].fX, q[1].fX), SkScalarAve(q[0].fY, q[1] .fY) }; | 428 const SkPoint r = { SkScalarAve(q[0].fX, q[1].fX), SkScalarAve(q[0].fY, q[1] .fY) }; |
| 502 | 429 |
| 503 pointsLeft >>= 1; | 430 pointsLeft >>= 1; |
| 504 prev = generate_quadratic_points(p0, q[0], r, tolSqd, prev, head, pointsLeft , alloc); | 431 prev = generate_quadratic_points(p0, q[0], r, tolSqd, prev, head, pointsLeft , alloc); |
| 505 prev = generate_quadratic_points(r, q[1], p2, tolSqd, prev, head, pointsLeft , alloc); | 432 prev = generate_quadratic_points(r, q[1], p2, tolSqd, prev, head, pointsLeft , alloc); |
| 506 return prev; | 433 return prev; |
| 507 } | 434 } |
| 508 | 435 |
| 509 Vertex* generate_cubic_points(const SkPoint& p0, | 436 TessellatorVertex* generate_cubic_points(const SkPoint& p0, |
| 510 const SkPoint& p1, | 437 const SkPoint& p1, |
| 511 const SkPoint& p2, | 438 const SkPoint& p2, |
| 512 const SkPoint& p3, | 439 const SkPoint& p3, |
| 513 SkScalar tolSqd, | 440 SkScalar tolSqd, |
| 514 Vertex* prev, | 441 TessellatorVertex* prev, |
| 515 Vertex** head, | 442 TessellatorVertex** head, |
| 516 int pointsLeft, | 443 int pointsLeft, |
| 517 SkChunkAlloc& alloc) { | 444 SkChunkAlloc& alloc) { |
| 518 SkScalar d1 = p1.distanceToLineSegmentBetweenSqd(p0, p3); | 445 SkScalar d1 = p1.distanceToLineSegmentBetweenSqd(p0, p3); |
| 519 SkScalar d2 = p2.distanceToLineSegmentBetweenSqd(p0, p3); | 446 SkScalar d2 = p2.distanceToLineSegmentBetweenSqd(p0, p3); |
| 520 if (pointsLeft < 2 || (d1 < tolSqd && d2 < tolSqd) || | 447 if (pointsLeft < 2 || (d1 < tolSqd && d2 < tolSqd) || |
| 521 !SkScalarIsFinite(d1) || !SkScalarIsFinite(d2)) { | 448 !SkScalarIsFinite(d1) || !SkScalarIsFinite(d2)) { |
| 522 return append_point_to_contour(p3, prev, head, alloc); | 449 return append_point_to_contour(p3, prev, head, alloc); |
| 523 } | 450 } |
| 524 const SkPoint q[] = { | 451 const SkPoint q[] = { |
| 525 { SkScalarAve(p0.fX, p1.fX), SkScalarAve(p0.fY, p1.fY) }, | 452 { SkScalarAve(p0.fX, p1.fX), SkScalarAve(p0.fY, p1.fY) }, |
| 526 { SkScalarAve(p1.fX, p2.fX), SkScalarAve(p1.fY, p2.fY) }, | 453 { SkScalarAve(p1.fX, p2.fX), SkScalarAve(p1.fY, p2.fY) }, |
| 527 { SkScalarAve(p2.fX, p3.fX), SkScalarAve(p2.fY, p3.fY) } | 454 { SkScalarAve(p2.fX, p3.fX), SkScalarAve(p2.fY, p3.fY) } |
| 528 }; | 455 }; |
| 529 const SkPoint r[] = { | 456 const SkPoint r[] = { |
| 530 { SkScalarAve(q[0].fX, q[1].fX), SkScalarAve(q[0].fY, q[1].fY) }, | 457 { SkScalarAve(q[0].fX, q[1].fX), SkScalarAve(q[0].fY, q[1].fY) }, |
| 531 { SkScalarAve(q[1].fX, q[2].fX), SkScalarAve(q[1].fY, q[2].fY) } | 458 { SkScalarAve(q[1].fX, q[2].fX), SkScalarAve(q[1].fY, q[2].fY) } |
| 532 }; | 459 }; |
| 533 const SkPoint s = { SkScalarAve(r[0].fX, r[1].fX), SkScalarAve(r[0].fY, r[1] .fY) }; | 460 const SkPoint s = { SkScalarAve(r[0].fX, r[1].fX), SkScalarAve(r[0].fY, r[1] .fY) }; |
| 534 pointsLeft >>= 1; | 461 pointsLeft >>= 1; |
| 535 prev = generate_cubic_points(p0, q[0], r[0], s, tolSqd, prev, head, pointsLe ft, alloc); | 462 prev = generate_cubic_points(p0, q[0], r[0], s, tolSqd, prev, head, pointsLe ft, alloc); |
| 536 prev = generate_cubic_points(s, r[1], q[2], p3, tolSqd, prev, head, pointsLe ft, alloc); | 463 prev = generate_cubic_points(s, r[1], q[2], p3, tolSqd, prev, head, pointsLe ft, alloc); |
| 537 return prev; | 464 return prev; |
| 538 } | 465 } |
| 539 | 466 |
| 540 // Stage 1: convert the input path to a set of linear contours (linked list of V ertices). | 467 // Stage 1: convert the input path to a set of linear contours (linked list of V ertices). |
| 541 | 468 |
| 542 void path_to_contours(const SkPath& path, SkScalar tolerance, const SkRect& clip Bounds, | 469 void path_to_contours(const SkPath& path, SkScalar tolerance, const SkRect& clip Bounds, |
| 543 Vertex** contours, SkChunkAlloc& alloc, bool *isLinear) { | 470 TessellatorVertex** contours, SkChunkAlloc& alloc, bool *i sLinear) { |
| 544 | |
| 545 SkScalar toleranceSqd = tolerance * tolerance; | 471 SkScalar toleranceSqd = tolerance * tolerance; |
| 546 | 472 |
| 547 SkPoint pts[4]; | 473 SkPoint pts[4]; |
| 548 bool done = false; | 474 bool done = false; |
| 549 *isLinear = true; | 475 *isLinear = true; |
| 550 SkPath::Iter iter(path, false); | 476 SkPath::Iter iter(path, false); |
| 551 Vertex* prev = nullptr; | 477 TessellatorVertex* prev = nullptr; |
| 552 Vertex* head = nullptr; | 478 TessellatorVertex* head = nullptr; |
| 553 if (path.isInverseFillType()) { | 479 if (path.isInverseFillType()) { |
| 554 SkPoint quad[4]; | 480 SkPoint quad[4]; |
| 555 clipBounds.toQuad(quad); | 481 clipBounds.toQuad(quad); |
| 556 for (int i = 3; i >= 0; i--) { | 482 for (int i = 3; i >= 0; i--) { |
| 557 prev = append_point_to_contour(quad[i], prev, &head, alloc); | 483 prev = append_point_to_contour(quad[i], prev, &head, alloc); |
| 558 } | 484 } |
| 559 head->fPrev = prev; | 485 head->fPrev = prev; |
| 560 prev->fNext = head; | 486 prev->fNext = head; |
| 561 *contours++ = head; | 487 *contours++ = head; |
| 562 head = prev = nullptr; | 488 head = prev = nullptr; |
| (...skipping 70 matching lines...) Expand 10 before | Expand all | Expand 10 after Loading... | |
| 633 case SkPath::kInverseWinding_FillType: | 559 case SkPath::kInverseWinding_FillType: |
| 634 return winding == 1; | 560 return winding == 1; |
| 635 case SkPath::kInverseEvenOdd_FillType: | 561 case SkPath::kInverseEvenOdd_FillType: |
| 636 return (winding & 1) == 1; | 562 return (winding & 1) == 1; |
| 637 default: | 563 default: |
| 638 SkASSERT(false); | 564 SkASSERT(false); |
| 639 return false; | 565 return false; |
| 640 } | 566 } |
| 641 } | 567 } |
| 642 | 568 |
| 643 Edge* new_edge(Vertex* prev, Vertex* next, SkChunkAlloc& alloc, Comparator& c) { | 569 Edge* new_edge(TessellatorVertex* prev, TessellatorVertex* next, SkChunkAlloc& a lloc, |
| 570 Comparator& c) { | |
| 644 int winding = c.sweep_lt(prev->fPoint, next->fPoint) ? 1 : -1; | 571 int winding = c.sweep_lt(prev->fPoint, next->fPoint) ? 1 : -1; |
| 645 Vertex* top = winding < 0 ? next : prev; | 572 TessellatorVertex* top = winding < 0 ? next : prev; |
| 646 Vertex* bottom = winding < 0 ? prev : next; | 573 TessellatorVertex* bottom = winding < 0 ? prev : next; |
| 647 return ALLOC_NEW(Edge, (top, bottom, winding), alloc); | 574 return ALLOC_NEW(Edge, (top, bottom, winding), alloc); |
| 648 } | 575 } |
| 649 | 576 |
| 650 void remove_edge(Edge* edge, EdgeList* edges) { | 577 void remove_edge(Edge* edge, EdgeList* edges) { |
| 651 LOG("removing edge %g -> %g\n", edge->fTop->fID, edge->fBottom->fID); | 578 LOG("removing edge %g -> %g\n", edge->fTop->fID, edge->fBottom->fID); |
| 652 SkASSERT(edge->isActive(edges)); | 579 SkASSERT(edge->isActive(edges)); |
| 653 remove<Edge, &Edge::fLeft, &Edge::fRight>(edge, &edges->fHead, &edges->fTail ); | 580 remove<Edge, &Edge::fLeft, &Edge::fRight>(edge, &edges->fHead, &edges->fTail ); |
| 654 } | 581 } |
| 655 | 582 |
| 656 void insert_edge(Edge* edge, Edge* prev, EdgeList* edges) { | 583 void insert_edge(Edge* edge, Edge* prev, EdgeList* edges) { |
| 657 LOG("inserting edge %g -> %g\n", edge->fTop->fID, edge->fBottom->fID); | 584 LOG("inserting edge %g -> %g\n", edge->fTop->fID, edge->fBottom->fID); |
| 658 SkASSERT(!edge->isActive(edges)); | 585 SkASSERT(!edge->isActive(edges)); |
| 659 Edge* next = prev ? prev->fRight : edges->fHead; | 586 Edge* next = prev ? prev->fRight : edges->fHead; |
| 660 insert<Edge, &Edge::fLeft, &Edge::fRight>(edge, prev, next, &edges->fHead, & edges->fTail); | 587 insert<Edge, &Edge::fLeft, &Edge::fRight>(edge, prev, next, &edges->fHead, & edges->fTail); |
| 661 } | 588 } |
| 662 | 589 |
| 663 void find_enclosing_edges(Vertex* v, EdgeList* edges, Edge** left, Edge** right) { | 590 void find_enclosing_edges(TessellatorVertex* v, EdgeList* edges, Edge** left, Ed ge** right) { |
| 664 if (v->fFirstEdgeAbove) { | 591 if (v->fFirstEdgeAbove) { |
| 665 *left = v->fFirstEdgeAbove->fLeft; | 592 *left = v->fFirstEdgeAbove->fLeft; |
| 666 *right = v->fLastEdgeAbove->fRight; | 593 *right = v->fLastEdgeAbove->fRight; |
| 667 return; | 594 return; |
| 668 } | 595 } |
| 669 Edge* next = nullptr; | 596 Edge* next = nullptr; |
| 670 Edge* prev; | 597 Edge* prev; |
| 671 for (prev = edges->fTail; prev != nullptr; prev = prev->fLeft) { | 598 for (prev = edges->fTail; prev != nullptr; prev = prev->fLeft) { |
| 672 if (prev->isLeftOf(v)) { | 599 if (prev->isLeftOf(v)) { |
| 673 break; | 600 break; |
| (...skipping 30 matching lines...) Expand all Loading... | |
| 704 remove_edge(edge, activeEdges); | 631 remove_edge(edge, activeEdges); |
| 705 } | 632 } |
| 706 } else if (edge->fTop->fProcessed && !edge->fBottom->fProcessed) { | 633 } else if (edge->fTop->fProcessed && !edge->fBottom->fProcessed) { |
| 707 Edge* left; | 634 Edge* left; |
| 708 Edge* right; | 635 Edge* right; |
| 709 find_enclosing_edges(edge, activeEdges, c, &left, &right); | 636 find_enclosing_edges(edge, activeEdges, c, &left, &right); |
| 710 insert_edge(edge, left, activeEdges); | 637 insert_edge(edge, left, activeEdges); |
| 711 } | 638 } |
| 712 } | 639 } |
| 713 | 640 |
| 714 void insert_edge_above(Edge* edge, Vertex* v, Comparator& c) { | 641 void insert_edge_above(Edge* edge, TessellatorVertex* v, Comparator& c) { |
| 715 if (edge->fTop->fPoint == edge->fBottom->fPoint || | 642 if (edge->fTop->fPoint == edge->fBottom->fPoint || |
| 716 c.sweep_gt(edge->fTop->fPoint, edge->fBottom->fPoint)) { | 643 c.sweep_gt(edge->fTop->fPoint, edge->fBottom->fPoint)) { |
| 717 return; | 644 return; |
| 718 } | 645 } |
| 719 LOG("insert edge (%g -> %g) above vertex %g\n", edge->fTop->fID, edge->fBott om->fID, v->fID); | 646 LOG("insert edge (%g -> %g) above vertex %g\n", edge->fTop->fID, edge->fBott om->fID, v->fID); |
| 720 Edge* prev = nullptr; | 647 Edge* prev = nullptr; |
| 721 Edge* next; | 648 Edge* next; |
| 722 for (next = v->fFirstEdgeAbove; next; next = next->fNextEdgeAbove) { | 649 for (next = v->fFirstEdgeAbove; next; next = next->fNextEdgeAbove) { |
| 723 if (next->isRightOf(edge->fTop)) { | 650 if (next->isRightOf(edge->fTop)) { |
| 724 break; | 651 break; |
| 725 } | 652 } |
| 726 prev = next; | 653 prev = next; |
| 727 } | 654 } |
| 728 insert<Edge, &Edge::fPrevEdgeAbove, &Edge::fNextEdgeAbove>( | 655 insert<Edge, &Edge::fPrevEdgeAbove, &Edge::fNextEdgeAbove>( |
| 729 edge, prev, next, &v->fFirstEdgeAbove, &v->fLastEdgeAbove); | 656 edge, prev, next, &v->fFirstEdgeAbove, &v->fLastEdgeAbove); |
| 730 } | 657 } |
| 731 | 658 |
| 732 void insert_edge_below(Edge* edge, Vertex* v, Comparator& c) { | 659 void insert_edge_below(Edge* edge, TessellatorVertex* v, Comparator& c) { |
| 733 if (edge->fTop->fPoint == edge->fBottom->fPoint || | 660 if (edge->fTop->fPoint == edge->fBottom->fPoint || |
| 734 c.sweep_gt(edge->fTop->fPoint, edge->fBottom->fPoint)) { | 661 c.sweep_gt(edge->fTop->fPoint, edge->fBottom->fPoint)) { |
| 735 return; | 662 return; |
| 736 } | 663 } |
| 737 LOG("insert edge (%g -> %g) below vertex %g\n", edge->fTop->fID, edge->fBott om->fID, v->fID); | 664 LOG("insert edge (%g -> %g) below vertex %g\n", edge->fTop->fID, edge->fBott om->fID, v->fID); |
| 738 Edge* prev = nullptr; | 665 Edge* prev = nullptr; |
| 739 Edge* next; | 666 Edge* next; |
| 740 for (next = v->fFirstEdgeBelow; next; next = next->fNextEdgeBelow) { | 667 for (next = v->fFirstEdgeBelow; next; next = next->fNextEdgeBelow) { |
| 741 if (next->isRightOf(edge->fBottom)) { | 668 if (next->isRightOf(edge->fBottom)) { |
| 742 break; | 669 break; |
| (...skipping 25 matching lines...) Expand all Loading... | |
| 768 LOG("erasing edge (%g -> %g)\n", edge->fTop->fID, edge->fBottom->fID); | 695 LOG("erasing edge (%g -> %g)\n", edge->fTop->fID, edge->fBottom->fID); |
| 769 remove_edge_above(edge); | 696 remove_edge_above(edge); |
| 770 remove_edge_below(edge); | 697 remove_edge_below(edge); |
| 771 if (edge->isActive(edges)) { | 698 if (edge->isActive(edges)) { |
| 772 remove_edge(edge, edges); | 699 remove_edge(edge, edges); |
| 773 } | 700 } |
| 774 } | 701 } |
| 775 | 702 |
| 776 void merge_collinear_edges(Edge* edge, EdgeList* activeEdges, Comparator& c); | 703 void merge_collinear_edges(Edge* edge, EdgeList* activeEdges, Comparator& c); |
| 777 | 704 |
| 778 void set_top(Edge* edge, Vertex* v, EdgeList* activeEdges, Comparator& c) { | 705 void set_top(Edge* edge, TessellatorVertex* v, EdgeList* activeEdges, Comparator & c) { |
| 779 remove_edge_below(edge); | 706 remove_edge_below(edge); |
| 780 edge->fTop = v; | 707 edge->fTop = v; |
| 781 edge->recompute(); | 708 edge->recompute(); |
| 782 insert_edge_below(edge, v, c); | 709 insert_edge_below(edge, v, c); |
| 783 fix_active_state(edge, activeEdges, c); | 710 fix_active_state(edge, activeEdges, c); |
| 784 merge_collinear_edges(edge, activeEdges, c); | 711 merge_collinear_edges(edge, activeEdges, c); |
| 785 } | 712 } |
| 786 | 713 |
| 787 void set_bottom(Edge* edge, Vertex* v, EdgeList* activeEdges, Comparator& c) { | 714 void set_bottom(Edge* edge, TessellatorVertex* v, EdgeList* activeEdges, Compara tor& c) { |
| 788 remove_edge_above(edge); | 715 remove_edge_above(edge); |
| 789 edge->fBottom = v; | 716 edge->fBottom = v; |
| 790 edge->recompute(); | 717 edge->recompute(); |
| 791 insert_edge_above(edge, v, c); | 718 insert_edge_above(edge, v, c); |
| 792 fix_active_state(edge, activeEdges, c); | 719 fix_active_state(edge, activeEdges, c); |
| 793 merge_collinear_edges(edge, activeEdges, c); | 720 merge_collinear_edges(edge, activeEdges, c); |
| 794 } | 721 } |
| 795 | 722 |
| 796 void merge_edges_above(Edge* edge, Edge* other, EdgeList* activeEdges, Comparato r& c) { | 723 void merge_edges_above(Edge* edge, Edge* other, EdgeList* activeEdges, Comparato r& c) { |
| 797 if (coincident(edge->fTop->fPoint, other->fTop->fPoint)) { | 724 if (coincident(edge->fTop->fPoint, other->fTop->fPoint)) { |
| (...skipping 45 matching lines...) Expand 10 before | Expand all | Expand 10 after Loading... | |
| 843 } | 770 } |
| 844 if (edge->fPrevEdgeBelow && (edge->fBottom == edge->fPrevEdgeBelow->fBottom || | 771 if (edge->fPrevEdgeBelow && (edge->fBottom == edge->fPrevEdgeBelow->fBottom || |
| 845 !edge->fPrevEdgeBelow->isLeftOf(edge->fBottom)) ) { | 772 !edge->fPrevEdgeBelow->isLeftOf(edge->fBottom)) ) { |
| 846 merge_edges_below(edge, edge->fPrevEdgeBelow, activeEdges, c); | 773 merge_edges_below(edge, edge->fPrevEdgeBelow, activeEdges, c); |
| 847 } else if (edge->fNextEdgeBelow && (edge->fBottom == edge->fNextEdgeBelow->f Bottom || | 774 } else if (edge->fNextEdgeBelow && (edge->fBottom == edge->fNextEdgeBelow->f Bottom || |
| 848 !edge->isLeftOf(edge->fNextEdgeBelow->fB ottom))) { | 775 !edge->isLeftOf(edge->fNextEdgeBelow->fB ottom))) { |
| 849 merge_edges_below(edge, edge->fNextEdgeBelow, activeEdges, c); | 776 merge_edges_below(edge, edge->fNextEdgeBelow, activeEdges, c); |
| 850 } | 777 } |
| 851 } | 778 } |
| 852 | 779 |
| 853 void split_edge(Edge* edge, Vertex* v, EdgeList* activeEdges, Comparator& c, SkC hunkAlloc& alloc); | 780 void split_edge(Edge* edge, TessellatorVertex* v, EdgeList* activeEdges, Compara tor& c, |
| 781 SkChunkAlloc& alloc); | |
| 854 | 782 |
| 855 void cleanup_active_edges(Edge* edge, EdgeList* activeEdges, Comparator& c, SkCh unkAlloc& alloc) { | 783 void cleanup_active_edges(Edge* edge, EdgeList* activeEdges, Comparator& c, SkCh unkAlloc& alloc) { |
| 856 Vertex* top = edge->fTop; | 784 TessellatorVertex* top = edge->fTop; |
| 857 Vertex* bottom = edge->fBottom; | 785 TessellatorVertex* bottom = edge->fBottom; |
| 858 if (edge->fLeft) { | 786 if (edge->fLeft) { |
| 859 Vertex* leftTop = edge->fLeft->fTop; | 787 TessellatorVertex* leftTop = edge->fLeft->fTop; |
| 860 Vertex* leftBottom = edge->fLeft->fBottom; | 788 TessellatorVertex* leftBottom = edge->fLeft->fBottom; |
| 861 if (c.sweep_gt(top->fPoint, leftTop->fPoint) && !edge->fLeft->isLeftOf(t op)) { | 789 if (c.sweep_gt(top->fPoint, leftTop->fPoint) && !edge->fLeft->isLeftOf(t op)) { |
| 862 split_edge(edge->fLeft, edge->fTop, activeEdges, c, alloc); | 790 split_edge(edge->fLeft, edge->fTop, activeEdges, c, alloc); |
| 863 } else if (c.sweep_gt(leftTop->fPoint, top->fPoint) && !edge->isRightOf( leftTop)) { | 791 } else if (c.sweep_gt(leftTop->fPoint, top->fPoint) && !edge->isRightOf( leftTop)) { |
| 864 split_edge(edge, leftTop, activeEdges, c, alloc); | 792 split_edge(edge, leftTop, activeEdges, c, alloc); |
| 865 } else if (c.sweep_lt(bottom->fPoint, leftBottom->fPoint) && | 793 } else if (c.sweep_lt(bottom->fPoint, leftBottom->fPoint) && |
| 866 !edge->fLeft->isLeftOf(bottom)) { | 794 !edge->fLeft->isLeftOf(bottom)) { |
| 867 split_edge(edge->fLeft, bottom, activeEdges, c, alloc); | 795 split_edge(edge->fLeft, bottom, activeEdges, c, alloc); |
| 868 } else if (c.sweep_lt(leftBottom->fPoint, bottom->fPoint) && !edge->isRi ghtOf(leftBottom)) { | 796 } else if (c.sweep_lt(leftBottom->fPoint, bottom->fPoint) && !edge->isRi ghtOf(leftBottom)) { |
| 869 split_edge(edge, leftBottom, activeEdges, c, alloc); | 797 split_edge(edge, leftBottom, activeEdges, c, alloc); |
| 870 } | 798 } |
| 871 } | 799 } |
| 872 if (edge->fRight) { | 800 if (edge->fRight) { |
| 873 Vertex* rightTop = edge->fRight->fTop; | 801 TessellatorVertex* rightTop = edge->fRight->fTop; |
| 874 Vertex* rightBottom = edge->fRight->fBottom; | 802 TessellatorVertex* rightBottom = edge->fRight->fBottom; |
| 875 if (c.sweep_gt(top->fPoint, rightTop->fPoint) && !edge->fRight->isRightO f(top)) { | 803 if (c.sweep_gt(top->fPoint, rightTop->fPoint) && !edge->fRight->isRightO f(top)) { |
| 876 split_edge(edge->fRight, top, activeEdges, c, alloc); | 804 split_edge(edge->fRight, top, activeEdges, c, alloc); |
| 877 } else if (c.sweep_gt(rightTop->fPoint, top->fPoint) && !edge->isLeftOf( rightTop)) { | 805 } else if (c.sweep_gt(rightTop->fPoint, top->fPoint) && !edge->isLeftOf( rightTop)) { |
| 878 split_edge(edge, rightTop, activeEdges, c, alloc); | 806 split_edge(edge, rightTop, activeEdges, c, alloc); |
| 879 } else if (c.sweep_lt(bottom->fPoint, rightBottom->fPoint) && | 807 } else if (c.sweep_lt(bottom->fPoint, rightBottom->fPoint) && |
| 880 !edge->fRight->isRightOf(bottom)) { | 808 !edge->fRight->isRightOf(bottom)) { |
| 881 split_edge(edge->fRight, bottom, activeEdges, c, alloc); | 809 split_edge(edge->fRight, bottom, activeEdges, c, alloc); |
| 882 } else if (c.sweep_lt(rightBottom->fPoint, bottom->fPoint) && | 810 } else if (c.sweep_lt(rightBottom->fPoint, bottom->fPoint) && |
| 883 !edge->isLeftOf(rightBottom)) { | 811 !edge->isLeftOf(rightBottom)) { |
| 884 split_edge(edge, rightBottom, activeEdges, c, alloc); | 812 split_edge(edge, rightBottom, activeEdges, c, alloc); |
| 885 } | 813 } |
| 886 } | 814 } |
| 887 } | 815 } |
| 888 | 816 |
| 889 void split_edge(Edge* edge, Vertex* v, EdgeList* activeEdges, Comparator& c, SkC hunkAlloc& alloc) { | 817 void split_edge(Edge* edge, TessellatorVertex* v, EdgeList* activeEdges, Compara tor& c, |
| 818 SkChunkAlloc& alloc) { | |
| 890 LOG("splitting edge (%g -> %g) at vertex %g (%g, %g)\n", | 819 LOG("splitting edge (%g -> %g) at vertex %g (%g, %g)\n", |
| 891 edge->fTop->fID, edge->fBottom->fID, | 820 edge->fTop->fID, edge->fBottom->fID, |
| 892 v->fID, v->fPoint.fX, v->fPoint.fY); | 821 v->fID, v->fPoint.fX, v->fPoint.fY); |
| 893 if (c.sweep_lt(v->fPoint, edge->fTop->fPoint)) { | 822 if (c.sweep_lt(v->fPoint, edge->fTop->fPoint)) { |
| 894 set_top(edge, v, activeEdges, c); | 823 set_top(edge, v, activeEdges, c); |
| 895 } else if (c.sweep_gt(v->fPoint, edge->fBottom->fPoint)) { | 824 } else if (c.sweep_gt(v->fPoint, edge->fBottom->fPoint)) { |
| 896 set_bottom(edge, v, activeEdges, c); | 825 set_bottom(edge, v, activeEdges, c); |
| 897 } else { | 826 } else { |
| 898 Edge* newEdge = ALLOC_NEW(Edge, (v, edge->fBottom, edge->fWinding), allo c); | 827 Edge* newEdge = ALLOC_NEW(Edge, (v, edge->fBottom, edge->fWinding), allo c); |
| 899 insert_edge_below(newEdge, v, c); | 828 insert_edge_below(newEdge, v, c); |
| 900 insert_edge_above(newEdge, edge->fBottom, c); | 829 insert_edge_above(newEdge, edge->fBottom, c); |
| 901 set_bottom(edge, v, activeEdges, c); | 830 set_bottom(edge, v, activeEdges, c); |
| 902 cleanup_active_edges(edge, activeEdges, c, alloc); | 831 cleanup_active_edges(edge, activeEdges, c, alloc); |
| 903 fix_active_state(newEdge, activeEdges, c); | 832 fix_active_state(newEdge, activeEdges, c); |
| 904 merge_collinear_edges(newEdge, activeEdges, c); | 833 merge_collinear_edges(newEdge, activeEdges, c); |
| 905 } | 834 } |
| 906 } | 835 } |
| 907 | 836 |
| 908 void merge_vertices(Vertex* src, Vertex* dst, Vertex** head, Comparator& c, SkCh unkAlloc& alloc) { | 837 void merge_vertices(TessellatorVertex* src, TessellatorVertex* dst, TessellatorV ertex** head, |
| 838 Comparator& c, SkChunkAlloc& alloc) { | |
| 909 LOG("found coincident verts at %g, %g; merging %g into %g\n", src->fPoint.fX , src->fPoint.fY, | 839 LOG("found coincident verts at %g, %g; merging %g into %g\n", src->fPoint.fX , src->fPoint.fY, |
| 910 src->fID, dst->fID); | 840 src->fID, dst->fID); |
| 911 for (Edge* edge = src->fFirstEdgeAbove; edge;) { | 841 for (Edge* edge = src->fFirstEdgeAbove; edge;) { |
| 912 Edge* next = edge->fNextEdgeAbove; | 842 Edge* next = edge->fNextEdgeAbove; |
| 913 set_bottom(edge, dst, nullptr, c); | 843 set_bottom(edge, dst, nullptr, c); |
| 914 edge = next; | 844 edge = next; |
| 915 } | 845 } |
| 916 for (Edge* edge = src->fFirstEdgeBelow; edge;) { | 846 for (Edge* edge = src->fFirstEdgeBelow; edge;) { |
| 917 Edge* next = edge->fNextEdgeBelow; | 847 Edge* next = edge->fNextEdgeBelow; |
| 918 set_top(edge, dst, nullptr, c); | 848 set_top(edge, dst, nullptr, c); |
| 919 edge = next; | 849 edge = next; |
| 920 } | 850 } |
| 921 remove<Vertex, &Vertex::fPrev, &Vertex::fNext>(src, head, nullptr); | 851 remove<TessellatorVertex, &TessellatorVertex::fPrev, &TessellatorVertex::fNe xt>(src, head, |
| 852 nullptr); | |
| 922 } | 853 } |
| 923 | 854 |
| 924 Vertex* check_for_intersection(Edge* edge, Edge* other, EdgeList* activeEdges, C omparator& c, | 855 TessellatorVertex* check_for_intersection(Edge* edge, Edge* other, EdgeList* act iveEdges, |
| 925 SkChunkAlloc& alloc) { | 856 Comparator& c, SkChunkAlloc& alloc) { |
| 926 SkPoint p; | 857 SkPoint p; |
| 927 if (!edge || !other) { | 858 if (!edge || !other) { |
| 928 return nullptr; | 859 return nullptr; |
| 929 } | 860 } |
| 930 if (edge->intersect(*other, &p)) { | 861 if (edge->intersect(*other, &p)) { |
| 931 Vertex* v; | 862 TessellatorVertex* v; |
| 932 LOG("found intersection, pt is %g, %g\n", p.fX, p.fY); | 863 LOG("found intersection, pt is %g, %g\n", p.fX, p.fY); |
| 933 if (p == edge->fTop->fPoint || c.sweep_lt(p, edge->fTop->fPoint)) { | 864 if (p == edge->fTop->fPoint || c.sweep_lt(p, edge->fTop->fPoint)) { |
| 934 split_edge(other, edge->fTop, activeEdges, c, alloc); | 865 split_edge(other, edge->fTop, activeEdges, c, alloc); |
| 935 v = edge->fTop; | 866 v = edge->fTop; |
| 936 } else if (p == edge->fBottom->fPoint || c.sweep_gt(p, edge->fBottom->fP oint)) { | 867 } else if (p == edge->fBottom->fPoint || c.sweep_gt(p, edge->fBottom->fP oint)) { |
| 937 split_edge(other, edge->fBottom, activeEdges, c, alloc); | 868 split_edge(other, edge->fBottom, activeEdges, c, alloc); |
| 938 v = edge->fBottom; | 869 v = edge->fBottom; |
| 939 } else if (p == other->fTop->fPoint || c.sweep_lt(p, other->fTop->fPoint )) { | 870 } else if (p == other->fTop->fPoint || c.sweep_lt(p, other->fTop->fPoint )) { |
| 940 split_edge(edge, other->fTop, activeEdges, c, alloc); | 871 split_edge(edge, other->fTop, activeEdges, c, alloc); |
| 941 v = other->fTop; | 872 v = other->fTop; |
| 942 } else if (p == other->fBottom->fPoint || c.sweep_gt(p, other->fBottom-> fPoint)) { | 873 } else if (p == other->fBottom->fPoint || c.sweep_gt(p, other->fBottom-> fPoint)) { |
| 943 split_edge(edge, other->fBottom, activeEdges, c, alloc); | 874 split_edge(edge, other->fBottom, activeEdges, c, alloc); |
| 944 v = other->fBottom; | 875 v = other->fBottom; |
| 945 } else { | 876 } else { |
| 946 Vertex* nextV = edge->fTop; | 877 TessellatorVertex* nextV = edge->fTop; |
| 947 while (c.sweep_lt(p, nextV->fPoint)) { | 878 while (c.sweep_lt(p, nextV->fPoint)) { |
| 948 nextV = nextV->fPrev; | 879 nextV = nextV->fPrev; |
| 949 } | 880 } |
| 950 while (c.sweep_lt(nextV->fPoint, p)) { | 881 while (c.sweep_lt(nextV->fPoint, p)) { |
| 951 nextV = nextV->fNext; | 882 nextV = nextV->fNext; |
| 952 } | 883 } |
| 953 Vertex* prevV = nextV->fPrev; | 884 TessellatorVertex* prevV = nextV->fPrev; |
| 954 if (coincident(prevV->fPoint, p)) { | 885 if (coincident(prevV->fPoint, p)) { |
| 955 v = prevV; | 886 v = prevV; |
| 956 } else if (coincident(nextV->fPoint, p)) { | 887 } else if (coincident(nextV->fPoint, p)) { |
| 957 v = nextV; | 888 v = nextV; |
| 958 } else { | 889 } else { |
| 959 v = ALLOC_NEW(Vertex, (p), alloc); | 890 v = ALLOC_NEW(TessellatorVertex, (p), alloc); |
| 960 LOG("inserting between %g (%g, %g) and %g (%g, %g)\n", | 891 LOG("inserting between %g (%g, %g) and %g (%g, %g)\n", |
| 961 prevV->fID, prevV->fPoint.fX, prevV->fPoint.fY, | 892 prevV->fID, prevV->fPoint.fX, prevV->fPoint.fY, |
| 962 nextV->fID, nextV->fPoint.fX, nextV->fPoint.fY); | 893 nextV->fID, nextV->fPoint.fX, nextV->fPoint.fY); |
| 963 #if LOGGING_ENABLED | 894 #if TESSELLATOR_LOGGING_ENABLED |
| 964 v->fID = (nextV->fID + prevV->fID) * 0.5f; | 895 v->fID = (nextV->fID + prevV->fID) * 0.5f; |
| 965 #endif | 896 #endif |
| 966 v->fPrev = prevV; | 897 v->fPrev = prevV; |
| 967 v->fNext = nextV; | 898 v->fNext = nextV; |
| 968 prevV->fNext = v; | 899 prevV->fNext = v; |
| 969 nextV->fPrev = v; | 900 nextV->fPrev = v; |
| 970 } | 901 } |
| 971 split_edge(edge, v, activeEdges, c, alloc); | 902 split_edge(edge, v, activeEdges, c, alloc); |
| 972 split_edge(other, v, activeEdges, c, alloc); | 903 split_edge(other, v, activeEdges, c, alloc); |
| 973 } | 904 } |
| 974 return v; | 905 return v; |
| 975 } | 906 } |
| 976 return nullptr; | 907 return nullptr; |
| 977 } | 908 } |
| 978 | 909 |
| 979 void sanitize_contours(Vertex** contours, int contourCnt) { | 910 void sanitize_contours(TessellatorVertex** contours, int contourCnt) { |
| 980 for (int i = 0; i < contourCnt; ++i) { | 911 for (int i = 0; i < contourCnt; ++i) { |
| 981 SkASSERT(contours[i]); | 912 SkASSERT(contours[i]); |
| 982 for (Vertex* v = contours[i];;) { | 913 for (TessellatorVertex* v = contours[i];;) { |
| 983 if (coincident(v->fPrev->fPoint, v->fPoint)) { | 914 if (coincident(v->fPrev->fPoint, v->fPoint)) { |
| 984 LOG("vertex %g,%g coincident; removing\n", v->fPoint.fX, v->fPoi nt.fY); | 915 LOG("vertex %g,%g coincident; removing\n", v->fPoint.fX, v->fPoi nt.fY); |
| 985 if (v->fPrev == v) { | 916 if (v->fPrev == v) { |
| 986 contours[i] = nullptr; | 917 contours[i] = nullptr; |
| 987 break; | 918 break; |
| 988 } | 919 } |
| 989 v->fPrev->fNext = v->fNext; | 920 v->fPrev->fNext = v->fNext; |
| 990 v->fNext->fPrev = v->fPrev; | 921 v->fNext->fPrev = v->fPrev; |
| 991 if (contours[i] == v) { | 922 if (contours[i] == v) { |
| 992 contours[i] = v->fNext; | 923 contours[i] = v->fNext; |
| 993 } | 924 } |
| 994 v = v->fPrev; | 925 v = v->fPrev; |
| 995 } else { | 926 } else { |
| 996 v = v->fNext; | 927 v = v->fNext; |
| 997 if (v == contours[i]) break; | 928 if (v == contours[i]) break; |
| 998 } | 929 } |
| 999 } | 930 } |
| 1000 } | 931 } |
| 1001 } | 932 } |
| 1002 | 933 |
| 1003 void merge_coincident_vertices(Vertex** vertices, Comparator& c, SkChunkAlloc& a lloc) { | 934 void merge_coincident_vertices(TessellatorVertex** vertices, Comparator& c, SkCh unkAlloc& alloc) { |
| 1004 for (Vertex* v = (*vertices)->fNext; v != nullptr; v = v->fNext) { | 935 for (TessellatorVertex* v = (*vertices)->fNext; v != nullptr; v = v->fNext) { |
| 1005 if (c.sweep_lt(v->fPoint, v->fPrev->fPoint)) { | 936 if (c.sweep_lt(v->fPoint, v->fPrev->fPoint)) { |
| 1006 v->fPoint = v->fPrev->fPoint; | 937 v->fPoint = v->fPrev->fPoint; |
| 1007 } | 938 } |
| 1008 if (coincident(v->fPrev->fPoint, v->fPoint)) { | 939 if (coincident(v->fPrev->fPoint, v->fPoint)) { |
| 1009 merge_vertices(v->fPrev, v, vertices, c, alloc); | 940 merge_vertices(v->fPrev, v, vertices, c, alloc); |
| 1010 } | 941 } |
| 1011 } | 942 } |
| 1012 } | 943 } |
| 1013 | 944 |
| 1014 // Stage 2: convert the contours to a mesh of edges connecting the vertices. | 945 // Stage 2: convert the contours to a mesh of edges connecting the vertices. |
| 1015 | 946 |
| 1016 Vertex* build_edges(Vertex** contours, int contourCnt, Comparator& c, SkChunkAll oc& alloc) { | 947 TessellatorVertex* build_edges(TessellatorVertex** contours, int contourCnt, Com parator& c, |
| 1017 Vertex* vertices = nullptr; | 948 SkChunkAlloc& alloc) { |
| 1018 Vertex* prev = nullptr; | 949 TessellatorVertex* vertices = nullptr; |
| 950 TessellatorVertex* prev = nullptr; | |
| 1019 for (int i = 0; i < contourCnt; ++i) { | 951 for (int i = 0; i < contourCnt; ++i) { |
| 1020 for (Vertex* v = contours[i]; v != nullptr;) { | 952 for (TessellatorVertex* v = contours[i]; v != nullptr;) { |
| 1021 Vertex* vNext = v->fNext; | 953 TessellatorVertex* vNext = v->fNext; |
| 1022 Edge* edge = new_edge(v->fPrev, v, alloc, c); | 954 Edge* edge = new_edge(v->fPrev, v, alloc, c); |
| 1023 if (edge->fWinding > 0) { | 955 if (edge->fWinding > 0) { |
| 1024 insert_edge_below(edge, v->fPrev, c); | 956 insert_edge_below(edge, v->fPrev, c); |
| 1025 insert_edge_above(edge, v, c); | 957 insert_edge_above(edge, v, c); |
| 1026 } else { | 958 } else { |
| 1027 insert_edge_below(edge, v, c); | 959 insert_edge_below(edge, v, c); |
| 1028 insert_edge_above(edge, v->fPrev, c); | 960 insert_edge_above(edge, v->fPrev, c); |
| 1029 } | 961 } |
| 1030 merge_collinear_edges(edge, nullptr, c); | 962 merge_collinear_edges(edge, nullptr, c); |
| 1031 if (prev) { | 963 if (prev) { |
| 1032 prev->fNext = v; | 964 prev->fNext = v; |
| 1033 v->fPrev = prev; | 965 v->fPrev = prev; |
| 1034 } else { | 966 } else { |
| 1035 vertices = v; | 967 vertices = v; |
| 1036 } | 968 } |
| 1037 prev = v; | 969 prev = v; |
| 1038 v = vNext; | 970 v = vNext; |
| 1039 if (v == contours[i]) break; | 971 if (v == contours[i]) break; |
| 1040 } | 972 } |
| 1041 } | 973 } |
| 1042 if (prev) { | 974 if (prev) { |
| 1043 prev->fNext = vertices->fPrev = nullptr; | 975 prev->fNext = vertices->fPrev = nullptr; |
| 1044 } | 976 } |
| 1045 return vertices; | 977 return vertices; |
| 1046 } | 978 } |
| 1047 | 979 |
| 1048 // Stage 3: sort the vertices by increasing sweep direction. | 980 // Stage 3: sort the vertices by increasing sweep direction. |
| 1049 | 981 |
| 1050 Vertex* sorted_merge(Vertex* a, Vertex* b, Comparator& c); | 982 TessellatorVertex* sorted_merge(TessellatorVertex* a, TessellatorVertex* b, Comp arator& c); |
| 1051 | 983 |
| 1052 void front_back_split(Vertex* v, Vertex** pFront, Vertex** pBack) { | 984 void front_back_split(TessellatorVertex* v, TessellatorVertex** pFront, Tessella torVertex** pBack) { |
| 1053 Vertex* fast; | 985 TessellatorVertex* fast; |
| 1054 Vertex* slow; | 986 TessellatorVertex* slow; |
| 1055 if (!v || !v->fNext) { | 987 if (!v || !v->fNext) { |
| 1056 *pFront = v; | 988 *pFront = v; |
| 1057 *pBack = nullptr; | 989 *pBack = nullptr; |
| 1058 } else { | 990 } else { |
| 1059 slow = v; | 991 slow = v; |
| 1060 fast = v->fNext; | 992 fast = v->fNext; |
| 1061 | 993 |
| 1062 while (fast != nullptr) { | 994 while (fast != nullptr) { |
| 1063 fast = fast->fNext; | 995 fast = fast->fNext; |
| 1064 if (fast != nullptr) { | 996 if (fast != nullptr) { |
| 1065 slow = slow->fNext; | 997 slow = slow->fNext; |
| 1066 fast = fast->fNext; | 998 fast = fast->fNext; |
| 1067 } | 999 } |
| 1068 } | 1000 } |
| 1069 | 1001 |
| 1070 *pFront = v; | 1002 *pFront = v; |
| 1071 *pBack = slow->fNext; | 1003 *pBack = slow->fNext; |
| 1072 slow->fNext->fPrev = nullptr; | 1004 slow->fNext->fPrev = nullptr; |
| 1073 slow->fNext = nullptr; | 1005 slow->fNext = nullptr; |
| 1074 } | 1006 } |
| 1075 } | 1007 } |
| 1076 | 1008 |
| 1077 void merge_sort(Vertex** head, Comparator& c) { | 1009 void merge_sort(TessellatorVertex** head, Comparator& c) { |
| 1078 if (!*head || !(*head)->fNext) { | 1010 if (!*head || !(*head)->fNext) { |
| 1079 return; | 1011 return; |
| 1080 } | 1012 } |
| 1081 | 1013 |
| 1082 Vertex* a; | 1014 TessellatorVertex* a; |
| 1083 Vertex* b; | 1015 TessellatorVertex* b; |
| 1084 front_back_split(*head, &a, &b); | 1016 front_back_split(*head, &a, &b); |
| 1085 | 1017 |
| 1086 merge_sort(&a, c); | 1018 merge_sort(&a, c); |
| 1087 merge_sort(&b, c); | 1019 merge_sort(&b, c); |
| 1088 | 1020 |
| 1089 *head = sorted_merge(a, b, c); | 1021 *head = sorted_merge(a, b, c); |
| 1090 } | 1022 } |
| 1091 | 1023 |
| 1092 inline void append_vertex(Vertex* v, Vertex** head, Vertex** tail) { | 1024 inline void append_vertex(TessellatorVertex* v, TessellatorVertex** head, |
| 1093 insert<Vertex, &Vertex::fPrev, &Vertex::fNext>(v, *tail, nullptr, head, tail ); | 1025 TessellatorVertex** tail) { |
| 1026 insert<TessellatorVertex, &TessellatorVertex::fPrev, &TessellatorVertex::fNe xt>(v, *tail, | |
| 1027 nullptr, head, | |
| 1028 tail); | |
| 1094 } | 1029 } |
| 1095 | 1030 |
| 1096 inline void append_vertex_list(Vertex* v, Vertex** head, Vertex** tail) { | 1031 inline void append_vertex_list(TessellatorVertex* v, TessellatorVertex** head, |
| 1097 insert<Vertex, &Vertex::fPrev, &Vertex::fNext>(v, *tail, v->fNext, head, tai l); | 1032 TessellatorVertex** tail) { |
| 1033 insert<TessellatorVertex, &TessellatorVertex::fPrev, &TessellatorVertex::fNe xt>(v, *tail, | |
| 1034 v->fNext, head, | |
| 1035 tail); | |
| 1098 } | 1036 } |
| 1099 | 1037 |
| 1100 Vertex* sorted_merge(Vertex* a, Vertex* b, Comparator& c) { | 1038 TessellatorVertex* sorted_merge(TessellatorVertex* a, TessellatorVertex* b, Comp arator& c) { |
| 1101 Vertex* head = nullptr; | 1039 TessellatorVertex* head = nullptr; |
| 1102 Vertex* tail = nullptr; | 1040 TessellatorVertex* tail = nullptr; |
| 1103 | 1041 |
| 1104 while (a && b) { | 1042 while (a && b) { |
| 1105 if (c.sweep_lt(a->fPoint, b->fPoint)) { | 1043 if (c.sweep_lt(a->fPoint, b->fPoint)) { |
| 1106 Vertex* next = a->fNext; | 1044 TessellatorVertex* next = a->fNext; |
| 1107 append_vertex(a, &head, &tail); | 1045 append_vertex(a, &head, &tail); |
| 1108 a = next; | 1046 a = next; |
| 1109 } else { | 1047 } else { |
| 1110 Vertex* next = b->fNext; | 1048 TessellatorVertex* next = b->fNext; |
| 1111 append_vertex(b, &head, &tail); | 1049 append_vertex(b, &head, &tail); |
| 1112 b = next; | 1050 b = next; |
| 1113 } | 1051 } |
| 1114 } | 1052 } |
| 1115 if (a) { | 1053 if (a) { |
| 1116 append_vertex_list(a, &head, &tail); | 1054 append_vertex_list(a, &head, &tail); |
| 1117 } | 1055 } |
| 1118 if (b) { | 1056 if (b) { |
| 1119 append_vertex_list(b, &head, &tail); | 1057 append_vertex_list(b, &head, &tail); |
| 1120 } | 1058 } |
| 1121 return head; | 1059 return head; |
| 1122 } | 1060 } |
| 1123 | 1061 |
| 1124 // Stage 4: Simplify the mesh by inserting new vertices at intersecting edges. | 1062 // Stage 4: Simplify the mesh by inserting new vertices at intersecting edges. |
| 1125 | 1063 |
| 1126 void simplify(Vertex* vertices, Comparator& c, SkChunkAlloc& alloc) { | 1064 void simplify(TessellatorVertex* vertices, Comparator& c, SkChunkAlloc& alloc) { |
| 1127 LOG("simplifying complex polygons\n"); | 1065 LOG("simplifying complex polygons\n"); |
| 1128 EdgeList activeEdges; | 1066 EdgeList activeEdges; |
| 1129 for (Vertex* v = vertices; v != nullptr; v = v->fNext) { | 1067 for (TessellatorVertex* v = vertices; v != nullptr; v = v->fNext) { |
| 1130 if (!v->fFirstEdgeAbove && !v->fFirstEdgeBelow) { | 1068 if (!v->fFirstEdgeAbove && !v->fFirstEdgeBelow) { |
| 1131 continue; | 1069 continue; |
| 1132 } | 1070 } |
| 1133 #if LOGGING_ENABLED | 1071 #if TESSELLATOR_LOGGING_ENABLED |
| 1134 LOG("\nvertex %g: (%g,%g)\n", v->fID, v->fPoint.fX, v->fPoint.fY); | 1072 LOG("\nvertex %g: (%g,%g)\n", v->fID, v->fPoint.fX, v->fPoint.fY); |
| 1135 #endif | 1073 #endif |
| 1136 Edge* leftEnclosingEdge = nullptr; | 1074 Edge* leftEnclosingEdge = nullptr; |
| 1137 Edge* rightEnclosingEdge = nullptr; | 1075 Edge* rightEnclosingEdge = nullptr; |
| 1138 bool restartChecks; | 1076 bool restartChecks; |
| 1139 do { | 1077 do { |
| 1140 restartChecks = false; | 1078 restartChecks = false; |
| 1141 find_enclosing_edges(v, &activeEdges, &leftEnclosingEdge, &rightEncl osingEdge); | 1079 find_enclosing_edges(v, &activeEdges, &leftEnclosingEdge, &rightEncl osingEdge); |
| 1142 if (v->fFirstEdgeBelow) { | 1080 if (v->fFirstEdgeBelow) { |
| 1143 for (Edge* edge = v->fFirstEdgeBelow; edge != nullptr; edge = ed ge->fNextEdgeBelow) { | 1081 for (Edge* edge = v->fFirstEdgeBelow; edge != nullptr; edge = ed ge->fNextEdgeBelow) { |
| 1144 if (check_for_intersection(edge, leftEnclosingEdge, &activeE dges, c, alloc)) { | 1082 if (check_for_intersection(edge, leftEnclosingEdge, &activeE dges, c, alloc)) { |
| 1145 restartChecks = true; | 1083 restartChecks = true; |
| 1146 break; | 1084 break; |
| 1147 } | 1085 } |
| 1148 if (check_for_intersection(edge, rightEnclosingEdge, &active Edges, c, alloc)) { | 1086 if (check_for_intersection(edge, rightEnclosingEdge, &active Edges, c, alloc)) { |
| 1149 restartChecks = true; | 1087 restartChecks = true; |
| 1150 break; | 1088 break; |
| 1151 } | 1089 } |
| 1152 } | 1090 } |
| 1153 } else { | 1091 } else { |
| 1154 if (Vertex* pv = check_for_intersection(leftEnclosingEdge, right EnclosingEdge, | 1092 if (TessellatorVertex* pv = check_for_intersection(leftEnclosing Edge, |
| 1155 &activeEdges, c, alloc)) { | 1093 rightEnclosin gEdge, &activeEdges, |
| 1094 c, alloc)) { | |
| 1156 if (c.sweep_lt(pv->fPoint, v->fPoint)) { | 1095 if (c.sweep_lt(pv->fPoint, v->fPoint)) { |
| 1157 v = pv; | 1096 v = pv; |
| 1158 } | 1097 } |
| 1159 restartChecks = true; | 1098 restartChecks = true; |
| 1160 } | 1099 } |
| 1161 | 1100 |
| 1162 } | 1101 } |
| 1163 } while (restartChecks); | 1102 } while (restartChecks); |
| 1164 for (Edge* e = v->fFirstEdgeAbove; e; e = e->fNextEdgeAbove) { | 1103 for (Edge* e = v->fFirstEdgeAbove; e; e = e->fNextEdgeAbove) { |
| 1165 remove_edge(e, &activeEdges); | 1104 remove_edge(e, &activeEdges); |
| 1166 } | 1105 } |
| 1167 Edge* leftEdge = leftEnclosingEdge; | 1106 Edge* leftEdge = leftEnclosingEdge; |
| 1168 for (Edge* e = v->fFirstEdgeBelow; e; e = e->fNextEdgeBelow) { | 1107 for (Edge* e = v->fFirstEdgeBelow; e; e = e->fNextEdgeBelow) { |
| 1169 insert_edge(e, leftEdge, &activeEdges); | 1108 insert_edge(e, leftEdge, &activeEdges); |
| 1170 leftEdge = e; | 1109 leftEdge = e; |
| 1171 } | 1110 } |
| 1172 v->fProcessed = true; | 1111 v->fProcessed = true; |
| 1173 } | 1112 } |
| 1174 } | 1113 } |
| 1175 | 1114 |
| 1176 // Stage 5: Tessellate the simplified mesh into monotone polygons. | 1115 // Stage 5: Tessellate the simplified mesh into monotone polygons. |
| 1177 | 1116 |
| 1178 Poly* tessellate(Vertex* vertices, SkChunkAlloc& alloc) { | 1117 Poly* tessellate(TessellatorVertex* vertices, SkChunkAlloc& alloc) { |
| 1179 LOG("tessellating simple polygons\n"); | 1118 LOG("tessellating simple polygons\n"); |
| 1180 EdgeList activeEdges; | 1119 EdgeList activeEdges; |
| 1181 Poly* polys = nullptr; | 1120 Poly* polys = nullptr; |
| 1182 for (Vertex* v = vertices; v != nullptr; v = v->fNext) { | 1121 for (TessellatorVertex* v = vertices; v != nullptr; v = v->fNext) { |
| 1183 if (!v->fFirstEdgeAbove && !v->fFirstEdgeBelow) { | 1122 if (!v->fFirstEdgeAbove && !v->fFirstEdgeBelow) { |
| 1184 continue; | 1123 continue; |
| 1185 } | 1124 } |
| 1186 #if LOGGING_ENABLED | 1125 #if TESSELLATOR_LOGGING_ENABLED |
| 1187 LOG("\nvertex %g: (%g,%g)\n", v->fID, v->fPoint.fX, v->fPoint.fY); | 1126 LOG("\nvertex %g: (%g,%g)\n", v->fID, v->fPoint.fX, v->fPoint.fY); |
| 1188 #endif | 1127 #endif |
| 1189 Edge* leftEnclosingEdge = nullptr; | 1128 Edge* leftEnclosingEdge = nullptr; |
| 1190 Edge* rightEnclosingEdge = nullptr; | 1129 Edge* rightEnclosingEdge = nullptr; |
| 1191 find_enclosing_edges(v, &activeEdges, &leftEnclosingEdge, &rightEnclosin gEdge); | 1130 find_enclosing_edges(v, &activeEdges, &leftEnclosingEdge, &rightEnclosin gEdge); |
| 1192 Poly* leftPoly = nullptr; | 1131 Poly* leftPoly = nullptr; |
| 1193 Poly* rightPoly = nullptr; | 1132 Poly* rightPoly = nullptr; |
| 1194 if (v->fFirstEdgeAbove) { | 1133 if (v->fFirstEdgeAbove) { |
| 1195 leftPoly = v->fFirstEdgeAbove->fLeftPoly; | 1134 leftPoly = v->fFirstEdgeAbove->fLeftPoly; |
| 1196 rightPoly = v->fLastEdgeAbove->fRightPoly; | 1135 rightPoly = v->fLastEdgeAbove->fRightPoly; |
| 1197 } else { | 1136 } else { |
| 1198 leftPoly = leftEnclosingEdge ? leftEnclosingEdge->fRightPoly : nullp tr; | 1137 leftPoly = leftEnclosingEdge ? leftEnclosingEdge->fRightPoly : nullp tr; |
| 1199 rightPoly = rightEnclosingEdge ? rightEnclosingEdge->fLeftPoly : nul lptr; | 1138 rightPoly = rightEnclosingEdge ? rightEnclosingEdge->fLeftPoly : nul lptr; |
| 1200 } | 1139 } |
| 1201 #if LOGGING_ENABLED | 1140 #if TESSELLATOR_LOGGING_ENABLED |
| 1202 LOG("edges above:\n"); | 1141 LOG("edges above:\n"); |
| 1203 for (Edge* e = v->fFirstEdgeAbove; e; e = e->fNextEdgeAbove) { | 1142 for (Edge* e = v->fFirstEdgeAbove; e; e = e->fNextEdgeAbove) { |
| 1204 LOG("%g -> %g, lpoly %d, rpoly %d\n", e->fTop->fID, e->fBottom->fID, | 1143 LOG("%g -> %g, lpoly %d, rpoly %d\n", e->fTop->fID, e->fBottom->fID, |
| 1205 e->fLeftPoly ? e->fLeftPoly->fID : -1, e->fRightPoly ? e->fRight Poly->fID : -1); | 1144 e->fLeftPoly ? e->fLeftPoly->fID : -1, e->fRightPoly ? e->fRight Poly->fID : -1); |
| 1206 } | 1145 } |
| 1207 LOG("edges below:\n"); | 1146 LOG("edges below:\n"); |
| 1208 for (Edge* e = v->fFirstEdgeBelow; e; e = e->fNextEdgeBelow) { | 1147 for (Edge* e = v->fFirstEdgeBelow; e; e = e->fNextEdgeBelow) { |
| 1209 LOG("%g -> %g, lpoly %d, rpoly %d\n", e->fTop->fID, e->fBottom->fID, | 1148 LOG("%g -> %g, lpoly %d, rpoly %d\n", e->fTop->fID, e->fBottom->fID, |
| 1210 e->fLeftPoly ? e->fLeftPoly->fID : -1, e->fRightPoly ? e->fRight Poly->fID : -1); | 1149 e->fLeftPoly ? e->fLeftPoly->fID : -1, e->fRightPoly ? e->fRight Poly->fID : -1); |
| 1211 } | 1150 } |
| (...skipping 61 matching lines...) Expand 10 before | Expand all | Expand 10 after Loading... | |
| 1273 int winding = leftEdge->fLeftPoly ? leftEdge->fLeftPoly->fWindin g : 0; | 1212 int winding = leftEdge->fLeftPoly ? leftEdge->fLeftPoly->fWindin g : 0; |
| 1274 winding += leftEdge->fWinding; | 1213 winding += leftEdge->fWinding; |
| 1275 if (winding != 0) { | 1214 if (winding != 0) { |
| 1276 Poly* poly = new_poly(&polys, v, winding, alloc); | 1215 Poly* poly = new_poly(&polys, v, winding, alloc); |
| 1277 leftEdge->fRightPoly = rightEdge->fLeftPoly = poly; | 1216 leftEdge->fRightPoly = rightEdge->fLeftPoly = poly; |
| 1278 } | 1217 } |
| 1279 leftEdge = rightEdge; | 1218 leftEdge = rightEdge; |
| 1280 } | 1219 } |
| 1281 v->fLastEdgeBelow->fRightPoly = rightPoly; | 1220 v->fLastEdgeBelow->fRightPoly = rightPoly; |
| 1282 } | 1221 } |
| 1283 #if LOGGING_ENABLED | 1222 #if TESSELLATOR_LOGGING_ENABLED |
| 1284 LOG("\nactive edges:\n"); | 1223 LOG("\nactive edges:\n"); |
| 1285 for (Edge* e = activeEdges.fHead; e != nullptr; e = e->fRight) { | 1224 for (Edge* e = activeEdges.fHead; e != nullptr; e = e->fRight) { |
| 1286 LOG("%g -> %g, lpoly %d, rpoly %d\n", e->fTop->fID, e->fBottom->fID, | 1225 LOG("%g -> %g, lpoly %d, rpoly %d\n", e->fTop->fID, e->fBottom->fID, |
| 1287 e->fLeftPoly ? e->fLeftPoly->fID : -1, e->fRightPoly ? e->fRight Poly->fID : -1); | 1226 e->fLeftPoly ? e->fLeftPoly->fID : -1, e->fRightPoly ? e->fRight Poly->fID : -1); |
| 1288 } | 1227 } |
| 1289 #endif | 1228 #endif |
| 1290 } | 1229 } |
| 1291 return polys; | 1230 return polys; |
| 1292 } | 1231 } |
| 1293 | 1232 |
| 1294 // This is a driver function which calls stages 2-5 in turn. | 1233 // This is a driver function which calls stages 2-5 in turn. |
| 1295 | 1234 |
| 1296 Poly* contours_to_polys(Vertex** contours, int contourCnt, Comparator& c, SkChun kAlloc& alloc) { | 1235 Poly* contours_to_polys(TessellatorVertex** contours, int contourCnt, SkRect pat hBounds, |
| 1297 #if LOGGING_ENABLED | 1236 SkChunkAlloc& alloc) { |
| 1237 Comparator c; | |
| 1238 if (pathBounds.width() > pathBounds.height()) { | |
| 1239 c.sweep_lt = sweep_lt_horiz; | |
| 1240 c.sweep_gt = sweep_gt_horiz; | |
| 1241 } else { | |
| 1242 c.sweep_lt = sweep_lt_vert; | |
| 1243 c.sweep_gt = sweep_gt_vert; | |
| 1244 } | |
| 1245 #if TESSELLATOR_LOGGING_ENABLED | |
| 1298 for (int i = 0; i < contourCnt; ++i) { | 1246 for (int i = 0; i < contourCnt; ++i) { |
| 1299 Vertex* v = contours[i]; | 1247 TessellatorVertex* v = contours[i]; |
| 1300 SkASSERT(v); | 1248 SkASSERT(v); |
| 1301 LOG("path.moveTo(%20.20g, %20.20g);\n", v->fPoint.fX, v->fPoint.fY); | 1249 LOG("path.moveTo(%20.20g, %20.20g);\n", v->fPoint.fX, v->fPoint.fY); |
| 1302 for (v = v->fNext; v != contours[i]; v = v->fNext) { | 1250 for (v = v->fNext; v != contours[i]; v = v->fNext) { |
| 1303 LOG("path.lineTo(%20.20g, %20.20g);\n", v->fPoint.fX, v->fPoint.fY); | 1251 LOG("path.lineTo(%20.20g, %20.20g);\n", v->fPoint.fX, v->fPoint.fY); |
| 1304 } | 1252 } |
| 1305 } | 1253 } |
| 1306 #endif | 1254 #endif |
| 1307 sanitize_contours(contours, contourCnt); | 1255 sanitize_contours(contours, contourCnt); |
| 1308 Vertex* vertices = build_edges(contours, contourCnt, c, alloc); | 1256 TessellatorVertex* vertices = build_edges(contours, contourCnt, c, alloc); |
| 1309 if (!vertices) { | 1257 if (!vertices) { |
| 1310 return nullptr; | 1258 return nullptr; |
| 1311 } | 1259 } |
| 1312 | 1260 |
| 1313 // Sort vertices in Y (secondarily in X). | 1261 // Sort vertices in Y (secondarily in X). |
| 1314 merge_sort(&vertices, c); | 1262 merge_sort(&vertices, c); |
| 1315 merge_coincident_vertices(&vertices, c, alloc); | 1263 merge_coincident_vertices(&vertices, c, alloc); |
| 1316 #if LOGGING_ENABLED | 1264 #if TESSELLATOR_LOGGING_ENABLED |
| 1317 for (Vertex* v = vertices; v != nullptr; v = v->fNext) { | 1265 for (TessellatorVertex* v = vertices; v != nullptr; v = v->fNext) { |
| 1318 static float gID = 0.0f; | 1266 static float gID = 0.0f; |
| 1319 v->fID = gID++; | 1267 v->fID = gID++; |
| 1320 } | 1268 } |
| 1321 #endif | 1269 #endif |
| 1322 simplify(vertices, c, alloc); | 1270 simplify(vertices, c, alloc); |
| 1323 return tessellate(vertices, alloc); | 1271 return tessellate(vertices, alloc); |
| 1324 } | 1272 } |
| 1325 | 1273 |
| 1274 Poly* path_to_polys(const SkPath& path, SkScalar tolerance, const SkRect& clipBo unds, | |
| 1275 bool* isLinear) { | |
| 1276 int contourCnt; | |
| 1277 int maxPts = GrPathUtils::worstCasePointCount(path, &contourCnt, tolerance); | |
| 1278 if (maxPts <= 0) { | |
| 1279 return nullptr; | |
| 1280 } | |
| 1281 if (maxPts > ((int)SK_MaxU16 + 1)) { | |
| 1282 SkDebugf("Path not rendered, too many verts (%d)\n", maxPts); | |
| 1283 return nullptr; | |
| 1284 } | |
| 1285 SkPath::FillType fillType = path.getFillType(); | |
| 1286 if (SkPath::IsInverseFillType(fillType)) { | |
| 1287 contourCnt++; | |
| 1288 } | |
| 1289 SkAutoTDeleteArray<TessellatorVertex*> contours(new TessellatorVertex* [cont ourCnt]); | |
| 1290 | |
| 1291 // For the initial size of the chunk allocator, estimate based on the point count: | |
| 1292 // one vertex per point for the initial passes, plus two for the vertices in the | |
| 1293 // resulting Polys, since the same point may end up in two Polys. Assume mi nimal | |
| 1294 // connectivity of one Edge per TessellatorVertex (will grow for intersectio ns). | |
| 1295 SkChunkAlloc alloc(maxPts * (3 * sizeof(TessellatorVertex) + sizeof(Edge))); | |
| 1296 path_to_contours(path, tolerance, clipBounds, contours.get(), alloc, isLinea r); | |
| 1297 return contours_to_polys(contours.get(), contourCnt, path.getBounds(), alloc ); | |
| 1298 } | |
| 1299 | |
| 1326 // Stage 6: Triangulate the monotone polygons into a vertex buffer. | 1300 // Stage 6: Triangulate the monotone polygons into a vertex buffer. |
| 1327 | 1301 |
| 1328 SkPoint* polys_to_triangles(Poly* polys, SkPath::FillType fillType, SkPoint* dat a) { | 1302 int polys_to_triangles(Poly* polys, SkPath::FillType fillType, bool isLinear, |
| 1329 SkPoint* d = data; | 1303 GrResourceProvider* resourceProvider, |
| 1304 SkAutoTUnref<GrVertexBuffer>& vertexBuffer, bool canMapVB ) { | |
| 1305 int count = 0; | |
| 1306 for (Poly* poly = polys; poly; poly = poly->fNext) { | |
| 1307 if (apply_fill_type(fillType, poly->fWinding) && poly->fCount >= 3) { | |
| 1308 count += (poly->fCount - 2) * (TESSELLATOR_WIREFRAME ? 6 : 3); | |
| 1309 } | |
| 1310 } | |
| 1311 if (0 == count) { | |
| 1312 return 0; | |
| 1313 } | |
| 1314 | |
| 1315 size_t size = count * sizeof(SkPoint); | |
| 1316 if (!vertexBuffer.get() || vertexBuffer->gpuMemorySize() < size) { | |
| 1317 vertexBuffer.reset(resourceProvider->createVertexBuffer( | |
| 1318 size, GrResourceProvider::kStatic_BufferUsage, 0)); | |
| 1319 } | |
| 1320 if (!vertexBuffer.get()) { | |
| 1321 SkDebugf("Could not allocate vertices\n"); | |
| 1322 return 0; | |
| 1323 } | |
| 1324 SkPoint* verts; | |
| 1325 if (canMapVB) { | |
| 1326 verts = static_cast<SkPoint*>(vertexBuffer->map()); | |
| 1327 } else { | |
| 1328 verts = new SkPoint[count]; | |
| 1329 } | |
| 1330 SkPoint* end = verts; | |
| 1330 for (Poly* poly = polys; poly; poly = poly->fNext) { | 1331 for (Poly* poly = polys; poly; poly = poly->fNext) { |
| 1331 if (apply_fill_type(fillType, poly->fWinding)) { | 1332 if (apply_fill_type(fillType, poly->fWinding)) { |
| 1332 d = poly->emit(d); | 1333 end = poly->emit(end); |
| 1333 } | 1334 } |
| 1334 } | 1335 } |
| 1335 return d; | 1336 int actualCount = static_cast<int>(end - verts); |
| 1337 LOG("actual count: %d\n", actualCount); | |
| 1338 SkASSERT(actualCount <= count); | |
| 1339 if (canMapVB) { | |
| 1340 vertexBuffer->unmap(); | |
| 1341 } else { | |
| 1342 vertexBuffer->updateData(verts, actualCount * sizeof(SkPoint)); | |
| 1343 delete[] verts; | |
| 1344 } | |
| 1345 | |
| 1346 return actualCount; | |
| 1336 } | 1347 } |
| 1337 | 1348 |
| 1338 struct TessInfo { | 1349 int polys_to_vertices(Poly* polys, SkPath::FillType fillType, bool isLinear, |
| 1339 SkScalar fTolerance; | 1350 WindingVertex** verts) { |
| 1340 int fCount; | 1351 int count = 0; |
| 1341 }; | 1352 for (Poly* poly = polys; poly; poly = poly->fNext) { |
| 1342 | 1353 if (apply_fill_type(fillType, poly->fWinding) && poly->fCount >= 3) { |
| 1343 bool cache_match(GrVertexBuffer* vertexBuffer, SkScalar tol, int* actualCount) { | 1354 count += (poly->fCount - 2) * (TESSELLATOR_WIREFRAME ? 6 : 3); |
| 1344 if (!vertexBuffer) { | 1355 } |
| 1345 return false; | |
| 1346 } | 1356 } |
| 1347 const SkData* data = vertexBuffer->getUniqueKey().getCustomData(); | 1357 if (0 == count) { |
| 1348 SkASSERT(data); | 1358 *verts = nullptr; |
| 1349 const TessInfo* info = static_cast<const TessInfo*>(data->data()); | 1359 return 0; |
| 1350 if (info->fTolerance == 0 || info->fTolerance < 3.0f * tol) { | |
| 1351 *actualCount = info->fCount; | |
| 1352 return true; | |
| 1353 } | |
| 1354 return false; | |
| 1355 } | |
| 1356 | |
| 1357 }; | |
| 1358 | |
| 1359 GrTessellatingPathRenderer::GrTessellatingPathRenderer() { | |
| 1360 } | |
| 1361 | |
| 1362 namespace { | |
| 1363 | |
| 1364 // When the SkPathRef genID changes, invalidate a corresponding GrResource descr ibed by key. | |
| 1365 class PathInvalidator : public SkPathRef::GenIDChangeListener { | |
| 1366 public: | |
| 1367 explicit PathInvalidator(const GrUniqueKey& key) : fMsg(key) {} | |
| 1368 private: | |
| 1369 GrUniqueKeyInvalidatedMessage fMsg; | |
| 1370 | |
| 1371 void onChange() override { | |
| 1372 SkMessageBus<GrUniqueKeyInvalidatedMessage>::Post(fMsg); | |
| 1373 } | |
| 1374 }; | |
| 1375 | |
| 1376 } // namespace | |
| 1377 | |
| 1378 bool GrTessellatingPathRenderer::onCanDrawPath(const CanDrawPathArgs& args) cons t { | |
| 1379 // This path renderer can draw all fill styles, all stroke styles except hai rlines, but does | |
| 1380 // not do antialiasing. It can do convex and concave paths, but we'll leave the convex ones to | |
| 1381 // simpler algorithms. | |
| 1382 return !IsStrokeHairlineOrEquivalent(*args.fStroke, *args.fViewMatrix, nullp tr) && | |
| 1383 !args.fAntiAlias && !args.fPath->isConvex(); | |
| 1384 } | |
| 1385 | |
| 1386 class TessellatingPathBatch : public GrVertexBatch { | |
| 1387 public: | |
| 1388 DEFINE_BATCH_CLASS_ID | |
| 1389 | |
| 1390 static GrDrawBatch* Create(const GrColor& color, | |
| 1391 const SkPath& path, | |
| 1392 const GrStrokeInfo& stroke, | |
| 1393 const SkMatrix& viewMatrix, | |
| 1394 SkRect clipBounds) { | |
| 1395 return new TessellatingPathBatch(color, path, stroke, viewMatrix, clipBo unds); | |
| 1396 } | 1360 } |
| 1397 | 1361 |
| 1398 const char* name() const override { return "TessellatingPathBatch"; } | 1362 *verts = new WindingVertex[count]; |
| 1399 | 1363 WindingVertex* vertsEnd = *verts; |
| 1400 void computePipelineOptimizations(GrInitInvariantOutput* color, | 1364 SkPoint* points = new SkPoint[count]; |
| 1401 GrInitInvariantOutput* coverage, | 1365 SkPoint* pointsEnd = points; |
| 1402 GrBatchToXPOverrides* overrides) const ove rride { | 1366 for (Poly* poly = polys; poly; poly = poly->fNext) { |
| 1403 color->setKnownFourComponents(fColor); | 1367 if (apply_fill_type(fillType, poly->fWinding)) { |
| 1404 coverage->setUnknownSingleComponent(); | 1368 SkPoint* start = pointsEnd; |
| 1405 overrides->fUsePLSDstRead = false; | 1369 pointsEnd = poly->emit(pointsEnd); |
| 1406 } | 1370 while (start != pointsEnd) { |
| 1407 | 1371 vertsEnd->fPos = *start; |
| 1408 private: | 1372 vertsEnd->fWinding = poly->fWinding; |
| 1409 void initBatchTracker(const GrXPOverridesForBatch& overrides) override { | 1373 ++start; |
| 1410 // Handle any color overrides | 1374 ++vertsEnd; |
| 1411 if (!overrides.readsColor()) { | |
| 1412 fColor = GrColor_ILLEGAL; | |
| 1413 } | |
| 1414 overrides.getOverrideColorIfSet(&fColor); | |
| 1415 fPipelineInfo = overrides; | |
| 1416 } | |
| 1417 | |
| 1418 int tessellate(GrUniqueKey* key, | |
| 1419 GrResourceProvider* resourceProvider, | |
| 1420 SkAutoTUnref<GrVertexBuffer>& vertexBuffer, | |
| 1421 bool canMapVB) const { | |
| 1422 SkPath path; | |
| 1423 GrStrokeInfo stroke(fStroke); | |
| 1424 if (stroke.isDashed()) { | |
| 1425 if (!stroke.applyDashToPath(&path, &stroke, fPath)) { | |
| 1426 return 0; | |
| 1427 } | |
| 1428 } else { | |
| 1429 path = fPath; | |
| 1430 } | |
| 1431 if (!stroke.isFillStyle()) { | |
| 1432 stroke.setResScale(SkScalarAbs(fViewMatrix.getMaxScale())); | |
| 1433 if (!stroke.applyToPath(&path, path)) { | |
| 1434 return 0; | |
| 1435 } | |
| 1436 stroke.setFillStyle(); | |
| 1437 } | |
| 1438 SkRect pathBounds = path.getBounds(); | |
| 1439 Comparator c; | |
| 1440 if (pathBounds.width() > pathBounds.height()) { | |
| 1441 c.sweep_lt = sweep_lt_horiz; | |
| 1442 c.sweep_gt = sweep_gt_horiz; | |
| 1443 } else { | |
| 1444 c.sweep_lt = sweep_lt_vert; | |
| 1445 c.sweep_gt = sweep_gt_vert; | |
| 1446 } | |
| 1447 SkScalar screenSpaceTol = GrPathUtils::kDefaultTolerance; | |
| 1448 SkScalar tol = GrPathUtils::scaleToleranceToSrc(screenSpaceTol, fViewMat rix, pathBounds); | |
| 1449 int contourCnt; | |
| 1450 int maxPts = GrPathUtils::worstCasePointCount(path, &contourCnt, tol); | |
| 1451 if (maxPts <= 0) { | |
| 1452 return 0; | |
| 1453 } | |
| 1454 if (maxPts > ((int)SK_MaxU16 + 1)) { | |
| 1455 SkDebugf("Path not rendered, too many verts (%d)\n", maxPts); | |
| 1456 return 0; | |
| 1457 } | |
| 1458 SkPath::FillType fillType = path.getFillType(); | |
| 1459 if (SkPath::IsInverseFillType(fillType)) { | |
| 1460 contourCnt++; | |
| 1461 } | |
| 1462 | |
| 1463 LOG("got %d pts, %d contours\n", maxPts, contourCnt); | |
| 1464 SkAutoTDeleteArray<Vertex*> contours(new Vertex* [contourCnt]); | |
| 1465 | |
| 1466 // For the initial size of the chunk allocator, estimate based on the po int count: | |
| 1467 // one vertex per point for the initial passes, plus two for the vertice s in the | |
| 1468 // resulting Polys, since the same point may end up in two Polys. Assum e minimal | |
| 1469 // connectivity of one Edge per Vertex (will grow for intersections). | |
| 1470 SkChunkAlloc alloc(maxPts * (3 * sizeof(Vertex) + sizeof(Edge))); | |
| 1471 bool isLinear; | |
| 1472 path_to_contours(path, tol, fClipBounds, contours.get(), alloc, &isLinea r); | |
| 1473 Poly* polys; | |
| 1474 polys = contours_to_polys(contours.get(), contourCnt, c, alloc); | |
| 1475 int count = 0; | |
| 1476 for (Poly* poly = polys; poly; poly = poly->fNext) { | |
| 1477 if (apply_fill_type(fillType, poly->fWinding) && poly->fCount >= 3) { | |
| 1478 count += (poly->fCount - 2) * (WIREFRAME ? 6 : 3); | |
| 1479 } | 1375 } |
| 1480 } | 1376 } |
| 1481 if (0 == count) { | |
| 1482 return 0; | |
| 1483 } | |
| 1484 | |
| 1485 size_t size = count * sizeof(SkPoint); | |
| 1486 if (!vertexBuffer.get() || vertexBuffer->gpuMemorySize() < size) { | |
| 1487 vertexBuffer.reset(resourceProvider->createVertexBuffer( | |
| 1488 size, GrResourceProvider::kStatic_BufferUsage, 0)); | |
| 1489 } | |
| 1490 if (!vertexBuffer.get()) { | |
| 1491 SkDebugf("Could not allocate vertices\n"); | |
| 1492 return 0; | |
| 1493 } | |
| 1494 SkPoint* verts; | |
| 1495 if (canMapVB) { | |
| 1496 verts = static_cast<SkPoint*>(vertexBuffer->map()); | |
| 1497 } else { | |
| 1498 verts = new SkPoint[count]; | |
| 1499 } | |
| 1500 SkPoint* end = polys_to_triangles(polys, fillType, verts); | |
| 1501 int actualCount = static_cast<int>(end - verts); | |
| 1502 LOG("actual count: %d\n", actualCount); | |
| 1503 SkASSERT(actualCount <= count); | |
| 1504 if (canMapVB) { | |
| 1505 vertexBuffer->unmap(); | |
| 1506 } else { | |
| 1507 vertexBuffer->updateData(verts, actualCount * sizeof(SkPoint)); | |
| 1508 delete[] verts; | |
| 1509 } | |
| 1510 | |
| 1511 | |
| 1512 if (!fPath.isVolatile()) { | |
| 1513 TessInfo info; | |
| 1514 info.fTolerance = isLinear ? 0 : tol; | |
| 1515 info.fCount = actualCount; | |
| 1516 SkAutoTUnref<SkData> data(SkData::NewWithCopy(&info, sizeof(info))); | |
| 1517 key->setCustomData(data.get()); | |
| 1518 resourceProvider->assignUniqueKeyToResource(*key, vertexBuffer.get() ); | |
| 1519 SkPathPriv::AddGenIDChangeListener(fPath, new PathInvalidator(*key)) ; | |
| 1520 } | |
| 1521 return actualCount; | |
| 1522 } | 1377 } |
| 1523 | 1378 int actualCount = static_cast<int>(vertsEnd - *verts); |
| 1524 void onPrepareDraws(Target* target) const override { | 1379 SkASSERT(actualCount <= count); |
| 1525 // construct a cache key from the path's genID and the view matrix | 1380 SkASSERT(pointsEnd - points == actualCount); |
| 1526 static const GrUniqueKey::Domain kDomain = GrUniqueKey::GenerateDomain() ; | 1381 delete[] points; |
| 1527 GrUniqueKey key; | 1382 return actualCount; |
| 1528 int clipBoundsSize32 = | |
| 1529 fPath.isInverseFillType() ? sizeof(fClipBounds) / sizeof(uint32_t) : 0; | |
| 1530 int strokeDataSize32 = fStroke.computeUniqueKeyFragmentData32Cnt(); | |
| 1531 GrUniqueKey::Builder builder(&key, kDomain, 2 + clipBoundsSize32 + strok eDataSize32); | |
| 1532 builder[0] = fPath.getGenerationID(); | |
| 1533 builder[1] = fPath.getFillType(); | |
| 1534 // For inverse fills, the tessellation is dependent on clip bounds. | |
| 1535 if (fPath.isInverseFillType()) { | |
| 1536 memcpy(&builder[2], &fClipBounds, sizeof(fClipBounds)); | |
| 1537 } | |
| 1538 fStroke.asUniqueKeyFragment(&builder[2 + clipBoundsSize32]); | |
| 1539 builder.finish(); | |
| 1540 GrResourceProvider* rp = target->resourceProvider(); | |
| 1541 SkAutoTUnref<GrVertexBuffer> vertexBuffer(rp->findAndRefTByUniqueKey<GrV ertexBuffer>(key)); | |
| 1542 int actualCount; | |
| 1543 SkScalar screenSpaceTol = GrPathUtils::kDefaultTolerance; | |
| 1544 SkScalar tol = GrPathUtils::scaleToleranceToSrc( | |
| 1545 screenSpaceTol, fViewMatrix, fPath.getBounds()); | |
| 1546 if (!cache_match(vertexBuffer.get(), tol, &actualCount)) { | |
| 1547 bool canMapVB = GrCaps::kNone_MapFlags != target->caps().mapBufferFl ags(); | |
| 1548 actualCount = this->tessellate(&key, rp, vertexBuffer, canMapVB); | |
| 1549 } | |
| 1550 | |
| 1551 if (actualCount == 0) { | |
| 1552 return; | |
| 1553 } | |
| 1554 | |
| 1555 SkAutoTUnref<const GrGeometryProcessor> gp; | |
| 1556 { | |
| 1557 using namespace GrDefaultGeoProcFactory; | |
| 1558 | |
| 1559 Color color(fColor); | |
| 1560 LocalCoords localCoords(fPipelineInfo.readsLocalCoords() ? | |
| 1561 LocalCoords::kUsePosition_Type : | |
| 1562 LocalCoords::kUnused_Type); | |
| 1563 Coverage::Type coverageType; | |
| 1564 if (fPipelineInfo.readsCoverage()) { | |
| 1565 coverageType = Coverage::kSolid_Type; | |
| 1566 } else { | |
| 1567 coverageType = Coverage::kNone_Type; | |
| 1568 } | |
| 1569 Coverage coverage(coverageType); | |
| 1570 gp.reset(GrDefaultGeoProcFactory::Create(color, coverage, localCoord s, | |
| 1571 fViewMatrix)); | |
| 1572 } | |
| 1573 | |
| 1574 target->initDraw(gp, this->pipeline()); | |
| 1575 SkASSERT(gp->getVertexStride() == sizeof(SkPoint)); | |
| 1576 | |
| 1577 GrPrimitiveType primitiveType = WIREFRAME ? kLines_GrPrimitiveType | |
| 1578 : kTriangles_GrPrimitiveType; | |
| 1579 GrVertices vertices; | |
| 1580 vertices.init(primitiveType, vertexBuffer.get(), 0, actualCount); | |
| 1581 target->draw(vertices); | |
| 1582 } | |
| 1583 | |
| 1584 bool onCombineIfPossible(GrBatch*, const GrCaps&) override { return false; } | |
| 1585 | |
| 1586 TessellatingPathBatch(const GrColor& color, | |
| 1587 const SkPath& path, | |
| 1588 const GrStrokeInfo& stroke, | |
| 1589 const SkMatrix& viewMatrix, | |
| 1590 const SkRect& clipBounds) | |
| 1591 : INHERITED(ClassID()) | |
| 1592 , fColor(color) | |
| 1593 , fPath(path) | |
| 1594 , fStroke(stroke) | |
| 1595 , fViewMatrix(viewMatrix) { | |
| 1596 const SkRect& pathBounds = path.getBounds(); | |
| 1597 fClipBounds = clipBounds; | |
| 1598 // Because the clip bounds are used to add a contour for inverse fills, they must also | |
| 1599 // include the path bounds. | |
| 1600 fClipBounds.join(pathBounds); | |
| 1601 if (path.isInverseFillType()) { | |
| 1602 fBounds = fClipBounds; | |
| 1603 } else { | |
| 1604 fBounds = path.getBounds(); | |
| 1605 } | |
| 1606 if (!stroke.isFillStyle()) { | |
| 1607 SkScalar radius = SkScalarHalf(stroke.getWidth()); | |
| 1608 if (stroke.getJoin() == SkPaint::kMiter_Join) { | |
| 1609 SkScalar scale = stroke.getMiter(); | |
| 1610 if (scale > SK_Scalar1) { | |
| 1611 radius = SkScalarMul(radius, scale); | |
| 1612 } | |
| 1613 } | |
| 1614 fBounds.outset(radius, radius); | |
| 1615 } | |
| 1616 viewMatrix.mapRect(&fBounds); | |
| 1617 } | |
| 1618 | |
| 1619 GrColor fColor; | |
| 1620 SkPath fPath; | |
| 1621 GrStrokeInfo fStroke; | |
| 1622 SkMatrix fViewMatrix; | |
| 1623 SkRect fClipBounds; // in source space | |
| 1624 GrXPOverridesForBatch fPipelineInfo; | |
| 1625 | |
| 1626 typedef GrVertexBatch INHERITED; | |
| 1627 }; | |
| 1628 | |
| 1629 bool GrTessellatingPathRenderer::onDrawPath(const DrawPathArgs& args) { | |
| 1630 SkASSERT(!args.fAntiAlias); | |
| 1631 const GrRenderTarget* rt = args.fPipelineBuilder->getRenderTarget(); | |
| 1632 if (nullptr == rt) { | |
| 1633 return false; | |
| 1634 } | |
| 1635 | |
| 1636 SkIRect clipBoundsI; | |
| 1637 args.fPipelineBuilder->clip().getConservativeBounds(rt->width(), rt->height( ), &clipBoundsI); | |
| 1638 SkRect clipBounds = SkRect::Make(clipBoundsI); | |
| 1639 SkMatrix vmi; | |
| 1640 if (!args.fViewMatrix->invert(&vmi)) { | |
| 1641 return false; | |
| 1642 } | |
| 1643 vmi.mapRect(&clipBounds); | |
| 1644 SkAutoTUnref<GrDrawBatch> batch(TessellatingPathBatch::Create(args.fColor, * args.fPath, | |
| 1645 *args.fStroke, *args.fViewMatrix, | |
| 1646 clipBounds)); | |
| 1647 args.fTarget->drawBatch(*args.fPipelineBuilder, batch); | |
| 1648 | |
| 1649 return true; | |
| 1650 } | 1383 } |
| 1651 | |
| 1652 //////////////////////////////////////////////////////////////////////////////// /////////////////// | |
| 1653 | |
| 1654 #ifdef GR_TEST_UTILS | |
| 1655 | |
| 1656 DRAW_BATCH_TEST_DEFINE(TesselatingPathBatch) { | |
| 1657 GrColor color = GrRandomColor(random); | |
| 1658 SkMatrix viewMatrix = GrTest::TestMatrixInvertible(random); | |
| 1659 SkPath path = GrTest::TestPath(random); | |
| 1660 SkRect clipBounds = GrTest::TestRect(random); | |
| 1661 SkMatrix vmi; | |
| 1662 bool result = viewMatrix.invert(&vmi); | |
| 1663 if (!result) { | |
| 1664 SkFAIL("Cannot invert matrix\n"); | |
| 1665 } | |
| 1666 vmi.mapRect(&clipBounds); | |
| 1667 GrStrokeInfo strokeInfo = GrTest::TestStrokeInfo(random); | |
| 1668 return TessellatingPathBatch::Create(color, path, strokeInfo, viewMatrix, cl ipBounds); | |
| 1669 } | |
| 1670 | |
| 1671 #endif | |
| OLD | NEW |