aboutsummaryrefslogtreecommitdiffhomepage
diff options
context:
space:
mode:
Diffstat
-rw-r--r--gm/concavepaths.cpp15
-rw-r--r--src/gpu/GrTessellator.cpp340
2 files changed, 188 insertions, 167 deletions
diff --git a/gm/concavepaths.cpp b/gm/concavepaths.cpp
index 890f6c0855..fe8a1418ab 100644
--- a/gm/concavepaths.cpp
+++ b/gm/concavepaths.cpp
@@ -159,6 +159,20 @@ void test_star(SkCanvas* canvas, const SkPaint& paint) {
canvas->restore();
}
+// Exercise a case where the intersection is below a bottom edge.
+void test_twist(SkCanvas* canvas, const SkPaint& paint) {
+ SkPath path;
+ canvas->save();
+ path.moveTo( 0.5, 6);
+ path.lineTo(5.8070392608642578125, 6.4612660408020019531);
+ path.lineTo(-2.9186885356903076172, 2.811046600341796875);
+ path.lineTo(0.49999994039535522461, -1.4124038219451904297);
+ canvas->translate(420, 220);
+ canvas->scale(10, 10);
+ canvas->drawPath(path, paint);
+ canvas->restore();
+}
+
// Stairstep with repeated vert (intersection)
void test_stairstep(SkCanvas* canvas, const SkPaint& paint) {
SkPath path;
@@ -409,6 +423,7 @@ DEF_SIMPLE_GM(concavepaths, canvas, 500, 600) {
test_fast_forward(canvas, paint);
test_hole(canvas, paint);
test_star(canvas, paint);
+ test_twist(canvas, paint);
test_inversion_repeat_vertex(canvas, paint);
test_stairstep(canvas, paint);
test_stairstep2(canvas, paint);
diff --git a/src/gpu/GrTessellator.cpp b/src/gpu/GrTessellator.cpp
index de14afe40e..6e9665f7c7 100644
--- a/src/gpu/GrTessellator.cpp
+++ b/src/gpu/GrTessellator.cpp
@@ -50,17 +50,15 @@
* line-sweep algorithm, but due to floating point inaccuracy, the intersection points are
* not exact and may violate the mesh topology or active edge list ordering. We
* accommodate this by adjusting the topology of the mesh and AEL to match the intersection
- * points. This occurs in three ways:
+ * points. This occurs in two ways:
*
* A) Intersections may cause a shortened edge to no longer be ordered with respect to its
* neighbouring edges at the top or bottom vertex. This is handled by merging the
* edges (merge_collinear_edges()).
* B) Intersections may cause an edge to violate the left-to-right ordering of the
- * active edge list. This is handled by splitting the neighbour edge on the
- * intersected vertex (cleanup_active_edges()).
- * C) Shortening an edge may cause an active edge to become inactive or an inactive edge
- * to become active. This is handled by removing or inserting the edge in the active
- * edge list (fix_active_state()).
+ * active edge list. This is handled by detecting potential violati0ns and rewinding
+ * the active edge list to the vertex before they occur (rewind() during merging,
+ * rewind_if_necessary() during splitting).
*
* The tessellation steps (5) and (6) are based on "Triangulating Simple Polygons and
* Equivalent Problems" (Fournier and Montuno); also a line-sweep algorithm. Note that it
@@ -145,25 +143,26 @@ struct Vertex {
: fPoint(point), fPrev(nullptr), fNext(nullptr)
, fFirstEdgeAbove(nullptr), fLastEdgeAbove(nullptr)
, fFirstEdgeBelow(nullptr), fLastEdgeBelow(nullptr)
+ , fLeftEnclosingEdge(nullptr), fRightEnclosingEdge(nullptr)
, fPartner(nullptr)
- , fProcessed(false)
, fAlpha(alpha)
#if LOGGING_ENABLED
, fID (-1.0f)
#endif
{}
- SkPoint fPoint; // Vertex position
- Vertex* fPrev; // Linked list of contours, then Y-sorted vertices.
- Vertex* fNext; // "
- Edge* fFirstEdgeAbove; // Linked list of edges above this vertex.
- Edge* fLastEdgeAbove; // "
- Edge* fFirstEdgeBelow; // Linked list of edges below this vertex.
- Edge* fLastEdgeBelow; // "
- Vertex* fPartner; // Corresponding inner or outer vertex (for AA).
- bool fProcessed; // Has this vertex been seen in simplify()?
+ SkPoint fPoint; // Vertex position
+ Vertex* fPrev; // Linked list of contours, then Y-sorted vertices.
+ Vertex* fNext; // "
+ Edge* fFirstEdgeAbove; // Linked list of edges above this vertex.
+ Edge* fLastEdgeAbove; // "
+ Edge* fFirstEdgeBelow; // Linked list of edges below this vertex.
+ Edge* fLastEdgeBelow; // "
+ Edge* fLeftEnclosingEdge; // Nearest edge in the AEL left of this vertex.
+ Edge* fRightEnclosingEdge; // Nearest edge in the AEL right of this vertex.
+ Vertex* fPartner; // Corresponding inner or outer vertex (for AA).
uint8_t fAlpha;
#if LOGGING_ENABLED
- float fID; // Identifier used for logging.
+ float fID; // Identifier used for logging.
#endif
};
@@ -312,7 +311,7 @@ struct Line {
* "edge below" a vertex as well as for the active edge list is handled by isLeftOf()/isRightOf().
* Note that an Edge will give occasionally dist() != 0 for its own endpoints (because floating
* point). For speed, that case is only tested by the callers that require it (e.g.,
- * cleanup_active_edges()). Edges also handle checking for intersection with other edges.
+ * rewind_if_necessary()). Edges also handle checking for intersection with other edges.
* Currently, this converts the edges to the parametric form, in order to avoid doing a division
* until an intersection has been confirmed. This is slightly slower in the "found" case, but
* a lot faster in the "not found" case.
@@ -808,40 +807,6 @@ void find_enclosing_edges(Vertex* v, EdgeList* edges, Edge** left, Edge** right)
*right = next;
}
-void find_enclosing_edges(Edge* edge, EdgeList* edges, Comparator& c, Edge** left, Edge** right) {
- Edge* prev = nullptr;
- Edge* next;
- for (next = edges->fHead; next != nullptr; next = next->fRight) {
- if ((c.sweep_lt(next->fTop->fPoint, edge->fTop->fPoint) && next->isRightOf(edge->fTop)) ||
- (c.sweep_lt(edge->fTop->fPoint, next->fTop->fPoint) && edge->isLeftOf(next->fTop)) ||
- (c.sweep_lt(edge->fBottom->fPoint, next->fBottom->fPoint) &&
- next->isRightOf(edge->fBottom)) ||
- (c.sweep_lt(next->fBottom->fPoint, edge->fBottom->fPoint) &&
- edge->isLeftOf(next->fBottom))) {
- break;
- }
- prev = next;
- }
- *left = prev;
- *right = next;
-}
-
-void fix_active_state(Edge* edge, EdgeList* activeEdges, Comparator& c) {
- if (!activeEdges) {
- return;
- }
- if (activeEdges->contains(edge)) {
- if (edge->fBottom->fProcessed || !edge->fTop->fProcessed) {
- remove_edge(edge, activeEdges);
- }
- } else if (edge->fTop->fProcessed && !edge->fBottom->fProcessed) {
- Edge* left;
- Edge* right;
- find_enclosing_edges(edge, activeEdges, c, &left, &right);
- insert_edge(edge, left, activeEdges);
- }
-}
-
void insert_edge_above(Edge* edge, Vertex* v, Comparator& c) {
if (edge->fTop->fPoint == edge->fBottom->fPoint ||
c.sweep_lt(edge->fBottom->fPoint, edge->fTop->fPoint)) {
@@ -898,80 +863,137 @@ void disconnect(Edge* edge)
remove_edge_below(edge);
}
-void erase_edge(Edge* edge, EdgeList* edges) {
- LOG("erasing edge (%g -> %g)\n", edge->fTop->fID, edge->fBottom->fID);
- disconnect(edge);
- if (edges && edges->contains(edge)) {
- remove_edge(edge, edges);
+void merge_collinear_edges(Edge* edge, EdgeList* activeEdges, Vertex** current, Comparator& c);
+
+void rewind(EdgeList* activeEdges, Vertex** current, Vertex* dst, Comparator& c) {
+ if (!current || *current == dst || c.sweep_lt((*current)->fPoint, dst->fPoint)) {
+ return;
}
+ Vertex* v = *current;
+ LOG("rewinding active edges from vertex %g to vertex %g\n", v->fID, dst->fID);
+ while (v != dst) {
+ v = v->fPrev;
+ for (Edge* e = v->fFirstEdgeBelow; e; e = e->fNextEdgeBelow) {
+ remove_edge(e, activeEdges);
+ }
+ Edge* leftEdge = v->fLeftEnclosingEdge;
+ for (Edge* e = v->fFirstEdgeAbove; e; e = e->fNextEdgeAbove) {
+ insert_edge(e, leftEdge, activeEdges);
+ leftEdge = e;
+ }
+ }
+ *current = v;
}
-void merge_collinear_edges(Edge* edge, EdgeList* activeEdges, Comparator& c);
+void rewind_if_necessary(Edge* edge, EdgeList* activeEdges, Vertex** current, Comparator& c) {
+ if (!activeEdges || !current) {
+ return;
+ }
+ Vertex* top = edge->fTop;
+ Vertex* bottom = edge->fBottom;
+ if (edge->fLeft) {
+ Vertex* leftTop = edge->fLeft->fTop;
+ Vertex* leftBottom = edge->fLeft->fBottom;
+ if (c.sweep_lt(leftTop->fPoint, top->fPoint) && !edge->fLeft->isLeftOf(top)) {
+ rewind(activeEdges, current, leftTop, c);
+ } else if (c.sweep_lt(top->fPoint, leftTop->fPoint) && !edge->isRightOf(leftTop)) {
+ rewind(activeEdges, current, top, c);
+ } else if (c.sweep_lt(bottom->fPoint, leftBottom->fPoint) &&
+ !edge->fLeft->isLeftOf(bottom)) {
+ rewind(activeEdges, current, leftTop, c);
+ } else if (c.sweep_lt(leftBottom->fPoint, bottom->fPoint) && !edge->isRightOf(leftBottom)) {
+ rewind(activeEdges, current, top, c);
+ }
+ }
+ if (edge->fRight) {
+ Vertex* rightTop = edge->fRight->fTop;
+ Vertex* rightBottom = edge->fRight->fBottom;
+ if (c.sweep_lt(rightTop->fPoint, top->fPoint) && !edge->fRight->isRightOf(top)) {
+ rewind(activeEdges, current, rightTop, c);
+ } else if (c.sweep_lt(top->fPoint, rightTop->fPoint) && !edge->isLeftOf(rightTop)) {
+ rewind(activeEdges, current, top, c);
+ } else if (c.sweep_lt(bottom->fPoint, rightBottom->fPoint) &&
+ !edge->fRight->isRightOf(bottom)) {
+ rewind(activeEdges, current, rightTop, c);
+ } else if (c.sweep_lt(rightBottom->fPoint, bottom->fPoint) &&
+ !edge->isLeftOf(rightBottom)) {
+ rewind(activeEdges, current, top, c);
+ }
+ }
+}
-void set_top(Edge* edge, Vertex* v, EdgeList* activeEdges, Comparator& c) {
+void set_top(Edge* edge, Vertex* v, EdgeList* activeEdges, Vertex** current, Comparator& c) {
remove_edge_below(edge);
edge->fTop = v;
edge->recompute();
insert_edge_below(edge, v, c);
- fix_active_state(edge, activeEdges, c);
- merge_collinear_edges(edge, activeEdges, c);
+ rewind_if_necessary(edge, activeEdges, current, c);
+ merge_collinear_edges(edge, activeEdges, current, c);
}
-void set_bottom(Edge* edge, Vertex* v, EdgeList* activeEdges, Comparator& c) {
+void set_bottom(Edge* edge, Vertex* v, EdgeList* activeEdges, Vertex** current, Comparator& c) {
remove_edge_above(edge);
edge->fBottom = v;
edge->recompute();
insert_edge_above(edge, v, c);
- fix_active_state(edge, activeEdges, c);
- merge_collinear_edges(edge, activeEdges, c);
+ rewind_if_necessary(edge, activeEdges, current, c);
+ merge_collinear_edges(edge, activeEdges, current, c);
}
-void merge_edges_above(Edge* edge, Edge* other, EdgeList* activeEdges, Comparator& c) {
+void merge_edges_above(Edge* edge, Edge* other, EdgeList* activeEdges, Vertex** current,
+ Comparator& c) {
if (coincident(edge->fTop->fPoint, other->fTop->fPoint)) {
LOG("merging coincident above edges (%g, %g) -> (%g, %g)\n",
edge->fTop->fPoint.fX, edge->fTop->fPoint.fY,
edge->fBottom->fPoint.fX, edge->fBottom->fPoint.fY);
+ rewind(activeEdges, current, edge->fTop, c);
other->fWinding += edge->fWinding;
- erase_edge(edge, activeEdges);
+ disconnect(edge);
} else if (c.sweep_lt(edge->fTop->fPoint, other->fTop->fPoint)) {
+ rewind(activeEdges, current, edge->fTop, c);
other->fWinding += edge->fWinding;
- set_bottom(edge, other->fTop, activeEdges, c);
+ set_bottom(edge, other->fTop, activeEdges, current, c);
} else {
+ rewind(activeEdges, current, other->fTop, c);
edge->fWinding += other->fWinding;
- set_bottom(other, edge->fTop, activeEdges, c);
+ set_bottom(other, edge->fTop, activeEdges, current, c);
}
}
-void merge_edges_below(Edge* edge, Edge* other, EdgeList* activeEdges, Comparator& c) {
+void merge_edges_below(Edge* edge, Edge* other, EdgeList* activeEdges, Vertex** current,
+ Comparator& c) {
if (coincident(edge->fBottom->fPoint, other->fBottom->fPoint)) {
LOG("merging coincident below edges (%g, %g) -> (%g, %g)\n",
edge->fTop->fPoint.fX, edge->fTop->fPoint.fY,
edge->fBottom->fPoint.fX, edge->fBottom->fPoint.fY);
+ rewind(activeEdges, current, edge->fTop, c);
other->fWinding += edge->fWinding;
- erase_edge(edge, activeEdges);
+ disconnect(edge);
} else if (c.sweep_lt(edge->fBottom->fPoint, other->fBottom->fPoint)) {
+ rewind(activeEdges, current, other->fTop, c);
edge->fWinding += other->fWinding;
- set_top(other, edge->fBottom, activeEdges, c);
+ set_top(other, edge->fBottom, activeEdges, current, c);
} else {
+ rewind(activeEdges, current, edge->fTop, c);
other->fWinding += edge->fWinding;
- set_top(edge, other->fBottom, activeEdges, c);
+ set_top(edge, other->fBottom, activeEdges, current, c);
}
}
-void merge_collinear_edges(Edge* edge, EdgeList* activeEdges, Comparator& c) {
+void merge_collinear_edges(Edge* edge, EdgeList* activeEdges, Vertex** current, Comparator& c) {
for (;;) {
if (edge->fPrevEdgeAbove && (edge->fTop == edge->fPrevEdgeAbove->fTop ||
!edge->fPrevEdgeAbove->isLeftOf(edge->fTop))) {
- merge_edges_above(edge, edge->fPrevEdgeAbove, activeEdges, c);
+ merge_edges_above(edge, edge->fPrevEdgeAbove, activeEdges, current, c);
} else if (edge->fNextEdgeAbove && (edge->fTop == edge->fNextEdgeAbove->fTop ||
!edge->isLeftOf(edge->fNextEdgeAbove->fTop))) {
- merge_edges_above(edge, edge->fNextEdgeAbove, activeEdges, c);
+ merge_edges_above(edge, edge->fNextEdgeAbove, activeEdges, current, c);
} else if (edge->fPrevEdgeBelow && (edge->fBottom == edge->fPrevEdgeBelow->fBottom ||
!edge->fPrevEdgeBelow->isLeftOf(edge->fBottom))) {
- merge_edges_below(edge, edge->fPrevEdgeBelow, activeEdges, c);
+ merge_edges_below(edge, edge->fPrevEdgeBelow, activeEdges, current, c);
} else if (edge->fNextEdgeBelow && (edge->fBottom == edge->fNextEdgeBelow->fBottom ||
!edge->isLeftOf(edge->fNextEdgeBelow->fBottom))) {
- merge_edges_below(edge, edge->fNextEdgeBelow, activeEdges, c);
+ merge_edges_below(edge, edge->fNextEdgeBelow, activeEdges, current, c);
} else {
break;
}
@@ -982,59 +1004,30 @@ void merge_collinear_edges(Edge* edge, EdgeList* activeEdges, Comparator& c) {
SkASSERT(!edge->fNextEdgeBelow || edge->fNextEdgeBelow->isRightOf(edge->fBottom));
}
-void split_edge(Edge* edge, Vertex* v, EdgeList* activeEdges, Comparator& c, SkArenaAlloc& alloc);
-
-void cleanup_active_edges(Edge* edge, EdgeList* activeEdges, Comparator& c, SkArenaAlloc& alloc) {
- Vertex* top = edge->fTop;
- Vertex* bottom = edge->fBottom;
- if (edge->fLeft) {
- Vertex* leftTop = edge->fLeft->fTop;
- Vertex* leftBottom = edge->fLeft->fBottom;
- if (c.sweep_lt(leftTop->fPoint, top->fPoint) && !edge->fLeft->isLeftOf(top)) {
- split_edge(edge->fLeft, edge->fTop, activeEdges, c, alloc);
- } else if (c.sweep_lt(top->fPoint, leftTop->fPoint) && !edge->isRightOf(leftTop)) {
- split_edge(edge, leftTop, activeEdges, c, alloc);
- } else if (c.sweep_lt(bottom->fPoint, leftBottom->fPoint) &&
- !edge->fLeft->isLeftOf(bottom)) {
- split_edge(edge->fLeft, bottom, activeEdges, c, alloc);
- } else if (c.sweep_lt(leftBottom->fPoint, bottom->fPoint) && !edge->isRightOf(leftBottom)) {
- split_edge(edge, leftBottom, activeEdges, c, alloc);
- }
- }
- if (edge->fRight) {
- Vertex* rightTop = edge->fRight->fTop;
- Vertex* rightBottom = edge->fRight->fBottom;
- if (c.sweep_lt(rightTop->fPoint, top->fPoint) && !edge->fRight->isRightOf(top)) {
- split_edge(edge->fRight, top, activeEdges, c, alloc);
- } else if (c.sweep_lt(top->fPoint, rightTop->fPoint) && !edge->isLeftOf(rightTop)) {
- split_edge(edge, rightTop, activeEdges, c, alloc);
- } else if (c.sweep_lt(bottom->fPoint, rightBottom->fPoint) &&
- !edge->fRight->isRightOf(bottom)) {
- split_edge(edge->fRight, bottom, activeEdges, c, alloc);
- } else if (c.sweep_lt(rightBottom->fPoint, bottom->fPoint) &&
- !edge->isLeftOf(rightBottom)) {
- split_edge(edge, rightBottom, activeEdges, c, alloc);
- }
- }
-}
-
-void split_edge(Edge* edge, Vertex* v, EdgeList* activeEdges, Comparator& c, SkArenaAlloc& alloc) {
+void split_edge(Edge* edge, Vertex* v, EdgeList* activeEdges, Vertex** current, Comparator& c,
+ SkArenaAlloc& alloc) {
LOG("splitting edge (%g -> %g) at vertex %g (%g, %g)\n",
edge->fTop->fID, edge->fBottom->fID,
v->fID, v->fPoint.fX, v->fPoint.fY);
+ Vertex* top;
+ Vertex* bottom;
if (c.sweep_lt(v->fPoint, edge->fTop->fPoint)) {
- set_top(edge, v, activeEdges, c);
+ top = v;
+ bottom = edge->fTop;
+ set_top(edge, v, activeEdges, current, c);
} else if (c.sweep_lt(edge->fBottom->fPoint, v->fPoint)) {
- set_bottom(edge, v, activeEdges, c);
+ top = edge->fBottom;
+ bottom = v;
+ set_bottom(edge, v, activeEdges, current, c);
} else {
- Edge* newEdge = alloc.make<Edge>(v, edge->fBottom, edge->fWinding, edge->fType);
- insert_edge_below(newEdge, v, c);
- insert_edge_above(newEdge, edge->fBottom, c);
- set_bottom(edge, v, activeEdges, c);
- cleanup_active_edges(edge, activeEdges, c, alloc);
- fix_active_state(newEdge, activeEdges, c);
- merge_collinear_edges(newEdge, activeEdges, c);
+ top = v;
+ bottom = edge->fBottom;
+ set_bottom(edge, v, activeEdges, current, c);
}
+ Edge* newEdge = alloc.make<Edge>(top, bottom, edge->fWinding, edge->fType);
+ insert_edge_below(newEdge, top, c);
+ insert_edge_above(newEdge, bottom, c);
+ merge_collinear_edges(newEdge, activeEdges, current, c);
}
Edge* connect(Vertex* prev, Vertex* next, Edge::Type type, Comparator& c, SkArenaAlloc& alloc,
@@ -1043,7 +1036,7 @@ Edge* connect(Vertex* prev, Vertex* next, Edge::Type type, Comparator& c, SkAren
insert_edge_below(edge, edge->fTop, c);
insert_edge_above(edge, edge->fBottom, c);
edge->fWinding *= winding_scale;
- merge_collinear_edges(edge, nullptr, c);
+ merge_collinear_edges(edge, nullptr, nullptr, c);
return edge;
}
@@ -1057,12 +1050,12 @@ void merge_vertices(Vertex* src, Vertex* dst, VertexList* mesh, Comparator& c,
}
for (Edge* edge = src->fFirstEdgeAbove; edge;) {
Edge* next = edge->fNextEdgeAbove;
- set_bottom(edge, dst, nullptr, c);
+ set_bottom(edge, dst, nullptr, nullptr, c);
edge = next;
}
for (Edge* edge = src->fFirstEdgeBelow; edge;) {
Edge* next = edge->fNextEdgeBelow;
- set_top(edge, dst, nullptr, c);
+ set_top(edge, dst, nullptr, nullptr, c);
edge = next;
}
mesh->remove(src);
@@ -1079,61 +1072,69 @@ uint8_t max_edge_alpha(Edge* a, Edge* b) {
}
}
-Vertex* check_for_intersection(Edge* edge, Edge* other, EdgeList* activeEdges, Comparator& c,
- SkArenaAlloc& alloc) {
+bool check_for_intersection(Edge* edge, Edge* other, EdgeList* activeEdges, Vertex** current,
+ Comparator& c, SkArenaAlloc& alloc) {
if (!edge || !other) {
- return nullptr;
+ return false;
}
SkPoint p;
uint8_t alpha;
if (edge->intersect(*other, &p, &alpha)) {
Vertex* v;
LOG("found intersection, pt is %g, %g\n", p.fX, p.fY);
- if (p == edge->fTop->fPoint || c.sweep_lt(p, edge->fTop->fPoint)) {
- split_edge(other, edge->fTop, activeEdges, c, alloc);
+ Vertex* top = *current;
+ // If the intersection point is above the current vertex, rewind to the vertex above the
+ // intersection.
+ while (c.sweep_lt(p, top->fPoint) && top->fPrev) {
+ top = top->fPrev;
+ }
+ rewind(activeEdges, current, top, c);
+ if (p == edge->fTop->fPoint) {
+ split_edge(other, edge->fTop, activeEdges, current, c, alloc);
v = edge->fTop;
- } else if (p == edge->fBottom->fPoint || c.sweep_lt(edge->fBottom->fPoint, p)) {
- split_edge(other, edge->fBottom, activeEdges, c, alloc);
+ } else if (p == edge->fBottom->fPoint) {
+ split_edge(other, edge->fBottom, activeEdges, current, c, alloc);
v = edge->fBottom;
- } else if (p == other->fTop->fPoint || c.sweep_lt(p, other->fTop->fPoint)) {
- split_edge(edge, other->fTop, activeEdges, c, alloc);
+ } else if (p == other->fTop->fPoint) {
+ split_edge(edge, other->fTop, activeEdges, current, c, alloc);
v = other->fTop;
- } else if (p == other->fBottom->fPoint || c.sweep_lt(other->fBottom->fPoint, p)) {
- split_edge(edge, other->fBottom, activeEdges, c, alloc);
+ } else if (p == other->fBottom->fPoint) {
+ split_edge(edge, other->fBottom, activeEdges, current, c, alloc);
v = other->fBottom;
} else {
- Vertex* nextV = edge->fTop;
- while (c.sweep_lt(p, nextV->fPoint)) {
- nextV = nextV->fPrev;
- }
- while (c.sweep_lt(nextV->fPoint, p)) {
+ Vertex* prevV = top;
+ Vertex* nextV = top->fNext;
+ while (nextV && c.sweep_lt(nextV->fPoint, p)) {
+ prevV = nextV;
nextV = nextV->fNext;
}
- Vertex* prevV = nextV->fPrev;
- if (coincident(prevV->fPoint, p)) {
+ if (prevV && coincident(prevV->fPoint, p)) {
v = prevV;
- } else if (coincident(nextV->fPoint, p)) {
+ } else if (nextV && coincident(nextV->fPoint, p)) {
v = nextV;
} else {
v = alloc.make<Vertex>(p, alpha);
- LOG("inserting between %g (%g, %g) and %g (%g, %g)\n",
- prevV->fID, prevV->fPoint.fX, prevV->fPoint.fY,
- nextV->fID, nextV->fPoint.fX, nextV->fPoint.fY);
#if LOGGING_ENABLED
- v->fID = (nextV->fID + prevV->fID) * 0.5f;
+ float prevID = prevV ? prevV->fID : 0.0f;
+ float nextID = nextV ? nextV->fID : prevV->fID + 1.0f;
+ v->fID = (prevID + nextID) * 0.5f;
#endif
v->fPrev = prevV;
v->fNext = nextV;
- prevV->fNext = v;
- nextV->fPrev = v;
+ if (prevV) {
+ prevV->fNext = v;
+ }
+ if (nextV) {
+ nextV->fPrev = v;
+ }
}
- split_edge(edge, v, activeEdges, c, alloc);
- split_edge(other, v, activeEdges, c, alloc);
+ split_edge(edge, v, activeEdges, current, c, alloc);
+ split_edge(other, v, activeEdges, current, c, alloc);
}
v->fAlpha = SkTMax(v->fAlpha, alpha);
- return v;
+ return true;
}
- return nullptr;
+ return false;
}
void sanitize_contours(VertexList* contours, int contourCnt, bool approximate) {
@@ -1224,6 +1225,12 @@ void sorted_merge(VertexList* front, VertexList* back, VertexList* result, Compa
} else {
sorted_merge<sweep_lt_vert>(front, back, result);
}
+#if LOGGING_ENABLED
+ float id = 0.0f;
+ for (Vertex* v = result->fHead; v; v = v->fNext) {
+ v->fID = id++;
+ }
+#endif
}
// Stage 3: sort the vertices by increasing sweep direction.
@@ -1265,37 +1272,37 @@ void simplify(const VertexList& vertices, Comparator& c, SkArenaAlloc& alloc) {
if (!v->fFirstEdgeAbove && !v->fFirstEdgeBelow) {
continue;
}
-#if LOGGING_ENABLED
- LOG("\nvertex %g: (%g,%g), alpha %d\n", v->fID, v->fPoint.fX, v->fPoint.fY, v->fAlpha);
-#endif
Edge* leftEnclosingEdge;
Edge* rightEnclosingEdge;
bool restartChecks;
do {
+ LOG("\nvertex %g: (%g,%g), alpha %d\n", v->fID, v->fPoint.fX, v->fPoint.fY, v->fAlpha);
restartChecks = false;
find_enclosing_edges(v, &activeEdges, &leftEnclosingEdge, &rightEnclosingEdge);
if (rightEnclosingEdge && !rightEnclosingEdge->isRightOf(v)) {
- split_edge(rightEnclosingEdge, v, &activeEdges, c, alloc);
+ split_edge(rightEnclosingEdge, v, &activeEdges, &v, c, alloc);
restartChecks = true;
continue;
}
+ SkASSERT(!rightEnclosingEdge || rightEnclosingEdge->isRightOf(v));
+ v->fLeftEnclosingEdge = leftEnclosingEdge;
+ v->fRightEnclosingEdge = rightEnclosingEdge;
if (v->fFirstEdgeBelow) {
for (Edge* edge = v->fFirstEdgeBelow; edge; edge = edge->fNextEdgeBelow) {
- if (check_for_intersection(edge, leftEnclosingEdge, &activeEdges, c, alloc)) {
+ if (check_for_intersection(edge, leftEnclosingEdge, &activeEdges, &v, c,
+ alloc)) {
restartChecks = true;
break;
}
- if (check_for_intersection(edge, rightEnclosingEdge, &activeEdges, c, alloc)) {
+ if (check_for_intersection(edge, rightEnclosingEdge, &activeEdges, &v, c,
+ alloc)) {
restartChecks = true;
break;
}
}
} else {
- if (Vertex* pv = check_for_intersection(leftEnclosingEdge, rightEnclosingEdge,
- &activeEdges, c, alloc)) {
- if (c.sweep_lt(pv->fPoint, v->fPoint)) {
- v = pv;
- }
+ if (check_for_intersection(leftEnclosingEdge, rightEnclosingEdge,
+ &activeEdges, &v, c, alloc)) {
restartChecks = true;
}
@@ -1315,7 +1322,6 @@ void simplify(const VertexList& vertices, Comparator& c, SkArenaAlloc& alloc) {
insert_edge(e, leftEdge, &activeEdges);
leftEdge = e;
}
- v->fProcessed = true;
}
}
generated by cgit v1.2.3 (git 2.39.1) at 2024-06-10 20:29:50 +0000