Add internal tree implementation to EdgeList.
Makes some of the intersection and comparison calculations more
robust and faster as well.
Bug: skia:
Change-Id: Ic6b6599be185d4fd888899ecd02ba0df7bc33e18
Reviewed-on: https://skia-review.googlesource.com/146383
Commit-Queue: Jim Van Verth <jvanverth@google.com>
Reviewed-by: Robert Phillips <robertphillips@google.com>
diff --git a/src/utils/SkPolyUtils.cpp b/src/utils/SkPolyUtils.cpp
index a23942c..8d378f5 100644
--- a/src/utils/SkPolyUtils.cpp
+++ b/src/utils/SkPolyUtils.cpp
@@ -7,7 +7,6 @@
#include "SkPolyUtils.h"
-#include <set>
#include "SkPointPriv.h"
#include "SkTArray.h"
#include "SkTemplates.h"
@@ -526,16 +525,14 @@
///////////////////////////////////////////////////////////////////////////////////////////
-// a point is "left" to another if its x coordinate is less, or if equal, its y coordinate
+// a point is "left" to another if its x-coord is less, or if equal, its y-coord is greater
static bool left(const SkPoint& p0, const SkPoint& p1) {
- return p0.fX < p1.fX || (!(p0.fX > p1.fX) && p0.fY < p1.fY);
+ return p0.fX < p1.fX || (!(p0.fX > p1.fX) && p0.fY > p1.fY);
}
-// checks to see if a point that is collinear with a segment lies in the segment's range
-static bool in_segment(const SkPoint& p0, const SkVector& v, const SkPoint& p) {
- SkVector w = p - p0;
- SkScalar numer = w.dot(v);
- return (numer >= 0 && numer <= v.dot(v));
+// a point is "right" to another if its x-coord is greater, or if equal, its y-coord is less
+static bool right(const SkPoint& p0, const SkPoint& p1) {
+ return p0.fX > p1.fX || (!(p0.fX < p1.fX) && p0.fY < p1.fY);
}
struct Vertex {
@@ -557,39 +554,50 @@
};
struct ActiveEdge {
- ActiveEdge(const SkPoint& p0, const SkPoint& p1, uint16_t index0, uint16_t index1)
- : fSegment({p0, p1-p0})
+ ActiveEdge() : fChild{ nullptr, nullptr }, fAbove(nullptr), fBelow(nullptr), fRed(false) {}
+ ActiveEdge(const SkPoint& p0, const SkVector& v, uint16_t index0, uint16_t index1)
+ : fSegment({ p0, v })
, fIndex0(index0)
- , fIndex1(index1) {}
+ , fIndex1(index1)
+ , fAbove(nullptr)
+ , fBelow(nullptr)
+ , fRed(true) {
+ fChild[0] = nullptr;
+ fChild[1] = nullptr;
+ }
- // returns true if "this" is above "that"
- bool above(const ActiveEdge& that) const {
- SkASSERT(this->fSegment.fP0.fX <= that.fSegment.fP0.fX);
- const SkVector& u = this->fSegment.fV;
- SkVector dv = that.fSegment.fP0 - this->fSegment.fP0;
- // The idea here is that if the vector between the origins of the two segments (dv)
- // rotates counterclockwise up to the vector representing the "this" segment (u),
- // then we know that "this" is above that. If the result is clockwise we say it's below.
- if (this->fIndex0 != that.fIndex0) {
- SkScalar cross = dv.cross(u);
+ // Returns true if "this" is above "that", assuming this->p0 is to the left of that->p0
+ // This is only used to verify the edgelist -- the actual test for insertion/deletion is much
+ // simpler because we can make certain assumptions then.
+ bool aboveIfLeft(const ActiveEdge* that) const {
+ const SkPoint& p0 = this->fSegment.fP0;
+ const SkPoint& q0 = that->fSegment.fP0;
+ SkASSERT(p0.fX <= q0.fX);
+ SkVector d = q0 - p0;
+ const SkVector& v = this->fSegment.fV;
+ const SkVector& w = that->fSegment.fV;
+ // The idea here is that if the vector between the origins of the two segments (d)
+ // rotates counterclockwise up to the vector representing the "this" segment (v),
+ // then we know that "this" is above "that". If the result is clockwise we say it's below.
+ if (this->fIndex0 != that->fIndex0) {
+ SkScalar cross = d.cross(v);
if (cross > kCrossTolerance) {
return true;
} else if (cross < -kCrossTolerance) {
return false;
}
- } else if (this->fIndex1 == that.fIndex1) {
- // they're the same edge
+ } else if (this->fIndex1 == that->fIndex1) {
return false;
}
// At this point either the two origins are nearly equal or the origin of "that"
// lies on dv. So then we try the same for the vector from the tail of "this"
// to the head of "that". Again, ccw means "this" is above "that".
- // dv = that.P1 - this.P0
- // = that.fP0 + that.fV - this.fP0
- // = that.fP0 - this.fP0 + that.fV
- // = old_dv + that.fV
- dv += that.fSegment.fV;
- SkScalar cross = dv.cross(u);
+ // d = that.P1 - this.P0
+ // = that.fP0 + that.fV - this.fP0
+ // = that.fP0 - this.fP0 + that.fV
+ // = old_d + that.fV
+ d += w;
+ SkScalar cross = d.cross(v);
if (cross > kCrossTolerance) {
return true;
} else if (cross < -kCrossTolerance) {
@@ -597,27 +605,38 @@
}
// If the previous check fails, the two segments are nearly collinear
// First check y-coord of first endpoints
- if (this->fSegment.fP0.fX < that.fSegment.fP0.fX) {
- return (this->fSegment.fP0.fY >= that.fSegment.fP0.fY);
- } else if (this->fSegment.fP0.fY > that.fSegment.fP0.fY) {
+ if (p0.fX < q0.fX) {
+ return (p0.fY >= q0.fY);
+ } else if (p0.fY > q0.fY) {
return true;
- } else if (this->fSegment.fP0.fY < that.fSegment.fP0.fY) {
+ } else if (p0.fY < q0.fY) {
return false;
}
// The first endpoints are the same, so check the other endpoint
- SkPoint thisP1 = this->fSegment.fP0 + this->fSegment.fV;
- SkPoint thatP1 = that.fSegment.fP0 + that.fSegment.fV;
- if (thisP1.fX < thatP1.fX) {
- return (thisP1.fY >= thatP1.fY);
+ SkPoint p1 = p0 + v;
+ SkPoint q1 = q0 + w;
+ if (p1.fX < q1.fX) {
+ return (p1.fY >= q1.fY);
} else {
- return (thisP1.fY > thatP1.fY);
+ return (p1.fY > q1.fY);
}
}
- bool intersect(const ActiveEdge& that) const {
+ // same as leftAndAbove(), but generalized
+ bool above(const ActiveEdge* that) const {
+ const SkPoint& p0 = this->fSegment.fP0;
+ const SkPoint& q0 = that->fSegment.fP0;
+ if (right(p0, q0)) {
+ return !that->aboveIfLeft(this);
+ } else {
+ return this->aboveIfLeft(that);
+ }
+ }
+
+ bool intersect(const SkPoint& q0, const SkVector& w, uint16_t index0, uint16_t index1) const {
// check first to see if these edges are neighbors in the polygon
- if (this->fIndex0 == that.fIndex0 || this->fIndex1 == that.fIndex0 ||
- this->fIndex0 == that.fIndex1 || this->fIndex1 == that.fIndex1) {
+ if (this->fIndex0 == index0 || this->fIndex1 == index0 ||
+ this->fIndex0 == index1 || this->fIndex1 == index1) {
return false;
}
@@ -625,104 +644,434 @@
const SkPoint& p0 = this->fSegment.fP0;
const SkVector& v = this->fSegment.fV;
SkPoint p1 = p0 + v;
- const SkPoint& q0 = that.fSegment.fP0;
- const SkVector& w = that.fSegment.fV;
SkPoint q1 = q0 + w;
- int side0 = compute_side(p0, v, q0);
- int side1 = compute_side(p0, v, q1);
- int side2 = compute_side(q0, w, p0);
- int side3 = compute_side(q0, w, p1);
+ // We assume some x-overlap due to how the edgelist works
+ // This allows us to simplify our test
+ // We need some slop here because storing the vector and recomputing the second endpoint
+ // doesn't necessary give us the original result in floating point.
+ // TODO: Store vector as double? Store endpoint as well?
+ SkASSERT(q0.fX <= p1.fX + SK_ScalarNearlyZero);
// if each segment straddles the other (i.e., the endpoints have different sides)
// then they intersect
- if (side0*side1 < 0 && side2*side3 < 0) {
- return true;
+ bool result;
+ if (p0.fX < q0.fX) {
+ if (q1.fX < p1.fX) {
+ result = (compute_side(p0, v, q0)*compute_side(p0, v, q1) < 0);
+ } else {
+ result = (compute_side(p0, v, q0)*compute_side(q0, w, p1) > 0);
+ }
+ } else {
+ if (p1.fX < q1.fX) {
+ result = (compute_side(q0, w, p0)*compute_side(q0, w, p1) < 0);
+ } else {
+ result = (compute_side(q0, w, p0)*compute_side(p0, v, q1) > 0);
+ }
}
-
- // check collinear cases
- // q0 lies on segment0's line, see if it's inside the segment
- if (side0 == 0 && in_segment(p0, v, q0)) {
- return true;
- }
- // q0 + w lies on segment0's line, see if it's inside the segment
- if (side1 == 0 && in_segment(p0, v, q1)) {
- return true;
- }
- // p0 lies on segment1's line, see if it's inside the segment
- if (side2 == 0 && in_segment(q0, w, p0)) {
- return true;
- }
- // p0 + v lies on segment0's line, see if it's inside the segment
- if (side3 == 0 && in_segment(q0, w, p1)) {
- return true;
- }
-
- return false;
+ return result;
}
- bool lessThan(const ActiveEdge& that) const {
- if (this->fSegment.fP0.fX > that.fSegment.fP0.fX ||
- (this->fSegment.fP0.fX == that.fSegment.fP0.fX &&
- this->fSegment.fP0.fY < that.fSegment.fP0.fY)) {
- return !that.above(*this);
- }
+ bool intersect(const ActiveEdge* edge) {
+ return this->intersect(edge->fSegment.fP0, edge->fSegment.fV, edge->fIndex0, edge->fIndex1);
+ }
+
+ bool lessThan(const ActiveEdge* that) const {
+ SkASSERT(!this->above(this));
+ SkASSERT(!that->above(that));
+ SkASSERT(!(this->above(that) && that->above(this)));
return this->above(that);
}
- bool operator<(const ActiveEdge& that) const {
- SkASSERT(!this->lessThan(*this));
- SkASSERT(!that.lessThan(that));
- SkASSERT(!(this->lessThan(that) && that.lessThan(*this)));
- return this->lessThan(that);
+ bool equals(uint16_t index0, uint16_t index1) const {
+ return (this->fIndex0 == index0 && this->fIndex1 == index1);
}
OffsetSegment fSegment;
- uint16_t fIndex0; // indices for previous and next vertex
+ uint16_t fIndex0; // indices for previous and next vertex in polygon
uint16_t fIndex1;
+ ActiveEdge* fChild[2];
+ ActiveEdge* fAbove;
+ ActiveEdge* fBelow;
+ int32_t fRed;
};
class ActiveEdgeList {
public:
+ ActiveEdgeList(int maxEdges) {
+ fAllocation = (char*) sk_malloc_throw(sizeof(ActiveEdge)*maxEdges);
+ fCurrFree = 0;
+ fMaxFree = maxEdges;
+ }
+ ~ActiveEdgeList() {
+ fTreeHead.fChild[1] = nullptr;
+ sk_free(fAllocation);
+ }
+
bool insert(const SkPoint& p0, const SkPoint& p1, uint16_t index0, uint16_t index1) {
- std::pair<Iterator, bool> result = fEdgeTree.emplace(p0, p1, index0, index1);
- if (!result.second) {
- return false;
+ SkVector v = p1 - p0;
+ // empty tree case -- easy
+ if (!fTreeHead.fChild[1]) {
+ ActiveEdge* root = fTreeHead.fChild[1] = this->allocate(p0, v, index0, index1);
+ SkASSERT(root);
+ if (!root) {
+ return false;
+ }
+ root->fRed = false;
+ return true;
}
- Iterator& curr = result.first;
- if (curr != fEdgeTree.begin() && curr->intersect(*std::prev(curr))) {
- return false;
+ // set up helpers
+ ActiveEdge* top = &fTreeHead;
+ ActiveEdge *grandparent = nullptr;
+ ActiveEdge *parent = nullptr;
+ ActiveEdge *curr = top->fChild[1];
+ int dir = 0;
+ int last = 0; // ?
+ // predecessor and successor, for intersection check
+ ActiveEdge* pred = nullptr;
+ ActiveEdge* succ = nullptr;
+
+ // search down the tree
+ while (true) {
+ if (!curr) {
+ // check for intersection with predecessor and successor
+ if ((pred && pred->intersect(p0, v, index0, index1)) ||
+ (succ && succ->intersect(p0, v, index0, index1))) {
+ return false;
+ }
+ // insert new node at bottom
+ parent->fChild[dir] = curr = this->allocate(p0, v, index0, index1);
+ SkASSERT(curr);
+ if (!curr) {
+ return false;
+ }
+ curr->fAbove = pred;
+ curr->fBelow = succ;
+ if (pred) {
+ pred->fBelow = curr;
+ }
+ if (succ) {
+ succ->fAbove = curr;
+ }
+ if (IsRed(parent)) {
+ int dir2 = (top->fChild[1] == grandparent);
+ if (curr == parent->fChild[last]) {
+ top->fChild[dir2] = SingleRotation(grandparent, !last);
+ } else {
+ top->fChild[dir2] = DoubleRotation(grandparent, !last);
+ }
+ }
+ break;
+ } else if (IsRed(curr->fChild[0]) && IsRed(curr->fChild[1])) {
+ // color flip
+ curr->fRed = true;
+ curr->fChild[0]->fRed = false;
+ curr->fChild[1]->fRed = false;
+ if (IsRed(parent)) {
+ int dir2 = (top->fChild[1] == grandparent);
+ if (curr == parent->fChild[last]) {
+ top->fChild[dir2] = SingleRotation(grandparent, !last);
+ } else {
+ top->fChild[dir2] = DoubleRotation(grandparent, !last);
+ }
+ }
+ }
+
+ last = dir;
+ int side;
+ // check to see if segment is above or below
+ if (curr->fIndex0 == index0) {
+ side = compute_side(curr->fSegment.fP0, curr->fSegment.fV, p1);
+ } else {
+ side = compute_side(curr->fSegment.fP0, curr->fSegment.fV, p0);
+ }
+ if (0 == side) {
+ return false;
+ }
+ dir = (side < 0);
+
+ if (0 == dir) {
+ succ = curr;
+ } else {
+ pred = curr;
+ }
+
+ // update helpers
+ if (grandparent) {
+ top = grandparent;
+ }
+ grandparent = parent;
+ parent = curr;
+ curr = curr->fChild[dir];
}
- Iterator next = std::next(curr);
- if (next != fEdgeTree.end() && curr->intersect(*next)) {
- return false;
- }
+
+ // update root and make it black
+ fTreeHead.fChild[1]->fRed = false;
+
+ SkDEBUGCODE(VerifyTree(fTreeHead.fChild[1]));
return true;
}
- bool remove(const ActiveEdge& edge) {
- auto element = fEdgeTree.find(edge);
- // this better not happen
- if (element == fEdgeTree.end()) {
- return false;
- }
- if (element != fEdgeTree.begin() && element->intersect(*std::prev(element))) {
- return false;
- }
- Iterator next = std::next(element);
- if (next != fEdgeTree.end() && element->intersect(*next)) {
+ // replaces edge p0p1 with p1p2
+ bool replace(const SkPoint& p0, const SkPoint& p1, const SkPoint& p2,
+ uint16_t index0, uint16_t index1, uint16_t index2) {
+ if (!fTreeHead.fChild[1]) {
return false;
}
- fEdgeTree.erase(element);
+ SkVector v = p2 - p1;
+ ActiveEdge* curr = &fTreeHead;
+ ActiveEdge* found = nullptr;
+ int dir = 1;
+
+ // search
+ while (curr->fChild[dir] != nullptr) {
+ // update helpers
+ curr = curr->fChild[dir];
+ // save found node
+ if (curr->equals(index0, index1)) {
+ found = curr;
+ break;
+ } else {
+ // check to see if segment is above or below
+ int side;
+ if (curr->fIndex1 == index1) {
+ side = compute_side(curr->fSegment.fP0, curr->fSegment.fV, p0);
+ } else {
+ side = compute_side(curr->fSegment.fP0, curr->fSegment.fV, p1);
+ }
+ if (0 == side) {
+ return false;
+ }
+ dir = (side < 0);
+ }
+ }
+
+ if (!found) {
+ return false;
+ }
+
+ // replace if found
+ ActiveEdge* pred = found->fAbove;
+ ActiveEdge* succ = found->fBelow;
+ // check deletion and insert intersection cases
+ if (pred && (pred->intersect(found) || pred->intersect(p1, v, index1, index2))) {
+ return false;
+ }
+ if (succ && (succ->intersect(found) || succ->intersect(p1, v, index1, index2))) {
+ return false;
+ }
+ found->fSegment.fP0 = p1;
+ found->fSegment.fV = v;
+ found->fIndex0 = index1;
+ found->fIndex1 = index2;
+ // above and below should stay the same
+
+ SkDEBUGCODE(VerifyTree(fTreeHead.fChild[1]));
+
+ return true;
+ }
+
+ bool remove(const SkPoint& p0, const SkPoint& p1, uint16_t index0, uint16_t index1) {
+ if (!fTreeHead.fChild[1]) {
+ return false;
+ }
+
+ ActiveEdge* curr = &fTreeHead;
+ ActiveEdge* parent = nullptr;
+ ActiveEdge* grandparent = nullptr;
+ ActiveEdge* found = nullptr;
+ int dir = 1;
+
+ // search and push a red node down
+ while (curr->fChild[dir] != nullptr) {
+ int last = dir;
+
+ // update helpers
+ grandparent = parent;
+ parent = curr;
+ curr = curr->fChild[dir];
+ // save found node
+ if (curr->equals(index0, index1)) {
+ found = curr;
+ dir = 0;
+ } else {
+ // check to see if segment is above or below
+ int side;
+ if (curr->fIndex1 == index1) {
+ side = compute_side(curr->fSegment.fP0, curr->fSegment.fV, p0);
+ } else {
+ side = compute_side(curr->fSegment.fP0, curr->fSegment.fV, p1);
+ }
+ if (0 == side) {
+ return false;
+ }
+ dir = (side < 0);
+ }
+
+ // push the red node down
+ if (!IsRed(curr) && !IsRed(curr->fChild[dir])) {
+ if (IsRed(curr->fChild[!dir])) {
+ parent = parent->fChild[last] = SingleRotation(curr, dir);
+ } else {
+ ActiveEdge *s = parent->fChild[!last];
+
+ if (s != NULL) {
+ if (!IsRed(s->fChild[!last]) && !IsRed(s->fChild[last])) {
+ // color flip
+ parent->fRed = false;
+ s->fRed = true;
+ curr->fRed = true;
+ } else {
+ int dir2 = (grandparent->fChild[1] == parent);
+
+ if (IsRed(s->fChild[last])) {
+ grandparent->fChild[dir2] = DoubleRotation(parent, last);
+ } else if (IsRed(s->fChild[!last])) {
+ grandparent->fChild[dir2] = SingleRotation(parent, last);
+ }
+
+ // ensure correct coloring
+ curr->fRed = grandparent->fChild[dir2]->fRed = true;
+ grandparent->fChild[dir2]->fChild[0]->fRed = false;
+ grandparent->fChild[dir2]->fChild[1]->fRed = false;
+ }
+ }
+ }
+ }
+ }
+
+ // replace and remove if found
+ if (found) {
+ ActiveEdge* pred = found->fAbove;
+ ActiveEdge* succ = found->fBelow;
+ if ((pred && pred->intersect(found)) || (succ && succ->intersect(found))) {
+ return false;
+ }
+ if (found != curr) {
+ found->fSegment = curr->fSegment;
+ found->fIndex0 = curr->fIndex0;
+ found->fIndex1 = curr->fIndex1;
+ found->fAbove = curr->fAbove;
+ pred = found->fAbove;
+ // we don't need to set found->fBelow here
+ } else {
+ if (succ) {
+ succ->fAbove = pred;
+ }
+ }
+ if (pred) {
+ pred->fBelow = curr->fBelow;
+ }
+ parent->fChild[parent->fChild[1] == curr] = curr->fChild[!curr->fChild[0]];
+
+ // no need to delete
+ curr->fAbove = reinterpret_cast<ActiveEdge*>(0xdeadbeefll);
+ curr->fBelow = reinterpret_cast<ActiveEdge*>(0xdeadbeefll);
+ if (fTreeHead.fChild[1]) {
+ fTreeHead.fChild[1]->fRed = false;
+ }
+ }
+
+ // update root and make it black
+ if (fTreeHead.fChild[1]) {
+ fTreeHead.fChild[1]->fRed = false;
+ }
+
+ SkDEBUGCODE(VerifyTree(fTreeHead.fChild[1]));
+
return true;
}
private:
- std::set<ActiveEdge> fEdgeTree;
- typedef std::set<ActiveEdge>::iterator Iterator;
+ // allocator
+ ActiveEdge * allocate(const SkPoint& p0, const SkPoint& p1, uint16_t index0, uint16_t index1) {
+ if (fCurrFree >= fMaxFree) {
+ return nullptr;
+ }
+ char* bytes = fAllocation + sizeof(ActiveEdge)*fCurrFree;
+ ++fCurrFree;
+ return new(bytes) ActiveEdge(p0, p1, index0, index1);
+ }
+
+ ///////////////////////////////////////////////////////////////////////////////////
+ // Red-black tree methods
+ ///////////////////////////////////////////////////////////////////////////////////
+ static bool IsRed(const ActiveEdge* node) {
+ return node && node->fRed;
+ }
+
+ static ActiveEdge* SingleRotation(ActiveEdge* node, int dir) {
+ ActiveEdge* tmp = node->fChild[!dir];
+
+ node->fChild[!dir] = tmp->fChild[dir];
+ tmp->fChild[dir] = node;
+
+ node->fRed = true;
+ tmp->fRed = false;
+
+ return tmp;
+ }
+
+ static ActiveEdge* DoubleRotation(ActiveEdge* node, int dir) {
+ node->fChild[!dir] = SingleRotation(node->fChild[!dir], !dir);
+
+ return SingleRotation(node, dir);
+ }
+
+ // returns black link count
+ static int VerifyTree(const ActiveEdge* tree) {
+ if (!tree) {
+ return 1;
+ }
+
+ const ActiveEdge* left = tree->fChild[0];
+ const ActiveEdge* right = tree->fChild[1];
+
+ // no consecutive red links
+ if (IsRed(tree) && (IsRed(left) || IsRed(right))) {
+ SkASSERT(false);
+ return 0;
+ }
+
+ // check secondary links
+ if (tree->fAbove) {
+ SkASSERT(tree->fAbove->fBelow == tree);
+ SkASSERT(tree->fAbove->lessThan(tree));
+ }
+ if (tree->fBelow) {
+ SkASSERT(tree->fBelow->fAbove == tree);
+ SkASSERT(tree->lessThan(tree->fBelow));
+ }
+
+ // violates binary tree order
+ if ((left && tree->lessThan(left)) || (right && right->lessThan(tree))) {
+ SkASSERT(false);
+ return 0;
+ }
+
+ int leftCount = VerifyTree(left);
+ int rightCount = VerifyTree(right);
+
+ // return black link count
+ if (leftCount != 0 && rightCount != 0) {
+ // black height mismatch
+ if (leftCount != rightCount) {
+ SkASSERT(false);
+ return 0;
+ }
+ return IsRed(tree) ? leftCount : leftCount + 1;
+ } else {
+ return 0;
+ }
+ }
+
+ ActiveEdge fTreeHead;
+ char* fAllocation;
+ int fCurrFree;
+ int fMaxFree;
};
// Here we implement a sweep line algorithm to determine whether the provided points
@@ -741,6 +1090,11 @@
return false;
}
+ // If it's convex, it's simple
+ if (SkIsConvexPolygon(polygon, polygonSize)) {
+ return true;
+ }
+
SkTDPQueue <Vertex, Vertex::Left> vertexQueue(polygonSize);
for (int i = 0; i < polygonSize; ++i) {
Vertex newVertex;
@@ -763,32 +1117,40 @@
// pop each vertex from the queue and generate events depending on
// where it lies relative to its neighboring edges
- ActiveEdgeList sweepLine;
+ ActiveEdgeList sweepLine(polygonSize);
while (vertexQueue.count() > 0) {
const Vertex& v = vertexQueue.peek();
- // check edge to previous vertex
- if (v.fFlags & kPrevLeft_VertexFlag) {
- ActiveEdge edge(polygon[v.fPrevIndex], v.fPosition, v.fPrevIndex, v.fIndex);
- if (!sweepLine.remove(edge)) {
- break;
- }
- } else {
+ // both to the right -- insert both
+ if (v.fFlags == 0) {
if (!sweepLine.insert(v.fPosition, polygon[v.fPrevIndex], v.fIndex, v.fPrevIndex)) {
break;
}
- }
-
- // check edge to next vertex
- if (v.fFlags & kNextLeft_VertexFlag) {
- ActiveEdge edge(polygon[v.fNextIndex], v.fPosition, v.fNextIndex, v.fIndex);
- if (!sweepLine.remove(edge)) {
- break;
- }
- } else {
if (!sweepLine.insert(v.fPosition, polygon[v.fNextIndex], v.fIndex, v.fNextIndex)) {
break;
}
+ // both to the left -- remove both
+ } else if (v.fFlags == (kPrevLeft_VertexFlag | kNextLeft_VertexFlag)) {
+ if (!sweepLine.remove(polygon[v.fPrevIndex], v.fPosition, v.fPrevIndex, v.fIndex)) {
+ break;
+ }
+ if (!sweepLine.remove(polygon[v.fNextIndex], v.fPosition, v.fNextIndex, v.fIndex)) {
+ break;
+ }
+ // one to left and right -- replace one with another
+ } else {
+ if (v.fFlags & kPrevLeft_VertexFlag) {
+ if (!sweepLine.replace(polygon[v.fPrevIndex], v.fPosition, polygon[v.fNextIndex],
+ v.fPrevIndex, v.fIndex, v.fNextIndex)) {
+ break;
+ }
+ } else {
+ SkASSERT(v.fFlags & kNextLeft_VertexFlag);
+ if (!sweepLine.replace(polygon[v.fNextIndex], v.fPosition, polygon[v.fPrevIndex],
+ v.fNextIndex, v.fIndex, v.fPrevIndex)) {
+ break;
+ }
+ }
}
vertexQueue.pop();