Chromium Code Reviews
chromiumcodereview-hr@appspot.gserviceaccount.com (chromiumcodereview-hr) | Please choose your nickname with Settings | Help | Chromium Project | Gerrit Changes | Sign out
(239)

Issues Search
    My Issues | Starred     Open | Closed | All

Unified Diff: src/gpu/GrTessellator.cpp

Issue 2029243002: Tessellator: stop copying vertices into Polys and Monotones. (Closed) Base URL: https://skia.googlesource.com/skia.git@master
Patch Set: Created 4 years, 7 months ago
Use n/p to move between diff chunks; N/P to move between comments. Draft comments are only viewable by you.
Jump to:
View side-by-side diff with in-line comments
Download patch
« no previous file with comments | « no previous file | no next file » | no next file with comments »
Expand Comments ('e') | Collapse Comments ('c') | Show Comments Hide Comments ('s')
Index: src/gpu/GrTessellator.cpp
diff --git a/src/gpu/GrTessellator.cpp b/src/gpu/GrTessellator.cpp
index 5fb008dad5047a1f5c5db7a3977d13b171b44471..6b7b6c3bbcc56431d157399e3e467b9f5aaa2c7c 100644
--- a/src/gpu/GrTessellator.cpp
+++ b/src/gpu/GrTessellator.cpp
@@ -204,21 +204,26 @@ struct EdgeList {
Edge* fTail;
};
-struct VertexList {
- VertexList() : fHead(nullptr), fTail(nullptr) {}
- Vertex* fHead;
- Vertex* fTail;
- void insert(Vertex* v, Vertex* prev, Vertex* next) {
- list_insert<Vertex, &Vertex::fPrev, &Vertex::fNext>(v, prev, next, &fHead, &fTail);
+template<class T> struct List {
+ List() : fHead(nullptr), fTail(nullptr) {}
+ T* fHead;
+ T* fTail;
+ void insert(T* t, T* prev, T* next) {
+ list_insert<T, &T::fPrev, &T::fNext>(t, prev, next, &fHead, &fTail);
}
- void append(Vertex* v) {
- insert(v, fTail, nullptr);
+ void append(T* t) {
+ insert(t, fTail, nullptr);
}
- void prepend(Vertex* v) {
- insert(v, nullptr, fHead);
+ void prepend(T* t) {
+ insert(t, nullptr, fHead);
+ }
+ void remove(T* t) {
+ list_remove<T, &T::fPrev, &T::fNext>(t, &fHead, &fTail);
}
};
+typedef List<Vertex> VertexList;
+
/**
* An Edge joins a top Vertex to a bottom Vertex. Edge ordering for the list of "edges above" and
* "edge below" a vertex as well as for the active edge list is handled by isLeftOf()/isRightOf().
@@ -249,7 +254,11 @@ struct Edge {
, fPrevEdgeBelow(nullptr)
, fNextEdgeBelow(nullptr)
, fLeftPoly(nullptr)
- , fRightPoly(nullptr) {
+ , fRightPoly(nullptr)
+ , fLeftPolyPrev(nullptr)
+ , fLeftPolyNext(nullptr)
+ , fRightPolyPrev(nullptr)
+ , fRightPolyNext(nullptr) {
recompute();
}
int fWinding; // 1 == edge goes downward; -1 = edge goes upward.
@@ -263,6 +272,10 @@ struct Edge {
Edge* fNextEdgeBelow; // "
Poly* fLeftPoly; // The Poly to the left of this edge, if any.
Poly* fRightPoly; // The Poly to the right of this edge, if any.
+ Edge* fLeftPolyPrev;
+ Edge* fLeftPolyNext;
+ Edge* fRightPolyPrev;
+ Edge* fRightPolyNext;
double fDX; // The line equation for this edge, in implicit form.
double fDY; // fDY * x + fDX * y + fC = 0, for point (x, y) on the line.
double fC;
@@ -316,11 +329,9 @@ struct Edge {
/***************************************************************************************/
struct Poly {
- Poly(int winding)
- : fWinding(winding)
- , fHead(nullptr)
- , fTail(nullptr)
- , fActive(nullptr)
+ Poly(Vertex* v, int winding)
+ : fFirstVertex(v)
+ , fWinding(winding)
, fNext(nullptr)
, fPartner(nullptr)
, fCount(0)
@@ -331,36 +342,49 @@ struct Poly {
LOG("*** created Poly %d\n", fID);
#endif
}
- typedef enum { kNeither_Side, kLeft_Side, kRight_Side } Side;
+ typedef enum { kLeft_Side, kRight_Side } Side;
struct MonotonePoly {
- MonotonePoly()
- : fSide(kNeither_Side)
+ MonotonePoly(Edge* edge, Side side)
+ : fSide(side)
+ , fFirstEdge(nullptr)
+ , fLastEdge(nullptr)
, fPrev(nullptr)
- , fNext(nullptr) {}
+ , fNext(nullptr) {
+ addEdge(edge);
+ }
Side fSide;
- VertexList fVertices;
+ Edge* fFirstEdge;
+ Edge* fLastEdge;
MonotonePoly* fPrev;
MonotonePoly* fNext;
- bool addVertex(Vertex* v, Side side, SkChunkAlloc& alloc) {
- Vertex* newV = ALLOC_NEW(Vertex, (v->fPoint), alloc);
- bool done = false;
- if (fSide == kNeither_Side) {
- fSide = side;
- } else {
- done = side != fSide;
- }
+ void addEdge(Edge* edge) {
if (fSide == kRight_Side) {
- fVertices.append(newV);
+ list_insert<Edge, &Edge::fRightPolyPrev, &Edge::fRightPolyNext>(
+ edge, fLastEdge, nullptr, &fFirstEdge, &fLastEdge);
} else {
- fVertices.prepend(newV);
+ list_insert<Edge, &Edge::fLeftPolyPrev, &Edge::fLeftPolyNext>(
+ edge, fLastEdge, nullptr, &fFirstEdge, &fLastEdge);
}
- return done;
}
SkPoint* emit(SkPoint* data) {
- Vertex* first = fVertices.fHead;
+ Edge* e = fFirstEdge;
+ e->fTop->fPrev = e->fTop->fNext = nullptr;
+ VertexList vertices;
+ vertices.append(e->fTop);
+ while (e != nullptr) {
+ e->fBottom->fPrev = e->fBottom->fNext = nullptr;
+ if (kRight_Side == fSide) {
+ vertices.append(e->fBottom);
+ e = e->fRightPolyNext;
+ } else {
+ vertices.prepend(e->fBottom);
+ e = e->fLeftPolyNext;
+ }
+ }
+ Vertex* first = vertices.fHead;
Vertex* v = first->fNext;
- while (v != fVertices.fTail) {
+ while (v != vertices.fTail) {
SkASSERT(v && v->fPrev && v->fNext);
Vertex* prev = v->fPrev;
Vertex* curr = v;
@@ -385,60 +409,56 @@ struct Poly {
return data;
}
};
- Poly* addVertex(Vertex* v, Side side, SkChunkAlloc& alloc) {
- LOG("addVertex() to %d at %g (%g, %g), %s side\n", fID, v->fID, v->fPoint.fX, v->fPoint.fY,
- side == kLeft_Side ? "left" : side == kRight_Side ? "right" : "neither");
+ void addEdge(Edge* e, Side side, SkChunkAlloc& alloc) {
+ LOG("addEdge (%g,%g)-(%g,%g) to poly %d, %s side\n",
+ e->fTop->fPoint.fX, e->fTop->fPoint.fY,
+ e->fBottom->fPoint.fX, e->fBottom->fPoint.fY,
robertphillips 2016/06/02 12:19:48 Does the "neither" case still make sense ?
Stephen White 2016/06/02 18:01:21 Good point. Removed.
+ fID, side == kLeft_Side ? "left" : side == kRight_Side ? "right" : "neither");
Poly* partner = fPartner;
- Poly* poly = this;
if (partner) {
fPartner = partner->fPartner = nullptr;
}
- if (!fActive) {
- fActive = ALLOC_NEW(MonotonePoly, (), alloc);
- }
- if (fActive->addVertex(v, side, alloc)) {
- if (fTail) {
- fActive->fPrev = fTail;
- fTail->fNext = fActive;
- fTail = fActive;
- } else {
- fHead = fTail = fActive;
+ if (!fMonotones.fTail) {
+ fMonotones.append(ALLOC_NEW(MonotonePoly, (e, side), alloc));
+ fCount += 2;
+ } else if (side == fMonotones.fTail->fSide) {
+ fMonotones.fTail->addEdge(e);
+ fCount++;
+ } else {
+ if (e->fBottom == fMonotones.fTail->fLastEdge->fBottom) {
+ return;
}
+ e = ALLOC_NEW(Edge, (fMonotones.fTail->fLastEdge->fBottom, e->fBottom, 1), alloc);
+ fMonotones.fTail->addEdge(e);
+ fCount++;
+ MonotonePoly* m;
if (partner) {
- partner->addVertex(v, side, alloc);
- poly = partner;
+ m = partner->fMonotones.fTail;
+ m->addEdge(e);
+ partner->fMonotones.remove(m);
} else {
- Vertex* prev = fActive->fSide == Poly::kLeft_Side ?
- fActive->fVertices.fHead->fNext : fActive->fVertices.fTail->fPrev;
- fActive = ALLOC_NEW(MonotonePoly, , alloc);
- fActive->addVertex(prev, Poly::kNeither_Side, alloc);
- fActive->addVertex(v, side, alloc);
+ m = ALLOC_NEW(MonotonePoly, (e, side), alloc);
}
+ fCount += 2;
+ fMonotones.append(m);
}
- fCount++;
- return poly;
- }
- void end(Vertex* v, SkChunkAlloc& alloc) {
- LOG("end() %d at %g, %g\n", fID, v->fPoint.fX, v->fPoint.fY);
- if (fPartner) {
- fPartner = fPartner->fPartner = nullptr;
- }
- addVertex(v, fActive->fSide == kLeft_Side ? kRight_Side : kLeft_Side, alloc);
}
SkPoint* emit(SkPoint *data) {
if (fCount < 3) {
return data;
}
LOG("emit() %d, size %d\n", fID, fCount);
- for (MonotonePoly* m = fHead; m != nullptr; m = m->fNext) {
+ for (MonotonePoly* m = fMonotones.fHead; m != nullptr; m = m->fNext) {
data = m->emit(data);
}
return data;
}
+ Vertex* lastVertex() const {
+ return fMonotones.fTail ? fMonotones.fTail->fLastEdge->fBottom : fFirstVertex;
+ }
+ Vertex* fFirstVertex;
int fWinding;
- MonotonePoly* fHead;
- MonotonePoly* fTail;
- MonotonePoly* fActive;
+ List<MonotonePoly> fMonotones;
Poly* fNext;
Poly* fPartner;
int fCount;
@@ -454,8 +474,7 @@ bool coincident(const SkPoint& a, const SkPoint& b) {
}
Poly* new_poly(Poly** head, Vertex* v, int winding, SkChunkAlloc& alloc) {
- Poly* poly = ALLOC_NEW(Poly, (winding), alloc);
- poly->addVertex(v, Poly::kNeither_Side, alloc);
+ Poly* poly = ALLOC_NEW(Poly, (v, winding), alloc);
poly->fNext = *head;
*head = poly;
return poly;
@@ -1195,25 +1214,15 @@ Poly* tessellate(Vertex* vertices, SkChunkAlloc& alloc) {
}
#endif
if (v->fFirstEdgeAbove) {
robertphillips 2016/06/02 12:19:48 Either "nullptr != e" or "e" ?
- if (leftPoly) {
- leftPoly = leftPoly->addVertex(v, Poly::kRight_Side, alloc);
- }
- if (rightPoly) {
- rightPoly = rightPoly->addVertex(v, Poly::kLeft_Side, alloc);
- }
- for (Edge* e = v->fFirstEdgeAbove; e != v->fLastEdgeAbove; e = e->fNextEdgeAbove) {
- Edge* leftEdge = e;
- Edge* rightEdge = e->fNextEdgeAbove;
- SkASSERT(rightEdge->isRightOf(leftEdge->fTop));
- remove_edge(leftEdge, &activeEdges);
- if (leftEdge->fRightPoly) {
- leftEdge->fRightPoly->end(v, alloc);
+ for (Edge* e = v->fFirstEdgeAbove; e != nullptr; e = e->fNextEdgeAbove) {
+ remove_edge(e, &activeEdges);
+ if (e->fLeftPoly) {
+ e->fLeftPoly->addEdge(e, Poly::kRight_Side, alloc);
}
- if (rightEdge->fLeftPoly && rightEdge->fLeftPoly != leftEdge->fRightPoly) {
- rightEdge->fLeftPoly->end(v, alloc);
+ if (e->fRightPoly) {
+ e->fRightPoly->addEdge(e, Poly::kLeft_Side, alloc);
}
}
- remove_edge(v->fLastEdgeAbove, &activeEdges);
if (!v->fFirstEdgeBelow) {
if (leftPoly && rightPoly && leftPoly != rightPoly) {
SkASSERT(leftPoly->fPartner == nullptr && rightPoly->fPartner == nullptr);
@@ -1224,28 +1233,22 @@ Poly* tessellate(Vertex* vertices, SkChunkAlloc& alloc) {
}
if (v->fFirstEdgeBelow) {
if (!v->fFirstEdgeAbove) {
- if (leftPoly && leftPoly == rightPoly) {
- // Split the poly.
- if (leftPoly->fActive->fSide == Poly::kLeft_Side) {
- leftPoly = new_poly(&polys, leftEnclosingEdge->fTop, leftPoly->fWinding,
- alloc);
- leftPoly->addVertex(v, Poly::kRight_Side, alloc);
- rightPoly->addVertex(v, Poly::kLeft_Side, alloc);
- leftEnclosingEdge->fRightPoly = leftPoly;
- } else {
- rightPoly = new_poly(&polys, rightEnclosingEdge->fTop, rightPoly->fWinding,
- alloc);
- rightPoly->addVertex(v, Poly::kLeft_Side, alloc);
- leftPoly->addVertex(v, Poly::kRight_Side, alloc);
- rightEnclosingEdge->fLeftPoly = rightPoly;
- }
- } else {
- if (leftPoly) {
- leftPoly = leftPoly->addVertex(v, Poly::kRight_Side, alloc);
- }
- if (rightPoly) {
- rightPoly = rightPoly->addVertex(v, Poly::kLeft_Side, alloc);
+ if (leftPoly) {
+ if (leftPoly == rightPoly) {
+ if (leftPoly->fMonotones.fTail &&
+ leftPoly->fMonotones.fTail->fSide == Poly::kLeft_Side) {
+ leftPoly = new_poly(&polys, leftPoly->lastVertex(),
+ leftPoly->fWinding, alloc);
+ leftEnclosingEdge->fRightPoly = leftPoly;
+ } else {
+ rightPoly = new_poly(&polys, rightPoly->lastVertex(),
+ rightPoly->fWinding, alloc);
+ rightEnclosingEdge->fLeftPoly = rightPoly;
+ }
}
+ Edge* join = ALLOC_NEW(Edge, (leftPoly->lastVertex(), v, 1), alloc);
+ leftPoly->addEdge(join, Poly::kRight_Side, alloc);
+ rightPoly->addEdge(join, Poly::kLeft_Side, alloc);
}
}
Edge* leftEdge = v->fFirstEdgeBelow;
« no previous file with comments | « no previous file | no next file » | no next file with comments »

Powered by Google App Engine
This is Rietveld 408576698