OLD | NEW |
(Empty) | |
| 1 /* |
| 2 * Copyright 2015 Google Inc. |
| 3 * |
| 4 * Use of this source code is governed by a BSD-style license that can be |
| 5 * found in the LICENSE file. |
| 6 */ |
| 7 |
| 8 #include "GrTessellatingPathRenderer.h" |
| 9 |
| 10 #include "GrDefaultGeoProcFactory.h" |
| 11 #include "GrPathUtils.h" |
| 12 #include "SkChunkAlloc.h" |
| 13 #include "SkGeometry.h" |
| 14 |
| 15 #include <stdio.h> |
| 16 |
| 17 /* |
| 18 * This path renderer tessellates the path into triangles, uploads the triangles
to a |
| 19 * vertex buffer, and renders them with a single draw call. It does not currentl
y do |
| 20 * antialiasing, so it must be used in conjunction with multisampling. |
| 21 * |
| 22 * There are six stages to the algorithm: |
| 23 * |
| 24 * 1) Linearize the path contours into piecewise linear segments (path_to_contou
rs()). |
| 25 * 2) Build a mesh of edges connecting the vertices (build_edges()). |
| 26 * 3) Sort the vertices in Y (and secondarily in X) (merge_sort()). |
| 27 * 4) Simplify the mesh by inserting new vertices at intersecting edges (simplif
y()). |
| 28 * 5) Tessellate the simplified mesh into monotone polygons (tessellate()). |
| 29 * 6) Triangulate the monotone polygons directly into a vertex buffer (polys_to_
triangles()). |
| 30 * |
| 31 * The vertex sorting in step (3) is a merge sort, since it plays well with the
linked list |
| 32 * of vertices (and the necessity of inserting new vertices on intersection). |
| 33 * |
| 34 * Stages (4) and (5) use an active edge list, which a list of all edges for whi
ch the |
| 35 * sweep line has crossed the top vertex, but not the bottom vertex. It's sorte
d |
| 36 * left-to-right based on the point where both edges are active (when both top v
ertices |
| 37 * have been seen, so the "lower" top vertex of the two). If the top vertices ar
e equal |
| 38 * (shared), it's sorted based on the last point where both edges are active, so
the |
| 39 * "upper" bottom vertex. |
| 40 * |
| 41 * The most complex step is the simplification (4). It's based on the Bentley-Ot
tman |
| 42 * line-sweep algorithm, but due to floating point inaccuracy, the intersection
points are |
| 43 * not exact and may violate the mesh topology or active edge list ordering. We |
| 44 * accommodate this by adjusting the topology of the mesh and AEL to match the i
ntersection |
| 45 * points. This occurs in three ways: |
| 46 * |
| 47 * A) Intersections may cause a shortened edge to no longer be ordered with resp
ect to its |
| 48 * neighbouring edges at the top or bottom vertex. This is handled by merging
the |
| 49 * edges (merge_collinear_edges()). |
| 50 * B) Intersections may cause an edge to violate the left-to-right ordering of t
he |
| 51 * active edge list. This is handled by splitting the neighbour edge on the |
| 52 * intersected vertex (cleanup_active_edges()). |
| 53 * C) Shortening an edge may cause an active edge to become inactive or an inact
ive edge |
| 54 * to become active. This is handled by removing or inserting the edge in the
active |
| 55 * edge list (fix_active_state()). |
| 56 * |
| 57 * The tessellation steps (5) and (6) are based on "Triangulating Simple Polygon
s and |
| 58 * Equivalent Problems" (Fournier and Montuno); also a line-sweep algorithm. Not
e that it |
| 59 * currently uses a linked list for the active edge list, rather than a 2-3 tree
as the |
| 60 * paper describes. The 2-3 tree gives O(lg N) lookups, but insertion and remova
l also |
| 61 * become O(lg N). In all the test cases, it was found that the cost of frequent
O(lg N) |
| 62 * insertions and removals was greater than the cost of infrequent O(N) lookups
with the |
| 63 * linked list implementation. With the latter, all removals are O(1), and most
insertions |
| 64 * are O(1), since we know the adjacent edge in the active edge list based on th
e topology. |
| 65 * Only type 2 vertices (see paper) require the O(N) lookups, and these are much
less |
| 66 * frequent. There may be other data structures worth investigating, however. |
| 67 * |
| 68 * Note that there is a compile-time flag (SWEEP_IN_X) which changes the orienta
tion of the |
| 69 * line sweep algorithms. When SWEEP_IN_X is unset, we sort vertices based on in
creasing |
| 70 * Y coordinate, and secondarily by increasing X coordinate. When SWEEP_IN_X is
set, we sort by |
| 71 * increasing X coordinate, but secondarily by *decreasing* Y coordinate. This i
s so that the |
| 72 * "left" and "right" orientation in the code remains correct (edges to the left
are increasing |
| 73 * in Y; edges to the right are decreasing in Y). That is, the setting rotates 9
0 degrees |
| 74 * counterclockwise, rather that transposing. |
| 75 * |
| 76 * The choice is arbitrary, but most test cases are wider than they are tall, so
the |
| 77 * default is to sweep in X. In the future, we may want to make this a runtime p
arameter |
| 78 * and base it on the aspect ratio of the clip bounds. |
| 79 */ |
| 80 #define LOGGING_ENABLED 0 |
| 81 #define WIREFRAME 0 |
| 82 #define SWEEP_IN_X 1 |
| 83 |
| 84 #if LOGGING_ENABLED |
| 85 #define LOG printf |
| 86 #else |
| 87 #define LOG(...) |
| 88 #endif |
| 89 |
| 90 #define ALLOC_NEW(Type, args, alloc) \ |
| 91 SkNEW_PLACEMENT_ARGS(alloc.allocThrow(sizeof(Type)), Type, args) |
| 92 |
| 93 namespace { |
| 94 |
| 95 struct Vertex; |
| 96 struct Edge; |
| 97 struct Poly; |
| 98 |
| 99 template <class T, T* T::*Prev, T* T::*Next> |
| 100 void insert(T* t, T* prev, T* next, T** head, T** tail) { |
| 101 t->*Prev = prev; |
| 102 t->*Next = next; |
| 103 if (prev) { |
| 104 prev->*Next = t; |
| 105 } else if (head) { |
| 106 *head = t; |
| 107 } |
| 108 if (next) { |
| 109 next->*Prev = t; |
| 110 } else if (tail) { |
| 111 *tail = t; |
| 112 } |
| 113 } |
| 114 |
| 115 template <class T, T* T::*Prev, T* T::*Next> |
| 116 void remove(T* t, T** head, T** tail) { |
| 117 if (t->*Prev) { |
| 118 t->*Prev->*Next = t->*Next; |
| 119 } else if (head) { |
| 120 *head = t->*Next; |
| 121 } |
| 122 if (t->*Next) { |
| 123 t->*Next->*Prev = t->*Prev; |
| 124 } else if (tail) { |
| 125 *tail = t->*Prev; |
| 126 } |
| 127 t->*Prev = t->*Next = NULL; |
| 128 } |
| 129 |
| 130 /** |
| 131 * Vertices are used in three ways: first, the path contours are converted into
a |
| 132 * circularly-linked list of Vertices for each contour. After edge construction,
the same Vertices |
| 133 * are re-ordered by the merge sort according to the sweep_lt comparator (usuall
y, increasing |
| 134 * in Y) using the same fPrev/fNext pointers that were used for the contours, to
avoid |
| 135 * reallocation. Finally, MonotonePolys are built containing a circularly-linked
list of |
| 136 * Vertices. (Currently, those Vertices are newly-allocated for the MonotonePoly
s, since |
| 137 * an individual Vertex from the path mesh may belong to multiple |
| 138 * MonotonePolys, so the original Vertices cannot be re-used. |
| 139 */ |
| 140 |
| 141 struct Vertex { |
| 142 Vertex(const SkPoint& point) |
| 143 : fPoint(point), fPrev(NULL), fNext(NULL) |
| 144 , fFirstEdgeAbove(NULL), fLastEdgeAbove(NULL) |
| 145 , fFirstEdgeBelow(NULL), fLastEdgeBelow(NULL) |
| 146 , fProcessed(false) |
| 147 #if LOGGING_ENABLED |
| 148 , fID (-1.0f) |
| 149 #endif |
| 150 {} |
| 151 SkPoint fPoint; // Vertex position |
| 152 Vertex* fPrev; // Linked list of contours, then Y-sorted vertices
. |
| 153 Vertex* fNext; // " |
| 154 Edge* fFirstEdgeAbove; // Linked list of edges above this vertex. |
| 155 Edge* fLastEdgeAbove; // " |
| 156 Edge* fFirstEdgeBelow; // Linked list of edges below this vertex. |
| 157 Edge* fLastEdgeBelow; // " |
| 158 bool fProcessed; // Has this vertex been seen in simplify()? |
| 159 #if LOGGING_ENABLED |
| 160 float fID; // Identifier used for logging. |
| 161 #endif |
| 162 }; |
| 163 |
| 164 /*******************************************************************************
********/ |
| 165 |
| 166 bool sweep_lt(const SkPoint& a, const SkPoint& b) { |
| 167 #if SWEEP_IN_X |
| 168 return a.fX == b.fX ? a.fY > b.fY : a.fX < b.fX; |
| 169 #else |
| 170 return a.fY == b.fY ? a.fX < b.fX : a.fY < b.fY; |
| 171 #endif |
| 172 } |
| 173 |
| 174 bool sweep_gt(const SkPoint& a, const SkPoint& b) { |
| 175 #if SWEEP_IN_X |
| 176 return a.fX == b.fX ? a.fY < b.fY : a.fX > b.fX; |
| 177 #else |
| 178 return a.fY == b.fY ? a.fX > b.fX : a.fY > b.fY; |
| 179 #endif |
| 180 } |
| 181 |
| 182 inline void* emit_vertex(Vertex* v, void* data) { |
| 183 SkPoint* d = static_cast<SkPoint*>(data); |
| 184 *d++ = v->fPoint; |
| 185 return d; |
| 186 } |
| 187 |
| 188 void* emit_triangle(Vertex* v0, Vertex* v1, Vertex* v2, void* data) { |
| 189 #if WIREFRAME |
| 190 data = emit_vertex(v0, data); |
| 191 data = emit_vertex(v1, data); |
| 192 data = emit_vertex(v1, data); |
| 193 data = emit_vertex(v2, data); |
| 194 data = emit_vertex(v2, data); |
| 195 data = emit_vertex(v0, data); |
| 196 #else |
| 197 data = emit_vertex(v0, data); |
| 198 data = emit_vertex(v1, data); |
| 199 data = emit_vertex(v2, data); |
| 200 #endif |
| 201 return data; |
| 202 } |
| 203 |
| 204 /** |
| 205 * An Edge joins a top Vertex to a bottom Vertex. Edge ordering for the list of
"edges above" and |
| 206 * "edge below" a vertex as well as for the active edge list is handled by isLef
tOf()/isRightOf(). |
| 207 * Note that an Edge will give occasionally dist() != 0 for its own endpoints (b
ecause floating |
| 208 * point). For speed, that case is only tested by the callers which require it (
e.g., |
| 209 * cleanup_active_edges()). Edges also handle checking for intersection with oth
er edges. |
| 210 * Currently, this converts the edges to the parametric form, in order to avoid
doing a division |
| 211 * until an intersection has been confirmed. This is slightly slower in the "fou
nd" case, but |
| 212 * a lot faster in the "not found" case. |
| 213 * |
| 214 * The coefficients of the line equation stored in double precision to avoid cat
astrphic |
| 215 * cancellation in the isLeftOf() and isRightOf() checks. Using doubles ensures
that the result is |
| 216 * correct in float, since it's a polynomial of degree 2. The intersect() functi
on, being |
| 217 * degree 5, is still subject to catastrophic cancellation. We deal with that by
assuming its |
| 218 * output may be incorrect, and adjusting the mesh topology to match (see commen
t at the top of |
| 219 * this file). |
| 220 */ |
| 221 |
| 222 struct Edge { |
| 223 Edge(Vertex* top, Vertex* bottom, int winding) |
| 224 : fWinding(winding) |
| 225 , fTop(top) |
| 226 , fBottom(bottom) |
| 227 , fLeft(NULL) |
| 228 , fRight(NULL) |
| 229 , fPrevEdgeAbove(NULL) |
| 230 , fNextEdgeAbove(NULL) |
| 231 , fPrevEdgeBelow(NULL) |
| 232 , fNextEdgeBelow(NULL) |
| 233 , fLeftPoly(NULL) |
| 234 , fRightPoly(NULL) { |
| 235 recompute(); |
| 236 } |
| 237 int fWinding; // 1 == edge goes downward; -1 = edge goes upwar
d. |
| 238 Vertex* fTop; // The top vertex in vertex-sort-order (sweep_lt
). |
| 239 Vertex* fBottom; // The bottom vertex in vertex-sort-order. |
| 240 Edge* fLeft; // The linked list of edges in the active edge l
ist. |
| 241 Edge* fRight; // " |
| 242 Edge* fPrevEdgeAbove; // The linked list of edges in the bottom Vertex
's "edges above". |
| 243 Edge* fNextEdgeAbove; // " |
| 244 Edge* fPrevEdgeBelow; // The linked list of edges in the top Vertex's
"edges below". |
| 245 Edge* fNextEdgeBelow; // " |
| 246 Poly* fLeftPoly; // The Poly to the left of this edge, if any. |
| 247 Poly* fRightPoly; // The Poly to the right of this edge, if any. |
| 248 double fDX; // The line equation for this edge, in implicit
form. |
| 249 double fDY; // fDY * x + fDX * y + fC = 0, for point (x, y)
on the line. |
| 250 double fC; |
| 251 double dist(const SkPoint& p) const { |
| 252 return fDY * p.fX - fDX * p.fY + fC; |
| 253 } |
| 254 bool isRightOf(Vertex* v) const { |
| 255 return dist(v->fPoint) < 0.0; |
| 256 } |
| 257 bool isLeftOf(Vertex* v) const { |
| 258 return dist(v->fPoint) > 0.0; |
| 259 } |
| 260 void recompute() { |
| 261 fDX = static_cast<double>(fBottom->fPoint.fX) - fTop->fPoint.fX; |
| 262 fDY = static_cast<double>(fBottom->fPoint.fY) - fTop->fPoint.fY; |
| 263 fC = static_cast<double>(fTop->fPoint.fY) * fBottom->fPoint.fX - |
| 264 static_cast<double>(fTop->fPoint.fX) * fBottom->fPoint.fY; |
| 265 } |
| 266 bool intersect(const Edge& other, SkPoint* p) { |
| 267 LOG("intersecting %g -> %g with %g -> %g\n", |
| 268 fTop->fID, fBottom->fID, |
| 269 other.fTop->fID, other.fBottom->fID); |
| 270 if (fTop == other.fTop || fBottom == other.fBottom) { |
| 271 return false; |
| 272 } |
| 273 double denom = fDX * other.fDY - fDY * other.fDX; |
| 274 if (denom == 0.0) { |
| 275 return false; |
| 276 } |
| 277 double dx = static_cast<double>(fTop->fPoint.fX) - other.fTop->fPoint.fX
; |
| 278 double dy = static_cast<double>(fTop->fPoint.fY) - other.fTop->fPoint.fY
; |
| 279 double sNumer = dy * other.fDX - dx * other.fDY; |
| 280 double tNumer = dy * fDX - dx * fDY; |
| 281 // If (sNumer / denom) or (tNumer / denom) is not in [0..1], exit early. |
| 282 // This saves us doing the divide below unless absolutely necessary. |
| 283 if (denom > 0.0 ? (sNumer < 0.0 || sNumer > denom || tNumer < 0.0 || tNu
mer > denom) |
| 284 : (sNumer > 0.0 || sNumer < denom || tNumer > 0.0 || tNu
mer < denom)) { |
| 285 return false; |
| 286 } |
| 287 double s = sNumer / denom; |
| 288 SkASSERT(s >= 0.0 && s <= 1.0); |
| 289 p->fX = SkDoubleToScalar(fTop->fPoint.fX + s * fDX); |
| 290 p->fY = SkDoubleToScalar(fTop->fPoint.fY + s * fDY); |
| 291 return true; |
| 292 } |
| 293 bool isActive(Edge** activeEdges) const { |
| 294 return activeEdges && (fLeft || fRight || *activeEdges == this); |
| 295 } |
| 296 }; |
| 297 |
| 298 /*******************************************************************************
********/ |
| 299 |
| 300 struct Poly { |
| 301 Poly(int winding) |
| 302 : fWinding(winding) |
| 303 , fHead(NULL) |
| 304 , fTail(NULL) |
| 305 , fActive(NULL) |
| 306 , fNext(NULL) |
| 307 , fPartner(NULL) |
| 308 , fCount(0) |
| 309 { |
| 310 #if LOGGING_ENABLED |
| 311 static int gID = 0; |
| 312 fID = gID++; |
| 313 LOG("*** created Poly %d\n", fID); |
| 314 #endif |
| 315 } |
| 316 typedef enum { kNeither_Side, kLeft_Side, kRight_Side } Side; |
| 317 struct MonotonePoly { |
| 318 MonotonePoly() |
| 319 : fSide(kNeither_Side) |
| 320 , fHead(NULL) |
| 321 , fTail(NULL) |
| 322 , fPrev(NULL) |
| 323 , fNext(NULL) {} |
| 324 Side fSide; |
| 325 Vertex* fHead; |
| 326 Vertex* fTail; |
| 327 MonotonePoly* fPrev; |
| 328 MonotonePoly* fNext; |
| 329 bool addVertex(Vertex* v, Side side, SkChunkAlloc& alloc) { |
| 330 Vertex* newV = ALLOC_NEW(Vertex, (v->fPoint), alloc); |
| 331 bool done = false; |
| 332 if (fSide == kNeither_Side) { |
| 333 fSide = side; |
| 334 } else { |
| 335 done = side != fSide; |
| 336 } |
| 337 if (fHead == NULL) { |
| 338 fHead = fTail = newV; |
| 339 } else if (fSide == kRight_Side) { |
| 340 newV->fPrev = fTail; |
| 341 fTail->fNext = newV; |
| 342 fTail = newV; |
| 343 } else { |
| 344 newV->fNext = fHead; |
| 345 fHead->fPrev = newV; |
| 346 fHead = newV; |
| 347 } |
| 348 return done; |
| 349 } |
| 350 |
| 351 void* emit(void* data) { |
| 352 Vertex* first = fHead; |
| 353 Vertex* v = first->fNext; |
| 354 while (v != fTail) { |
| 355 SkASSERT(v && v->fPrev && v->fNext); |
| 356 #ifdef SK_DEBUG |
| 357 validate(); |
| 358 #endif |
| 359 Vertex* prev = v->fPrev; |
| 360 Vertex* curr = v; |
| 361 Vertex* next = v->fNext; |
| 362 double ax = static_cast<double>(curr->fPoint.fX) - prev->fPoint.
fX; |
| 363 double ay = static_cast<double>(curr->fPoint.fY) - prev->fPoint.
fY; |
| 364 double bx = static_cast<double>(next->fPoint.fX) - curr->fPoint.
fX; |
| 365 double by = static_cast<double>(next->fPoint.fY) - curr->fPoint.
fY; |
| 366 if (ax * by - ay * bx >= 0.0) { |
| 367 data = emit_triangle(prev, curr, next, data); |
| 368 v->fPrev->fNext = v->fNext; |
| 369 v->fNext->fPrev = v->fPrev; |
| 370 if (v->fPrev == first) { |
| 371 v = v->fNext; |
| 372 } else { |
| 373 v = v->fPrev; |
| 374 } |
| 375 } else { |
| 376 v = v->fNext; |
| 377 SkASSERT(v != fTail); |
| 378 } |
| 379 } |
| 380 return data; |
| 381 } |
| 382 |
| 383 #ifdef SK_DEBUG |
| 384 void validate() { |
| 385 int winding = sweep_lt(fHead->fPoint, fTail->fPoint) ? 1 : -1; |
| 386 Vertex* top = winding < 0 ? fTail : fHead; |
| 387 Vertex* bottom = winding < 0 ? fHead : fTail; |
| 388 Edge e(top, bottom, winding); |
| 389 for (Vertex* v = fHead->fNext; v != fTail; v = v->fNext) { |
| 390 if (fSide == kRight_Side) { |
| 391 SkASSERT(!e.isRightOf(v)); |
| 392 } else if (fSide == Poly::kLeft_Side) { |
| 393 SkASSERT(!e.isLeftOf(v)); |
| 394 } |
| 395 } |
| 396 } |
| 397 #endif |
| 398 }; |
| 399 Poly* addVertex(Vertex* v, Side side, SkChunkAlloc& alloc) { |
| 400 LOG("addVertex() to %d at %g (%g, %g), %s side\n", fID, v->fID, v->fPoin
t.fX, v->fPoint.fY, |
| 401 side == kLeft_Side ? "left" : side == kRight_Side ? "right" : "ne
ither"); |
| 402 Poly* partner = fPartner; |
| 403 Poly* poly = this; |
| 404 if (partner) { |
| 405 fPartner = partner->fPartner = NULL; |
| 406 } |
| 407 if (!fActive) { |
| 408 fActive = ALLOC_NEW(MonotonePoly, (), alloc); |
| 409 } |
| 410 if (fActive->addVertex(v, side, alloc)) { |
| 411 #ifdef SK_DEBUG |
| 412 fActive->validate(); |
| 413 #endif |
| 414 if (fTail) { |
| 415 fActive->fPrev = fTail; |
| 416 fTail->fNext = fActive; |
| 417 fTail = fActive; |
| 418 } else { |
| 419 fHead = fTail = fActive; |
| 420 } |
| 421 if (partner) { |
| 422 partner->addVertex(v, side, alloc); |
| 423 poly = partner; |
| 424 } else { |
| 425 Vertex* prev = fActive->fSide == Poly::kLeft_Side ? |
| 426 fActive->fHead->fNext : fActive->fTail->fPrev; |
| 427 fActive = ALLOC_NEW(MonotonePoly, , alloc); |
| 428 fActive->addVertex(prev, Poly::kNeither_Side, alloc); |
| 429 fActive->addVertex(v, side, alloc); |
| 430 } |
| 431 } |
| 432 fCount++; |
| 433 return poly; |
| 434 } |
| 435 void end(Vertex* v, SkChunkAlloc& alloc) { |
| 436 LOG("end() %d at %g, %g\n", fID, v->fPoint.fX, v->fPoint.fY); |
| 437 if (fPartner) { |
| 438 fPartner = fPartner->fPartner = NULL; |
| 439 } |
| 440 addVertex(v, fActive->fSide == kLeft_Side ? kRight_Side : kLeft_Side, al
loc); |
| 441 } |
| 442 void* emit(void *data) { |
| 443 if (fCount < 3) { |
| 444 return data; |
| 445 } |
| 446 LOG("emit() %d, size %d\n", fID, fCount); |
| 447 for (MonotonePoly* m = fHead; m != NULL; m = m->fNext) { |
| 448 data = m->emit(data); |
| 449 } |
| 450 return data; |
| 451 } |
| 452 int fWinding; |
| 453 MonotonePoly* fHead; |
| 454 MonotonePoly* fTail; |
| 455 MonotonePoly* fActive; |
| 456 Poly* fNext; |
| 457 Poly* fPartner; |
| 458 int fCount; |
| 459 #if LOGGING_ENABLED |
| 460 int fID; |
| 461 #endif |
| 462 }; |
| 463 |
| 464 /*******************************************************************************
********/ |
| 465 |
| 466 bool coincident(const SkPoint& a, const SkPoint& b) { |
| 467 return a == b; |
| 468 } |
| 469 |
| 470 Poly* new_poly(Poly** head, Vertex* v, int winding, SkChunkAlloc& alloc) { |
| 471 Poly* poly = ALLOC_NEW(Poly, (winding), alloc); |
| 472 poly->addVertex(v, Poly::kNeither_Side, alloc); |
| 473 poly->fNext = *head; |
| 474 *head = poly; |
| 475 return poly; |
| 476 } |
| 477 |
| 478 #ifdef SK_DEBUG |
| 479 void validate_edges(Edge* head) { |
| 480 for (Edge* e = head; e != NULL; e = e->fRight) { |
| 481 SkASSERT(e->fTop != e->fBottom); |
| 482 if (e->fLeft) { |
| 483 SkASSERT(e->fLeft->fRight == e); |
| 484 if (sweep_gt(e->fTop->fPoint, e->fLeft->fTop->fPoint)) { |
| 485 SkASSERT(e->fLeft->isLeftOf(e->fTop)); |
| 486 } |
| 487 if (sweep_lt(e->fBottom->fPoint, e->fLeft->fBottom->fPoint)) { |
| 488 SkASSERT(e->fLeft->isLeftOf(e->fBottom)); |
| 489 } |
| 490 } else { |
| 491 SkASSERT(e == head); |
| 492 } |
| 493 if (e->fRight) { |
| 494 SkASSERT(e->fRight->fLeft == e); |
| 495 if (sweep_gt(e->fTop->fPoint, e->fRight->fTop->fPoint)) { |
| 496 SkASSERT(e->fRight->isRightOf(e->fTop)); |
| 497 } |
| 498 if (sweep_lt(e->fBottom->fPoint, e->fRight->fBottom->fPoint)) { |
| 499 SkASSERT(e->fRight->isRightOf(e->fBottom)); |
| 500 } |
| 501 } |
| 502 } |
| 503 } |
| 504 |
| 505 void validate_connectivity(Vertex* v) { |
| 506 for (Edge* e = v->fFirstEdgeAbove; e != NULL; e = e->fNextEdgeAbove) { |
| 507 SkASSERT(e->fBottom == v); |
| 508 if (e->fPrevEdgeAbove) { |
| 509 SkASSERT(e->fPrevEdgeAbove->fNextEdgeAbove == e); |
| 510 SkASSERT(e->fPrevEdgeAbove->isLeftOf(e->fTop)); |
| 511 } else { |
| 512 SkASSERT(e == v->fFirstEdgeAbove); |
| 513 } |
| 514 if (e->fNextEdgeAbove) { |
| 515 SkASSERT(e->fNextEdgeAbove->fPrevEdgeAbove == e); |
| 516 SkASSERT(e->fNextEdgeAbove->isRightOf(e->fTop)); |
| 517 } else { |
| 518 SkASSERT(e == v->fLastEdgeAbove); |
| 519 } |
| 520 } |
| 521 for (Edge* e = v->fFirstEdgeBelow; e != NULL; e = e->fNextEdgeBelow) { |
| 522 SkASSERT(e->fTop == v); |
| 523 if (e->fPrevEdgeBelow) { |
| 524 SkASSERT(e->fPrevEdgeBelow->fNextEdgeBelow == e); |
| 525 SkASSERT(e->fPrevEdgeBelow->isLeftOf(e->fBottom)); |
| 526 } else { |
| 527 SkASSERT(e == v->fFirstEdgeBelow); |
| 528 } |
| 529 if (e->fNextEdgeBelow) { |
| 530 SkASSERT(e->fNextEdgeBelow->fPrevEdgeBelow == e); |
| 531 SkASSERT(e->fNextEdgeBelow->isRightOf(e->fBottom)); |
| 532 } else { |
| 533 SkASSERT(e == v->fLastEdgeBelow); |
| 534 } |
| 535 } |
| 536 } |
| 537 #endif |
| 538 |
| 539 Vertex* append_point_to_contour(const SkPoint& p, Vertex* prev, Vertex** head, |
| 540 SkChunkAlloc& alloc) { |
| 541 Vertex* v = ALLOC_NEW(Vertex, (p), alloc); |
| 542 #if LOGGING_ENABLED |
| 543 static float gID = 0.0f; |
| 544 v->fID = gID++; |
| 545 #endif |
| 546 if (prev) { |
| 547 prev->fNext = v; |
| 548 v->fPrev = prev; |
| 549 } else { |
| 550 *head = v; |
| 551 } |
| 552 return v; |
| 553 } |
| 554 |
| 555 Vertex* generate_quadratic_points(const SkPoint& p0, |
| 556 const SkPoint& p1, |
| 557 const SkPoint& p2, |
| 558 SkScalar tolSqd, |
| 559 Vertex* prev, |
| 560 Vertex** head, |
| 561 int pointsLeft, |
| 562 SkChunkAlloc& alloc) { |
| 563 SkScalar d = p1.distanceToLineSegmentBetweenSqd(p0, p2); |
| 564 if (pointsLeft < 2 || d < tolSqd || !SkScalarIsFinite(d)) { |
| 565 return append_point_to_contour(p2, prev, head, alloc); |
| 566 } |
| 567 |
| 568 const SkPoint q[] = { |
| 569 { SkScalarAve(p0.fX, p1.fX), SkScalarAve(p0.fY, p1.fY) }, |
| 570 { SkScalarAve(p1.fX, p2.fX), SkScalarAve(p1.fY, p2.fY) }, |
| 571 }; |
| 572 const SkPoint r = { SkScalarAve(q[0].fX, q[1].fX), SkScalarAve(q[0].fY, q[1]
.fY) }; |
| 573 |
| 574 pointsLeft >>= 1; |
| 575 prev = generate_quadratic_points(p0, q[0], r, tolSqd, prev, head, pointsLeft
, alloc); |
| 576 prev = generate_quadratic_points(r, q[1], p2, tolSqd, prev, head, pointsLeft
, alloc); |
| 577 return prev; |
| 578 } |
| 579 |
| 580 Vertex* generate_cubic_points(const SkPoint& p0, |
| 581 const SkPoint& p1, |
| 582 const SkPoint& p2, |
| 583 const SkPoint& p3, |
| 584 SkScalar tolSqd, |
| 585 Vertex* prev, |
| 586 Vertex** head, |
| 587 int pointsLeft, |
| 588 SkChunkAlloc& alloc) { |
| 589 SkScalar d1 = p1.distanceToLineSegmentBetweenSqd(p0, p3); |
| 590 SkScalar d2 = p2.distanceToLineSegmentBetweenSqd(p0, p3); |
| 591 if (pointsLeft < 2 || (d1 < tolSqd && d2 < tolSqd) || |
| 592 !SkScalarIsFinite(d1) || !SkScalarIsFinite(d2)) { |
| 593 return append_point_to_contour(p3, prev, head, alloc); |
| 594 } |
| 595 const SkPoint q[] = { |
| 596 { SkScalarAve(p0.fX, p1.fX), SkScalarAve(p0.fY, p1.fY) }, |
| 597 { SkScalarAve(p1.fX, p2.fX), SkScalarAve(p1.fY, p2.fY) }, |
| 598 { SkScalarAve(p2.fX, p3.fX), SkScalarAve(p2.fY, p3.fY) } |
| 599 }; |
| 600 const SkPoint r[] = { |
| 601 { SkScalarAve(q[0].fX, q[1].fX), SkScalarAve(q[0].fY, q[1].fY) }, |
| 602 { SkScalarAve(q[1].fX, q[2].fX), SkScalarAve(q[1].fY, q[2].fY) } |
| 603 }; |
| 604 const SkPoint s = { SkScalarAve(r[0].fX, r[1].fX), SkScalarAve(r[0].fY, r[1]
.fY) }; |
| 605 pointsLeft >>= 1; |
| 606 prev = generate_cubic_points(p0, q[0], r[0], s, tolSqd, prev, head, pointsLe
ft, alloc); |
| 607 prev = generate_cubic_points(s, r[1], q[2], p3, tolSqd, prev, head, pointsLe
ft, alloc); |
| 608 return prev; |
| 609 } |
| 610 |
| 611 // Stage 1: convert the input path to a set of linear contours (linked list of V
ertices). |
| 612 |
| 613 void path_to_contours(const SkPath& path, SkScalar tolerance, const SkRect& clip
Bounds, |
| 614 Vertex** contours, SkChunkAlloc& alloc) { |
| 615 |
| 616 SkScalar toleranceSqd = tolerance * tolerance; |
| 617 |
| 618 SkPoint pts[4]; |
| 619 bool done = false; |
| 620 SkPath::Iter iter(path, false); |
| 621 Vertex* prev = NULL; |
| 622 Vertex* head = NULL; |
| 623 if (path.isInverseFillType()) { |
| 624 SkPoint quad[4]; |
| 625 clipBounds.toQuad(quad); |
| 626 for (int i = 3; i >= 0; i--) { |
| 627 prev = append_point_to_contour(quad[i], prev, &head, alloc); |
| 628 } |
| 629 head->fPrev = prev; |
| 630 prev->fNext = head; |
| 631 *contours++ = head; |
| 632 head = prev = NULL; |
| 633 } |
| 634 SkAutoConicToQuads converter; |
| 635 while (!done) { |
| 636 SkPath::Verb verb = iter.next(pts); |
| 637 switch (verb) { |
| 638 case SkPath::kConic_Verb: { |
| 639 SkScalar weight = iter.conicWeight(); |
| 640 const SkPoint* quadPts = converter.computeQuads(pts, weight, tol
eranceSqd); |
| 641 for (int i = 0; i < converter.countQuads(); ++i) { |
| 642 int pointsLeft = GrPathUtils::quadraticPointCount(quadPts, t
oleranceSqd); |
| 643 prev = generate_quadratic_points(quadPts[0], quadPts[1], qua
dPts[2], |
| 644 toleranceSqd, prev, &head,
pointsLeft, alloc); |
| 645 quadPts += 2; |
| 646 } |
| 647 break; |
| 648 } |
| 649 case SkPath::kMove_Verb: |
| 650 if (head) { |
| 651 head->fPrev = prev; |
| 652 prev->fNext = head; |
| 653 *contours++ = head; |
| 654 } |
| 655 head = prev = NULL; |
| 656 prev = append_point_to_contour(pts[0], prev, &head, alloc); |
| 657 break; |
| 658 case SkPath::kLine_Verb: { |
| 659 prev = append_point_to_contour(pts[1], prev, &head, alloc); |
| 660 break; |
| 661 } |
| 662 case SkPath::kQuad_Verb: { |
| 663 int pointsLeft = GrPathUtils::quadraticPointCount(pts, tolerance
Sqd); |
| 664 prev = generate_quadratic_points(pts[0], pts[1], pts[2], toleran
ceSqd, prev, |
| 665 &head, pointsLeft, alloc); |
| 666 break; |
| 667 } |
| 668 case SkPath::kCubic_Verb: { |
| 669 int pointsLeft = GrPathUtils::cubicPointCount(pts, toleranceSqd)
; |
| 670 prev = generate_cubic_points(pts[0], pts[1], pts[2], pts[3], |
| 671 toleranceSqd, prev, &head, pointsLeft, alloc); |
| 672 break; |
| 673 } |
| 674 case SkPath::kClose_Verb: |
| 675 if (head) { |
| 676 head->fPrev = prev; |
| 677 prev->fNext = head; |
| 678 *contours++ = head; |
| 679 } |
| 680 head = prev = NULL; |
| 681 break; |
| 682 case SkPath::kDone_Verb: |
| 683 if (head) { |
| 684 head->fPrev = prev; |
| 685 prev->fNext = head; |
| 686 *contours++ = head; |
| 687 } |
| 688 done = true; |
| 689 break; |
| 690 } |
| 691 } |
| 692 } |
| 693 |
| 694 inline bool apply_fill_type(SkPath::FillType fillType, int winding) { |
| 695 switch (fillType) { |
| 696 case SkPath::kWinding_FillType: |
| 697 return winding != 0; |
| 698 case SkPath::kEvenOdd_FillType: |
| 699 return (winding & 1) != 0; |
| 700 case SkPath::kInverseWinding_FillType: |
| 701 return winding == 1; |
| 702 case SkPath::kInverseEvenOdd_FillType: |
| 703 return (winding & 1) == 1; |
| 704 default: |
| 705 SkASSERT(false); |
| 706 return false; |
| 707 } |
| 708 } |
| 709 |
| 710 Edge* new_edge(Vertex* prev, Vertex* next, SkChunkAlloc& alloc) { |
| 711 int winding = sweep_lt(prev->fPoint, next->fPoint) ? 1 : -1; |
| 712 Vertex* top = winding < 0 ? next : prev; |
| 713 Vertex* bottom = winding < 0 ? prev : next; |
| 714 return ALLOC_NEW(Edge, (top, bottom, winding), alloc); |
| 715 } |
| 716 |
| 717 void remove_edge(Edge* edge, Edge** head) { |
| 718 LOG("removing edge %g -> %g\n", edge->fTop->fID, edge->fBottom->fID); |
| 719 SkASSERT(edge->isActive(head)); |
| 720 remove<Edge, &Edge::fLeft, &Edge::fRight>(edge, head, NULL); |
| 721 } |
| 722 |
| 723 void insert_edge(Edge* edge, Edge* prev, Edge** head) { |
| 724 LOG("inserting edge %g -> %g\n", edge->fTop->fID, edge->fBottom->fID); |
| 725 SkASSERT(!edge->isActive(head)); |
| 726 Edge* next = prev ? prev->fRight : *head; |
| 727 insert<Edge, &Edge::fLeft, &Edge::fRight>(edge, prev, next, head, NULL); |
| 728 } |
| 729 |
| 730 void find_enclosing_edges(Vertex* v, Edge* head, Edge** left, Edge** right) { |
| 731 if (v->fFirstEdgeAbove) { |
| 732 *left = v->fFirstEdgeAbove->fLeft; |
| 733 *right = v->fLastEdgeAbove->fRight; |
| 734 return; |
| 735 } |
| 736 Edge* prev = NULL; |
| 737 Edge* next; |
| 738 for (next = head; next != NULL; next = next->fRight) { |
| 739 if (next->isRightOf(v)) { |
| 740 break; |
| 741 } |
| 742 prev = next; |
| 743 } |
| 744 *left = prev; |
| 745 *right = next; |
| 746 return; |
| 747 } |
| 748 |
| 749 void find_enclosing_edges(Edge* edge, Edge* head, Edge** left, Edge** right) { |
| 750 Edge* prev = NULL; |
| 751 Edge* next; |
| 752 for (next = head; next != NULL; next = next->fRight) { |
| 753 if ((sweep_gt(edge->fTop->fPoint, next->fTop->fPoint) && next->isRightOf
(edge->fTop)) || |
| 754 (sweep_gt(next->fTop->fPoint, edge->fTop->fPoint) && edge->isLeftOf(
next->fTop)) || |
| 755 (sweep_lt(edge->fBottom->fPoint, next->fBottom->fPoint) && |
| 756 next->isRightOf(edge->fBottom)) || |
| 757 (sweep_lt(next->fBottom->fPoint, edge->fBottom->fPoint) && |
| 758 edge->isLeftOf(next->fBottom))) { |
| 759 break; |
| 760 } |
| 761 prev = next; |
| 762 } |
| 763 *left = prev; |
| 764 *right = next; |
| 765 return; |
| 766 } |
| 767 |
| 768 void fix_active_state(Edge* edge, Edge** activeEdges) { |
| 769 if (edge->isActive(activeEdges)) { |
| 770 if (edge->fBottom->fProcessed || !edge->fTop->fProcessed) { |
| 771 remove_edge(edge, activeEdges); |
| 772 } |
| 773 } else if (edge->fTop->fProcessed && !edge->fBottom->fProcessed) { |
| 774 Edge* left; |
| 775 Edge* right; |
| 776 find_enclosing_edges(edge, *activeEdges, &left, &right); |
| 777 insert_edge(edge, left, activeEdges); |
| 778 } |
| 779 } |
| 780 |
| 781 void insert_edge_above(Edge* edge, Vertex* v) { |
| 782 if (edge->fTop->fPoint == edge->fBottom->fPoint || |
| 783 sweep_gt(edge->fTop->fPoint, edge->fBottom->fPoint)) { |
| 784 SkASSERT(false); |
| 785 return; |
| 786 } |
| 787 LOG("insert edge (%g -> %g) above vertex %g\n", edge->fTop->fID, edge->fBott
om->fID, v->fID); |
| 788 Edge* prev = NULL; |
| 789 Edge* next; |
| 790 for (next = v->fFirstEdgeAbove; next; next = next->fNextEdgeAbove) { |
| 791 if (next->isRightOf(edge->fTop)) { |
| 792 break; |
| 793 } |
| 794 prev = next; |
| 795 } |
| 796 insert<Edge, &Edge::fPrevEdgeAbove, &Edge::fNextEdgeAbove>( |
| 797 edge, prev, next, &v->fFirstEdgeAbove, &v->fLastEdgeAbove); |
| 798 } |
| 799 |
| 800 void insert_edge_below(Edge* edge, Vertex* v) { |
| 801 if (edge->fTop->fPoint == edge->fBottom->fPoint || |
| 802 sweep_gt(edge->fTop->fPoint, edge->fBottom->fPoint)) { |
| 803 SkASSERT(false); |
| 804 return; |
| 805 } |
| 806 LOG("insert edge (%g -> %g) below vertex %g\n", edge->fTop->fID, edge->fBott
om->fID, v->fID); |
| 807 Edge* prev = NULL; |
| 808 Edge* next; |
| 809 for (next = v->fFirstEdgeBelow; next; next = next->fNextEdgeBelow) { |
| 810 if (next->isRightOf(edge->fBottom)) { |
| 811 break; |
| 812 } |
| 813 prev = next; |
| 814 } |
| 815 insert<Edge, &Edge::fPrevEdgeBelow, &Edge::fNextEdgeBelow>( |
| 816 edge, prev, next, &v->fFirstEdgeBelow, &v->fLastEdgeBelow); |
| 817 } |
| 818 |
| 819 void remove_edge_above(Edge* edge) { |
| 820 LOG("removing edge (%g -> %g) above vertex %g\n", edge->fTop->fID, edge->fBo
ttom->fID, |
| 821 edge->fBottom->fID); |
| 822 remove<Edge, &Edge::fPrevEdgeAbove, &Edge::fNextEdgeAbove>( |
| 823 edge, &edge->fBottom->fFirstEdgeAbove, &edge->fBottom->fLastEdgeAbove); |
| 824 } |
| 825 |
| 826 void remove_edge_below(Edge* edge) { |
| 827 LOG("removing edge (%g -> %g) below vertex %g\n", edge->fTop->fID, edge->fBo
ttom->fID, |
| 828 edge->fTop->fID); |
| 829 remove<Edge, &Edge::fPrevEdgeBelow, &Edge::fNextEdgeBelow>( |
| 830 edge, &edge->fTop->fFirstEdgeBelow, &edge->fTop->fLastEdgeBelow); |
| 831 } |
| 832 |
| 833 void erase_edge_if_zero_winding(Edge* edge, Edge** head) { |
| 834 if (edge->fWinding != 0) { |
| 835 return; |
| 836 } |
| 837 LOG("erasing edge (%g -> %g)\n", edge->fTop->fID, edge->fBottom->fID); |
| 838 remove_edge_above(edge); |
| 839 remove_edge_below(edge); |
| 840 if (edge->isActive(head)) { |
| 841 remove_edge(edge, head); |
| 842 } |
| 843 } |
| 844 |
| 845 void merge_collinear_edges(Edge* edge, Edge** activeEdges); |
| 846 |
| 847 void set_top(Edge* edge, Vertex* v, Edge** activeEdges) { |
| 848 remove_edge_below(edge); |
| 849 edge->fTop = v; |
| 850 edge->recompute(); |
| 851 insert_edge_below(edge, v); |
| 852 fix_active_state(edge, activeEdges); |
| 853 merge_collinear_edges(edge, activeEdges); |
| 854 } |
| 855 |
| 856 void set_bottom(Edge* edge, Vertex* v, Edge** activeEdges) { |
| 857 remove_edge_above(edge); |
| 858 edge->fBottom = v; |
| 859 edge->recompute(); |
| 860 insert_edge_above(edge, v); |
| 861 fix_active_state(edge, activeEdges); |
| 862 merge_collinear_edges(edge, activeEdges); |
| 863 } |
| 864 |
| 865 void merge_edges_above(Edge* edge, Edge* other, Edge** activeEdges) { |
| 866 if (coincident(edge->fTop->fPoint, other->fTop->fPoint)) { |
| 867 LOG("merging coincident above edges (%g, %g) -> (%g, %g)\n", |
| 868 edge->fTop->fPoint.fX, edge->fTop->fPoint.fY, |
| 869 edge->fBottom->fPoint.fX, edge->fBottom->fPoint.fY); |
| 870 other->fWinding += edge->fWinding; |
| 871 erase_edge_if_zero_winding(other, activeEdges); |
| 872 edge->fWinding = 0; |
| 873 erase_edge_if_zero_winding(edge, activeEdges); |
| 874 } else if (sweep_lt(edge->fTop->fPoint, other->fTop->fPoint)) { |
| 875 other->fWinding += edge->fWinding; |
| 876 erase_edge_if_zero_winding(other, activeEdges); |
| 877 set_bottom(edge, other->fTop, activeEdges); |
| 878 } else { |
| 879 edge->fWinding += other->fWinding; |
| 880 erase_edge_if_zero_winding(edge, activeEdges); |
| 881 set_bottom(other, edge->fTop, activeEdges); |
| 882 } |
| 883 } |
| 884 |
| 885 void merge_edges_below(Edge* edge, Edge* other, Edge** activeEdges) { |
| 886 if (coincident(edge->fBottom->fPoint, other->fBottom->fPoint)) { |
| 887 LOG("merging coincident below edges (%g, %g) -> (%g, %g)\n", |
| 888 edge->fTop->fPoint.fX, edge->fTop->fPoint.fY, |
| 889 edge->fBottom->fPoint.fX, edge->fBottom->fPoint.fY); |
| 890 other->fWinding += edge->fWinding; |
| 891 erase_edge_if_zero_winding(other, activeEdges); |
| 892 edge->fWinding = 0; |
| 893 erase_edge_if_zero_winding(edge, activeEdges); |
| 894 } else if (sweep_lt(edge->fBottom->fPoint, other->fBottom->fPoint)) { |
| 895 edge->fWinding += other->fWinding; |
| 896 erase_edge_if_zero_winding(edge, activeEdges); |
| 897 set_top(other, edge->fBottom, activeEdges); |
| 898 } else { |
| 899 other->fWinding += edge->fWinding; |
| 900 erase_edge_if_zero_winding(other, activeEdges); |
| 901 set_top(edge, other->fBottom, activeEdges); |
| 902 } |
| 903 } |
| 904 |
| 905 void merge_collinear_edges(Edge* edge, Edge** activeEdges) { |
| 906 if (edge->fPrevEdgeAbove && (edge->fTop == edge->fPrevEdgeAbove->fTop || |
| 907 !edge->fPrevEdgeAbove->isLeftOf(edge->fTop))) { |
| 908 merge_edges_above(edge, edge->fPrevEdgeAbove, activeEdges); |
| 909 } else if (edge->fNextEdgeAbove && (edge->fTop == edge->fNextEdgeAbove->fTop
|| |
| 910 !edge->isLeftOf(edge->fNextEdgeAbove->fT
op))) { |
| 911 merge_edges_above(edge, edge->fNextEdgeAbove, activeEdges); |
| 912 } |
| 913 if (edge->fPrevEdgeBelow && (edge->fBottom == edge->fPrevEdgeBelow->fBottom
|| |
| 914 !edge->fPrevEdgeBelow->isLeftOf(edge->fBottom))
) { |
| 915 merge_edges_below(edge, edge->fPrevEdgeBelow, activeEdges); |
| 916 } else if (edge->fNextEdgeBelow && (edge->fBottom == edge->fNextEdgeBelow->f
Bottom || |
| 917 !edge->isLeftOf(edge->fNextEdgeBelow->fB
ottom))) { |
| 918 merge_edges_below(edge, edge->fNextEdgeBelow, activeEdges); |
| 919 } |
| 920 } |
| 921 |
| 922 void split_edge(Edge* edge, Vertex* v, Edge** activeEdges, SkChunkAlloc& alloc); |
| 923 |
| 924 void cleanup_active_edges(Edge* edge, Edge** activeEdges, SkChunkAlloc& alloc) { |
| 925 Vertex* top = edge->fTop; |
| 926 Vertex* bottom = edge->fBottom; |
| 927 if (edge->fLeft) { |
| 928 Vertex* leftTop = edge->fLeft->fTop; |
| 929 Vertex* leftBottom = edge->fLeft->fBottom; |
| 930 if (sweep_gt(top->fPoint, leftTop->fPoint) && !edge->fLeft->isLeftOf(top
)) { |
| 931 split_edge(edge->fLeft, edge->fTop, activeEdges, alloc); |
| 932 } else if (sweep_gt(leftTop->fPoint, top->fPoint) && !edge->isRightOf(le
ftTop)) { |
| 933 split_edge(edge, leftTop, activeEdges, alloc); |
| 934 } else if (sweep_lt(bottom->fPoint, leftBottom->fPoint) && !edge->fLeft-
>isLeftOf(bottom)) { |
| 935 split_edge(edge->fLeft, bottom, activeEdges, alloc); |
| 936 } else if (sweep_lt(leftBottom->fPoint, bottom->fPoint) && !edge->isRigh
tOf(leftBottom)) { |
| 937 split_edge(edge, leftBottom, activeEdges, alloc); |
| 938 } |
| 939 } |
| 940 if (edge->fRight) { |
| 941 Vertex* rightTop = edge->fRight->fTop; |
| 942 Vertex* rightBottom = edge->fRight->fBottom; |
| 943 if (sweep_gt(top->fPoint, rightTop->fPoint) && !edge->fRight->isRightOf(
top)) { |
| 944 split_edge(edge->fRight, top, activeEdges, alloc); |
| 945 } else if (sweep_gt(rightTop->fPoint, top->fPoint) && !edge->isLeftOf(ri
ghtTop)) { |
| 946 split_edge(edge, rightTop, activeEdges, alloc); |
| 947 } else if (sweep_lt(bottom->fPoint, rightBottom->fPoint) && |
| 948 !edge->fRight->isRightOf(bottom)) { |
| 949 split_edge(edge->fRight, bottom, activeEdges, alloc); |
| 950 } else if (sweep_lt(rightBottom->fPoint, bottom->fPoint) && |
| 951 !edge->isLeftOf(rightBottom)) { |
| 952 split_edge(edge, rightBottom, activeEdges, alloc); |
| 953 } |
| 954 } |
| 955 } |
| 956 |
| 957 void split_edge(Edge* edge, Vertex* v, Edge** activeEdges, SkChunkAlloc& alloc)
{ |
| 958 LOG("splitting edge (%g -> %g) at vertex %g (%g, %g)\n", |
| 959 edge->fTop->fID, edge->fBottom->fID, |
| 960 v->fID, v->fPoint.fX, v->fPoint.fY); |
| 961 Edge* newEdge = ALLOC_NEW(Edge, (v, edge->fBottom, edge->fWinding), alloc); |
| 962 insert_edge_below(newEdge, v); |
| 963 insert_edge_above(newEdge, edge->fBottom); |
| 964 set_bottom(edge, v, activeEdges); |
| 965 cleanup_active_edges(edge, activeEdges, alloc); |
| 966 fix_active_state(newEdge, activeEdges); |
| 967 merge_collinear_edges(newEdge, activeEdges); |
| 968 } |
| 969 |
| 970 void merge_vertices(Vertex* src, Vertex* dst, Vertex** head, SkChunkAlloc& alloc
) { |
| 971 LOG("found coincident verts at %g, %g; merging %g into %g\n", src->fPoint.fX
, src->fPoint.fY, |
| 972 src->fID, dst->fID); |
| 973 for (Edge* edge = src->fFirstEdgeAbove; edge;) { |
| 974 Edge* next = edge->fNextEdgeAbove; |
| 975 set_bottom(edge, dst, NULL); |
| 976 edge = next; |
| 977 } |
| 978 for (Edge* edge = src->fFirstEdgeBelow; edge;) { |
| 979 Edge* next = edge->fNextEdgeBelow; |
| 980 set_top(edge, dst, NULL); |
| 981 edge = next; |
| 982 } |
| 983 remove<Vertex, &Vertex::fPrev, &Vertex::fNext>(src, head, NULL); |
| 984 } |
| 985 |
| 986 Vertex* check_for_intersection(Edge* edge, Edge* other, Edge** activeEdges, SkCh
unkAlloc& alloc) { |
| 987 SkPoint p; |
| 988 if (!edge || !other) { |
| 989 return NULL; |
| 990 } |
| 991 if (edge->intersect(*other, &p)) { |
| 992 Vertex* v; |
| 993 LOG("found intersection, pt is %g, %g\n", p.fX, p.fY); |
| 994 if (p == edge->fTop->fPoint || sweep_lt(p, edge->fTop->fPoint)) { |
| 995 split_edge(other, edge->fTop, activeEdges, alloc); |
| 996 v = edge->fTop; |
| 997 } else if (p == edge->fBottom->fPoint || sweep_gt(p, edge->fBottom->fPoi
nt)) { |
| 998 split_edge(other, edge->fBottom, activeEdges, alloc); |
| 999 v = edge->fBottom; |
| 1000 } else if (p == other->fTop->fPoint || sweep_lt(p, other->fTop->fPoint))
{ |
| 1001 split_edge(edge, other->fTop, activeEdges, alloc); |
| 1002 v = other->fTop; |
| 1003 } else if (p == other->fBottom->fPoint || sweep_gt(p, other->fBottom->fP
oint)) { |
| 1004 split_edge(edge, other->fBottom, activeEdges, alloc); |
| 1005 v = other->fBottom; |
| 1006 } else { |
| 1007 Vertex* nextV = edge->fTop; |
| 1008 while (sweep_lt(p, nextV->fPoint)) { |
| 1009 nextV = nextV->fPrev; |
| 1010 } |
| 1011 while (sweep_lt(nextV->fPoint, p)) { |
| 1012 nextV = nextV->fNext; |
| 1013 } |
| 1014 Vertex* prevV = nextV->fPrev; |
| 1015 if (coincident(prevV->fPoint, p)) { |
| 1016 v = prevV; |
| 1017 } else if (coincident(nextV->fPoint, p)) { |
| 1018 v = nextV; |
| 1019 } else { |
| 1020 v = ALLOC_NEW(Vertex, (p), alloc); |
| 1021 LOG("inserting between %g (%g, %g) and %g (%g, %g)\n", |
| 1022 prevV->fID, prevV->fPoint.fX, prevV->fPoint.fY, |
| 1023 nextV->fID, nextV->fPoint.fX, nextV->fPoint.fY); |
| 1024 #if LOGGING_ENABLED |
| 1025 v->fID = (nextV->fID + prevV->fID) * 0.5f; |
| 1026 #endif |
| 1027 v->fPrev = prevV; |
| 1028 v->fNext = nextV; |
| 1029 prevV->fNext = v; |
| 1030 nextV->fPrev = v; |
| 1031 } |
| 1032 split_edge(edge, v, activeEdges, alloc); |
| 1033 split_edge(other, v, activeEdges, alloc); |
| 1034 } |
| 1035 #ifdef SK_DEBUG |
| 1036 validate_connectivity(v); |
| 1037 #endif |
| 1038 return v; |
| 1039 } |
| 1040 return NULL; |
| 1041 } |
| 1042 |
| 1043 void sanitize_contours(Vertex** contours, int contourCnt) { |
| 1044 for (int i = 0; i < contourCnt; ++i) { |
| 1045 SkASSERT(contours[i]); |
| 1046 for (Vertex* v = contours[i];;) { |
| 1047 if (coincident(v->fPrev->fPoint, v->fPoint)) { |
| 1048 LOG("vertex %g,%g coincident; removing\n", v->fPoint.fX, v->fPoi
nt.fY); |
| 1049 if (v->fPrev == v) { |
| 1050 contours[i] = NULL; |
| 1051 break; |
| 1052 } |
| 1053 v->fPrev->fNext = v->fNext; |
| 1054 v->fNext->fPrev = v->fPrev; |
| 1055 if (contours[i] == v) { |
| 1056 contours[i] = v->fNext; |
| 1057 } |
| 1058 v = v->fPrev; |
| 1059 } else { |
| 1060 v = v->fNext; |
| 1061 if (v == contours[i]) break; |
| 1062 } |
| 1063 } |
| 1064 } |
| 1065 } |
| 1066 |
| 1067 void merge_coincident_vertices(Vertex** vertices, SkChunkAlloc& alloc) { |
| 1068 for (Vertex* v = (*vertices)->fNext; v != NULL; v = v->fNext) { |
| 1069 if (sweep_lt(v->fPoint, v->fPrev->fPoint)) { |
| 1070 v->fPoint = v->fPrev->fPoint; |
| 1071 } |
| 1072 if (coincident(v->fPrev->fPoint, v->fPoint)) { |
| 1073 merge_vertices(v->fPrev, v, vertices, alloc); |
| 1074 } |
| 1075 } |
| 1076 } |
| 1077 |
| 1078 // Stage 2: convert the contours to a mesh of edges connecting the vertices. |
| 1079 |
| 1080 Vertex* build_edges(Vertex** contours, int contourCnt, SkChunkAlloc& alloc) { |
| 1081 Vertex* vertices = NULL; |
| 1082 Vertex* prev = NULL; |
| 1083 for (int i = 0; i < contourCnt; ++i) { |
| 1084 for (Vertex* v = contours[i]; v != NULL;) { |
| 1085 Vertex* vNext = v->fNext; |
| 1086 Edge* edge = new_edge(v->fPrev, v, alloc); |
| 1087 if (edge->fWinding > 0) { |
| 1088 insert_edge_below(edge, v->fPrev); |
| 1089 insert_edge_above(edge, v); |
| 1090 } else { |
| 1091 insert_edge_below(edge, v); |
| 1092 insert_edge_above(edge, v->fPrev); |
| 1093 } |
| 1094 merge_collinear_edges(edge, NULL); |
| 1095 if (prev) { |
| 1096 prev->fNext = v; |
| 1097 v->fPrev = prev; |
| 1098 } else { |
| 1099 vertices = v; |
| 1100 } |
| 1101 prev = v; |
| 1102 v = vNext; |
| 1103 if (v == contours[i]) break; |
| 1104 } |
| 1105 } |
| 1106 if (prev) { |
| 1107 prev->fNext = vertices->fPrev = NULL; |
| 1108 } |
| 1109 return vertices; |
| 1110 } |
| 1111 |
| 1112 // Stage 3: sort the vertices by increasing Y (or X if SWEEP_IN_X is on). |
| 1113 |
| 1114 Vertex* sorted_merge(Vertex* a, Vertex* b); |
| 1115 |
| 1116 void front_back_split(Vertex* v, Vertex** pFront, Vertex** pBack) { |
| 1117 Vertex* fast; |
| 1118 Vertex* slow; |
| 1119 if (!v || !v->fNext) { |
| 1120 *pFront = v; |
| 1121 *pBack = NULL; |
| 1122 } else { |
| 1123 slow = v; |
| 1124 fast = v->fNext; |
| 1125 |
| 1126 while (fast != NULL) { |
| 1127 fast = fast->fNext; |
| 1128 if (fast != NULL) { |
| 1129 slow = slow->fNext; |
| 1130 fast = fast->fNext; |
| 1131 } |
| 1132 } |
| 1133 |
| 1134 *pFront = v; |
| 1135 *pBack = slow->fNext; |
| 1136 slow->fNext->fPrev = NULL; |
| 1137 slow->fNext = NULL; |
| 1138 } |
| 1139 } |
| 1140 |
| 1141 void merge_sort(Vertex** head) { |
| 1142 if (!*head || !(*head)->fNext) { |
| 1143 return; |
| 1144 } |
| 1145 |
| 1146 Vertex* a; |
| 1147 Vertex* b; |
| 1148 front_back_split(*head, &a, &b); |
| 1149 |
| 1150 merge_sort(&a); |
| 1151 merge_sort(&b); |
| 1152 |
| 1153 *head = sorted_merge(a, b); |
| 1154 } |
| 1155 |
| 1156 Vertex* sorted_merge(Vertex* a, Vertex* b) { |
| 1157 if (!a) { |
| 1158 return b; |
| 1159 } else if (!b) { |
| 1160 return a; |
| 1161 } |
| 1162 |
| 1163 Vertex* result = NULL; |
| 1164 |
| 1165 if (sweep_lt(a->fPoint, b->fPoint)) { |
| 1166 result = a; |
| 1167 result->fNext = sorted_merge(a->fNext, b); |
| 1168 } else { |
| 1169 result = b; |
| 1170 result->fNext = sorted_merge(a, b->fNext); |
| 1171 } |
| 1172 result->fNext->fPrev = result; |
| 1173 return result; |
| 1174 } |
| 1175 |
| 1176 // Stage 4: Simplify the mesh by inserting new vertices at intersecting edges. |
| 1177 |
| 1178 void simplify(Vertex* vertices, SkChunkAlloc& alloc) { |
| 1179 LOG("simplifying complex polygons\n"); |
| 1180 Edge* activeEdges = NULL; |
| 1181 for (Vertex* v = vertices; v != NULL; v = v->fNext) { |
| 1182 if (!v->fFirstEdgeAbove && !v->fFirstEdgeBelow) { |
| 1183 continue; |
| 1184 } |
| 1185 #if LOGGING_ENABLED |
| 1186 LOG("\nvertex %g: (%g,%g)\n", v->fID, v->fPoint.fX, v->fPoint.fY); |
| 1187 #endif |
| 1188 #ifdef SK_DEBUG |
| 1189 validate_connectivity(v); |
| 1190 #endif |
| 1191 Edge* leftEnclosingEdge = NULL; |
| 1192 Edge* rightEnclosingEdge = NULL; |
| 1193 bool restartChecks; |
| 1194 do { |
| 1195 restartChecks = false; |
| 1196 find_enclosing_edges(v, activeEdges, &leftEnclosingEdge, &rightEnclo
singEdge); |
| 1197 if (v->fFirstEdgeBelow) { |
| 1198 for (Edge* edge = v->fFirstEdgeBelow; edge != NULL; edge = edge-
>fNextEdgeBelow) { |
| 1199 if (check_for_intersection(edge, leftEnclosingEdge, &activeE
dges, alloc)) { |
| 1200 restartChecks = true; |
| 1201 break; |
| 1202 } |
| 1203 if (check_for_intersection(edge, rightEnclosingEdge, &active
Edges, alloc)) { |
| 1204 restartChecks = true; |
| 1205 break; |
| 1206 } |
| 1207 } |
| 1208 } else { |
| 1209 if (Vertex* pv = check_for_intersection(leftEnclosingEdge, right
EnclosingEdge, |
| 1210 &activeEdges, alloc)) { |
| 1211 if (sweep_lt(pv->fPoint, v->fPoint)) { |
| 1212 v = pv; |
| 1213 } |
| 1214 restartChecks = true; |
| 1215 } |
| 1216 |
| 1217 } |
| 1218 } while (restartChecks); |
| 1219 SkASSERT(!leftEnclosingEdge || leftEnclosingEdge->isLeftOf(v)); |
| 1220 SkASSERT(!rightEnclosingEdge || rightEnclosingEdge->isRightOf(v)); |
| 1221 #ifdef SK_DEBUG |
| 1222 validate_edges(activeEdges); |
| 1223 #endif |
| 1224 for (Edge* e = v->fFirstEdgeAbove; e; e = e->fNextEdgeAbove) { |
| 1225 remove_edge(e, &activeEdges); |
| 1226 } |
| 1227 Edge* leftEdge = leftEnclosingEdge; |
| 1228 for (Edge* e = v->fFirstEdgeBelow; e; e = e->fNextEdgeBelow) { |
| 1229 insert_edge(e, leftEdge, &activeEdges); |
| 1230 leftEdge = e; |
| 1231 } |
| 1232 v->fProcessed = true; |
| 1233 } |
| 1234 } |
| 1235 |
| 1236 // Stage 5: Tessellate the simplified mesh into monotone polygons. |
| 1237 |
| 1238 Poly* tessellate(Vertex* vertices, SkChunkAlloc& alloc) { |
| 1239 LOG("tessellating simple polygons\n"); |
| 1240 Edge* activeEdges = NULL; |
| 1241 Poly* polys = NULL; |
| 1242 for (Vertex* v = vertices; v != NULL; v = v->fNext) { |
| 1243 if (!v->fFirstEdgeAbove && !v->fFirstEdgeBelow) { |
| 1244 continue; |
| 1245 } |
| 1246 #if LOGGING_ENABLED |
| 1247 LOG("\nvertex %g: (%g,%g)\n", v->fID, v->fPoint.fX, v->fPoint.fY); |
| 1248 #endif |
| 1249 #ifdef SK_DEBUG |
| 1250 validate_connectivity(v); |
| 1251 #endif |
| 1252 Edge* leftEnclosingEdge = NULL; |
| 1253 Edge* rightEnclosingEdge = NULL; |
| 1254 find_enclosing_edges(v, activeEdges, &leftEnclosingEdge, &rightEnclosing
Edge); |
| 1255 SkASSERT(!leftEnclosingEdge || leftEnclosingEdge->isLeftOf(v)); |
| 1256 SkASSERT(!rightEnclosingEdge || rightEnclosingEdge->isRightOf(v)); |
| 1257 #ifdef SK_DEBUG |
| 1258 validate_edges(activeEdges); |
| 1259 #endif |
| 1260 Poly* leftPoly = NULL; |
| 1261 Poly* rightPoly = NULL; |
| 1262 if (v->fFirstEdgeAbove) { |
| 1263 leftPoly = v->fFirstEdgeAbove->fLeftPoly; |
| 1264 rightPoly = v->fLastEdgeAbove->fRightPoly; |
| 1265 } else { |
| 1266 leftPoly = leftEnclosingEdge ? leftEnclosingEdge->fRightPoly : NULL; |
| 1267 rightPoly = rightEnclosingEdge ? rightEnclosingEdge->fLeftPoly : NUL
L; |
| 1268 } |
| 1269 #if LOGGING_ENABLED |
| 1270 LOG("edges above:\n"); |
| 1271 for (Edge* e = v->fFirstEdgeAbove; e; e = e->fNextEdgeAbove) { |
| 1272 LOG("%g -> %g, lpoly %d, rpoly %d\n", e->fTop->fID, e->fBottom->fID, |
| 1273 e->fLeftPoly ? e->fLeftPoly->fID : -1, e->fRightPoly ? e->fRight
Poly->fID : -1); |
| 1274 } |
| 1275 LOG("edges below:\n"); |
| 1276 for (Edge* e = v->fFirstEdgeBelow; e; e = e->fNextEdgeBelow) { |
| 1277 LOG("%g -> %g, lpoly %d, rpoly %d\n", e->fTop->fID, e->fBottom->fID, |
| 1278 e->fLeftPoly ? e->fLeftPoly->fID : -1, e->fRightPoly ? e->fRight
Poly->fID : -1); |
| 1279 } |
| 1280 #endif |
| 1281 if (v->fFirstEdgeAbove) { |
| 1282 if (leftPoly) { |
| 1283 leftPoly = leftPoly->addVertex(v, Poly::kRight_Side, alloc); |
| 1284 } |
| 1285 if (rightPoly) { |
| 1286 rightPoly = rightPoly->addVertex(v, Poly::kLeft_Side, alloc); |
| 1287 } |
| 1288 for (Edge* e = v->fFirstEdgeAbove; e != v->fLastEdgeAbove; e = e->fN
extEdgeAbove) { |
| 1289 Edge* leftEdge = e; |
| 1290 Edge* rightEdge = e->fNextEdgeAbove; |
| 1291 SkASSERT(rightEdge->isRightOf(leftEdge->fTop)); |
| 1292 remove_edge(leftEdge, &activeEdges); |
| 1293 if (leftEdge->fRightPoly) { |
| 1294 leftEdge->fRightPoly->end(v, alloc); |
| 1295 } |
| 1296 if (rightEdge->fLeftPoly && rightEdge->fLeftPoly != leftEdge->fR
ightPoly) { |
| 1297 rightEdge->fLeftPoly->end(v, alloc); |
| 1298 } |
| 1299 } |
| 1300 remove_edge(v->fLastEdgeAbove, &activeEdges); |
| 1301 if (!v->fFirstEdgeBelow) { |
| 1302 if (leftPoly && rightPoly && leftPoly != rightPoly) { |
| 1303 SkASSERT(leftPoly->fPartner == NULL && rightPoly->fPartner =
= NULL); |
| 1304 rightPoly->fPartner = leftPoly; |
| 1305 leftPoly->fPartner = rightPoly; |
| 1306 } |
| 1307 } |
| 1308 } |
| 1309 if (v->fFirstEdgeBelow) { |
| 1310 if (!v->fFirstEdgeAbove) { |
| 1311 if (leftPoly && leftPoly == rightPoly) { |
| 1312 // Split the poly. |
| 1313 if (leftPoly->fActive->fSide == Poly::kLeft_Side) { |
| 1314 leftPoly = new_poly(&polys, leftEnclosingEdge->fTop, lef
tPoly->fWinding, |
| 1315 alloc); |
| 1316 leftPoly->addVertex(v, Poly::kRight_Side, alloc); |
| 1317 rightPoly->addVertex(v, Poly::kLeft_Side, alloc); |
| 1318 leftEnclosingEdge->fRightPoly = leftPoly; |
| 1319 } else { |
| 1320 rightPoly = new_poly(&polys, rightEnclosingEdge->fTop, r
ightPoly->fWinding, |
| 1321 alloc); |
| 1322 rightPoly->addVertex(v, Poly::kLeft_Side, alloc); |
| 1323 leftPoly->addVertex(v, Poly::kRight_Side, alloc); |
| 1324 rightEnclosingEdge->fLeftPoly = rightPoly; |
| 1325 } |
| 1326 } else { |
| 1327 if (leftPoly) { |
| 1328 leftPoly = leftPoly->addVertex(v, Poly::kRight_Side, all
oc); |
| 1329 } |
| 1330 if (rightPoly) { |
| 1331 rightPoly = rightPoly->addVertex(v, Poly::kLeft_Side, al
loc); |
| 1332 } |
| 1333 } |
| 1334 } |
| 1335 Edge* leftEdge = v->fFirstEdgeBelow; |
| 1336 leftEdge->fLeftPoly = leftPoly; |
| 1337 insert_edge(leftEdge, leftEnclosingEdge, &activeEdges); |
| 1338 for (Edge* rightEdge = leftEdge->fNextEdgeBelow; rightEdge; |
| 1339 rightEdge = rightEdge->fNextEdgeBelow) { |
| 1340 insert_edge(rightEdge, leftEdge, &activeEdges); |
| 1341 int winding = leftEdge->fLeftPoly ? leftEdge->fLeftPoly->fWindin
g : 0; |
| 1342 winding += leftEdge->fWinding; |
| 1343 if (winding != 0) { |
| 1344 Poly* poly = new_poly(&polys, v, winding, alloc); |
| 1345 leftEdge->fRightPoly = rightEdge->fLeftPoly = poly; |
| 1346 } |
| 1347 leftEdge = rightEdge; |
| 1348 } |
| 1349 v->fLastEdgeBelow->fRightPoly = rightPoly; |
| 1350 } |
| 1351 #ifdef SK_DEBUG |
| 1352 validate_edges(activeEdges); |
| 1353 #endif |
| 1354 #if LOGGING_ENABLED |
| 1355 LOG("\nactive edges:\n"); |
| 1356 for (Edge* e = activeEdges; e != NULL; e = e->fRight) { |
| 1357 LOG("%g -> %g, lpoly %d, rpoly %d\n", e->fTop->fID, e->fBottom->fID, |
| 1358 e->fLeftPoly ? e->fLeftPoly->fID : -1, e->fRightPoly ? e->fRight
Poly->fID : -1); |
| 1359 } |
| 1360 #endif |
| 1361 } |
| 1362 return polys; |
| 1363 } |
| 1364 |
| 1365 // This is a driver function which calls stages 2-5 in turn. |
| 1366 |
| 1367 Poly* contours_to_polys(Vertex** contours, int contourCnt, SkChunkAlloc& alloc)
{ |
| 1368 #if LOGGING_ENABLED |
| 1369 for (int i = 0; i < contourCnt; ++i) { |
| 1370 Vertex* v = contours[i]; |
| 1371 SkASSERT(v); |
| 1372 LOG("path.moveTo(%20.20g, %20.20g);\n", v->fPoint.fX, v->fPoint.fY); |
| 1373 for (v = v->fNext; v != contours[i]; v = v->fNext) { |
| 1374 LOG("path.lineTo(%20.20g, %20.20g);\n", v->fPoint.fX, v->fPoint.fY); |
| 1375 } |
| 1376 } |
| 1377 #endif |
| 1378 sanitize_contours(contours, contourCnt); |
| 1379 Vertex* vertices = build_edges(contours, contourCnt, alloc); |
| 1380 if (!vertices) { |
| 1381 return NULL; |
| 1382 } |
| 1383 |
| 1384 // Sort vertices in Y (secondarily in X). |
| 1385 merge_sort(&vertices); |
| 1386 merge_coincident_vertices(&vertices, alloc); |
| 1387 #if LOGGING_ENABLED |
| 1388 for (Vertex* v = vertices; v != NULL; v = v->fNext) { |
| 1389 static float gID = 0.0f; |
| 1390 v->fID = gID++; |
| 1391 } |
| 1392 #endif |
| 1393 simplify(vertices, alloc); |
| 1394 return tessellate(vertices, alloc); |
| 1395 } |
| 1396 |
| 1397 // Stage 6: Triangulate the monotone polygons into a vertex buffer. |
| 1398 |
| 1399 void* polys_to_triangles(Poly* polys, SkPath::FillType fillType, void* data) { |
| 1400 void* d = data; |
| 1401 for (Poly* poly = polys; poly; poly = poly->fNext) { |
| 1402 if (apply_fill_type(fillType, poly->fWinding)) { |
| 1403 d = poly->emit(d); |
| 1404 } |
| 1405 } |
| 1406 return d; |
| 1407 } |
| 1408 |
| 1409 }; |
| 1410 |
| 1411 GrTessellatingPathRenderer::GrTessellatingPathRenderer() { |
| 1412 } |
| 1413 |
| 1414 GrPathRenderer::StencilSupport GrTessellatingPathRenderer::onGetStencilSupport( |
| 1415 const GrDrawTarget*, |
| 1416 const GrPipelineBuil
der*, |
| 1417 const SkPath&, |
| 1418 const SkStrokeRec&)
const { |
| 1419 return GrPathRenderer::kNoSupport_StencilSupport; |
| 1420 } |
| 1421 |
| 1422 bool GrTessellatingPathRenderer::canDrawPath(const GrDrawTarget* target, |
| 1423 const GrPipelineBuilder* pipelineBu
ilder, |
| 1424 const SkMatrix& viewMatrix, |
| 1425 const SkPath& path, |
| 1426 const SkStrokeRec& stroke, |
| 1427 bool antiAlias) const { |
| 1428 // This path renderer can draw all fill styles, but does not do antialiasing
. It can do convex |
| 1429 // and concave paths, but we'll leave the convex ones to simpler algorithms. |
| 1430 return stroke.isFillStyle() && !antiAlias && !path.isConvex(); |
| 1431 } |
| 1432 |
| 1433 bool GrTessellatingPathRenderer::onDrawPath(GrDrawTarget* target, |
| 1434 GrPipelineBuilder* pipelineBuilder, |
| 1435 GrColor color, |
| 1436 const SkMatrix& viewM, |
| 1437 const SkPath& path, |
| 1438 const SkStrokeRec& stroke, |
| 1439 bool antiAlias) { |
| 1440 SkASSERT(!antiAlias); |
| 1441 const GrRenderTarget* rt = pipelineBuilder->getRenderTarget(); |
| 1442 if (NULL == rt) { |
| 1443 return false; |
| 1444 } |
| 1445 |
| 1446 SkScalar tol = GrPathUtils::scaleToleranceToSrc(SK_Scalar1, viewM, path.getB
ounds()); |
| 1447 |
| 1448 int contourCnt; |
| 1449 int maxPts = GrPathUtils::worstCasePointCount(path, &contourCnt, tol); |
| 1450 if (maxPts <= 0) { |
| 1451 return false; |
| 1452 } |
| 1453 if (maxPts > ((int)SK_MaxU16 + 1)) { |
| 1454 SkDebugf("Path not rendered, too many verts (%d)\n", maxPts); |
| 1455 return false; |
| 1456 } |
| 1457 SkPath::FillType fillType = path.getFillType(); |
| 1458 if (SkPath::IsInverseFillType(fillType)) { |
| 1459 contourCnt++; |
| 1460 } |
| 1461 |
| 1462 LOG("got %d pts, %d contours\n", maxPts, contourCnt); |
| 1463 |
| 1464 SkAutoTDeleteArray<Vertex*> contours(SkNEW_ARRAY(Vertex *, contourCnt)); |
| 1465 |
| 1466 // For the initial size of the chunk allocator, estimate based on the point
count: |
| 1467 // one vertex per point for the initial passes, plus two for the vertices in
the |
| 1468 // resulting Polys, since the same point may end up in two Polys. Assume mi
nimal |
| 1469 // connectivity of one Edge per Vertex (will grow for intersections). |
| 1470 SkChunkAlloc alloc(maxPts * (3 * sizeof(Vertex) + sizeof(Edge))); |
| 1471 SkIRect clipBoundsI; |
| 1472 pipelineBuilder->clip().getConservativeBounds(rt, &clipBoundsI); |
| 1473 SkRect clipBounds = SkRect::Make(clipBoundsI); |
| 1474 SkMatrix vmi; |
| 1475 if (!viewM.invert(&vmi)) { |
| 1476 return false; |
| 1477 } |
| 1478 vmi.mapRect(&clipBounds); |
| 1479 path_to_contours(path, tol, clipBounds, contours.get(), alloc); |
| 1480 Poly* polys; |
| 1481 uint32_t flags = GrDefaultGeoProcFactory::kPosition_GPType; |
| 1482 polys = contours_to_polys(contours.get(), contourCnt, alloc); |
| 1483 SkAutoTUnref<const GrGeometryProcessor> gp( |
| 1484 GrDefaultGeoProcFactory::Create(flags, color, viewM, SkMatrix::I())); |
| 1485 int count = 0; |
| 1486 for (Poly* poly = polys; poly; poly = poly->fNext) { |
| 1487 if (apply_fill_type(fillType, poly->fWinding) && poly->fCount >= 3) { |
| 1488 count += (poly->fCount - 2) * (WIREFRAME ? 6 : 3); |
| 1489 } |
| 1490 } |
| 1491 |
| 1492 int stride = gp->getVertexStride(); |
| 1493 GrDrawTarget::AutoReleaseGeometry arg; |
| 1494 if (!arg.set(target, count, stride, 0)) { |
| 1495 return false; |
| 1496 } |
| 1497 LOG("emitting %d verts\n", count); |
| 1498 void* end = polys_to_triangles(polys, fillType, arg.vertices()); |
| 1499 int actualCount = (static_cast<char*>(end) - static_cast<char*>(arg.vertices
())) / stride; |
| 1500 LOG("actual count: %d\n", actualCount); |
| 1501 SkASSERT(actualCount <= count); |
| 1502 |
| 1503 GrPrimitiveType primitiveType = WIREFRAME ? kLines_GrPrimitiveType |
| 1504 : kTriangles_GrPrimitiveType; |
| 1505 target->drawNonIndexed(pipelineBuilder, gp, primitiveType, 0, actualCount); |
| 1506 |
| 1507 return true; |
| 1508 } |
OLD | NEW |