| 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 "GrTessellatingPathRenderer.h" |
| 9 | 9 |
| 10 #include "GrBatchFlushState.h" | 10 #include "GrBatchFlushState.h" |
| (...skipping 107 matching lines...) Expand 10 before | Expand all | Expand 10 after Loading... |
| 118 if (t->*Prev) { | 118 if (t->*Prev) { |
| 119 t->*Prev->*Next = t->*Next; | 119 t->*Prev->*Next = t->*Next; |
| 120 } else if (head) { | 120 } else if (head) { |
| 121 *head = t->*Next; | 121 *head = t->*Next; |
| 122 } | 122 } |
| 123 if (t->*Next) { | 123 if (t->*Next) { |
| 124 t->*Next->*Prev = t->*Prev; | 124 t->*Next->*Prev = t->*Prev; |
| 125 } else if (tail) { | 125 } else if (tail) { |
| 126 *tail = t->*Prev; | 126 *tail = t->*Prev; |
| 127 } | 127 } |
| 128 t->*Prev = t->*Next = NULL; | 128 t->*Prev = t->*Next = nullptr; |
| 129 } | 129 } |
| 130 | 130 |
| 131 /** | 131 /** |
| 132 * Vertices are used in three ways: first, the path contours are converted into
a | 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 | 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 | 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 | 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 | 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 | 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 | 138 * an individual Vertex from the path mesh may belong to multiple |
| 139 * MonotonePolys, so the original Vertices cannot be re-used. | 139 * MonotonePolys, so the original Vertices cannot be re-used. |
| 140 */ | 140 */ |
| 141 | 141 |
| 142 struct Vertex { | 142 struct Vertex { |
| 143 Vertex(const SkPoint& point) | 143 Vertex(const SkPoint& point) |
| 144 : fPoint(point), fPrev(NULL), fNext(NULL) | 144 : fPoint(point), fPrev(nullptr), fNext(nullptr) |
| 145 , fFirstEdgeAbove(NULL), fLastEdgeAbove(NULL) | 145 , fFirstEdgeAbove(nullptr), fLastEdgeAbove(nullptr) |
| 146 , fFirstEdgeBelow(NULL), fLastEdgeBelow(NULL) | 146 , fFirstEdgeBelow(nullptr), fLastEdgeBelow(nullptr) |
| 147 , fProcessed(false) | 147 , fProcessed(false) |
| 148 #if LOGGING_ENABLED | 148 #if LOGGING_ENABLED |
| 149 , fID (-1.0f) | 149 , fID (-1.0f) |
| 150 #endif | 150 #endif |
| 151 {} | 151 {} |
| 152 SkPoint fPoint; // Vertex position | 152 SkPoint fPoint; // Vertex position |
| 153 Vertex* fPrev; // Linked list of contours, then Y-sorted vertices
. | 153 Vertex* fPrev; // Linked list of contours, then Y-sorted vertices
. |
| 154 Vertex* fNext; // " | 154 Vertex* fNext; // " |
| 155 Edge* fFirstEdgeAbove; // Linked list of edges above this vertex. | 155 Edge* fFirstEdgeAbove; // Linked list of edges above this vertex. |
| 156 Edge* fLastEdgeAbove; // " | 156 Edge* fLastEdgeAbove; // " |
| (...skipping 45 matching lines...) Expand 10 before | Expand all | Expand 10 after Loading... |
| 202 data = emit_vertex(v0, data); | 202 data = emit_vertex(v0, data); |
| 203 #else | 203 #else |
| 204 data = emit_vertex(v0, data); | 204 data = emit_vertex(v0, data); |
| 205 data = emit_vertex(v1, data); | 205 data = emit_vertex(v1, data); |
| 206 data = emit_vertex(v2, data); | 206 data = emit_vertex(v2, data); |
| 207 #endif | 207 #endif |
| 208 return data; | 208 return data; |
| 209 } | 209 } |
| 210 | 210 |
| 211 struct EdgeList { | 211 struct EdgeList { |
| 212 EdgeList() : fHead(NULL), fTail(NULL) {} | 212 EdgeList() : fHead(nullptr), fTail(nullptr) {} |
| 213 Edge* fHead; | 213 Edge* fHead; |
| 214 Edge* fTail; | 214 Edge* fTail; |
| 215 }; | 215 }; |
| 216 | 216 |
| 217 /** | 217 /** |
| 218 * An Edge joins a top Vertex to a bottom Vertex. Edge ordering for the list of
"edges above" and | 218 * 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(). | 219 * "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 | 220 * 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., | 221 * 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. | 222 * 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 | 223 * 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 | 224 * 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. | 225 * a lot faster in the "not found" case. |
| 226 * | 226 * |
| 227 * The coefficients of the line equation stored in double precision to avoid cat
astrphic | 227 * 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 | 228 * 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 | 229 * 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 | 230 * 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 | 231 * output may be incorrect, and adjusting the mesh topology to match (see commen
t at the top of |
| 232 * this file). | 232 * this file). |
| 233 */ | 233 */ |
| 234 | 234 |
| 235 struct Edge { | 235 struct Edge { |
| 236 Edge(Vertex* top, Vertex* bottom, int winding) | 236 Edge(Vertex* top, Vertex* bottom, int winding) |
| 237 : fWinding(winding) | 237 : fWinding(winding) |
| 238 , fTop(top) | 238 , fTop(top) |
| 239 , fBottom(bottom) | 239 , fBottom(bottom) |
| 240 , fLeft(NULL) | 240 , fLeft(nullptr) |
| 241 , fRight(NULL) | 241 , fRight(nullptr) |
| 242 , fPrevEdgeAbove(NULL) | 242 , fPrevEdgeAbove(nullptr) |
| 243 , fNextEdgeAbove(NULL) | 243 , fNextEdgeAbove(nullptr) |
| 244 , fPrevEdgeBelow(NULL) | 244 , fPrevEdgeBelow(nullptr) |
| 245 , fNextEdgeBelow(NULL) | 245 , fNextEdgeBelow(nullptr) |
| 246 , fLeftPoly(NULL) | 246 , fLeftPoly(nullptr) |
| 247 , fRightPoly(NULL) { | 247 , fRightPoly(nullptr) { |
| 248 recompute(); | 248 recompute(); |
| 249 } | 249 } |
| 250 int fWinding; // 1 == edge goes downward; -1 = edge goes upwar
d. | 250 int fWinding; // 1 == edge goes downward; -1 = edge goes upwar
d. |
| 251 Vertex* fTop; // The top vertex in vertex-sort-order (sweep_lt
). | 251 Vertex* fTop; // The top vertex in vertex-sort-order (sweep_lt
). |
| 252 Vertex* fBottom; // The bottom vertex in vertex-sort-order. | 252 Vertex* fBottom; // The bottom vertex in vertex-sort-order. |
| 253 Edge* fLeft; // The linked list of edges in the active edge l
ist. | 253 Edge* fLeft; // The linked list of edges in the active edge l
ist. |
| 254 Edge* fRight; // " | 254 Edge* fRight; // " |
| 255 Edge* fPrevEdgeAbove; // The linked list of edges in the bottom Vertex
's "edges above". | 255 Edge* fPrevEdgeAbove; // The linked list of edges in the bottom Vertex
's "edges above". |
| 256 Edge* fNextEdgeAbove; // " | 256 Edge* fNextEdgeAbove; // " |
| 257 Edge* fPrevEdgeBelow; // The linked list of edges in the top Vertex's
"edges below". | 257 Edge* fPrevEdgeBelow; // The linked list of edges in the top Vertex's
"edges below". |
| (...skipping 48 matching lines...) Expand 10 before | Expand all | Expand 10 after Loading... |
| 306 bool isActive(EdgeList* activeEdges) const { | 306 bool isActive(EdgeList* activeEdges) const { |
| 307 return activeEdges && (fLeft || fRight || activeEdges->fHead == this); | 307 return activeEdges && (fLeft || fRight || activeEdges->fHead == this); |
| 308 } | 308 } |
| 309 }; | 309 }; |
| 310 | 310 |
| 311 /*******************************************************************************
********/ | 311 /*******************************************************************************
********/ |
| 312 | 312 |
| 313 struct Poly { | 313 struct Poly { |
| 314 Poly(int winding) | 314 Poly(int winding) |
| 315 : fWinding(winding) | 315 : fWinding(winding) |
| 316 , fHead(NULL) | 316 , fHead(nullptr) |
| 317 , fTail(NULL) | 317 , fTail(nullptr) |
| 318 , fActive(NULL) | 318 , fActive(nullptr) |
| 319 , fNext(NULL) | 319 , fNext(nullptr) |
| 320 , fPartner(NULL) | 320 , fPartner(nullptr) |
| 321 , fCount(0) | 321 , fCount(0) |
| 322 { | 322 { |
| 323 #if LOGGING_ENABLED | 323 #if LOGGING_ENABLED |
| 324 static int gID = 0; | 324 static int gID = 0; |
| 325 fID = gID++; | 325 fID = gID++; |
| 326 LOG("*** created Poly %d\n", fID); | 326 LOG("*** created Poly %d\n", fID); |
| 327 #endif | 327 #endif |
| 328 } | 328 } |
| 329 typedef enum { kNeither_Side, kLeft_Side, kRight_Side } Side; | 329 typedef enum { kNeither_Side, kLeft_Side, kRight_Side } Side; |
| 330 struct MonotonePoly { | 330 struct MonotonePoly { |
| 331 MonotonePoly() | 331 MonotonePoly() |
| 332 : fSide(kNeither_Side) | 332 : fSide(kNeither_Side) |
| 333 , fHead(NULL) | 333 , fHead(nullptr) |
| 334 , fTail(NULL) | 334 , fTail(nullptr) |
| 335 , fPrev(NULL) | 335 , fPrev(nullptr) |
| 336 , fNext(NULL) {} | 336 , fNext(nullptr) {} |
| 337 Side fSide; | 337 Side fSide; |
| 338 Vertex* fHead; | 338 Vertex* fHead; |
| 339 Vertex* fTail; | 339 Vertex* fTail; |
| 340 MonotonePoly* fPrev; | 340 MonotonePoly* fPrev; |
| 341 MonotonePoly* fNext; | 341 MonotonePoly* fNext; |
| 342 bool addVertex(Vertex* v, Side side, SkChunkAlloc& alloc) { | 342 bool addVertex(Vertex* v, Side side, SkChunkAlloc& alloc) { |
| 343 Vertex* newV = ALLOC_NEW(Vertex, (v->fPoint), alloc); | 343 Vertex* newV = ALLOC_NEW(Vertex, (v->fPoint), alloc); |
| 344 bool done = false; | 344 bool done = false; |
| 345 if (fSide == kNeither_Side) { | 345 if (fSide == kNeither_Side) { |
| 346 fSide = side; | 346 fSide = side; |
| 347 } else { | 347 } else { |
| 348 done = side != fSide; | 348 done = side != fSide; |
| 349 } | 349 } |
| 350 if (fHead == NULL) { | 350 if (fHead == nullptr) { |
| 351 fHead = fTail = newV; | 351 fHead = fTail = newV; |
| 352 } else if (fSide == kRight_Side) { | 352 } else if (fSide == kRight_Side) { |
| 353 newV->fPrev = fTail; | 353 newV->fPrev = fTail; |
| 354 fTail->fNext = newV; | 354 fTail->fNext = newV; |
| 355 fTail = newV; | 355 fTail = newV; |
| 356 } else { | 356 } else { |
| 357 newV->fNext = fHead; | 357 newV->fNext = fHead; |
| 358 fHead->fPrev = newV; | 358 fHead->fPrev = newV; |
| 359 fHead = newV; | 359 fHead = newV; |
| 360 } | 360 } |
| (...skipping 27 matching lines...) Expand all Loading... |
| 388 } | 388 } |
| 389 return data; | 389 return data; |
| 390 } | 390 } |
| 391 }; | 391 }; |
| 392 Poly* addVertex(Vertex* v, Side side, SkChunkAlloc& alloc) { | 392 Poly* addVertex(Vertex* 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, | 393 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"); | 394 side == kLeft_Side ? "left" : side == kRight_Side ? "right" : "ne
ither"); |
| 395 Poly* partner = fPartner; | 395 Poly* partner = fPartner; |
| 396 Poly* poly = this; | 396 Poly* poly = this; |
| 397 if (partner) { | 397 if (partner) { |
| 398 fPartner = partner->fPartner = NULL; | 398 fPartner = partner->fPartner = nullptr; |
| 399 } | 399 } |
| 400 if (!fActive) { | 400 if (!fActive) { |
| 401 fActive = ALLOC_NEW(MonotonePoly, (), alloc); | 401 fActive = ALLOC_NEW(MonotonePoly, (), alloc); |
| 402 } | 402 } |
| 403 if (fActive->addVertex(v, side, alloc)) { | 403 if (fActive->addVertex(v, side, alloc)) { |
| 404 if (fTail) { | 404 if (fTail) { |
| 405 fActive->fPrev = fTail; | 405 fActive->fPrev = fTail; |
| 406 fTail->fNext = fActive; | 406 fTail->fNext = fActive; |
| 407 fTail = fActive; | 407 fTail = fActive; |
| 408 } else { | 408 } else { |
| 409 fHead = fTail = fActive; | 409 fHead = fTail = fActive; |
| 410 } | 410 } |
| 411 if (partner) { | 411 if (partner) { |
| 412 partner->addVertex(v, side, alloc); | 412 partner->addVertex(v, side, alloc); |
| 413 poly = partner; | 413 poly = partner; |
| 414 } else { | 414 } else { |
| 415 Vertex* prev = fActive->fSide == Poly::kLeft_Side ? | 415 Vertex* prev = fActive->fSide == Poly::kLeft_Side ? |
| 416 fActive->fHead->fNext : fActive->fTail->fPrev; | 416 fActive->fHead->fNext : fActive->fTail->fPrev; |
| 417 fActive = ALLOC_NEW(MonotonePoly, , alloc); | 417 fActive = ALLOC_NEW(MonotonePoly, , alloc); |
| 418 fActive->addVertex(prev, Poly::kNeither_Side, alloc); | 418 fActive->addVertex(prev, Poly::kNeither_Side, alloc); |
| 419 fActive->addVertex(v, side, alloc); | 419 fActive->addVertex(v, side, alloc); |
| 420 } | 420 } |
| 421 } | 421 } |
| 422 fCount++; | 422 fCount++; |
| 423 return poly; | 423 return poly; |
| 424 } | 424 } |
| 425 void end(Vertex* v, SkChunkAlloc& alloc) { | 425 void end(Vertex* v, SkChunkAlloc& alloc) { |
| 426 LOG("end() %d at %g, %g\n", fID, v->fPoint.fX, v->fPoint.fY); | 426 LOG("end() %d at %g, %g\n", fID, v->fPoint.fX, v->fPoint.fY); |
| 427 if (fPartner) { | 427 if (fPartner) { |
| 428 fPartner = fPartner->fPartner = NULL; | 428 fPartner = fPartner->fPartner = nullptr; |
| 429 } | 429 } |
| 430 addVertex(v, fActive->fSide == kLeft_Side ? kRight_Side : kLeft_Side, al
loc); | 430 addVertex(v, fActive->fSide == kLeft_Side ? kRight_Side : kLeft_Side, al
loc); |
| 431 } | 431 } |
| 432 SkPoint* emit(SkPoint *data) { | 432 SkPoint* emit(SkPoint *data) { |
| 433 if (fCount < 3) { | 433 if (fCount < 3) { |
| 434 return data; | 434 return data; |
| 435 } | 435 } |
| 436 LOG("emit() %d, size %d\n", fID, fCount); | 436 LOG("emit() %d, size %d\n", fID, fCount); |
| 437 for (MonotonePoly* m = fHead; m != NULL; m = m->fNext) { | 437 for (MonotonePoly* m = fHead; m != nullptr; m = m->fNext) { |
| 438 data = m->emit(data); | 438 data = m->emit(data); |
| 439 } | 439 } |
| 440 return data; | 440 return data; |
| 441 } | 441 } |
| 442 int fWinding; | 442 int fWinding; |
| 443 MonotonePoly* fHead; | 443 MonotonePoly* fHead; |
| 444 MonotonePoly* fTail; | 444 MonotonePoly* fTail; |
| 445 MonotonePoly* fActive; | 445 MonotonePoly* fActive; |
| 446 Poly* fNext; | 446 Poly* fNext; |
| 447 Poly* fPartner; | 447 Poly* fPartner; |
| (...skipping 93 matching lines...) Expand 10 before | Expand all | Expand 10 after Loading... |
| 541 | 541 |
| 542 void path_to_contours(const SkPath& path, SkScalar tolerance, const SkRect& clip
Bounds, | 542 void path_to_contours(const SkPath& path, SkScalar tolerance, const SkRect& clip
Bounds, |
| 543 Vertex** contours, SkChunkAlloc& alloc, bool *isLinear) { | 543 Vertex** contours, SkChunkAlloc& alloc, bool *isLinear) { |
| 544 | 544 |
| 545 SkScalar toleranceSqd = tolerance * tolerance; | 545 SkScalar toleranceSqd = tolerance * tolerance; |
| 546 | 546 |
| 547 SkPoint pts[4]; | 547 SkPoint pts[4]; |
| 548 bool done = false; | 548 bool done = false; |
| 549 *isLinear = true; | 549 *isLinear = true; |
| 550 SkPath::Iter iter(path, false); | 550 SkPath::Iter iter(path, false); |
| 551 Vertex* prev = NULL; | 551 Vertex* prev = nullptr; |
| 552 Vertex* head = NULL; | 552 Vertex* head = nullptr; |
| 553 if (path.isInverseFillType()) { | 553 if (path.isInverseFillType()) { |
| 554 SkPoint quad[4]; | 554 SkPoint quad[4]; |
| 555 clipBounds.toQuad(quad); | 555 clipBounds.toQuad(quad); |
| 556 for (int i = 3; i >= 0; i--) { | 556 for (int i = 3; i >= 0; i--) { |
| 557 prev = append_point_to_contour(quad[i], prev, &head, alloc); | 557 prev = append_point_to_contour(quad[i], prev, &head, alloc); |
| 558 } | 558 } |
| 559 head->fPrev = prev; | 559 head->fPrev = prev; |
| 560 prev->fNext = head; | 560 prev->fNext = head; |
| 561 *contours++ = head; | 561 *contours++ = head; |
| 562 head = prev = NULL; | 562 head = prev = nullptr; |
| 563 } | 563 } |
| 564 SkAutoConicToQuads converter; | 564 SkAutoConicToQuads converter; |
| 565 while (!done) { | 565 while (!done) { |
| 566 SkPath::Verb verb = iter.next(pts); | 566 SkPath::Verb verb = iter.next(pts); |
| 567 switch (verb) { | 567 switch (verb) { |
| 568 case SkPath::kConic_Verb: { | 568 case SkPath::kConic_Verb: { |
| 569 SkScalar weight = iter.conicWeight(); | 569 SkScalar weight = iter.conicWeight(); |
| 570 const SkPoint* quadPts = converter.computeQuads(pts, weight, tol
eranceSqd); | 570 const SkPoint* quadPts = converter.computeQuads(pts, weight, tol
eranceSqd); |
| 571 for (int i = 0; i < converter.countQuads(); ++i) { | 571 for (int i = 0; i < converter.countQuads(); ++i) { |
| 572 int pointsLeft = GrPathUtils::quadraticPointCount(quadPts, t
olerance); | 572 int pointsLeft = GrPathUtils::quadraticPointCount(quadPts, t
olerance); |
| 573 prev = generate_quadratic_points(quadPts[0], quadPts[1], qua
dPts[2], | 573 prev = generate_quadratic_points(quadPts[0], quadPts[1], qua
dPts[2], |
| 574 toleranceSqd, prev, &head,
pointsLeft, alloc); | 574 toleranceSqd, prev, &head,
pointsLeft, alloc); |
| 575 quadPts += 2; | 575 quadPts += 2; |
| 576 } | 576 } |
| 577 *isLinear = false; | 577 *isLinear = false; |
| 578 break; | 578 break; |
| 579 } | 579 } |
| 580 case SkPath::kMove_Verb: | 580 case SkPath::kMove_Verb: |
| 581 if (head) { | 581 if (head) { |
| 582 head->fPrev = prev; | 582 head->fPrev = prev; |
| 583 prev->fNext = head; | 583 prev->fNext = head; |
| 584 *contours++ = head; | 584 *contours++ = head; |
| 585 } | 585 } |
| 586 head = prev = NULL; | 586 head = prev = nullptr; |
| 587 prev = append_point_to_contour(pts[0], prev, &head, alloc); | 587 prev = append_point_to_contour(pts[0], prev, &head, alloc); |
| 588 break; | 588 break; |
| 589 case SkPath::kLine_Verb: { | 589 case SkPath::kLine_Verb: { |
| 590 prev = append_point_to_contour(pts[1], prev, &head, alloc); | 590 prev = append_point_to_contour(pts[1], prev, &head, alloc); |
| 591 break; | 591 break; |
| 592 } | 592 } |
| 593 case SkPath::kQuad_Verb: { | 593 case SkPath::kQuad_Verb: { |
| 594 int pointsLeft = GrPathUtils::quadraticPointCount(pts, tolerance
); | 594 int pointsLeft = GrPathUtils::quadraticPointCount(pts, tolerance
); |
| 595 prev = generate_quadratic_points(pts[0], pts[1], pts[2], toleran
ceSqd, prev, | 595 prev = generate_quadratic_points(pts[0], pts[1], pts[2], toleran
ceSqd, prev, |
| 596 &head, pointsLeft, alloc); | 596 &head, pointsLeft, alloc); |
| 597 *isLinear = false; | 597 *isLinear = false; |
| 598 break; | 598 break; |
| 599 } | 599 } |
| 600 case SkPath::kCubic_Verb: { | 600 case SkPath::kCubic_Verb: { |
| 601 int pointsLeft = GrPathUtils::cubicPointCount(pts, tolerance); | 601 int pointsLeft = GrPathUtils::cubicPointCount(pts, tolerance); |
| 602 prev = generate_cubic_points(pts[0], pts[1], pts[2], pts[3], | 602 prev = generate_cubic_points(pts[0], pts[1], pts[2], pts[3], |
| 603 toleranceSqd, prev, &head, pointsLeft, alloc); | 603 toleranceSqd, prev, &head, pointsLeft, alloc); |
| 604 *isLinear = false; | 604 *isLinear = false; |
| 605 break; | 605 break; |
| 606 } | 606 } |
| 607 case SkPath::kClose_Verb: | 607 case SkPath::kClose_Verb: |
| 608 if (head) { | 608 if (head) { |
| 609 head->fPrev = prev; | 609 head->fPrev = prev; |
| 610 prev->fNext = head; | 610 prev->fNext = head; |
| 611 *contours++ = head; | 611 *contours++ = head; |
| 612 } | 612 } |
| 613 head = prev = NULL; | 613 head = prev = nullptr; |
| 614 break; | 614 break; |
| 615 case SkPath::kDone_Verb: | 615 case SkPath::kDone_Verb: |
| 616 if (head) { | 616 if (head) { |
| 617 head->fPrev = prev; | 617 head->fPrev = prev; |
| 618 prev->fNext = head; | 618 prev->fNext = head; |
| 619 *contours++ = head; | 619 *contours++ = head; |
| 620 } | 620 } |
| 621 done = true; | 621 done = true; |
| 622 break; | 622 break; |
| 623 } | 623 } |
| (...skipping 35 matching lines...) Expand 10 before | Expand all | Expand 10 after Loading... |
| 659 Edge* next = prev ? prev->fRight : edges->fHead; | 659 Edge* next = prev ? prev->fRight : edges->fHead; |
| 660 insert<Edge, &Edge::fLeft, &Edge::fRight>(edge, prev, next, &edges->fHead, &
edges->fTail); | 660 insert<Edge, &Edge::fLeft, &Edge::fRight>(edge, prev, next, &edges->fHead, &
edges->fTail); |
| 661 } | 661 } |
| 662 | 662 |
| 663 void find_enclosing_edges(Vertex* v, EdgeList* edges, Edge** left, Edge** right)
{ | 663 void find_enclosing_edges(Vertex* v, EdgeList* edges, Edge** left, Edge** right)
{ |
| 664 if (v->fFirstEdgeAbove) { | 664 if (v->fFirstEdgeAbove) { |
| 665 *left = v->fFirstEdgeAbove->fLeft; | 665 *left = v->fFirstEdgeAbove->fLeft; |
| 666 *right = v->fLastEdgeAbove->fRight; | 666 *right = v->fLastEdgeAbove->fRight; |
| 667 return; | 667 return; |
| 668 } | 668 } |
| 669 Edge* next = NULL; | 669 Edge* next = nullptr; |
| 670 Edge* prev; | 670 Edge* prev; |
| 671 for (prev = edges->fTail; prev != NULL; prev = prev->fLeft) { | 671 for (prev = edges->fTail; prev != nullptr; prev = prev->fLeft) { |
| 672 if (prev->isLeftOf(v)) { | 672 if (prev->isLeftOf(v)) { |
| 673 break; | 673 break; |
| 674 } | 674 } |
| 675 next = prev; | 675 next = prev; |
| 676 } | 676 } |
| 677 *left = prev; | 677 *left = prev; |
| 678 *right = next; | 678 *right = next; |
| 679 return; | 679 return; |
| 680 } | 680 } |
| 681 | 681 |
| 682 void find_enclosing_edges(Edge* edge, EdgeList* edges, Comparator& c, Edge** lef
t, Edge** right) { | 682 void find_enclosing_edges(Edge* edge, EdgeList* edges, Comparator& c, Edge** lef
t, Edge** right) { |
| 683 Edge* prev = NULL; | 683 Edge* prev = nullptr; |
| 684 Edge* next; | 684 Edge* next; |
| 685 for (next = edges->fHead; next != NULL; next = next->fRight) { | 685 for (next = edges->fHead; next != nullptr; next = next->fRight) { |
| 686 if ((c.sweep_gt(edge->fTop->fPoint, next->fTop->fPoint) && next->isRight
Of(edge->fTop)) || | 686 if ((c.sweep_gt(edge->fTop->fPoint, next->fTop->fPoint) && next->isRight
Of(edge->fTop)) || |
| 687 (c.sweep_gt(next->fTop->fPoint, edge->fTop->fPoint) && edge->isLeftO
f(next->fTop)) || | 687 (c.sweep_gt(next->fTop->fPoint, edge->fTop->fPoint) && edge->isLeftO
f(next->fTop)) || |
| 688 (c.sweep_lt(edge->fBottom->fPoint, next->fBottom->fPoint) && | 688 (c.sweep_lt(edge->fBottom->fPoint, next->fBottom->fPoint) && |
| 689 next->isRightOf(edge->fBottom)) || | 689 next->isRightOf(edge->fBottom)) || |
| 690 (c.sweep_lt(next->fBottom->fPoint, edge->fBottom->fPoint) && | 690 (c.sweep_lt(next->fBottom->fPoint, edge->fBottom->fPoint) && |
| 691 edge->isLeftOf(next->fBottom))) { | 691 edge->isLeftOf(next->fBottom))) { |
| 692 break; | 692 break; |
| 693 } | 693 } |
| 694 prev = next; | 694 prev = next; |
| 695 } | 695 } |
| (...skipping 14 matching lines...) Expand all Loading... |
| 710 insert_edge(edge, left, activeEdges); | 710 insert_edge(edge, left, activeEdges); |
| 711 } | 711 } |
| 712 } | 712 } |
| 713 | 713 |
| 714 void insert_edge_above(Edge* edge, Vertex* v, Comparator& c) { | 714 void insert_edge_above(Edge* edge, Vertex* v, Comparator& c) { |
| 715 if (edge->fTop->fPoint == edge->fBottom->fPoint || | 715 if (edge->fTop->fPoint == edge->fBottom->fPoint || |
| 716 c.sweep_gt(edge->fTop->fPoint, edge->fBottom->fPoint)) { | 716 c.sweep_gt(edge->fTop->fPoint, edge->fBottom->fPoint)) { |
| 717 return; | 717 return; |
| 718 } | 718 } |
| 719 LOG("insert edge (%g -> %g) above vertex %g\n", edge->fTop->fID, edge->fBott
om->fID, v->fID); | 719 LOG("insert edge (%g -> %g) above vertex %g\n", edge->fTop->fID, edge->fBott
om->fID, v->fID); |
| 720 Edge* prev = NULL; | 720 Edge* prev = nullptr; |
| 721 Edge* next; | 721 Edge* next; |
| 722 for (next = v->fFirstEdgeAbove; next; next = next->fNextEdgeAbove) { | 722 for (next = v->fFirstEdgeAbove; next; next = next->fNextEdgeAbove) { |
| 723 if (next->isRightOf(edge->fTop)) { | 723 if (next->isRightOf(edge->fTop)) { |
| 724 break; | 724 break; |
| 725 } | 725 } |
| 726 prev = next; | 726 prev = next; |
| 727 } | 727 } |
| 728 insert<Edge, &Edge::fPrevEdgeAbove, &Edge::fNextEdgeAbove>( | 728 insert<Edge, &Edge::fPrevEdgeAbove, &Edge::fNextEdgeAbove>( |
| 729 edge, prev, next, &v->fFirstEdgeAbove, &v->fLastEdgeAbove); | 729 edge, prev, next, &v->fFirstEdgeAbove, &v->fLastEdgeAbove); |
| 730 } | 730 } |
| 731 | 731 |
| 732 void insert_edge_below(Edge* edge, Vertex* v, Comparator& c) { | 732 void insert_edge_below(Edge* edge, Vertex* v, Comparator& c) { |
| 733 if (edge->fTop->fPoint == edge->fBottom->fPoint || | 733 if (edge->fTop->fPoint == edge->fBottom->fPoint || |
| 734 c.sweep_gt(edge->fTop->fPoint, edge->fBottom->fPoint)) { | 734 c.sweep_gt(edge->fTop->fPoint, edge->fBottom->fPoint)) { |
| 735 return; | 735 return; |
| 736 } | 736 } |
| 737 LOG("insert edge (%g -> %g) below vertex %g\n", edge->fTop->fID, edge->fBott
om->fID, v->fID); | 737 LOG("insert edge (%g -> %g) below vertex %g\n", edge->fTop->fID, edge->fBott
om->fID, v->fID); |
| 738 Edge* prev = NULL; | 738 Edge* prev = nullptr; |
| 739 Edge* next; | 739 Edge* next; |
| 740 for (next = v->fFirstEdgeBelow; next; next = next->fNextEdgeBelow) { | 740 for (next = v->fFirstEdgeBelow; next; next = next->fNextEdgeBelow) { |
| 741 if (next->isRightOf(edge->fBottom)) { | 741 if (next->isRightOf(edge->fBottom)) { |
| 742 break; | 742 break; |
| 743 } | 743 } |
| 744 prev = next; | 744 prev = next; |
| 745 } | 745 } |
| 746 insert<Edge, &Edge::fPrevEdgeBelow, &Edge::fNextEdgeBelow>( | 746 insert<Edge, &Edge::fPrevEdgeBelow, &Edge::fNextEdgeBelow>( |
| 747 edge, prev, next, &v->fFirstEdgeBelow, &v->fLastEdgeBelow); | 747 edge, prev, next, &v->fFirstEdgeBelow, &v->fLastEdgeBelow); |
| 748 } | 748 } |
| (...skipping 154 matching lines...) Expand 10 before | Expand all | Expand 10 after Loading... |
| 903 fix_active_state(newEdge, activeEdges, c); | 903 fix_active_state(newEdge, activeEdges, c); |
| 904 merge_collinear_edges(newEdge, activeEdges, c); | 904 merge_collinear_edges(newEdge, activeEdges, c); |
| 905 } | 905 } |
| 906 } | 906 } |
| 907 | 907 |
| 908 void merge_vertices(Vertex* src, Vertex* dst, Vertex** head, Comparator& c, SkCh
unkAlloc& alloc) { | 908 void merge_vertices(Vertex* src, Vertex* dst, Vertex** head, Comparator& c, SkCh
unkAlloc& alloc) { |
| 909 LOG("found coincident verts at %g, %g; merging %g into %g\n", src->fPoint.fX
, src->fPoint.fY, | 909 LOG("found coincident verts at %g, %g; merging %g into %g\n", src->fPoint.fX
, src->fPoint.fY, |
| 910 src->fID, dst->fID); | 910 src->fID, dst->fID); |
| 911 for (Edge* edge = src->fFirstEdgeAbove; edge;) { | 911 for (Edge* edge = src->fFirstEdgeAbove; edge;) { |
| 912 Edge* next = edge->fNextEdgeAbove; | 912 Edge* next = edge->fNextEdgeAbove; |
| 913 set_bottom(edge, dst, NULL, c); | 913 set_bottom(edge, dst, nullptr, c); |
| 914 edge = next; | 914 edge = next; |
| 915 } | 915 } |
| 916 for (Edge* edge = src->fFirstEdgeBelow; edge;) { | 916 for (Edge* edge = src->fFirstEdgeBelow; edge;) { |
| 917 Edge* next = edge->fNextEdgeBelow; | 917 Edge* next = edge->fNextEdgeBelow; |
| 918 set_top(edge, dst, NULL, c); | 918 set_top(edge, dst, nullptr, c); |
| 919 edge = next; | 919 edge = next; |
| 920 } | 920 } |
| 921 remove<Vertex, &Vertex::fPrev, &Vertex::fNext>(src, head, NULL); | 921 remove<Vertex, &Vertex::fPrev, &Vertex::fNext>(src, head, nullptr); |
| 922 } | 922 } |
| 923 | 923 |
| 924 Vertex* check_for_intersection(Edge* edge, Edge* other, EdgeList* activeEdges, C
omparator& c, | 924 Vertex* check_for_intersection(Edge* edge, Edge* other, EdgeList* activeEdges, C
omparator& c, |
| 925 SkChunkAlloc& alloc) { | 925 SkChunkAlloc& alloc) { |
| 926 SkPoint p; | 926 SkPoint p; |
| 927 if (!edge || !other) { | 927 if (!edge || !other) { |
| 928 return NULL; | 928 return nullptr; |
| 929 } | 929 } |
| 930 if (edge->intersect(*other, &p)) { | 930 if (edge->intersect(*other, &p)) { |
| 931 Vertex* v; | 931 Vertex* v; |
| 932 LOG("found intersection, pt is %g, %g\n", p.fX, p.fY); | 932 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)) { | 933 if (p == edge->fTop->fPoint || c.sweep_lt(p, edge->fTop->fPoint)) { |
| 934 split_edge(other, edge->fTop, activeEdges, c, alloc); | 934 split_edge(other, edge->fTop, activeEdges, c, alloc); |
| 935 v = edge->fTop; | 935 v = edge->fTop; |
| 936 } else if (p == edge->fBottom->fPoint || c.sweep_gt(p, edge->fBottom->fP
oint)) { | 936 } else if (p == edge->fBottom->fPoint || c.sweep_gt(p, edge->fBottom->fP
oint)) { |
| 937 split_edge(other, edge->fBottom, activeEdges, c, alloc); | 937 split_edge(other, edge->fBottom, activeEdges, c, alloc); |
| 938 v = edge->fBottom; | 938 v = edge->fBottom; |
| (...skipping 27 matching lines...) Expand all Loading... |
| 966 v->fPrev = prevV; | 966 v->fPrev = prevV; |
| 967 v->fNext = nextV; | 967 v->fNext = nextV; |
| 968 prevV->fNext = v; | 968 prevV->fNext = v; |
| 969 nextV->fPrev = v; | 969 nextV->fPrev = v; |
| 970 } | 970 } |
| 971 split_edge(edge, v, activeEdges, c, alloc); | 971 split_edge(edge, v, activeEdges, c, alloc); |
| 972 split_edge(other, v, activeEdges, c, alloc); | 972 split_edge(other, v, activeEdges, c, alloc); |
| 973 } | 973 } |
| 974 return v; | 974 return v; |
| 975 } | 975 } |
| 976 return NULL; | 976 return nullptr; |
| 977 } | 977 } |
| 978 | 978 |
| 979 void sanitize_contours(Vertex** contours, int contourCnt) { | 979 void sanitize_contours(Vertex** contours, int contourCnt) { |
| 980 for (int i = 0; i < contourCnt; ++i) { | 980 for (int i = 0; i < contourCnt; ++i) { |
| 981 SkASSERT(contours[i]); | 981 SkASSERT(contours[i]); |
| 982 for (Vertex* v = contours[i];;) { | 982 for (Vertex* v = contours[i];;) { |
| 983 if (coincident(v->fPrev->fPoint, v->fPoint)) { | 983 if (coincident(v->fPrev->fPoint, v->fPoint)) { |
| 984 LOG("vertex %g,%g coincident; removing\n", v->fPoint.fX, v->fPoi
nt.fY); | 984 LOG("vertex %g,%g coincident; removing\n", v->fPoint.fX, v->fPoi
nt.fY); |
| 985 if (v->fPrev == v) { | 985 if (v->fPrev == v) { |
| 986 contours[i] = NULL; | 986 contours[i] = nullptr; |
| 987 break; | 987 break; |
| 988 } | 988 } |
| 989 v->fPrev->fNext = v->fNext; | 989 v->fPrev->fNext = v->fNext; |
| 990 v->fNext->fPrev = v->fPrev; | 990 v->fNext->fPrev = v->fPrev; |
| 991 if (contours[i] == v) { | 991 if (contours[i] == v) { |
| 992 contours[i] = v->fNext; | 992 contours[i] = v->fNext; |
| 993 } | 993 } |
| 994 v = v->fPrev; | 994 v = v->fPrev; |
| 995 } else { | 995 } else { |
| 996 v = v->fNext; | 996 v = v->fNext; |
| 997 if (v == contours[i]) break; | 997 if (v == contours[i]) break; |
| 998 } | 998 } |
| 999 } | 999 } |
| 1000 } | 1000 } |
| 1001 } | 1001 } |
| 1002 | 1002 |
| 1003 void merge_coincident_vertices(Vertex** vertices, Comparator& c, SkChunkAlloc& a
lloc) { | 1003 void merge_coincident_vertices(Vertex** vertices, Comparator& c, SkChunkAlloc& a
lloc) { |
| 1004 for (Vertex* v = (*vertices)->fNext; v != NULL; v = v->fNext) { | 1004 for (Vertex* v = (*vertices)->fNext; v != nullptr; v = v->fNext) { |
| 1005 if (c.sweep_lt(v->fPoint, v->fPrev->fPoint)) { | 1005 if (c.sweep_lt(v->fPoint, v->fPrev->fPoint)) { |
| 1006 v->fPoint = v->fPrev->fPoint; | 1006 v->fPoint = v->fPrev->fPoint; |
| 1007 } | 1007 } |
| 1008 if (coincident(v->fPrev->fPoint, v->fPoint)) { | 1008 if (coincident(v->fPrev->fPoint, v->fPoint)) { |
| 1009 merge_vertices(v->fPrev, v, vertices, c, alloc); | 1009 merge_vertices(v->fPrev, v, vertices, c, alloc); |
| 1010 } | 1010 } |
| 1011 } | 1011 } |
| 1012 } | 1012 } |
| 1013 | 1013 |
| 1014 // Stage 2: convert the contours to a mesh of edges connecting the vertices. | 1014 // Stage 2: convert the contours to a mesh of edges connecting the vertices. |
| 1015 | 1015 |
| 1016 Vertex* build_edges(Vertex** contours, int contourCnt, Comparator& c, SkChunkAll
oc& alloc) { | 1016 Vertex* build_edges(Vertex** contours, int contourCnt, Comparator& c, SkChunkAll
oc& alloc) { |
| 1017 Vertex* vertices = NULL; | 1017 Vertex* vertices = nullptr; |
| 1018 Vertex* prev = NULL; | 1018 Vertex* prev = nullptr; |
| 1019 for (int i = 0; i < contourCnt; ++i) { | 1019 for (int i = 0; i < contourCnt; ++i) { |
| 1020 for (Vertex* v = contours[i]; v != NULL;) { | 1020 for (Vertex* v = contours[i]; v != nullptr;) { |
| 1021 Vertex* vNext = v->fNext; | 1021 Vertex* vNext = v->fNext; |
| 1022 Edge* edge = new_edge(v->fPrev, v, alloc, c); | 1022 Edge* edge = new_edge(v->fPrev, v, alloc, c); |
| 1023 if (edge->fWinding > 0) { | 1023 if (edge->fWinding > 0) { |
| 1024 insert_edge_below(edge, v->fPrev, c); | 1024 insert_edge_below(edge, v->fPrev, c); |
| 1025 insert_edge_above(edge, v, c); | 1025 insert_edge_above(edge, v, c); |
| 1026 } else { | 1026 } else { |
| 1027 insert_edge_below(edge, v, c); | 1027 insert_edge_below(edge, v, c); |
| 1028 insert_edge_above(edge, v->fPrev, c); | 1028 insert_edge_above(edge, v->fPrev, c); |
| 1029 } | 1029 } |
| 1030 merge_collinear_edges(edge, NULL, c); | 1030 merge_collinear_edges(edge, nullptr, c); |
| 1031 if (prev) { | 1031 if (prev) { |
| 1032 prev->fNext = v; | 1032 prev->fNext = v; |
| 1033 v->fPrev = prev; | 1033 v->fPrev = prev; |
| 1034 } else { | 1034 } else { |
| 1035 vertices = v; | 1035 vertices = v; |
| 1036 } | 1036 } |
| 1037 prev = v; | 1037 prev = v; |
| 1038 v = vNext; | 1038 v = vNext; |
| 1039 if (v == contours[i]) break; | 1039 if (v == contours[i]) break; |
| 1040 } | 1040 } |
| 1041 } | 1041 } |
| 1042 if (prev) { | 1042 if (prev) { |
| 1043 prev->fNext = vertices->fPrev = NULL; | 1043 prev->fNext = vertices->fPrev = nullptr; |
| 1044 } | 1044 } |
| 1045 return vertices; | 1045 return vertices; |
| 1046 } | 1046 } |
| 1047 | 1047 |
| 1048 // Stage 3: sort the vertices by increasing sweep direction. | 1048 // Stage 3: sort the vertices by increasing sweep direction. |
| 1049 | 1049 |
| 1050 Vertex* sorted_merge(Vertex* a, Vertex* b, Comparator& c); | 1050 Vertex* sorted_merge(Vertex* a, Vertex* b, Comparator& c); |
| 1051 | 1051 |
| 1052 void front_back_split(Vertex* v, Vertex** pFront, Vertex** pBack) { | 1052 void front_back_split(Vertex* v, Vertex** pFront, Vertex** pBack) { |
| 1053 Vertex* fast; | 1053 Vertex* fast; |
| 1054 Vertex* slow; | 1054 Vertex* slow; |
| 1055 if (!v || !v->fNext) { | 1055 if (!v || !v->fNext) { |
| 1056 *pFront = v; | 1056 *pFront = v; |
| 1057 *pBack = NULL; | 1057 *pBack = nullptr; |
| 1058 } else { | 1058 } else { |
| 1059 slow = v; | 1059 slow = v; |
| 1060 fast = v->fNext; | 1060 fast = v->fNext; |
| 1061 | 1061 |
| 1062 while (fast != NULL) { | 1062 while (fast != nullptr) { |
| 1063 fast = fast->fNext; | 1063 fast = fast->fNext; |
| 1064 if (fast != NULL) { | 1064 if (fast != nullptr) { |
| 1065 slow = slow->fNext; | 1065 slow = slow->fNext; |
| 1066 fast = fast->fNext; | 1066 fast = fast->fNext; |
| 1067 } | 1067 } |
| 1068 } | 1068 } |
| 1069 | 1069 |
| 1070 *pFront = v; | 1070 *pFront = v; |
| 1071 *pBack = slow->fNext; | 1071 *pBack = slow->fNext; |
| 1072 slow->fNext->fPrev = NULL; | 1072 slow->fNext->fPrev = nullptr; |
| 1073 slow->fNext = NULL; | 1073 slow->fNext = nullptr; |
| 1074 } | 1074 } |
| 1075 } | 1075 } |
| 1076 | 1076 |
| 1077 void merge_sort(Vertex** head, Comparator& c) { | 1077 void merge_sort(Vertex** head, Comparator& c) { |
| 1078 if (!*head || !(*head)->fNext) { | 1078 if (!*head || !(*head)->fNext) { |
| 1079 return; | 1079 return; |
| 1080 } | 1080 } |
| 1081 | 1081 |
| 1082 Vertex* a; | 1082 Vertex* a; |
| 1083 Vertex* b; | 1083 Vertex* b; |
| 1084 front_back_split(*head, &a, &b); | 1084 front_back_split(*head, &a, &b); |
| 1085 | 1085 |
| 1086 merge_sort(&a, c); | 1086 merge_sort(&a, c); |
| 1087 merge_sort(&b, c); | 1087 merge_sort(&b, c); |
| 1088 | 1088 |
| 1089 *head = sorted_merge(a, b, c); | 1089 *head = sorted_merge(a, b, c); |
| 1090 } | 1090 } |
| 1091 | 1091 |
| 1092 inline void append_vertex(Vertex* v, Vertex** head, Vertex** tail) { | 1092 inline void append_vertex(Vertex* v, Vertex** head, Vertex** tail) { |
| 1093 insert<Vertex, &Vertex::fPrev, &Vertex::fNext>(v, *tail, NULL, head, tail); | 1093 insert<Vertex, &Vertex::fPrev, &Vertex::fNext>(v, *tail, nullptr, head, tail
); |
| 1094 } | 1094 } |
| 1095 | 1095 |
| 1096 inline void append_vertex_list(Vertex* v, Vertex** head, Vertex** tail) { | 1096 inline void append_vertex_list(Vertex* v, Vertex** head, Vertex** tail) { |
| 1097 insert<Vertex, &Vertex::fPrev, &Vertex::fNext>(v, *tail, v->fNext, head, tai
l); | 1097 insert<Vertex, &Vertex::fPrev, &Vertex::fNext>(v, *tail, v->fNext, head, tai
l); |
| 1098 } | 1098 } |
| 1099 | 1099 |
| 1100 Vertex* sorted_merge(Vertex* a, Vertex* b, Comparator& c) { | 1100 Vertex* sorted_merge(Vertex* a, Vertex* b, Comparator& c) { |
| 1101 Vertex* head = NULL; | 1101 Vertex* head = nullptr; |
| 1102 Vertex* tail = NULL; | 1102 Vertex* tail = nullptr; |
| 1103 | 1103 |
| 1104 while (a && b) { | 1104 while (a && b) { |
| 1105 if (c.sweep_lt(a->fPoint, b->fPoint)) { | 1105 if (c.sweep_lt(a->fPoint, b->fPoint)) { |
| 1106 Vertex* next = a->fNext; | 1106 Vertex* next = a->fNext; |
| 1107 append_vertex(a, &head, &tail); | 1107 append_vertex(a, &head, &tail); |
| 1108 a = next; | 1108 a = next; |
| 1109 } else { | 1109 } else { |
| 1110 Vertex* next = b->fNext; | 1110 Vertex* next = b->fNext; |
| 1111 append_vertex(b, &head, &tail); | 1111 append_vertex(b, &head, &tail); |
| 1112 b = next; | 1112 b = next; |
| 1113 } | 1113 } |
| 1114 } | 1114 } |
| 1115 if (a) { | 1115 if (a) { |
| 1116 append_vertex_list(a, &head, &tail); | 1116 append_vertex_list(a, &head, &tail); |
| 1117 } | 1117 } |
| 1118 if (b) { | 1118 if (b) { |
| 1119 append_vertex_list(b, &head, &tail); | 1119 append_vertex_list(b, &head, &tail); |
| 1120 } | 1120 } |
| 1121 return head; | 1121 return head; |
| 1122 } | 1122 } |
| 1123 | 1123 |
| 1124 // Stage 4: Simplify the mesh by inserting new vertices at intersecting edges. | 1124 // Stage 4: Simplify the mesh by inserting new vertices at intersecting edges. |
| 1125 | 1125 |
| 1126 void simplify(Vertex* vertices, Comparator& c, SkChunkAlloc& alloc) { | 1126 void simplify(Vertex* vertices, Comparator& c, SkChunkAlloc& alloc) { |
| 1127 LOG("simplifying complex polygons\n"); | 1127 LOG("simplifying complex polygons\n"); |
| 1128 EdgeList activeEdges; | 1128 EdgeList activeEdges; |
| 1129 for (Vertex* v = vertices; v != NULL; v = v->fNext) { | 1129 for (Vertex* v = vertices; v != nullptr; v = v->fNext) { |
| 1130 if (!v->fFirstEdgeAbove && !v->fFirstEdgeBelow) { | 1130 if (!v->fFirstEdgeAbove && !v->fFirstEdgeBelow) { |
| 1131 continue; | 1131 continue; |
| 1132 } | 1132 } |
| 1133 #if LOGGING_ENABLED | 1133 #if LOGGING_ENABLED |
| 1134 LOG("\nvertex %g: (%g,%g)\n", v->fID, v->fPoint.fX, v->fPoint.fY); | 1134 LOG("\nvertex %g: (%g,%g)\n", v->fID, v->fPoint.fX, v->fPoint.fY); |
| 1135 #endif | 1135 #endif |
| 1136 Edge* leftEnclosingEdge = NULL; | 1136 Edge* leftEnclosingEdge = nullptr; |
| 1137 Edge* rightEnclosingEdge = NULL; | 1137 Edge* rightEnclosingEdge = nullptr; |
| 1138 bool restartChecks; | 1138 bool restartChecks; |
| 1139 do { | 1139 do { |
| 1140 restartChecks = false; | 1140 restartChecks = false; |
| 1141 find_enclosing_edges(v, &activeEdges, &leftEnclosingEdge, &rightEncl
osingEdge); | 1141 find_enclosing_edges(v, &activeEdges, &leftEnclosingEdge, &rightEncl
osingEdge); |
| 1142 if (v->fFirstEdgeBelow) { | 1142 if (v->fFirstEdgeBelow) { |
| 1143 for (Edge* edge = v->fFirstEdgeBelow; edge != NULL; edge = edge-
>fNextEdgeBelow) { | 1143 for (Edge* edge = v->fFirstEdgeBelow; edge != nullptr; edge = ed
ge->fNextEdgeBelow) { |
| 1144 if (check_for_intersection(edge, leftEnclosingEdge, &activeE
dges, c, alloc)) { | 1144 if (check_for_intersection(edge, leftEnclosingEdge, &activeE
dges, c, alloc)) { |
| 1145 restartChecks = true; | 1145 restartChecks = true; |
| 1146 break; | 1146 break; |
| 1147 } | 1147 } |
| 1148 if (check_for_intersection(edge, rightEnclosingEdge, &active
Edges, c, alloc)) { | 1148 if (check_for_intersection(edge, rightEnclosingEdge, &active
Edges, c, alloc)) { |
| 1149 restartChecks = true; | 1149 restartChecks = true; |
| 1150 break; | 1150 break; |
| 1151 } | 1151 } |
| 1152 } | 1152 } |
| 1153 } else { | 1153 } else { |
| (...skipping 17 matching lines...) Expand all Loading... |
| 1171 } | 1171 } |
| 1172 v->fProcessed = true; | 1172 v->fProcessed = true; |
| 1173 } | 1173 } |
| 1174 } | 1174 } |
| 1175 | 1175 |
| 1176 // Stage 5: Tessellate the simplified mesh into monotone polygons. | 1176 // Stage 5: Tessellate the simplified mesh into monotone polygons. |
| 1177 | 1177 |
| 1178 Poly* tessellate(Vertex* vertices, SkChunkAlloc& alloc) { | 1178 Poly* tessellate(Vertex* vertices, SkChunkAlloc& alloc) { |
| 1179 LOG("tessellating simple polygons\n"); | 1179 LOG("tessellating simple polygons\n"); |
| 1180 EdgeList activeEdges; | 1180 EdgeList activeEdges; |
| 1181 Poly* polys = NULL; | 1181 Poly* polys = nullptr; |
| 1182 for (Vertex* v = vertices; v != NULL; v = v->fNext) { | 1182 for (Vertex* v = vertices; v != nullptr; v = v->fNext) { |
| 1183 if (!v->fFirstEdgeAbove && !v->fFirstEdgeBelow) { | 1183 if (!v->fFirstEdgeAbove && !v->fFirstEdgeBelow) { |
| 1184 continue; | 1184 continue; |
| 1185 } | 1185 } |
| 1186 #if LOGGING_ENABLED | 1186 #if LOGGING_ENABLED |
| 1187 LOG("\nvertex %g: (%g,%g)\n", v->fID, v->fPoint.fX, v->fPoint.fY); | 1187 LOG("\nvertex %g: (%g,%g)\n", v->fID, v->fPoint.fX, v->fPoint.fY); |
| 1188 #endif | 1188 #endif |
| 1189 Edge* leftEnclosingEdge = NULL; | 1189 Edge* leftEnclosingEdge = nullptr; |
| 1190 Edge* rightEnclosingEdge = NULL; | 1190 Edge* rightEnclosingEdge = nullptr; |
| 1191 find_enclosing_edges(v, &activeEdges, &leftEnclosingEdge, &rightEnclosin
gEdge); | 1191 find_enclosing_edges(v, &activeEdges, &leftEnclosingEdge, &rightEnclosin
gEdge); |
| 1192 Poly* leftPoly = NULL; | 1192 Poly* leftPoly = nullptr; |
| 1193 Poly* rightPoly = NULL; | 1193 Poly* rightPoly = nullptr; |
| 1194 if (v->fFirstEdgeAbove) { | 1194 if (v->fFirstEdgeAbove) { |
| 1195 leftPoly = v->fFirstEdgeAbove->fLeftPoly; | 1195 leftPoly = v->fFirstEdgeAbove->fLeftPoly; |
| 1196 rightPoly = v->fLastEdgeAbove->fRightPoly; | 1196 rightPoly = v->fLastEdgeAbove->fRightPoly; |
| 1197 } else { | 1197 } else { |
| 1198 leftPoly = leftEnclosingEdge ? leftEnclosingEdge->fRightPoly : NULL; | 1198 leftPoly = leftEnclosingEdge ? leftEnclosingEdge->fRightPoly : nullp
tr; |
| 1199 rightPoly = rightEnclosingEdge ? rightEnclosingEdge->fLeftPoly : NUL
L; | 1199 rightPoly = rightEnclosingEdge ? rightEnclosingEdge->fLeftPoly : nul
lptr; |
| 1200 } | 1200 } |
| 1201 #if LOGGING_ENABLED | 1201 #if LOGGING_ENABLED |
| 1202 LOG("edges above:\n"); | 1202 LOG("edges above:\n"); |
| 1203 for (Edge* e = v->fFirstEdgeAbove; e; e = e->fNextEdgeAbove) { | 1203 for (Edge* e = v->fFirstEdgeAbove; e; e = e->fNextEdgeAbove) { |
| 1204 LOG("%g -> %g, lpoly %d, rpoly %d\n", e->fTop->fID, e->fBottom->fID, | 1204 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); | 1205 e->fLeftPoly ? e->fLeftPoly->fID : -1, e->fRightPoly ? e->fRight
Poly->fID : -1); |
| 1206 } | 1206 } |
| 1207 LOG("edges below:\n"); | 1207 LOG("edges below:\n"); |
| 1208 for (Edge* e = v->fFirstEdgeBelow; e; e = e->fNextEdgeBelow) { | 1208 for (Edge* e = v->fFirstEdgeBelow; e; e = e->fNextEdgeBelow) { |
| 1209 LOG("%g -> %g, lpoly %d, rpoly %d\n", e->fTop->fID, e->fBottom->fID, | 1209 LOG("%g -> %g, lpoly %d, rpoly %d\n", e->fTop->fID, e->fBottom->fID, |
| (...skipping 15 matching lines...) Expand all Loading... |
| 1225 if (leftEdge->fRightPoly) { | 1225 if (leftEdge->fRightPoly) { |
| 1226 leftEdge->fRightPoly->end(v, alloc); | 1226 leftEdge->fRightPoly->end(v, alloc); |
| 1227 } | 1227 } |
| 1228 if (rightEdge->fLeftPoly && rightEdge->fLeftPoly != leftEdge->fR
ightPoly) { | 1228 if (rightEdge->fLeftPoly && rightEdge->fLeftPoly != leftEdge->fR
ightPoly) { |
| 1229 rightEdge->fLeftPoly->end(v, alloc); | 1229 rightEdge->fLeftPoly->end(v, alloc); |
| 1230 } | 1230 } |
| 1231 } | 1231 } |
| 1232 remove_edge(v->fLastEdgeAbove, &activeEdges); | 1232 remove_edge(v->fLastEdgeAbove, &activeEdges); |
| 1233 if (!v->fFirstEdgeBelow) { | 1233 if (!v->fFirstEdgeBelow) { |
| 1234 if (leftPoly && rightPoly && leftPoly != rightPoly) { | 1234 if (leftPoly && rightPoly && leftPoly != rightPoly) { |
| 1235 SkASSERT(leftPoly->fPartner == NULL && rightPoly->fPartner =
= NULL); | 1235 SkASSERT(leftPoly->fPartner == nullptr && rightPoly->fPartne
r == nullptr); |
| 1236 rightPoly->fPartner = leftPoly; | 1236 rightPoly->fPartner = leftPoly; |
| 1237 leftPoly->fPartner = rightPoly; | 1237 leftPoly->fPartner = rightPoly; |
| 1238 } | 1238 } |
| 1239 } | 1239 } |
| 1240 } | 1240 } |
| 1241 if (v->fFirstEdgeBelow) { | 1241 if (v->fFirstEdgeBelow) { |
| 1242 if (!v->fFirstEdgeAbove) { | 1242 if (!v->fFirstEdgeAbove) { |
| 1243 if (leftPoly && leftPoly == rightPoly) { | 1243 if (leftPoly && leftPoly == rightPoly) { |
| 1244 // Split the poly. | 1244 // Split the poly. |
| 1245 if (leftPoly->fActive->fSide == Poly::kLeft_Side) { | 1245 if (leftPoly->fActive->fSide == Poly::kLeft_Side) { |
| (...skipping 29 matching lines...) Expand all Loading... |
| 1275 if (winding != 0) { | 1275 if (winding != 0) { |
| 1276 Poly* poly = new_poly(&polys, v, winding, alloc); | 1276 Poly* poly = new_poly(&polys, v, winding, alloc); |
| 1277 leftEdge->fRightPoly = rightEdge->fLeftPoly = poly; | 1277 leftEdge->fRightPoly = rightEdge->fLeftPoly = poly; |
| 1278 } | 1278 } |
| 1279 leftEdge = rightEdge; | 1279 leftEdge = rightEdge; |
| 1280 } | 1280 } |
| 1281 v->fLastEdgeBelow->fRightPoly = rightPoly; | 1281 v->fLastEdgeBelow->fRightPoly = rightPoly; |
| 1282 } | 1282 } |
| 1283 #if LOGGING_ENABLED | 1283 #if LOGGING_ENABLED |
| 1284 LOG("\nactive edges:\n"); | 1284 LOG("\nactive edges:\n"); |
| 1285 for (Edge* e = activeEdges.fHead; e != NULL; e = e->fRight) { | 1285 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, | 1286 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); | 1287 e->fLeftPoly ? e->fLeftPoly->fID : -1, e->fRightPoly ? e->fRight
Poly->fID : -1); |
| 1288 } | 1288 } |
| 1289 #endif | 1289 #endif |
| 1290 } | 1290 } |
| 1291 return polys; | 1291 return polys; |
| 1292 } | 1292 } |
| 1293 | 1293 |
| 1294 // This is a driver function which calls stages 2-5 in turn. | 1294 // This is a driver function which calls stages 2-5 in turn. |
| 1295 | 1295 |
| 1296 Poly* contours_to_polys(Vertex** contours, int contourCnt, Comparator& c, SkChun
kAlloc& alloc) { | 1296 Poly* contours_to_polys(Vertex** contours, int contourCnt, Comparator& c, SkChun
kAlloc& alloc) { |
| 1297 #if LOGGING_ENABLED | 1297 #if LOGGING_ENABLED |
| 1298 for (int i = 0; i < contourCnt; ++i) { | 1298 for (int i = 0; i < contourCnt; ++i) { |
| 1299 Vertex* v = contours[i]; | 1299 Vertex* v = contours[i]; |
| 1300 SkASSERT(v); | 1300 SkASSERT(v); |
| 1301 LOG("path.moveTo(%20.20g, %20.20g);\n", v->fPoint.fX, v->fPoint.fY); | 1301 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) { | 1302 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); | 1303 LOG("path.lineTo(%20.20g, %20.20g);\n", v->fPoint.fX, v->fPoint.fY); |
| 1304 } | 1304 } |
| 1305 } | 1305 } |
| 1306 #endif | 1306 #endif |
| 1307 sanitize_contours(contours, contourCnt); | 1307 sanitize_contours(contours, contourCnt); |
| 1308 Vertex* vertices = build_edges(contours, contourCnt, c, alloc); | 1308 Vertex* vertices = build_edges(contours, contourCnt, c, alloc); |
| 1309 if (!vertices) { | 1309 if (!vertices) { |
| 1310 return NULL; | 1310 return nullptr; |
| 1311 } | 1311 } |
| 1312 | 1312 |
| 1313 // Sort vertices in Y (secondarily in X). | 1313 // Sort vertices in Y (secondarily in X). |
| 1314 merge_sort(&vertices, c); | 1314 merge_sort(&vertices, c); |
| 1315 merge_coincident_vertices(&vertices, c, alloc); | 1315 merge_coincident_vertices(&vertices, c, alloc); |
| 1316 #if LOGGING_ENABLED | 1316 #if LOGGING_ENABLED |
| 1317 for (Vertex* v = vertices; v != NULL; v = v->fNext) { | 1317 for (Vertex* v = vertices; v != nullptr; v = v->fNext) { |
| 1318 static float gID = 0.0f; | 1318 static float gID = 0.0f; |
| 1319 v->fID = gID++; | 1319 v->fID = gID++; |
| 1320 } | 1320 } |
| 1321 #endif | 1321 #endif |
| 1322 simplify(vertices, c, alloc); | 1322 simplify(vertices, c, alloc); |
| 1323 return tessellate(vertices, alloc); | 1323 return tessellate(vertices, alloc); |
| 1324 } | 1324 } |
| 1325 | 1325 |
| 1326 // Stage 6: Triangulate the monotone polygons into a vertex buffer. | 1326 // Stage 6: Triangulate the monotone polygons into a vertex buffer. |
| 1327 | 1327 |
| (...skipping 44 matching lines...) Expand 10 before | Expand all | Expand 10 after Loading... |
| 1372 SkMessageBus<GrUniqueKeyInvalidatedMessage>::Post(fMsg); | 1372 SkMessageBus<GrUniqueKeyInvalidatedMessage>::Post(fMsg); |
| 1373 } | 1373 } |
| 1374 }; | 1374 }; |
| 1375 | 1375 |
| 1376 } // namespace | 1376 } // namespace |
| 1377 | 1377 |
| 1378 bool GrTessellatingPathRenderer::onCanDrawPath(const CanDrawPathArgs& args) cons
t { | 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 | 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 | 1380 // not do antialiasing. It can do convex and concave paths, but we'll leave
the convex ones to |
| 1381 // simpler algorithms. | 1381 // simpler algorithms. |
| 1382 return !IsStrokeHairlineOrEquivalent(*args.fStroke, *args.fViewMatrix, NULL)
&& | 1382 return !IsStrokeHairlineOrEquivalent(*args.fStroke, *args.fViewMatrix, nullp
tr) && |
| 1383 !args.fAntiAlias && !args.fPath->isConvex(); | 1383 !args.fAntiAlias && !args.fPath->isConvex(); |
| 1384 } | 1384 } |
| 1385 | 1385 |
| 1386 class TessellatingPathBatch : public GrVertexBatch { | 1386 class TessellatingPathBatch : public GrVertexBatch { |
| 1387 public: | 1387 public: |
| 1388 | 1388 |
| 1389 static GrDrawBatch* Create(const GrColor& color, | 1389 static GrDrawBatch* Create(const GrColor& color, |
| 1390 const SkPath& path, | 1390 const SkPath& path, |
| 1391 const GrStrokeInfo& stroke, | 1391 const GrStrokeInfo& stroke, |
| 1392 const SkMatrix& viewMatrix, | 1392 const SkMatrix& viewMatrix, |
| (...skipping 219 matching lines...) Expand 10 before | Expand all | Expand 10 after Loading... |
| 1612 SkPath fPath; | 1612 SkPath fPath; |
| 1613 GrStrokeInfo fStroke; | 1613 GrStrokeInfo fStroke; |
| 1614 SkMatrix fViewMatrix; | 1614 SkMatrix fViewMatrix; |
| 1615 SkRect fClipBounds; // in source space | 1615 SkRect fClipBounds; // in source space |
| 1616 GrPipelineOptimizations fPipelineInfo; | 1616 GrPipelineOptimizations fPipelineInfo; |
| 1617 }; | 1617 }; |
| 1618 | 1618 |
| 1619 bool GrTessellatingPathRenderer::onDrawPath(const DrawPathArgs& args) { | 1619 bool GrTessellatingPathRenderer::onDrawPath(const DrawPathArgs& args) { |
| 1620 SkASSERT(!args.fAntiAlias); | 1620 SkASSERT(!args.fAntiAlias); |
| 1621 const GrRenderTarget* rt = args.fPipelineBuilder->getRenderTarget(); | 1621 const GrRenderTarget* rt = args.fPipelineBuilder->getRenderTarget(); |
| 1622 if (NULL == rt) { | 1622 if (nullptr == rt) { |
| 1623 return false; | 1623 return false; |
| 1624 } | 1624 } |
| 1625 | 1625 |
| 1626 SkIRect clipBoundsI; | 1626 SkIRect clipBoundsI; |
| 1627 args.fPipelineBuilder->clip().getConservativeBounds(rt, &clipBoundsI); | 1627 args.fPipelineBuilder->clip().getConservativeBounds(rt, &clipBoundsI); |
| 1628 SkRect clipBounds = SkRect::Make(clipBoundsI); | 1628 SkRect clipBounds = SkRect::Make(clipBoundsI); |
| 1629 SkMatrix vmi; | 1629 SkMatrix vmi; |
| 1630 if (!args.fViewMatrix->invert(&vmi)) { | 1630 if (!args.fViewMatrix->invert(&vmi)) { |
| 1631 return false; | 1631 return false; |
| 1632 } | 1632 } |
| (...skipping 19 matching lines...) Expand all Loading... |
| 1652 bool result = viewMatrix.invert(&vmi); | 1652 bool result = viewMatrix.invert(&vmi); |
| 1653 if (!result) { | 1653 if (!result) { |
| 1654 SkFAIL("Cannot invert matrix\n"); | 1654 SkFAIL("Cannot invert matrix\n"); |
| 1655 } | 1655 } |
| 1656 vmi.mapRect(&clipBounds); | 1656 vmi.mapRect(&clipBounds); |
| 1657 GrStrokeInfo strokeInfo = GrTest::TestStrokeInfo(random); | 1657 GrStrokeInfo strokeInfo = GrTest::TestStrokeInfo(random); |
| 1658 return TessellatingPathBatch::Create(color, path, strokeInfo, viewMatrix, cl
ipBounds); | 1658 return TessellatingPathBatch::Create(color, path, strokeInfo, viewMatrix, cl
ipBounds); |
| 1659 } | 1659 } |
| 1660 | 1660 |
| 1661 #endif | 1661 #endif |
| OLD | NEW |