Lines Matching full:edge
42 * Stages (4) and (5) use an active edge list -- a list of all edges for which the
51 * not exact and may violate the mesh topology or active edge list ordering. We
55 * A) Intersections may cause a shortened edge to no longer be ordered with respect to its
58 * B) Intersections may cause an edge to violate the left-to-right ordering of the
59 * active edge list. This is handled by detecting potential violations and rewinding
60 * the active edge list to the vertex before they occur (rewind() during merging,
65 * currently uses a linked list for the active edge list, rather than a 2-3 tree as the
70 * are O(1), since we know the adjacent edge in the active edge list based on the topology.
96 struct Edge;
132 * circularly-linked list of Vertices for each contour. After edge construction, the same Vertices
156 Edge* fFirstEdgeAbove; // Linked list of edges above this vertex.
157 Edge* fLastEdgeAbove; // "
158 Edge* fFirstEdgeBelow; // Linked list of edges below this vertex.
159 Edge* fLastEdgeBelow; // "
160 Edge* fLeftEnclosingEdge; // Nearest edge in the AEL left of this vertex.
161 Edge* fRightEnclosingEdge; // Nearest edge in the AEL right of this vertex.
310 * An Edge joins a top Vertex to a bottom Vertex. Edge ordering for the list of "edges above" and
311 * "edge below" a vertex as well as for the active edge list is handled by isLeftOf()/isRightOf().
312 * Note that an Edge will give occasionally dist() != 0 for its own endpoints (because floating
327 struct Edge {
329 Edge(Vertex* top, Vertex* bottom, int winding, Type type)
350 int fWinding; // 1 == edge goes downward; -1 = edge goes upward.
354 Edge* fLeft; // The linked list of edges in the active edge list.
355 Edge* fRight; // "
356 Edge* fPrevEdgeAbove; // The linked list of edges in the bottom Vertex's "edges above".
357 Edge* fNextEdgeAbove; // "
358 Edge* fPrevEdgeBelow; // The linked list of edges in the top Vertex's "edges below".
359 Edge* fNextEdgeBelow; // "
360 Poly* fLeftPoly; // The Poly to the left of this edge, if any.
361 Poly* fRightPoly; // The Poly to the right of this edge, if any.
362 Edge* fLeftPolyPrev;
363 Edge* fLeftPolyNext;
364 Edge* fRightPolyPrev;
365 Edge* fRightPolyNext;
381 bool intersect(const Edge& other, SkPoint* p, uint8_t* alpha = nullptr) {
424 Edge* fHead;
425 Edge* fTail;
426 void insert(Edge* edge, Edge* prev, Edge* next) {
427 list_insert<Edge, &Edge::fLeft, &Edge::fRight>(edge, prev, next, &fHead, &fTail);
429 void append(Edge* e) {
432 void remove(Edge* edge) {
433 list_remove<Edge, &Edge::fLeft, &Edge::fRight>(edge, &fHead, &fTail);
446 bool contains(Edge* edge) const {
447 return edge->fLeft || edge->fRight || fHead == edge;
471 MonotonePoly(Edge* edge, Side side)
477 this->addEdge(edge);
480 Edge* fFirstEdge;
481 Edge* fLastEdge;
484 void addEdge(Edge* edge) {
486 SkASSERT(!edge->fUsedInRightPoly);
487 list_insert<Edge, &Edge::fRightPolyPrev, &Edge::fRightPolyNext>(
488 edge, fLastEdge, nullptr, &fFirstEdge, &fLastEdge);
489 edge->fUsedInRightPoly = true;
491 SkASSERT(!edge->fUsedInLeftPoly);
492 list_insert<Edge, &Edge::fLeftPolyPrev, &Edge::fLeftPolyNext>(
493 edge, fLastEdge, nullptr, &fFirstEdge, &fLastEdge);
494 edge->fUsedInLeftPoly = true;
499 Edge* e = fFirstEdge;
544 Poly* addEdge(Edge* e, Side side, SkArenaAlloc& alloc) {
570 e = alloc.make<Edge>(fTail->fLastEdge->fBottom, e->fBottom, 1, Edge::Type::kInner);
775 Edge* new_edge(Vertex* prev, Vertex* next, Edge::Type type, Comparator& c, SkArenaAlloc& alloc) {
779 return alloc.make<Edge>(top, bottom, winding, type);
782 void remove_edge(Edge* edge, EdgeList* edges) {
783 LOG("removing edge %g -> %g\n", edge->fTop->fID, edge->fBottom->fID);
784 SkASSERT(edges->contains(edge));
785 edges->remove(edge);
788 void insert_edge(Edge* edge, Edge* prev, EdgeList* edges) {
789 LOG("inserting edge %g -> %g\n", edge->fTop->fID, edge->fBottom->fID);
790 SkASSERT(!edges->contains(edge));
791 Edge* next = prev ? prev->fRight : edges->fHead;
792 edges->insert(edge, prev, next);
795 void find_enclosing_edges(Vertex* v, EdgeList* edges, Edge** left, Edge** right) {
801 Edge* next = nullptr;
802 Edge* prev;
813 void insert_edge_above(Edge* edge, Vertex* v, Comparator& c) {
814 if (edge->fTop->fPoint == edge->fBottom->fPoint ||
815 c.sweep_lt(edge->fBottom->fPoint, edge->fTop->fPoint)) {
818 LOG("insert edge (%g -> %g) above vertex %g\n", edge->fTop->fID, edge->fBottom->fID, v->fID);
819 Edge* prev = nullptr;
820 Edge* next;
822 if (next->isRightOf(edge->fTop)) {
827 list_insert<Edge, &Edge::fPrevEdgeAbove, &Edge::fNextEdgeAbove>(
828 edge, prev, next, &v->fFirstEdgeAbove, &v->fLastEdgeAbove);
831 void insert_edge_below(Edge* edge, Vertex* v, Comparator& c) {
832 if (edge->fTop->fPoint == edge->fBottom->fPoint ||
833 c.sweep_lt(edge->fBottom->fPoint, edge->fTop->fPoint)) {
836 LOG("insert edge (%g -> %g) below vertex %g\n", edge->fTop->fID, edge->fBottom->fID, v->fID);
837 Edge* prev = nullptr;
838 Edge* next;
840 if (next->isRightOf(edge->fBottom)) {
845 list_insert<Edge, &Edge::fPrevEdgeBelow, &Edge::fNextEdgeBelow>(
846 edge, prev, next, &v->fFirstEdgeBelow, &v->fLastEdgeBelow);
849 void remove_edge_above(Edge* edge) {
850 LOG("removing edge (%g -> %g) above vertex %g\n", edge->fTop->fID, edge->fBottom->fID,
851 edge->fBottom->fID);
852 list_remove<Edge, &Edge::fPrevEdgeAbove, &Edge::fNextEdgeAbove>(
853 edge, &edge->fBottom->fFirstEdgeAbove, &edge->fBottom->fLastEdgeAbove);
856 void remove_edge_below(Edge* edge) {
857 LOG("removing edge (%g -> %g) below vertex %g\n", edge->fTop->fID, edge->fBottom->fID,
858 edge->fTop->fID);
859 list_remove<Edge, &Edge::fPrevEdgeBelow, &Edge::fNextEdgeBelow>(
860 edge, &edge->fTop->fFirstEdgeBelow, &edge->fTop->fLastEdgeBelow);
863 void disconnect(Edge* edge)
865 remove_edge_above(edge);
866 remove_edge_below(edge);
869 void merge_collinear_edges(Edge* edge, EdgeList* activeEdges, Vertex** current, Comparator& c);
879 for (Edge* e = v->fFirstEdgeBelow; e; e = e->fNextEdgeBelow) {
882 Edge* leftEdge = v->fLeftEnclosingEdge;
883 for (Edge* e = v->fFirstEdgeAbove; e; e = e->fNextEdgeAbove) {
891 void rewind_if_necessary(Edge* edge, EdgeList* activeEdges, Vertex** current, Comparator& c) {
895 Vertex* top = edge->fTop;
896 Vertex* bottom = edge->fBottom;
897 if (edge->fLeft) {
898 Vertex* leftTop = edge->fLeft->fTop;
899 Vertex* leftBottom = edge->fLeft->fBottom;
900 if (c.sweep_lt(leftTop->fPoint, top->fPoint) && !edge->fLeft->isLeftOf(top)) {
902 } else if (c.sweep_lt(top->fPoint, leftTop->fPoint) && !edge->isRightOf(leftTop)) {
905 !edge->fLeft->isLeftOf(bottom)) {
907 } else if (c.sweep_lt(leftBottom->fPoint, bottom->fPoint) && !edge->isRightOf(leftBottom)) {
911 if (edge->fRight) {
912 Vertex* rightTop = edge->fRight->fTop;
913 Vertex* rightBottom = edge->fRight->fBottom;
914 if (c.sweep_lt(rightTop->fPoint, top->fPoint) && !edge->fRight->isRightOf(top)) {
916 } else if (c.sweep_lt(top->fPoint, rightTop->fPoint) && !edge->isLeftOf(rightTop)) {
919 !edge->fRight->isRightOf(bottom)) {
922 !edge->isLeftOf(rightBottom)) {
928 void set_top(Edge* edge, Vertex* v, EdgeList* activeEdges, Vertex** current, Comparator& c) {
929 remove_edge_below(edge);
930 edge->fTop = v;
931 edge->recompute();
932 insert_edge_below(edge, v, c);
933 rewind_if_necessary(edge, activeEdges, current, c);
934 merge_collinear_edges(edge, activeEdges, current, c);
937 void set_bottom(Edge* edge, Vertex* v, EdgeList* activeEdges, Vertex** current, Comparator& c) {
938 remove_edge_above(edge);
939 edge->fBottom = v;
940 edge->recompute();
941 insert_edge_above(edge, v, c);
942 rewind_if_necessary(edge, activeEdges, current, c);
943 merge_collinear_edges(edge, activeEdges, current, c);
946 void merge_edges_above(Edge* edge, Edge* other, EdgeList* activeEdges, Vertex** current,
948 if (coincident(edge->fTop->fPoint, other->fTop->fPoint)) {
950 edge->fTop->fPoint.fX, edge->fTop->fPoint.fY,
951 edge->fBottom->fPoint.fX, edge->fBottom->fPoint.fY);
952 rewind(activeEdges, current, edge->fTop, c);
953 other->fWinding += edge->fWinding;
954 disconnect(edge);
955 } else if (c.sweep_lt(edge->fTop->fPoint, other->fTop->fPoint)) {
956 rewind(activeEdges, current, edge->fTop, c);
957 other->fWinding += edge->fWinding;
958 set_bottom(edge, other->fTop, activeEdges, current, c);
961 edge->fWinding += other->fWinding;
962 set_bottom(other, edge->fTop, activeEdges, current, c);
966 void merge_edges_below(Edge* edge, Edge* other, EdgeList* activeEdges, Vertex** current,
968 if (coincident(edge->fBottom->fPoint, other->fBottom->fPoint)) {
970 edge->fTop->fPoint.fX, edge->fTop->fPoint.fY,
971 edge->fBottom->fPoint.fX, edge->fBottom->fPoint.fY);
972 rewind(activeEdges, current, edge->fTop, c);
973 other->fWinding += edge->fWinding;
974 disconnect(edge);
975 } else if (c.sweep_lt(edge->fBottom->fPoint, other->fBottom->fPoint)) {
977 edge->fWinding += other->fWinding;
978 set_top(other, edge->fBottom, activeEdges, current, c);
980 rewind(activeEdges, current, edge->fTop, c);
981 other->fWinding += edge->fWinding;
982 set_top(edge, other->fBottom, activeEdges, current, c);
986 void merge_collinear_edges(Edge* edge, EdgeList* activeEdges, Vertex** current, Comparator& c) {
988 if (edge->fPrevEdgeAbove && (edge->fTop == edge->fPrevEdgeAbove->fTop ||
989 !edge->fPrevEdgeAbove->isLeftOf(edge->fTop))) {
990 merge_edges_above(edge, edge->fPrevEdgeAbove, activeEdges, current, c);
991 } else if (edge->fNextEdgeAbove && (edge->fTop == edge->fNextEdgeAbove->fTop ||
992 !edge->isLeftOf(edge->fNextEdgeAbove->fTop))) {
993 merge_edges_above(edge, edge->fNextEdgeAbove, activeEdges, current, c);
994 } else if (edge->fPrevEdgeBelow && (edge->fBottom == edge->fPrevEdgeBelow->fBottom ||
995 !edge->fPrevEdgeBelow->isLeftOf(edge->fBottom))) {
996 merge_edges_below(edge, edge->fPrevEdgeBelow, activeEdges, current, c);
997 } else if (edge->fNextEdgeBelow && (edge->fBottom == edge->fNextEdgeBelow->fBottom ||
998 !edge->isLeftOf(edge->fNextEdgeBelow->fBottom))) {
999 merge_edges_below(edge, edge->fNextEdgeBelow, activeEdges, current, c);
1004 SkASSERT(!edge->fPrevEdgeAbove || edge->fPrevEdgeAbove->isLeftOf(edge->fTop));
1005 SkASSERT(!edge->fPrevEdgeBelow || edge->fPrevEdgeBelow->isLeftOf(edge->fBottom));
1006 SkASSERT(!edge->fNextEdgeAbove || edge->fNextEdgeAbove->isRightOf(edge->fTop));
1007 SkASSERT(!edge->fNextEdgeBelow || edge->fNextEdgeBelow->isRightOf(edge->fBottom));
1010 void split_edge(Edge* edge, Vertex* v, EdgeList* activeEdges, Vertex** current, Comparator& c,
1012 if (v == edge->fTop || v == edge->fBottom) {
1015 LOG("splitting edge (%g -> %g) at vertex %g (%g, %g)\n",
1016 edge->fTop->fID, edge->fBottom->fID,
1020 if (c.sweep_lt(v->fPoint, edge->fTop->fPoint)) {
1022 bottom = edge->fTop;
1023 set_top(edge, v, activeEdges, current, c);
1024 } else if (c.sweep_lt(edge->fBottom->fPoint, v->fPoint)) {
1025 top = edge->fBottom;
1027 set_bottom(edge, v, activeEdges, current, c);
1030 bottom = edge->fBottom;
1031 set_bottom(edge, v, activeEdges, current, c);
1033 Edge* newEdge = alloc.make<Edge>(top, bottom, edge->fWinding, edge->fType);
1039 Edge* connect(Vertex* prev, Vertex* next, Edge::Type type, Comparator& c, SkArenaAlloc& alloc,
1041 Edge* edge = new_edge(prev, next, type, c, alloc);
1042 insert_edge_below(edge, edge->fTop, c);
1043 insert_edge_above(edge, edge->fBottom, c);
1044 edge->fWinding *= winding_scale;
1045 merge_collinear_edges(edge, nullptr, nullptr, c);
1046 return edge;
1057 for (Edge* edge = src->fFirstEdgeAbove; edge;) {
1058 Edge* next = edge->fNextEdgeAbove;
1059 set_bottom(edge, dst, nullptr, nullptr, c);
1060 edge = next;
1062 for (Edge* edge = src->fFirstEdgeBelow; edge;) {
1063 Edge* next = edge->fNextEdgeBelow;
1064 set_top(edge, dst, nullptr, nullptr, c);
1065 edge = next;
1070 uint8_t max_edge_alpha(Edge* a, Edge* b) {
1071 if (a->fType == Edge::Type::kInner || b->fType == Edge::Type::kInner) {
1073 } else if (a->fType == Edge::Type::kOuter && b->fType == Edge::Type::kOuter) {
1081 bool check_for_intersection(Edge* edge, Edge* other, EdgeList* activeEdges, Vertex** current,
1083 if (!edge || !other) {
1088 if (edge->intersect(*other, &p, &alpha) && p.isFinite()) {
1097 if (p == edge->fTop->fPoint) {
1098 v = edge->fTop;
1099 } else if (p == edge->fBottom->fPoint) {
1100 v = edge->fBottom;
1131 split_edge(edge, v, activeEdges, current, c, alloc);
1183 connect(prev, v, Edge::Type::kInner, c, alloc);
1196 connect(outer, inner, Edge::Type::kConnector, c, alloc, 0);
1274 Edge* leftEnclosingEdge;
1275 Edge* rightEnclosingEdge;
1290 for (Edge* edge = v->fFirstEdgeBelow; edge; edge = edge->fNextEdgeBelow) {
1291 edge, leftEnclosingEdge, &activeEdges, &v, mesh, c,
1296 if (check_for_intersection(edge, rightEnclosingEdge, &activeEdges, &v, mesh, c,
1316 for (Edge* e = v->fFirstEdgeAbove; e; e = e->fNextEdgeAbove) {
1319 Edge* leftEdge = leftEnclosingEdge;
1320 for (Edge* e = v->fFirstEdgeBelow; e; e = e->fNextEdgeBelow) {
1336 Edge* leftEnclosingEdge;
1337 Edge* rightEnclosingEdge;
1341 for (Edge* edge = v->fFirstEdgeBelow; edge; edge = edge->fNextEdgeBelow) {
1342 if (edge && leftEnclosingEdge && edge->intersect(*leftEnclosingEdge, &dummy)) {
1346 if (edge && rightEnclosingEdge && edge->intersect(*rightEnclosingEdge, &dummy)) {
1356 for (Edge* e = v->fFirstEdgeAbove; e; e = e->fNextEdgeAbove) {
1359 Edge* leftEdge = leftEnclosingEdge;
1360 for (Edge* e = v->fFirstEdgeBelow; e; e = e->fNextEdgeBelow) {
1382 Edge* leftEnclosingEdge;
1383 Edge* rightEnclosingEdge;
1396 for (Edge* e = v->fFirstEdgeAbove; e; e = e->fNextEdgeAbove) {
1401 for (Edge* e = v->fFirstEdgeBelow; e; e = e->fNextEdgeBelow) {
1413 for (Edge* e = v->fFirstEdgeAbove; e != v->fLastEdgeAbove; e = e->fNextEdgeAbove) {
1414 Edge* rightEdge = e->fNextEdgeAbove;
1446 Edge* join = alloc.make<Edge>(leftPoly->lastVertex(), v, 1, Edge::Type::kInner);
1451 Edge* leftEdge = v->fFirstEdgeBelow;
1454 for (Edge* rightEdge = leftEdge->fNextEdgeBelow; rightEdge;
1469 for (Edge* e = activeEdges.fHead; e != nullptr; e = e->fRight) {
1486 Edge* leftEnclosingEdge;
1487 Edge* rightEnclosingEdge;
1491 for (Edge* e = v->fFirstEdgeAbove; e;) {
1492 Edge* next = e->fNextEdgeAbove;
1501 Edge* prev = leftEnclosingEdge;
1502 for (Edge* e = v->fFirstEdgeBelow; e; e = e->fNextEdgeBelow) {
1512 // Note: this is the normal to the edge, but not necessarily unit length.
1513 void get_edge_normal(const Edge* e, SkVector* normal) {
1518 // Stage 5c: detect and remove "pointy" vertices whose edge normals point in opposite directions
1519 // and whose adjacent vertices are less than a quarter pixel from an edge. These are guaranteed to
1523 Edge* prevEdge = boundary->fTail;
1526 for (Edge* e = boundary->fHead; e != nullptr;) {
1534 Edge* join = new_edge(prev, next, Edge::Type::kInner, c, alloc);
1554 void fix_inversions(Vertex* prev, Vertex* next, Edge* prevBisector, Edge* nextBisector,
1555 Edge* prevEdge, Comparator& c) {
1578 Edge* prevEdge = boundary->fTail;
1587 Edge* prevBisector = nullptr;
1588 for (Edge* e = boundary->fHead; e != nullptr; e = e->fRight) {
1599 Edge* bisector = new_edge(outerVertex, innerVertex, Edge::Type::kConnector, c, alloc);
1618 Edge* bisector = new_edge(outerVertices.fHead, innerVertices.fHead, Edge::Type::kConnector, c,
1628 connect(prevOuterVertex, outerVertex, Edge::Type::kOuter, c, alloc);
1629 connect(prevInnerVertex, innerVertex, Edge::Type::kInner, c, alloc, -2);
1639 void extract_boundary(EdgeList* boundary, Edge* e, SkPath::FillType fillType, SkArenaAlloc& alloc) {
1643 Edge* next;
1646 // Find outgoing edge, in clockwise order.
1655 // Find outgoing edge, in counter-clockwise order.
1807 for (Edge* e = v->fFirstEdgeBelow; e; e = e->fNextEdgeBelow) {
1816 for (Edge* e = v->fFirstEdgeBelow; e; e = e->fNextEdgeBelow) {
